Programování

3D grafika Java: Vykreslení fraktální krajiny

3D počítačová grafika má mnoho využití - od her přes vizualizaci dat, virtuální realitu a další. Více často než ne, rychlost má prvořadý význam, takže specializovaný software a hardware je nutností k dokončení práce. Speciální grafické knihovny poskytují rozhraní API na vysoké úrovni, ale skryjí, jak se dělá skutečná práce. Jako programátoři z nosu to však pro nás není dost dobré! Chystáme se dát API do skříně a podívat se do zákulisí toho, jak se obrázky ve skutečnosti generují - od definice virtuálního modelu až po jeho skutečné vykreslení na obrazovku.

Podíváme se na poměrně specifický předmět: generování a vykreslování terénních map, jako je povrch Marsu nebo několik atomů zlata. Vykreslování map terénu lze použít nejen k estetickým účelům - mnoho technik vizualizace dat vytváří data, která lze vykreslit jako mapy terénu. Moje záměry jsou samozřejmě zcela umělecké, jak vidíte na obrázku níže! Pokud si přejete, kód, který vyprodukujeme, je dostatečně obecný, že jej lze pouze s drobným vylepšením použít k vykreslení jiných 3D struktur než terénu.

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

V rámci přípravy na dnešní diskusi vám doporučuji přečíst si červnový „Nakreslete texturované koule“, pokud jste tak dosud neučinili. Článek ukazuje přístup sledování paprsků k vykreslování obrázků (vypalování paprsků do virtuální scény za účelem vytvoření obrazu). V tomto článku budeme vykreslovat prvky scény přímo na displej. I když používáme dvě různé techniky, první článek obsahuje některé podklady k obrázek java.awt balíček, který nebudu v této diskusi znovu omývat.

Terénní mapy

Začněme definováním a

terénní mapa

. Terénní mapa je funkce, která mapuje 2D souřadnice

(x, y)

do nadmořské výšky

A

a barva

C

. Jinými slovy, terénní mapa je jednoduše funkce, která popisuje topografii malé oblasti.

Pojďme definovat náš terén jako rozhraní:

veřejné rozhraní Terén {veřejné dvojité getAltitude (dvojité i, dvojité j); veřejné RGB getColor (dvojité i, dvojité j); } 

Pro účely tohoto článku to předpokládáme 0,0 <= i, j, nadmořská výška <= 1,0. To není požadavek, ale dá nám dobrý nápad, kde najít terén, který budeme prohlížet.

Barva našeho terénu je popsána jednoduše jako RGB triplet. Abychom vytvořili zajímavější obrázky, můžeme zvážit přidání dalších informací, jako je například povrchová lesklost atd. Prozatím však bude fungovat následující třída:

public class RGB {private double r, g, b; veřejné RGB (dvojité r, dvojité g, dvojité b) {this.r = r; this.g = g; this.b = b; } veřejné přidání RGB (RGB rgb) {vrátit nové RGB (r + rgb.r, g + rgb.g, b + rgb.b); } veřejné RGB odečtení (RGB rgb) {vrátit nové RGB (r - rgb.r, g - rgb.g, b - rgb.b); } veřejné měřítko RGB (dvojité měřítko) {vrátit nové RGB (měřítko r *, měřítko g *, měřítko b *); } private int toInt (dvojitá hodnota) {návrat (hodnota 1,0)? 255: (int) (hodnota * 255,0); } public int toRGB () toInt (b); } 

The RGB třída definuje jednoduchý barevný kontejner. Poskytujeme základní vybavení pro provádění aritmetiky barev a převádění barev s plovoucí desetinnou čárkou na formát s celými čísly.

Transcendentální terény

Začneme tím, že se podíváme na transcendentální terén - fancyspeak pro terén vypočítaný ze sinusů a kosinů:

veřejná třída TranscendentalTerrain implementuje Terrain {private double alpha, beta; public TranscendentalTerrain (dvojitá alfa, dvojitá 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); } 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áš konstruktér přijímá dvě hodnoty, které definují frekvenci našeho terénu. Používáme je k výpočtu výšek a barev pomocí Math.sin () a Math.cos (). Nezapomeňte, že tyto funkce vracejí hodnoty -1,0 <= sin (), cos () <= 1,0, takže musíme odpovídajícím způsobem upravit naše návratové hodnoty.

Fraktální terény

Jednoduché matematické terény nejsou žádná zábava. Chceme něco, co vypadá přinejmenším přijatelně reálné. Jako naši terénní mapu bychom mohli použít skutečné topografické soubory (například San Francisco Bay nebo povrch Marsu). I když je to snadné a praktické, je to poněkud nudné. Myslím, že jsme

