The Bounding Mesh Algorithm

abstract

We present an algorithm to generate a one-sided approximation of a given triangular mesh. We refer to such an approximate mesh as a bounding mesh, which includes the original mesh and has fewer vertices. Likewise, an inner bounding mesh is defined as an approximate mesh that is included by a given mesh. Our proposed bounding mesh algorithm performs iterative edge contractions and can generate both types of approximation. Contrary to regular, two-sided mesh approximation, which is a well studied subject in computer graphics, our algorithm is novel and one of a handful approaches to one-sided mesh approximation. While we are the first to apply bounding meshes to safe collision detection, path planning, and robot motion planning, applications range further to computer geometry and computer graphics. The bounding mesh algorithm helps pre-processing complex geometries and increases the efficiency of existing geometric algorithms, especially those that search in a bounding volume hierarchy. It can speed up search, intersection and inclusion detection, as well as silhouette, clipping, and other operations, acting as an intermediate level of approximation between coarser bounding boxes or bounding spheres and the exact mesh. Furthermore, the bounding mesh algorithm combines well with approximate convex decomposition to generate a bounding set of convexes with very few vertices, which is an efficient data structure for intersection, distance and normal computation, as well as other geometric operations.