廣号Skeleton-Based SeamComputationforTriangulated Surface ParameterizationShi-MinHuTsinghua University,Beijing2009.3.30Tsinghua University
Sk l t e e on-B d S C t ti Based Seam Computation for Triangulated Surface Parameterization Shi-Min Hu T i h U i it B iji Tsinghua University, Beijing Tsinghua University 2009.3.30
廣窖1.Parametrization and seam computingTriangle meshes and parameterization(参数化)-Due to flexibility and efficiency,triangle mesheshavebeen widely used inthe entertainmentindustry to represent arbitrary surfaces for 3Dgames and movies during the last few years.Manynewmeshtechnigueshavebeendevelopedfor different applications. In these techniquesparameterization is akeyissue-Parameterizationprovidesmappingbetweenmeshesandadomain2009.3.30Tsinghua University
1 Parametrization and seam computing 1. Parametrization and seam computing • Triangle meshes and parameterization(参数化) – Due to flexibility and efficiency triangle meshes Due to flexibility and efficiency, triangle meshes have been widely used in the entertainment industry to represent arbitrary surfaces for 3D industry to represent arbitrary surfaces for 3D games and movies during the last few years. – Many new mesh techniques have been developed Many new mesh techniques have been developed for different applications. In these techniques, parameterization is a key issue. parameterization is a key issue. – Parameterization provides mapping between meshes and a domain Tsinghua University 2009. 3.30 meshes and a domain
廣窖Parameterizationmethodscanbegroupedintothreecategories(类别),dependingonwhetherthedomainisapolyhedron(多面体），sphereorplanePlanarBase-meshSpherical2009.3.30TsinghuaUniversity
– Parameterization methods can be grouped into three cate g ( ories (类别), p g de pendin g on whether the domain is a polyhedron(多面体), sphere or plane. Base -mesh Spherical Planar Tsinghua University 2009. 3.30 Base mesh Spherical Planar
廣窖Seam(缝)computing- Our goal is to map an arbitrary topology(拓扑)surface mesh to a single chart with lowdistortion(扭曲).Theoretically,any closed surfacecan be opened into a topological disc(圆盘)using aset of cut edges making up a “seam". Cutting alongthe seam, we can get a disc-like patch2009.3.30Tsinghua University
• Seam(缝) computing – Our goal is to map an arbitrary topology( Our goal is to map an arbitrary topology(拓扑) surface mesh to a single chart with low distortion(扭曲) Theoretically any closed surface ). Theoretically, any closed surface can be opened into a topological disc(圆盘) using a set o cut edges a g up a sea . Cutt g a o g of cut edges making up a “seam”. Cutting along the seam, we can get a disc-like patch. Tsinghua University 2009. 3.30
廣琴-Unlessthesurfaceisdevelopable,parameterizationusingasinglechartinevitably（不可避免的）createsdistortion(扭曲),which isespeciallygreatwhereprotrusions(突出物)ofthe surfaceareflattenedinto the plane. (such as fingers of a hand andhorses'legs)2009.3.30Tsinghua University
– Unless the surface is developable, parameterization using a single chart inevitably( using a single chart inevitably(不可避免的) creates ) creates distortion(扭曲), which is especially great where p ( rotrusions (突出物 ) of the surface are flattened into the plane. (such as fingers of a hand and horses' legs) Tsinghua University 2009. 3.30
廣季-Itsfoundthattoreducethedistortion,itisimportantfortheseamtopassthroughthevariousso-called“extrema"（极值点）- Although extrema can be foundaccurately,itis stilldifficulttoguidetheseamthroughtheseextrema2009.3.30Tsinghua University
– It’s found that to reduce the distortion, it is important for the seam to p g ass throu gh the various so-called “extrema”(极值点). – Althou gh extrema can be found accurately, it is still difficult to guide the seam through these extrema. the seam through these extrema. Tsinghua University 2009. 3.30
廣号Theobjective(目标)is to consider seam computation with givenextremalvertices(wecalledextrema(极值点）2009.3.30Tsinghua University
The objective(目标), is to consider seam computation with given is to consider seam computation with given extremal vertices (we called extrema(极值点)). Tsinghua University 2009. 3.30
廣琴2. Related WorkTo seek a good seam, we should follow twostrategies(策略）The seam should pass through all extremal verticesThe seam'slength shouldbeminimum(最小）2009.3.30Tsinghua University
2 Related Work 2. Related Work • To seek a good seam, we should follow two strategies(策略): – The seam should pass through all The seam should pass through all extremal vertices extremal vertices. – The seam’s length should be minimum( The seam’s length should be minimum(最小). Tsinghua University 2009. 3.30
廣翠-Forgivenextremalvertices,Tofindaminimumlengthseamconnecting all extremal vertices comesdowntothe Steiner Tree problem in Graph Theory. For a givenweighted graph,it's aNP-completeproblem-Twomain approximated algorithm for it are Minimumspanning tree (MST)method and GreedyalgorithmShefferandGuusethosetwomethodsforseamcomputingrespectively2009.3.30Tsinghua University
– For given extremal vertices, To find a minimum length seam connecting all extremal vertices comes down to seam connecting all extremal vertices comes down to the Steiner Tree problem in Graph Theory. For a given weighted graph, it weighted graph, it s’ a NP -complete problem. complete problem. – Two main approximated algorithm for it are Minimum spanning tree (MST) method and Greedy algorithm spanning tree (MST) method and Greedy algorithm. Sheffer and Gu use those two methods for seam computing respectively computing respectively. Tsinghua University 2009. 3.30
廣翠Guetal.“GeometryImage（几何图像）-Guetal.firstfindaninitial cutthatopensmeshM intoa disk.-Extremawasfoundbyutilizingtheshape-preservingfeatureofFloater'sparameterizationwhenanewextremalvertexisdetected,the shortestpathbetween the current seam and the new extremalvertex is added to the seam2009.3.30Tsinghua University
• Gu etal. “Geometry Image” (几何图像 ) – Gu et al first find an initial cut that opens mesh Gu et al. first find an initial cut that opens mesh M into a disk. – Extrema was found by utilizing the shape Extrema was found by utilizing the shape -preserving preserving feature of Floater's parameterization. – when a new extremal vertex is detected, the shortest path between the current seam and the new extremal vertex is added to the seam. Tsinghua University 2009. 3.30