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?
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.
The way to do this is to find a sphere that fits 4 points on your frustum. If this is a proper frustum (a truncated pyramid - my bad I was assuming a cylindrical fristum), then you get two points from opposite corners of the top quad, and the other two from the bottom quad, out of phase with the top two. Then use this to get your sphere.
Any set of four noncoplanar points defines a sphere. Assuming you're using a four-sided pyramid for your frustum, there are 70 possible sets of four points. Try all 70 spheres and see which is the smallest.
Given that your frustum probably has some symmetries, you can probably pick the four points on opposite corners and use plinth's solution.
You need to find a point on a "vertical" line down the center of the frustum where the distance to an edge on the bottom and top of the frustum (assuming it's symmetrical) is the same.
solve such that a point on the bottom is Xb, Yb, Zb, a point on the top is Xt, Yt, Zt and the line is a point Xp, Yp, Zp plus a vector Ax, By, Cz.
so solve the equation
sqrt( (Xb - (Xp + VAx) )^2 + (Yb - (Yp + VBy))^2 + (Zb - (Zp + VCy))^2) =
sqrt( (Xt - (Xp + VAx) )^2 + (Yt - (Yp + VBy))^2 + (Zt - (Zp + VCy))^2).
The only variable in there is the scalar V.
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.
Strictly speaking (according to this) the base of the frustum can be any polygon and, also strictly speaking, that polygon doesn't even have to be convex. That said, to get a general solution to the problem, I think you might need to use (almost) all the vertices as suggested above. There might be special cases, though, whose solution might (as suggested above) only require the comparison of a couple of spheres. I like the link by Anthony above: Megiddo provides a transformation that he claims yields a solution in O(n) (!) time. Not bad !