Power Crust

Algorithm

Given a dense sample S from a surface F, we approximate the MAT of F with the polar balls of S. We then compute a piecewise-linear surface approximation of F from this approximation as follows:

    1. Compute the power diagram of the poles, weighted by the radii of the polar balls.
    2. Label each pole as inside or outside.
    3. Output the power diagram faces separating the power diagram cells of inside poles from the cells of outside poles.
 
 
 

Labeling

To label the set V of poles as inner or outer, we use the power diagram to define a graph on V. Two poles share an edge if their power diagram cells share a two-dimensional face.  We traverse the graph, using two facts to label the poles. The first is that an inner polar ball and an outer polar ball can only intersect shallowly. The second is that one of the poles of each sample is an inner pole and the other is an outer pole.

We start by labeling the poles on the bounding box as outer and then propagate labels by traversing the graph. For a  pole p with label outer , we label its neighbor q as outer if the polar balls at   p and q intersect deeply. For each sample s for which p is a pole, we label the other pole of s as inner. We follow a similar proceedure for inner poles.

A naive implementation of this algorithm would fail when the sampling fails to be sufficiently dense. To make it more robust, we use a greedy heuristic to propagate labels. We keep track of the "confidence" that each pole is inner or outer and label the poles for which we have the most confidence first.  The details are in our paper [1].

Power Shape

The power diagram of the poles also define a topologically correct approximation of the medial axis as a simplicial complex, which we call the power shape of S. The vertices of the complex are the poles of S.  Poles with the same label (inner or outer) whose power diagram cells are adjacent are joined by simplices. The power shape is a subset of the regular triangulation of the poles (the simplicial complex  dual to the power diagram, just as the Delaunay triangulation is dual to the Voronoi diagram.) .

Although the real medial axis is a two-dimensional surface, the power shape can contain some rather flat tetrahedra. In this sense it is not a great approximation of the medial axis. But we prove that it is a good approximation in other topological and geometric senses; for details see our papers.