Calculate diameter of sphere large enough to encompasss a frustum

Question

I'm attempting to speed up box-to-box collision checks by first testing if two spheres large enough to encompass each (respectively) would collide (because I'm using separating axis theorem and it's slower than I'd like it to be).

This is fine for equilateral boxes (ie, cubes) since I can just take two opposing corners and the line between them is the exact diameter of a sphere big enough to encompass the whole thing properly; and also the point in it's middle is the origin of the sphere. I add an epsilon just to avoid any glitches with colliding with the corners of the cube, but theoretically it shouldn't be necessary.

But for non-equilateral boxes, such as frusta, this method does not work. I've pondered it over and nothing I can come up with is a quick enough calculation for my taste. The best I've come up with is to take two opposing edges (diagonally through the box) from the near face to the far face, get their individual lengths and sum them; then do the same thing for the left-to-right faces and top-to-bottom faces. with these three sums, take the largest and just use that.

Anyway, that method works but it's too much calculation, involving 6 square roots. I need something faster and preferably more accurate. I've googled and haven't found much on this subject at all. I'd like the solution to work for boxes of any shape (as long as faces are valid) and frustums of unknown orientation (meaning the large face could be any side, not a known one).

It's also important to know the origin of the sphere (which is the dead center of the frustum). Which if there is no faster calculation, this is just the sum of all 8 verts divided by 8.

Any ideas?

Answer 1

I do not think this answers your question in the general case, this is more specific to a frustum, and assumes that you know the 8 vertices formed by the intersecting planes ahead of time.

Effectively, you need to know the distance from the center of your frustum to the 8 points where 3 planes intersect. What you do not need is to know the Euclidean distance for all 8; squared distance will work just fine.

On the range [0,oo):

(n+1)^2 > n^2

On the range: (-oo,0]:

(n-1)^2 > n^2

Since the only thing you are interested in is the magnitude of the distance from the center of your frustum to the extremes, this works quite well. The square of any non-zero displacement will always be greater than a shorter displacement (regardless of direction).

Now, given the squared distance to each of the 8 points, all you need to know is which one of them has greater magnitude.

The squared distance with greatest magnitude is the only distance you actually have to perform a sqrt on. This will be the minimum radius necessary to create a circumsphere for your frustum. Thus, what takes you 6 sqrt operations right now can be done with only 1.