An accurate sampling-based method for approximating geometry

We present a sampling-based method for approximating the boundary of a geometry defined by various geometric operations. Based on a novel adaptive sampling condition, we first construct volumetric grids such that an error-minimizing point can be found in each cell to capture all the geometric objects inside the cell. We then construct a polygonal model from the grid. We guarantee the boundary approximation has the same topology as the exact surfaces, and the maximum approximation error from the exact surfaces is bounded by a user specified tolerance. Our method is robust and easy to implement. We have applied it in various applications such as remeshing of polygonal models, Boolean operations, and offsetting operations. We report experimental results on a variety of CAD models. (C) 2007 Elsevier Ltd. All rights reserved.