User-Assisted Sphere-Mesh Construction

In this study, we investigate the semi-automated generation of sphere-meshes as high-quality approximations for given three-dimensional shapes, originally represented as common triangular meshes. A sphere-mesh is a class of geometric proxy defined as the volume swept by spheres with linearly interpolated centers and radii, that potentially strikes a good balance between conciseness of representation, simplicity of spatial queries, and expressive power, and is amenable to animations. Despite these favorable characteristics, its broader adoption in applications such as video games, physical simulation, or robotics is hindered by the difficulty of its construction, which remains an open problem. Existing fully automatic algorithms, based on interactive coarsening of the input mesh, fail to consistently produce satisfactory results, especially when very coarse sphere-meshes are sought. We improve on this situation with a 3D interface specifically designed to permit users to easily and intuitively modify the automatically generated models. The two phases (existing automatic algorithm and novel interactive tool), used in cascade, constitute a viable semi-automatic way to produce sphere-meshes. We test our method on several inputs tri-meshes, assess their quality, and finally experiment with a few downstream applications to exemplify the usability of our results.