A realtime GPU subdivision kernel

ABSTRACT

By organizing the control mesh of subdivision in texture memory so that irregularities occur strictly inside independently refinable fragment meshes, all major features of subdivision algorithms can be realized in the framework of highly parallel stream processing. Our implementation of Catmull-Clark subdivision as a GPU kernel in programmable graphics hardware can model features like semi-smooth creases and global boundaries; and a simplified version achieves near-realtime depth-five re-evaluation of moderate-sized subdivision meshes. The approach is easily adapted to other refinement patterns, such as Loop, Doo-Sabin or √3 and it allows for postprocessing with additional shaders.

REFERENCES

• 1: Henning Biermann , Ioana Martin , Fausto Bernardini , Denis Zorin, Cut-and-paste editing of multiresolution surfaces, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 2: Bolz, J., and Schröder, P. Evaluation Of Subdivision Surfaces On Programmable Graphics Hardware. http://www.multires.caltech.edu/pubs/gpusubd.pdf.
• 3: Jeffrey Bolz , Peter Schröder, Rapid evaluation of Catmull-Clark subdivision surfaces, Proceeding of the seventh international conference on 3D Web technology, p.11-17, February 24-28, 2002, Tempe, Arizona, USA [doi>10.1145/504502.504505]
• 4: Bolz, J., Farmer, I., Grinspun, E., and Schröder, P. 2003. Sparse matrix solvers on the gpu: conjugate gradients and multi-grid. In SIGGRAPH '03 Conference Proceedings, 917--924.
• 5: M. Bóo , M. Amor , M. Doggett , J. Hirche , W. Strasser, Hardware support for adaptive subdivision surface rendering, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.33-40, August 2001, Los Angeles, California, United States [doi>10.1145/383507.383522]
• 6: Matt Pharr , Randima Fernando, GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation (Gpu Gems), Addison-Wesley Professional, 2005
• 7: Catmull, E., and Clark, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design 10, 350--355.
• 8: 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]
• 9: Doo, D., and Sabin, M. 1978. Behaviour of recursive division surfaces near extraordinary points. Computer Aided Design 10 (Sept.), 356--360.
• 10: Naga K. Govindaraju , Stephane Redon , Ming C. Lin , Dinesh Manocha, CULLIDE: interactive collision detection between complex models in large environments using graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 11: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 12: Leo J. Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.221-234, December 1983 [doi>10.1145/800061.808751]
• 13: Mark J. Harris , William V. Baxter , Thorsten Scheuermann , Anselmo Lastra, Simulation of cloud dynamics on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 14: David Luebke , Mark Harris , Jens Krüger , Tim Purcell , Naga Govindaraju , Ian Buck , Cliff Woolley , Aaron Lefohn, GPGPU: general purpose computation on graphics hardware, Proceedings of the conference on SIGGRAPH 2004 course notes, p.33-es, August 08-12, 2004, Los Angeles, CA [doi>10.1145/1103900.1103933]
• 15: John Kessenich, D. B., and Rost, R. 2004. The OpenGL shading language (version 1.10. Tech. rep., April.
• 16: Lutz Kettner, Using generic programming for designing a data structure for polyhedral surfaces, Computational Geometry: Theory and Applications, v.13 n.1, p.65-90, May 1999 [doi>10.1016/S0925-7721(99)00007-3]
• 17: Peter Kipfer , Mark Segal , Rüdiger Westermann, UberFlow: a GPU-based particle engine, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058146]
• 18: Leif Kobbelt, √3-subdivision, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.103-112, July 2000 [doi>10.1145/344779.344835]
• 19: A. Kolb , L. Latta , C. Rezk-Salama, Hardware-based simulation and collision detection for large particle systems, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058147]
• 20: Krüger, J., and Westermann, R. 2003. Linear algebra operators for gpu implementation of numerical algorithms. In SIGGRAPH '03 Conference Proceedings, 908--916.
• 21: Erik Lindholm , Mark J. Kligard , Henry Moreton, A user-programmable vertex engine, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.149-158, August 2001 [doi>10.1145/383259.383274]
• 22: Loop, C. T., 1987. Smooth subdivision surfaces based on triangles. Master's Thesis, Department of Mathematics, University of Utah.
• 23: F. Losasso , H. Hoppe , S. Schaefer , J. Warren, Smooth geometry images, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 24: Mace, R. 2004. OpenGL ARB Superbuffers (OpenGL tutorial). Tech. rep. Game Developers Conference.
• 25: Müller, K., and Havemann, S. 2000. Subdivision surface tesselation on the fly using a versatile mesh data structure. Computer Graphics Forum 19, 3 (Aug.).
• 26: E. J. Padrón , M. Amor , M. Bóo , R. Doallo, Efficient parallel implementations for surface subdivision, Proceedings of the Fourth Eurographics Workshop on Parallel Graphics and Visualization, September 09-10, 2002, Blaubeuren, Germany
• 27: Jörg Peters, Patching Catmull-Clark meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.255-258, July 2000 [doi>10.1145/344779.344908]
• 28: Kari Pulli , Mark Segal, Fast rendering of subdivision surfaces, Proceedings of the eurographics workshop on Rendering techniques '96, p.61-70, December 1996, Porto, Portugal
• 29: Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 30: Le-Jeng Shiue , Jörg Peters, A pattern-based data structure for manipulating meshes with regular regions, Proceedings of the 2005 conference on Graphics interface, May 09-11, 2005, Victoria, British Columbia
• 31: Le-Jeng Shiue , Vineet Goel , Jorg Peters, Mesh mutation in programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 32: Joe Warren , Joseph D. Warren , Henrik Weimer, Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 33: Weiler, K. 1985. Edge-based data structures for solid modeling in curved-surface environments. IEEE Computer Graphics and Applications 5, 1 (Jan.), 21--40.
• 34: Zorin, D. 1999. Implementing subdivision and multiresolution meshes. Chapter 6 of Course notes 37 of SIGGRAPH 99.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.4 Graphics Utilities
          Subjects: Software support

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

Keywords:
geometric data structure, programmable graphics hardware, shader, subdivision surfaces