Dinesh Manocha and James W. Demmel

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-698
August 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-698.pdf

The problem of computing the intersection of parametric and algebraic curves arises in many applications of computer graphics, geometric and solid modeling. Previous algorithms are based on techniques from Elimination theory or subdivision and iteration. The former is however, restricted to low degree curves. This is mainly due to issues of efficiency and numerical stability. In this paper we use Elimination theory and express the resultant of the equations of intersection as a matrix determinant. The matrix itself rather than its symbolic determinant, a polynomial, is used as the representation. The algorithm for intersection corresponds to substituting the other equation to construct an equivalent matrix such that the intersection points can be extracted from the eigenvalues and eigenvectors of the latter. Moreover, the algebraic and geometric multiplicities of the eigenvalues give us information about the intersection (multiplicity, tangential intersection etc.). As a result we are able to accurately compute higher order intersections in most cases. The main advantage of this approach lies in its efficiency and robustness. Moreover, the numerical accuracy of these operations is well understood. For almost all cases we are able to compute accurate answers in 64 bit IEEE floating point arithmetic.

BibTeX citation:

@techreport{Manocha:CSD-92-698,
    Author = {Manocha, Dinesh and Demmel, James W.},
    Title = {Algorithms for Intersecting Parametric and Algebraic Curves},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1992},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6266.html},
    Number = {UCB/CSD-92-698},
    Abstract = {The problem of computing the intersection of parametric and algebraic curves arises in many applications of computer graphics, geometric and solid modeling. Previous algorithms are based on techniques from Elimination theory or subdivision and iteration. The former is however, restricted to low degree curves. This is mainly due to issues of efficiency and numerical stability. In this paper we use Elimination theory and express the resultant of the equations of intersection as a matrix determinant. The matrix itself rather than its symbolic determinant, a polynomial, is used as the representation. The algorithm for intersection corresponds to substituting the other equation to construct an equivalent matrix such that the intersection points can be extracted from the eigenvalues and eigenvectors of the latter. Moreover, the algebraic and geometric multiplicities of the eigenvalues give us information about the intersection (multiplicity, tangential intersection etc.).  As a result we are able to accurately compute higher order intersections in most cases. The main advantage of this approach lies in its efficiency and robustness. Moreover, the numerical accuracy of these operations is well understood. For almost all cases we are able to compute accurate answers in 64 bit IEEE floating point arithmetic.}
}

EndNote citation:

%0 Report
%A Manocha, Dinesh
%A Demmel, James W.
%T Algorithms for Intersecting Parametric and Algebraic Curves
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-698
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6266.html
%F Manocha:CSD-92-698