A new method for speeding up ray tracing nurbs surfaces

Abstract

In this paper, a new method for computing the intersection of a ray and a NURBS surface is presented. The method is based on Newton iteration for a system of nonlinear equations, but its convergence is accelerated by using the polynomial extrapolation. Additionally, a ray is defined to be the intersection of two planes, which are usually non-orthogonal, so that theoperations are significantly reduced. A trapezoid prism is adopted for the bounding box enclosing the patch as tightly as possible. It can be used both for getting a good start point for the Newton iteration and for efficiently detecting whether a ray intersects a patch. The method proposed for speeding up ray tracing NURBS surfaces can reduce both the iteration steps and arithmetic operations, thus much CPU time is saved. The new method is faster than the previous methods for which published performance data allow reliable comparison. The acceleration techniques with extrapolation presented for solution to a system of nonlinear equations can also be used to speed up tracing the intersection of two parametric surfaces as well as others that need Newton iteration. © 1997 Elsevier Science Ltd. All rights reserved.