A Resultant-Based Algorithm for Ray Intersection

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Department of Computer Science, 4130 Upson Hall, Cornell University, Ithaca, NY 14853
vavasis@cs.cornell.edu

Abstract
A subroutine important for many mesh generation algorithms is the computation of the point(s) where a ray crosses a parametric patch. This problem can be formulated as solving a system of polynomial equations in two variables with moderate degree. In some uses of this subroutine (such as in a point-in-brep test), it is crucial to robustly detect all crossing points. Therefore, a standard numerical technique like Newton's method by itself is not sufficient for this problem.

We propose an algorithm based on a Macaulay's resultant combined with a u-resultant technique. Macaulay and u-resultant algorithms have been proposed in the literature recently by a number of authors including Canny, Demmel, Emiris, Mourrain, and Manocha. These authors suggest solving the resultant using a generalized eigenvalue routine. We modify previous resultant-based algorithms in two ways. First, we develop a new technique for selecting the monomials that weight the rows. Second, we propose a perturbation scheme to handle certain degenerate cases that arise often in mesh generation, such as a patch whose leading coefficents vanish (e.g., a Bezier cubic triangle that happens to be linear). This algorithm is currently implemented (using LAPACK routine dgegv for finding generalized eigenvalues) in the QMG 2.0 mesh generator and appears to be quite robust. Some numerical stability analysis of the new algorithm will also be presented.

Part of this talk represents joint work with Gudbjorn Jonsson of Cornell.