“Direct manipulation of subdivision surfaces on GPUs” by Zhou, Huang, Xu, Guo and Shum

We present an algorithm for interactive deformation of subdivision surfaces, including displaced subdivision surfaces and subdivision surfaces with geometric textures. Our system lets the user directly manipulate the surface using freely-selected surface points as handles. During deformation the control mesh vertices are automatically adjusted such that the deforming surface satisfies the handle position constraints while preserving the original surface shape and details. To best preserve surface details, we develop a gradient domain technique that incorporates the handle position constraints and detail preserving objectives into the deformation energy. For displaced subdivision surfaces and surfaces with geometric textures, the deformation energy is highly nonlinear and cannot be handled with existing iterative solvers. To address this issue, we introduce a shell deformation solver, which replaces each numerically unstable iteration step with two stable mesh deformation operations. Our deformation algorithm only uses local operations and is thus suitable for GPU implementation. The result is a real-time deformation system running orders of magnitude faster than the state-of-the-art multigrid mesh deformation solver. We demonstrate our technique with a variety of examples, including examples of creating visually pleasing character animations in real-time by driving a subdivision surface with motion capture data.

1. Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105–114.Google ScholarCross Ref
2. Au, O. K.-C., Tai, C.-L., Liu, L., and Fu, H. 2006. Dual laplacian editing for meshes. IEEE TVCG 12, 3, 386–395. Google ScholarDigital Library
3. Boier-Martin, I., Ronfard, R., and Bernardini, F. 2004. Detail-preserving variational surface design with multiresolution constraints. In Proceedings of the Shape Modeling International 2004, 119–128. Google ScholarCross Ref
4. Bolz, J., and Schröder, P. 2004. Evaluation of subdivision surfaces on programmable graphics hardware. to appear.Google Scholar
5. Bolz, J., Farmer, I., Grinspun, E., and Schröder, P. 2003. Sparse matrix solvers on the gpu: Conjugate gradients and multigrid. ACM Trans. Graph. 22, 3, 917–924. Google ScholarDigital Library
6. Botsch, M., and Kobbelt, L. 2004. An intuitive framework for real-time freeform-modeling. ACM Trans. Graph. 23, 3, 630–634. Google ScholarDigital Library
7. Botsch, M., and Kobbelt, L. 2005. Real-time shape editing using radial basis functions. In Eurographics 2005, 611–621.Google Scholar
8. Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. Primo: Coupled prisms for intuitive surface modeling. In Eurographics Symposium on Geometry Processing, 11–20. Google ScholarDigital Library
9. Cohen, J., Varshney, A., Manocha, D., Turk, G., Weber, H., Agarwal, P., Brooks, F., and Wright, W. 1996. Simplification envelopes. In SIGGRAPH 96 Conference Proceedings, 223–231. Google ScholarDigital Library
10. Cook, R. L. 1984. Shade trees. In SIGGRAPH 84 Conference Proceedings, 223–231. Google ScholarDigital Library
11. Der, K. G., Sumner, R. W., and Popović, J. 2006. Inverse kinematics for reduced deformable modelss. ACM Trans. Graph. 25, 3, 1174–1179. Google ScholarDigital Library
12. DeRose, T., Kass, M., and Truong, T. 1998. Subdivision surfaces in character animation. In SIGGRAPH 98 Conference Proceedings, 85–94. Google ScholarDigital Library
13. Desbrun, M., Meyer, M., Schroder, P., and Barr, A. H. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In SIGGRAPH 99 Conference Proceedings, 317–324. Google ScholarDigital Library
14. Forsey, D. R., and Bartels, R. H. 1988. Hierarchical b-spline refinement. In SIGGRAPH 88 Conference Proceedings, 205–212. Google ScholarDigital Library
15. Guskov, I., Vidimce, K., Sweldens, W., and Schroder, P. 2000. Normal meshes. In SIGGRAPH 2000 Conference Proceedings, 95–102. Google ScholarDigital Library
16. Hsu, W. M., Hughes, J. F., and Kaufman, H. 1992. Direct manipulation of free-form deformations. In SIGGRAPH 92 Conference Proceedings, 177–184. Google ScholarDigital Library
17. 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, 1126–1134. Google ScholarDigital Library
18. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566. Google ScholarDigital Library
19. Kobbelt, L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In SIGGRAPH 98 Conference Proceedings, 105–114. Google ScholarDigital Library
20. Kruger, J., and Westermann, R. 2003. Linear algebra operators for gpu implementation of numerical algorithms. ACM Trans. Graph. 22, 3, 908–916. Google ScholarDigital Library
21. Lee, A., Moreton, H., and Hoppe, H. 2000. Displaced subdivision surfaces. In SIGGRAPH 2000 Conference Proceedings, 85–94. Google ScholarDigital Library
22. Lipman, Y., Sorkine, O., Levin, D., and Cohen-Or, D. 2005. Linear rotation-invariant coordinates for meshes. ACM Trans. Graph. 24, 3, 479–487. Google ScholarDigital Library
23. Lipman, Y., Cohen-Or, D., Gal, R., and Levin, D. 2006. Volume and shape preservation via moving frame manipulation. ACM Trans. Graph., to appear. Google ScholarDigital Library
24. Loop, C. T. 1987. Smooth subdivision surfaces based on triangles. Master’s Thesis, Department of Mathematics, University of Utah.Google Scholar
25. Marinov, M., Botsch, M., and Kobbelt, L. 2007. Gpu-based multiresolution deformation using approximate normal field reconstruction. Journal of Graphics Tools 12, 1, 27–46.Google ScholarCross Ref
26. 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
27. Peng, J., Kristjansson, D., and Zorin, D. 2004. Interactive modeling of topologically complex geometric detail. ACM Trans. Graph. 23, 3, 635–643. Google ScholarDigital Library
28. Porumbescu, S. D., Budge, B., Feng, L., and Joy, K. I. 2005. Shell maps. ACM Trans. Graph. 23, 3, 626–633. Google ScholarDigital Library
29. Sederberg, T. W., and Parry, S. R. 1986. Free-form deformation of solid geometric models. In SIGGRAPH 86 Conference Proceedings, 151–160. Google ScholarDigital Library
30. Sheffer, A., and Kraevoy, V. 2004. Pyramid coordinates for morphing and deformation. In Proceedings of 3DPVT ’04, 68–75. Google ScholarCross Ref
31. Shi, L., Yu, Y., Bell, N., and Feng, W.-W. 2006. A fast multigrid algorithm for mesh deformation. ACM Trans. Graph. 25, 3, 1108–1117. Google ScholarDigital Library
32. Shiue, L.-J., Jones, I., and Peters, J. 2005. A realtime gpu subdivision kernel. ACM Trans. Graph. 24, 3, 1010–1015. Google ScholarDigital Library
33. Singh, K., and Fiume, E. 1998. Wires: a geometric deformation technique. In SIGGRAPH 98 Conference Proceedings, 405–414. Google ScholarDigital Library
34. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Eurographics Symposium on Geometry Processing, 175–184. Google ScholarDigital Library
35. Steihaug, T. 1995. An inexact gauss-newton approach to mildly nonlinear problems. Tech. rep., Dept. of Mathematics, University of Linkoping.Google Scholar
36. Sumner, R. W., Zwicker, M., Gotsman, C., and Popović, J. 2005. Mesh-based inverse kinematics. ACM Trans. Graph. 24, 3, 488–495. Google ScholarDigital Library
37. von Funck, W., Theisel, H., and Seidel, H.-P. 2006. Vector field based shape deformations. ACM Trans. Graph. 25, 3, 1118–1125. Google ScholarDigital Library
38. Warren, J., and Weimer, H. 2002. Subdivision Methods for Geometric Design. Morgan Kaufmann Publishers. Google ScholarDigital Library
39. Welch, W., and Witkin, A. 1992. Variational surface modeling. In Proceedings of SIGGRAPH 92, 157–166. Google ScholarDigital Library
40. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., and Shum, H.-Y. 2004. Mesh editing with poisson-based gradient field manipulation. ACM Trans. Graph. 23, 3, 644–651. Google ScholarDigital Library
41. Zayer, R., Rössl, C., Karni, Z., and Seidel, H.-P. 2005. Harmonic guidance for surface deformation. In Eurographics 2005, 601–609.Google Scholar
42. Zhou, K., Huang, J., Snyder, J., Liu, X., Bao, H., Guo, B., and Shum, H.-Y. 2005. Large mesh deformation using the volumetric graph laplacian. ACM Trans. Graph. 24, 3, 496–503. Google ScholarDigital Library
43. Zorin, D., Schröderr, P., and Sweldens, W. 1997. Interactive multiresolution mesh editing. In SIGGRAPH 97 Conference Proceedings, 259–268. Google ScholarDigital Library
44. Zorin, D., Schröderr, P., DeRose, T., Kobbelt, L., Levin, A., and Sweldens, W. 2000. Subdivision for modeling and animation. Course notes of SIGGRAPH 2000.Google Scholar