Efficient substitutes for subdivision surfaces in feature-quality games

ABSTRACT

As real time graphics aspires to movie-quality rendering, higher order, smooth surface representations take center stage. Catmull-Clark subdivision surfaces are the dominant higher-order surface type used in feature films as they can model surfaces of arbitrary topological type and provide a compact representation for smooth surfaces that facilitate modeling and animation. Although Catmull-Clark surfaces are popular in Digital Content Creation packages (DCC) and feature films, their use has been hindered in real time applications because the exact evaluation of such surfaces on modern GPUs is neither memory nor performance efficient. Developments in hardware and recent theoretical results in efficient substitutes for subdivision surfaces bring us to the possibility to see real-time cinematic rendering in the near future.

References

1. {BRS05} Tamy Boubekeur, Patrick Reuter, and Christophe Schlick. Scalar Tagged PN Triangles. In EUROGRAPHICS 2005 (Short Papers). Eurographics, 2005.
2. {BS02} J. Bolz and P. Schröder. Rapid Evaluation of Catmull-Clark Subdivision Surfaces. In Proceedings of the Web3D 2002 Symposium, pages 11--18. ACM Press, 2002.
3. {BS05} Tamy Boubekeur and Christophe Schlick. Generic Mesh Refinement on Gpu. In ACM SIGGRAPH/Eurographics Graphics Hardware, 2005.
4. {BS08} Tamy Boubekeur and Christophe Schlick. A Flexible Kernel for Adaptive Mesh Refinement on GPU. Computer Graphics Forum, 27(1):102--114, 2008.
5. {Bun05} Michael Bunnell. GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation, chapter Adaptive Tessellation of Subdivision Surfaces With Displacement Mapping. Addison-Wesley, Reading, MA, 2005.
6. {Cas08a} Ignacio Castaño. Next-Generation Rendering of Subdivision Surfaces, 2008. SIGGRAPH.
7. {Cas08b} Ignacio Castaño. Tessellation of Subdivision Surfaces in Directx 11, 2008. Gamefest.
8. {CC78} Edwin Catmull and James Clark. Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes. Computer-Aided Design, pages 350--355, 1978.
9. {CH02} Nathan A. Carr and John C. Hart. Meshed Atlases for Real-Time Procedural Solid Texturing. ACM Trans. Graph., 21(2):106--131, 2002.
10. {CHCH06} Nathan A. Carr, Jared Hoberock, Keenan Crane, and John C. Hart. Rectangular Multi-chart Geometry Images. In SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing, pages 181--190, Aire-la-Ville, Switzerland, Switzerland, 2006. Eurographics Association.
11. {CY10} Sarah Tariq Cem Yuksel. Advanced Techniques in Real-Time Hair Rendering and Simulation. In Siggraph 2010 Course Notes, 2010.
12. {DBG+06} Shen Dong, Peer-Timo Bremer, Michael Garland, Valerio Pascucci, and John C. Hart. Spectral Surface Quadrangulation. ACM Trans. Graph., 25(3):1057--1066, 2006.
13. {DKT98} T. DeRose, M. Kass, and T. Truong. Subdivision Surfaces in Character Animation. In SIGGRAPH '98: Proceedings of the 25th annual conference on Computer graphics and interactive techniques, pages 85--94, New York, NY, USA, 1998. ACM Press.
14. {DRS08} C. Dyken, M. Reimers, and J. Seland. Real-Time Gpu Silhouette Refinement Using Adaptively Blended Bezier Patches. In Computer Graphics Forum 27 (1), pages 1--12, 2008.
15. {DRSar} Christopher Dyken, Martin Reimers, and Johan Seland. Semi-Uniform Adaptive Patch Tessellation. Computer Graphics Forum, to appear.
16. {Far97} Gerald Farin. Curves and Surfaces for Computer-Aided Geometric Design: A Practical Guide. Academic Press, pub-ACADEMIC:adr, fourth edition, 1997.
17. {FH05} Michael S. Floater and Kai Hormann. Surface Parameterization: a Tutorial and Survey. pages 157--186, 2005.
18. {For03} Tom Forsyth. Practical Displacement Mapping. In Game Developers Conference, 2003.
19. {For06} Tom Forsyth. Linear-Speed Vertex Cache Optimization. 2006.
20. {JH08} Jin Ma Xinguo Liu Leif Kobbelt Hujun Bao Jin Huang, Muyang Zhang. Spectral Quadrangulation with Orientation and Alignment Control. SIGGRAPH Asia, 2008.
21. {KMDZ09} Denis Kovacs, Jason Mitchell, Shanon Drone, and Denis Zorin. Real-time Creased Approximate Subdivision Surfaces. In I3D '09: Proceedings of the 2009 Symposium on Interactive 3D Graphics and Games, pages 155--160, New York, NY, USA, 2009. ACM.
22. {KSG03} Vladislav Kraevoy, Alla Sheffer, and Craig Gotsman. Matchmaker: Constructing Constrained Texture Maps. 2003.
23. {LMH00} Aaron Lee, Henry Moreton, and Hugues Hoppe. Displaced Subdivision Surfaces. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 85--94, 2000.
24. {LS08} Charles Loop and Scott Schaefer. Approximating Catmull-Clark Subdivision Surfaces with Bicubic Patches. ACM Trans. Graph., 27(1):1--11, 2008.
25. {LSNC09} Charles Loop, Scott Schaefer, Tianyun Ni, and Ignacio Castaño. Approximating Subdivision Surfaces with Gregory Patches for Hardware Tessellation. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia), 28(5), 2009.
26. {LY06} Gang Lin and Thomas P. Y. Yu. An improved vertex caching scheme for 3d mesh rendering. IEEE Transactions on Visualization and Computer Graphics, 12(4):640--648, 2006.
27. {MC10} Matthias Mller and Nuttapong Chentanez. Wrinkle meshes. Eurographics / ACM SIGGRAPH Symposium on Computer Animation, 2010.
28. {MHAM08} Jacob Munkberg, Jon Hasselgren, and Tomas Akenine-Mller. Non-Uniform Fractional Tessellation. In ACM SIGGRAPH/Graphics Hardware 2008, 2008.
29. {MNP08} Ashish Myles, Tianyun Ni, and Jörg Peters. Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets. In Symposium on Geometry Processing, July 2--4, 2008, Copenhagen, Denmark, pages 1--8. Blackwell, 2008.
30. {Mor01} Henry Moreton. Watertight Tessellation Using Forward Differencing. In HWWS '01: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, pages 25--32, New York, NY, USA, 2001. ACM.
31. {NYM+08} Tianyun Ni, Young In Yeo, Ashish Myles, Vineet Goel, and Jörg Peters. GPU Smoothing of Quad Meshes. In IEEE International Conference on Shape Modeling and Applications, 2008.
32. {PB00} Dan Piponi and George Borshukov. Seamless Texture Mapping of Subdivision Surfaces by Model Pelting and Texture Blending. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 471--478, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.
33. {PCK04} Budirijanto Purnomo, Jonathan D. Cohen, and Subodh Kumar. Seamless Texture Atlases. In SGP '04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 65--74, New York, NY, USA, 2004. ACM.
34. {Pet08} Jörg Peters. PN-Quads. Technical Report 2008-421, Dept CISE, University of Florida, 2008.
35. {SJP05} Le-Jeng Shiue, Ian Jones, and J. Peters. A Realtime GPU Subdivision Kernel. In Marcus Gross, editor, Siggraph 2005, Computer Graphics Proceedings, Annual Conference Series, pages 1010--1015. ACM Press / ACM SIGGRAPH / Addison Wesley Longman, 2005.
36. {SNB07} Pedro V. Sander, Diego Nehab, and Joshua Barczak. Fast Triangle Reordering for Vertex Locality and Reduced Overdraw. ACM Trans. Graph., 26(3):89, 2007.
37. {SPR06} Alla Sheffer, Emil Praun, and Kenneth Rose. Mesh Parameterization Methods and Their Applications. Found. Trends. Comput. Graph. Vis., 2(2):105--171, 2006.
38. {Sta98} Jos Stam. Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values. In M. Cohen, editor, SIGGRAPH 98 Proceedings, pages 395--404. Addison Wesley, 1998.
39. {TACSD06} Y. Tong, P. Alliez, D. Cohen-Steiner, and M. Desbrun. Designing Quadrangulations with Discrete Harmonic Forms. Eurographics Symposium on Geometry Processing, 2006.
40. {Tat08} Andrei Tatarinov. Instanced Tessellation in Directx 10, 2008. GDC, http://developer.nvidia.com/object/gamefest-2008-subdiv.html.
41. {VPBM01} Alex Vlachos, Jörg Peters, Chas Boyd, and Jason Mitchell. Curved PN Triangles. In I3D 2001: Proceedings of the 2001 Symposium on Interactive 3D Graphics, pages 159--166, 2001.
42. {YNM+} Young In Yeo, Tianyun Ni, Ashish Myles, Vineet Goel, and Jörg Peters. Parallel Smoothing of Quad Meshes. The Visual Computer, pages x--x. accepted, in press, TVCJ-267.

Index Terms

• Applied computing

  • Computers in other domains

    • Personal computers and PC applications

• Computing methodologies

  • Computer graphics

    • Animation

    • Graphics systems and interfaces

    • Shape modeling

• Information systems

  • Information systems applications

    • Multimedia information systems

      • Massively multiplayer online games

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Virtual worlds software