Rapid evaluation of Catmull-Clark subdivision surfaces

ABSTRACT

Using subdivision as a basic primitive for the construction of arbitrary topology, smooth, free-form surfaces is attractive for content destined for display on devices with greatly varying rendering performance. Subdivision naturally supports level of detail rendering and powerful compression algorithms. While the underlying algorithms are conceptually simple it is difficult to implement player engines which achieve optimal performance on modern CPUs such as the Intel Pentium family.In this paper we describe a novel table driven evaluation strategy for subdivision surfaces using as an example the scheme of Catmull and Clark. Cache conscious design and exploitation of SIMD instructions allows us to achieve nearly 100% FPU utilization in the inner loop and achieve a composite performance of 1.2 flop/cycle on the Intel PIII and 1.8 flop/cycle on the Intel P4 including all memory transfers. The algorithm supports tradeoffs between cache size and memory bus usage which we examine. A library which implements this engine is freely available from the authors.

REFERENCES

• 1: Henning Biermann , Adi Levin , Denis Zorin, Piecewise smooth subdivision surfaces with normal control, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.113-120, July 2000 [doi>10.1145/344779.344841]
• 2: Stephan Bischoff , Leif P. Kobbelt , Hans-Peter Seidel, Towards hardware implementation of loop subdivision, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.41-50, August 21-22, 2000, Interlaken, Switzerland [doi>10.1145/346876.346886]
• 3: BRICKHILL, D. Practical Implementation Techniques for Multi-Resolution Subdivision Surfaces. In Game Developers Conference, 2001.
• 4: CATMULL, E., AND CLARK, J. Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes. Computer Aided Design 10, 6 (1978), 350-355.
• 5: 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]
• 6: HAVEMANN, S. Interactive Rendering of Catmull/Clark Surfaces with Crease Edges. Tech. Rep. TUBSCG-2001-01, TU Braunschweig, 2001.
• 7: INTEL CORPORATION. C++ Class Libraries for SIMD Operations Reference Manual., 1997-1999.
• 8: INTEL CORPORATION. IA-32 Intel Architecture Software Developer's Manual, 1997-2001.
• 9: JUNKINS, S. Fast Triangle Neighbor Finding for Subdivision Surfaces. Tech. rep., Intel Architecture Labs, September 1999.
• 10: Andrei Khodakovsky , Peter Schröder , Wim Sweldens, Progressive geometry compression, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.271-278, July 2000 [doi>10.1145/344779.344922]
• 11: Sheue-Ling Lien , Michael Shantz , Vaughan Pratt, Adaptive forward differencing for rendering curves and surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.111-118, July 1987
• 12: LOOP, C. Smooth Subdivision Surfaces Based on Triangles. Master's thesis, University of Utah, Department of Mathematics, 1987.
• 13: MULLER, K., AND HAVEMANN, S. Subdivision Surface Tessellation on the Fly using a versatile Mesh Data Structure. Computer Graphics Forum 19, 3 (2000).
• 14: 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
• 15: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: Jos Stam, Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.395-404, July 1998 [doi>10.1145/280814.280945]
• 17: Lexing Ying , Denis Zorin, Nonmanifold subdivision, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 18: ZORIN, D., AND KRISTJANSSON, D. Evaluation of Piecewise Smooth Subdivision Surfaces. Visual Computer (2002).
• 19: ZORIN, D., AND SCHRODER, P., Eds. Subdivision for Modeling and Animation. Course Notes. ACM Siggraph, 2000.
• 20: 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]

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:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

General Terms:
Algorithms, Design