A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic

Julian M. Smith

doi:10.1016/j.cad.2006.11.003

A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic

2007-02-01

24

PRE

AI

DOI：10.1016/j.cad.2006.11.003

Original

Original request for help

Save

Abstract

En 中文

We present a topologically robust algorithm for Boolean operations on polyhedral boundary models. The algorithm can be proved always to generate a result with valid connectivity if the input shape representations have valid connectivity, irrespective of the type of arithmetic used or the extent of numerical errors in the computations or input data. The main part of the algorithm is based on a series of interdependent operations. The relationship between these operations ensures a consistency in the intermediate results that guarantees correct connectivity in the final result. Either a triangle mesh or polygon mesh can be used. Although the basic algorithm may generate geometric artifacts, principally gaps and slivers, a data smoothing post-process can be applied to the result to remove such artifacts, thereby making the combined process a practical and reliable way of performing Boolean operations. (C) 2006 Elsevier Ltd. All rights reserved.

Keywords:

Boolean operations

boundary mesh representations

robustness

A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic

Abstract

Journal

Organization