The Bounding Mesh Algorithm The Bounding Mesh Algorithm

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 ap-proximation. 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 plan-ning, 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 intermedi-ate level of approximation between coarser bounding boxes or bounding spheres and the exact mesh. Furthermore, the bounding mesh algorithm combines well with ap-proximate 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.