• Create Account

## Need code for AABB vs triangle collision with least separation distance

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #1drnick@ludumdare  Members

106
Like
0Likes
Like

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.

### #2Randy Gaul  Members

2343
Like
4Likes
Like

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.

### #3drnick@ludumdare  Members

106
Like
0Likes
Like

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.

### #4Dirk Gregorius  Members

2432
Like
0Likes
Like

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.

### #5drnick@ludumdare  Members

106
Like
0Likes
Like

Posted 05 August 2014 - 02:40 AM

https://github.com/lucasdealmeidasm/TriangleBox.js

What I achieved, now that I have succeed.

### #6Aardvajk  Members

12259
Like
0Likes
Like

Posted 06 August 2014 - 04:11 AM

https://github.com/lucasdealmeidasm/TriangleBox.js
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).

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.