文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Terrain modeling using voronoi hierarchies
侵权投诉

Terrain modeling using voronoi hierarchies

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email