CODEWITHSUNDEEP
mathlanguage-agnosticphysicsgame-physics
mcmonkey4eva
mcmonkey4eva

Reputation: 1377

Tracing the movement of an AABB into a polyhedron

Let's say you have an AABB (Axis-Aligned Bounding Box... a cuboid, basically). You also have a polyhedron (a convex shape of undefined form - it can be anything, a cuboid, a sphere, a capsule, all you know is a list of planes that make it up).

Now let's say this AABB is a moving object. In fact, it's moving at light speed. However, the polyhedron is unmoveable. The AABB is firing straight at the polyhedron, and we need to know where exactly it stops (it stops immediately upon contact with the polyhedron.)

There is the obvious method of calculating it: Cut the movement into a bunch of tiny chunks, step it forward piece by piece, and stop at the spot before the spot in which it intersects the polyhedron. But this is slow and inaccurate.

There is a method which only works feasibly in 2D: Take the minkowski difference (subtract all points of one object from the other), calculate a convex hull from that, then trace a line into the box. Unfortunately, in 3D, the convex hull is a pretty intense calculation, and can't really be done for every moving object in a world against every static polyhedron, even with a quickly-calculated broad check.

So the question is... what's the proper way to calculate this, that works with perfect or near-perfect accuracy, and works from any distance?

Is my method (the one marked for 2D) the correct method, just implemented poorly on my end? Is there a better method?

I'm working in C#, though this question should be the same for any language.

This is a 3D question, but here's a 2D diagram to help get the idea across:

enter image description here

Upvotes: 2

Views: 199

Answers (1)

Jay Kominek
Jay Kominek

Reputation: 8783

Let's just treat the AABB as another, boring polyhedron, M (for moving). It's travelling towards polyhedron S (for stationary), along vector T (for travel).

There are two possibilities:

  1. The corner of one polyhedron pierces the other polyhedron through a facet.
  2. Edges or facets of the polyhedrons are parallel, and impact one another along their surfaces.

The second case can be ignored, as it implies one or more corners impacting simultaneously.

First, only a limited number of planes of each polyhedron can participate in the collision. For M, only the planes whose dot product with T is positive. For S, only the planes whose dot product with T is negative. Find all those planes, and keep them, we'll call them the collision participating planes.

Then, find all of the coordinates of the corners of M, and express them as functions of time, t. (x coordinate of corner M_0 at time t, {{M_0}_x}^t = T_x * t + {{M_0}_x}^0, etc)

Find the smallest t where one of the corners of M has passed through all of the collision-participating planes of S, and you'll know when M first pierces S. (This is a standard linear programming problem.)

Finally, repeat the last two steps, but move the "stationary" S towards M, backwards along T (use negative "time", t). In negative time, the largest t where one of the corners of S has passed through all the collision-participating planes of M will be the impact time. You can flip the sign on it, compare to the t you got from moving M, and take the least one. That'll be the time of impact. You can plug that into coordinates of M to figure out the exact position.

And since M was actually an AABB, you can reconstruct it quite quickly and losslessly from the coordinates.

(I haven't implemented this. Let me know if any parts are unclear.)

Upvotes: 1

Related Questions