byl

tam. To, co opravdu chceme, je něco, co vypadá přijatelně skutečné

a

nikdy předtím nebyl viděn. Vstupte do světa fraktálů.

Fraktál je něco (funkce nebo objekt), které vykazuje sebepodobnost. Například sada Mandelbrot je fraktální funkcí: pokud sadu Mandelbrot velmi zvětšíte, najdete drobné vnitřní struktury, které se podobají hlavnímu samotnému Mandelbrotovi. Pohoří je také fraktální, alespoň na pohled. Z blízka se malé rysy jednotlivých hor podobají velkým rysům pohoří, a to až do drsnosti jednotlivých balvanů. Budeme následovat tento princip sebe-podobnosti, abychom vytvořili naše fraktální terény.

V podstatě to, co uděláme, je vytvořit hrubý, počáteční náhodný terén. Pak rekurzivně přidáme další náhodné podrobnosti, které napodobují strukturu celku, ale ve stále menších měřítcích. Skutečný algoritmus, který použijeme, algoritmus Diamond-Square, původně popsali Fournier, Fussell a Carpenter v roce 1982 (podrobnosti viz Zdroje).

Toto jsou kroky, kterými se budeme snažit vybudovat náš fraktální terén:

  1. Nejprve přiřadíme náhodnou výšku čtyřem rohovým bodům mřížky.

  2. Pak vezmeme průměr z těchto čtyř rohů, přidáme náhodné poruchy a přiřadíme to ke středu mřížky (ii v následujícím diagramu). Tomu se říká diamant krok, protože na mřížce vytváříme diamantový vzor. (Při první iteraci diamanty nevypadají jako diamanty, protože jsou na okraji mřížky; ale pokud se podíváte na diagram, pochopíte, na co se dívám.)

  3. Poté vezmeme každý z diamantů, které jsme vyrobili, zprůměrujeme čtyři rohy, přidáme náhodnou poruchu a přiřadíme ji ke středu diamantu (iii v následujícím diagramu). Tomu se říká náměstí krok, protože na mřížce vytváříme čtvercový vzor.

  4. Dále znovu použijeme diamantový krok na každý čtverec, který jsme vytvořili ve čtvercovém kroku, a poté znovu použijeme náměstí krok ke každému diamantu, který jsme vytvořili v diamantovém kroku, a tak dále, dokud nebude naše mřížka dostatečně hustá.

Vyvstává zřejmá otázka: Kolik rušíme mřížku? Odpověď je, že začneme s koeficientem drsnosti 0,0 <drsnost <1,0. Při iteraci n našeho algoritmu Diamond-Square přidáme do mřížky náhodnou poruchu: -roughnessn <= rušení <= drsnostn. V podstatě přidáváme do mřížky jemnější detaily a zmenšujeme rozsah provedených změn. Malé změny v malém měřítku jsou fraktálně podobné velkým změnám ve větším měřítku.

Pokud zvolíme malou hodnotu pro drsnost, pak bude náš terén velmi hladký - změny se velmi rychle zmenší na nulu. Pokud zvolíme velkou hodnotu, pak bude terén velmi drsný, protože změny zůstávají významné i při malých dělení mřížky.

Zde je kód pro implementaci naší mapy fraktálního terénu:

veřejná třída FractalTerrain implementuje Terrain {private double [] [] terén; soukromá dvojitá drsnost, min, max; soukromé int divize; soukromé Náhodné rng; public FractalTerrain (int lod, dvojitá drsnost) {this.roughness = drsnost; this.divisions = 1 << lod; terén = nová dvojitá [divize + 1] [divize + 1]; rng = new Random (); terén [0] [0] = rnd (); terén [0] [divize] = rnd (); terén [divize] [divize] = rnd (); terén [divize] [0] = rnd (); dvojitý drsný = drsnost; pro (int i = 0; i <lod; ++ i) {int q = 1 << i, r = 1 <> 1; pro (int j = 0; j <divize; j + = r) pro (int k = 0; k 0) pro (int j = 0; j <= divize; j + = s) pro (int k = (j + s)% r; k <= dělení; k + = r) čtverec (j - s, k - s, r, hrubý); drsný * = drsnost; } min = max = terén [0] [0]; pro (int i = 0; i <= divize; ++ i) pro (int j = 0; j <= divize; ++ j) if (terén [i] [j] max) max = terén [i] [ j]; } soukromý prázdný diamant (int x, int y, int strana, dvojitá stupnice) {if (strana> 1) {int polovina = 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 + polovina] [y + polovina] = průměr + rnd () * měřítko; }} square soukromých void (int x, int y, int side, double scale) {int half = side / 2; dvojitý průměr = 0,0, součet = 0,0; if (x> = 0) {avg + = terén [x] [y + polovina]; součet + = 1,0; } if (y> = 0) {avg + = terén [x + polovina] [y]; součet + = 1,0; } if (x + strana <= divize) {avg + = terén [x + strana] [y + polovina]; součet + = 1,0; } if (y + strana <= divize) {avg + = terén [x + polovina] [y + strana]; součet + = 1,0; } terén [x + polovina] [y + polovina] = průměr / součet + rnd () * měřítko; } private double rnd () {return 2. * rng.nextDouble () - 1,0; } veřejné dvojité getAltitude (dvojité i, dvojité j) {dvojité alt = terén [(int) (i * divize)] [(int) (j * divize)]; návrat (alt - min) / (max - min); } privátní RGB modrá = nová RGB (0,0, 0,0, 1,0); privátní RGB zelená = nová RGB (0,0; 1,0; 0,0); privátní RGB bílá = nová 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)); }} 

