\documentstyle[IEEEtran]{article}
\begin{document}

\title{Efficient and Robust Ray Intersection}
\author{Ole Caprani, Lars Hvidegaard,
Mikkel Mortensen, and Thomas Schneider}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ }

\maketitle

\auffil{The authors are with the 
Computer Science Department,
Aarhus University, Denmark, email ocaprani@daimi.aau.dk.}

\maketitle


\section{Ray Intersection is Important for Computer Graphics}
The generation of ray traced images of a variety of surfaces play a 
central role in computer graphics. 

One of the central operations in 
ray tracing is the calculation of {\it intersections} 
between rays and surfaces.

\section{Ray Intersection as a Mathematical Problem}
In the case of implicitly given surfaces, the intersection problem can be 
formulated as that of finding the first non-negative root  of a single 
equation in one variable (i.e. a non-negative root closest to zero).

\section{Traditional Numerical Methods Can Lead to a Wrong Image} 
If traditional numerical methods are used for the root finding,
the resulting image may be very wrong: e.g., when the surface
is thin, the ray may ``miss'' the surface, and a possible result
is an image with background colour spots in the image of the surface. 

\section{Interval Methods Lead to a Robust (Guaranteed) Intersection
Detection}
To obtain
a safe (robust) intersection detection, an interval based bisection method
combined with a safe interval test for uniqueness ($F'(X)$ does not 
contain zero) has been 
used  to isolate the first root, and a traditional method such as Newton's
method has been 
used to refine the isolated root \cite{mit90}. 

\section{The New Method of Robust Ray Intersection}
In this paper, we apply
a variant of Hansen's globally convergent method for computing and bounding 
all the roots of a single equation \cite{hansen}. Hansen's method has 
been modified as follows:
instead of searching for all roots, a recursive depth-first search is
carried out to obtain the first non-negative root. 

\section{The New Method Is More Efficient}
It is found that this 
variant of Hansen's method is a more efficient method for isolation of
the first root  when compared to simple 
interval based bisection. 

Furthermore, even if the first 
root is safely isolated, the traditional Newton method may
diverge or fail to converge to the first root. This problem is
avoided in  the described variant of Hansen's method. 

\begin{thebibliography}{99}


\bibitem{mit90}
Don P. Mitchell,
``Robust Ray Intersection with Interval Arithmetic'', 
{\it Proceedings of Graphics Interface '90}, May 1990, pp. 68--74.

\bibitem{hansen}
E. Hansen, 
``Globally Convergent Interval Method for Computing and Bounding 
Real Roots'',
{\it BIT}, 1978, Vol. 18, pp. 415--424.


\end{thebibliography}

\end{document}