Programovanie

3D grafika Java: Vykresľuje fraktálne krajiny

3D počítačová grafika má mnoho využití - od hier po vizualizáciu údajov, virtuálnu realitu a ďalšie. Častejšie je najdôležitejšie, že rýchlosť musí byť prvoradá, a preto je pri práci nevyhnutný špecializovaný softvér a hardware. Špeciálne grafické knižnice poskytujú rozhranie API na vysokej úrovni, ale zakrývajú, ako sa robí skutočná práca. Ako nosní kovoví programátori to však pre nás nie je dosť dobré! Chystáme sa umiestniť API do skrinky a pozrieť sa do zákulisia toho, ako sa obrázky v skutočnosti generujú - od definície virtuálneho modelu po jeho skutočné vykreslenie na obrazovku.

Pozrime sa na celkom konkrétny predmet: generovanie a vykreslenie terénnych máp, ako je povrch Marsu alebo niekoľko atómov zlata. Vykreslenie terénnej mapy sa dá použiť nielen na estetické účely - mnoho techník vizualizácie údajov vytvára údaje, ktoré je možné vykresliť ako terénne mapy. Moje zámery sú samozrejme úplne umelecké, ako vidíte na obrázku nižšie! Ak si to prajete, kód, ktorý vyprodukujeme, je dostatočne všeobecný, aby ho bolo možné s malými úpravami použiť aj na vykreslenie 3D štruktúr iných ako terény.

Kliknutím sem zobrazíte a manipulujete s appletom terénu.

V rámci prípravy na našu dnešnú diskusiu vám odporúčam prečítať si júnový text „Nakreslite tvarované guľôčky“, ak ste tak ešte neurobili. Článok demonštruje prístup sledovania lúčov k vykresľovaniu obrázkov (vypaľovanie lúčov do virtuálnej scény na vytvorenie obrazu). V tomto článku budeme vykresľovať prvky scény priamo na displej. Aj keď používame dve rôzne techniky, prvý článok obsahuje niekoľko podkladových materiálov o java.awt.obrázok balíček, ktorý v tejto diskusii nebudem znova rozbíjať.

Terénne mapy

Začnime definovaním a

terénna mapa

. Terénna mapa je funkcia mapujúca 2D súradnice

(x, y)

do nadmorskej výšky

a

a farbu

c

. Inými slovami, terénna mapa je jednoducho funkcia, ktorá popisuje topografiu malého územia.

Definujme náš terén ako rozhranie:

verejné rozhranie Terén {verejné dvojité getAltitude (dvojité i, dvojité j); verejné RGB getColor (dvojité i, dvojité j); } 

Na účely tohto článku to budeme predpokladať 0,0 <= i, j, nadmorská výška <= 1,0. Toto nie je požiadavka, ale dá nám dobrý nápad, kde nájdeme terén, ktorý si prezeráme.

Farba nášho terénu je opísaná jednoducho ako RGB trojica. Na vytvorenie zaujímavejších obrázkov by sme mohli zvážiť pridanie ďalších informácií, ako je napríklad povrchová lesklosť atď. Zatiaľ však bude stačiť nasledujúca trieda:

verejná trieda RGB {súkromná dvojitá r, g, b; verejné RGB (dvojité r, dvojité g, dvojité b) {this.r = r; this.g = g; this.b = b; } verejné pridanie RGB (RGB rgb) {vrátiť nové RGB (r + rgb.r, g + rgb.g, b + rgb.b); } verejné odčítanie RGB (RGB rgb) {vrátiť nové RGB (r - rgb.r, g - rgb.g, b - rgb.b); } verejná stupnica RGB (dvojitá stupnica) {vrátiť novú RGB (stupnica r *, stupnica g *, stupnica b *); } private int toInt (dvojitá hodnota) {návrat (hodnota 1,0)? 255: (int) (hodnota * 255,0); } public int toRGB () toInt (b); } 

