Fraktaler
Terreng
Glatting
Grafikk
Jon Roar Odden / Student 2005
Å tegne:>Fraktal terreng

Fraktalterreng

Hva
illus_terreng

Fraktalterreng eller "procedural terrain generation" er måten man lager tilfeldig landskap på i spill, flysimulatorer og liknende. Fraktalterreng går ut på at man ved hjelp av forskjellige algoritmer kommer opp med et array av verdier som kan representere høyder. Dette kalles et heightmap eller høydekart på norsk. For å forstå selve teknikken med høydekart legger vi bort "fraktal" delen en liten stund og tar for oss "terreng" delen.

Terreng "lastes" ofte i begrensede miljøer som for eksempel demoer, små spill og liknende. Bakgrunnen for et slikt terreng er et gråskala bilde, ofte lagret som bitmap eller raw. Sistnevnte er kun pixelverdiene skrevet rett til fil uten noen form for headere. Et eksempel på et slikt bilde kan du se på figur 1. Hver pixel i et slikt gråskalabilde har en verdi mellom 0 og 255. Jo sortere farge i bildet, desto lavere verdi. Jo lavere verdi, desto lavere blir terrenget på dette punktet. Men dette kan selvfølgelig gjøres motsatt helt avhengig av hva programmereren ønsker.

Så, siden jeg sier "lastes" så må de jo bli laget på en eller annen måte. Og Photoshop for eksempel, kan gjøre dette for deg. Lag et nytt bilde, velg to forskjellige farger på forgrunn og bakgrunn. Deretter går på du Filter->Render->Clouds eller Difference Clouds. Nå har du et potensielt heightmap. Du kan også bruke min Perlin Noise bildegenerator for å lage slike bilder. Disse bildene kan så lastes inn i et program og rendres som høydeverdier i et terreng.

Nå sier det seg selv at man ikke kan holde på å lage et 100-talls slike bilder i Photoshop for å sende med et spill. Selv om dette er teoretisk mulig vil det ikke være en god løsning da hengivende brukere etterhvert vil ha spilt igjennom alle terrengene. Så hva gjør man? Man genererer høydekart realtime. Og dette fører oss inn på hvordan de genereres, og Perlin Noise som vi snart skal se på.

perlin_hf

figur 1

mandelbrot3d
Se Anton Feenstras
Mandelbrot Pictures [1] .

Så til "fraktal" delen av fraktalterreng. Mange forbinder Mandelbrot med fraktaler, og dette er såvidt jeg vet, den eneste virkelige fraktalen. for at noe skal være fraktal etter ordets strengeste definisjon må et fragment av fraktalet være identisk lik fraktalet i sin helhet. Mandelbrot fraktaler er nettop dette. En litt løsere definisjon er selv-likhet, altså at et fragment av fraktalet må likne fraktalet selv. Og det kan absolutt et terreng gjøre. Uansett er det mange som også forbinder fraktaler med tilfeldighet, og det er noe av det viktigste vi prøver å oppnå også med terreng. Vi vil gjerne lage noe som forandrer seg, og ikke ser for likt ut. For å fly over det samme terrenget gang etter gang blir fort kjedelig.

Høydekart og Perlin Noise

Perlin Noise oppkalt etter oppfinneren Ken Perlin og er en prisbelønnet algoritme for å lage strukturert støy. Med strukturert mener jeg at verdiene er ikke helt tilfeldig, de følger et visst mønster. White noise er motsetningen. Denne inneholder helt tilfeldige verdier og ser ut som når du ikke har signal på TV'n. Så, hva har støy med terreng å gjøre? Som nevnt tidligere ønsker vi en grad av tilfeldighet og med støy oppnår vi dette. Kjernen i Perlin Noise som er det jeg har brukt ser du i figur 2.

n = x + y * 57;
    n = (n<<13) ^ n;
    res = (float)( 1.0 - ( (n * (n * n * 15731 + 789221) + 1376312589) & 0x7fffffff )
          /1073741824.0);

figur 2

