Rendering trimmed NURBS with adaptive forward differencing

ABSTRACT

Trimmed non-uniform rational B-splines have become a very useful surface representation form in the mechanical CAD industry. Previous rendering methods use the de Boor algorithm to evaluate the surface at equal increments in parameter space. This yields polygons which are then rendered. Alternatively the Oslo algorithm and Boehm's knot insertion algorithms are used in a subdivision approach. In this paper a new method is presented for rendering trimmed NURB surfaces of arbitrary order using the adaptive forward differencing (AFD) technique. This method extends the AFD technique to higher order, efficiently computes the basis matrix for each span, calculates the shading approximation functions for rational surfaces, and trims and image maps NURB surfaces. Trimming is accomplished by using AFD to scan convert the trimming curves in parameter space, thus producing the intersection points between the trim curves and an isoparametric curve across the surface. A winding rule is used to determine the regions bounded by the curve which are then rendered with AFD. The method is suitable for both hardware and software implementations, however, higher order surfaces require very high precision due to the forward difference nature of the algorithm.

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: Wolfgang Boehm, Inserting New Knots into B-Spline Curves, 12, pp. 199-201, Computer Aided Design, 1980.
• 3: Wolfgang Boehm, Efficient Evaluation of Splines, 33 , pp. 171-177, Computing, 1984.
• 4: Carl de Boor, On calculating with B-splines, 6, pp. 50- 62, Journal of Approximation Theory, 1972.
• 5: Edwin Catmull, A Subdivision Algorithm for Computer Display of Curved Surfaces, UTEC-CSe-74-133, University of Utah, Computer Science, 1974.
• 6: Elaine Cohen, Tom Lyche, and Richard Riesenfeld, Discrete B-Splines and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics, 14, Computer Graphics and Image Processing, October 1980.
• 7: Robert Cook, Patch Work, Tech. Memo 118, Computer Div., Lucasfilm Ltd., June 1985.
• 8: Robert L. Cook , Loren Carpenter , Edwin Catmull, The Reyes image rendering architecture, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.95-102, August 1987
• 9: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 10: E.T.Y. Lee, Efficient Evaluation of Splines, 329, pp. 365-371, Computing, 1982.
• 11: 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
• 12: T Lyche , K Morken, Making the Oslo algorithm more efficient, SIAM Journal on Numerical Analysis, v.23 n.3, p.663-675, June 1986 [doi>10.1137/0723042]
• 13: Hartmut Prautzsch, A Short Proof of the Oslo Algorithm, 1, Computer Aided Geometric Design, 1984.
• 14: 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
• 15: 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.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Design, Performance, Theory

Keywords:
B-splines, NURBS, adaptive forward differencing, graphics VLSI, image synthesis, parametric surfaces, shading