Medial Axis & Skeletons

2 min read•1 page

The medial axis is the set of all points inside a shape that have more than one closest point on the boundary. In 2D, we can approximate it using the Voronoi vertices of points sampled along the boundary. Pruning removes noisy branches caused by boundary discretization.

Medial Axis Extraction:

1. Boundary Sampling: Sample vertices along the boundary curve. 2. Voronoi Filtering: Filter Voronoi vertices, keeping only those located inside the polygon. 3. Branch Pruning: Prune branches whose distances to the boundary are below the pruning threshold.

python

1def compute_2d_medial_axis(polygon_pts, prune_threshold):
2    # 1. Compute Voronoi diagram of boundary vertices
3    vor = Voronoi(polygon_pts)
4    
5    medial_edges = []
6    for edge in vor.ridge_vertices:
7        v0, v1 = vor.vertices[edge[0]], vor.vertices[edge[1]]
8        
9        # 2. Keep edges strictly inside the polygon
10        if is_inside(v0, polygon_pts) and is_inside(v1, polygon_pts):
11            # 3. Prune noise: check distance to boundary
12            d0 = min_dist_to_boundary(v0, polygon_pts)
13            d1 = min_dist_to_boundary(v1, polygon_pts)
14            if d0 > prune_threshold and d1 > prune_threshold:
15                medial_edges.append((v0, v1))
16                
17    return medial_edges

Pruning Threshold

0.25

1 min read•1 page

In 3D, the Medial Axis Transform (MAT) represents a shape as a continuous set of maximal inscribed spheres. A sphere is maximal if no other inscribed sphere contains it. The locus of the centers of these spheres forms the medial surface or medial curve network.

3D MAT Principles:

1. Skeletal Points: Centers of the maximal inscribed spheres form the 3D internal skeleton. 2. Tangency & Radius: Each sphere radius is the shortest distance to the shape's boundary, touching the surface in two or more points. 3. Reconstructibility: The original 3D volume can be fully reconstructed by taking the union of all maximal spheres.

python

1def compute_3d_medial_axis_transform(mesh):
2    # MAT represents the skeleton as a set of spheres: S = (center, radius)
3    mat_spheres = []
4    skeleton_vertices = extract_3d_voronoi_skeleton(mesh)
5    for v in skeleton_vertices:
6        # Distance to the closest boundary face
7        radius = compute_distance_to_boundary(v, mesh)
8        mat_spheres.append(Sphere(center=v, radius=radius))
9    return mat_spheres

Spine Sphere Position

0.00

2 min read•1 page

Volumetric thinning operates on 3D voxel grids. By iteratively removing voxels that lie on the outer boundary while preserving the topological connectivity (Euler characteristic) of the neighborhood, the shape is eroded down to a 1-pixel thick skeleton.

Thinning Rules:

1. Boundary Voxel: Has at least one background neighbor in its 6-connected neighborhood. 2. Simple Voxel: Deleting it does not create holes, merge cavities, or split a connected component in its 26-neighborhood. 3. Grassfire Analogy: Imagine lighting a fire at the boundary; the fire burns inward at constant speed, and the skeleton is where the fire fronts meet.

python

1def topological_voxel_thinning(grid):
2    # Progressively remove boundary voxels without changing topology
3    skeleton_grid = grid.copy()
4    eroded_any = True
5    while eroded_any:
6        eroded_any = False
7        candidates = []
8        for v in skeleton_grid.active_voxels:
9            # Check if voxel is on boundary and is 'simple'
10            # (Removal does not split or change topology in 26-neighborhood)
11            if is_boundary(v, skeleton_grid) and is_simple_voxel(v, skeleton_grid):
12                candidates.append(v)
13        
14        if candidates:
15            for c in candidates:
16                skeleton_grid.remove(c)
17            eroded_any = True
18            
19    return skeleton_grid

Thinning Iteration

0.00