Large mesh deformation using the volumetric graph Laplacian

ABSTRACT

We present a novel technique for large deformations on 3D meshes using the volumetric graph Laplacian. We first construct a graph representing the volume inside the input mesh. The graph need not form a solid meshing of the input mesh's interior; its edges simply connect nearby points in the volume. This graph's Laplacian encodes volumetric details as the difference between each point in the graph and the average of its neighbors. Preserving these volumetric details during deformation imposes a volumetric constraint that prevents unnatural changes in volume. We also include in the graph points a short distance outside the mesh to avoid local self-intersections. Volumetric detail preservation is represented by a quadric energy function. Minimizing it preserves details in a least-squares sense, distributing error uniformly over the whole deformed mesh. It can also be combined with conventional constraints involving surface positions, details or smoothness, and efficiently minimized by solving a sparse linear system.We apply this technique in a 2D curve-based deformation system allowing novice users to create pleasing deformations with little effort. A novel application of this system is to apply nonrigid and exaggerated deformations of 2D cartoon characters to 3D meshes. We demonstrate our system's potential with several examples.

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: 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
• 4: G. H. Bendels , R. Klein, Mesh forging: editing of 3D-meshes using implicitly defined occluders, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 5: Botsch, M., and Kobbelt, L. 2003. Multiresolution surface representation based on displacement volumes. Computer Graphics Forum 22, 3.
• 6: Mario Botsch , Leif Kobbelt, An intuitive framework for real-time freeform modeling, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 7: Christoph Bregler , Lorie Loeb , Erika Chuang , Hrishi Deshpande, Turning to the masters: motion capturing cartoons, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 8: Bridson, R., Teran, J., Molino, N., and Fedkiw, R. 2004. Adaptive physics based tetrahedral mesh generation using level sets. Engineering with Computers, to appear.
• 9: Chung, F. R. K. 1997. Spectral graph theory. CBMS 92, AMS.
• 10: Sabine Coquillart, Extended free-form deformation: a sculpturing tool for 3D geometric modeling, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.187-196, Aug. 1990
• 11: 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]
• 12: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 13: Laurent Favreau , Lionel Reveret , Christine Depraz , Marie-Paule Cani, Animal gaits from video, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028560]
• 14: Adam Finkelstein , David H. Salesin, Multiresolution curves, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.261-268, July 1994 [doi>10.1145/192161.192223]
• 15: Fujiwara, K. 1995. Eigenvalues of laplacians on a closed riemannian manifold and its nets. In Proceedings of AMS 123, 2585--2594.
• 16: 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]
• 17: Aaron Hertzmann , Nuria Oliver , Brian Curless , Steven M. Seitz, Curve analogies, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 18: Gentaro Hirota , Renee Maheshwari , Ming C. Lin, Fast volume-preserving free form deformation using multi-level optimization, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.234-245, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304036]
• 19: 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
• 20: Takeo Igarashi , Satoshi Matsuoka , Hidehiko Tanaka, Teddy: a sketching interface for 3D freeform design, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.409-416, July 1999 [doi>10.1145/311535.311602]
• 21: 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]
• 22: 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]
• 23: Kobbelt, L., Bareuther, T., and Seidel, H.-P. 2000. Multiresolution shape deformations for meshes with dynamic vertex connectivity. Computer Graphics Forum 19, 3, 249--260.
• 24: Differential Coordinates for Interactive Mesh Editing, Proceedings of the Shape Modeling International 2004 (SMI'04), p.181-190, June 07-09, 2004 [doi>10.1109/SMI.2004.30]
• 25: 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]
• 26: Meyer, M., Desbrun, M., Schröder, P., and Barr, A. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In Proc. VisMath.
• 27: 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]
• 28: Owen, S. J. 1998. A survey fo unstructured mesh generation technology. In 7th International Mehsing Roundtable, 239--267.
• 29: Ari Rappoport , Alla Sheffer , Michel Bercovier, Volume-preserving free-form solid, Proceedings of the third ACM symposium on Solid modeling and applications, p.361-372, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218086]
• 30: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.151-160, Aug. 1986
• 31: Alla Sheffer , Vladislav Kraevoy, Pyramid Coordinates for Morphing and Deformation, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium on (3DPVT'04), p.68-75, September 06-09, 2004 [doi>10.1109/3DPVT.2004.99]
• 32: 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]
• 33: 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]
• 34: 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]
• 35: Robert W. Sumner , Jovan Popović, Deformation transfer for triangle meshes, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 36: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 37: William Welch , Andrew Witkin, Free-form shape design using triangulated surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.247-256, July 1994 [doi>10.1145/192161.192216]
• 38: 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
• 39: Steve Zelinka , Michael Garland, Mesh Modelling with Curve Analogies, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference on (PG'04), p.94-98, October 06-08, 2004
• 40: 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.4 IMAGE PROCESSING AND COMPUTER VISION
        I.4.10 Image Representation
            Subjects: Volumetric

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance

Keywords:
deformation retargeting, differential domain methods, local transform propagation, volumetric details