License: MIT.

This repository provides two skeletonization methods based on inner-point selection:

• 🌟 Coverage Axis.
  • Coverage Axis computation for both mesh and point cloud inputs.
    • The point cloud can be unoriented -> check out our latest SIGGRAPH 2023 work here.
  • Operations are accelerated by GPU, e.g., computation of coverage matrix and winding number for a mesh.
  • Codes for building connectivity are in skel_connection: README.md.
• 🌟 Coverage Axis++.
  • Coverage Axis++: Efficient Inner Point Selection for 3D Shape Skeletonization: https://arxiv.org/abs/2401.12946.

Related: some geometry tools for MAT and related topics are in Geometry_Tools.

• [June, 2026] Added a GPU-accelerated exact solver for the Coverage Axis point-selection step (beta). It solves the same 0-1 set-cover program and returns the same optimal selection as the original (no heuristic), with the coverage matrix built on the GPU (NVIDIA Warp) and the integer program solved exactly. Includes a double-cover-of-a-torus example (offset the surface inward and outward, then cover both shells). See CA_GPU.
• [May, 2026] Added an integrated pipeline with GPU Q-MAT (beta): a GPU re-implementation of Q-MAT medial-axis simplification (NVIDIA Warp), with native support for preserving Coverage Axis poles via --selected-poles. See Geometry_Tools/QMAT_GPU.
• [Sep, 2026] Added the skeleton connection step for mesh inputs to the tutorial: mesh_to_ma.py computes the initial medial axis of the mesh (with the Voronoi candidate inner points) and Coverage_Axis_connection.py simplifies it onto the selected inner points with the anchored edge collapse of Q-MAT (Sec. 4.3 of the paper).
• [Aug, 2025] Added an integrated pipeline (credit to Jiaxin Wang): integrated_qmat_coverage_axis.py. You will be using Q-MAT (see more instructions here).

🐱 Coverage Axis: Inner Point Selection for 3D Shape Skeletonization , Eurographics 2022.

+ Top Cited Article in Computer Graphics Forum (CGF) 2022-2023.

Authors: Zhiyang Dou, Cheng Lin, Rui Xu, Lei Yang, Shiqing Xin, Taku Komura, Wenping Wang.

[Project Page][Paper][Code]

In this paper, we present a simple yet effective formulation called Coverage Axis for 3D shape skeletonization. Inspired by the set cover problem, our key idea is to cover all the surface points using as few inside medial balls as possible. This formulation inherently induces a compact and expressive approximation of the Medial Axis Transform (MAT) of a given shape. Different from previous methods that rely on local approximation error, our method allows a global consideration of the overall shape structure, leading to an efficient high-level abstraction and superior robustness to noise. Another appealing aspect of our method is its capability to handle more generalized input such as point clouds and poor-quality meshes. Extensive comparisons and evaluations demonstrate the remarkable effectiveness of our method for generating compact and expressive skeletal representation to approximate the MAT.

🐱 Coverage Axis++: Efficient Inner Point Selection for 3D Shape Skeletonization , SGP 2024.

+ Top View Article in Computer Graphics Forum (CGF) 2024.

Authors: Zimeng Wang*, Zhiyang Dou*, Rui Xu, Cheng Lin, Yuan Liu, Xiaoxiao Long, Shiqing Xin, Lingjie Liu, Taku Komura, Xiaoming Yuan, Wenping Wang.

[Project Page][Paper][Code]

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 both shape coverage and uniformity 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++.

• Linux Ubuntu 20.04
• Python 3.8
• Nvidia GeForce RTX 3090 (GPU is used for acceleration)

git clone https://github.com/Frank-ZY-Dou/Coverage_Axis --recursive
conda env create -f ca.yml
conda activate CA
pip install -r requirements.txt

The skeleton connection step for mesh inputs uses Q-MAT (submodule skel_connection/QMAT, C++; our copy of Net-Maker/QMAT with a fix in the simplification with selected poles, see below). It needs CGAL, GMP and MPFR; on Ubuntu:

sudo apt install cmake build-essential libcgal-dev libgmp-dev libmpfr-dev
cd skel_connection/QMAT && mkdir build && cd build && cmake -DCMAKE_BUILD_TYPE=Release .. && make -j4 && cd ../../..

This produces the executable skel_connection/QMAT/build/QMAT. If the submodule folder is empty, run git submodule update --init first. The point-selection scripts do not need Q-MAT.

The input mesh 01Ants-12_mesh.off is placed in the folder input. The mesh is normalized. The pipeline has three steps: the initial medial axis with the candidate inner points, the selection of the inner points, and their connection into a skeleton.

python mesh_to_ma.py --mesh ./input/01Ants-12_mesh.off --out ./input/01Ants-12_mesh.ma

computes the initial medial axis of the mesh, i.e. the Voronoi diagram of the mesh vertices restricted to the inside of the mesh (a few seconds). It writes

• input/01Ants-12_mesh.ma: the medial axis (vertices with radii, edges and faces) in the .ma format of Q-MAT, used by the skeleton connection step;
• input/01Ants-12_mesh_VD.txt: the vertices of the medial axis with their radii, one line v x y z r per vertex. They are the candidate inner points of the selection.

Both files are provided in the repository for the ant, so this step can also be skipped.

Specify the settings for Coverage Axis in Coverage_Axis_mesh.py

real_name = '01Ants-12_mesh'
surface_sample_num = 2000
dilation = 0.02
inner_points = "voronoi"
# inner_points = "random"
max_time_SCP = 1000 # in second

For Coverage Axis, Run

python Coverage_Axis_mesh.py

For Coverage Axis++, Run

python Coverage_Axis_plusplus_mesh.py

The outputs are placed in the folder output.

• mesh_inner_points.obj contains the candidate inner points.
• mesh.obj contains the input mesh.
• mesh_samples_2000.obj contains the sampled surface points that are covered (mesh_samples_1500.obj for Coverage Axis++, i.e., mesh_samples_<surface_sample_num>.obj).
• mesh_selected_inner_points.obj contains the selected inner points.
• mesh_selected_inner_points.txt contains the selected inner points with the radii of their medial balls, one line v x y z r per point. It is the input of the skeleton connection step below.

Note that all outputs except mesh.obj are point sets: these .obj files contain only v lines and no faces. A viewer that only renders triangles shows them as empty; use one that renders points (e.g., MeshLab).

Instead of the vertices of the medial axis, randomly generated points inside the volume can be used as candidates by setting inner_points = "random" (a sample, input/01Ants-12_mesh_random.obj, is provided; generating it takes a while). Their radii are estimated from the surface samples and they are not vertices of the medial axis, so the skeleton connection below snaps them to the nearest medial axis vertex; the skeletons are less regular than with the Voronoi candidates.

python Coverage_Axis_connection.py --mesh ./input/01Ants-12_mesh.off --ma ./input/01Ants-12_mesh.ma --selected ./output/mesh_selected_inner_points.txt --out ./output/mesh_skeleton

connects the selected inner points into a skeleton following Sec. 4.3 of the Coverage Axis paper (mesh input with candidates from the Voronoi diagram): the selected points are anchors on the initial medial axis, which is simplified onto them by the edge collapse of Q-MAT. An edge whose two endpoints are anchors is never collapsed, an edge with one anchor endpoint is collapsed onto the anchor, and an edge without anchor endpoints is collapsed onto the optimal sphere of Q-MAT, until only the anchors remain; the skeleton therefore inherits the connectivity of the medial axis. The script runs mode 2 of the Q-MAT executable (--qmat gives its path if it is not ./skel_connection/QMAT/build/QMAT) and prints the size of the skeleton, its number of connected components (one for the ant) and the distance between the selected points and the skeleton vertices (Q-MAT can move an anchor slightly when a collapse onto it would fold the medial mesh).