The RGB trieda definuje jednoduchý farebný kontajner. Poskytujeme základné vybavenie na vykonávanie farebnej aritmetiky a prevod farby s pohyblivou rádovou čiarkou na formát s celočíselnými číslami.

Transcendentálne terény

Začneme pohľadom na transcendentálny terén - fancyspeak pre terén vypočítaný zo sínusov a kosínusov:

verejná trieda TranscendentalTerrain implementuje Terrain {súkromné ​​dvojité alfa, beta; public TranscendentalTerrain (dvojitá alfa, dvojitá beta) {this.alpha = alfa; this.beta = beta; } verejné dvojité getAltitude (dvojité i, dvojité j) {návrat 0,5 + 0,5 * Math.sin (i * alfa) * Math.cos (j * beta); } public RGB getColor (double i, double j) {return new RGB (.5 + .5 * Math.sin (i * alpha), .5 - .5 * Math.cos (j * beta), 0.0); }} 

Náš konštruktér akceptuje dve hodnoty, ktoré určujú frekvenciu nášho terénu. Pomocou nich vypočítame nadmorské výšky a farby pomocou Math.sin () a Math.cos (). Pamätajte, že tieto funkcie vracajú hodnoty -1,0 <= sin (), cos () <= 1,0, takže musíme zodpovedajúcim spôsobom upraviť naše návratové hodnoty.

Fraktálne terény

Jednoduché matematické terény nie sú žiadna sranda. Čo chceme, je niečo, čo vyzerá prinajmenšom prijateľne reálne. Ako našu terénnu mapu by sme mohli použiť skutočné topografické súbory (napríklad záliv San Francisco alebo povrch Marsu). Aj keď je to jednoduché a praktické, je to do istej miery nudné. Teda, máme

Bol

tam. To, čo skutočne chceme, je niečo, čo vyzerá prijateľne reálne

a

nikdy predtým nevidel. Vstúpte do sveta fraktálov.

Fraktál je niečo (funkcia alebo objekt), ktoré vykazuje sebapodobnosť. Napríklad Mandelbrotova sada je fraktálna funkcia: ak veľmi zväčšíte Mandelbrotovu sadu, nájdete drobné vnútorné štruktúry, ktoré sa podobajú samotnému hlavnému Mandelbrotovi. Pohorie je tiež fraktálne, aspoň na prvý pohľad. Z blízka pripomínajú malé prvky jednotlivej hory veľké prvky pohoria, dokonca až po drsnosť jednotlivých balvanov. Budeme nasledovať tento princíp podobnosti, aby sme vytvorili naše fraktálne terény.

V zásade urobíme to, že vygenerujeme hrubý počiatočný náhodný terén. Potom rekurzívne pridáme ďalšie náhodné podrobnosti, ktoré napodobňujú štruktúru celku, ale v čoraz menších mierkach. Skutočný algoritmus, ktorý použijeme, algoritmus Diamond-Square, pôvodne opísali Fournier, Fussell a Carpenter v roku 1982 (podrobnosti nájdete v časti Zdroje).

Toto sú kroky, cez ktoré sa prepracujeme k vybudovaniu nášho fraktálneho terénu:

  1. Najskôr priradíme náhodnú výšku k štyrom rohovým bodom mriežky.

  2. Potom zoberieme priemer z týchto štyroch rohov, pridáme náhodné rušenie a priradíme ho k stredu mriežky (ii v nasledujúcom diagrame). Toto sa nazýva diamant krok, pretože na mriežke vytvárame diamantový vzor. (Pri prvej iterácii diamanty nevyzerajú ako diamanty, pretože sú na okraji mriežky; ale keď sa pozriete na diagram, pochopíte, na čo narážam.)

  3. Potom vezmeme každý z diamantov, ktoré sme vyrobili, spriemerujeme štyri rohy, pridáme náhodnú poruchu a priradíme ju k stredu diamantu (iii v nasledujúcom diagrame). Toto sa nazýva námestie krok, pretože na mriežke vytvárame štvorcový vzor.

  4. Ďalej znovu použijeme diamantový krok na každý štvorec, ktorý sme vytvorili v štvorcovom kroku, a potom znova použijeme námestie krok ku každému diamantu, ktorý sme vytvorili v diamantovom kroku, a tak ďalej, až kým nebude naša mriežka dostatočne hustá.

