Posts

Showing posts from December, 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 su

Big or beautiful

Here is a capture from a couple of simple demos. I've made a number of improvements to the solver lately and also now gathering multiple contact points in the initial manifold. Incremental manifold is such a neat idea, but it does affect stacking stability, and objects tend to penetrate more, which in turn affects both performance and behavior. I'm now using relative rotations and reiterating GJK to find multiple points, but I'm experimenting with other methods that should be both cheaper and more stable. All demos use a 60 Hz update and four solver iterations. Various shock propagation methods in the solver remove a lot of the sponginess you normally see at four iterations. I strongly believe in elegant algorithms, rather than hand-optimized brute force code. Hence, I think it's better to have a rather sophisticated solver that do more work per iteration rather than just increasing the number of iterations. As you can see in the demos, even a quite large stack is pret

Full hull

Today I was scouting around for a decent convex hull generator. It's quite surprising to me that such a clearly defined task still doesn't have a de facto standard implementation that everybody uses. I just wanted one for computing the visualization meshes, so performance is not even critical. I looked into a couple of different ones that had clean interfaces. This one looked promising due to its simplicity, but after trying just a few point clouds it crashed on me. Convex hull generation is tricky that way "Oh, how hard can it be, just split that triangle, merge those two, test for that plane, blah blah" and then when you sit down and implement it there are all these degenerate cases, and you can't really make assumptions about anything . Our convex hull generator at Meqon was a constant pain in the ass for three years. I don't think we ever got it right. Qhull seems to be very robust, but a) it's a huge mess, b) it has a ton of features you don't