Direct manipulation of subdivision surfaces on GPUs

ABSTRACT

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.

REFERENCES

• 1: Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105--114.
• 2: Oscar Kin-Chung Au , Chiew-Lan Tai , Ligang Liu , Hongbo Fu, Dual Laplacian Editing for Meshes, IEEE Transactions on Visualization and Computer Graphics, v.12 n.3, p.386-395, May 2006 [doi>10.1109/TVCG.2006.47]
• 3: Detail-Preserving Variational Surface Design with Multiresolution Constraints, Proceedings of the Shape Modeling International 2004, p.119-128, June 07-09, 2004 [doi>10.1109/SMI.2004.28]
• 4: Bolz, J., and Schröder, P. 2004. Evaluation of subdivision surfaces on programmable graphics hardware. to appear.
• 5: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 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: Botsch, M., and Kobbelt, L. 2005. Real-time shape editing using radial basis functions. In Eurographics 2005, 611--621.
• 8: Mario Botsch , Mark Pauly , Markus Gross , Leif Kobbelt, PriMo: coupled prisms for intuitive surface modeling, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 9: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 10: Robert L. Cook, Shade trees, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.223-231, January 1984
• 11: Kevin G. Der , Robert W. Sumner , Jovan Popović, Inverse kinematics for reduced deformable models, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 12: Tony DeRose , Michael Kass , Tien Truong, Subdivision surfaces in character animation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.85-94, July 1998 [doi>10.1145/280814.280826]
• 13: 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]
• 14: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.205-212, June 1988
• 15: Igor Guskov , Kiril Vidimče , Wim Sweldens , Peter Schröder, Normal meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.95-102, July 2000 [doi>10.1145/344779.344831]
• 16: 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
• 17: Jin Huang , Xiaohan Shi , Xinguo Liu , Kun Zhou , Li-Yi Wei , Shang-Hua Teng , Hujun Bao , Baining Guo , Heung-Yeung Shum, Subspace gradient domain mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 18: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 19: 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]
• 20: Jens Krüger , Rüdiger Westermann, Linear algebra operators for GPU implementation of numerical algorithms, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 21: Aaron Lee , Henry Moreton , Hugues Hoppe, Displaced subdivision surfaces, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.85-94, July 2000 [doi>10.1145/344779.344829]
• 22: Yaron Lipman , Olga Sorkine , David Levin , Daniel Cohen-Or, Linear rotation-invariant coordinates for meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 23: Yaron Lipman , Daniel Cohen-Or , Ran Gal , David Levin, Volume and shape preservation via moving frame manipulation, ACM Transactions on Graphics (TOG), v.26 n.1, p.5-es, January 2007 [doi>10.1145/1189762.1189767]
• 24: Loop, C. T. 1987. Smooth subdivision surfaces based on triangles. Master's Thesis, Department of Mathematics, University of Utah.
• 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.
• 26: Andrew Nealen , Olga Sorkine , Marc Alexa , Daniel Cohen-Or, A sketch-based interface for detail-preserving mesh editing, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 27: Jianbo Peng , Daniel Kristjansson , Denis Zorin, Interactive modeling of topologically complex geometric detail, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 28: Serban D. Porumbescu , Brian Budge , Louis Feng , Kenneth I. Joy, Shell maps, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 29: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.151-160, August 1986
• 30: Alla Sheffer , Vladislav Kraevoy, Pyramid Coordinates for Morphing and Deformation, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, p.68-75, September 06-09, 2004 [doi>10.1109/3DPVT.2004.99]
• 31: Lin Shi , Yizhou Yu , Nathan Bell , Wei-Wen Feng, A fast multigrid algorithm for mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 32: Le-Jeng Shiue , Ian Jones , Jörg Peters, A realtime GPU subdivision kernel, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 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: Steihaug, T. 1995. An inexact gauss-newton approach to mildly nonlinear problems. Tech. rep., Dept. of Mathematics, University of Linkoping.
• 36: Robert W. Sumner , Matthias Zwicker , Craig Gotsman , Jovan Popović, Mesh-based inverse kinematics, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 37: Wolfram von Funck , Holger Theisel , Hans-Peter Seidel, Vector field based shape deformations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 38: Joe Warren , Henrik Weimer, Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 39: William Welch , Andrew Witkin, Variational surface modeling, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.157-166, July 1992
• 40: 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
• 41: Zayer, R., Rössl, C., Karni, Z., and Seidel, H.-P. 2005. Harmonic guidance for surface deformation. In Eurographics 2005, 601--609.
• 42: Kun Zhou , Jin Huang , John Snyder , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, Large mesh deformation using the volumetric graph Laplacian, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 43: 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]
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Algorithms, Design

Keywords:
detail preservation, displacement mapping, geometric texture, subdivision surface