計(jì)算機(jī)畢設(shè)外文翻譯

25-GeneratingRandomFractalTerrainPartI:GeneratingRandomFractalTerrainIntroductionTenyearsago,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-SimilarityThekeyconceptbehindanyfractalisself-similarity.Anobjectissaidtobeself-similarwhenmagnifiedsubsetsoftheobjectlooklike(oridenticalto)thewholeandtoeachother.2Considerthehumancirculatorysystem.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.Itakeupmuchlessspacethantheimageitself.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,eachrenderedwithvaryingHvaluesHeightMapsThemidpointdisplacementalgorithmdescribedabovecanbeimplementedusingaone-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.中文譯文：隨機(jī)分形地形的生成第一部分：生成隨機(jī)分形地形介紹十年前，我參加1986年SIGGRAPH活動(dòng)，GavinS.P.Miller那篇題為DefinitionandRenderingofTerrainMaps的論文讓我充滿敬畏。該文描述了少數(shù)生成分形地形的算法，作者還介紹了一個(gè)他們認(rèn)為更先進(jìn)的新方法。開始我被這些算法能夠生成難以置信的風(fēng)景圖所震驚！（盡管這些算法被作者認(rèn)為“漏洞百出”）后來(lái)，讀過(guò)論文，這些算法之簡(jiǎn)單將我完全打敗了。我從此成為一個(gè)分形地形迷。算法背后的數(shù)學(xué)可能相當(dāng)復(fù)雜。然而，完全理解這些數(shù)學(xué)并不是掌握這些算法的必要條件。很好，否則我得在解釋算法之前講解所有的數(shù)，也許永遠(yuǎn)也講不到算法。此外，關(guān)于分形數(shù)學(xué)的文字材料數(shù)以噸計(jì)，參見本文本的參考部分會(huì)有所幫助。同樣的原因，我不會(huì)深入到數(shù)學(xué)細(xì)節(jié)，也不包括對(duì)分形的廣泛總覽及它們可被用來(lái)做的每樣?xùn)|西。相反，我將描述分形地形生成背后的概念，并集中仔細(xì)講解我個(gè)人最喜歡的”diamond-square”算法。我將演示如何使用這個(gè)算法靜態(tài)拼嵌高度數(shù)據(jù)數(shù)組，這些數(shù)據(jù)可用于幾何地形數(shù)據(jù)、地形紋理數(shù)據(jù)及云紋理映射。分形有什么用呢？假定你已經(jīng)知道，那正是你讀本文的原因。隨機(jī)地形圖對(duì)飛行模擬或制作背景紋理圖（如顯示一帶遠(yuǎn)山）十分有用。生成地形的算法也可用于生成部分云天的紋理圖。在繼續(xù)之前，申明一下：我不是游戲程序員。如果你為找到一個(gè)快速繪制地形的算法而讀此文，那你來(lái)錯(cuò)了地方。我只描述生成地形模型的過(guò)程。著色繪制是你自己的事。自相似任何分形最關(guān)鍵的概念是自相似。當(dāng)一個(gè)物體的一部分放大后看起來(lái)仍與整個(gè)物體一樣，那這個(gè)物體就是自相似。考慮一下人體的循環(huán)系統(tǒng)。這是自然界中自相似的好例子。從最大的動(dòng)脈和靜脈分支直到最小的微血管，整個(gè)過(guò)程都顯現(xiàn)相同的分支模式。如果你不知道正在使用顯微鏡，將無(wú)法分辨微血管和大動(dòng)脈?，F(xiàn)在再考慮一個(gè)簡(jiǎn)單的球。它是自相似的嗎？不！大幅度放大后，它看起來(lái)不再象一個(gè)球，而象塊平板。如果你不相信，看看戶外。除非恰好你在太空軌道上看本文，否則將完全沒(méi)法看出地球是個(gè)球體。球體不是自相似的。它適用傳統(tǒng)的歐幾里德幾何描述而不是分形。地形屬于自相似范疇。手掌上的碎巖鋸齒狀邊緣與遠(yuǎn)處地平線邊的山脊有相同的不規(guī)則形狀。這使我們可以用分形來(lái)生成地形，不管顯示時(shí)怎么放大，它看起來(lái)仍然象地面。有關(guān)自相似請(qǐng)注意：嚴(yán)格意義下，它意味著自分辨(self-identical)，即，自身精確的縮略拷貝在逐漸放大縮小時(shí)可見。我并不知道自然界存在任何自分辨分形。但mandelbrot集是自分辨的。我不會(huì)進(jìn)一步討論Mandelbrot集。到參考里找進(jìn)一步的信息。一維中點(diǎn)變換后邊要講的diamond-square算法，在兩維上使用一種中點(diǎn)變換算法。為幫助你了解個(gè)大概，我們先看一維情況。當(dāng)山脈出現(xiàn)在遠(yuǎn)處地平線處時(shí)，一維中點(diǎn)變換是繪制山脊的好算法?？纯此窃趺垂ぷ鞯模阂砸粭l水平地平線段開始重復(fù)足夠多次{對(duì)場(chǎng)景中的每條線段做{找到線段的中點(diǎn)在Y方向上隨機(jī)移動(dòng)中點(diǎn)一段距離減小隨機(jī)數(shù)取值范圍}}將隨機(jī)數(shù)值域減速小多少呢？那取決于你想要分形的陡峭程度。每次循環(huán)減少的越多，所得山脊線就越平滑。但如果減得太多，則會(huì)有明顯的鋸齒感?？梢源植诙却嬖谝粋€(gè)常量里。后面會(huì)解釋如何做。來(lái)看個(gè)例子。我們以一條x從-1.0到1.0，y均為0的線段開始。開始，我們將隨機(jī)值范圍設(shè)為-1.0到1.0（可任意取）。這樣我們?cè)诖朔秶锷梢粋€(gè)數(shù)字，并將中點(diǎn)移動(dòng)這么多。這之后，我們就得到了：現(xiàn)在第二次經(jīng)過(guò)外圈循環(huán)，我們有兩段，長(zhǎng)度均原來(lái)的一半。我們的隨機(jī)值也減半，即-0.5到0.5。我們?yōu)閮蓚€(gè)中點(diǎn)都生成一個(gè)這個(gè)范圍內(nèi)的隨機(jī)點(diǎn)，結(jié)果為：再次縮減范圍，現(xiàn)在是-0.25到0.25。再以該范圍內(nèi)的數(shù)變換四個(gè)中點(diǎn)后，我們得到了：有兩件事你可能已經(jīng)注意到了。首先，它是遞歸的。實(shí)際上，它可以用一個(gè)迭代過(guò)程相當(dāng)自然的實(shí)現(xiàn)。對(duì)于這種情況，遞歸或迭代都成。對(duì)于表面生成代碼，使用迭代實(shí)現(xiàn)比遞歸會(huì)有一些好處。所以為保持一致，線和面相應(yīng)的代碼都