Gradient domain editing of deforming mesh sequences

ABSTRACT

Many graphics applications, including computer games and 3D animated films, make heavy use of deforming mesh sequences. In this paper, we generalize gradient domain editing to deforming mesh sequences. Our framework is keyframe based. Given sparse and irregularly distributed constraints at unevenly spaced keyframes, our solution first adjusts the meshes at the keyframes to satisfy these constraints, and then smoothly propagate the constraints and deformations at keyframes to the whole sequence to generate new deforming mesh sequence. To achieve convenient keyframe editing, we have developed an efficient alternating least-squares method. It harnesses the power of subspace deformation and two-pass linear methods to achieve high-quality deformations. We have also developed an effective algorithm to define boundary conditions for all frames using handle trajectory editing. Our deforming mesh editing framework has been successfully applied to a number of editing scenarios with increasing complexity, including footprint editing, path editing, temporal filtering, handle-based deformation mixing, and spacetime morphing.

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: Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105--114.
• 3: Oscar Kin-Chung Au , Chiew-Lan Tai , Ligang Liu , Hongbo Fu, Dual Laplacian Editing for Meshes, IEEE Transactions on Visualization and Computer Graphics, v.12 n.3, p.386-395, May 2006 [doi>10.1109/TVCG.2006.47]
• 4: Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. Primo: Coupled prisms for intuitive surface modeling. 11--20.
• 5: Davis, T. A. 2005. Umfpack version 4.4 user guide. Tech. Rep. TR-04-003, University of Florida.
• 6: Davis, T. A. 2006. User guide for cholmod. Tech. rep., University of Florida.
• 7: Kevin G. Der , Robert W. Sumner , Jovan Popović, Inverse kinematics for reduced deformable models, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 8: Michael Gleicher, Motion path editing, Proceedings of the 2001 symposium on Interactive 3D graphics, p.195-202, March 2001 [doi>10.1145/364338.364400]
• 9: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 10: Horn, B. 1987. Closed-form solution of absolute orientation using unit quaternions. J. Opt. Soc. Am. A 4, 4, 629--642.
• 11: 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
• 12: Takeo Igarashi , Tomer Moscovich , John F. Hughes, As-rigid-as-possible shape manipulation, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 13: Doug L. James , Christopher D. Twigg, Skinning mesh animations, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 14: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 15: Scott Kircher , Michael Garland, Editing arbitrarily deforming surface animations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 16: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 17: Vladislav Kraevoy , Alla Sheffer, Cross-parameterization and compatible remeshing of 3D models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 18: 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
• 19: Lipman, Y., Cohen-Or, D., Gal, R., and Levin, D. 2006. Volume and shape preservation via moving frame manipulation. Technical report.
• 20: Alex Mohr , Michael Gleicher, Building efficient, accurate character skins from examples, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 21: Matthias Müller , Bruno Heidelberger , Matthias Teschner , Markus Gross, Meshless deformations based on shape matching, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 22: Sang Il Park , Jessica K. Hodgins, Capturing and animating skin deformation in human motion, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 23: Alla Sheffer , Vladislav Kraevoy, Pyramid Coordinates for Morphing and Deformation, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, p.68-75, September 06-09, 2004 [doi>10.1109/3DPVT.2004.99]
• 24: Lin Shi , Yizhou Yu , Nathan Bell , Wei-Wen Feng, A fast multigrid algorithm for mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 25: 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]
• 26: Robert W. Sumner , Jovan Popović, Deformation transfer for triangle meshes, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 27: Robert W. Sumner , Matthias Zwicker , Craig Gotsman , Jovan Popović, Mesh-based inverse kinematics, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 28: Jue Wang , Steven M. Drucker , Maneesh Agrawala , Michael F. Cohen, The cartoon animation filter, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 29: 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
• 30: Zayer, R., Rössl, C., Karni, Z., and Seidel, H.-P. 2005. Harmonic guidance for surface deformation. Computer Graphics Forum (Eurographics 2005) 24, 3.
• 31: 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
• 32: Denis Zorin , Peter Schröder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997 [doi>10.1145/258734.258863]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Least squares methods

General Terms:
Algorithms, Design

Keywords:
control meshes, handle trajectory, keyframes, local frames, mesh deformation, rotation interpolation