Realistic Rendering

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.

References

• 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, (1995)
• 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).