Programmering

3D-grafisk Java: gengiv fraktallandskaber

3D-computergrafik har mange anvendelser - fra spil til datavisualisering, virtual reality og videre. Oftere end ikke er hastighed af største betydning, hvilket gør specialsoftware og hardware til et must for at få arbejdet gjort. Specielle grafikbiblioteker leverer et API på højt niveau, men skjuler hvordan det virkelige arbejde udføres. Som næse-til-metal-programmører er det dog ikke godt nok for os! Vi skal sætte API'en i skabet og se bag kulisserne på, hvordan billeder faktisk genereres - fra definitionen af ​​en virtuel model til dens faktiske gengivelse på skærmen.

Vi ser på et ret specifikt emne: generering og gengivelse af terrænkort, såsom Mars overflade eller et par atomer af guld. Terrænkortgengivelse kan bruges til mere end bare æstetiske formål - mange datavisualiseringsteknikker producerer data, der kan gengives som terrænkort. Mine intentioner er selvfølgelig helt kunstneriske, som du kan se på billedet nedenfor! Hvis du ønsker det, er koden, som vi producerer, generel nok til, at den med kun mindre tilpasning også kan bruges til at gengive andre 3D-strukturer end terræn.

Klik her for at se og manipulere terrænapplet.

Som forberedelse til vores diskussion i dag foreslår jeg, at du læser Junis "Tegn teksturerede kugler", hvis du ikke allerede har gjort det. Artiklen demonstrerer en strålesporingsmetode til gengivelse af billeder (skyder stråler ind i en virtuel scene for at producere et billede). I denne artikel gengiver vi sceneelementer direkte på skærmen. Selvom vi bruger to forskellige teknikker, indeholder den første artikel noget baggrundsmateriale om java.awt.billede pakke, som jeg ikke vil gentage i denne diskussion.

Terrænkort

Lad os starte med at definere en

terræn kort

. Et terrænkort er en funktion, der kortlægger en 2D-koordinat

(x, y)

til en højde

-en

og farve

c

. Med andre ord er et terrænkort simpelthen en funktion, der beskriver topografien i et lille område.

Lad os definere vores terræn som en grænseflade:

offentlig grænseflade Terræn {offentlig dobbelt getAltitude (dobbelt i, dobbelt j); offentlig RGB getColor (dobbelt i, dobbelt j); } 

Med henblik på denne artikel antager vi det 0,0 <= i, j, højde <= 1,0. Dette er ikke et krav, men det giver os en god idé, hvor vi finder det terræn, vi vil se på.

Farven på vores terræn er simpelthen beskrevet som en RGB-triplet. For at producere mere interessante billeder kan vi overveje at tilføje anden information såsom overfladens skinnende osv. Indtil videre vil følgende klasse dog gøre:

offentlig klasse RGB {privat dobbelt r, g, b; offentlig RGB (dobbelt r, dobbelt g, dobbelt b) {this.r = r; this.g = g; this.b = b; } offentlig RGB tilføj (RGB rgb) {returner ny RGB (r + rgb.r, g + rgb.g, b + rgb.b); } offentlig RGB-fratrækning (RGB rgb) {returner ny RGB (r - rgb.r, g - rgb.g, b - rgb.b); } offentlig RGB-skala (dobbelt skala) {returner ny RGB (r * skala, g * skala, b * skala); } privat int toInt (dobbelt værdi) {return (værdi 1.0)? 255: (int) (værdi * 255,0); } offentlig int toRGB () til Int (b); } 

Det RGB klasse definerer en simpel farvebeholder. Vi leverer nogle grundlæggende faciliteter til udførelse af farveregning og konvertering af en flydende punktfarve til pakket heltal-format.

Transcendentale terræn

Vi starter med at se på et transcendentalt terræn - fancyspeak for et terræn beregnet fra sines og cosinus:

offentlig klasse TranscendentalTerrain implementerer Terrain {privat dobbelt alfa, beta; offentlig TranscendentalTerrain (dobbelt alfa, dobbelt beta) {this.alpha = alpha; this.beta = beta; } offentlig dobbelt getAltitude (dobbelt i, dobbelt j) {return .5 + .5 * Math.sin (i * alpha) * Math.cos (j * beta); } offentlig RGB getColor (dobbelt i, dobbelt j) {returner ny RGB (.5 + .5 * Math.sin (i * alpha), .5 - .5 * Math.cos (j * beta), 0.0); }} 

Vores konstruktør accepterer to værdier, der definerer hyppigheden af ​​vores terræn. Vi bruger disse til at beregne højder og farver ved hjælp af Math.sin () og Math.cos (). Husk, at disse funktioner returnerer værdier -1,0 <= sin (), cos () <= 1,0, så vi skal justere vores returværdier i overensstemmelse hermed.

Fraktale terræn

Enkle matematiske terræn er ikke sjovt. Det, vi ønsker, er noget, der i det mindste ser rigtig godt ud. Vi kunne bruge ægte topografifiler som vores terrænkort (for eksempel San Francisco-bugten eller Mars overflade). Selvom dette er let og praktisk, er det noget kedeligt. Jeg mener, vi har

