1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ You do not need more than a single square root for this... you can compare the length to each plane in terms of squared distance. The act of squaring a series of monotonic numbers is always monotonic, so 3^2 < 4^2 ... n^2 < (n+sign (n))^2. This way you can find the largest (squared) radius, once you have that you can do a single sqrt on it and you have your Euclidean radius with 7 fewer sqrts. \$\endgroup\$ – Andon M. Coleman May 8 '14 at 0:20
  • \$\begingroup\$ Trying to, anyway. using squared lengths always scares me because it's difficult to visualize. sqrtf(4) is 2, and sqrt(4)+sqrt(4) is 4. sqrt(4+4), however is not 4. it is 2.82 \$\endgroup\$ – zeroth May 8 '14 at 0:33
  • \$\begingroup\$ I get what you're saying about monotonic whatnots but I don't get what you're saying about using 5 sqrtfs. you said at the beginning that I would only need 1. PS - post it as an answer and I'll +1 you. \$\endgroup\$ – zeroth May 8 '14 at 0:36
  • \$\begingroup\$ yes, I have all 8 unique vertices that compose the planes of the frustum \$\endgroup\$ – zeroth May 8 '14 at 1:03
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ apparently I don't have enough rep to +1 the comment, but I accepted your answer anyhow. \$\endgroup\$ – zeroth May 8 '14 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.