Exploiting topological and geometric properties for selective subdivision

Abstract

This paper presents a theorem relating the geometry of two smooth surfaces with the topology of their intersection. Algorithms for computing intersections of surfaces are very basic to those solid-modeling systems that allow Boolean operations such as Union, Intersection, and Subtraction on solids. Recently, such an algorithm based on recursive subdivision of the surfaces has attracted a lot of attention because of its simplicity and wide applicability. However, this algorithm for intersection of surfaces fails to find all intersections for certain relative orientations of surfaces. Finer subdivision of the surfaces may result in the correct intersections but also results in many unnecessary computations. The mathematical result established in this paper is significant in that it provides a check to determine when finer subdivision will yield no new topological information for an intersection. It is shown how the check may be incorporated into the existing subdivision algorithm to compute intersections reliably and efficiently.