Just in case you are curious, for the more general case where you have two triangular meshes that can both move/rotate/stretch and need to collide against each other, as long as you consider the particles in each mesh to be individually moving linearly the problem can be solved. The three cases; a.tri vs b.part, a.part vs b.tri, and a.edge vs b.edge all involve four particles moving linearly. If you consider one of these particles to be your origin, you can subtract it's starting location from the other starting locations and its ending location from the other ending locations. This will give you a set of three basis vectors that change linearly over time, and when the determinant of the matrix describing this basis goes to zero you know that the particles have become coplanar. Solving this equation for t (the time of coplanarity) turns out to be a matter of finding the roots of a cubic equation.

The fact that you have nothing that rotates or stretches in your problem simplifies things a lot, because you go from having to solve a cubic in the general case to knowing the normal in advance and just having to solve something linear, i.e. start + t (end - start) = fixed, where start end and fixed are all just nice one dimensional scalars in the normal direction.

The fact that you have nothing that rotates or stretches in your problem simplifies things a lot, because you go from having to solve a cubic in the general case to knowing the normal in advance and just having to solve something linear, i.e. start + t (end - start) = fixed, where start end and fixed are all just nice one dimensional scalars in the normal direction.

Thanks a lot for your help. I've actually got an implementation mostly working. I do have 2 follow up questions:

1. I don't foresee scaling being needed, but rotation might be added. Could you recommend an algorithm/technique for this?

2. I'm using a delta timer to keep execution consistent across frame rates. With that said, I am noticing issues with the collision detection failing due to precision when the frame rate runs uncapped and the delta is very small. Are precision issues common? How often do physics implementations use a fixed time step as opposed to running as fast as possible?

I don't foresee scaling being needed, but rotation might be added. Could you recommend an algorithm/technique for this?

To be completely accurate in your resolution, for a rotating object you would need to use the full cubic solver described in my previous post for all of your triangle-particle, particle-triangle, and edge-edge collision pairs.

You can get approximate continuous collision with a rotating body by considering the features of one body from the point of view of the frame of the body that is rotating. With a point vs a rotating box, you can get where the point is relative to the frame of the box at the start of the frame, where it is in the frame of the box at the end of the frame, and then pretend that the particle has moved linearly in the space of the box and resolve in that space. This linearizes what would actually be a curved motion in that space, so there can be edge cases where a particle slips through the cracks between triangles. Giving the particle some radius can help to make this more robust.

I'm using a delta timer to keep execution consistent across frame rates. With that said, I am noticing issues with the collision detection failing due to precision when the frame rate runs uncapped and the delta is very small. Are precision issues common? How often do physics implementations use a fixed time step as opposed to running as fast as possible?

Precision issues are definitely common, and 80% of the work to make a robust physics system is doing extensive testing to find edge cases that fail, making sure that you have consistent repro steps so you can step in the debugger and see exactly which numeric operation is incorrect and for what reason (parallel moving edges can be a nightmare). A way that I've found works well to keep things fairly consistent/jitter free at arbitrary dynamic framerates is to advance the physics at a fixed large timestep which you never run slower than (typically 30fps), and then rewind the final result back to however much time actually elapsed. Since particles move linearly, if the final state is valid for continuous collision then interpolating the system backward will always be a valid state as well.

As a side note, I tend to use positional dynamics for simulation, which means at the start of the physics step I integrate initial particle positions to obtain an initial set of predicted positions, and then have constraints work directly by moving those predicted particle positions around until constraints are satisfied. Final velocities are then computed by subtracting where each particle lands from where it started. This makes stepping through what collisions and other constraints are doing a lot easier than working in velocity space.

There is an important distinction between a broad phase and actually resolving collisions. The only purpose of the broad phase is to do a cheap query that gives you candidates upon which you do more expensive tests. The broad phase is generally going to be pessimistic; it will find candidates that don't collide, but it should never miss candidates that do collide.

The broad phase makes it possible to build a list of every potentially colliding feature pair (face-particle or edge-edge) to test without having to go N^2 over the whole world. The individual feature pair tests still have to be run to see if there was a collision, and for those that collided you want to resolve the one colliding earliest in the frame.

That said, you can make a more optimized tighter fitting broad phase shape. A k-DOP, or Discrete Oriented Polytope, generalizes the idea of the bounding box. Instead of just keeping the min/max extents in the x direction, y direction, and z direction, you add in some diagonal directions as well - for instance, the x+y direction or the x-y+z direction. Just like with a bounding box, only if all corresponding ranges for the two objects contain some overlap are the objects considered to be potentially colliding. This will reduce the number of false positive candidates you generate, but it won't completely eliminate them.

Finding the time of coplanarity is not the last step. This is again, as you noted, a pessimistic test - coplanarity is necessary, but not sufficient, for a collision to occur. Once you have a time of coplanarity, you have to determine whether the features are actually intersecting at that time. You interpolate all particles involved to the time in question, and then do a test within the plane of collision. For face-particle this is a check that the particle is contained within the face in 2D (for convex faces this basically means verifying that if the particle forms a triangle with each edge in the polygon, the winding orders of all the triangles formed are the same, i.e. their normals point in the same direction). For edge-edge this is a test that the location where the lines formed by each edge cross each other is between the endpoints for both edges involved.

These tests can be done completely in 2D, since everything is coplanar at the time you are testing.

For face-particle this is a check that the particle is contained within the face in 2D (for convex faces this basically means verifying that if the particle forms a triangle with each edge in the polygon, the winding orders of all the triangles formed are the same, i.e. their normals point in the same direction). For edge-edge this is a test that the location where the lines formed by each edge cross each other is between the endpoints for both edges involved. These tests can be done completely in 2D, since everything is coplanar at the time you are testing.

Ah! Now that makes sense. You've been a tremendous help.