Interval Assignment for Volumes with Holes

This paper presents a new technique for automatically detecting interval constraints for swept volumes with holes. The technique finds true volume constraints that are not necessarily imposed by the surfaces of the volume. A graphing algorithm finds independent, parallel paths of edges from source surfaces to target surfaces. The number of intervals on two paths between a given source and target surface must be equal; in general, the collection of paths determine a set of linear constraints. Linear programming techniques solve the interval assignment problem for the surface and volume constraints simultaneously