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

  • ©Kun Zhou, Xin Huang, Weiwei Xu, Baining Guo, and Heung-Yeung Shum




    Direct manipulation of subdivision surfaces on GPUs



    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

ACM Digital Library Publication:

Overview Page: