Boolean Operations on Surfel-Bounded Solids Using Programmable Graphics Hardware

Abstract

In this paper we present an algorithm to compute boolean operations on free-form solids bounded by surfels using programmable graphics hardware. The intersection, union and difference of two or more solids, is calculated on the GPU using vertex and fragment programs. First, we construct an inside-outside partitioning using 3-color grids and signed distance fields. Next, we use this partitioning to classify the surfels of both solids as inside or outside the other solid. For surfels close to the boundary of the other solid, we use the distance field and its gradient to define a clipping plane, which can be used to resample or clip the surfel. Our algorithm runs at interactive rates on consumer-level graphics hardware.