Finding a minimum bounding sphere for a frustum

问题:

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?

回答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.

回答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.

回答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.

回答4:

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.

回答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.

回答6:

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.

回答7:

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 !

回答8:

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