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

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 !

Answer 2

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 3

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.

Answer 4

Well let's solve with math.

Using right hand Y up coordinate system (forward is –Z axis), for frustum with viewport width w, height h, near plane n, far plane f, X axis field of view angle fov, then the minimal bounding sphere is

k = sqrt(1+(h/w)^2) * tan⁡(fov/2)

if( k^2 >= (f-n)/(f+n) )
{
    C = (0, 0, -f)
    R = f*k
}
else
{
    C = (0, 0, -0.5 * (f+n) * (1+k^2))
    R = 0.5 * sqrt( (f-n)^2 + 2*(f^2+n^2)*k^2 + (f+n)^2*k^4 )
}

C is the center of the sphere, in view space, and R is radius.

I put details in my blog if you are interested: https://lxjk.github.io/2017/04/15/Calculate-Minimal-Bounding-Sphere-of-Frustum.html

Answer 5

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.

Answer 6

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.