Interactive display of large-scale NURBS models

ABSTRACT

We present serial and parallel algorithms for interactive rendering of large scale and complex NURBS models on current graphics systems. The algorithms tessellate the NURBS surfaces into triangles and render them using triangle rendering engines. The main characteristics of the algorithms are improved polygonization algorithms, exploitation of spatial and temporal coherence and back-patch culling. Polygonization anomalies like cracks and angularities are avoided. We analyze a number of issues in parallelization of these techniques, as well. The algorithms work well in practice and are able to display models consisting of thousands of surfaces at interactive frame rates on the highly parallel graphics system, Pixel-Planes 5.

REFERENCES

• 1: S.S. Abi-Ezzi and L.A. Shirman. Tessellation of curved surfaces under highly varying transformations. Proceedings of Eurographics '91 1 pages 385-97, 1991.
• 2: Salim A. Abi-Ezzi , Leon A. Shirman, The Scaling Behavior of Viewing Transformations, IEEE Computer Graphics and Applications, v.13 n.3, p.48-54, May 1993 [doi>10.1109/38.210491]
• 3: Kurt Akeley, Reality Engine graphics, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.109-116, September 1993 [doi>10.1145/166117.166131]
• 4: Chandrajit L. Bajaj , Andrew Royappa, Triangulation and display of rational parametric surfaces, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
• 5: David Banks, Interactive manipulation and display of surfaces in four dimensions, Proceedings of the 1992 symposium on Interactive 3D graphics, p.197-207, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147205]
• 6: Edwin Earl Catmull, A subdivision algorithm for computer display of curved surfaces., 1974
• 7: J. H. Cla:rk. A fast algorithm for rendering parametric surfaces. Proceedings of ACM Siggmph, pages 289-99, 1979.
• 8: Michael F. Deering , Scott R. Nelson, Leo: a system for cost effective 3D shaded graphics, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.101-108, September 1993 [doi>10.1145/166117.166130]
• 9: David Ellsworth , Howard Good , Brice Tebbs, Distributing display lists on a multicomputer, Proceedings of the 1990 symposium on Interactive 3D graphics, p.147-154, February 1990, Snowbird, Utah, United States
• 10: T. Derose et. al. Apex: two architectures for generating pars metric curves and surfaces. The Visual Computer, 5:264--276, 1989.
• 11: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 12: Daniel Filip , Robert Magedson , Robert Markot, Surface algorithms using bounds on derivatives, Computer Aided Geometric Design, v.3 n.4, p.295-311, 1987 [doi>10.1016/0167-8396(86)90005-1]
• 13: D. R. Forsey , R. V. Klassen, An adaptive subdivision algorithm for crack prevention in the display of parametric surfaces, Proceedings on Graphics interface '90, p.1-8, June 1990, Halifax, Nova Scotia
• 14: Henry Fuchs , John Poulton , John Eyles , Trey Greer , Jack Goldfeather , David Ellsworth , Steve Molnar , Greg Turk , Brice Tebbs , Laura Israel, Pixel-planes 5: a heterogeneous multiprocessor graphics system using processor-enhanced memories, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.79-88, July 1989
• 15: James T. Kajiya, Ray tracing parametric patches, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.245-254, July 1982
• 16: Shankar Krishnan , Dinesh Manocha, Hidden Surface Removal Algorithms for Curved Surfaces, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1994
• 17: S. Kumar and D. Manocha. Efficient rendering of trimmed nurbs surfaces. Computer-rlided Design, 1994. to appear.
• 18: 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]
• 19: J.M. Lane and R.F. Riesenfeld. Bounds on polynomials. .BIT, 2:112-117,198j.
• 20: W.L. Luken and Fuhua Cheng. Rendering trimmed nurb surfaces. Computer science research report 18669(81711), IBM Research Division, 1993.
• 21: Dinesh Manocha , James Demmel, Algorithms for intersecting parametric and algebraic curves I: simple intersections, ACM Transactions on Graphics (TOG), v.13 n.1, p.73-100, Jan. 1994 [doi>10.1145/174462.174617]
• 22: R. Nzh. Silicon Graphics, Personal Communication, 1993.
• 23: 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
• 24: 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
• 25: T. W. Sederberg, Algorithm for algebraic curve intersection, Computer-Aided Design, v.21 n.9, p.547-554, Nov. 1989 [doi>10.1016/0010-4485(89)90015-8]
• 26: Micheal Shantz , Sheue-Ling Chang, Rendering trimmed NURBS with adaptive forward differencing, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.189-198, June 1988
• 27: Michael Shantz , Sheue-Ling Lien, Shading bicubic patches, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.189-196, August 1987

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Parallel processing
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Geometric algorithms, languages, and systems

General Terms:
Algorithms, Performance