været

der. Hvad vi virkelig vil have, er noget, der ser utroligt rigtigt ud

og

har aldrig været set før. Gå ind i verdenen af ​​fraktaler.

En fraktal er noget (en funktion eller et objekt), der udviser selv-lighed. For eksempel er Mandelbrot-sættet en fraktal funktion: Hvis du forstørrer Mandelbrot-sættet meget, finder du små interne strukturer, der ligner selve Mandelbrot-hovedet. En bjergkæde er også fraktal, i det mindste i udseende. Fra nærbillede ligner små træk ved et individuelt bjerg store træk ved bjergkæden, selv ned til ruhed af enkelte stenblokke. Vi vil følge dette princip om selvlignelighed for at generere vores fraktale terræn.

I det væsentlige skal vi generere et groft, indledende tilfældigt terræn. Derefter tilføjer vi rekursivt yderligere tilfældige detaljer, der efterligner strukturen for det hele, men på stadig mindre skalaer. Den egentlige algoritme, som vi vil bruge, Diamond-Square-algoritmen, blev oprindeligt beskrevet af Fournier, Fussell og Carpenter i 1982 (se Ressourcer for detaljer).

Dette er de trin, vi arbejder igennem for at opbygge vores fraktale terræn:

  1. Vi tildeler først en tilfældig højde til de fire hjørnepunkter i et gitter.

  2. Vi tager derefter gennemsnittet af disse fire hjørner, tilføjer en tilfældig forstyrrelse og tildeler dette til gitterets midtpunkt (ii i det følgende diagram). Dette kaldes diamant trin, fordi vi skaber et diamantmønster på gitteret. (Ved den første iteration ser diamanterne ikke ud som diamanter, fordi de er ved kanten af ​​gitteret; men hvis du ser på diagrammet, forstår du, hvad jeg kommer til.)

  3. Derefter tager vi hver af de diamanter, vi har produceret, gennemsnittet af de fire hjørner, tilføjer en tilfældig forstyrrelse og tildeler dette til diamantmidepunktet (iii i det følgende diagram). Dette kaldes firkant trin, fordi vi opretter et kvadratisk mønster på gitteret.

  4. Dernæst anvender vi diamanttrinet igen på hver firkant, som vi oprettede i det firkantede trin, og derefter genanvender vi firkant gå til hver diamant, som vi skabte i diamanttrinnet, og så videre, indtil vores gitter er tilstrækkelig tæt.

Et oplagt spørgsmål opstår: Hvor meget forstyrrer vi nettet? Svaret er, at vi starter med en ruhedskoefficient 0,0 <ruhed <1,0. Ved iteration n af vores Diamond-Square-algoritme tilføjer vi en tilfældig forstyrrelse i nettet: -Throughnessn <= forstyrrelse <= ruhedn. Når vi tilføjer mere detaljerede detaljer til nettet, reducerer vi i det væsentlige omfanget af ændringer, vi foretager. Små ændringer i lille skala ligner fraktalt store ændringer i større skala.

Hvis vi vælger en lille værdi for ruhed, så vil vores terræn være meget glat - ændringerne vil hurtigt reduceres til nul. Hvis vi vælger en stor værdi, vil terrænet være meget groft, da ændringerne forbliver betydelige ved små netafdelinger.

Her er koden til implementering af vores fraktale terrænkort:

