三維物體在電腦的應用相當廣泛，而三角網格是用來表示三維物體常用的方法，其來源通常為3D scanners、商用軟體，或者經電腦視覺演算法由二維影像重構而來。但是三角上述方法所得之三角網格普遍存在二個問題：不規則（irregular）與不一致（non-uniform）。這二個問題導致三角網格有許多狹長三角形的存在，使三角網格的應用，如貼圖、變形等，其困難度增加。

　　流程一開始讓使用者將幾何模型作切割，切割的路徑會盡量經過物體的特徵，形成若干盤子狀（disk-like）的表面區域，之後透過有權重的質心范諾圖（Weighted Centroidal Voronoi Diagram）自動將每個表面區域細分為更多三角形表面區域，並將其各別攤平與重新三角化。此方法將三維物體重新網格化，去除狹長三角形，整個流程是接近自動化，而且低誤差的，並且能控制重新網格化後三維物體的三角形個數，可應用於多層解析度網格。

In computer graphics and geometric modeling, surfaces are often represented by triangular meshes. Somehow, the triangular meshes are often irregular and complicate processing such as numerical analysis, texturing, and storage.

We present a novel method to decompose an arbitrary 3D model, and then resample vertices in the model by low-distortion parameterization. There are two goals of this decomposition process: automatic and size-equally. We first need to cut a 2-manifold mesh into several disk-like patches. For each patch, we automatically partition it into more triangular patches. With the help of weighted centroidal Voronoi diagram (WCVD), these triangular patches are equally sized. Recursivelly subdividing these triangular patches, we finally get a regular model.

