All vertices in projected edges are now examined to see if they meet the threshold for significance using the Douglas-Peucker line approximation algorithm. Unfortunately, it seems difficult to determine a universal threshold, which is why having the algorithm run as a node instead of a command might be beneficial.
Here is the dog as an example, using 0.0015 as the Douglas-Peucker threshold. Knots are indicated by locators.
The results aren't particularly clear in this example, but further processing does occur so the threshold may change to accommodate that.
Best Fit Polynomial
In order to determine the best way to connect these knots to form components, ACD calculates a weight for each projected edge using the best fit polynomial from Andreas Hubeli and Markus Gross's 2001 Multiresolution Feature Extraction from Unstructured Meshes paper. The ACD paper was a little vague about what to do here, so I'm writing out my approach.
We know that the best fit polynomial is computed from the intersection between the plane that bisects an edge e and a subset of the model surrounding e. The following questions arise. How do we find the intersection? How big should the model subset be? What degree polynomial do we need? How does one even calculate the polynomial?
Finding the Intersection
Because the input model could be of any density or topology, there's no simple loop that we can iterate over to find appropriate nearby edges that intersect the plane.
We want to get all of the edges that intersect the plane without "skipping" one, so a traversal seems most intuitive. I considered a Dijkstra-type approach, but it was difficult to guarantee continuity. We don't care about other points, so depth-first traversal is preferable to breadth-first. We can guide the traversal by picking the neighbor that best fits a criterion. One criterion is to pick the neighbor closest to the plane, but this doesn't always work if the "best" edge is much longer than the other outgoing edges. Another criterion is to find the outgoing edge that points most towards the plane, storing the edge if it crosses the plane. This seems to work in my test cases.
If we have a strict depth-first traversal, we might not find intersecting edges the most efficient way (one side of the plane may be denser than the other, or one side may be curved). To counter this, we can pick the "best" unvisited edge (using our criteria) from the current vertex and the vertex we came from. This optimization may be unnecessary though. Then, in order to get roughly equal amounts of data on either side of the edge, we can simply restart our traversal with the best neighbor in the opposite direction. What happens if edge e is a length-wise edge on a low-poly cylinder? As such, it's probably best to alternate between the two directions to ensure an even spread.
Determining the Polynomial
In order to answer the question of "How much data?", we must first determine the method of processing the data. The best fit polynomial weight calls for a second derivative, which means that we need at least a quadratic or cubic polynomial for non-trivial results.
I don't have a lot of experience in this area, but it seems that the best general-use method for fitting a polynomial (or polynomial regression) is the least-squares method. I'm not about to implement my own linear algebra library, so I'll let Eigen do the work.
Because chances are that the knots are on C curves, even ordered polynomials would work best. It would also be very simple to check the nature of the curve and change orders accordingly. It's also worth noting here that polynomials can't handle overlapping y values, so nearly circular and related shapes need to be checked.
Model Subset Size
Although the best fit polynomial is more or less mesh-density agnostic, we still care about the mesh as a whole (for skeletonization), rather than at the detail level. However, I'll need to write some tools to find the best method for calculating mesh density. For now, I'll say that 3 points on either side of the edge are sufficient. This is because a typical animation rig limb might have around 8-24 (very rough estimate) lengthwise divisions, whereas the chest/pelvis likely has 16-32 (also rough estimate). Regardless of the estimate accuracy, 7 vertices are far more than enough to find the curvature of an 8 vertex circle, and they should also be enough to cover a feature on a high-res model.
That should be everything! Time to get to implementing.