3D grafička Java: Renderirajte fraktalne krajolike

3D računalna grafika ima mnogo primjena - od igara do vizualizacije podataka, virtualne stvarnosti i šire. Češće je brzina najvažnija, zbog čega specijalizirani softver i hardver moraju biti obavljeni. Grafičke knjižnice za posebne namjene pružaju API na visokoj razini, ali skrivaju kako se pravi posao radi. Međutim, kao programeri od nosa do metala, to nije dovoljno dobro za nas! Stavit ćemo API u ormar i pogledati iza kulisa kako se slike zapravo generiraju - od definicije virtualnog modela do stvarnog prikazivanja na ekranu.

Promatrat ćemo prilično specifičnu temu: generiranje i prikazivanje karata terena, poput površine Marsa ili nekoliko atoma zlata. Prikaz terena s kartama može se koristiti u više od samo estetske svrhe - mnoge tehnike vizualizacije podataka daju podatke koji se mogu prikazati kao karte terena. Moje namjere su, naravno, u potpunosti umjetničke, kao što vidite na donjoj slici! Ako tako želite, kôd koji ćemo proizvesti dovoljno je općenit da se uz samo manja podešavanja može koristiti i za generiranje 3D struktura osim terena.

Kliknite ovdje za prikaz i manipulaciju apletom terena.

Kao pripremu za našu današnju raspravu, predlažem da pročitate lipanjsku "Nacrtajte teksturirane sfere" ako to već niste učinili. Članak pokazuje pristup praćenju zraka pri prikazivanju slika (ispaljivanje zraka u virtualnu scenu radi stvaranja slike). U ovom ćemo članku prikazivati ​​elemente scene izravno na zaslon. Iako koristimo dvije različite tehnike, prvi članak sadrži neke pozadinske materijale na java.awt.imagepakiranju koje neću ponavljati u ovoj raspravi.

Karte terena

Počnimo s definiranjem a

karta terena

. Karta terena je funkcija koja preslikava 2D koordinate

(x, y)

do nadmorske visine

a

i boja

c

. Drugim riječima, karta terena jednostavno je funkcija koja opisuje topografiju malog područja.

Definirajmo svoj teren kao sučelje:

javno sučelje Terrain {javni dvostruki getAltitude (dvostruki i, dvostruki j); javni RGB getColor (dvostruki i, dvostruki j); }

U svrhu ovog članka pretpostavit ćemo da je 0,0 <= i, j, nadmorska visina <= 1,0 . To nije uvjet, ali dat će nam dobru ideju gdje pronaći teren koji ćemo gledati.

Boja našeg terena opisana je jednostavno kao RGB trojka. Da bismo stvorili zanimljivije slike, mogli bismo razmotriti dodavanje drugih podataka kao što je sjaj površine itd. Za sada, međutim, sljedeće će klase raditi:

javna klasa RGB {private double r, g, b; javni RGB (dvostruki r, dvostruki g, dvostruki b) {this.r = r; ovo.g = g; ovo.b = b; } javni RGB dodatak (RGB rgb) {vrati novi RGB (r + rgb.r, g + rgb.g, b + rgb.b); } javni RGB oduzimanje (RGB rgb) {vratiti novi RGB (r - rgb.r, g - rgb.g, b - rgb.b); } javna RGB ljestvica (dvostruka skala) {vrati novu RGB (r * ljestvica, g * ljestvica, b * ljestvica); } private int toInt (dvostruka vrijednost) {return (vrijednost 1.0)? 255: (int) (vrijednost * 255,0); } javni int toRGB () toInt (b); }

RGBKlasa definira jednostavan spremnik u boji. Pružamo neke osnovne mogućnosti za izvođenje aritmetike boja i pretvaranje boje s pomičnom zarezom u format s spakiranim cijelim brojevima.

Transcendentalni tereni

Za početak ćemo pogledati transcendentalni teren - fancyspeak za teren izračunat iz sinusa i kosinusa:

javna klasa TranscendentalTerrain implementira Terrain {private double alpha, beta; javni TranscendentalTerrain (dvostruka alfa, dvostruka beta) {this.alpha = alfa; this.beta = beta; } public double getAltitude (double i, double j) {return .5 + .5 * Math.sin (i * alpha) * Math.cos (j * beta); } javni RGB getColor (dvostruki i, dvostruki j) {vrati novi RGB (.5 + .5 * Math.sin (i * alpha), .5 - .5 * Math.cos (j * beta), 0.0); }}

Naš konstruktor prihvaća dvije vrijednosti koje definiraju učestalost našeg terena. Koristimo ih za izračunavanje nadmorske visine i boja pomoću Math.sin()i Math.cos(). Zapamtite, te funkcije vraćaju vrijednosti -1,0 <= sin (), cos () <= 1,0 , pa svoje povratne vrijednosti moramo prilagoditi u skladu s tim.

Fraktalni tereni

Jednostavni matematički tereni nisu zabava. Ono što želimo je nešto što izgleda barem prolazno stvarno. Kao mapu terena mogli bismo koristiti stvarne topografske datoteke (primjerice zaljev San Francisco ili površina Marsa). Iako je ovo jednostavno i praktično, donekle je dosadno. Mislim, jesmo

bio

tamo. Ono što zapravo želimo je nešto što izgleda prolazno stvarno

i

nikada prije nije viđena. Uđite u svijet fraktala.

Fraktal je nešto (funkcija ili objekt) što pokazuje samo-sličnost . Na primjer, Mandelbrotov skup je fraktalna funkcija: ako uvelike povećate Mandelbrotov skup, pronaći ćete malene unutarnje strukture koje nalikuju samom Mandelbrotu. Planinski lanac je također fraktan, barem na izgled. Iz blizine, male značajke pojedine planine nalikuju velikim značajkama planinskog lanca, čak i do hrapavosti pojedinih gromada. Slijedit ćemo ovaj princip samo-sličnosti kako bismo generirali naše fraktalne terene.

U osnovi ono što ćemo učiniti je generiranje grubog, početnog slučajnog terena. Tada ćemo rekurzivno dodavati dodatne slučajne detalje koji oponašaju strukturu cjeline, ali na sve manjim razmjerima. Stvarni algoritam koji ćemo koristiti, algoritam Diamond Square, izvorno su opisali Fournier, Fussell i Carpenter 1982. (za detalje pogledajte Resurse).

Ovo su koraci na kojima ćemo raditi za izgradnju našeg fraktalnog terena:

  1. Prvo dodijelimo slučajnu visinu na četiri kutne točke mreže.

  2. Zatim uzmemo prosjek ova četiri kuta, dodamo slučajno uznemirenje i dodijelimo to središnjoj točki rešetke ( ii u sljedećem dijagramu). To se naziva dijamantnim korakom jer stvaramo dijamantni uzorak na mreži. (U prvoj iteraciji dijamanti ne izgledaju poput dijamanata jer su na rubu rešetke; ali ako pogledate dijagram, razumjet ćete na što ciljam.)

  3. Zatim uzmemo svaki dijamant koji smo proizveli, prosječimo četiri kuta, dodamo slučajno uznemirenje i dodijelimo to dijamantnoj sredini ( iii u sljedećem dijagramu). To se naziva kvadratni korak jer stvaramo kvadratni uzorak na mreži.

  4. Dalje, dijamantni korak ponovno primjenjujemo na svaki kvadrat koji smo stvorili u kvadratnom koraku, a zatim ponovno primjenjujemo kvadratni korak na svaki dijamant koji smo stvorili u dijamantnom koraku, i tako sve dok naša mreža ne postane dovoljno gusta.

Postavlja se očito pitanje: Koliko uznemiravamo mrežu? Odgovor je da započinjemo s koeficijentom hrapavosti 0,0 <hrapavost <1,0 . U iteraciji n našeg algoritma Diamond-Square dodamo slučajnu perturbaciju u mrežu: -roughnessn <= perturbacija <= hrapavostn . U osnovi, dodavanjem sitnijih detalja mreži smanjujemo opseg promjena koje unosimo. Male promjene u malom opsegu fraktalno su slične velikim promjenama u većem opsegu.

If we choose a small value for roughness, then our terrain will be very smooth -- the changes will very rapidly diminish to zero. If we choose a large value, then the terrain will be very rough, as the changes remain significant at small grid divisions.

Here's the code to implement our fractal terrain map:

