Tuesday, December 15, 2009

More hull

I realized I never wrote anything about the generic convex object visualization I mentioned earlier. It actually turned out really good, and the algorithm is very simple:

1) Get the support point for each of the positive and negative coordinate axes.
2) Build an octahedron with corners at the six points (like a pyramid pointing up, on top of a pyramid pointing down. This is the starting shape.
3) For each triangle in the current shape:
Get support point in outwards normal direction.
If support point does not equal (within margin) any of the three corners,
split the triangle into three new ones, using the new point.
4) Repeat step three until convergence, or maximum number of iterations.

Splitting the triangle into three is not ideal since it encourages long thin triangles and a rather uneven triangle distribution, but in practice it works fairly well. I guess one could look into Loop-style edge splitting instead, but it would require more bookkeeping.

I add a small sphere to each support function to get the slick round edges virtually for free!

I think I'm gonna have to take back what I said about the performance of stanhull. It's actually really slow and can somtimes take several milliseconds for just a few hundred points. I'm going to try and write my own convex hull generator based on the visualization algorithm above, but with one extra step - after each triangle split, prune vertices that are inside the newly formed tetrahedron. It would not be able to generate an optimal hull without reduction, but it would be guaranteed to have valid topology and connectivity. It would also have an almost trivial implementation and perform really well.

No comments:

Post a Comment