terrain generation, papers, graphics, terrain
[ Pobierz całość w formacie PDF ]
RealtimeProceduralTerrainGeneration
RealtimeSynthesisofErodedFractalTerrainforUseinComputerGames
JacobOlsen,
DepartmentofMathematicsAndComputerScience(IMADA)
UniversityofSouthernDenmark
October31,2004
Abstract
Definitions
Themaingoalofthispaperistoprovidean
overviewofavarietyofmethodsforsynthesis
oferodedterrainforuseincomputergames,VR
worldsandthelike.Traditionally,suchsoftware
useseitherpredefinedterrainsorruntimegen-
erateddatabasedonsimplefractalnoisetech-
niques.
Inrecentyears,theadvancesinprocessingpower
ofaveragehomecomputershavemadeitpos-
sibletosimulateerosionprocessesnear-realtime
byputtingemphasisonspeedattheexpenseof
physicalcorrectness.Thispaperpresentsafast
methodtosynthesizenaturallookingfractalter-
rainandthenproceedstoevaluateandsuggest
optimizationsfortwoofthemostcommonlyused
erosionalgorithms[1,2].Withsomecriteriafor
applicabilityincomputergamesinmind,anew
andmuchfasteralgorithmisthenproposed.Fi-
nally,afewissuesregardingterrainmodifications
formaximumplayabilityarediscussed.
Datarepresentation
Inthealgorithmsdescribedinthispaper,terrain
willberepresentedbytwo-dimensionalheight
mapsusingfloatingpointvaluesbetween0and1.
Unlessotherwisestated,allexamplesusesquare
mapswithsidelengthN=2
9
=512,givinga
totalofN
2
=2
18
=262144cells,eachcellcon-
tainingaheightvalue.
TheheightmapisdenotedHandtheindividual
cellsareaddressedash
i
,
j
,whereiandjarecoor-
dinatesrangingfrom0to511.Somecalculations
willaddresscellsoutsidethisrange;inthiscase,
moduloisusedtowrapthecoordinatesaroundso
thattherightneighbourofaright-mostcellwill
betheleft-mostcellinthesamerowetc.
AllimplementationsweredoneiJava,andallcal-
culationtimesarefromtestsexecutedonafairly
standard2.4GHzPentium4PC.
Definingerosion
Figure1:Arenderedviewofasynthesized,
erodedterraincreatedwiththetechniquesdis-
cussedinthispaper.
Theeectsoferosionarediculttodescribe
mathematically:Thetermerosioncoversmany
naturallyoccurringphenomena,anddierentter-
raintypesandclimateswillproducemanydier-
entkindsofchangestoalandscape.Forsim-
plicity,asetofdesirabletraits(fromacomputer
gamedevelopmentperspective)thatwillbeused
tomeasurehowerodedaheightmapis,isdefined.
Overall,mosttypesoferosiondissolvematerial
fromsteepslopes,transportitdownhillandthen
depositthematerialatlowerinclinations.This
tendstomakesteepslopesevensteeper,andflat-
tenoutlow-altitudeterrainwhenthetransported
materialisdeposited.Toaidintheanalysisofthe
changesininclination,theslopemapSisdefined
1
suchthat
ofthefrequency,i.e.
s
i,j
=max(|h
i,j
−h
i
−
1,j
|,
|h
i,j
−h
i+1,j
|,
|h
i,j
−h
i,j
−
1
|,
|h
i,j
−h
i,j+1
|)
P(f)=
1
f
a
whereP(f)isthepowerfunctionofthefrequency
andaiscloseto1.Thiskindofnoiseapprox-
imatesreal-worldunerodedmountainousterrain
wellandhasbeenusedwidelyincomputergraph-
icsforthepastdecades.Twomethodsforgener-
ating1/f-likenoise,spectralsynthesisandmid-
pointdisplacement,arediscussedbelow.
Ingeneratingaterrainbasefortheerosional-
gorithmstoworkon,itisworthnotingthatthe
closertheterrainbaseistothedesiredresult,
thelessworkisrequiredbythe(oftencalculation
heavy)erosionalgorithmitself.Tohelpcreatea
terrainbasewithbettercharacteristicsoferoded
terrain,theuseofVoronoidiagramsandpertur-
bationfilteringareintroducedbelow.
inotherwords,thegreatestoftheheightdier-
encesbetweenthecellanditsfourneighboursin
aVonNeumannneighbourhood.
Thispaperfocusesonthesynthesisoferodedter-
rainforuseincomputergames;therefore,the
idealforerodedterrainmustsuitthisapplica-
tion.Physicalcorrectnessandvisualappearance
aresecondary,whatmattersisapplicability.In
mostcomputergamesandVRenvironmentsus-
inglarge-scaleoutdoorterrain,personsorvehicles
movearoundontheterrain,andvariousstruc-
turesareplacedontheterrain.Movementand
structureplacingisoftenrestrictedtolowincli-
nations,whichmeansthatalowaveragevalue
ofaheightmap’scorrespondingslopemapisde-
sirable.Thisrulealonewouldmakeaperfectly
flatheightmapideal,whichiswhyasecondrule
isaddedsayingthegreaterthestandarddevia-
tionoftheslopemap,thebetter.Theidealfor
erodedterrainisthereforeaheightmapwhose
correspondingslopemaphasalowmeanvalue
(reflectingtheoverallflatteningoftheterraindue
tomaterialdeposition)andahighstandarddevi-
ation(materialisdissolvedfromsteepareasmak-
ingthemevensteeper,anddepositionflattensthe
flatareasfurther).Theslopemapmeanvalue,¯s,
andstandarddeviation,
s
,aredefinedonthe
slopemapSasfollows:
Spectralsynthesis
Spectralsynthesissimulates1/fnoisebyadding
severaloctaves(layers)together,eachoctavecon-
sistingofnoisewithallitsspectralenergyconcen-
tratedonasinglefrequency.Foreachoctave,the
noisefrequencyisdoubledandtheamplitudeA
iscalculatedby
A=p
i
whereiistheoctavenumberstartingwith0at
thelowestfrequencyandpiscalledthepersis-
tence.Lettingp=0.5willapproximate1/fnoise
becauseeachtimethefrequencyisdoubledinthe
nextoctave,theamplitudewillbehalved.
Theoctavesthemselvesarecreatedbyfilling
inevenlyspacedpseudorandomnumberscorre-
spondingtotheoctaves’sfrequency,andthencal-
culatetheremainingvaluesbyinterpolation-see
Figure2foravisualcomparisonofinterpolation
methods.Whilecubicinterpolationgivesthebest
results,theslightlyvisibleverticalandhorizontal
artifactscausedbylinearinterpolationareanac-
ceptabletrade-oforacomputationtimereduced
toroughlyonefifth.
¯s=
1
N
2
N
−
1
X
N
−
1
X
s
i,j
i=0
j=0
s
=
v
u
u
t
1
N
2
N
−
1
X
N
−
1
X
(s
i,j
−¯s)
2
i=0
j=0
Usingthese,anoverall”erosionscore”,",isde-
finedas
"=
s
¯s
(ontheassumptionthat¯s6=0)
Midpointdisplacement
Anotherapproachatsimulating1/fnoiseisby
amidpointdisplacementmethod,inthiscasethe
diamond-squarealgorithm[3,4,5]. Insteadof
calculatingeverycellinseveraloctaves(upto9
octaveswithN=2
9
)andthenaddingtogether
theoctaves,thevalueofeachcellneedonlybe
calculatedonce.
Themidpointdisplacementmethodworksbyre-
cursivelycalculatingthemissingvalueshalfway
Generationofbaseterrain
Atechniqueoftenusedforfastterraingenera-
tionissimulating1/fnoise(alsoknownas”pink
noise”)whichischaracterizedbythespectralen-
ergydensitybeingproportionaltothereciprocal
2
erodedlookbymultiplyingthesizeoftheoset
rangewiththeheightaveragewhencalculating
newvalues.Thiscauseslowaltitudeareastobe-
comesmoother,therebysimulatingdepositionof
erodedmaterial.Thismethodisreferredtoas
smoothedmidpointdisplacement.
Figure2:Cubicinterpolation(left)versuslin-
earinterpolation(right)forthespectralsynthesis
algorithm.
betweenalreadyknownvaluesandthenrandomly
osetthenewvaluesinsidearangedetermined
bythecurrentdepthoftherecursion.With
apersistenceof0.5,thisrangeishalvedwith
eachrecursivestep,andanapproximationof
1/fnoiseiscreated.Ideally,therandomosets
shouldhaveagaussiandistributioninsidetheo-
setrange,butforthepurposeofsynthesizingter-
rain,uniformlydistributedvaluesareacceptable
(andmuchfastertocalculate).
Theimplementationdoneforthispaperisthe
square-diamondalgorithm,namedaftertheor-
derinwhichmidpointvaluesaredetermined(see
Figure3).
Figure4:Gaussian(left)versusuniform(right)
distributionofrandomosetsforthemidpoint
displacementalgorithm.
Voronoidiagrams
Theproblemwithusing1/fnoiseforsimulating
realworldterrainisthatitisstatisticallyhomoge-
neousandisotropic-propertiesthatrealterrain
doesnotshare.Onewaytobreakthemonotony
andcontrolthemajorcharacteristicsoftheland-
scapeareVoronoidiagramswhoseuseinproce-
duraltexturegenerationhasbeendescribedby
StevenWorley[6].Voronoidiagramscanbeused
foravarietyofeectswhencreatingprocedural
textures-mostvariantsresemblesomesortof
cell-likestructuresthatcanbeusedtosimulate
tissue,sponge,scales,pebbles,flagstones,orin
thiscase,entiremountains.
Theimplementationusedinthispaperworksby
dividingthemapintoregionsandthenrandomly
placeanumberof”featurepoints”ineachre-
gion.Foreachcellinthemap,asetofvalues
d
n
,n=1,2,3,...arecalculatedaccordingtoa
defineddistancemetricsothatd
1
isthedistance
tothenearestfeaturepoint,d
2
isthedistanceto
thenextnearestdistancepointetc.Linearcom-
binationsoftheform
s
s
c
c
c
s
c
c
c
c
c
s s
c
s s
s s s
c c
s
s
c
s
c
c
c
c
s s
c
s s
s s s
c c
s
s
c
c
c
s
c
c
c
c
c
s s
c
a b c d e
Figure3:Twoiterationsofthediamond-square
algorithm.Pseudorandomnumberareusedfor
initialvaluesinstepa.Instepb(the”diamond”
step)anewvalueisfoundbyosettingtheav-
erageofthefourvaluesofstepa.Stepc(the
”square”step)fillsintherestofthemidpoint
valuesalsobyosettingtheaverageofthefour
neighboursofeachnewpoint.Stepsdandeshow
thenextiteration.
Figure4showsavisualcomparisonofthetwo
waysofdistributingvaluesinsidetherandomo-
setranges.Althoughuniformdistributionpro-
ducesamorejaggedterrain,thiscanbecompen-
satedforbyloweringthepersistence.Sincethe
versionusinggaussiandistributiontakes4times
longertogenerate,uniformdistributionistobe
preferred.
Themidpointdisplacementmethodalsoallows
forindividualadjustmentsoftherandomo-
setrangesdependingoncoordinatesoraltitude,
whichcanbeusedtogivetheterrainamore
h=c
1
d
1
+c
2
d
2
+c
3
d
3
+···+c
n
d
n
withcoecientsc
1
...c
n
willthenproduce
thecellularstructures-seeFigure5forex-
amples. Forcreatingmountainousfeatures,
thecoecientsc
1
=−1andc
2
=1(with
therestbeingzeroes)areusedasitcanadd
distinctridgelinesandconnectedriverbedsto
theterrain.ThesevaluesalsogivetheVoronoi
diagramsanotherusefulpropertywhichwillbe
3
c
c
c
Combinationandperturbation
Figure5:ExamplesofVoronoidiagramswith
coecientsc
1
=−1(upperleft),c
2
=1(upper
right),c
3
=1(bottomleft),c
1
=−1andc
2
=1
(bottomright).
AlthoughVoronoidiagramshavesomeuseful
propertiesthat1/fnoiselacks,theyarenosub-
stituteforthenoisefunctions.Thebestresults
areachievedwithsomecombinationofboth;in
thiscasetwothirdssmootheddiamond-square
methodnoiseandonethirdVoronoidiagramwith
coecientsc
1
=−1andc
2
=1willbeused.This
combinationisreferredtoasthecombinedheight
map.
TocrumplethestraightlinesoftheVoronoidi-
agram,aperturbationfilterasdescribedin[6]
pages90-91isapplied.Thisfilterworksbyus-
inganoisefunction(similartotheonesdescribed
above)tocalculateadisplacementwithrandom
distanceanddirectionforeachcell.Thecom-
binedheightmapbeforeandafterperturbation
canbeseeninFigure7.Themagnitudeofthe
perturbationfilteringissetto0.25,meaningthat
agivenpointintheheightmapcannotbedis-
placedmorethan
N
4
cells.
Theperturbationfilteringitselfalsoincreasesthe
erosionscorebecausesomeareasarestretched
andsomearecompressed,whichincreases
s
.
Figure8showstheaveragerelationshipbetween
perturbationmagnitudeanderosionscoreforat
largenumberoftestrunsonthecombinedheight
mapgeneratedfromdierentrandomseednum-
bers.Erosionscorerisestoamaximumataper-
turbationmagnitudeof0.25andthenslowlyde-
clines.
coveredinthesectionregardingplayabilityissues.
Normally,distancesaredeterminedbytheEu-
clideandistancemetric
d=
p
dx
2
+dy
2
whichisquiteslowbecauseofthesquareroot.
Changingthedistancemetricto
d=dx
2
+dy
2
producesalargespeedup.AsFigure6shows,the
dierenceintheresultingheightmapisinsignif-
icant.Thisoptimizationtogetherwithareduc-
tioninsearchradiuswhenfindingnearestfeature
points(whichoccasionallyproducesminorerrors)
reducescalculationtimetoonethird.
Figure7:Thecombinedheightmapbeforeper-
turbation(left)andafter(right).
ThefinalbaseterrainisshowninFigure9.For
visualcomparison,allimageexamplesofvarious
erosionalgorithmsinthefollowingsectionsuse
thisterrainasastartingpoint.Figure10shows
arenderedviewofthisheightmap.
Figure6:Euclideandistancemetric(left)ver-
susthefasterdistancemetric(right)forVoronoi
diagrams.
Analysis
Averagecalculationtimesanderosionscoresfor
themethodsdiscussedinthissectioncanbeseen
inTable1.Ascanbeseen,theimplementations
ofspectralsynthesisandmidpointdisplacement
4
0.675
0.650
0.625
0.600
0.575
0.550
0.525
0.500
0.475
0.000.250.500.751.00
Perturbation magnitude
Figure8:Therelationshipbetweenperturbation
magnitudeanderosionscoreforthecombined
heightmap.
allachievenearlythesameerosionscore,butthe
midpointdisplacementmethodwithuniformran-
domosetdistributionisbyfarthefastest.The
smoothedversionisonlymarginallyslower,but
managestoachieveahighererosionscore.
TheVoronoidiagramsinthemselvesdonotscore
asmuchasthenoisefunctions,butthefastermet-
ricseemstobebettersuitedforthecoecients
used.Whencombinedwiththemodifiedversion
ofthemidpointdisplacementmethod,theero-
sionscorealmostreachesthelevelofthemodified
midpointdisplacementmethodalone.Asshown
inFigure8,theperturbationfilterimprovesthe
erosionscoreevenfurther.
WithN=512thebaseterraincanbesynthesized
inlessthan1second.EvenwithN=1024,the
synthesisofthebaseterrainisdoneinlessthan
3seconds.
Figure9:Thebaseterrainusedinimageexam-
plesoftheerosionalgorithms.
donebyexaminingeachcellanditsneighbour-
hoodinturn.Twodierenttypesofneighbour-
hoodsareused:TheMooreneighbourhoodwhich
includesall8neighboursofacell,andtheVon
Neumannneighbourhoodwhichonlyincludes4
oftheneighbouringcells(seeFigure11).With
thecurrentlyexaminedcellhavingvaluehand
itsneighboursbeingnamedh
i
,theheightdier-
encetoeachneighbour,d
i
,isdefinedas
d
i
=h−h
i
meaningthatlowerneighboursproducepositive
heightdierences.Formaximumcorrectness,the
Mooreneighbourhoodwasusedinbothreference
implementations.
Erosionalgorithms
Thermalerosion
Twotypesoferosionalgorithmsareexaminedin
thissection,namelythermalerosion(sometimes
referredtoasthermalweathering)andhydraulic
erosion.ThesewerefirstdescribedbyKenMus-
graveetalin1989[1],andhavesinceestablished
themselvesasabasefromwhichvariousimprove-
ments(mostlyintermsofphysicalcorrectness)
havebeensuggested[2,7,8,9,10].
Areferenceimplementationofeachtypeiscom-
paredtospeedoptimizedversionthatwillstill
delivercomparableresults.Forthermalerosion,
theoriginalmethodsuggestedin[1]isused,while
aversionofhydraulicerosionsuggestedin[2]is
usedbecauseofitsspeed.
Bothmethodsareiteratedcellularautomata
meaningthatcalculationsineachiterationare
Overview
Thermalerosionsimulatesmaterialbrakingloose
andslidingdownslopestopileupatthebottom.
Thereferenceimplementationworksasfollows:A
percentageofthematerialatthetopofaslope
whoseinclinationisaboveathresholdvalue-the
talusangleT-willbemoveddowntheslopeuntil
theinclinationreachesT:
h
i
=
d
i
>T:h
i
+c(d
i
−T)
d
i
T:h
i
ThisisillustratedinFigure12:Atthefirst
timestep,d
1
=Tandd
2
>T,whichmeansthat
materialwillbemovedfromhtoh
2
.Withc=1,
theamountofmovedmaterialresultsind
2
=T
5
0.450
[ Pobierz całość w formacie PDF ]