Metadata-Version: 2.4
Name: mesh-skeleton
Version: 1.0.3
Summary: Extract connected skeletal graphs (centerlines) from 3D meshes
Author-email: Salvatore Esposito <salvatore.esp95@gmail.com>
License: MIT
Project-URL: Homepage, https://github.com/iamsalvatore/mesh-skeleton
Project-URL: Repository, https://github.com/iamsalvatore/mesh-skeleton
Project-URL: Issues, https://github.com/iamsalvatore/mesh-skeleton/issues
Keywords: mesh,skeleton,centerline,medial-axis,graph,3d,geometry,voxel,skeletonization,medical-imaging
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Image Processing
Classifier: Topic :: Scientific/Engineering :: Medical Science Apps.
Classifier: Topic :: Scientific/Engineering :: Visualization
Classifier: Topic :: Multimedia :: Graphics :: 3D Modeling
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy
Requires-Dist: scipy
Requires-Dist: trimesh
Requires-Dist: scikit-image
Requires-Dist: matplotlib
Requires-Dist: networkx
Requires-Dist: tqdm
Provides-Extra: gpu
Requires-Dist: torch; extra == "gpu"
Dynamic: license-file

# Mesh Skeleton

Extract a **connected skeletal graph** (centerline) from a 3D mesh. Unlike a point-cloud skeleton, the output is a NetworkX graph with full connectivity — so you can traverse paths, walk branches, find endpoints and junctions, and navigate the shape directly.

<table align="center">
<tr>
  <td align="center">
    <img src="https://raw.githubusercontent.com/iamsalvatore/mesh-skeleton/main/assets/tree_mesh_spin.gif" width="300" alt="Gnarled tree surface mesh, rotating 360 degrees"><br>
    <sub><b>1 · Input mesh</b><br>510k-vertex surface</sub>
  </td>
  <td align="center">
    <img src="https://raw.githubusercontent.com/iamsalvatore/mesh-skeleton/main/assets/tree_skeleton_spin.gif" width="300" alt="Extracted skeleton graph of the tree, rotating 360 degrees"><br>
    <sub><b>2 · Skeleton graph</b><br>single trunk centerline + branches</sub>
  </td>
</tr>
</table>

<p align="center"><sub>Demo mesh: <a href="https://www.fab.com/listings/ceb1f02c-f0a9-4795-b8f6-8bd55703b1b4"><i>Ancient Gnarled Tree</i></a> by <b>Amstad Digital</b> (Fab, Standard License), shown for illustration.</sub></p>

## Installation

```bash
pip install mesh-skeleton
```

Or from source:

```bash
git clone https://github.com/iamsalvatore/mesh-skeleton.git
cd mesh-skeleton
pip install -e .
```

## Quick Start

### Command line

```bash
mesh-skeleton input_mesh.obj                                   # basic extraction
mesh-skeleton input_mesh.stl -o skeleton.ply -r 256            # custom resolution / output
mesh-skeleton input_mesh.obj --no_viz                          # skip the matplotlib preview

# organic / thick-trunked meshes (like the tree above): a coarser grid keeps the
# trunk a single centerline, and --clip_base drops a flat ground/root slab
mesh-skeleton tree.glb -r 128 --clip_base 0.05 -o tree_skeleton.ply
```

### Python API

```python
import trimesh
from mesh_skeleton import SkeletonExtractor

mesh = trimesh.load('model.obj', force='mesh')
extractor = SkeletonExtractor(mesh, voxel_resolution=256)
skeleton_coords = extractor.extract_skeleton()      # simplify=True by default

# The connected graph and its topology
G          = extractor.skeleton_graph               # NetworkX graph (nodes -> rows of skeleton_coords)
endpoints  = extractor.endpoints                    # degree-1 nodes (branch tips)
junctions  = extractor.junctions                    # degree>=3 nodes (bifurcations)
main_path  = extractor.main_path                    # longest centerline (graph diameter)

# Ordered centerline between two world-space points
centerline = extractor.get_ordered_centerline(start_point=[0, 0, 0], end_point=[1, 1, 1])

# Save PLY (points + edges) and JSON (full graph)
extractor.save_skeleton(skeleton_coords, 'skeleton.ply')
```

## How it works

The skeleton is the **medial axis** of the solid enclosed by the mesh — the curve that stays equidistant from the surface. The pipeline turns that idea into a clean, connected graph:

