Geometric modeling in shape space

Abstract

We present a novel framework to treat shapes in the setting of Riemannian geometry. Shapes -- triangular meshes or more generally straight line graphs in Euclidean space -- are treated as points in a shape space. We introduce useful Riemannian metrics in this space to aid the user in design and modeling tasks, especially to explore the space of (approximately) isometric deformations of a given shape. Much of the work relies on an efficient algorithm to compute geodesics in shape spaces; to this end, we present a multi-resolution framework to solve the interpolation problem -- which amounts to solving a boundary value problem -- as well as the extrapolation problem -- an initial value problem -- in shape space. Based on these two operations, several classical concepts like parallel transport and the exponential map can be used in shape space to solve various geometric modeling and geometry processing tasks. Applications include shape morphing, shape deformation, deformation transfer, and intuitive shape exploration.

References

1. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proc. SIGGRAPH '00, 157--164.
2. Allen, B., Curless, B., and Popović, Z. 2003. The space of human body shapes: reconstruction and parameterization from range scans. ACM Trans. Graphics 22, 3, 587--594.
3. Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. 2005. SCAPE: shape completion and animation of people. ACM Trans. Graphics 24, 3, 408--416.
4. Berger, M. 1987. Geometry I, II. Springer.
5. Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. Primo: coupled prisms for intuitive surface modeling. In Symp. Geom. Processing, 11--20.
6. Bottema, O., and Roth, B. 1990. Theoretical kinematics. Dover Publ.
7. Bronstein, A., Bronstein, M., and Kimmel, R. 2005. Isometric embedding of facial surfaces into S³. In Proc. of Scale-Space, 622--631.
8. Cecil, T. 1992. Lie Sphere Geometry. Springer.
9. Charpiat, G., Faugeras, O., and Keriven, R. 2005. Approximations of shape metrics and application to shape warping and empirical statistics. Foundations of Comp. Math., 5, 1--58.
10. Charpiat, G., Keriven, R., Pons, J.-P., and Faugeras, O. 2005. Designing spatially coherent minimizing flows for variational problems based on active contours. In Proc. ICCV 2005, vol. 2, 1403--1408.
11. Cheng, H.-L., Edelsbrunner, H., and Fu, P. 1998. Shape space from deformation. In Proc. Pacific Graphics, 104--113.
12. Cox, T., and Cox, M. 2001. Multidimensional Scaling. CRC/Chapman and Hall.
13. Do Carmo, M. P. 1992. Riemannian Geometry. Birkhäuser.
14. Funck, W., Theisel, H., and Seidel, H. 2006. Vector field based shape deformations. ACM Trans. Graphics 25, 3, 1118--1125.
15. Garland, M., and Heckbert, P. 1997. Surface simplification using quadric error metrics. In ACM SIGGRAPH, 209--216.
16. Gelfand, I. M., and Fomin, S. V. 1963. Calculus of Variations. Prentice Hall.
17. Hoppe, H. 1996. Progressive meshes. In ACM SIGGRAPH, 99--108.
18. Huang, J., Shi, X., Liu, X., Zhou, K., Wei, L., Teng, S., Bao, H., Guo, B., and Shum, H. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graphics 25, 3, 1126--1134.
19. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graphics 24, 3, 1134--1141.
20. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graphics 24, 3, 561--566.
21. Kendall, D. G. 1984. Shape manifolds, procrustean metrics and complex projective spaces. Bull. London Math. Soc. 18, 81--121.
22. Kilian, M. 2007. Shapes, metrics, and their geodesics. Tech. Rep. 178, Vienna University of Technology.
23. Kimmel, R., and Sethian, J. 1998. Computing geodesic paths on manifolds. Proc. Natl. Acad. Sci. 95, 8431--8435.
24. Klassen, E., Srivastava, A., Mio, W., and Joshi, S. H. 2004. Analysis of planar shapes using geodesic paths on shape spaces. IEEE PAMI 26, 3, 372--383.
25. Kraevoy, V., and Sheffer, A. 2004. Cross-parameterization and compatible remeshing of 3D models. ACM Trans. Graphics 23, 3, 861--869.
26. Kraevoy, V., and Sheffer, A. 2007. Mean-value geometry encoding. International Journal of Shape Modeling 12, 1.
27. Lipman, Y., Sorkine, O., Levin, D., and Cohen-Or, D. 2005. Linear rotation-invariant coordinates for meshes. ACM Trans. Graphics 24, 3, 479--487.
28. Lipman, Y., Cohen-Or, D., Gal, R., and Levin, D. 2007. Volume and shape preservation vai moving frame manipulation. ACM Trans. Graphics 26, 1.
29. Liu, D. C., and Nocedal, J. 1989. On the limited memory BFGS method for large scale optimization. Math. Program. 45, 3, 503--528.
30. Memoli, F., and Sapiro, G. 2001. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. J. Comput. Phys. 173, 730--764.
31. Mémoli, F., and Sapiro, G. 2004. Comparing point clouds. In Symp. Geometry Processing, 32--40.
32. Michor, P. W., and Mumford, D. 2006. Riemannian geometries on spaces of plane curves. J. Eur. Math. Soc. 8, 1--48.
33. Pottmann, H., and Wallner, J. 2001. Computational Line Geometry. Springer.
34. Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. Inter-surface mapping. ACM Trans. Graphics 23, 3, 870--877.
35. Sloan, P.-P. J., Rose, C. F., and Cohen, M. F. 2001. Shape by example. In Proc. of the 2001 symposium on interactive 3D graphics, 135--143.
36. Sorkine, O., Lipman, Y., Cohen-Or, D., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Symp. Geom. Processing, 179--188.
37. Sumner, R. W., and Popovič, J. 2004. Deformation transfer for triangle meshes. ACM Trans. Graphics 23, 3, 399--405.
38. Xu, D., Zhang, H., Wang, Q., and Bao, H. 2005. Poisson shape interpolation. In SPM '05: Proc. ACM Symp. on Solid and Physical Modeling, 267--274.
39. Yezzi, A., and Mennucci, A. 2005. Conformal metrics and true "gradient flows" for curves. In Proc. ICCV '05, 913--919.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry