Watertight tessellation using forward differencing

ABSTRACT

In this paper we describe an algorithm and hardware for the tessellation of polynomial surfaces. While conventional forward difference-based tessellation is subject to round off error and cracking, our algorithm produces a bit-for-bit consistent triangle mesh across multiple independently tessellated patches. We present tessellation patterns that exploit the efficiency of iterative evaluation techniques while delivering a defect free adaptive tessellation with continuous level-of-detail. We also report the rendering performance of the resulting physical hardware implementation.

REFERENCES

• 1: 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]
• 2: J. Bruijns, Quadratic Bezier triangles as drawing primitives, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.15-ff., August 31-September 01, 1998, Lisbon, Portugal [doi>10.1145/285305.285307]
• 3: Edwin E. Catmull. Computer Display of Curved Surfaces. Proceedings of the IEEE Conference on Computer Graphics, Pattern Recognition, and Data Structure, pages 11- 17 (May 1975).
• 4: James H. Clark, A fast scan-line algorithm for rendering parametric surfaces, ACM SIGGRAPH Computer Graphics, v.13 n.2, p.174, August 1979
• 5: G. Farin, Curves and surfaces for computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1990
• 6: R. T. Farouki , V. T. Rajan, Algorithms for polynomials in Bernstein form, Computer Aided Geometric Design, v.5 n.1, p.1-26, June 1988 [doi>10.1016/0167-8396(88)90016-7]
• 7: Tim Heidmann. Real Shadows, Real Time, Iris Universe, No. 18, pp 23-31, Silicon Graphics Inc., November 1991.
• 8: D. Hilbert and S. Cohn-Vossen. Geometry and the Imagination. Chelsea Publishing Company, New York, 1952.
• 9: James T. Kajiya, Ray tracing parametric patches, Proceedings of the 9th annual conference on Computer graphics and interactive techniques, p.245-254, July 26-30, 1982, Boston, Massachusetts, United States
• 10: Subodh Kumar , Dinesh Manocha , Anselmo Lastra, Interactive display of large-scale NURBS models, Proceedings of the 1995 symposium on Interactive 3D graphics, p.51-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199413]
• 11: Jeffrey M. Lane , Loren C. Carpenter , Turner Whitted , James F. Blinn, Scan line methods for displaying parametrically defined surfaces, Communications of the ACM, v.23 n.1, p.23-34, Jan. 1980 [doi>10.1145/358808.358815]
• 12: 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
• 13: Dani Lischinski, Converting Be´zier triangles into rectangular patches, Graphics Gems III, Academic Press Professional, Inc., San Diego, CA, 1992
• 14: Wayne Liu , Stephen Mann, An optimal algorithm for expanding the composition of polynomials, ACM Transactions on Graphics (TOG), v.16 n.2, p.155-178, April 1997 [doi>10.1145/248210.248221]
• 15: Charles T. Loop. Smooth Subdivision Surfaces Based on Triangles. Master's thesis, University of Utah, Department of Mathematics, 1987.
• 16: NVIDIA OpenGL Extension Specifications, NVIDIA Corporation, March 1, 2001. http://www.nvidia.com/ marketing/developer/devrel.nsf/oglFrame?OpenPage
• 17: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 18: Ron Pulleyblank , John Kapenga, The feasibility of a VLSI chip for ray tracing bicubic patches, IEEE Computer Graphics and Applications, v.7 n.3, p.33-44, March 1987 [doi>10.1109/MCG.1987.276963]
• 19: 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
• 20: Alyn P. Rockwood, Generalized scanning technique for display of parametrically defined surfaces, IEEE Computer Graphics and Applications, v.7 n.9, p.15-26, Aug. 1987
• 21: Alyn Rockwood , Kurt Heaton , Tom Davis, Real-time rendering of trimmed surfaces, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.107-116, July 1989
• 22: Mark Segal and Kurt Akeley. The OpenGL Graphics System: A Specification (Version 1.2.1). www.opengl.org.
• 23: Alex Vlachos , Jörg Peters , Chas Boyd , Jason L. Mitchell, Curved PN triangles, Proceedings of the 2001 symposium on Interactive 3D graphics, p.159-166, March 2001 [doi>10.1145/364338.364387]

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.1 Hardware architecture
          Subjects: Graphics processors

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
CAD, curves & surfaces, geometric modeling, graphics hardware, hardware systems, rendering hardware