Comparison of surface and derivative evaluation methods for the rendering of NURB surfaces

ABSTRACT

Three methods for evaluating the surface coordinates, first derivatives, and normal vectors of a NURB surface are compared. These methods include forward differencing, knot insertion, and a tow-stage Cox-de Boor technique. The computational complexity of each of these techniques is analyzed and summarized. The use of Hermite functions is shown to yield a poor approximation for the shading functions of a NURB surface. An improved method for computing derivatives by knot insertion is presented. An efficient algorithm for computing the foward difference matrix and a method for using foward differencing to compute the first derivatives of a NURB surface are also presented.

REFERENCES

• 1: CHENG, F. AND LUKEN, W.L. 1992. Computing step sizes for the tessellation of trimmed NURB surfaces. IBM Rep. RC18499.
• 2: BOEHM, W. 1984. Efficient evaluation of splines. Computing 33, 171-177.
• 3: BOEHM, W. 1980. Inserting New Knots into B-spline Curves. Comput. Aided Des. 12, 199-201.
• 4: DE BOOR, C. 1972. On calculating with B-splines. J. Approx. Theory 6, 50-62.
• 5: Cox, M.G. 1972. The Numerical Evaluation of B-splines. J. Inst. Math. Appl. 10, 134-149.
• 6: R. T. Farouki, On the stability of transformations between power and Bernstein polynomial forms, Computer Aided Geometric Design, v.8 n.1, p.29-36, Feb. 1991 [doi>10.1016/0167-8396(91)90047-F]
• 7: R. T. Farouki , V. T. Rajan, On the numerical condition of polynomials in Berstein form, Computer Aided Geometric Design, v.4 n.3, p.191-216, Nov., 1987 [doi>10.1016/0167-8396(87)90012-4]
• 8: LEE, E. T.Y. 1982. A simplified B-spline computation routine. Computing 329, 365-373.
• 9: 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
• 10: William L. Luken, Tessellation of trimmed NURB surfaces, Computer Aided Geometric Design, v.13 n.2, p.163-177, March 1996 [doi>10.1016/0167-8396(95)00019-4]
• 11: LUKEN, W. L. AND CHENG, F. 1993. Rendering trimmed NURB surfaces. IBM Rep. RC18669.
• 12: Tomoyuki Nishita , Thomas W. Sederberg , Masanori Kakimoto, Ray tracing trimmed rational surface patches, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.337-345, Aug. 1990
• 13: 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
• 14: Alyn Rockwood , Kurt Heaton , Tom Davis, Real-time rendering of trimmed surfaces, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.107-116, July 1989
• 15: Micheal Shantz , Sheue-Ling Chang, Rendering trimmed NURBS with adaptive forward differencing, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.189-198, Aug. 1988
• 16: SHENG, X. AND HIRSCH, B.E. 1992. Triangulation of trimmed surfaces in parametric space. Comput. Aided Geom. Des. 24, 8, 437-444.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.4 Graphics Utilities
          Subjects: Software support
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Algorithms, Performance, Verification

Keywords:
B-spline, Cox-de boor algorithm, Hermite interpolation, NURBS, forward differencing, knot insertion, shading model, surface rendering