The Q-MAT copy in the submodule orders the edges incident to a selected point by the distance between the point and the other vertex, instead of the quadric error of the anchor sphere: the latter penalises the large medial balls, whose neighbourhood is then absorbed by smaller anchors, leaving the large ball connected by a single edge. The merged sphere and the collapse rules are unchanged.

The outputs are placed in the folder output.

• mesh_skeleton.obj contains the skeleton: the vertices (v), the edges (l) and the triangles (f). MeshLab and Blender display the edges and triangles.
• mesh_skeleton.ma contains the same skeleton with the radii of the medial balls in the .ma format of Q-MAT (nv ne nf header, then v x y z r, e i j and f i j k with 0-based indices).
• mesh_skeleton_balls.obj contains the medial balls of the skeleton vertices as sphere meshes, to view the skeleton together with its balls as in the figures of the paper.

skeleton: selected points, edges and triangles

skeleton with its medial balls

The same command works for the output of Coverage Axis++ (Coverage_Axis_plusplus_mesh.py writes the same mesh_selected_inner_points.txt).

A GPU-accelerated exact solver for this point-selection step, with a double-cover example, is in CA_GPU. Offsetting a surface inward and outward gives two shells; sampling candidates on the original surface, Coverage Axis selects points that cover both shells:

original mesh (yellow) + double cover

original mesh + selected points

I will give more instructions on this part.

We use Fast Winding Number for Inside-outside determination for point cloud inputs. Note that we use "oriented point cloud" in our paper. You can use mesh_oriented_pc.py to generate this sample given a mesh input. After running the code you will get the input: 01Ants-12_mesh_ori_pc.obj in the folder of input.

If you want to process unoriented point clouds, please check out our SIGGRAPH 2023 work (SIGGRAPH 2023 The Best Paper Award): Globally Consistent Normal Orientation for Point Clouds by Regularizing the Winding-Number Field. Our approach involves developing a smooth objective function to define the requirements of an acceptable WindingNumber Field, which facilitates the identification of globally consistent normal orientations for Unoriented Point Cloud, even in the presence of noisy normals. GCNO significantly outperforms previous methods, especially in handling sparse and noisy point clouds, as well as shapes with complex geometry and topology.

Please use the following commands for building the modified libigl at https://github.com/Frank-ZY-Dou/libigl_CA. Note that Eigen is needed for libigl; make sure you have installed it.

sudo apt-get install git
sudo apt-get install build-essential
sudo apt-get install cmake
sudo apt-get install libx11-dev
sudo apt-get install mesa-common-dev libgl1-mesa-dev libglu1-mesa-dev
sudo apt-get install libxrandr-dev
sudo apt-get install libxi-dev
sudo apt-get install libxmu-dev
sudo apt-get install libblas-dev
sudo apt-get install libxinerama-dev
sudo apt-get install libxcursor-dev
sudo apt install libeigen3-dev
sudo apt-get install libcgal-dev

git clone https://github.com/Frank-ZY-Dou/libigl_CA.git
cd libigl_CA/
mkdir build
cd build
cmake ../
make -j8

Once finished, you will get two executable files under bin: 807_FastWindingNumber and 807_FastWindingNumber_CA.

cd bin

You will find an executable file 807_FastWindingNumber in the folder bin. This is a tutorial program.
You can run it by

./807_FastWindingNumber

Press "1" twice to toggle between viewing the polygon soup and the point cloud.

This is our case. Please remember to put the input file 01Ants-12_mesh_ori_pc.obj in to the bin folder.

./807_FastWindingNumber_CA ./01Ants-12_mesh_ori_pc.obj  ./01Ants-12_mesh_inner_points.obj

Visulization: Press "1" to view the point cloud.

Press "2" twice to toggle between viewing the full query point cloud and the point cloud identified within the volume—these are the inside candidates we need.

Once you run this code, you will get the output 01Ants-12_mesh_inner_points.obj - inner candidate points. Please rename it to 01Ants-12_pc_random.obj and move it to the folder input. You can downsample the inner points if you want.

