基于微分坐标的网格morphing
|
摘要
随着计算机图形学和硬件技术的高速发展,计算机动画作为一种新兴的产业已经渗透到了人们生活的各个角落,如商业广告,电影特技、动画片、几何造型、工业设计等领域。作为计算机动画的主要手段,morphing属于变形的一种,它是指从一个物体(初始物体)到另一个物体(目标物体)的连续、光滑、自然的过渡。设计者们可以通过该技术产生新的中间物体“填满”两个给定的物体,并通过原有的几何形状融合出新的几何形状。随着需求的增长激发了大量的三维物体morphing的工作。这里的物体可以是数字图象、多边形、多面体、网格曲面、点云数据等。本文主要针对三维网格曲面morphing展开相关研究。一般情况下,网格曲面的morphing过程可以分为两个阶段：1.网格配准；2.形状插值。
本文对微分坐标的相关知识和三维网格morphing技术的发展进行了深入的研究、分类和总结。针对三维网格morphing中存在的问题并结合微分坐标的性质,本文提出了一套基于微分坐标系统三维网格的morphing算法。在网格配准阶段,我们首先对初始网格和目标网格做带约束的最小二乘网格,实质上是在最小二乘意义下通过修改网格顶点的微分坐标得出新的顶点位置,使其达到初始对齐；其次,最小化双向最近点距离；最后我们构造法向投影算子完成网格配准。在形状插值阶段,直接插值配准阶段求得的始末网格微分坐标,并补充在差值过程中丢失的微分信息,进而重建“关键帧”网格。
与传统的办法相比,配准阶段,该算法可以在任意亏格的同胚网格模型之间进行,并且对输入网格的点数没有过多的要求,直接利用起始网格的链接关系重构目标网格。不需要借助共同参数域,也不用先将网格进行分割再融合技术,避免了由此带来的很多问题。扩大了实用性,化简了算法的流程,提高了运算速度。在形状插值部分中,本文很好的利用在配准过程中已经计算好的微分坐标,有效的防止了形状插值的体积收缩,并且的到了较好的视觉效果。此外,本文提出的morphing技术还具有用户交互少的特点,在用户给定初始配准点对集之后,算法可以自动生成有效的morphing序列。
With the rapid development of computer graphics and the technology of hardware, as a new industry, computer animation has infiltrated into every corner of people's life, such as commercial advertisement, special effects in movie, cartoons, geometric modeling, industrial design etc. As the main means of computer animation, morphing, belongs to deformation technics, has been investigated in many contexts in recent years, is the gradual transformation of one object (the source) into another (the target). It gives the animator the ability to "fill" an animation between key-framed objects by inbetweening. It allows the designer to blend existing shapes in order to create new shapes. The growing demands stimulate a lot of related work on 3D-object morphing. Here, object can be an digital image, a polygon, a polyhedral, mesh or point cloud, etc. Nowadays the research priority has been given to 3D mesh morphing. In general case, mesh morphing consist of two phrases:1. Mesh correspondence; 2. Shape interpolation.
We study on differential coordinates related knowledge and the development of 3D morphing, and do some classification and conclusions. Based on differential coordinates this paper proposes an integrated 3D mesh morphing, due to the problems exist and the properties of differential coordinates. In correspondence phrase, first, we get least square meshes, with some constrains, from the start mesh and target mesh respectively. In itself, we get the new vertices' positions from the adjusted differential coordinates in least square sense, which produces a initial correspondence. Then the double sided distance is minimized. At last, a projective operator is designed to complete the correspondence. In shape interpolation phrase, we directly interpolate differential coordinates between the two meshes with the length adjustment, then we reconstruct the inbetween mesh from them.
Compared to traditional approaches, in the correspondence phrase, the algorithm proposed here can be applied to arbitrary manifold meshes no matter what the vertices numbers of input meshes. Our approach directly maps the connectivity of the source mesh onto the target mesh without needing to find the common parameter domain or first segment input meshes and then join them together, thus effectively enhances its utility, simplifies the process and raises the computation speed. In the second phrase, we take advantages of the differential coordinates which are computed through the corresponding process. An improved shape interpolation algorithm based on differential coordinates has been proposed in our work. It effectively avoids volume contraction during the shape interpolation process and produce a visual pleasing effect. In addition, our approach is with less user interactions. Users only have to define the initial correspondence set, then the morphing sequence will be produced by our algorithm
本文对微分坐标的相关知识和三维网格morphing技术的发展进行了深入的研究、分类和总结。针对三维网格morphing中存在的问题并结合微分坐标的性质,本文提出了一套基于微分坐标系统三维网格的morphing算法。在网格配准阶段,我们首先对初始网格和目标网格做带约束的最小二乘网格,实质上是在最小二乘意义下通过修改网格顶点的微分坐标得出新的顶点位置,使其达到初始对齐；其次,最小化双向最近点距离；最后我们构造法向投影算子完成网格配准。在形状插值阶段,直接插值配准阶段求得的始末网格微分坐标,并补充在差值过程中丢失的微分信息,进而重建“关键帧”网格。
与传统的办法相比,配准阶段,该算法可以在任意亏格的同胚网格模型之间进行,并且对输入网格的点数没有过多的要求,直接利用起始网格的链接关系重构目标网格。不需要借助共同参数域,也不用先将网格进行分割再融合技术,避免了由此带来的很多问题。扩大了实用性,化简了算法的流程,提高了运算速度。在形状插值部分中,本文很好的利用在配准过程中已经计算好的微分坐标,有效的防止了形状插值的体积收缩,并且的到了较好的视觉效果。此外,本文提出的morphing技术还具有用户交互少的特点,在用户给定初始配准点对集之后,算法可以自动生成有效的morphing序列。
With the rapid development of computer graphics and the technology of hardware, as a new industry, computer animation has infiltrated into every corner of people's life, such as commercial advertisement, special effects in movie, cartoons, geometric modeling, industrial design etc. As the main means of computer animation, morphing, belongs to deformation technics, has been investigated in many contexts in recent years, is the gradual transformation of one object (the source) into another (the target). It gives the animator the ability to "fill" an animation between key-framed objects by inbetweening. It allows the designer to blend existing shapes in order to create new shapes. The growing demands stimulate a lot of related work on 3D-object morphing. Here, object can be an digital image, a polygon, a polyhedral, mesh or point cloud, etc. Nowadays the research priority has been given to 3D mesh morphing. In general case, mesh morphing consist of two phrases:1. Mesh correspondence; 2. Shape interpolation.
We study on differential coordinates related knowledge and the development of 3D morphing, and do some classification and conclusions. Based on differential coordinates this paper proposes an integrated 3D mesh morphing, due to the problems exist and the properties of differential coordinates. In correspondence phrase, first, we get least square meshes, with some constrains, from the start mesh and target mesh respectively. In itself, we get the new vertices' positions from the adjusted differential coordinates in least square sense, which produces a initial correspondence. Then the double sided distance is minimized. At last, a projective operator is designed to complete the correspondence. In shape interpolation phrase, we directly interpolate differential coordinates between the two meshes with the length adjustment, then we reconstruct the inbetween mesh from them.
Compared to traditional approaches, in the correspondence phrase, the algorithm proposed here can be applied to arbitrary manifold meshes no matter what the vertices numbers of input meshes. Our approach directly maps the connectivity of the source mesh onto the target mesh without needing to find the common parameter domain or first segment input meshes and then join them together, thus effectively enhances its utility, simplifies the process and raises the computation speed. In the second phrase, we take advantages of the differential coordinates which are computed through the corresponding process. An improved shape interpolation algorithm based on differential coordinates has been proposed in our work. It effectively avoids volume contraction during the shape interpolation process and produce a visual pleasing effect. In addition, our approach is with less user interactions. Users only have to define the initial correspondence set, then the morphing sequence will be produced by our algorithm
引文
[1]Floater MS. Mean value coordinates[J]. Computer Aided Geometric Design,2003,20(1): 19-27.
[2]Praun E, Hoppe H. Spherical parametrization and remeshing[J]. ACM Transactions on Graphics (TOG),2003,22(3):340-349.
[3]Shlafman S, Tal A, Katz S. Metamorphosis of polyhedral surfaces using decomposition[J]. Computer Graphics Forum,2002,21 (3):219-228.
[4]Kraevoy V, Sheffer A. Cross-parameterization and compatible remeshing of 3D models[J]. ACM Transactions on Graphics,2004,23(3),861-869.
[5]Zhang L, Liu L, Ji Z, et al. Manifold parameterization[C]. Hangzhou, China:Computer Graphics International,2006,160-171.
[6]Wu H, Pan C,Yang Q,et al. Consistent Correspondence between Arbitrary Manifold Surfaces[C]. Rio de Janeiro, Brazil:International Conference on Computer Vision, 2007,1-8.
[7]Gregory A, State A, Lin M, et al. Feature-based sur-face decomposition for correspondence and morphing between polyhedra[C]. Philadelphia, USA:Computer Animation'98,1998.
[8]Kanai T, Suzuki H, Kimura F. Metamorphosis of arbitrary triangular meshes[C]. IEEE Computer Graphics & Applications,20(2):62-75.
[9]Zockler M, Stalling D, Hege HC. Fast and intuitive generation of geometric shape transitions[J]. The Visual Computer,2000:16(5):241-253.
[10]Cohen-Or D, Camrel E. Warp-guided objeet-space moprhing[J]. The Visual Computer,1998,13(9-10):465-478.
[11]Cohen-Or D, Solomovici A, Levin D. Threedimensional distance field metamorphosis [J]. ACM Transactions on Graphics,17(2):116-141, April 1998.
[12]Alexa M. Differential coordinates for local mesh morphing and deformation[J]. The Visual Computer 2003; 19(2):105-114.
[13]Sorkine 0, Cohen-Or D. Least-Squares Meshes[C]. Genova, Italy:Shape Modeling International,2004,191-199.
[14]Tutte W. How to draw a graph[C]. In:Proceedings of London Mathematical Society,1963.
[15]DO CARMO M. P.:Differential Geometry of Curves and Surfaces[M]. Prentice-Hall, 1976.
[16]Meyer M, Desbin M., Schroder P, et al. Discrete differential-geometry operators for triangulated 2-manifolds[C]. In Visualization and Mathematics III, Hege H.-C. Polthier K., (Eds.). Springer-Verlag, Heidelberg,2003.
[17]Su Z., Wang H., Cao J. Mesh denoising based on differential coordinates[C]. In:Proc. of International Conference on Shape Modeling and Applications 2009, pp.1-6 (2009)
[18]Sorkine 0. Differential Representations for Mesh Processing[J]. Computer Graphics Forum,206,25 (4):789-807
[19]Lipman Y, Sorkine 0, Cohen-Or D, et al. Differential coordinates for interactive mesh editin[C]g, in:Proceedings of Shape Modeling International, IEEE Computer Society, 2004
[20]Sorkine 0, Lipman Y, Cohen-Or D, et al. Laplacian surface editing[C]. In:Symposium on Geometry Processing, ACM,2004
[21]Yu Y, Zhou K, Xu D, et al.Mesh editing with poisson-based gradient field manipulation[J], ACM Transactions on Graphics 23 (3) (2004) 644-651.
[22]Sorkine 0, Alexa M, As-rigid-as-possible surface modeling[C]. In:Proceedings of Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, ACM.2007.
[23]Fu H, Au 0, Tai C, Effective derivation of similarity transformations for implicit laplacian mesh editing[J]. Computer Graphics Forum 26 (1) (2007) 34-45.
[24]Wang H, Chen H, Su Z, et al. Versatile surface detail editing via Laplacian Coordinates,2010
[25]Vallet B, LevyB. Spectral geometry processing with manifold harmonics [J]. Computer Graphics Forum 2008,27(2):51-260
[26]Au 0, Tai C, Liu L, et al. Mesh editing with curvature flow laplacian operator[R]. Tech. Rep. HKUST-CS05-10, Computer Science Technical Report,2005.
[27]Sumner RW, Popovic J. Deformation transfer for triangle meshes[J]. ACM Transactions on Graphics,2004,23(3),399-405.
[28]Dinh HQ, Yezzi A, Turk G. Texture Transfer During Shape Transformation[J]. ACM Transactions on Graphics,2005 24(2):289-310.
[29]Kent J, Parent R, Carlson W. Establishing correspondences by topological merging: A new approach to 3-d shape transformation[C]. Graphics Interface,1991.
[30]Kent J, Carlson W, Parent R. Shape transformation for polyhedralobjects [J]. Computer Graphics,1992,26(2):47-54
[31]Haker S, Angenent S, Tannenbaum S, et al. Conformal surface parametrization for texture mapping[C]. IEEE TVCG,2000,6(2):181-189.
[32]Praun E, Hoppe H. Spherical parameterization and remeshing[C]. In:Proceedings of SIGGRAPH,2003.
[33]Gotsman C, Gu X, Sheffer A. Fundamentals of spherical parameterization for 3d meshes[C]. In:Proceedings of SIGGRAPH,2003.
[34]Sheffer A, Gotsman C, Dyn N. Robust spherical parameterization of triangular meshes[C].4th Israel-Korea Bi-National Conf. on Geometric Modeling and Computer Graphics,2003.
[35]Saba S, Yavneh I, Gotsman C.et al. Practical Spherical Embedding of Manifold Triangle Meshes[C]. Proceedings of Shape Modeling International.,2005.
[36]Lee A, Dobkin D, Sweldens W, et al. Multiresolution mesh morphing[C]. Proceedings of SIGGRAPH 99, Los Angeles:California,1999.
[37]Zhang H, Sheffer A, Cohen-Or D. et al. Deformation-driven shape correspondence[J]. Comput. Graph. Forum,2008,27 (5):1431-1439
[38]Cohen-Or D, Solomoviei A, Levin D. Three dimensional distance field metamorphosis[J]. ACM Transactions on Graphics,1998,17(2):116-141.
[39]Floater MS, Gotsman C. How to moprh tilings injeetively[J]. Journal of Computational and Applied Mathematies,1999,101:117-129.
[40]Surazhsky V, Gotsman C. Controllable morphing of compatible Planar triangulations[J]. ACM. Transactions on Graphics,2001,20(4):203-231.
[41]Francis L, Anne V. Three-dimensional metamor-phosis:a survey[J]. The Visual Computer,1998,14(8/9):373-389.
[42]Alexa M. Recent advances in mesh morphing[J]. Computer Graphics Forum, 2002,21 (2):173-196
[43]Taubin G. A Signal Processing Approach to Fair Surface Design[C]. Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995
[44]Guskov I, Sweldens W, Schroder P. Multiresolution signal processing for meshes[C]. In SIGGRAPH'99:Proceedings of the 26th annual conference on Computer graphics and interactive techniques, pages 325-334, New York, NY, USA,1999.
[45]Meyer M, Desbrun M, Schroder P, et al. Discrete Differential Geometry Operators for Triangulated 2-Manifolds. In VisMath'02 Proceedings,2002.
[46]Desbrun M, Meyer M, Schroder P, et al. Implicit fairing of irregular meshes using diffusion and curvature flow. In SIGGRAPH'99:Proceedings of the 26th annual conference on Computer graphics and interactive techniques, pages 317-324, New York, NY, USA,1999. ACM Press/Addison-Wesley Publishing Co.
[47]李治隆,苏志勋,王辉,毕海川.基于曲面基本型特征的网格平滑和增强.计算机工程,36(20)：13-15
[2]Praun E, Hoppe H. Spherical parametrization and remeshing[J]. ACM Transactions on Graphics (TOG),2003,22(3):340-349.
[3]Shlafman S, Tal A, Katz S. Metamorphosis of polyhedral surfaces using decomposition[J]. Computer Graphics Forum,2002,21 (3):219-228.
[4]Kraevoy V, Sheffer A. Cross-parameterization and compatible remeshing of 3D models[J]. ACM Transactions on Graphics,2004,23(3),861-869.
[5]Zhang L, Liu L, Ji Z, et al. Manifold parameterization[C]. Hangzhou, China:Computer Graphics International,2006,160-171.
[6]Wu H, Pan C,Yang Q,et al. Consistent Correspondence between Arbitrary Manifold Surfaces[C]. Rio de Janeiro, Brazil:International Conference on Computer Vision, 2007,1-8.
[7]Gregory A, State A, Lin M, et al. Feature-based sur-face decomposition for correspondence and morphing between polyhedra[C]. Philadelphia, USA:Computer Animation'98,1998.
[8]Kanai T, Suzuki H, Kimura F. Metamorphosis of arbitrary triangular meshes[C]. IEEE Computer Graphics & Applications,20(2):62-75.
[9]Zockler M, Stalling D, Hege HC. Fast and intuitive generation of geometric shape transitions[J]. The Visual Computer,2000:16(5):241-253.
[10]Cohen-Or D, Camrel E. Warp-guided objeet-space moprhing[J]. The Visual Computer,1998,13(9-10):465-478.
[11]Cohen-Or D, Solomovici A, Levin D. Threedimensional distance field metamorphosis [J]. ACM Transactions on Graphics,17(2):116-141, April 1998.
[12]Alexa M. Differential coordinates for local mesh morphing and deformation[J]. The Visual Computer 2003; 19(2):105-114.
[13]Sorkine 0, Cohen-Or D. Least-Squares Meshes[C]. Genova, Italy:Shape Modeling International,2004,191-199.
[14]Tutte W. How to draw a graph[C]. In:Proceedings of London Mathematical Society,1963.
[15]DO CARMO M. P.:Differential Geometry of Curves and Surfaces[M]. Prentice-Hall, 1976.
[16]Meyer M, Desbin M., Schroder P, et al. Discrete differential-geometry operators for triangulated 2-manifolds[C]. In Visualization and Mathematics III, Hege H.-C. Polthier K., (Eds.). Springer-Verlag, Heidelberg,2003.
[17]Su Z., Wang H., Cao J. Mesh denoising based on differential coordinates[C]. In:Proc. of International Conference on Shape Modeling and Applications 2009, pp.1-6 (2009)
[18]Sorkine 0. Differential Representations for Mesh Processing[J]. Computer Graphics Forum,206,25 (4):789-807
[19]Lipman Y, Sorkine 0, Cohen-Or D, et al. Differential coordinates for interactive mesh editin[C]g, in:Proceedings of Shape Modeling International, IEEE Computer Society, 2004
[20]Sorkine 0, Lipman Y, Cohen-Or D, et al. Laplacian surface editing[C]. In:Symposium on Geometry Processing, ACM,2004
[21]Yu Y, Zhou K, Xu D, et al.Mesh editing with poisson-based gradient field manipulation[J], ACM Transactions on Graphics 23 (3) (2004) 644-651.
[22]Sorkine 0, Alexa M, As-rigid-as-possible surface modeling[C]. In:Proceedings of Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, ACM.2007.
[23]Fu H, Au 0, Tai C, Effective derivation of similarity transformations for implicit laplacian mesh editing[J]. Computer Graphics Forum 26 (1) (2007) 34-45.
[24]Wang H, Chen H, Su Z, et al. Versatile surface detail editing via Laplacian Coordinates,2010
[25]Vallet B, LevyB. Spectral geometry processing with manifold harmonics [J]. Computer Graphics Forum 2008,27(2):51-260
[26]Au 0, Tai C, Liu L, et al. Mesh editing with curvature flow laplacian operator[R]. Tech. Rep. HKUST-CS05-10, Computer Science Technical Report,2005.
[27]Sumner RW, Popovic J. Deformation transfer for triangle meshes[J]. ACM Transactions on Graphics,2004,23(3),399-405.
[28]Dinh HQ, Yezzi A, Turk G. Texture Transfer During Shape Transformation[J]. ACM Transactions on Graphics,2005 24(2):289-310.
[29]Kent J, Parent R, Carlson W. Establishing correspondences by topological merging: A new approach to 3-d shape transformation[C]. Graphics Interface,1991.
[30]Kent J, Carlson W, Parent R. Shape transformation for polyhedralobjects [J]. Computer Graphics,1992,26(2):47-54
[31]Haker S, Angenent S, Tannenbaum S, et al. Conformal surface parametrization for texture mapping[C]. IEEE TVCG,2000,6(2):181-189.
[32]Praun E, Hoppe H. Spherical parameterization and remeshing[C]. In:Proceedings of SIGGRAPH,2003.
[33]Gotsman C, Gu X, Sheffer A. Fundamentals of spherical parameterization for 3d meshes[C]. In:Proceedings of SIGGRAPH,2003.
[34]Sheffer A, Gotsman C, Dyn N. Robust spherical parameterization of triangular meshes[C].4th Israel-Korea Bi-National Conf. on Geometric Modeling and Computer Graphics,2003.
[35]Saba S, Yavneh I, Gotsman C.et al. Practical Spherical Embedding of Manifold Triangle Meshes[C]. Proceedings of Shape Modeling International.,2005.
[36]Lee A, Dobkin D, Sweldens W, et al. Multiresolution mesh morphing[C]. Proceedings of SIGGRAPH 99, Los Angeles:California,1999.
[37]Zhang H, Sheffer A, Cohen-Or D. et al. Deformation-driven shape correspondence[J]. Comput. Graph. Forum,2008,27 (5):1431-1439
[38]Cohen-Or D, Solomoviei A, Levin D. Three dimensional distance field metamorphosis[J]. ACM Transactions on Graphics,1998,17(2):116-141.
[39]Floater MS, Gotsman C. How to moprh tilings injeetively[J]. Journal of Computational and Applied Mathematies,1999,101:117-129.
[40]Surazhsky V, Gotsman C. Controllable morphing of compatible Planar triangulations[J]. ACM. Transactions on Graphics,2001,20(4):203-231.
[41]Francis L, Anne V. Three-dimensional metamor-phosis:a survey[J]. The Visual Computer,1998,14(8/9):373-389.
[42]Alexa M. Recent advances in mesh morphing[J]. Computer Graphics Forum, 2002,21 (2):173-196
[43]Taubin G. A Signal Processing Approach to Fair Surface Design[C]. Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995
[44]Guskov I, Sweldens W, Schroder P. Multiresolution signal processing for meshes[C]. In SIGGRAPH'99:Proceedings of the 26th annual conference on Computer graphics and interactive techniques, pages 325-334, New York, NY, USA,1999.
[45]Meyer M, Desbrun M, Schroder P, et al. Discrete Differential Geometry Operators for Triangulated 2-Manifolds. In VisMath'02 Proceedings,2002.
[46]Desbrun M, Meyer M, Schroder P, et al. Implicit fairing of irregular meshes using diffusion and curvature flow. In SIGGRAPH'99:Proceedings of the 26th annual conference on Computer graphics and interactive techniques, pages 317-324, New York, NY, USA,1999. ACM Press/Addison-Wesley Publishing Co.
[47]李治隆,苏志勋,王辉,毕海川.基于曲面基本型特征的网格平滑和增强.计算机工程,36(20)：13-15