EFFICIENT RAY-TRACING FOR BEZIER AND B-SPLINE SURFACES

Generating realistic pictures by ray tracing requires intersecting the objects with many rays (1 million or more). With Bezier or B-spline s urfaces as objects the intersections must be calculated by an iterativ e method. This paper describes an algorithm that performs these calcul ations efficiently. In a preprocessing step, the surface is subdivided adaptively into parts and a tight enclosure is calculated for each pa rt. We selected parallelepipeds (first order approximations) as enclos ures, their orientation and the angles between their edges are chosen in such a way that they enclose the respective part as tightly as poss ible, they are not rectangular in general. A binary tree built with th ese enclosures allows us to test very fast which parts of the surface may be hit by a given ray. The leaves ofthe tree contain small, almost plane parts of the surface. For each part a linear approximation is c alculated, this is a parallelogram, in general not rectangular. For ea ch ray that hits the enclosure the intersection with this approximatio n is calculated first, yielding an accurate starting point for the fol lowing iteration.