Our interest in this topic is about ray-tracing algorithms specialized
for NURBS surfaces. The basic problem in a ray-tracing surface algorithm
is the ray/patch intersection.
If the surface is trimmed, it follows a step to determine whether the
intersection point lies inside or outside a trimmed region using a 2D
Point Membership Classification algorithm.
During our research we have implemented and compared two methods for
ray/patch intersection and we proposed a new one; all these algorithms
are able in the xcrayt system. For more details about the
original methods and our proposal see the references in the following.
- Toth's algorithm is based on interval
Newton iteration. It works robustly on any parametric surface for which
bounds onto the surface and its first derivative can be obtained.
- Bezier Clipping
algorithm uses the convex-hull property in a powerful manner, by
determining parameter ranges which guarantee that they do not include points
of intersection. Bezier Clipping has the flavor of a geometrically based
interval Newton method, and thus may be categorized as partly a subdivision
based algorithm and partly a numerical method.
- Our proposal was called Toth speed.
It is a combination of the Toth and Bezier Clipping algorithms that
outperforms their performances.
The idea is to reduce the application of the interval Newton iterations of
the Toth method, trying to find the solution using a simple Newton,
in the knowledge that, if a solution exists, it is unique.
If this fails, an interval Newton iteration is applied.
Moreover, when the Toth algorithm is forced to use binary subdivision,
our method uses Bezier Clipping.
Realistic Rendering example (400x400, 38Kb).
Realistic Rendering example (800x800, 245Kb).
Our ray tracing implementation exploits a certain number of optimization
techniques in order to speed up performance,
such as subdividing a 3D scene into a uniform grid of voxels,
subdividing the NURBS surfaces
in rational Bezier patches, further subdividing each rational Bezier
patch until a given flat tolerance is reached and introducing a second level
of subdivision of the surface bounding boxes.
G.Casciola, S.Morigi, xcmodel: an aCADemic system,
Annali Universita` di Ferrara, Sez. VII - Sc.Mat.,
Supplemento al Vol.XLV (2000).
M.Marini, D.Grilli, Un algoritmo di ray-tracing per superfici spline
razionali, degree thesis in Computer Science, Univ. of Bologna,
S.Spagna, Analisi, sviluppo e applicazione di metodi di intersezione
per spline razionali, degree thesis in Computer Science,
Univ. of Bologna, (1998)
D.Toth, On ray tracing parametric surfaces,
Proceeding of SIGGRAPH'85, (1985). In Computer Graphics, 19 (1985) pp.171--179.
T.Nishita, T.W.Sederberg and M. Kakimoto,
Ray tracing trimmed rational surface patches, ACM Computer Graphics,
24 (1990), pp. 337--345.
A.S.Glassner, An Introduction to ray Tracing, Academic Press, (1989).