计算机毕设外文翻译.docx

计算机毕设外文翻译.docx

《计算机毕设外文翻译.docx》由会员分享，可在线阅读，更多相关《计算机毕设外文翻译.docx（10页珍藏版）》请在冰点文库上搜索。

计算机毕设外文翻译

GeneratingRandomFractalTerrain

PartI:

GeneratingRandomFractalTerrain

Introduction

Tenyearsago,Istumbledacrossthe1986SIGGRAPHProceedingsandwasawestruckbyonepaperinparticular,entitledTheDefinitionandRenderingofTerrainMapsbyGavinS.P.Miller1.Itdescribedahandfulofalgorithmsforgeneratingfractalterrain,andtheauthorsalsointroduceanewmethodwhichtheyconsideredtobeanimprovement.

InitiallyIwasimpressedthatthesealgorithms（eventhealgorithmsconsidered"flawed"bytheauthors）couldcreatesuchincrediblelandscapeimages!

Then,uponreadingthepaper,Iwasflooredbythesimplicityofthesealgorithms.

I'vebeenafractalterrainaddicteversince.

Themathbehindthealgorithmcangetquitecomplex.However,completelyunderstandingthemathisnotaprerequisiteforgraspingthealgorithm.Andthat'sgood.BecauseifIhadtoexplainallthemathtoyoubeforeexplainingthealgorithm,we'dnevergettothealgorithm.Besides,thereisliterallytonsofmaterialoutthereonthemathematicalconceptsinvolvedinfractals.Seethereferencesattheendofthisarticleforagoodstart.

ForthesamereasonsthatIwon'tgointothemathdetails,Ican'tincludeabroadoverviewoffractalsandeverythingtheycanbeusedfor.Instead,I'mgoingdescribetheconceptsbehindfractalterraingeneration,andgiveafocusedanddetaileddescriptionofmypersonalfavoritealgorithm:

the"diamond-square"algorithm.I'lldemonstratehowtousethisalgorithmtostaticallytessellateanarrayofheightdatathatcanbeusedforgeometricterraindata,terraintexturemaps,andcloudtexturemaps.

Whatcanyoudowithafractalterrain?

Iassumeyoualreadyknowthat;that'swhyyou'rereadingthis.Randomterrainmapsaregreatforflightsimulatorsormakingtexturemapstouseasabackground（showingadistantmountainrange,forexample）.Thesamealgorithmthatmakesterraincanalsobeusedtogeneratetexturemapsforpartlycloudyskies.

BeforeIgofurther,adisclaimer:

Iamnotagameprogrammer.Ifyouarereadingthisbecauseyouwantalgorithmsforrenderingterrainquickly,you'vecometothewrongplace.I'llonlydescribetheprocessofgeneratingtheterrainmodel.Howyourenderitisuptoyou.

Self-Similarity

Thekeyconceptbehindanyfractalisself-similarity.Anobjectissaidtobeself-similarwhenmagnifiedsubsetsoftheobjectlooklike（oridenticalto）thewholeandtoeachother.2

Considerthehumancirculatorysystem.Thisisafineexampleofself-similarityinnature.Thesamebranchingpatternisexhibitedfromthelargestarteriesandveinsallthewaydowntothesmallestcapillaries.Ifyoudidn'tknowyouwereusingamicroscope,youwouldn'tbeabletotellthedifferencebetweencapillariesandarteries.

Nowconsiderasimplesphere.Isitself-similar?

No.Atsignificantlylargemagnification,itstopslookinglikeaspherealtogetherandstartslookinglikeaflatplane.Ifyoudon'tbelieveme,justtakealookoutside.Unlessyouhappentobeinorbitwhilereadingthis,you'llseenoindicationthattheEarthisasphere.Asphereisnotself-similar.ItisbestdescribedusingtraditionalEuclideangeometry,ratherthanafractalalgorithm.

