Computing Medial Axis Transform with Feature Preservation via Restricted Power Diagram

ACM Transactions on Graphics (SIGGRAPH Asia 2022)

Abstract

We propose a novel framework for computing the medial axis transform of 3D shapes while preserving their medial features via restricted power diagram (RPD). Medial features, including external features such as the sharp edges and corners of the input mesh surface and internal features such as the seams and junctions of medial axis, are important shape descriptors both topologically and geometrically. However, existing medial axis approximation methods fail to capture and preserve them due to the fundamentally under-sampling in the vicinity of medial features, and the difficulty to build their correct connections. In this paper we use the RPD of medial spheres and its affiliated structures to help solve these challenges. The dual structure of RPD provides the connectivity of medial spheres. The surface restricted power cell (RPC) of each medial sphere provides the tangential surface regions that these spheres have contact with. The connected components (CC) of surface RPC give us the classification of each sphere, to be on a medial sheet, a seam, or a junction. They allow us to detect insufficient sphere sampling around medial features and develop necessary conditions to preserve them. Using this RPD-based framework, we are able to construct high quality medial meshes with features preserved. Compared with existing sampling-based or voxel-based methods, our method is the first one that can preserve not only external features but also internal features of medial axes.

Pipeline

Given a closed manifold 3D mesh surface (a) with sharp edges and corners pre-detected (marked in black lines), the initial medial spheres (b) are generated including zero-radius spheres (shown as red points) placed on convex sharp features and inner Voronoi balls (shown as blue spheres) of surface samples, as described in Sec. 4.1. Inner Voronoi balls protrudes from the surface are then updated and pushed to be tangential to the surface (c), as described in Sec. 4.2. An initial medial mesh (d) is then constructed based on RRT, and internal features (shown as red lines) are selected using a seam tracing algorithm, as described in Sec. 4.3. A refined medial mesh (d) with higher quality can be obtained from feature preservation strategies and a thinning process, as described in Sec. 4.4.

Citation

@article{wang2022matfp,
    title={Computing medial axis transform with feature preservation via restricted power diagram},
    author={Wang, Ningna and Wang, Bin and Wang, Wenping and Guo, Xiaohu},
    journal={ACM Transactions on Graphics (Proc. SIGGRAPH Asia)},
    volume={41},
    number={6},
    pages={1--18},
    year={2022},
    publisher={ACM New York, NY, USA}
}