Animation and Bounding Sheres

X-Plane uses transform animation - that is, 3-d models are animated by applying rotations and translations to parts of their geometry.  This makes calculating the bounding sphere tricky.

In attempting to find the smallest static bounding sphere that accounted for all animation, I first tried transforming the bounding sphere by the animation.  Translations would move the sphere half-way to the extrema of the translation and increase the radius by half the translation distance. Rotations around the origin would move the sphere to the origin and increase the sphere size by its original distance from the origin.  (This is like convolving the sphere around a sphere.)

This didn't work very well - consider a rotating beacon on top of a tall pole.  This object has only one animation - a rotate around the Y axis.  If we convolve around a sphere, we end up rotating the rotating beacon around the arm of the pole (e.g. its very tall height) when in fact it only rotates around the Y axis, which it is not far from at all.

So take two was to take the axis into account, convolving the sphere correctly around the axis. This helped a lot, but for some models the sphere was still really huge.

Then a modeler pointed the problem out to me: some authors will rotate an object a tiny bit around a very long arm to create a not-quite-linear translation.  Convolving around 360 degrees for this tiny rotation means picking up a ton of area that would never be in the object.

So take three is to explicitly convolve the rotated geometry along the real rotated arc at a few degrees spacing, with the spacing decided by whether we need to be faster or more accurate. This seems to work pretty well.

The most accurate thing I can image would be to actually convolve all of the points to create a finalized point cloud and then take the bounding sphere.  We get false area by convolving a larger volume than we need to.  The problem with the point cloud approach is that the number of points increases exponentially as we nest animations - to truly get it right, assuming 36 convolve steps, each point is multiplied up to 36 times for each rotation.

Assuming we could afford that cost, to be even more correct, we would want to convolve taking into account aligned animation variables - that is, if two animations happen in lock-step, we should not multiply out all possibilities because they cannot animate separately.

But at some point, the bounding sphere is a heuristic, and in practice the three refinements above make a huge improvement and don't leave a lot of slop on the table.