Then, for Coverage Axis, run

python Coverage_Axis_pc.py

For Coverage Axis++, run

python Coverage_Axis_plusplus_pc.py

The outputs are placed in the folder output.

• pc_inner_points.obj contains the candidate inner points.
• pc_samples.obj contains the points of the point cloud that is covered. SCP is an NP-hard problem; make sure the number of to-be-covered samples is not that large.
• pc_selected_inner_points.obj contains the selected inner points.
• pc_selected_inner_points.txt contains the selected inner points with the radii of their medial balls (v x y z r).

Remark: We generate the point cloud inputs and inside candidates based on Fast Winding Number. The candidates are generated by randomly sampling inside the volume. Other sampling strategies, like Voronoi-based sampling, can also be used. The core code for sampling the point cloud and generating inside candidates are given in

./libigl_CA/tutorial/807_FastWindingNumber_CA/main.cpp

update: The code in MATLAB can be found in ./MATLAB.

Run

Pole_Selection_offset

The results are written to ./MATLAB/outputs

You could check with output file like vis_MA_init01Ants-27_scale0.03.obj.

The original optimization is solved by MATLAB. In this repo, we solve SCP by Scipy in Python. I found the solver of MILP in scipy is a little unstable compared with the MATLAB one; please suggest if you have a more powerful solver or any idea for this. Thanks ;)

f =  ones(1,medial_num); 
A =  -D;
b =  -ones(boundary_num,1)*1;%here ,we fix p_i 
lb = zeros(medial_num,1);
ub = ones(medial_num,1);
iint = [1:medial_num];
tic;
[x,fval]=intlinprog(f,iint,A,b,[],[],lb,ub);
toc;
disp('min_number:');
disp(fval);

The skeleton connection of the tutorial above (mesh_to_ma.py + Coverage_Axis_connection.py) uses Q-MAT. integrated_qmat_coverage_axis.py is an all-in-one variant (Q-MAT pre-simplification of the initial medial axis, Coverage Axis++ selection, Q-MAT connection), see skel_connection. Both have only been tested on Ubuntu 22.04.

@inproceedings{dou2022coverage,
  title={Coverage Axis: Inner Point Selection for 3D Shape Skeletonization},
  author={Dou, Zhiyang and Lin, Cheng and Xu, Rui and Yang, Lei and Xin, Shiqing and Komura, Taku and Wang, Wenping},
  booktitle={Computer Graphics Forum},
  volume={41},
  number={2},
  pages={419--432},
  year={2022},
  organization={Wiley Online Library}
}

@inproceedings{wang2024coverage,
  title={Coverage Axis++: Efficient Inner Point Selection for 3D Shape Skeletonization},
  author={Wang, Zimeng and Dou, Zhiyang and Xu, Rui and Lin, Cheng and Liu, Yuan and Long, Xiaoxiao and Xin, Shiqing and Komura, Taku and Yuan, Xiaoming and Wang, Wenping},
  booktitle={Computer Graphics Forum},
  volume={43},
  number={5},
  pages={e15143},
  year={2024},
  organization={Wiley Online Library}
}

@article{xu2023globally,
  title={Globally consistent normal orientation for point clouds by regularizing the winding-number field},
  author={Xu, Rui and Dou, Zhiyang and Wang, Ningna and Xin, Shiqing and Chen, Shuangmin and Jiang, Mingyan and Guo, Xiaohu and Wang, Wenping and Tu, Changhe},
  journal={ACM Transactions on Graphics (TOG)},
  volume={42},
  number={4},
  pages={1--15},
  year={2023},
  publisher={ACM New York, NY, USA}
}

• https://libigl.github.io/tutorial/ Many thanks to the contributors of libigl :)
• https://www.cgal.org/
• https://gist.github.com/dendenxu/ee5008acb5607195582e7983a384e644

This repository is released under the MIT License. Third-party components retain their original copyright notices and licensing terms.