x og y her er x og y verdiene som representerer en vertex/pixel i høydekartet, og res innholder, etter dette, høyden for denne pixelen. Når dette er gjort for hver pixel i høydekartet har vi et array med mer eller mindre tilfeldig verdier. Ofte kan det være så store differanser på verdiene, at et terreng rendret direkte ikke vil bli spesielt pent. Og det fører oss inn på glatting som vi skal se nærmere på litt senere.

Men tilbake til hvordan Perlin Noise virker. Vi tar ting fra begynnelsen og da starter vi med en sinus kurve. Du husker vel trigonometri? For å friske opp litt bekreper forbundet med bølger. Bølgelengde er definert som avstand fra topp-til-topp (peak-to-peak). Amplitude er definert som avstand fra halve høyden til max høyde på en bølge. Frekvens er definert som 1 / bølgelengde. Dette kommer klart frem av figur 3.

wave01

figur 3

Så som vi har definisjonene våre klare i hodet kan vi gå løs på hvordan Perlin Noise blir laget. Hvis man definerer et antall tilfeldig verdier langs X aksen på en slik kurve får man figur 4. Dette er den generelle måten støy funksjoner jobber på.

wave02

figur 4

pn_gen01_sm

Nå, hvis du tar noen forskjellige slike funksjoner, med varierende frekvenser og bølgelengder, og legger disse sammen. Da har du Perlin Noise. Perlin Noise er 6 forskjellige støy funksjoner med forskjellige variabler, lagt over hverandre. Figur 5 viser dette gjort i en dimensjon. (Trykk for større bilde) Resultatet av dette i 2D, laget av min Perlin Noise bildegenerator kan du se på figur 1 og på bildet til høyre. Figur 8 viser Perlin Noise i 3D.

perlin_waves_450

figur 5

Når vi nå har alle disse verdiene som Perlin Noise har gitt oss, hvordan rendrer vi de? Jeg har valgt en enkel modell som rendrer en vertex for hver pixel i gråskalabildet vårt. Denne blir ofte kalt "Brute force". Dette er den enkleste og kvalitetsmessig beste måten å rendre et terreng på, men også den treigeste. Fordi datamaskinen må gjøre kalkulasjoner for hvert eneste punkt den skal tegne. Andre metoder bruker en eller annen form for CLOD, Continous Level Of Detail. Quadtree er en slik metode og baserer seg på å bruke store quads der hvor terrenget ikke har kurver, og legger til flere mindre quads der det trengs. Altså der hvor terrenget er mer kupert. Hvis vi har en stor helt flat slette kan dette altså bli en stor quad, som kun krever 4 punkter, og koster svært lite datakraft. Tilbake til brute force. Algoritmen jeg bruker går ganske enkelt igjennom radene og kolonnene i terrenget og legger til høydeverdiene definert i høydekartet. Vi går altså igjennom punktene for x (lengde retningen) og z aksene (dypde retningen), for så å legge til høydeverdiene på y aksen (høyderetningen). Figur 6 viser kjernen i denne algoritmen.

for ( X = 0; X < MAP_SIZE; X += STRIDE )
{
    for ( Y = 0; Y < MAP_SIZE; Y += STRIDE )
    {
        x = X;
        y = height(pHeightMap, X, Y );
        z = Y;
        glVertex3i(x, y, z);
        glVertex3i(...);
        ...
    }
}

figur 6

Denne koden i sin helhet finner du i terrain.cpp. Nå er terrenget rendret og vil for eksempel se ut som det venstre bildet i figur 8. Det eneste som gjenstår da, er glatting.

Glatting

Glatting er en egen vitenskap i seg selv og jeg skal ikke gå dypt ned i denne her. Skal kun forklare litt hva jeg har valgt åbruke til mitt terreng. Men først kan jeg nevne noen av de andre måtene det kan gjøres på. Man kan f.eks ta for seg nabopunktene og finne et gjennomsnitt, dette er ofte kalt et 'mean' filter, eller gjennomsnitts filter. Man kan bruke lavpass-, og høypassfilter, som henholdsvis setter grenser for hva som er max verdi eller min verdi for et punkt. Altså på samme måte som et lav/høypassfilter som du kanskje kjenner fra audio verdenen.

