Efficient mesh deformation using tetrahedron control mesh

ABSTRACT

It is a challenging problem to interactively deform densely sampled complex objects. This paper proposed an easy but efficient approach to it by using coarse control meshes to embed the target objects. The control mesh can be efficiently deformed by various existing methods, and then the target object can be accordingly deformed by interpolation. One of the most simplest interpolation methods is to use the barycentric coordinates, which however generates apparent first-order discontinuity artifacts across the boundary due to its piecewise linear property. To avoid such artifacts, this paper introduced a modified barycentric interpolation (modified-BI) technique. The central idea is to add a local transformation at each control vertex for interpolation, so that we can minimize the first-order discontinuity by optimizing the local transformations. We also minimize the second order derivatives of the interpolation function to avoid undesired vibrations. While focus on deforming 3D objects embedded in tetrahedron meshes, the proposed method is applicable to 2D image objects embed in planar triangular meshes. The experimental results in both 2D and 3D demonstrated the success and advantages of the proposed method.

REFERENCES

• 1: Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105--114.
• 2: Alan H. Barr, Global and local deformations of solid primitives, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.21-30, January 1984
• 3: Thaddeus Beier , Shawn Neely, Feature-based image metamorphosis, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.35-42, July 1992
• 4: Mario Botsch , Leif Kobbelt, An intuitive framework for real-time freeform modeling, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 5: Botsch, M., and Kobbelt, L. 2005. Real-time shape editing using radial basis functions. Computer Graphics Forum 24, 3, 611--621.
• 6: Daniel Cohen-Or , Amira Solomovic , David Levin, Three-dimensional distance field metamorphosis, ACM Transactions on Graphics (TOG), v.17 n.2, p.116-141, April 1998 [doi>10.1145/274363.274366]
• 7: Sabine Coquillart, Extended free-form deformation: a sculpturing tool for 3D geometric modeling, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.187-196, September 1990, Dallas, TX, USA
• 8: Kevin G. Der , Robert W. Sumner , Jovan Popović, Inverse kinematics for reduced deformable models, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 9: Feng, J., Ma, L., and Peng, Q. 1996. A new free-form deformation through the control of parametric surfaces. Computers & Graphics 20, 4, 531--539.
• 10: Michael S. Floater, Mean value coordinates, Computer Aided Geometric Design, v.20 n.1, p.19-27, March 2003 [doi>10.1016/S0167-8396(02)00002-5]
• 11: William M. Hsu , John F. Hughes , Henry Kaufman, Direct manipulation of free-form deformations, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.177-184, July 1992
• 12: Jin Huang , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, An efficient large deformation method using domain decomposition, Computers and Graphics, v.30 n.6, p.927-935, December, 2006 [doi>10.1016/j.cag.2006.08.014]
• 13: Jin Huang , Xiaohan Shi , Xinguo Liu , Kun Zhou , Baining Guo , Hujun Bao, Geometrically based potential energy for simulating deformable objects, The Visual Computer: International Journal of Computer Graphics, v.22 n.9, p.740-748, September 2006 [doi>10.1007/s00371-006-0058-7]
• 14: Jin Huang , Xiaohan Shi , Xinguo Liu , Kun Zhou , Li-Yi Wei , Shang-Hua Teng , Hujun Bao , Baining Guo , Heung-Yeung Shum, Subspace gradient domain mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 15: Takeo Igarashi , Tomer Moscovich , John F. Hughes, As-rigid-as-possible shape manipulation, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 16: Pushkar Joshi , Mark Meyer , Tony DeRose , Brian Green , Tom Sanocki, Harmonic coordinates for character articulation, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 17: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 18: Youngihn Kho , Michael Garland, Sketching mesh deformations, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053452]
• 19: Yaron Lipman , Olga Sorkine , David Levin , Daniel Cohen-Or, Linear rotation-invariant coordinates for meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 20: Yaron Lipman , Johannes Kopf , Daniel Cohen-Or , David Levin, GPU-assisted positive mean value coordinates for mesh deformations, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 21: Ron MacCracken , Kenneth I. Joy, Free-form deformations with lattices of arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.181-188, August 1996 [doi>10.1145/237170.237247]
• 22: Tim Milliron , Robert J. Jensen , Ronen Barzel , Adam Finkelstein, A framework for geometric warps and deformations, ACM Transactions on Graphics (TOG), v.21 n.1, p.20-51, January 2002 [doi>10.1145/504789.504791]
• 23: Henry P. Moreton , Carlo H. Séquin, Functional optimization for fair surface design, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.167-176, July 1992
• 24: Matthias Müller , Markus Gross, Interactive virtual materials, Proceedings of Graphics Interface 2004, p.239-246, May 17-19, 2004, London, Ontario, Canada
• 25: Andrew Nealen , Olga Sorkine , Marc Alexa , Daniel Cohen-Or, A sketch-based interface for detail-preserving mesh editing, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 26: S. Schaefer , J. Hakenberg , J. Warren, Smooth subdivision of tetrahedral meshes, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057452]
• 27: Scott Schaefer , Travis McPhail , Joe Warren, Image deformation using moving least squares, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 28: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.151-160, August 1986
• 29: Xiaohan Shi , Kun Zhou , Yiying Tong , Mathieu Desbrun , Hujun Bao , Baining Guo, Mesh puppetry: cascading optimization of mesh deformation with inverse kinematics, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 30: Karan Singh , Eugene Fiume, Wires: a geometric deformation technique, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.405-414, July 1998 [doi>10.1145/280814.280946]
• 31: Olga Sorkine , Marc Alexa, As-rigid-as-possible surface modeling, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 32: O. Sorkine , D. Cohen-Or , Y. Lipman , M. Alexa , C. Rössl , H.-P. Seidel, Laplacian surface editing, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057456]
• 33: Robert W. Sumner , Jovan Popović, Deformation transfer for triangle meshes, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 34: Robert W. Sumner , Matthias Zwicker , Craig Gotsman , Jovan Popović, Mesh-based inverse kinematics, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 35: Weber, O., Sorkine, O., Lipman, Y, and Gotsman, C. 2007. Context-aware skeletal shape deformation. Computer Graphics Forum (Proceedings of Eurographics) 26, 3.
• 36: William Welch , Andrew Witkin, Variational surface modeling, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.157-166, July 1992
• 37: Dong Xu , Hongxin Zhang , Qing Wang , Hujun Bao, Poisson shape interpolation, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.267-274, June 13-15, 2005, Cambridge, Massachusetts [doi>10.1145/1060244.1060274]
• 38: Yoshizawa, S., Belyaev, A. G., and Seidel, H.-P. 2007. Skeleton-based variational mesh deformations. Computer Graphics Forum, 255--264.
• 39: Yizhou Yu , Kun Zhou , Dong Xu , Xiaohan Shi , Hujun Bao , Baining Guo , Heung-Yeung Shum, Mesh editing with poisson-based gradient field manipulation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 40: Zayer, R., Róssl, C., Karni, Z., and Seidel, H.-P. 2005. Harmonic guidance for surface deformation. Computer Graphics Forum, Proceedings of Eurographics 2005 24, 3, 601--609.
• 41: Kun Zhou , Jin Huang , John Snyder , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, Large mesh deformation using the volumetric graph Laplacian, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Keywords:
barycentric interpolation, mesh deformation, shape modeling