So will there be cases when none of the edges of either triangle pass through the other triangle, but the two triangles intersect? I can only think of the special cases where an edge of a triangle is on the plane of the other triangle, and the edge goes through that triangle in the plane. But this should also be considered as the edge going through the triangle, right?
penguin
I was thinking, if the two triangles overlap so much such that it almost seems like they're the same triangle, would this reduction to edge-triangle detection make sense? It seems like it would be much harder to do. And also, what if the triangles are on the same plane and they overlap a little, what would be the edge in this case?
bpopeck
I think that every time two triangles intersect at least one of the edges will intersect the other triangle.
If the triangles are co-planar, then either the edges overlap or one triangle is contained in the other (so the edges of the smaller triangle are in the intersection).
If the triangles are not co-planar, then the intersection will be a line segment. The line segment will be on the line of intersection between the planes containing the triangles, and the endpoints of the line segment will be points at which a triangle edge intersects the line. So those edges at the endpoints must intersect the other triangle.
jacheng
So in the case of the moving triangle, you would treat time as another dimension and then the shape would be the triangle's area with an 4th dimension value as T, and then to determine if two moving triangles intersect, you would check if the corresponding 4D shapes intersect. Are there closed form formulas for doing this check?
keenan
@All: Good discussion. Yeah, definitely if two triangles intersect then an edge of one triangle has to touch the other triangle in at least one point. Numerically, however, things can get nasty if the triangles are close to co-planar, similar to this slide.
keenan
@jacheng If an edge (which is linear) moves along a linear trajectory in time, then it will trace out a bi-linear patch in space-time. I.e., you can write the location of an edge at barycentric coordinate $s$ and time $t$ as
where $\mathbf{a}_0, \mathbf{b}_0 \in \mathbb{R}^3$ are the locations of the edge endpoints at time (t=0), and $\mathbf{a}_1, \mathbf{b}_1$ are the endpoint locations at time $t=1$.
To find the exact location and moment where two edges intersect, you have to solve the equation $f(s,t) = 0$ for $s$ and $t$. This is a quadratic rather than linear equation, but is still not too hard to solve. If there are only solutions for $s$ or $t$ outside the interval $[0,1]$, then there is no collision.
This of course only tells you how to do a segment-segment collision test in time. Can you build on this idea to do a triangle-triangle collision test in time?
So will there be cases when none of the edges of either triangle pass through the other triangle, but the two triangles intersect? I can only think of the special cases where an edge of a triangle is on the plane of the other triangle, and the edge goes through that triangle in the plane. But this should also be considered as the edge going through the triangle, right?
I was thinking, if the two triangles overlap so much such that it almost seems like they're the same triangle, would this reduction to edge-triangle detection make sense? It seems like it would be much harder to do. And also, what if the triangles are on the same plane and they overlap a little, what would be the edge in this case?
I think that every time two triangles intersect at least one of the edges will intersect the other triangle.
If the triangles are co-planar, then either the edges overlap or one triangle is contained in the other (so the edges of the smaller triangle are in the intersection).
If the triangles are not co-planar, then the intersection will be a line segment. The line segment will be on the line of intersection between the planes containing the triangles, and the endpoints of the line segment will be points at which a triangle edge intersects the line. So those edges at the endpoints must intersect the other triangle.
So in the case of the moving triangle, you would treat time as another dimension and then the shape would be the triangle's area with an 4th dimension value as T, and then to determine if two moving triangles intersect, you would check if the corresponding 4D shapes intersect. Are there closed form formulas for doing this check?
@All: Good discussion. Yeah, definitely if two triangles intersect then an edge of one triangle has to touch the other triangle in at least one point. Numerically, however, things can get nasty if the triangles are close to co-planar, similar to this slide.
@jacheng If an edge (which is linear) moves along a linear trajectory in time, then it will trace out a bi-linear patch in space-time. I.e., you can write the location of an edge at barycentric coordinate $s$ and time $t$ as
$$f(s,t) = (1-t)((1-s)\mathbf{a}_0 + s\mathbf{b}_0) + t((1-s)\mathbf{a}_1 + s\mathbf{b}_1),$$
where $\mathbf{a}_0, \mathbf{b}_0 \in \mathbb{R}^3$ are the locations of the edge endpoints at time (t=0), and $\mathbf{a}_1, \mathbf{b}_1$ are the endpoint locations at time $t=1$.
To find the exact location and moment where two edges intersect, you have to solve the equation $f(s,t) = 0$ for $s$ and $t$. This is a quadratic rather than linear equation, but is still not too hard to solve. If there are only solutions for $s$ or $t$ outside the interval $[0,1]$, then there is no collision.
This of course only tells you how to do a segment-segment collision test in time. Can you build on this idea to do a triangle-triangle collision test in time?