多边形网格

3DModelingPolygonMeshesShandongUniversity3DObjectRepresentations•Rawdata–Pointcloud–Rangeimage–Polygonsoup•Surfaces–Mesh–Subdivision–Parametric–Implicit•Solids–Voxels–BSPtree–CSG–Sweep•High-levelstructures–Scenegraph–Skeleton–ApplicationspecificPolygonMeshRepresentation•Datastructuresdeterminealgorithms–Datastructuremustsupportkeyoperationsofalgorithmefficiently•Examples:–Drawingamesh–Removingavertex–Smoothingaregion–Intersectingpolyhedra•DifferentdatastructuresfordifferentalgorithmsPolygonMeshRepresentation•Possibledatastructures–Listofindependentfaces–Vertexandfacetables–Adjacencylists–Wingededge–Halfedge–etc.IndependentFaces•Eachfacelistsvertexcoordinates–Redundantvertices–NoadjacencyinformationVertexandFaceTables•Eachfacelistsvertexreferences–Sharedvertices–StillnoadjacencyinformationAdjacencyLists•Storeallvertex,edge,andfaceadjacencies–Efficientadjacencytraversal–ExtrastoragePartialAdjacencyLists•Canwestoreonlysomeadjacencyrelationshipsandderiveothers?WingedEdge•Adjacencyencodedinedges–AlladjacenciesinO(1)time–Littleextrastorage(fixedrecords)–ArbitrarypolygonsWingedEdge•Edgepointers–totwoendpointvertices–totwofacesthatshareedge–tofouredgesemanatingfromitsendpoints•Faces,verticescontainpointertooneedge•Facesoutlinesbywalkingedges•MeshinformationisfullydescribedbythisdatastructureF1F2V1V21e1e2e2eeWingedEdgeExample:e1e2e3e4e5e6e7HalfEdge•Adjacencyencodedinedges–AlladjacenciesinO(1)time–Littleextrastorage(fixedrecords)–Arbitrarypolygons•Similartowinged-edge,exceptadjacencyencodedinhalf-edges•Eachedgeisdecomposedintotwohalf-edgeswithoppositeorientations.HalfEdge•Ineachhalfedge:–Incidentvertex–Incidentface–Nexthalfedge–Oppositehalfedge–Previoushalfedge(Optional)HalfEdge•Operationssupported–Walkaroundtheboundaryofagivenface–Visitalledgesincidenttoavertexv•Example–Enumerateallverticesthatareadjacenttoagivenvertex–thisiscalledtheone-ringofavertex•Popular––•Example–EnumerateallverticesthatareadjacenttoagivenvertexvHalfEdgeh=outgoing_halfedge(v)HalfEdgehstop=h;DoVertexw=h-opposite()-origine//DOSIMETHINGWITHVERTEXwh=h-opposite()-next_halfEgde();While(h!=hstop)Summary•Polygonmeshes–Mostcommonsurfacerepresentation–Fastrendering•Processingoperations–Mustconsiderirregularvertexsampling–Musthandle/avoidtopologicaldegeneracies•Representation–Whichadjacencyrelationshipstostoredependonwhichoperationsmustbeefficient