projects

Approximate Boolean Operations for Subdivision Surfaces

Subdivision representations of surfaces are convenient for many common tasks such as rendering, topology-preserving editing and simulation.

However, some important editing operations modify the topology of surfaces, for example, computing a union, intersection or difference of solids represented by closed surfaces. In general, it is impossible to represent the resulting surface as a subdivision surface precisely. Nevertheless, it is possible to find a subdivision surface which approximates the result sufficiently well. This approach is attractive for computer graphics applications, as high accuracy is often less important than high efficiency.

In this talk, we describe how to approximate the result of a boolean operation applied to a pair of solids represented by closed subdivision surfaces. We present algorithms for generating a control mesh for a subdivision surface approximating the result, and for fitting the surface defined on the new mesh to the geometry of the original surfaces.

Our algorithms aim to minimize the size of the new control mesh, and to control the valence of the newly created vertices. All algorithms are quite fast as they modify the control meshes only in a neighborhood of the intersection. Our algorithms can be applied to subdivision-based multiresolution surfaces, for which it is possible to trade performance for accuracy of the approximation.

Presentation

H. Biermann, D. Kristjansson, D. Zorin. Approximate Boolean operations for subdivision surfaces. CAGD 2000. Oslo, Norway. June 29 - July 4, 2000.

SIGGRAPH 2001 Paper:

H. Biermann, D. Kristjansson, D. Zorin. Approximate Boolean operations on Free-Form Solids.

Examples

Many important modeling operations can be expressed as boolean operations on closed solids. The top row shows two free-from solids. We combine both solids using Boolean operations to obtain the surfaces of the bottom row: green minus red, green and red, red minus green, red or green.

Boolean operations may change the surface topology. This example shows how one can drill a hole by subtracting two solids:

Our algorithms proceed in three main stages: remeshing, parameterization and fitting. The steps in detail: (1) intersection, (2) intersection curve in parameter space, (3) trimming, (4) parameter optimization, (5) fitting.