Abstract. We present a new algorithm for terrain modeling based on Voronoi diagrams and Sibson’s interpolant. Starting with a set of scattered data sites in the plane with associated function values defining a height field, our algorithm constructs a top-
TerrainModelingusingVoronoiHierarchies
MartinBertram
BerndHamann
KenJoy
ShirleyKonkle
Abstract.WepresentanewalgorithmforterrainmodelingbasedonVoronoidiagramsandSibson’sinterpolant.Startingwithasetofscattereddatasitesintheplanewithassociatedfunctionvaluesde ningaheight eld,ouralgorithmconstructsatop-downhierarchyofsmoothapproximations.Weusetheconvexhullofgivensitesasdomainforourhierarchicalrepresentation.Sibson’sinterpolantisusedtoapproximatetheunderlyingheight eldbasedonassociatedfunctionvaluesofselectedsubsetsofthedatasites.Therefore,ouralgorithmconstructsahierarchyofVoronoidia-gramsfornestedsubsetsofthegivensites.Thequalityofapprox-imationsobtainedwithourmethodcomparesfavorablytoresultsobtainedfromothermultiresolutionalgorithmslikewavelettrans-forms.OurApproximationsforeverylevelofresolutionare
-continuous,exceptattheselectedsites,whereonly
-continuityissatis ed.Theexpectedtimecomplexityofouralgorithmis
forsiteswhenapplyingsimpleaccelerationmethods.
Inadditiontoahierarchyofsmoothapproximations,ourmethodprovidesaclusterhierarchybasedonconvexcellsandanimpor-tancerankingforsites.
1Introduction
Clusteringtechniques[7]generateadata-dependentpartitioningofspacerepresentinginherenttopologicalandgeometricstructuresofscattereddata.Adaptiveclusteringmethodsrecursivelyre nethispartitioningresultinginamultiresolutionrepresentationthatisre-quiredforapplicationslikeprogressivetransmission,compression,view-dependentrendering,andtopologyreconstruction.Forex-ample,topologicalstructuresoftwo-manifoldsurfacescanbere-constructedfromscatteredpointsinthree-dimensionalspaceusingadaptiveclusteringmethods[6].Incontrasttomesh-simpli cationalgorithms,adaptiveclusteringmethodsdonotrequireagridstruc-tureconnectingthegivendatapoints.Aclusterhierarchyisbuiltina“top-down”approach,sothatcoarselevelsofresolutionrequirelesscomputationtimesthan nerlevels.
Inthispaper,wepresentaVoronoi-basedadaptiveclusteringmethodforterrainmodeling.Arbitrarysamplestakenfromlarge-scaleterrainmodelsarerecursivelyselectedaccordingtotheirrel-evance.Continuousapproximationsoftheterrainmodelarecon-structedbasedontheindividualsetsofselectedsitesusingSib-son’sinterpolant[10].WehaveimplementedthisalgorithmusingaDelaunaytriangulation,i.e.,thedualofaVoronoidiagram,asunderlyingdatastructure.ConstructingaDelaunaytriangulationrequireslessimplementationthanconstructingthecorrespondingVoronoidiagram,sincealotofspecialcases(thesewhereVoronoiverticeshaveavalencegreaterthanthree)canbeignored.Ama-jordrawbackofDelaunaytriangulationsisthattheyarenotunique,ingeneral.Thisbecomesevidentwhentheselectedsitesaresam-pledfromregular,rectilineargridssuchthatthediagonalforeveryquadrilateralcanbe ipped,resultinginrandomchoicesaffectingtheapproximation.ThecorrespondingVoronoidiagram,however,isuniquelyde nedandcaninstantlybederivedfromaDelaunaytriangulation.Sibson’sinterpolantisalsoef cientlycomputedfrom
HansHagen
erent from terrains, so these methods for building hierarchies cannot be ...closest (the immediate representatives) using the already-determined Voronoi ...
modeling of radio frequency energy propagation in the presence of terrain and...tion, etc. Multi-resolution triangulation hierarchies ?, ?] have been ...
modeling of radio frequency energy propagation in the presence of terrain and...tion, etc. Multi-resolution triangulation hierarchies ?, ?] have been ...
热门文档