V konstruktoru zadáme oba koeficient drsnosti drsnost a úroveň podrobností lod. Úroveň podrobností je počet iterací, které je třeba provést - pro úroveň podrobností n, vyrábíme mřížku (2n + 1 x 2n + 1) Vzorky. Pro každou iteraci použijeme diamantový krok na každý čtverec v mřížce a poté čtvereční krok na každý diamant. Poté vypočítáme minimální a maximální hodnoty vzorku, které použijeme pro změnu měřítka našich výšek terénu.

Abychom vypočítali nadmořskou výšku bodu, změříme měřítko a vrátíme nejbližší vzorek mřížky na požadované místo. V ideálním případě bychom ve skutečnosti interpolovali mezi okolními body vzorkování, ale tato metoda je v tomto bodě jednodušší a dostatečně dobrá. V naší finální aplikaci tento problém nevznikne, protože budeme skutečně odpovídat místům, kde vzorkujeme terén, na požadovanou úroveň podrobností. K vybarvení našeho terénu jednoduše vrátíme hodnotu mezi modrou, zelenou a bílou v závislosti na nadmořské výšce bodu vzorkování.

Teselace našeho terénu

Nyní máme terénní mapu definovanou přes čtvercovou doménu. Musíme se rozhodnout, jak to vlastně nakreslíme na obrazovku. Mohli jsme vystřelit paprsky do světa a pokusit se určit, na kterou část terénu narazili, jak jsme to udělali v předchozím článku. Tento přístup by však byl extrémně pomalý. Místo toho uděláme aproximaci hladkého terénu spoustou propojených trojúhelníků - to znamená, že náš terén dláždíme.

Tessellate: tvarovat do nebo zdobit mozaikou (z latiny tessellatus).

Abychom vytvořili síť trojúhelníků, rovnoměrně vzorkujeme náš terén do pravidelné mřížky a poté tuto mřížku zakryjeme trojúhelníky - dva pro každý čtverec mřížky. Existuje mnoho zajímavých technik, které bychom mohli použít ke zjednodušení této trojúhelníkové sítě, ale my bychom je potřebovali, pouze pokud by se jednalo o rychlost.

Následující fragment kódu naplní prvky naší terénní mřížky daty fraktálního terénu. Zmenšujeme vertikální osu našeho terénu, aby byly nadmořské výšky o něco méně přehnané.

dvojité přehánění = 0,7; int lod = 5; int kroky = 1 << lod; Trojitá [] mapa = nová Trojitá [kroky + 1] [kroky + 1]; Triple [] barvy = nové RGB [kroky + 1] [kroky + 1]; Terénní terén = nový FractalTerrain (lod, 0,5); pro (int i = 0; i <= kroky; ++ i) {pro (int j = 0; j <= kroky; ++ j) {double x = 1,0 * i / kroky, z = 1,0 * j / kroky ; dvojnásobná nadmořská výška = terén.getAltitude (x, z); mapa [i] [j] = nový Triple (x, nadmořská výška * nadsázka, z); barvy [i] [j] = terén.getColor (x, z); }} 

Možná se ptáte sami sebe: Tak proč trojúhelníky a ne čtverce? Problém s použitím čtverců mřížky spočívá v tom, že v 3D prostoru nejsou ploché. Pokud vezmete v úvahu čtyři náhodné body ve vesmíru, je extrémně nepravděpodobné, že budou koplanární. Místo toho tedy rozložíme náš terén na trojúhelníky, protože můžeme zaručit, že jakékoli tři body ve vesmíru budou koplanární. To znamená, že v terénu nebudou žádné mezery, které nakonec nakreslíme.