1. **Voxelize & fill.** The mesh is rasterized onto a voxel grid and its interior is filled *solid*. Watertight meshes use exact ray-cast containment (`mesh.contains`); non-watertight meshes are sealed by morphological **closing + exterior flood-fill** — raise `--closing_iterations` when surface gaps are large enough to let the fill leak.
2. **Thin.** The solid volume is reduced to a one-voxel-wide skeleton by 3-D topological thinning ([`skimage.skeletonize`](https://scikit-image.org/)), which preserves connectivity and topology.
3. **Build the graph.** Skeleton voxels become nodes; 26-connected neighbors become edges (via a KDTree query).
4. **Enforce connectivity.** Components separated by small gaps (within `mesh_scale * 0.1`) are bridged with interpolated edges, so the result is a single traversable graph.
5. **Simplify.** Thinning a *thick* region produces a medial **surface** — a web of tiny loops and short spurs — rather than one line. So the graph is cleaned: loops are broken with a length-weighted **minimum spanning tree** (a tree-like skeleton should be acyclic) and short dead-end **spurs are pruned**. Pass `--no_simplify` to keep genuine cycles (e.g. vascular loops).
6. **Analyze.** Endpoints (degree 1), junctions (degree ≥ 3), the **main centerline** (graph diameter via double-BFS on the largest component), and non-overlapping branch segments are extracted.

> **Getting a correct centerline.** A truly flat or bulky region (a tree's root buttress, a ground plane, a wide slab) has no 1-D medial axis — its medial axis is a *sheet*, which thins to a tangle. Two knobs fix this: use a **coarser `--resolution`** so thick parts are only a few voxels across (they then thin to a single line), and **`--clip_base`** to drop a flat ground/root slab before thinning. The tree above is `-r 128 --clip_base 0.05`.

## GPU acceleration

When PyTorch with CUDA is available, voxelization and the morphological fill run on the GPU automatically — no code changes, with transparent CPU fallback.

## Output files

**`skeleton.ply`** — vertex positions and edge connectivity.

**`skeleton_graph.json`** — the full graph:

```json
{
  "vertices":     [[x, y, z], ...],
  "edges":        [[v1, v2], ...],
  "endpoints":    [0, 5, ...],
  "junctions":    [12, 34, ...],
  "main_path":    [0, 1, 2, ...],
  "branch_paths": [[12, 13, 14], ...]
}
```

## CLI arguments

| Argument | Default | Description |
|----------|---------|-------------|
| `input_mesh` | required | Input mesh (OBJ, STL, PLY, GLB, …) |
| `-o, --output` | `skeleton.ply` | Output path (`_graph.json` is written alongside) |
| `-r, --resolution` | `256` | Voxel grid resolution (128 = fast/coarse, 256 = balanced, 512 = fine) |
| `--closing_iterations` | auto | Closing iterations for the non-watertight fill; raise to seal larger surface gaps |
| `--clip_base` | `0.0` | Fraction of height to drop at the base before thinning (removes a flat ground/root slab) |
| `--no_simplify` | off | Keep the raw skeleton (do **not** break loops or prune spurs) |
| `--no_viz` | off | Skip the matplotlib preview |

## Resolution & tuning guide

| Resolution | Use case | Notes |
|-----------|----------|-------|
| 128 | Quick preview; thick/bulky shapes | Fewer, cleaner branches — thick parts thin to a single line |
| 256 | Production | Balanced detail and speed |
| 512 | Fine structures | Slower; captures thin branches (erosion scales up automatically) |

## Troubleshooting

**Empty skeleton** — check the mesh has valid geometry and consistent normals; try a higher resolution.

**A thick trunk/slab looks like a web of lines** — that region's medial axis is a *surface*. Lower `--resolution` and/or use `--clip_base` (see *How it works*). Simplification (`on` by default) removes the residual loops and spurs.

**Many disconnected components** — components under 10 voxels are pruned; larger ones are bridged within `mesh_scale * 0.1`. Verify the mesh is (nearly) watertight, or raise `--closing_iterations`.

**Slow processing** — the bottleneck is `skeletonize` (CPU-bound). Reduce the resolution.

## Credits

The demonstration mesh is *[Ancient Gnarled Tree](https://www.fab.com/listings/ceb1f02c-f0a9-4795-b8f6-8bd55703b1b4)* by **Amstad Digital**, published on [Fab](https://www.fab.com/) under the Standard License, and is used here purely to illustrate the skeleton extraction.

## License

MIT — see [LICENSE](LICENSE).
