I’ve been reminded of Limb Hacker.
This product was originally a fork of Turbo Slicer, which sliced animated characters. The big idea was that if the interface takes a bone instead of a plane, than it’s easy to:
- Slice the skeleton
- Slice the raw mesh
- Wholly ignore geometry that isn’t associated with the bone in question
My target was the original iPad and the iPhone 3GS, and it worked; I could hack of arms and legs. Dorky stuff. Very metal.
But it would mangle the mesh around the hips, and would slice the head. I had no idea how to fix it, and few people bought it. So in 2016, I dumped it on GitHub. It’s “freemium” now.
Last week, I was asked what’s up with it. A user shared with me this image:
It’s necessary to choose a slice plane automatically. Near the hips, often, the plane includes too many triangles. My strategy for choosing a slice plane requires a child of the bone, but the head is a leaf node.
The slice plane is chosen by taking the root of the bone, orienting it towards the child bones, in the space of the raw mesh.
But if we ask it to sever the left leg at the hip, it will tend to produce a slice plane that crosses both legs. If you slice at the knee, but Limb Hacker deals with that by ignoring vertices that aren’t associated with the relevant bones. Since the two legs aren’t sharing geometry, one leg is sliced while the other is untouched.
But near the hips, the relevant and non-relevant parts share geometry. There isn’t such a clean separation. The hole, therefore, is not flat, and cannot be filled in.
New Strategy
I realize now that I only need to choose the plane based on the vertices.
- Using the relevance test, one can find the “borders” of the relevant area.
- One can produce a plane that does not intersect this border geometry.
How, though, to produce a plane? I’m not a math guy. While I had some ideas about how I might produce one analytically, I decided that I’m not up to it, and I decided to try a genetic algorithm.
The job is to bisect the space such automatically, such that the red and orange point clouds are cleanly separated. The two point clouds represent the different borders of the slice.
I tried first a “naïve” bisector in a simplified (2D) environment. This bisector takes only the average of each point cloud – and both together – to find a center and orientation.
We see here two orange dots on the wrong side of the line. A plane line this would intersect with ignored geometry, resulting in a non-flat slice and a mangled mesh.
I tried text a brute for search, using the bounds of the point clouds as a hint:
These lines are valid! Each line shown was found within only a few hundred attempts. This might even be a solution, but:
- I will want to be able to pass in a “hint;” a slice plane we would like the result to resemble.
- If given an impossible scenario, it should produce a plausible plane.
- Ideally we would like it to be faster.
I’ve always wanted to a pretense to try a genetic algorithm. It’s easy to romanticize but doesn’t come up in my work. Well, here it is.
Using the “naïve” to choose the initial population speeds it further, with final lines chosen after as few as ten to thirty tests.
The code is more complex, as the fitness function is not binary (as in the brute force approach) but the difference in total tests is enough that the genetic approach is, in practice, over 50% faster than brute force.
We see here, also, it is able to cope with unsolvable scenarios in finite time:
What’s left? Before Limb Hacker can use this to find a plane, it will need to construct this point cloud explicitly. I expect to use the relevancy test; vertices which are relevant, but share triangles with vertices which are not, may serve as these “border” points. Another challenge will be classifying these points.
