JISE Vol.18 No.4 #6

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Journal of Information Science and Engineering, Vol.18 No.4, pp.541-561 (July 2002)

An Efficient and Stable Ray Trancing Algorithm
for Parametric Surfaces

Shyue-Wu Wang^*, Zen-Chung Shih^*
and Ruei-Chuan Chang^*+
Department of Computer and Information Science
^*Department of Computer and Information Science
National Chiao Tung University
Hsinchu, 300 Taiwan
⁺Institute of Information Science
Academia Sinica
Taipei, 115 Taiwan

In this paper, we propose an efficient and stable algorithm for finding the ray-surface intersections. Newton’s method and B?zier clipping are adapted to form the core of our algorithm. Ray coherence is used to find starting points for Newton iteration. We introduce an obstruction detection technique to verify whether an intersection point found by using Newton’s method is the closest one. When Newton’s method fails to achieve convergence, we use B?zier clipping as the substitution to find the intersection points. This combination achieves significant improvement in tracing primary rays. A similar approach also successfully improves the performance in tracing secondary rays.

Keywords: ray tracing, Newton’s method, B?zier clipping, parametric surfaces, ray coherence, B?zier surface

Retrieve PDF document (200207_06.pdf)

Received December 6, 1999; revised May 22, 2000; accepted November 16, 2000.
Communicated by Tomoyuki Nishita.