public class FractalTerrain implements Terrain { private double[][] terrain; private double roughness, min, max; private int divisions; private Random rng; public FractalTerrain (int lod, double roughness) { this.roughness = roughness; this.divisions = 1 << lod; terrain = new double[divisions + 1][divisions + 1]; rng = new Random (); terrain[0][0] = rnd (); terrain[0][divisions] = rnd (); terrain[divisions][divisions] = rnd (); terrain[divisions][0] = rnd (); double rough = roughness; for (int i = 0; i < lod; ++ i) { int q = 1 << i, r = 1 <> 1; for (int j = 0; j < divisions; j += r) for (int k = 0; k  0) for (int j = 0; j <= divisions; j += s) for (int k = (j + s) % r; k <= divisions; k += r) square (j - s, k - s, r, rough); rough *= roughness; } min = max = terrain[0][0]; for (int i = 0; i <= divisions; ++ i) for (int j = 0; j <= divisions; ++ j) if (terrain[i][j]  max) max = terrain[i][j]; } private void diamond (int x, int y, int side, double scale) { if (side > 1) { int half = side / 2; double avg = (terrain[x][y] + terrain[x + side][y] + terrain[x + side][y + side] + terrain[x][y + side]) * 0.25; terrain[x + half][y + half] = avg + rnd () * scale; } } private void square (int x, int y, int side, double scale) { int half = side / 2; double avg = 0.0, sum = 0.0; if (x >= 0) { avg += terrain[x][y + half]; sum += 1.0; } if (y >= 0) { avg += terrain[x + half][y]; sum += 1.0; } if (x + side <= divisions) { avg += terrain[x + side][y + half]; sum += 1.0; } if (y + side <= divisions) { avg += terrain[x + half][y + side]; sum += 1.0; } terrain[x + half][y + half] = avg / sum + rnd () * scale; } private double rnd () { return 2. * rng.nextDouble () - 1.0; } public double getAltitude (double i, double j) { double alt = terrain[(int) (i * divisions)][(int) (j * divisions)]; return (alt - min) / (max - min); } private RGB blue = new RGB (0.0, 0.0, 1.0); private RGB green = new RGB (0.0, 1.0, 0.0); private RGB white = new RGB (1.0, 1.0, 1.0); public RGB getColor (double i, double j) { double a = getAltitude (i, j); if (a < .5) return blue.add (green.subtract (blue).scale ((a - 0.0) / 0.5)); else return green.add (white.subtract (green).scale ((a - 0.5) / 0.5)); } } 

In the constructor, we specify both the roughness coefficient roughness and the level of detail lod. The level of detail is the number of iterations to perform -- for a level of detail n, we produce a grid of (2n+1 x 2n+1) samples. For each iteration, we apply the diamond step to each square in the grid and then the square step to each diamond. Afterwards, we compute the minimum and maximum sample values, which we'll use to scale our terrain altitudes.

To compute the altitude of a point, we scale and return the closest grid sample to the requested location. Ideally, we would actually interpolate between surrounding sample points, but this method is simpler, and good enough at this point. In our final application this issue will not arise because we will actually match the locations where we sample the terrain to the level of detail that we request. To color our terrain, we simply return a value between blue, green, and white, depending upon the altitude of the sample point.

Tessellating our terrain

We now have a terrain map defined over a square domain. We need to decide how we are going to actually draw this onto the screen. We could fire rays into the world and try to determine which part of the terrain they strike, as we did in the previous article. This approach would, however, be extremely slow. What we'll do instead is approximate the smooth terrain with a bunch of connected triangles -- that is, we'll tessellate our terrain.

Tessellate: to form into or adorn with mosaic (from the Latin tessellatus).

To form the triangle mesh, we will evenly sample our terrain into a regular grid and then cover this grid with triangles -- two for each square of the grid. There are many interesting techniques that we could use to simplify this triangle mesh, but we'd only need those if speed was a concern.

The following code fragment populates the elements of our terrain grid with fractal terrain data. We scale down the vertical axis of our terrain to make the altitudes a bit less exaggerated.

double exaggeration = .7; int lod = 5; int steps = 1 << lod; Triple[] map = new Triple[steps + 1][steps + 1]; Triple[] colors = new RGB[steps + 1][steps + 1]; Terrain terrain = new FractalTerrain (lod, .5); for (int i = 0; i <= steps; ++ i) { for (int j = 0; j <= steps; ++ j) { double x = 1.0 * i / steps, z = 1.0 * j / steps; double altitude = terrain.getAltitude (x, z); map[i][j] = new Triple (x, altitude * exaggeration, z); colors[i][j] = terrain.getColor (x, z); } } 

Možda se pitate: Pa zašto onda trokuti, a ne kvadrati? Problem korištenja kvadrata mreže je taj što nisu ravni u 3D prostoru. Ako uzmete u obzir četiri slučajne točke u svemiru, krajnje je malo vjerojatno da će biti koplanarne. Umjesto toga, svoj teren raščlanjujemo na trokute jer možemo jamčiti da će bilo koje tri točke u prostoru biti koplanarne. To znači da na terenu neće biti praznina koje ćemo na kraju iscrtati.