continous triangle-triangle intersection test

[backtobedlam]

there are two triangles in the sence,one is movable,the other is not,the vertex of the movable triangle move linearly,now,the position of the three vertex of the movable triangle are known at two continous moments,how can I find out whether the two triangles interseced in this process，and if they really intersec,when they began to intersect?

[JoeJ]

Fixed tri is TF, lying on plane PF
Moving tri is T0 & T1, at planes P0 & P1

1. Check if all vertices T0 & T1 are on one side of PF - if so no intersection.
2. Take each moving vertex path (a line) and intersect with PF, giving a new triangle.
3. Clip this triangle between both planes P0 & P1 (like frustum clipping) giving a new polygon.
If this polygon has zero vertices, no intersection.
4. Clip this polygon inside TF (could be done in 2D). If polygon now has zero vertices, no intersection.
Else check distance poly vertices with plane P0 to find point of first intersection and time.

I'm not sure this works but think so. There should be something to find with google
I'm sure there are optimisations...

[backtobedlam]

Fixed tri is TF, lying on plane PF
Moving tri is T0 & T1, at planes P0 & P1

1. Check if all vertices T0 & T1 are on one side of PF - if so no intersection.
2. Take each moving vertex path (a line) and intersect with PF, giving a new triangle.
3. Clip this triangle between both planes P0 & P1 (like frustum clipping) giving a new polygon.
If this polygon has zero vertices, no intersection.
4. Clip this polygon inside TF (could be done in 2D). If polygon now has zero vertices, no intersection.
Else check distance poly vertices with plane P0 to find point of first intersection and time.

I'm not sure this works but think so. There should be something to find with google
I'm sure there are optimisations...

In step 3,the space between P0 and P1 may not be a frustum!
Because the moving direction of each vertex may be different,then the line made by adjective traving vertex may not on the same plane
if this happen,the process of cliping triangle in step 3 may be a bit difficult！

[JoeJ]

Step 3 means the two planes build from the 2 triangles at both points in time, so they are true planes.
I know building a plane from 2 lines does not work, but there is no need to do so with my solution.

I'm still pretty sure it works, the only case i didn't think much about is: What happens if those planes intersect inside the triangle...
But that special case should be easy to handle when anything else works.

[backtobedlam]

it seems that I miscomprehend what you mean, and I'm now working on the algorithm,I found another problem,
the algorithm to calculate the area of intersection for two triangles in the same plane is more complicated than I think,
is there any simple and robust algorithm for this?

[JoeJ]

You mean Step 4?
You can use the "frustum clipping" here again.
Construct 3 planes by cross (TF.normal, TF.edgevector(0..2)).
So you get a frustum without perspective and 3 planes to clip the other polygon.
Here everything is convex and so it's easy. Clilpping nonconvex polys would be pain.
Doing the same in 2D is no speed up today i think.

Edit: If you don't have a clip convex polygon against plane function, google for Michael Abrashs Graphics Black Book.
Oh, i still have his code handy:

Code: Select all

/////////////////////////////////////////////////////////////////////
// Clip a polygon to a plane.
/////////////////////////////////////////////////////////////////////
int ClipToPlane(polygon_t *pin, plane_t *pplane, polygon_t *pout)
{
    int     i, j, nextvert, curin, nextin;
    double  curdot, nextdot, scale;
    point_t *pinvert, *poutvert;

    pinvert = pin->verts;
    poutvert = pout->verts;

    curdot = DotProduct(pinvert, &pplane->normal);
    curin = (curdot >= pplane->distance);

    for (i=0 ; i<pin->numverts ; i++)
    {
        nextvert = (i + 1) % pin->numverts;

        // Keep the current vertex if it's inside the plane
        if (curin)
            *poutvert++ = *pinvert;

        nextdot = DotProduct(&pin->verts[nextvert], &pplane->normal);
        nextin = (nextdot >= pplane->distance);

        // Add a clipped vertex if one end of the current edge is
        // inside the plane and the other is outside
        if (curin != nextin)
        {
            scale = (pplane->distance - curdot) /
                    (nextdot - curdot);
            for (j=0 ; j<3 ; j++)
            {
                poutvert->v[j] = pinvert->v[j] +
                    ((pin->verts[nextvert].v[j] - pinvert->v[j]) *
                     scale);
            }
            poutvert++;
        }

        curdot = nextdot;
        curin = nextin;
        pinvert++;
    }

    pout->numverts = poutvert - pout->verts;
    if (pout->numverts < 3)
        return 0;

    pout->color = pin->color;
    return 1;
}


[Brendon77]

Simple Algorithm is a simple language of algorithm language and Robust Algorithm is testing of error and how effective algorithm.

[corbingravely]

Why don’t you people use a simple logic? Your second question is when they begin to intersect if at all they intersect? The answer might be simple. They will intersect only once. A perfect intersection is one when at least one of the vertices intersects with one of the vertices of the triangle. And that can happen only once. Now coming to you first question. The problem with your question is that it does not mention any points of direction and dimensional points are very far from this question. So Let us assume everything. It depicts in the question that the movable triangle’s vertices move linearly. That means the stationary triangle’s vertices should be in linear with any one of the vertices of the moveable triangle. Also the stationary triangle should be in the path of the moving triangle. Any other point will be a non intersecting point.

[JoeJ]

Turing test failed

[manny]

Turing test failed

[Julio Jerez]

The most robust algorithm I know is numerical stable and accurate and conceptually simple, but not the fastest.

basically you take th evertices of the tow trianagble an crate an array of vetuices by calculation all possible difrences

Qij = Diff (Pi - Pj)
I and j are the indices to the triangle
this is called the Minskousky difference to tow shapes
now you the array Qij and build the convex hull.

if the point p(0, 0, 0) is inside the convex hull, the triangles intersect, an the distance form the origin form the point to the closest face is the normal of the intersection plane.

if the origin is not inside, the distance from the origin to the closet point on the convex hull is the distance to intersection, for if the triangle has a linear velocity all you nee to do is subtract the velocities and if the projection along the mink distance is positive, the time T to cover that distance by the projected velocity is the time to Impact.

the hard slow part is building the convex hull, but you are dealing with triangles,
the calculation can be done in contact time. by any brute force algorithm.

The algorithm above is mathematically rigorous and numerically stable,
it will give the correvt 100% of the time with zero error.


There is a popular algorithm that deal with the part when the shape are disjoint, and is call GJK
this algorithm iteratively builds directed minimal partial convex hull (a tetrahedral) and test the distance as it keep doing until the distance does not decrease anymore.

this algorithm is Numerically unstable, because it can get into point of local minimal where the tetrahedral has face that are almost coplanar and the distance to the origin does not decrease.
This happen when the origin is very close to the surface of the convex hull.
The algorithm is unstable and another more complex version have to be use why is call the expanding polytope, which is also complex.
Both are Numercially unstable and it takes a lot of tuning and tweaking to get JGK to work reliably, but since they are very fast, they are one that most collision library use.

In your case I would go for the method I decribe above.

basically after you build the convey hull of a 9 point array of vertices, you problem is converted to a

find the triangle who's distance is closer to the orgin, of all the tringe face of a conve hull of a fix number of faces.
If the distance is positive the triangle are disjoint and you can calculate the time to impact.
if not then they intersect and you can even determine what king of intersection by checking what element of the original triangle form the face.