A Robust and Consistent Algorithm for Intersecting Convex Polyhedra

Abstract

This paper presents a numerically robust and topologically consistent algorithm for intersecting convex polyhedra. This algorithm is new in the sense that the consistency issue is completely separated from the numerical error issue. The intersection operation is combinatorially abstracted as the operation of changing the vertex-edge graphs associated with the input polyhedra, and numerical computation is employed only for choosing the branch of processing which is most likely to lead to the correct solution of the problem. Hence, the resultant algorithm is completely free from topological inconsistency.