6
\$\begingroup\$

I'm trying to understand swept-AABB collision detection. When checking for collisions between two positions of an object, I commonly see one of 3 strategies used:

  • Rays: trace rays from parts of the AABB at the previous postion to those on the final position, and check for intersection between them and other objects.
  • CCD: split the motion into multiple in-between positions, and check each one for collisions.
  • No sweep: just check that start and end positions are collision-free, and assume there was no collision in between.

A solution I've not seen discussed is just to use 2 triangles.

Here's how they compare:

Different Approaches

The math wouldn't change even if you started using OBBs or convex shapes with more vertices: you still just need 2 triangles.

The above image illustrates the shortcomings of each approach. Only the Polygon conversion test is sure to catch all of the swept region.

From the tests I have done, simple triangle collision in not that costly, though slower than AABB–AABB and sphere–sphere. It seems to cost less than CCD also, but avoids misses (e.g. CCD might miss the red cube in the top left). Rays have a tendency to miss small objects if you imagine moving one of the red cubes up or down in the image.

Are there issues with this technique that would cause it to be used so little?

\$\endgroup\$
2
\$\begingroup\$

Yes, your technique would work. It looks like a certain implementation of the convex hull technique, where you construct a convex hull describing the movement, and detect collisions by checking the overlap of those convex hulls with each other. Depending on implementation details, your technique could be faster or slower - note that your triangles technique has two redundant diagonal edge tests, which could be made faster by converting the two triangles into a single quad.

But there are other techniques, including spacial partitioning, Minkowski, and all sorts of variations under the bounding volume family (which includes everything from bounding spheres, AABB, down to convex hull).

One disadvantage with many of these techniques, including yours, is that it does not give the time and location of the collision. CCD does, so does transforming into a ray-volume test.

\$\endgroup\$
0
\$\begingroup\$

Continuous Collision Detection (CCD) and Ray Casting provide a specific time of impact (TOI). However using two AABBs and two triangles to create the 'hexagon' that covers all locations of the AABB's travel, you would only know whether TRUE/FALSE an intersection occurred - this isn't as useful when dealing with 'swept AABB' detection.

Even with the images if you have a box in the middle of your two triangles is true that the triangles will detect the hit as true but they cannot tell you which edge hit first or when along the swept aabb it occured.

\$\endgroup\$
  • 1
    \$\begingroup\$ thank you - but calculating the first impact from a list of collisions based on the hexagon polygon shape wouldn't be that difficult. \$\endgroup\$ – SkidRunner Apr 29 '16 at 13:42
  • \$\begingroup\$ Can you update your question with a diagram and pseudo code showing how? It's not clear to me. \$\endgroup\$ – Steven Apr 29 '16 at 14:22
  • 3
    \$\begingroup\$ Even though it does not give TOI it may be a good approach for a broad-phase where you just want to narrow down the number of possible collisions. Even better - it would allow you to get all of the objects directly on the path without false positives. And it could coexist with kd-tree giving even better results. \$\endgroup\$ – Sopel Sep 7 '16 at 19:53

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.