Vyvstáva zjavná otázka: Koľko rušíme mriežku? Odpoveď je, že začneme koeficientom drsnosti 0,0 <drsnosť <1,0. Pri iterácii n nášho algoritmu Diamond-Square pridáme do mriežky náhodnú poruchu: -drsnosťn <= rušenie <= drsnosťn. V zásade platí, že keď do mriežky pridávame jemnejšie podrobnosti, zmenšujeme rozsah uskutočňovaných zmien. Malé zmeny v malom meradle sú fraktálne podobné veľkým zmenám vo väčšom meradle.

Ak zvolíme malú hodnotu pre drsnosť, potom bude náš terén veľmi hladký - zmeny sa veľmi rýchlo zmenšia na nulu. Ak zvolíme veľkú hodnotu, potom bude terén veľmi drsný, pretože zmeny zostávajú značné pri malých rozdeleniach mriežky.

Tu je kód na implementáciu našej mapy fraktálneho terénu:

verejná trieda FractalTerrain implementuje terén {private double [] [] terén; súkromná dvojitá drsnosť, min, max; súkromné ​​int divízie; private Random rng; public FractalTerrain (int lod, dvojitá drsnosť) {this.roughness = drsnosť; this.divisions = 1 << lod; terén = nová dvojka [divízie + 1] [divízie + 1]; rng = new Random (); terén [0] [0] = rnd (); terén [0] [divízie] = rnd (); terén [divízie] [divízie] = rnd (); terén [divízie] [0] = rnd (); dvojitý drsný = drsnosť; pre (int i = 0; i <lod; ++ i) {int q = 1 << i, r = 1 <> 1; pre (int j = 0; j <divízie; j + = r) pre (int k = 0; k 0) pre (int j = 0; j <= divízie; j + = s) pre (int k = (j + s)% r; k <= divízie; k + = r) štvorec (j - s, k - s, r, hrubý); drsný * = drsnosť; } min = max = terén [0] [0]; pre (int i = 0; i <= divízie; ++ i) pre (int j = 0; j <= divízie; ++ j) if (terén [i] [j] max) max = terén [i] [ j]; } kosoštvorec súkromnej neplatnosti (int x, int y, int strana, dvojitá mierka) {if (strana> 1) {int polovica = strana / 2; double avg = (terén [x] [y] + terén [x + strana] [y] + terén [x + strana] [y + strana] + terén [x] [y + strana]) * 0,25; terén [x + polovica] [y + polovica] = priemer + rnd () * mierka; }} štvorec súkromnej neplatnosti (int x, int y, int strana, dvojitá mierka) {int polovica = strana / 2; dvojnásobok priem = 0,0, súčet = 0,0; if (x> = 0) {avg + = terén [x] [y + polovica]; suma + = 1,0; } if (y> = 0) {avg + = terén [x + polovica] [y]; suma + = 1,0; } if (x + strana <= divízie) {avg + = terén [x + strana] [y + polovica]; suma + = 1,0; } if (y + strana <= divízie) {avg + = terén [x + polovica] [y + strana]; suma + = 1,0; } terén [x + polovica] [y + polovica] = priemer / súčet + rnd () * mierka; } private double rnd () {return 2. * rng.nextDouble () - 1,0; } verejné dvojité getAltitude (dvojité i, dvojité j) {dvojité alt = terén [(int) (i * divízie)] [(int) (j * divízie)]; návrat (alt - min) / (max - min); } súkromné ​​RGB modré = nové RGB (0,0, 0,0, 1,0); súkromná zelená RGB = nové RGB (0,0, 1,0, 0,0); súkromná biela RGB = nové RGB (1,0, 1,0, 1,0); verejné RGB getColor (double i, double j) {double a = getAltitude (i, j); if (a <0,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)); }} 