Terrainfallsintothe"self-similar"category.Thejaggededgeofabrokenrockinthepalmofyourhandhasthesameirregularitiesasaridgelineonadistanthorizon.Thisallowsustousefractalstogenerateterrainwhichstilllooksliketerrain,regardlessofthescaleinwhichitisdisplayed.

Asidenoteonself-similarity:

Initsstrictestsense,itmeansself-identical,thatis,exactminiaturecopiesofitselfarevisibleatincreasinglysmallorlargescales.Iactuallydon'tknowofanyself-identicalfractalsthatexistinnature.ButtheMandelbrotsetisself-identical.Iwon'tevengointodescribingtheMandelbrotset.Godigupanyofthereferencesformoreinfo.

MidpointDisplacementinOneDimension

Thediamond-squarealgorithm,whichIwilldescribelater,usesakindofmidpoint-displacementalgorithmintwodimensions.Tohelpyougetagriponit,we'lllookatitfirstinonedimension.

One-dimensionalmidpointdisplacementisagreatalgorithmfordrawingaridgeline,asmountainsmightappearonadistanthorizon.Here'showitworks:

Startwithasinglehorizontallinesegment.

Repeatforasufficientlylargenumberoftimes{

Repeatovereachlinesegmentinthescene{

Findthemidpointofthelinesegment.

DisplacethemidpointinYbyarandomamount.

Reducetherangeforrandomnumbers.

}

}

Howmuchdoyoureducetherandomnumberrange?

Thatdependsonhowroughyouwantyourfractal.Themoreyoureduceiteachpassthroughtheloop,thesmoothertheresultingridgelinewillbe.Ifyoudon'treducetherangeverymuch,theresultingridgelinewillbeveryjagged.Itturnsoutyoucantieroughnesstoaconstant;I'llexplainhowtodothislateron.

Let'slookatanexample.Here,westartwithalinefrom-1.0to1.0inX,withtheYvalueateachendpointbeingzero.Initiallywe'llsettherandomnumberrangetobefrom-1.0to1.0（arbitrary）.Sowegeneratearandomnumberinthatrange,anddisplacethemidpointbythatamount.Afterdoingthis,wehave:

Nowthesecondtimethroughtheouterloop,wehavetwosegments,eachhalfthelengthoftheoriginalsegment.Ourrandomnumberrangeisreducedbyhalf,soitisnow-0.5to0.5.Wegeneratearandomnumberinthisrangeforeachofthetwomidpoints.Here'stheresult:

Weshrinktherangeagain;itisnow-0.25to0.25.Afterdisplacingthefourmidpointswithrandomnumbersinthisrange,wehave:

Twothingsyoushouldnoteaboutthis.

First,it'srecursive.Actually,itcanbeimplementedquitenaturallyasaniterativeroutine.Forthiscase,eitherrecursiveoriterativewoulddo.Itturnsoutthatforthesurfacegenerationcode,therearesomeadvantagestousinganiterativeimplementationoverarecursiveone.Soforconsistency,theaccompanyingsamplecodeimplementsboththelineandsurfacecodeasiterative.

Second,it'saverysimplealgorithm,yetitcreatesaverycomplexresult.Thatisthebeautyoffractalalgorithms.Afewsimpleinstructionscancreateaveryrichanddetailedimage.

HereIgooffonatangent:

Therealizationthatasmall,simplesetofinstructionscancreateacompleximagehasleadtoresearchinanewfieldknownasfractalimagecompression.Theideaistostorethesimple,recursiveinstructionsforcreatingtheimageratherthanstoringtheimageitself.Thisworksgreatforimageswhicharetrulyfractalinnature,sincetheinstructionstakeupmuchlessspacethantheimageitself.ChaosandFractals,NewFrontiersofScience3hasachapterandanappendixdevotedtothistopicandisagreatreadforanyfractalnutingeneral.

Backtoreality.

Withoutmucheffort,youcanreadtheoutputofthisfunctionintoapaintprogramandcomeupwithsomethinglikethis:

Thiscouldbeusedassceneryoutsideawindow,forexample.Thenicethingaboutitisthatitwraps,soyoucankeeparoundonerelativelysmallimageandcompletelywrapascenewithit.Thatis,ifyoudon'tmindseeingthesamemountainineverydirection.

OK,beforewegointo2Dfractalsurfaces,youneedtoknowabouttheroughnessconstant.Thisisthevaluewhichwilldeterminehowmuchtherandomnumberrangeisreducedeachtimethroughtheloopand,therefore,willdeterminetheroughnessoftheresultingfractal.Thesamplecodeusesafloating-pointnumberintherange0.0to1.0andcallsitH.2（-H）isthereforeanumberintherange1.0（forsmallH）to0.5（forlargeH）.Therandomnumberrangecanbemultipliedbythisamounteachtimethroughtheloop.WithHsetto1.0,therandomnumberrangewillbehalvedeachtimethroughtheloop,resultinginaverysmoothfractal.WithHsetto0.0,therangewillnotbereducedatall,resultinginsomethingquitejagged.

Herearethreeridgelines,eachrenderedwithvaryingHvalues

HeightMaps

Themidpointdisplacementalgorithmdescribedabovecanbeimplementedusingaone-dimensionalarrayofheightvalueswhichindicatetheverticallocationofeachlinesegmentvertex.Thisarrayisaone-dimensionalheightmap.Itmapsitsindices（Xvalues）toheightvalues（Yvalues）.

Tosimulaterandomterrain,wewanttoextrapolatethisalgorithminto3Dspace,andtodosoweneedatwo-dimensionalarrayofheightvalueswhichwillmapindices（XandZvalues）intoheightvalues（Yvalues）.Notethatalthoughourendgoalhereistogeneratethree-dimensionalcoordinates,thearrayonlyneedstostoretheheight（Y）values;thehorizontal（XandZ）valuescanbegeneratedontheflyasweparsethroughthearray.

Byassigningacolortoeachheightvalue,youcoulddisplayaheightmapasanimage.Here,highpointsintheterrain（largevalues）arerepresentedbywhite,andlowpoints（smallvalues）arerepresentedbyblack:

Renderingaheightmapthiswayisusefulforgeneratingcloudtexturemaps,whichI'lldiscusslater.Sucharepresentationcouldalsobeusedtoseedaheightmap.

中文译文：

随机分形地形的生成

第一部分：

生成随机分形地形

介绍

十年前，我参加1986年SIGGRAPH活动，GavinS.P.Miller那篇题为DefinitionandRenderingofTerrainMaps的论文让我充满敬畏。

该文描述了少数生成分形地形的算法，作者还介绍了一个他们认为更先进的新方法。

开始我被这些算法能够生成难以置信的风景图所震惊！

（尽管这些算法被作者认为“漏洞百出”）后来，读过论文，这些算法之简单将我完全打败了。

我从此成为一个分形地形迷。

算法背后的数学可能相当复杂。

然而，完全理解这些数学并不是掌握这些算法的必要条件。

很好，否则我得在解释算法之前讲解所有的数，也许永远也讲不到算法。

此外，关于分形数学的文字材料数以吨计，参见本文本的参考部分会有所帮助。

同样的原因，我不会深入到数学细节，也不包括对分形的广泛总览及它们可被用来做的每样东西。

相反，我将描述分形地形生成背后的概念，并集中仔细讲解我个人最喜欢的”diamond-square”算法。

我将演示如何使用这个算法静态拼嵌高度数据数组，这些数据可用于几何地形数据、地形纹理数据及云纹理映射。

分形有什么用呢？

假定你已经知道，那正是你读本文的原因。

随机地形图对飞行模拟或制作背景纹理图（如显示一带远山）十分有用。

生成地形的算法也可用于生成部分云天的纹理图。

在继续之前，申明一下：

我不是游戏程序员。

如果你为找到一个快速绘制地形的算法而读此文，那你来错了地方。