Finding a minimum bounding sphere for a frustum

Question

I have a frustum (truncated pyramid) and I need to compute a bounding sphere for this frustum that's as small as possible. I can choose the centre to be right in the centre of the frustum and the radius be the distance to one of the "far" corners, but that usually leaves quite a lot of slack around the narrow end of the frustum

This seems like simple geometry, but I can't seem to figure it out. Any ideas?

Answer 1

This is probably not the answer you're looking for, but you could compute all the verts of the frustum and plug them into a general minimum bounding sphere algorithm, like the miniball implementation.

Answer 2

Well, there's http://www.cgafaq.info/wiki/Minimal_enclosing_sphere of course (via Google).

I'd think there are two possibilities. One (if the frustum is very flat) would be that the opposite points of the base become opposite points on the sphere. The other (if the frustum is very tall) would be that opposite points of the frustum would be on the sphere and you'd figure out the sphere from those four points (one point on the base, one opposite the first on the base, one opposite the first on the higher square, one adjacent the first on the higher square).

Figure out the first sphere. If the frustum fits in it, that's your answer. Otherwise, the second sphere would be your answer.

Answer 3

There are several algorithms and implementations out there for this problem (see also this post).

• For 2D and 3D, Gärtner's implementation is probably the fastest.

• For higher dimensions (up to 10,000, say), take a look at https://github.com/hbf/miniball, which is the implementation of an algorithm by Gärtner, Kutz, and Fischer (note: I am one of the co-authors).

• For very, very high dimensions, core-set (approximation) algorithms will be faster.

In your particular application, you may want to try either of the first two algorithms. Both run in O(n) with a very small constant and are numerically stable.