清华大学：《计算机图形学基础》课程教学资源（授课教案）网格参数化模型切割的骨架算法

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 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

– 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( 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

– 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

– 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

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 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

– 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

• 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