I'm trying to find an algorithm or library that will perform continuous collision detection between a plane of triangles (see example.png) and an AABB.

I'm defining a plane of triangles as a set of triangles whose vertices all lay on the same plane. The triangles will be connected by edges meaning triangles will never connect by just one vertex and will never appear isolated (unconnected) from the set. The triangles may form a convex or concave shape - the picture shows a concave shape.

I did read up on SAT and GJK algorithms, but they seem to be designed for convex shapes - not a plane of triangles. Even if there is a way to detect collision, I'd still need a way to determine the time t in the range [0, 1) that contact would occur.

This question comes from the notion that a level will be made up of "surfaces" where each surface is a set of triangles on the same plane. See example2.png - the left side is wireframe and the right side shows the surfaces filled with color. So to be clear that picture shows four surfaces were each one is made up of two triangles.

You build the swept AABB around the original AABB at its start and end position (e.g. SweptAabb = Aabb(t1) + Aabb(t2)). You find/query all triangles within that swept AABB usually utilizing some kind of broadphase. This is the set of potentially colliding triangles and you have to compute the TOI for each triangle in this set and keep track of the minimum TOI.

You build the swept AABB around the original AABB at its start and end position (e.g. SweptAabb = Aabb(t1) + Aabb(t2)). You find/query all triangles within that swept AABB usually utilizing some kind of broadphase.

That makes a lot of sense. I even found a paper for testing if a triangle and AABB are overlapping:

http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tribox_tam.pdf

This is the set of potentially colliding triangles and you have to compute the TOI for each triangle in this set and keep track of the minimum TOI.

This is the part I'm struggling with. I'm not sure how to find the TOI, especially considering corner cases (see link). These scenarios could happen top-down or from the side. For reference, the colored lines are surfaces and the black box is the AABB.

http://imgur.com/a/koKuH

The problem with the first image is the green and blue surfaces are within the swept AABB and closer to the AABB's starting position then the purple surface. However they are clearly not colliding with the AABB at any time t like the purple surface does.

The second image shows how corners (were two surfaces meet) need to be accounted for. Also, the reverse situation could happen were the AABB is colliding into the interior of a V shaped pair of surfaces as opposed to the top of an /\ (arrow) shape like in the picture.

i am also interested in this topic. but i think SAT should solve this http://www.gamedev.net/topic/536601-general-obb-question/?view=findpost&p=4471803 previously it was mentioned to do tests AABB vs Tri. though didn't test it myself. and this example comes even with velocity support (exactly what you want)

but ofc there may be a better narrow case way to do this. (which would be great to know)

i am also interested in this topic. but i think SAT should solve this http://www.gamedev.net/topic/536601-general-obb-question/?view=findpost&p=4471803 previously it was mentioned to do tests AABB vs Tri. though didn't test it myself. and this example comes even with velocity support (exactly what you want)

That particular example appears to be for OBB vs OBB collision. I'm looking for the time t in the range [0, 1) that an AABB and a triangle make contact. There is some interesting reading material earlier in the thread so I'll look through that.

I already do have an AABB vs triangle function working using SAT. The problem is finding the time t. I haven't found any material to do this. I did find material for finding the least translation vector using the SAT algorithm, but that's not what I'm after. I need to account for velocity and find t.

