“Interactive Surface Modeling Using Modal Analysis” by Hildebrandt, Schulz, Tycowicz and Polthier

We propose a framework for deformation-based surface modeling that is interactive, robust, and intuitive to use. The deformations are described by a nonlinear optimization problem that models static states of elastic shapes under external forces which implement the user input. Interactive response is achieved by a combination of model reduction, a robust energy approximation, and an efficient quasi-Newton solver. Motivated by the observation that a typical modeling session requires only a fraction of the full shape space of the underlying model, we use second and third derivatives of a deformation energy to construct a low-dimensional shape space that forms the feasible set for the optimization. Based on mesh coarsening, we propose an energy approximation scheme with adjustable approximation quality. The quasi-Newton solver guarantees superlinear convergence without the need of costly Hessian evaluations during modeling. We demonstrate the effectiveness of the approach on different examples including the test suite introduced in Sorkine [2008].

Adams, B., Ovsjanikov, M., Wand, M., Seidel, H.-P., and Guibas, L. J. 2008. Meshless modeling of deformable shapes and their motion. In Proceedings of Symposium on Computer Animation. 77–86. Google ScholarDigital Library
An, S. S., Kim, T., and James, D. L. 2008. Optimizing cubature for efficient integration of subspace deformations. Trans. Graph. 27, 5, 1–10. Google ScholarDigital Library
Au, O. K.-C., Tai, C.-L., Liu, L., and Fu, H. 2006. Dual Laplacian editing for meshes. IEEE Trans. Vis. Comput. Graph. 12, 386–395. Google ScholarDigital Library
Baraff, D. and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of ACM SIGGRAPH. 43–54. Google ScholarDigital Library
Barbič, J. and James, D. L. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. Graph. 24, 3, 982–990. Google ScholarDigital Library
Barbič, J. and Popović, J. 2008. Real-time control of physically based simulations using gentle forces. ACM Trans. Graph. 27, 5, 1–10. Google ScholarDigital Library
Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Variational harmonic maps for space deformation. Trans. Graph. 28, 3. Google ScholarDigital Library
Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. PriMo: Coupled prisms for intuitive surface modeling. In Proceedings of Eurographics/Siggraph Symposium on Geometry Processing. 11–20. Google ScholarDigital Library
Botsch, M., Pauly, M., Wicke, M., and Gross, M. 2007. Adaptive space deformations based on rigid cells. Comput. Graph. Forum 26, 3, 339–347.Google ScholarCross Ref
Botsch, M. and Sorkine, O. 2008. On linear variational surface deformation methods. IEEE Trans. Vis. Comput. Graph. 14, 1, 213–230. Google ScholarDigital Library
Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 28–36. Google ScholarDigital Library
Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 38:1–38:6. Google ScholarDigital Library
Choi, M. G. and Ko, H.-S. 2005. Modal warping: Real-time simulation of large rotational deformation and manipulation. IEEE Trans. Vis. Comput. Graph. 11, 1, 91–101. Google ScholarDigital Library
Ciarlet, P. G. 2000. Mathematical Elasticity – Volume III: Theory of Shells. Studies in Mathematics and Its Applications, vol. 29. North Holland.Google Scholar
Garg, A., Grinspun, E., Wardetzky, M., and Zorin, D. 2007. Cubic Shells. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 91–98. Google ScholarDigital Library
Gill, P. E., Murray, W., and Wright, M. H. 1982. Practical Optimization. Academic Press.Google Scholar
Griewank, A., Juedes, D., and Utke, J. 1996. Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++. ACM Trans. Math. Softw. 22, 2, 131–167. Google ScholarDigital Library
Grinspun, E., Hirani, A. N., Desbrun, M., and Schröder, P. 2003. Discrete shells. In Proceedings of the Symposium on Computer Animation. 62–67. Google ScholarDigital Library
Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Proceedings of the Graphics Interface Conference. 247–256.Google Scholar
Hildebrandt, K., Schulz, C., von Tycowicz, C., and Polthier, K. 2010. Eigenmodes of surface energies for shape analysis. In Proceedings of the Geometric Modeling and Processing Conference. 296–314. Google ScholarDigital Library
Huang, J., Shi, X., Liu, X., Zhou, K., Wei, L.-Y., Teng, S.-H., Bao, H., Guo, B., and Shum, H.-Y. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graph. 25, 3. Google ScholarDigital Library
Huang, Q., Wicke, M., Adams, B., and Guibas, L. 2009. Shape decomposition using modal analysis. Comput. Graph. Forum 28, 2, 407–416.Google ScholarCross Ref
Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph.. 561–566. Google ScholarDigital Library
Kraevoy, V. and Sheffer, A. 2006. Mean-value geometry encoding. Int. J. Shape Model. 12, 1, 29–46.Google ScholarCross Ref
Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. Int. J. Numer. Meth. Engin. 51, 479–504.Google ScholarCross Ref
Lévy, B. and Zhang, H. 2009. Spectral mesh processing. In ACM SIGGRAPH ASIA Courses. 1–47. Google ScholarDigital Library
Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3, 1–10. Google ScholarDigital Library
Lipman, Y., Sorkine, O., Cohen-Or, D., Levin, D., Rössl, C., and Peter Seidel, H. 2004. Differential coordinates for interactive mesh editing. In Proceedings of the Shape Modeling International Conference. 181–190. Google ScholarDigital Library
Nealen, A., Sorkine, O., Alexa, M., and Cohen-Or, D. 2005. A sketch-based interface for detail-preserving mesh editing. ACM Trans. Graph. 24, 3, 1142–1147. Google ScholarDigital Library
Nocedal, J. and Wright, S. J. 2006. Numerical Optimization, 2nd ed. Springer.Google Scholar
Pentland, A. and Williams, J. 1989. Good vibrations: modal dynamics for graphics and animation. In Proceedings of the ACM SIGGRAPH Conference. 215–222. Google ScholarDigital Library
Shi, X., Zhou, K., Tong, Y., Desbrun, M., Bao, H., and Guo, B. 2007. Mesh puppetry: cascading optimization of mesh deformation with inverse kinematics. ACM Trans. Graph. 26, 3, 81. Google ScholarDigital Library
Sorkine, O. and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. 109–116. Google ScholarDigital Library
Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Proceedings of the Symposium on Geometry Processing. 175–184. Google ScholarDigital Library
Sumner, R. W., Schmid, J., and Pauly, M. 2007. Embedded deformation for shape manipulation. Trans. Graph. 26, 3. Google ScholarDigital Library
Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proceedings of the ACM SIGGRAPH Conference. 205–214. Google ScholarDigital Library
Vallet, B. and Lévy, B. 2008. Spectral geometry processing with manifold harmonics. Comput. Graph. Forum.Google Scholar
Zhang, H., van Kaick, O., and Dyer, R. 2010. Spectral mesh processing. Comput. Graph. Forum 29, 6, 1865–1894.Google ScholarCross Ref