“A realtime GPU subdivision kernel” by Shiue, Jones and Peters

  • ©Le-Jeng Shiue, Ian Jones, and Jörg Peters




    A realtime GPU subdivision kernel



    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.


    1. Biermann, H., Martin, I., Bernardini, F., and Zorin, D. 2002. Cut-and-paste editing of multiresolution surfaces. In SIGGRAPH ’02 Conference Proceedings, 312–321. Google ScholarDigital Library
    2. Bolz, J., and Schröder, P. Evaluation Of Subdivision Surfaces On Programmable Graphics Hardware. http://www.multires.caltech.edu/pubs/gpusubd.pdf.Google Scholar
    3. Bolz, J., and Schröder, P. 2002. Rapid evaluation of Catmull-Clark subdivision surfaces. In Proceedings of the Web3D 2002 Symposium, 11–18. Google ScholarDigital Library
    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. Google ScholarDigital Library
    5. Bóo. M., Amor, M., Doggett, M., Hirche, J., and Strasser, W. 2001. Hardware support for adaptive subdivision surface rendering. In Proceedings of the Workshop on Graphics Hardware, 33–40. Google ScholarDigital Library
    6. Bunnell, M. 2005. GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation. Addison-Wesley, Reading, MA, ch. Adaptive Tessellation of Subdivision Surfaces with Displacement Mapping. Google ScholarDigital Library
    7. Catmull, E., and Clark, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design 10, 350–355.Google ScholarCross Ref
    8. DeRose, T., Kass, M., and Truong, T. 1998. Subdivision surfaces in character animation. In SIGGRAPH ’98 Conference Proceedings, 85–94. Google ScholarDigital Library
    9. Doo, D., and Sabin, M. 1978. Behaviour of recursive division surfaces near extraordinary points. Computer Aided Design 10 (Sept.), 356–360.Google ScholarCross Ref
    10. Govindaraju, N. K., Redon, S., Lin, M. C., and Manocha, D. 2003. Cullide: interactive collision detection between complex models in large environments using graphics hardware. In Proceedings of the Conference on Graphics Hardware, Eurographics Association, 25–32. Google ScholarDigital Library
    11. Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry images. In SIGGRAPH ’02 Conference Proceedings, 335–361. Google ScholarDigital Library
    12. Guibas, L. J., and Stolfi, J. 1983. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 221–234. Google ScholarDigital Library
    13. Harris, M. J., Baxter, W. V., Scheuermann, T., and Lastra, A. 2003. Simulation of cloud dynamics on graphics hardware. In Proceedings of the Conference on Graphics Hardware, Eurographics Association, 92–101. Google ScholarDigital Library
    14. Harris, M., Luebke, D., Buck, I., Govindaraju, N., Krüger, J., Lefohn, A. E., Purcell, T. J., and Woolley, C. 2004. GPGPU: General-purpose computation on graphics hardware. Course notes 32 of SIGGRAPH 2004. Google ScholarDigital Library
    15. John Kessenich, D. B., and Rost, R. 2004. The OpenGL shading language (version 1.10. Tech. rep., April.Google Scholar
    16. Kettner, L. 1999. Using generic programming for designing a data structure for polyhedral surfaces. Computational Geometry 13, 1 (May), 65–90. Google ScholarDigital Library
    17. Kipfer, P., Segal, M., and Westermann, R. 2004. Uber-flow: A GPU-based particle engine. In Eurographics Symposium Proceedings Graphics Hardware 2004, 115–122. Google ScholarDigital Library
    18. Kobbelt, L. 2000. √3 subdivision. In SIGGRAPH ’00 Conference Proceedings, 103–112. Google ScholarDigital Library
    19. Kolb, A., Latta, L., and Rezk-Salama, C. 2004. Hardware-based simulation and collision detection for large particle systems. In Eurographics Symposium Proceedings Graphics Hardware 2004. Google ScholarDigital Library
    20. Krüger, J., and Westermann, R. 2003. Linear algebra operators for gpu implementation of numerical algorithms. In SIGGRAPH ’03 Conference Proceedings, 908–916. Google ScholarDigital Library
    21. Lindholm, E., Kligard, M. J., and Moreton, H. 2001. A user-programmable vertex engine. In SIGGRAPH ’01 Conference Proceedings, 149–158. Google ScholarDigital Library
    22. Loop, C. T., 1987. Smooth subdivision surfaces based on triangles. Master’s Thesis, Department of Mathematics, University of Utah.Google Scholar
    23. Losasso, F., Hoppe, H., Schaefer, S., and Warren, J. 2003. Smooth geometry images. In Proceedings of the symposium on Geometry processing, 138–145. Google ScholarDigital Library
    24. Mace, R. 2004. OpenGL ARB Superbuffers (OpenGL tutorial). Tech. rep. Game Developers Conference.Google Scholar
    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.).Google ScholarCross Ref
    26. Padrón, E. J., Amor, M., Bóo, M., and Doallo, R. 2002. Efficient parallel implementations for surface subdivision. In Proceedings of the Fourth Eurographics Workshop on Parallel Graphics and Visualization, 113–121. Google ScholarDigital Library
    27. Peters, J. 2000. Patching Catmull-Clark meshes. In SIGGRAPH ’00 Conference Proceedings, 255–258. Google ScholarDigital Library
    28. Pulli, K., and Segal, M. 1996. Fast rendering of subdivision surfaces. In Proceedings of the EUROGRAPHICS Workshop on Rendering Techniques, 61–70. Google ScholarDigital Library
    29. Purcell, T. J., Donner, C., Cammarano, M., Jensen, H. W., and Hanrahan, P. 2003. Photon mapping on programmable graphics hardware. In Proceedings of the Symposium on Graphics Hardware, Eurographics Association, 41–50. Google ScholarDigital Library
    30. Shiue, L.-J., and Peters, J. 2005. A pattern-based data structure for manipulating meshes with regular regions. In Graphics Interface, to appear. Google ScholarDigital Library
    31. Shiue, L.-J., Goel, V., and Peters, J. 2003. Mesh mutation in programmable graphics hardware. In Proceedings of the Conference on Graphics Hardware, 15–24. Google ScholarDigital Library
    32. Warren, J., and Weimer, H. 2002. Subdivision Methods for Geometric Design. Morgan Kaufmann Publishers. Google ScholarDigital Library
    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.Google ScholarDigital Library
    34. Zorin, D. 1999. Implementing subdivision and multiresolution meshes. Chapter 6 of Course notes 37 of SIGGRAPH 99.Google Scholar

ACM Digital Library Publication: