A NEW INTERSECTION ALGORITHM FOR CYCLIDES AND SWEPT SURFACES USING CIRCLE DECOMPOSITION

The present vocabulary of a solid modeler is canonically the plane, (some subset of) the quadrics, and the torus. The class of cyclides is also becoming important. Quadrics and cyclides lie in the more general class of ringed surfaces: surfaces that can be swept out by a circle. This class also contains the important class of revolute surfaces. We will present a method for the exact intersection of any ringed surface with any quadric or cyclide. This algorithm shows that it is feasible to expand the vocabulary of solid modeling primitives to include all ringed surfaces. In solid modeling, surface intersection is crucial to the design of solids and their subsequent analysis. Our intersection algorithm is exact: that is, the intersection is computed symbolically rather than numerically. For exact intersection, we must reduce to degree-4 computations. We do this by concentrating on the decomposition of a surface into simpler components. Previous algorithmic development has centered around the degree of an algebraic surface. Two keys to our algorithm are circle decomposition and inversion. Solutions are provided for the inversion of a cyclide to a torus, a torus, a torus to a cyclide, and the inversion of any circle.