Automatic and User-Assisted Sphere-Mesh Construction

A sphere-mesh is a class of geometric proxies defined as the volume swept by spheres with linearly interpolated centers and radii, potentially striking a good balance between conciseness of representation, simplicity of spatial queries, and expressive power. We investigate the semiautomatic generation of sphere-meshes from standard triangular meshes. We improve one known automatic construction algorithm, based on iterative local coarsening operation, by introducing a mechanism to prevent operations that would result in spheres exceeding the target shape; then, we propose a 3-D interface designed to permit users to easily and intuitively modify the automatically generated sphere-meshes. The two phases, an improved automatic algorithm and a novel interactive tool, used in cascade, constitute a viable semiautomatic way to produce high-quality sphere-meshes. We test our method on several inputs tri-meshes, assess their quality, and finally exemplify the usability of our results by testing them in a few downstream applications.