Blog

Sep 10

Written by:
Friday, September 10, 2010 

DigitalRune Geometry supports automatic generation of bounding shapes and convex hulls. Using simple bounding shapes or convex hulls is more efficient than using arbitrary triangle meshes in game physics. In this post we will investigate different kinds of bounding shapes.

What's up dude?

Let's look at a practical example. Here is the Dude from the XNA Skinned Model Example:

(Click image to enlarge.)

The model has 13132 vertices and the skeleton has 60 bones.

Bounding Spheres

Here is the same model where a bounding sphere is computed for the vertices of each bone.

(Please ignore the flat shading of the spheres. In the test program we didn't compute correct vertex normal - but these are really spheres.)

We have reduced a model with 13k vertices to 60 automatically fit spheres. But the spheres do not fit very tightly. We could get a better sphere-based representation by manually placing several smaller spheres per bone. And there are many small spheres that could be merged (e.g. for the finger bones).

Bounding Capsules

The same model with automatically fit capsules.

Capsules are very good bounding shapes for the arms and legs of human figures.

Oriented Bounding Boxes

This is the dude with Oriented Bounding Boxes (OBBs).

The boxes are much better for the torso. They also fit nicely on the arms. But when we use this shapes for a ragdoll animated by game physics, the movement will not be as smooth as with capsules.

Convex Hulls

In contrast, let's compute the convex hull for each bone.

Now, that is a much nicer fit. But the largest convex hull consists of 375 vertices. - Quite a lot for a single object. Good that the new convex hull creation in the next DigitalRune Geometry version supports simplification of convex hulls.

When we restrict each hull to max. 64 vertices, we get the following:

Restricting each hull to max. 32 vertices:

This is still a very good fit and all 60 convex hull together use 1130 vertices - less than 9% of the original triangle mesh. 

How far can go with this? Max. 16 vertices per convex hull:

Uh - maybe still acceptable. Let’s stop here before things get really ugly.

DigitalRune Geometry has several optimizations for convex hulls and they are a viable alternative to bounding spheres, capsules and boxes.

In the next post we will talk about creating convex hulls and how the convex hull simplification is done.