Terrain Simplification Simplified A General

LawrenceLivermoreNationalLaboratoryU.S.DepartmentofEnergyPreprintUCRL-JC-147847TerrainSimplificationSimplified:AGeneralFrameworkforView-DependentOut-of-CoreVisualizationP.LindstromandV.PascucciShorterversiontoappearinIEEETransactionsonVisualizationandComputerGraphicsMay8,2002Approvedforpublicrelease;furtherdisseminationunlimitedDISCLAIMERThisdocumentwaspreparedasanaccountofworksponsoredbyanagencyoftheUnitedStatesGovernment.NeithertheUnitedStatesGov-ernmentnortheUniversityofCalifornianoranyoftheiremployees,makesanywarranty,expressorimplied,orassumesanylegalliabilityorresponsibilityfortheaccuracy,completeness,orusefulnessofanyin-formation,apparatus,product,orprocessdisclosed,orrepresentsthatitsusewouldnotinfringeprivatelyownedrights.Referencehereintoanyspecificcommercialproduct,process,orservicebytradename,trade-mark,manufacturer,orotherwise,doesnotnecessarilyconstituteorim-plyitsendorsement,recommendation,orfavoringbytheUnitedStatesGovernmentortheUniversityofCalifornia.TheviewsandopinionsofauthorsexpressedhereindonotnecessarilystateorreflectthoseoftheUnitedStatesGovernmentortheUniversityofCalifornia,andshallnotbeusedforadvertisingorproductendorsementpurposes.Thisreporthasbeenreproduceddirectlyfromthebestavailablecopy.AvailabletoDOEandDOEcontractorsfromtheOfficeofScientificandTechnicalInformationP.O.Box62,OakRidge,TN37831Pricesavailablefrom(423)576-8401field,VA22161’sDigitalLibraryficationSimplified:AGeneralFrameworkforView-DependentOut-of-CoreVisualizationPeterLindstromandValerioPascucciAbstract—Thispaperdescribesageneralframeworkforout-of-coreren-deringandmanagementofmassiveterrainsurfaces.Thetwokeycom-ponentsofthisframeworkare:view-dependentrefinementoftheterrainmesh;andasimpleschemefororganizingtheterraindatatoimproveco-herenceandreducethenumberofpagingeventsfromexternalstoragetomainmemory.Similartoseveralpreviouslyproposedmethodsforview-dependentrefinement,werecursivelysubdivideatrianglemeshdefinedoverregularlygriddeddatausinglongest-edgebisection.Aspartofthissin-gle,per-framerefinementpass,weperformtrianglestripping,viewfrustumculling,andsmoothblendingofgeometryusinggeomorphing.Meanwhile,ourrefinementframeworksupportsalargeclassoferrormetrics,ishighlycompetitiveintermsofrenderingperformance,andissurprisinglysimpletoimplement.Independentofourrefinementalgorithm,wealsodescribeseveraldatalayouttechniquesforprovidingcoherentaccesstotheterraindata.Byre-orderingthedatainamannerthatismoreconsistentwithourrecursiveaccesspattern,weshowthatvisualizationofgigabyte-sizedatasetscanberealizedevenonlow-end,commodityPCswithouttheneedforcom-plicatedandexplicitdatapagingtechniques.Rather,byvirtueofdramaticimprovementsinmultilevelcachecoherence,werelyonthebuilt-inpagingmechanismsoftheoperatingsystemtoperformthistask.Theendresultisastraightforward,simple-to-implement,pointerlessindexingschemethatdramaticallyimprovesthedatalocalityandpagingperformanceovercon-ventionalmatrix-basedlayouts.I.INTRODUCTIONView-dependentrefinementandout-of-coredatamanage-mentaretwocriticalcomponentsoflarge-scale,interactivevi-sualizationofmassiveterrainsurfaces.Inrecentyearssev-eraleffectiveyetquitecomplicated,oftenspecialized,andmanytimesincompatiblemethodshavebeenproposedforthesetwotasks.Whereaslarge-scaleterrainvisualizationwasoncesyn-onymouswithindustrialflightsimulation,aplethoraofemerg-inguses,ranginganywherefrommilitaryandscientificappli-cationstovideogamesandhobbyuse,suggestthatsimple-to-implementyetpowerfulalgorithmsforterrainvisualizationarebecomingincreasinglyvaluable.Inparttoaddressthisprob-lem,werecentlyproposedageneralframeworkforperforminghighlyinteractiveview-dependentrendering,aswellasatrans-parentmechanismforimprovingmultilevelcacheperformanceandenablingefficientpagingofgigabyte-sizedatasets[1].Inthispaper,weprovideanextendedoverviewandin-depthdis-cussionofthesealgorithms,whiletakingcaretogiveenoughdetailtomakeend-to-endimplementationsofouralgorithmsreasonablystraightforward.Wewillfirstdescribeanalgorithmforefficientview-dependentrefinement.Usingthecommonvertexhierarchyin-ducedbyrecursiveedge/trianglebisection[2–4],weshowthatitispossibleto(1)constructanadaptivemeshfromscratcheachframe,(2)performfast,hierarchicalviewfrustumculling,(3)TheauthorsarewiththeLawrenceLivermoreNationalLaboratory,7000EastAvenue,L-560,Livermore,CA94551.E-mail:fpl,[e-mail]nthegeometryusinggeomorphing,while(4)simultaneouslyoutputtingasinglegeneralizedtrianglestripfortheentiremeshthatcanbeefficientlyrendered.More-over,allofthesetaskscanbeperformedwithouthavingtomain-tainanystateinformation,exceptofcoursefortheoutputbeinggenerated.Thatis,thetraversalcanbecastinapurelyfunctionalform,whichnotonlymakesefficientimplementationspossible,butisalsoafeaturethatmesheswellwiththeout-of-co