ICS Theory Group

ICS 269, Winter 1997: Theory Seminar

14 Feb 1997:
Surface/Surface Intersection '97
Mac Casale, ICS, UC Irvine

In high-school algebra, it is common to learn how to intersect two geometric objects (starting with straight lines) that are described by algebraic equations (e.g., y =  mx + b). In freshman calculus, the concept is extended to vector functions of a parameter. In both courses, some kind of substitution method is usually used. If a student goes further, he/she finds that substition methods had been extended long ago, under the name of elimination theory, to a high level of sophistication. (See the famous Theory of Equations, by J. V. Uspensky, McGraw Hill 1948). It may therefore come as a surprise that surface/surface intersection is still undergoing considerable research in the domain of Computer Aided Geometric Design.

In this paper, we will present the progress in algorithms that have been applied to intersecting two surfaces embedded in R3, with varying degree of success. It will be shown that this algorithm, which is central to the robustness of modern CAD systems, is inherently hard, not from the point of view time or space complexity but due to

  1. The chaotic nature of the requisite non-linear numerical methods, and
  2. The rich topology of intersection curves among intersecting surfaces that occur in real world problems.

Practical, state-of-the-art methods for overcoming these difficulties will be presented.