Coverage Axis++: Efficient Inner Point Selection for 3D Shape Skeletonization

Abstract

We introduce Coverage Axis++, a novel and efficient approach to 3D shape skeletonization. The current state-of-the-art approaches for this task often rely on the watertightness of the input or suffer from substantial computational costs, thereby limiting their practicality. To address this challenge, Coverage Axis++ proposes a heuristic algorithm to select skeletal points, offering a high-accuracy approximation of the Medial Axis Transform (MAT) while significantly mitigating computational intensity for various shape representations. We introduce a simple yet effective strategy that considers shape coverage, uniformity, and centrality to derive skeletal points. The selection procedure enforces consistency with the shape structure while favoring the dominant medial balls, which thus introduces a compact underlying shape representation in terms of MAT. As a result, Coverage Axis++ allows for skeletonization for various shape representations (e.g., water-tight meshes, triangle soups, point clouds), specification of the number of skeletal points, few hyperparameters, and highly efficient computation with improved reconstruction accuracy. Extensive experiments across a wide range of 3D shapes validate the efficiency and effectiveness of Coverage Axis++. The code will be publicly available once the paper is published.

Introduction

The pipeline of Coverage Axis++. (a) Input point cloud. (b) Inner point candidates. (c) Candidate inner balls with original radius. (d) Selected inner balls with original radius. (e) Selected inner points. (f) Skeletonization result.

More details can be found in the paper.

We develop a simple yet more efficient skeletonization method for shapes represented as meshes or point clouds. We take centrality and uniformity into consideration and develop a heuristic algorithm to achieve representative skeletal point selection with high efficiency. Specifically, we present a scoring scheme that assigns a score to each inner point as a quantification of its skeletal representation ability. The scoring consists of the coverage, uniformity and centrality scores. The coverage score is determined by evaluating the number of surface samples that can be covered within the dilated ball associated with the candidate to ensure coverage inspired by Coverage Axis. The coverage score ensures consistency with the shape structure by favoring interior points that dominate a larger area, aligning with the definition of the Medial Axis Transform (MAT) as the set of centers of maximally inscribed spheres. On the other hand, uniformity is one of the key desired features of compact skeletonization to suppress redundant structures, for which we introduce the uniformity score. The score is calculated by measuring the distance between the candidate and the nearest point in the set of selected inner points. This achieves a uniformly distributed skeletonization result by preventing the selected points from clustering together. Moreover, the centrality score is employed to encourage those central points to receive higher scores to promote centrality further. The skeletal points are derived by running a priority queue defined by an integration of these scores.

To summarize, our method enjoys the following features:

• Skeletonization for various shape representations including water-tight meshes, triangle soups, and point clouds.
• Specifying the number of skeletal points, which is a desirable feature for learning-based methods as a fixed number of points are typically required.
• Highly efficient computation while achieving better or more competitive reconstruction accuracy.
• Few hyperparameters.
• Randomly generated candidates inside the volume as it selects the most expressive ones from overfilled inner point candidates.

Coverage Axis++ from Mesh Input

Qualitative comparisons. (a-c) SAT. (d) MATFP. (e) QMAT. (f) QMAT+. (g) Coverage Axis. (h) Coverage Axis++.

Coverage Axis from Point Cloud Input

A gallery of skeletonization results of point clouds using Coverage Axis++.

More Experimental Results

Influence of Skeletal Point Number

Influence of target numbers |V|. We test our model with the target numbers being 30, 50 and 70.

Influence of Dilation Offset

Skeletonization results using different dilation offsets.

Ablation on Scoring Terms

Performance of different combinations of the three scores. (a) coverage score. (b) coverage + uniformity score. (c) coverage + uniformity + centrality score.

Running Time

Running time w.r.t. candidate skeletal point numbers |P| with |V| = 100, |S| = 2000.

Running time w.r.t. surface sample numbers |S| with |V| = 100, |P| = 10000.

Running time w.r.t. target skeletal point numbers |V| with |S| = 2000, |P| = 10000.