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.

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 pretty stiff.

Speaking about demos, I am SO tired of physics demos running in slow-motion.

1) Most programmers know that taking smaller time steps increases general stability. Objects move less per time step, hence making things easier to compute.

2) Decreasing gravity improves stability, since stacks feel less weight of the objects above them.

Most people would agree that altering any of the above is cheating. People are generally very picky about keeping the time step realistic, and some are proud to use 9.82 as gravity instead of just 10. But hey, why do most physics demos run in slow-motion then? Because there's a third way to cheat that nobody cares about:

3) Making objects larger is just as bad as decreasing gravity.

Remember what Galileo taught us four hundred years ago: Large objects receive the same gravitational acceleration as small objects. So, keeping the acceleration constant and increasing the size is equivalent to keeping the same size of the object and decreasing the gravity! Increasing the size of an object might seem quite innocent "Ho ho ho, my simulation is so stable. This box just happen to by six feet tall, who can blame me for that?"

How about simulating a pile of books? Or a couple of plates and wine glasses? At 60 Hz that's quite a challenge, and which objects are going to be more common in your game? So, if you evaluate a physics engine always make sure to do it in a realistic scale. The boxes in these demos are just above one foot along the side, which I think even that is questionable. A set of physics demos that really impressed me for their natural looking motion is the Tokamak Physics Engine.

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 want and c) it has a somewhat questionable license.

James Dolan kindly pointed me to an implementation written by my former colleague Stan Melax for a physics exporter. John Ratcliff then wrapped it up, gave it the name "stanhull" and posted it on his code suppository. It took me five minutes to integrate, it works like a charm, it has a great interface, no dependencies and it's fast. Look no more and cheers to Stan.

I have also contemplated to do an automatic visualization of implicit convex hulls using only the support function. Not that it would be super-useful, but still pretty cool to use the same code for visualizing all types of convex objects. A naive approach would be to sample the support function in a ton of different directions and just build a hull of the resulting points, but I've been thinking about a more intelligent subdivision method to avoid sampling crazy many directions and still not miss corners. Might try it tomorrow.

Putting on the shades

For rendering, I wanted to go one step (but not more than one step) beyond the flat-shaded polygons that are typical for physics demos. I wanted shadows, but I have never been a big fan of sharp edges, such as with shadow volumes or even shadow maps. Soft shadows is really what enables a whole new level of realism.

I worked on an ambient occlusion project for Ageia a couple of years ago, just before they got acquired by Nvidia and I think that's a really good alternative to real global illumination. My approach at the time was to compute ambient oclcusion in 3D on the second generation PhysX hardware (that was never released) and dynamically update low-res light maps for the parts of the scene that changed. It had good potential, but shortly after Crysis was released and the screen-space methods (SSAO) started taking off. I've always been curious about SSAO ever since but never got around to implement one, so I thought this was a good opportunity.

I found this article, which is a really good introduction. I didn't end up using exactly that method, but it's quite similar. Vertex position and normals are rendered to an FBO, then the occlusion is computed to another FBO and the final image is rendering to the framebuffer using deferred lighting. During the final pass occlusion values are blurred, using only samples in the same plane. Ideally one would want to do this with a gauss kernel, but I only do it horizontally and vertically to save some shader cycles. I'm still on my three year old MacBook Pro with an ATI X1600... Additionally I'm also blurring the normals a tiny bit during the final pass to soften the edges.

There's not an awful lot of time spent on the rendering part, but I'm quite happy with it for the time being. Here's a video demonstrating the scene with and without ambient occlusion.

A new hope

So I finally did what I should have done a long time ago - I started coding physics again. All those ideas that were lingering in the back of my head in the Meqon and Ageia days but I never had time to try will finally materialize, be implemented and posted on this very blog, along with pictures, videos, demos and general ideas around physics engines.

So far I've focused on rigid body dynamics, and more specifically the contact manifold and solver. I'm a big fan of GJK, so there's no surprise it makes up the backbone of the collision detection engine.

The solver is of sequential impulse type with warmstarting (just like everybody else), but has a big bag of tricks that accumulated over the years. I put a lot of effort in friction this time, since I really wanted a realistic friction that does not creep, but actually sticks and comes to rest, even in non-trivial poses.

Allright, here's the obligatory box pyramid: