CODEWITHSUNDEEP
algorithmmath3dgeometryfrustum
Bob
Bob

Reputation: 101

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?

Upvotes: 10

Views: 4219

Answers (8)

eric
eric

Reputation: 71

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

Upvotes: 2

Hbf
Hbf

Reputation: 3114

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.

Upvotes: 4

Grembo
Grembo

Reputation: 1243

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 !

Upvotes: 0

Anthony Mills
Anthony Mills

Reputation: 8784

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.

Upvotes: 5

patros
patros

Reputation: 7819

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.

Upvotes: 0

plinth
plinth

Reputation: 49179

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.

Upvotes: 2

Aric TenEyck
Aric TenEyck

Reputation: 8032

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.

Upvotes: 0

tfinniga
tfinniga

Reputation: 6849

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.

Upvotes: 5

Related Questions