offentlig klasse FractalTerrain implementerer terræn {privat dobbelt [] [] terræn; privat dobbelt ruhed, min, max; private int divisioner; privat Tilfældig rng; offentlig FractalTerrain (int lod, dobbelt ruhed) {this.roughness = ruhed; denne opdeling = 1 << lod; terræn = ny dobbelt [division + 1] [division + 1]; rng = ny tilfældig (); terræn [0] [0] = rnd (); terræn [0] [divisioner] = rnd (); terræn [divisioner] [divisioner] = rnd (); terræn [divisioner] [0] = rnd (); dobbelt ru = ruhed; for (int i = 0; i <lod; ++ i) {int q = 1 << i, r = 1 <> 1; for (int j = 0; j <divisioner; j + = r) for (int k = 0; k 0) for (int j = 0; j <= divisioner; j + = s) for (int k = (j + s)% r; k <= divisioner; k + = r) firkant (j - s, k - s, r, ru); ru * = ruhed; } min = maks = terræn [0] [0]; for (int i = 0; i <= divisioner; ++ i) for (int j = 0; j <= divisioner; ++ j) hvis (terræn [i] [j] max) max = terræn [i] [ j]; } privat ugyldig diamant (int x, int y, int side, dobbelt skala) {if (side> 1) {int half = side / 2; dobbeltgennemsnit = (terræn [x] [y] + terræn [x + side] [y] + terræn [x + side] [y + side] + terræn [x] [y + side]) * 0,25; terræn [x + halv] [y + halv] = gennemsnit + rnd () * skala; }} privat ugyldig firkant (int x, int y, int side, dobbelt skala) {int half = side / 2; dobbeltgennemsnit = 0,0, sum = 0,0; hvis (x> = 0) {avg + = terræn [x] [y + halv]; sum + = 1,0; } hvis (y> = 0) {avg + = terræn [x + halv] [y]; sum + = 1,0; } hvis (x + side <= divisioner) {avg + = terræn [x + side] [y + halv]; sum + = 1,0; } hvis (y + side <= divisioner) {avg + = terræn [x + halv] [y + side]; sum + = 1,0; } terræn [x + halv] [y + halv] = gennemsnit / sum + rnd () * skala; } privat dobbeltrnd () {retur 2. * rng.nextDouble () - 1.0; } offentlig dobbelt getAltitude (dobbelt i, dobbelt j) {dobbelt alt = terræn [(int) (i * divisioner)] [(int) (j * divisioner)]; retur (alt - min) / (max - min); } privat RGB blå = ny RGB (0,0, 0,0, 1,0); privat RGB grøn = ny RGB (0,0, 1,0, 0,0); privat RGB hvid = ny RGB (1.0, 1.0, 1.0); offentlig RGB getColor (dobbelt i, dobbelt j) {dobbelt a = getAltitude (i, j); hvis (a <.5) returnerer blue.add (green.subtract (blå). skala ((a - 0.0) / 0.5)); ellers returner grønt. tilføj (hvid. trækker (grøn). skala ((a - 0,5) / 0,5)); }} 

I konstruktøren specificerer vi både ruhedskoefficienten ruhed og detaljeringsniveauet lod. Detaljeringsniveauet er antallet af iterationer, der skal udføres - for et detaljeringsniveau n, vi producerer et gitter af (2n + 1 x 2n + 1) prøver. For hver iteration anvender vi diamanttrinnet på hver firkant i gitteret og derefter det firkantede trin på hver diamant. Derefter beregner vi minimums- og maksimumprøveværdierne, som vi bruger til at skalere vores terrænhøjder.

For at beregne højden på et punkt skalerer og returnerer vi tættest gitterprøve til det ønskede sted. Ideelt set ville vi faktisk interpolere mellem omgivende prøvepunkter, men denne metode er enklere og god nok på dette tidspunkt. I vores endelige ansøgning opstår dette problem ikke, fordi vi faktisk vil matche de placeringer, hvor vi prøver terrænet til det detaljeringsniveau, vi anmoder om. For at farve vores terræn returnerer vi simpelthen en værdi mellem blå, grøn og hvid afhængigt af prøvepunktets højde.

Tessellating vores terræn

Vi har nu et terrænkort defineret over et kvadratisk domæne. Vi er nødt til at beslutte, hvordan vi rent faktisk tegner dette på skærmen. Vi kunne skyde stråler ud i verden og forsøge at bestemme, hvilken del af terrænet de rammer, som vi gjorde i den foregående artikel. Denne tilgang ville dog være ekstremt langsom. Hvad vi i stedet vil gøre, er at tilnærme det glatte terræn med en masse forbundne trekanter - det vil sige, at vi tessellerer vores terræn.

Tessellate: at forme til eller pryde med mosaik (fra latin tessellatus).

For at danne trekantsnettet prøver vi jævnt vores terræn i et almindeligt gitter og dækker derefter dette gitter med trekanter - to for hver firkant af gitteret. Der er mange interessante teknikker, som vi kunne bruge til at forenkle dette trekantnet, men vi havde kun brug for dem, hvis hastighed var et problem.

Følgende kodefragment udfylder elementerne i vores terrænnet med fraktale terrændata. Vi skalerer ned den lodrette akse i vores terræn for at gøre højderne lidt mindre overdrevne.

dobbelt overdrivelse = .7; int lod = 5; int trin = 1 << lod; Triple [] map = new Triple [trin + 1] [trin + 1]; Triple [] farver = ny RGB [trin + 1] [trin + 1]; Terrænterreng = ny FractalTerrain (lod, .5); for (int i = 0; i <= trin; ++ i) {for (int j = 0; j <= trin; ++ j) {dobbelt x = 1,0 * i / trin, z = 1,0 * j / trin ; dobbelt højde = terræn.getAltitude (x, z); kort [i] [j] = ny tredobbelt (x, højde * overdrivelse, z); farver [i] [j] = terræn.getColor (x, z); }} 

Du spørger måske dig selv: Så hvorfor trekanter og ikke firkanter? Problemet med at bruge firkanterne på gitteret er, at de ikke er flade i 3D-rum. Hvis du overvejer fire tilfældige punkter i rummet, er det yderst usandsynligt, at de vil være i samme plan. Så i stedet nedbryder vi vores terræn til trekanter, fordi vi kan garantere, at ethvert tre punkter i rummet vil være ens. Dette betyder, at der ikke er nogen huller i terrænet, som vi ender med at tegne.