0
\$\begingroup\$

I am trying to calculate the exact collision time of two axis-aligned bounding boxes (aabb) as fast as possible (in the sense of CPU time).

  • I have all the required information (aabb min, max, center, etc., velocity vector, and so on)
  • My aabbs are not rotating, so they have linear velocity
  • The aabbs can be both moving, only one of them might be moving, or they both might be steady

My current approach creates lines from one of the boxes' corners and checks the collision among the planes of the other box (you can see the algorithm below); however it takes 6 times longer than I can afford. So, I am trying to find a faster algorithm; however, I couldn't have managed, yet.

My current "slow" algorithm:

  1. Add velocity of Aaabb to Baabb and assume Aaabb is steady and Baabb is moving
  2. Calculate the corner positions of Baabb
  3. For each corner of Baabb, perform the line-plane intersection with Aaabb's each 6 planes (I use the line-intersection formulate (algebraic form) on Wikipedia) to check if there is an intersection.
  4. If a corner of Baabb intersects with a plane of Aaabb, verify the intersection point is behind the other 5 planes of Aaabb
  5. Keep the smallest value of d and return
\$\endgroup\$
5
  • \$\begingroup\$ Subtract one box's velocity from both to reduce it to a moving-vs-stationary AABB test. Then shrink the moving box down to its center point and add its size to the other. Now you've reduced it to a single ray versus box test. \$\endgroup\$
    – DMGregory
    Jan 16, 2021 at 22:38
  • \$\begingroup\$ Thank you for the suggestion @DMGregory, this improved a lot, but I still would like to gain more if possible. \$\endgroup\$
    – ciyo
    Jan 17, 2021 at 15:09
  • \$\begingroup\$ Do you have a broadphase pass before this, to skip over pairs whose bounding rectangles over their whole movement don't overlap? \$\endgroup\$
    – DMGregory
    Jan 17, 2021 at 15:11
  • \$\begingroup\$ The nature of the problem does not really fit to perform a broadphase pass (in the sense of space partitioning). I want to provide two aabbs and get a time that can be 1 second, but also 500 seconds if possible. On the other hand, if there is a fast mathematical way to find out whether the aabbs will not collide without checking all the 6 planes, I do not have know and use it. @DMGregory \$\endgroup\$
    – ciyo
    Jan 18, 2021 at 18:57
  • \$\begingroup\$ You could find the closest approach between the rays described by their velocities - it it's greater than the sum of their bounding radii, you know they will never collide. \$\endgroup\$
    – DMGregory
    Jan 18, 2021 at 20:19

0

You must log in to answer this question.