“Rendering trimmed NURBS with adaptive forward differencing” by Shantz and Chang

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.

1. Richard Barrels, John Beatty, and Brian Barsky, An Introduction to Splines for use in Computer Graphics and Geometric Modeling, Morgan Kaufmann Publishers, 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 Cook, Loren Carpenter, and Edwin Catmull, The Reyes Image Rendering Architecture, SIG- GRAPH’87 Proceedings, July 1987.
9. James Foley and Andries Van Dam, Fundamentals of Interactive Computer Graphics, p. 533, Addison- Wesley Publishers, 1982.
10. E.T.Y. Lee, Efficient Evaluation of Splines, 329, pp. 365-371, Computing, 1982.
11. Sheue-Ling Lien, Michael Shantz, and Vaughan Pratt, Adaptive Forward Differencing for Rendering Curves and Surfaces, SIGGRAPH’87 Proceedings, July 1987.
12. Tom Lyche and Knut Morken, Making the Oslo Algorithm More Efficient, 23, pp. 663-675, SIAM J. Numer. Anal, 1986.
13. Hartmut Prautzsch, A Short Proof of the Oslo Algorithm, 1, Computer Aided Geometric Design, 1984.
14. Alyn Rockwood, A Generalized Scanning Technique for Display of Parametrically Defined Surfaces, 7, IEEE CG&A, August 1987.
15. Michael Shantz and Sheue-Ling Lien, Shading Bicubic Patches, SIGGRAPH’87 proceedings, July 1987.