I tillegg har man blant annet Gaussfilter og båndfilter. Sistnevnte er det jeg bruker. Et båndfilter er sannsynligvis, sammen med gjennomsnittsfilter, det enkleste filteret å bruke, og å implementere. Dette baserer seg på at du sender en rad/kolonne av høydekartet til filteret. Filteret går så gjennom alle verdiene tilhørende den rad eller kolonne du sendte. Dette gjøres for å beregne de nye verdiene. Disse blir kalkulert ved å bruke den opprinnelige verdien, naboverdien og en konstant. Figur 7 viser kjernen i båndfilteret mitt.

void filterHeightField(BYTE* fpHeightData, float fFilter)
{
    int i;

    //filtrer fra venstre mot høyre
    for(i=0; i<MAP_SIZE; i++)
        filterHeightBand(&fpHeightData[MAP_SIZE*i], 1, MAP_SIZE, fFilter);

    //filtrer fra høyre mot venstre
    for(i=0; i<MAP_SIZE; i++)
        filterHeightBand(&fpHeightData[MAP_SIZE*i+MAP_SIZE-1], -1, MAP_SIZE, fFilter);

    //filtrer fra topp til bunn
    for(i=0; i<MAP_SIZE; i++)
        filterHeightBand(&fpHeightData[i], MAP_SIZE, MAP_SIZE, fFilter);

    //filtrer fra bunn til topp
    for(i=0; i<MAP_SIZE; i++)
        filterHeightBand(&fpHeightData[MAP_SIZE*(MAP_SIZE-1)+i], -MAP_SIZE, MAP_SIZE, fFilter);
}
    

figur 7

Og her på figur 8 kan du se et før og etter screenshot hvor det ble glattet 10 ganger.

glatting_450

figur 8

Støttefunksjoner

I tillegg til de tre hoveddelene som er beskrevet over, trenger man endel støttefunksjoner for å få alt til å fungere sammen. Dette inkluderer for eksempel funksjoner for å generere tilfeldig tall. Dette er en svært viktig egenskap i programmer som dette, og i de fleste større programmer faktisk. Jeg bruker to funksjoner, som begge baserer seg på ANSI C's rand() funksjon. I tillegg bruker Perlin Noise implementasjonen en egen vri med primtall, uten bruk av rand(). Figur 9 viser mine to random funksjoner, henholdsvis for å generere floats og integers.

float randfloat(float min, float max)
{
    //seed random nummer generatoren
    srand((unsigned)time(0));

    int r = rand() % (int) ((max*1000)-(min*1000));
    r += (int)(min*1000);

    return ((float) r / 1000.0f);
}

int randint(int min, int max)
{
    //seed random nummer generatoren
    srand((unsigned)time(0));

    int r = rand() % (int) ((max*1000)-(min*1000));
    r += (int)(min*1000);

    return (int)(r / 1000);
}
    

figur 9

Et par andre viktige funksjoner for mange OpenGL programmer er mulighet for å laste og lagre bilder. I main.cpp kan man ved å ta bort en kommentar tag i drawGLScene() laste inn et forhåndslaget gråskalabilde. loadRawFile("perlin.raw", MAP_SIZE*MAP_SIZE, g_HeightMap); er den magiske linjen som gjør dette. Jeg har kun funksjoner for å laste og lagre .raw filer av den grunn at dette er det enkleste formatet å håndtere. Bitmap (.bmp) og targa (.tga) krever headere og .raw kun er rådata, og trenger ikke dette.

Funksjonene for å lese inn og for å lagre en .raw fil er i grunn veldig like. Det er i hovedsak to linjer som skiller disse to, og disse er vist i figur 9 og 10. Fra loadRawFile():

//åpne i read/binary mode
pFile = fopen(strName, "rb");
...
//les ut data
fread(pHeightMap, 1, nSize, pFile);

figur 9

Fra saveAsRawFile():

//åpne i write/binary mode
pFile = fopen(strName, "wb");
...
//skriv data til fil
fwrite(pHeightMap, 1, nSize, pFile);
    

figur 10

Som vi kan se fra disse linjene er forskjellen hvilken modus vi åpner fila i, read/binary i load funksjonen og write/binary i save funksjonen. I tillegg bruker vi fread og fwrite for henholdsvis å lese og skrive fra eller til fil.

