3D datagrafikk har mange bruksområder - fra spill til datavisualisering, virtual reality og videre. Oftere enn ikke er hastighet av største betydning, noe som gjør spesialisert programvare og maskinvare et must for å få jobben gjort. Spesielle grafikkbiblioteker gir et API på høyt nivå, men skjul hvordan det virkelige arbeidet gjøres. Som nese-til-metall-programmerere er det imidlertid ikke bra nok for oss! Vi skal sette API-en i skapet og se bak kulissene på hvordan bilder faktisk genereres - fra definisjonen av en virtuell modell til den faktiske gjengivelsen på skjermen.
Vi vil se på et ganske spesifikt emne: generere og gjengi terrengkart, som overflaten til Mars eller noen få atomer av gull. Terrengkartgjengivelse kan brukes til mer enn bare estetiske formål - mange datavisualiseringsteknikker produserer data som kan gjengis som terrengkart. Intensjonene mine er selvfølgelig helt kunstneriske, som du kan se på bildet nedenfor! Hvis du ønsker det, er koden vi skal produsere generell nok til at den med bare mindre justeringer også kan brukes til å gjengi andre 3D-strukturer enn terreng.
Klikk her for å se og manipulere terrengappleten.
Som forberedelse til diskusjonen vår i dag, foreslår jeg at du leser Junis "Tegn strukturerte kuler" hvis du ikke allerede har gjort det. Artikkelen demonstrerer en strålesporingsmetode for å gjengi bilder (skyte stråler inn i en virtuell scene for å produsere et bilde). I denne artikkelen gjengir vi sceneelementer direkte på skjermen. Selv om vi bruker to forskjellige teknikker, inneholder den første artikkelen noe bakgrunnsmateriale om java.awt.image pakke som jeg ikke vil rehash i denne diskusjonen.
Terrengkart
La oss starte med å definere en
terrengkart
. Et terrengkart er en funksjon som kartlegger en 2D-koordinat
(x, y)
til en høyde
en
og farge
c
. Et terrengkart er med andre ord ganske enkelt en funksjon som beskriver topografien til et lite område.
La oss definere terrenget vårt som et grensesnitt:
offentlig grensesnitt Terreng {offentlig dobbelt getAltitude (dobbelt i, dobbelt j); offentlig RGB getColor (dobbel i, dobbel j); } For formålet med denne artikkelen vil vi anta at 0,0 <= i, j, høyde <= 1,0. Dette er ikke et krav, men vil gi oss en god ide hvor vi finner terrenget vi skal se på.
Fargen på terrenget vårt er ganske enkelt beskrevet som en RGB-triplett. For å produsere mer interessante bilder, kan vi vurdere å legge til annen informasjon som overflatens skinnende etc. Foreløpig vil imidlertid følgende klasse gjøre:
offentlig klasse RGB {privat dobbel r, g, b; offentlig RGB (dobbel r, dobbel g, dobbel b) {this.r = r; this.g = g; this.b = b; } public RGB add (RGB rgb) {return new RGB (r + rgb.r, g + rgb.g, b + rgb.b); } offentlig RGB-subtraksjon (RGB rgb) {returner ny RGB (r - rgb.r, g - rgb.g, b - rgb.b); } offentlig RGB-skala (dobbel skala) {returner ny RGB (r * skala, g * skala, b * skala); } privat int toInt (dobbel verdi) {retur (verdi 1.0)? 255: (int) (verdi * 255,0); } public int toRGB () toInt (b); } De RGB klasse definerer en enkel fargebeholder. Vi tilbyr noen grunnleggende fasiliteter for å utføre farearitmetikk og konvertere en flytpunktsfarge til pakket heltallformat.
Transcendentale terreng
Vi begynner med å se på et transcendentalt terreng - fancyspeak for et terreng beregnet fra sines og cosinus:
offentlig klasse TranscendentalTerrain implementerer Terreng {privat dobbelt alfa, beta; offentlig TranscendentalTerrain (dobbel alfa, dobbel beta) {this.alpha = alpha; this.beta = beta; } offentlig dobbel getAltitude (dobbel i, dobbel j) {retur .5 + .5 * Math.sin (i * alpha) * Math.cos (j * beta); } offentlig RGB getColor (dobbel i, dobbel j) {returner ny RGB (.5 + .5 * Math.sin (i * alpha), .5 - .5 * Math.cos (j * beta), 0.0); }} Konstruktøren vår aksepterer to verdier som definerer hyppigheten av terrenget vårt. Vi bruker disse til å beregne høyder og farger ved hjelp av Math.sin () og Math.cos (). Husk at disse funksjonene returnerer verdier -1,0 <= sin (), cos () <= 1.0, så vi må justere returverdiene tilsvarende.
Fraktal terreng
Enkle matematiske terreng er ikke morsomt. Det vi ønsker er noe som i det minste ser passabelt ekte ut. Vi kunne bruke ekte topografifiler som vårt terrengkart (for eksempel San Francisco Bay eller Mars overflate). Selv om dette er enkelt og praktisk, er det noe kjedelig. Jeg mener, vi har
vært
der. Det vi virkelig vil ha, er noe som ser passabelt ekte ut
og
har aldri blitt sett før. Gå inn i verden av fraktaler.
En fraktal er noe (en funksjon eller et objekt) som viser selvlikhet. For eksempel er Mandelbrot-settet en fraktalfunksjon: hvis du forstørrer Mandelbrot-settet sterkt, vil du finne små interne strukturer som ligner selve Mandelbrot. En fjellkjede er også fraktal, i det minste i utseende. Fra nært hold ligner små trekk på et enkelt fjell store trekk ved fjellkjeden, til og med ned til grovheten til individuelle steinblokker. Vi vil følge dette prinsippet om selvlikhet for å generere våre fraktale terreng.
I hovedsak skal vi generere et grovt innledende tilfeldig terreng. Deretter legger vi rekursivt til flere tilfeldige detaljer som etterligner strukturen til helheten, men på stadig mindre skalaer. Den faktiske algoritmen vi vil bruke, Diamond-Square-algoritmen, ble opprinnelig beskrevet av Fournier, Fussell og Carpenter i 1982 (se Ressurser for detaljer).
Dette er trinnene vi skal gjennomføre for å bygge vårt fraktale terreng:
Vi tilordner først en tilfeldig høyde til de fire hjørnepunktene i et rutenett.
Vi tar deretter gjennomsnittet av disse fire hjørnene, legger til en tilfeldig forstyrrelse og tilordner dette til midtpunktet i rutenettet (ii i følgende diagram). Dette kalles diamant trinn fordi vi lager et diamantmønster på rutenettet. (Ved den første iterasjonen ser ikke diamantene ut som diamanter fordi de er i kanten av rutenettet; men hvis du ser på diagrammet, vil du forstå hva jeg kommer til.)
Vi tar deretter hver av diamantene vi har produsert, gjennomsnitter de fire hjørnene, legger til en tilfeldig forstyrrelse og tilordner dette til diamantens midtpunkt (iii i følgende diagram). Dette kalles torget trinn fordi vi lager et kvadratisk mønster på rutenettet.
- Deretter bruker vi diamant-trinnet på nytt på hvert kvadrat som vi opprettet i det kvadratiske trinnet, og deretter på nytt torget gå til hver diamant som vi skapte i diamanttrinnet, og så videre til rutenettet vårt er tilstrekkelig tett.
Et åpenbart spørsmål oppstår: Hvor mye forstyrrer vi nettet? Svaret er at vi starter med en ruhetskoeffisient 0,0 <ruhet <1,0. Ved iterasjon n av vår Diamond-Square-algoritme legger vi til en tilfeldig forstyrrelse i rutenettet: -Throughnessn <= forstyrrelse <= roughnessn. I hovedsak, når vi legger til finere detaljer i rutenettet, reduserer vi omfanget av endringene vi gjør. Små endringer i liten skala ligner fraktalt på store endringer i større skala.
Hvis vi velger en liten verdi for ruhet, så vil terrenget vårt være veldig glatt - endringene vil raskt reduseres til null. Hvis vi velger en stor verdi, vil terrenget være veldig grovt, ettersom endringene forblir betydelige ved små nettdeler.
Her er koden for å implementere vårt fraktale terrengkart:
offentlig klasse FractalTerrain implementerer Terreng {privat dobbelt [] [] terreng; privat dobbel ruhet, min, maks; private int divisjoner; private Tilfeldig rng; offentlig FractalTerrain (int lod, dobbel ruhet) {this.roughness = ruhet; dette. avdelinger = 1 << lod; terreng = ny dobbel [divisjoner + 1] [divisjoner + 1]; rng = ny Tilfeldig (); terreng [0] [0] = rnd (); terreng [0] [divisjoner] = rnd (); terreng [divisjoner] [divisjoner] = rnd (); terreng [divisjoner] [0] = rnd (); dobbelt grovhet = ruhet; for (int i = 0; i <lod; ++ i) {int q = 1 << i, r = 1 <> 1; for (int j = 0; j <divisjoner; j + = r) for (int k = 0; k 0) for (int j = 0; j <= divisjoner; j + = s) for (int k = (j + s)% r; k <= divisjoner; k + = r) firkant (j - s, k - s, r, grov); grov * = ruhet; } min = maks = terreng [0] [0]; for (int i = 0; i <= divisjoner; ++ i) for (int j = 0; j <= divisjoner; ++ j) hvis (terreng [i] [j] maks) maks = terreng [i] [ j]; } privat tomrom (int x, int y, int side, dobbel skala) {if (side> 1) {int half = side / 2; dobbel avg = (terreng [x] [y] + terreng [x + side] [y] + terreng [x + side] [y + side] + terreng [x] [y + side]) * 0,25; terreng [x + halv] [y + halv] = gjennomsnitt + rnd () * skala; }} privat tomrom (int x, int y, int side, dobbel skala) {int half = side / 2; dobbel gjennomsnitt = 0,0, sum = 0,0; hvis (x> = 0) {avg + = terreng [x] [y + halv]; sum + = 1.0; } hvis (y> = 0) {avg + = terreng [x + halv] [y]; sum + = 1.0; } hvis (x + side <= divisjoner) {avg + = terreng [x + side] [y + halv]; sum + = 1.0; } hvis (y + side <= divisjoner) {avg + = terreng [x + halv] [y + side]; sum + = 1.0; } terreng [x + halv] [y + halv] = gjennomsnitt / sum + rnd () * skala; } privat dobbeltrnd () {retur 2. * rng.nextDouble () - 1.0; } offentlig dobbel getAltitude (dobbel i, dobbel j) {dobbel alt = terreng [(int) (i * divisjoner)] [(int) (j * divisjoner)]; retur (alt - min) / (max - min); } privat RGB blå = ny RGB (0,0, 0,0, 1,0); privat RGB grønn = ny RGB (0,0, 1,0, 0,0); privat RGB hvit = ny RGB (1.0, 1.0, 1.0); offentlig RGB getColor (dobbelt i, dobbelt j) {dobbelt a = getAltitude (i, j); if (a <.5) return blue.add (green.subtract (blue) .scale ((a - 0.0) / 0.5)); ellers returner grønt. legg til (hvit. trekk (grønn). skala ((a - 0,5) / 0,5)); }} I konstruktøren spesifiserer vi både ruhetskoeffisienten ruhet og detaljnivået lodge. Detaljnivået er antall iterasjoner som skal utføres - for et detaljnivå n, produserer vi et rutenett av (2n + 1 x 2n + 1) prøver. For hver iterasjon bruker vi diamant-trinnet på hvert kvadrat i rutenettet og deretter det kvadratiske trinnet på hver diamant. Etterpå beregner vi minimums- og maksimumsprøveverdiene, som vi bruker til å skalere terrenghøydene våre.
For å beregne høyden på et punkt skalerer og returnerer vi nærmeste rutenettprøve til ønsket plassering. Ideelt sett ville vi faktisk interpolere mellom omkringliggende prøvepunkter, men denne metoden er enklere og god nok på dette punktet. I den endelige applikasjonen vil dette problemet ikke oppstå fordi vi faktisk vil matche stedene der vi prøver terrenget til detaljnivået vi ber om. For å fargelegge terrenget vårt returnerer vi ganske enkelt en verdi mellom blå, grønn og hvit, avhengig av høyden på prøvepunktet.
Tessellating terrenget vårt
Vi har nå et terrengkart definert over et firkantet domene. Vi må bestemme hvordan vi faktisk skal tegne dette på skjermen. Vi kunne skyte stråler inn i verden og prøve å bestemme hvilken del av terrenget de treffer, slik vi gjorde i forrige artikkel. Denne tilnærmingen vil imidlertid være ekstremt treg. Det vi skal gjøre i stedet er å tilnærme det glatte terrenget med en rekke sammenhengende trekanter - det vil si at vi skal tessellere terrenget vårt.
Tessellate: å forme til eller pryde med mosaikk (fra latin tessellatus).
For å danne trekantnettet vil vi jevnt prøve terrenget vårt til et vanlig rutenett og deretter dekke dette rutenettet med trekanter - to for hver firkant av rutenettet. Det er mange interessante teknikker vi kan bruke for å forenkle dette trekantnettet, men vi trenger dem bare hvis hastighet var en bekymring.
Følgende kodefragment fyller elementene i terrengruten med fraktal terrengdata. Vi skalerer ned den vertikale aksen i terrenget vårt for å gjøre høyden litt mindre overdrevet.
dobbel overdrivelse = .7; int lod = 5; int trinn = 1 << lod; Triple [] map = new Triple [trinn + 1] [trinn + 1]; Trippel [] farger = ny RGB [trinn + 1] [trinn + 1]; Terrengterreng = ny FractalTerrain (lod, .5); for (int i = 0; i <= trinn; ++ i) {for (int j = 0; j <= trinn; ++ j) {dobbel x = 1,0 * i / trinn, z = 1,0 * j / trinn ; dobbel høyde = terreng.getAltitude (x, z); kart [i] [j] = ny trippel (x, høyde * overdrivelse, z); farger [i] [j] = terreng.getColor (x, z); }} Du spør deg kanskje: Så hvorfor trekanter og ikke firkanter? Problemet med å bruke rutene i rutenettet er at de ikke er flate i 3D-rom. Hvis du vurderer fire tilfeldige punkter i rommet, er det ekstremt lite sannsynlig at de vil være i samme plan. Så i stedet bryter vi ned terrenget vårt til trekanter fordi vi kan garantere at noen tre punkter i rommet vil være i samme plan. Dette betyr at det ikke vil være hull i terrenget som vi ender med å tegne.
