Designing and implementing a general purpose halfedge data structure

《Designing and implementing a general purpose halfedge data structure》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、DesigningandimplementingageneralpurposehalfedgedatastructureHervéBrönnimann
PolytechnicUniversity,BrooklynNY11201,USAhbr@photon.poly.edu1IntroductionHalfedgedatastructures(HDS)arefundamentalinrepresentingcombinatorialgeomet-ricstructures,usefulforrepresentinganyplanarstru

2、cturessuchasplanegraphsandpla-narmaps,polyhedralsurfacesandboundaryrepresentations(BREPs),two-dimensionalviewsofathreedimensionalscene,etc.Manyvariantshavebeenproposedinthelitera-ture,startingwiththewinged-edgedatastructureofBaumgart[2],theDCELof[15,9],thequad-edgedatastru

3、cture[11],thehalfedgedatastructure[18,12,andrefs.therein].Theyhavebeenproposedinvariousframeworks(referencestoomanytogivehere):–Planestructures:includingplanarmapsforGIS,2DBooleanmodeling,2Dgraph-ics,scientificcomputations,computervision.TherequirementsonHDSarethatthatsomee

4、dgesmaybeinfinite(e.g.,Voronoidiagrams),orborderedges(e.g.,forboundedpolygonaldomains),itmayincludeholesinthefacets(planarmaps),andthatifso,oneoftheconnectedboundarycycleisdistinguishedastheouterboundary(theothersareinnerholes).–Boundaryrepresentationofthree-dimensionalsoli

5、ds:includingBreprepresenta-tion,solidmodeling,polyhedralsurfaces,3Dgraphics.Therequirementsherevaryslightly:holesmaystillbeallowed,butthereisnoneedtodistinguishanouterboundary,infiniteedgesarenotalwaysusefulbutborderedgesmightneedtobeallowed.–Planarstructuresencounteredinhi

6、gherdimensionalstructures:eventhoughthedatastructureitselfmaybehigherdimensional,wemightwanttointerpretsometwo-dimensionalsubstructurebyusingaHDS.Examplesincludethepolygonalfacetsofa3Dmodel,orthelocalstructureinaneighborhoodofavertexina3Dsubdivision,orthetwo-dimensionalvie

7、wofathree-dimensionalscene.–Specialstructuressuchastriangulationsorsimplicialcomplexes:inthesestruc-tures,thestorageisfacet-based.Theyareusuallyeasiertoextendtohigherdimen-sions,andasystematicpresentationisgivenin[4].Alltheimplementationsweareawareof,includingthosesurveyed

8、above,captureasinglevariantofHDS,withthenotableexceptionofthedesignofhalfedgedatastruc-tu