Sylvain Lazard, Inria - Loria, Nancy, France

visit sponsored by the Inria Equipe Associee Isa-McGill

Abstract : We present a new algorithm for computing a parametric representation of the intersection of two arbitrary implicit quadrics with rational coefficients. Our method is similar in spirit to the pencil method introduced by J. Levin (1976) for explicitly describing the intersection of two quadrics, but extends it in several directions. Combining results from the theory of quadratic forms, a projective formalism and new theorems relating the geometry of the intersection to properties of the discriminant of the pencil, we show how to obtain parametric representations that are both ``simple'' (the size of the coefficients is small) and ``as rational as possible'' (the size of the field extension in which the coefficients live is optimal in the worst case). Since computing the intersection of two surfaces is an important step in CSG-to-Brep (i.e., Constructive Solid Geometry -to- Boundary Representation) conversion, the output of our algorithm is well suited for the robust boundary evaluation of second-order CSG models.

Announcement Poster in PDF