bool collide(Body& other, float dt)
    {
        Vector mtd;
        Vector ncoll;
        float tcoll;
        bool intersecting;
        bool colliding;

        if(!SAT::TestBoxes(m_box, m_velocity, other.m_box, other.m_velocity, mtd, ncoll, tcoll, colliding, intersecting))
            return false;

        // collision too far ahead in time. ignore.
        if (tcoll > dt)
            return false;

tcoll > dt, looks just like t to me idk.

In general, when dealing with continuous collision detection with polygons, you want to identify vertex-face and edge-edge collisions, both of which can only occur when the particles involved become coplanar.

Having an AABB moving in a simple linear path should simplify the math for most of these operations. First we need a normal, which will be the face normal or the normalized cross product of the edge directions. Then you take the dot product of that normal with a point where the moving feature starts, a point where it ends, and a point where the fixed feature lies - this gives you 3 distances in the normal direction. Calculate the distance from start to fixed, and divide by the total distance from start to end to get the time 0-1 where the features became coplanar. If the time is outside of 0-1, they were never coplanar.

Once you have the time of coplanarity you can interpolate your positions and perform a static collision test at that point in time, which either boils down to verifying that the closest points on the two lines are within the line segments for edges, or testing that the cross product of the vertex with each polygon edge in a convex polygon points in the same direction. If your face is not convex you may need to break it into convex pieces and test them individually.

There are a couple of options to compute the TOI:

1) Conservative Advancement (B.Mirtich)
2) Bracketed Advancement (E. Catto)
3) Convex Cast (G. v. d. Bergen)
4) Special case version using continuous SAT

They all use basically the same idea. The first two require a stable version of GJK to compute distance inside the loop. If you have only linear movement (no rotation) CA is great as the root finding is trivial. For CCD with rotation CA has problems and might iterate forever and even might not find a solution. This is solved in bracketed advancement. A pathological example would be an icehockey pug spinning in place.

If you are not into this topic a lot what I am saying might not make sense to you. This is a pretty large topic and here are some suggestions for reading:

1) B. Mirtich's PhD explaining CA: http://www.kuffner.org/james/software/dynamics/mirtich/index.html
2) E. Catto's GDC presentations: http://box2d.org/files/GDC2013/ErinCatto_GDC2013.zip
3) Gino has a couple of great presentation here: http://dtecta.com/publications

In particular:
Ray Casting against General Convex Objects with Application to Continuous Collision Detection: http://dtecta.com/papers/unpublished04raycast.pdf
Continuous Collision Detection of General Convex Objects under Translation: http://dtecta.com/papers/gdc2005_Gino_vandenBergen.pps

4) There might be special version for swept AABB vs triangle. I would check Christer Ericson's book: 'Real-Time Collision Detection'



HTH,
-Dirk

Having an AABB moving in a simple linear path should simplify the math for most of these operations. First we need a normal, which will be the face normal or the normalized cross product of the edge directions. Then you take the dot product of that normal with a point where the moving feature starts, a point where it ends, and a point where the fixed feature lies - this gives you 3 distances in the normal direction. Calculate the distance from start to fixed, and divide by the total distance from start to end to get the time 0-1 where the features became coplanar. If the time is outside of 0-1, they were never coplanar.

That makes a lot of sense, but I'm wondering how to handle the "corner" case as depicted in the attached image. The black lines are the surfaces, the dashed gray lines are the planes for those surfaces, the green box is the AABB, and the red line is the expected sliding plane.

In this case the AABB needs to be close enough to overlap (e.g. clip through) the surface planes. And it seems to me you'd normally use the surface planes as the sliding plane, but in this case you'd actually want to use the AABB's surface as the sliding plane.

There are a couple of options to compute the TOI: 1) Conservative Advancement (B.Mirtich) 2) Bracketed Advancement (E. Catto) 3) Convex Cast (G. v. d. Bergen) 4) Special case version using continuous SAT

Thanks for the links. That's a lot of reading material :)

[attachment=33296:problem.png]

I'm wondering how to handle the "corner" case as depicted in the attached image.  The black lines are the surfaces, the dashed gray lines are the planes for those surfaces, the green box is the AABB, and the red line is the expected sliding plane.
In this case the AABB needs to be close enough to overlap (e.g. clip through) the surface planes.  And it seems to me you'd normally use the surface planes as the sliding plane, but in this case you'd actually want to use the AABB's surface as the sliding plane.

You need to handle 3 distinct cases. Edge vs edge is symmetrical, but for face vs particle you need the faces of the first body against the particles of the second, plus the particles of the first body against the faces of the second. In your case it happens to be that the face is moving, but that should still be fine... the face never rotates while it moves, so you can still use it to get a normal and then find where the particle falls on that normal relative to where the face starts and ends.