Fitting solid meshes to animated surfaces using linear elasticity

ABSTRACT

Computing correspondence between time frames of a time-dependent 3D surface is essential for the understanding of its motion and deformation. In particular, it can be a useful tool in compression, editing, texturing, or analysis of the physical or structural properties of deforming objects. However, correspondence information is not trivial to obtain for experimentally acquired 3D animations, such as time-dependent visual hulls (typically represented as either a binary occupancy grid or as a sequence of meshes of varying connectivity).

In this article we present a new nonrigid fitting method that can compute such correspondence information for objects that do not undergo large volume or topological changes, such as living creatures. Experimental results show that it is robust enough to handle visual hull data, allowing to convert it into a constant connectivity mesh with vertices moving in time. Our procedure first creates a rest-state mesh from one of the input frames. This rest-state mesh is then fitted to the consecutive frames. We do this by iteratively displacing its vertices so that a combination of surface distance and elastic potential energy is minimized. A novel rotation compensation method enables us to obtain high-quality results with linear elasticity, even in presence of significant bending.

REFERENCES

• 1: Marc Alexa , Daniel Cohen-Or , David Levin, As-rigid-as-possible shape interpolation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.157-164, July 2000 [doi>10.1145/344779.344859]
• 2: Brostow, G. J., Essa, I., Steedly, D., and Kwatra, V. 2004. Novel skeletal representation for articulated creatures. In ECCV04. Vol III: 66--78.
• 3: Jaeil Choi , Andrzej Szymczak , Greg Turk , Irfan Essa, Element-Free Elastic Models for Volume Fitting and Capture, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.2245-2252, June 17-22, 2006 [doi>10.1109/CVPR.2006.110]
• 4: B. Cutler , J. Dorsey , L. McMillan, Simplification and improvement of tetrahedral models for simulation, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057445]
• 5: Edelsbrunner, H. and Guoy, D. 2002. An experimental study of sliver exudation. Eng. Comput. SI Mesh Generation (10th IMR 2001) 18, 3, 229--240.
• 6: Löhner, R. 1988. Generation of three-dimensional unstructured grids by the advancing front algorithm. Int. J. Numer. Methods Fluids 8, 1135--1149.
• 7: Wojciech Matusik , Chris Buehler , Ramesh Raskar , Steven J. Gortler , Leonard McMillan, Image-based visual hulls, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.369-374, July 2000 [doi>10.1145/344779.344951]
• 8: McInerney, T. and Terzopoulos, D. 1993. A finite element model for 3D shape reconstruction and nonrigid motion tracking. In Proceedings of the IEEE International Conference on Computer Vision (ICCV). 518--523.
• 9: Molino, N., Bridson, R., Teran, J., and Fedkiw, R. 2003. A crystalline, red green strategy for meshing highly deformable objects with tetrahedra. In Proceedings of the 12th International Meshing Roundtable Conference, 103--114.
• 10: Matthias Müller , Julie Dorsey , Leonard McMillan , Robert Jagnow , Barbara Cutler, Stable real-time deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545269]
• 11: Gregory M. Nielson , Junwon Sung, Interval volume tetrahedrization, Proceedings of the 8th conference on Visualization '97, p.221-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 12: Alex Petland , Bradley Horowitz, Recovery of Nonrigid Motion and Structure, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.7, p.730-742, July 1991 [doi>10.1109/34.85661]
• 13: Rassineux, A. 1998. Generation and optimization of tetrahedral meshes by advancing front technique. Int. J. Numer. Methods Eng. 41, 651--674.
• 14: Peter Sand , Leonard McMillan , Jovan Popović, Continuous capture of skin deformation, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 15: Sethian, J. A. 1996. A fast marching level set method for monotonically advancing fronts. Appl. Math. 93, 4, 1591--1595.
• 16: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 17: Shöberl, J. 1997. Netgen - An advancing front 2D/3D mesh generator based on abstact rules. Comput. Visualiz. Sci. 1, 1, 41--52.
• 18: J. Starck , Adrian Hilton , John Illingworth, Reconstruction of Animated Models from Images Using Constrained Deformable Surfaces, Proceedings of the 10th International Conference on Discrete Geometry for Computer Imagery, p.382-391, April 03-05, 2002
• 19: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• 20: Demetri Terzopoulos , Andrew Witkin, Physically Based Models with Rigid and Deformable Components, IEEE Computer Graphics and Applications, v.8 n.6, p.41-51, November 1988 [doi>10.1109/38.20317]
• 21: Demetri Terzopoulos , Andrew Witkin , Michael Kass, Constraints on deformable models: recovering 3D shape and nongrid motion, Artificial Intelligence, v.36 n.1, p.91-123, August 1988 [doi>10.1016/0004-3702(88)90080-X]
• 22: Yerry, M. A. and Shephard, M. S. 1984. Automatic three-dimensional mesh generation by the modified octree technique. Int. J. Numer. Methods Eng. 20, 1965--1990.
• 23: 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
• 24: Yan Zhuang , John Canny, Real-time and physically realistic simulation of global deformation, ACM SIGGRAPH 99 Conference abstracts and applications, p.270, August 08-13, 1999, Los Angeles, California, United States [doi>10.1145/311625.312171]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis

General Terms:
Algorithms

Keywords:
Time-dependent surfaces, deformation, elasticity, finite element methods, fitting, tracking