Abstract

Robust implementations of the Boolean operation on boundary representations of shapes are highly problematic when the computations are based on inexact machine arithmetic. The arithmetic computations required can yield inconsistencies in the results, hindering the possibility of creating a topologically correct boundary. These difficulties are compounded by the fact that most operations perturb the boundary, which can lead to geometric errors such as boundary self-intersections.

I present a topologically robust Boolean algorithm for polygonal/polyhedral shapes. It is based on a hierarchy of interdependent operations guaranteed to yield consistency in the intermediate results. Hence, the algorithm provably always generates a topologically correct final result from topologically correct input, irrespective of the extent of any numerical rounding. The algorithm is tolerant to geometric errors, but does not resolve them. For the result to be acceptable to end-users, it is generally desirable to apply a smoothing post-process to remove marginal gaps, slivers and overlaps. I go on to discuss my present work, which concerns how to devise a robust algorithm for resolving geometric errors in a (topologically correct) shape representation. I discuss both algorithms in the context of the requirements for a robust approximate algorithm.