Jump to content

  • Log In with Google      Sign In   
  • Create Account

Need code for AABB vs triangle collision with least separation distance

  • You cannot reply to this topic
5 replies to this topic

#1 drnick@ludumdare   Members   -  Reputation: 106


Posted 30 July 2014 - 03:50 PM

I am looking for some 3D AABB vs. triangle collision code and it has been really hard to find.

More specifically, I need not only a boolean test of whether a box and a triangle overlap. I also need to find the least distance I need to move the box away so that it does not overlap anymore, to solve collisions.

I looked at this resource, http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html but it does not seem to give the distance, I also looked at this code http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tribox3.txt and it too does not seem to give the distance. I even translated it to Javascript actually, http://pastebin.com/FC7AYCx8. Googling, I found some old threads, including this one, http://www.gamedev.net/topic/386242-triangle---aabb-intersection/ but that too does not care about the distance.


So, if someone could link me to some code of a function that takes a triangle and a box and gives the least translation vector to separate them, I would appreciate very much.


#2 Randy Gaul   Members   -  Reputation: 376


Posted 30 July 2014 - 06:48 PM

You probably have trouble finding this code because it's not a very easy thing to write. However, it is a nearly identical problem to Triangle vs OBB, since you can transform the problem into the space of the OBB and treat the problem as Triangle vs AABB. Maybe this can help your search for resources.


There are 2 face axes and 3 edge axes on a triangle. On the AABB there are 3 face axes and 3 edge axes that need to be checked. In total you have to test 5 face axes and 9 edge pair axes. You can write a fast brute force test to find the axis of minimum penetration without too much trouble. I wrote an article specific for OBB to OBB derivation here: http://www.randygaul.net/2014/05/22/deriving-obb-to-obb-intersection-sat/ If you can understand this article you will realize the problem of Triangle to AABB is very similar.


Here is a boolean function from Ericson's orange book to get you started:

int TestTriangleAABB(Point v0, Point v1, Point v2, AABB b)
    float p0, p1, p2, r;

    // Compute box center and extents (if not already given in that format)
    Vector c = (b.min + b.max) * 0.5f;
    float e0 = (b.max.x – b.min.x) * 0.5f;
    float e1 = (b.max.y – b.min.y) * 0.5f;
    float e2 = (b.max.z – b.min.z) * 0.5f;

    // Translate triangle as conceptually moving AABB to origin
    v0 = v0 – c;
    v1 = v1 – c;
    v2 = v2 – c;

    // Compute edge vectors for triangle
    Vector f0 = v1 – v0,  f1 = v2 – v1, f2 = v0 – v2;

    // Test axes a00..a22 (category 3)
    // Test axis a00
    p0 = v0.z*v1.y – v0.y*v1.z;
    p2 = v2.z*(v1.y – v0.y) – v2.y*(v1.z – v0.z);
    r = e1 * Abs(f0.z) + e2 * Abs(f0.y);
    if (Max(-Max(p0, p2), Min(p0, p2)) > r) return 0; // Axis is a separating axis

    // Repeat similar tests for remaining axes a01..a22

    // Test the three axes corresponding to the face normals of AABB b (category 1).
    // Exit if...
    // ... [-e0, e0] and [min(v0.x,v1.x,v2.x), max(v0.x,v1.x,v2.x)] do not overlap
    if (Max(v0.x, v1.x, v2.x) < -e0 || Min(v0.x, v1.x, v2.x) > e0) return 0;
    // ... [-e1, e1] and [min(v0.y,v1.y,v2.y), max(v0.y,v1.y,v2.y)] do not overlap
    if (Max(v0.y, v1.y, v2.y) < -e1 || Min(v0.y, v1.y, v2.y) > e1) return 0;
    // ... [-e2, e2] and [min(v0.z,v1.z,v2.z), max(v0.z,v1.z,v2.z)] do not overlap
    if (Max(v0.z, v1.z, v2.z) < -e2 || Min(v0.z, v1.z, v2.z) > e2) return 0;

    // Test separating axis corresponding to triangle face normal (category 2)
    Plane p;
    p.n = Cross(f0, f1);
    p.d = Dot(p.n, v0);
    return TestAABBPlane(b, p);

Edited by Randy Gaul, 30 July 2014 - 06:51 PM.

#3 drnick@ludumdare   Members   -  Reputation: 106


Posted 30 July 2014 - 09:37 PM

Thanks for your help, but I already know that the problem of OBB vs. triangle is the same as AABB vs triangle... and I already have a boolean function, as the one you posted. My problem is specifically with getting this distance instead of a boolean.

If you could help me modify the function you coded to return distance, or help me understand what it's doing I'd appreciate very much... more specifically, what this part of the code is doing:

p0 = v0.z*v1.y – v0.y*v1.z;
p2 = v2.z*(v1.y – v0.y) – v2.y*(v1.z – v0.z);
r = e1 * Abs(f0.z) + e2 * Abs(f0.y);
if (Max(-Max(p0, p2), Min(p0, p2)) > r) return 0;

Edit: Oh, I looked at that book you mentioned and I figured out what is going on in the code, and now I will be able to find the best translation vector! Thank you.

Edited by drnick@ludumdare, 30 July 2014 - 11:09 PM.

#4 Dirk Gregorius   Members   -  Reputation: 742


Posted 31 July 2014 - 02:52 PM

You can look at my SAT presentation here: https://box2d.googlecode.com/files/DGregorius_GDC2013.zip


Essentially you need to keep track of the axis of minimum penetration instead of simply existing if you found a separating axis. Note that for disjoint objects the separating axis does not realize the actual distance. For the distance between two disjoint convex polyhedra I would use GJK.

#5 drnick@ludumdare   Members   -  Reputation: 106


Posted 05 August 2014 - 02:40 AM


What I achieved, now that I have succeed.

#6 Aardvajk   Crossbones+   -  Reputation: 5935


Posted 06 August 2014 - 04:11 AM

What I achieved, now that I have succeed.

The main difference between this solution and the one in the book is that this one normalizes the axes before calculating distances to give you the least translation vector, this makes this solution much more useful for game development.

Note you can skip this and compare the squared distances and then just normalize the final minimum separating axis vector instead to save a bunch of normalizings (sqrts).