Oppsummering

Vi har gått igjennom opplasting og generering av høydekart. Vi har vært innom det å rendre et terreng basert på disse verdiene, og vi har sett på glatting. Dette er de 3 hovedstegene for å lage et veldig elementært terreng. Ting vi ikke har snakket om her for å gjøre terrenget brukbart i et spill eller liknende, er teksturer og lys. For at det virkelig skal se bra ut må vi ha en eller annen form for teksturer på og gjerne slagskygge fra fjell over resten av terrenget. For at vi skal fåen tekstur som stemmer overens med et realtime generert terreng, må vi generere teksturen realtime også. For mer informasjon om dette kan man gjøre et søk på google etter procedural texture generation. For å få best utnyttelse av denne modulen bør du ha kildekoden tilgjengelig og følge med i den etter hvert som du leser. Lykke til.

Screenshots

Tidlig i utviklingen

terreng02_sm terreng03_sm terreng04_sm terreng05_sm

Litt senere:

ss_illus03_sm ss_illus04_sm ss_illus05_sm ss_illus06_sm

Kildekode

Programmet er skrevet helt og holdent i C, men filene har endingene CPP for enkelhets skyld.

C-kode
  • main.cpp
  • perlin.cpp
  • smoothing.cpp
  • images.cpp
  • terrain.cpp
  • text.cpp
  • utils.cpp
Header filer
  • globals.h
  • perlin.h
  • smoothing.h
  • images.h
  • terrain.h
  • text.h

Hele VS prosjektet zip'et

Og her er C# koden til Perlin Noise bildegeneratoren:

cs_perlin_noise_v2.zip

[2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18]
Referanser
  1. Mandelbrot PicturesAnton Feenstrawww.few.vu.nl/~feenstra/mandel_gallery.html14-04-2010
  1. Latest 'NEHE' NewsNEHE, NeonHelium ProductionsOpenGL-tutorials.nehe.gamedev.net/14-03-2009
  1. OpenGL TutorialsProgramming resourceswww.alsprogrammingresource.com/opengl.html14-04-2010
  1. TutorialsOpenGL Colonywww.codecolony.de/opengl.htm14-04-2010
  1. Terrain Tutorialwww.lighthouse3d.com/opengl/terrain/index.php3?introduction14-04-2010
  1. The developers Toolboxflipcodediverse artiklerwww.flipcode.com/archives/toolbox.shtml14-04-2010
  1. Generating Random Fractal TerrainGame programmerwww.gameprogrammer.com/fractal.html14-04-2010
  1. 3D Graphic Java: Render fractal landscapeswww.javaworld.com/javaworld/jw-08-1998/jw-08-step.html14-04-2010
  1. Perlin Noisefreespace.virgin.net/hugo.elias/models/m_perlin.htm14-04-2010
  1. diverse lenkerwww.mandelbrot-dazibao.com/14-04-2010
  1. Perlin Noisewww.vbaccelerator.com/home/VB/Code/vbMedia/Algorithmic_Images/Perlin_Noise/article.asp14-04-2010
  1. The OpenGL Programming Guide, 6 editionDave Schreiner, Mason Woo,Jackie Neider,Tom Davies2007Addison-Wesley Professional0321481003www.opengl.org/documentation/red_book/14-03-2010
  1. OpenGL game programmingKen HawkinsCourse Technology PTR0761533303
  1. Focus On 3D Terrain ProgrammingTrent PolackCourse Technology PTR1592000282
  1. Interactive Computer Graphics - A Top-Down Approach with OpenGLEdward AngelAddison Wesley0201773430
  1. OpenGL SuperBibleRichard S. Wright, Benjamin Lipchak, Nicholas HaemelAddison Wesley0321498828
  1. Mathematics for 3D Game Programming & Computer GraphicsEric LengvelCharles River Media1584500379
  1. Digital Image ProcessingRafael C. Gonzales,Richard E. WoodsPrentice Hall013168728X
Vedlikehold

Skrevet av Jon Roar Odden juni 2005
Omformet til std layout, Børre Stenseth juli 2005

Å tegne:>Fraktal terreng
til toppen