Fraktalterreng
figur 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.
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å.
figur 4
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.
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.
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
Litt senere:
Kildekode
Programmet er skrevet helt og holdent i C, men filene har endingene CPP for enkelhets skyld.
- main.cpp
- perlin.cpp
- smoothing.cpp
- images.cpp
- terrain.cpp
- text.cpp
- utils.cpp
- 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