[1] A. Hausner. Simulating Decorative Mosaics. ACM SIGGRAPH ‘01, pages 573-580, 2001.
[2] A. Khodakovsky, N. Litke and P. Schröder. Globally Smooth Parameterizations with Low Distortion. ACM SIGGRAPH, 2003.
[3] A. W.F. Lee, D. Dobkin, W. Sweldens and P. Schröder. MAPS: Multiresolution Adaptive Parameterization of Surfaces. ACM SIGGRAPH ‘98, pages 95-104, 1998.
[4] C. L. Lawson. Software for C1 Surface Interpolation. Mathematical Software III (John R. Rice, editor), pages 161-194. Academic Press, New York, 1977.
[5] D. T. Lee and B. J. Schachter. Two Algorithms for Constructing a Delaunay Triangulation. International Journal of Computer and Information Sciences 9(3):219-242, 1980.
[6] E. Praun, A. Finkelstein and H. Hoppe. Lapped Textures. ACM SIGGRAPH ‘00, pages 465-470, 2000.
[7] E. Praun, W. Sweldens and P. Schröder. Consistent mesh parameterizations. ACM SIGGRAPH ‘01, pages 179-184, 2001.
[8] G. Turk. Re-Tiling Polygonal Surfaces. ACM SIGGRAPH ‘92, pages 55-64, 1992.
[9] H. Hoppe. Progressive Meshes. ACM SIGGRAPH 1996, pages 99-108, 1996.
[10] I. Guskov, K. Vidimče, W. Sweldens and P. Schröder. Normal Meshes. ACM SIGGRAPH ‘00, pages 95-102, 2000.
[11] I. Guskov, W. Sweldens and P. Schröder. Multiresolution Signal Processing for Meshes. ACM SIGGRAPH ‘99, pages 325-334, 1999.
[12] J. Goldfeather and V. Interrante. Understanding Errors in Approximating Principal Directions. ACM Transactions on Graphics, 2003.
[13] J. R. Shewchuk. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. First Workshop on Applied Computational Geometry (Philadelphia, Pennsylvania), pages 124-133, ACM, May 1996
[14] J. Vorsatz, C. Rossl, Leif P. Kobbelt and Hans-Peter Seidel. Feature Sensitive Remeshing. Proceedings of EUROGRAPHICS 2001.
[15] K. E. Hoff, T. Culver, J. Keyser, M. Lin and D. Manocha. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hadware. ACM SIGGRAPH ‘99, pages 277-286, 1999.
[16] M. Desbrun, M. Meyer and P. Alliez. Intrinsic Parameterizations of Surface Meshes. Proceedings of EUROGRAPHICS, 2002.
[17] M. Eck, T. DeRose and T. Duchamp, H. Hoppe, M. Lounsbery and W. Stuetzle. Multiresolution Analysis of Arbitrary Meshes. ACM SIGGRAPH ‘95, pages 173-182, 1995.
[18] M. Garland and P. Heckbert. Surface Simplification Using Quadric Error Metrics. ACM SIGGRAPH, 1997.
[19] M. Kass, A. Witkin, and D. Terzopoulos. Snakes: Active contour models, Int. J. Computer Vision, 1(4): 321-331, 1987.
[20] M. Lounsbery, T. DeRose and J. Warren. Multiresolution Analysis for Surfaces of Arbitrary Type. ACM TOG, 1997.
[21] P. Alliez and M. Desbrun. Progressive Encoding for Lossless Transmission of 3D Meshes. ACM SIGGRAPH, 2001.
[22] P. Alliez and M. Desbrun. Valence-Driven Connectivity Encoding for 3D Meshes. Proceedings of EUROGRAPHICS, 2001.
[23] P. Alliez, M. Meyer and M. Desbrun. Interactive Geometry Remeshing. ACM SIGGRAPH ‘02, pages 347-354, 2002.
[24] P. Cignoni, C. Rocchini and R. Scopigno. Metro: measuring error on simplified surfaces. Computer Graphics Forum, vol. 17(2), pp 167-174, June 1998.
[25] P. Sender, J. Snyder, S. Gortler and H. Hoppe. Texture Mapping Progressive Meshes. ACM SIGGRAPH ‘01, pages 409-416, 2001.
[26] R. Malladi, J. Sethian, and B. Vemuri. Shape modeling with front propagation: A level set approach, IEEE Trans. Pattern Anal. Machine Intell., vol. 17, pp. 158-175, 1995.
[27] S. Fortune. A Sweepline Algorithm for Voronoï Diagrams. Algorithmica 2(2):153-174, 1987.
[28] S. J. Gortler and M. Cohen. Hierarchical and Variational Geometric Modeling with Wavelets. Symposium on Interactive 3D Graphics 1995.
[29] S. Lloyd. Least Square Quantization in PCM. IEEE Transactions on Information Theory 28(1982): 129-137, 1982.
[30] S. Shlafman, A. Tal and S. Katz. Metamorphosis of Polyhedral Surfaces using Decomposition. Proceedings of EUROGRAPHICS, 2002.
[31] T. Kanai, H. Suzuki and F. Kimura. Three-Dimensional Geometric Metamorphosis Based on Harmonic Maps. The Visual Computer , pages 166-176, 1998.
[32] T. Kanai, H. Suzuki. Approximate Shortest Path on a Polyhedral Surface Based on Selective Refinement of the Discrete Graph and Its Applications. Proc. IEEE Geometric Modeling and Processing 2000 (Theory and Applications). Hong Kong April 10-12, pages 241-250, 2000.
[33] Tong-Yee Lee, Po-Hua Huang, Fast and Intuitive Metamorphosis of 3D Polyhedral Models Using SMCC Mesh Merging Scheme, IEEE Transactions on Visualization and Computer Graphics Vol. 9, No. 1, pages 85-98, Jan-March, 2003.
[34] V. Caselles, F. Catte, T. Coll, and F. Dibos. A geometric model for active contours, Numerische Mathematik, 66: 1-31, 1993.
[35] V. Qstromoukhov. A Simple and Efficient Error-Diffusion Algorithm. In Proceedings of SIGGRAPH ‘01, pages 567-572, 2001.
[36] X. Gu, S. J. Gortler and H. Hoppe. Geometry Images. ACM SIGGRAPH, pages 355-361, 2002.
[37] Y. Lee and S. Lee. Geometric Snakes for Triangular Meshes. Proceedings of EUROGRAPHICS, 2002.
[38] 林漢盈，三維多面體攤平技術與其應用，成功大學資訊工程研究所碩士論文，2001年7月。