V konštruktore zadáme koeficient drsnosti drsnosť a úroveň podrobností lod. Úroveň podrobnosti je počet iterácií, ktoré sa majú vykonať - pre úroveň podrobností n, vyrábame mriežku z (2 n + 1 x 2 n + 1) vzorky. Pre každú iteráciu použijeme diamantový krok na každý štvorec v mriežke a potom štvorcový krok na každý diamant. Potom vypočítame minimálnu a maximálnu hodnotu vzorky, ktorú použijeme na zmenu mierky našich terénnych nadmorských výšok.

Na výpočet nadmorskej výšky bodu sa zmenší mierka a vráti sa hodnota najbližšie vzorka mriežky na požadované miesto. V ideálnom prípade by sme skutočne interpolovali medzi okolitými vzorkovými bodmi, ale táto metóda je v tomto bode jednoduchšia a dosť dobrá. V našej konečnej aplikácii tento problém nevznikne, pretože skutočne zodpovedáme miestam, kde vzorkujeme terén, na požadovanú úroveň detailov. Ak chcete vyfarbiť náš terén, jednoducho vrátime hodnotu medzi modrou, zelenou a bielou v závislosti od nadmorskej výšky bodu vzorkovania.

Teselovanie nášho terénu

Teraz máme terénnu mapu definovanú cez štvorcovú doménu. Musíme sa rozhodnúť, ako to skutočne nakreslíme na obrazovku. Mohli sme vystreliť lúče do sveta a pokúsiť sa určiť, na ktorú časť terénu narazia, ako sme to urobili v predchádzajúcom článku. Tento prístup by však bol mimoriadne pomalý. Namiesto toho urobíme aproximáciu hladkého terénu kopou spojených trojuholníkov - to znamená, že náš terén upravíme dláždením.

Tessellate: tvarovať do mozaiky alebo zdobiť mozaikou (z lat tessellatus).

Aby sme vytvorili sieťku trojuholníka, náš terén rovnomerne vzorkujeme do pravidelnej mriežky a potom túto mriežku pokryjeme trojuholníkmi - dvoma pre každý štvorec mriežky. Existuje mnoho zaujímavých techník, ktoré by sme mohli použiť na zjednodušenie tejto trojuholníkovej siete, ale tie by sme potrebovali iba v prípade, že by sa rýchlosť týkala.

Nasledujúci fragment kódu vyplňuje prvky našej terénnej mriežky údajmi o fraktálnom teréne. Zmenšujeme zvislú os nášho terénu, aby boli nadmorské výšky o niečo menej prehnané.

dvojité preháňanie = 0,7; int lod = 5; int kroky = 1 << lod; Trojitá [] mapa = nová Trojitá [kroky + 1] [kroky + 1]; Trojité [] farby = nové RGB [kroky + 1] [kroky + 1]; Terénny terén = nový FractalTerrain (lod, 0,5); pre (int i = 0; i <= kroky; ++ i) {pre (int j = 0; j <= kroky; ++ j) {double x = 1,0 * i / kroky, z = 1,0 * j / kroky ; dvojnásobná nadmorská výška = terén.getAltitude (x, z); mapa [i] [j] = nový Trojitý (x, nadmorská výška * preháňanie, z); farby [i] [j] = terén.getColor (x, z); }} 

Možno si kladiete otázku: Tak prečo trojuholníky a nie štvorce? Problém s používaním štvorcov mriežky je, že nie sú ploché v 3D priestore. Ak vezmete do úvahy štyri náhodné body vo vesmíre, je veľmi nepravdepodobné, že budú koplanárne. Namiesto toho teda rozkladáme náš terén na trojuholníky, pretože môžeme zaručiť, že akékoľvek tri body vo vesmíre budú koplanárne. To znamená, že v teréne nebudú žiadne medzery, ktoré nakoniec nakreslíme.

$config[zx-auto] not found$config[zx-overlay] not found