Towards hardware implementation of loop subdivision

ABSTRACT

We present a novel algorithm to evaluate and render Loop subdivision surfaces. The algorithm exploits the fact that Loop subdivision surfaces are piecewise polynomial and uses the forward difference technique for efficiently computing uniform samples on the limit surface. The main advantage of our algorithm is that it only requires a small and constant amount of memory that does not depend on the subdivision depth. The simple structure of the algorithm enables a scalable degree of hardware implementation. By low-level parallelization of the computations, we can reduce the critical computations costs to a theoretical minimum of about one float [3]-operation per triangle.

REFERENCES

• 1: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 2: 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]
• 3: E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 10:350-355, September 1978.
• 4: S.-L. Chang , M. S. R. Rocchetti, Rendering cubic curves and surfaces with integer adaptive forward differencing, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.157-166, July 1989
• 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: D. Doo and M. Sabin. Behaviour of recursive division surfaces near extraordinary points. Computer-Aided Design, 10:356-360, September 1978.
• 7: Denis Zorin et. al. Subdivision for modeling and animation. In SIGGRAPH 99 Course Notes, 1999.
• 8: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 9: Markus Kohler and Heinrich Muller. Efficient calculation of subdivision surfaces for visualization. Technical Report 585, University of Dortmund, 1995.
• 10: Sheue-Ling Lien , Michael Shantz , Vaughan Pratt, Adaptive forward differencing for rendering curves and surfaces, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.111-118, August 1987
• 11: Charles T. Loop. Smooth subdivision surfaces based on triangles. Master's thesis, University of Utah, Department of Mathematics, 1987.
• 12: Kerstin Muller and Sven Havemann. Subdivision surface tesselation on the fly using a versatile mesh data strucure. Computer Graphics Forum, Eurographics 2000 issue.
• 13: Ahmad H. Nasri, Polyhedral subdivision methods for free-form surfaces, ACM Transactions on Graphics (TOG), v.6 n.1, p.29-73, Jan. 1987 [doi>10.1145/27625.27628]
• 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: Ulrich Reif, A unified approach to subdivision algorithms near extraordinary vertices, Computer Aided Geometric Design, v.12 n.2, p.153-174, March 1995 [doi>10.1016/0167-8396(94)00007-F]
• 16: Michael Spivak. A comprehensive introduction to differential geometry. Publish or Perish, Inc., 1979.
• 17: 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]
• 18: Denis Zorin. C - Continuity of Subdivision Surfaces. PhD thesis, California Institute of Technology, Department of Computer Sciences, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
forward differences, hardware implementation, rendering, subdivision surfaces