Sign in to follow this  
shurcool

Tri-Tri collision resolution along a ray

Recommended Posts

I have a clearly defined problem in 3D space:

Input: two triangles A and B (such that they are intersecting or touching), a unit vector D
Output: the minimum non-negative value k, such that after moving triangle B by kD results in the two triangles no longer intersecting (within some small value)

Conditions: I'm using C++, and Wild Magic 5 library for vector math (it has more functionality for intersections/distance, etc., perhaps everything needed to solve this problem).

My questions are... Is this an easy problem with a well known solution? What would be a good approach to calculate the value of k. It should be reasonably fast.

Any help is greatly appreciated. Thanks!

Share this post


Link to post
Share on other sites
Abstractly, you have a time-varying distance function F(k) that computes the distance between the two triangles at time k. You know that F(0) = 0. Your goal is to compute the smallest kmax > 0 for which F(k) = 0 on [0,kmax] and F(k) > 0 for k > kmax.

You can set this up similar to a root-finding problem. It will be helpful to compute a number m > 0 for which F(m) > 0. You choose such an m so that the AABB of the first triangle and the AABB of the second triangle translated by k*D are not overlapping. Now you must compute kmax in (0,m).

Using bisection, initialize k0 = 0 and k1 = m. Compute kmid = (k0+k1)/2 and F(kmid). If F(kmid) = 0, set k0 = kmid. If F(kmid) > 0, set k1 = kmid. Repeat the bisection until convergence (with floating-point you can repeat until kmid is equal to k0 or k1, or you can set an upper limit on number of bisections).

You can also use the Secant Method (or Newton's method if you dare to implement the derivative function F'(k)). The details are more complicated, but you can take advantage of that fact that F(k) is a convex function. Starting at k0 = m, the iterates should monotonically decrease to kmax.

All you need is an implementation of F(k). Wild Magic 5 has this in Wm5DistTriangle3Triangle3.*, the Get and GetSquared functions with first argument "Real t". The last two arguments are the triangle velocities (zero for your first triangle, D for your second triangle).

Share this post


Link to post
Share on other sites
^^
Seems pretty involved, and you only get an approximation. I think it shouldn't be that hard to solve it directly, for example as follows:

Let P be the plane through A, Q the plane through B, and L the line where P and Q intersect (assuming they aren't parallel).

Then if the two triangles intersect, their intersection will be a segment of this line.

So if we can find this segment, and find an easy way of updating it as B moves, then all we need to do is find the value of k for which the segment vanishes.

And this is in fact pretty easy to do:

Each triangle can be specified as the intersection of its plane and the 3 halfspaces specified by the planes through the edges of the triangle. Taking the intersection of these half spaces and L gives us a set of intervals of the form:

(s,inf)

or

(-inf,s)

If we calculate those intervals for both A and B, we get 6 such intervals. Now the two triangles intersect iff the intersection of these intervals is non empty.

If we move triangle B along D, the intervals of course change, but they always change with a constant velocity (this velocity will be different for each interval though), so if we can find these velocities (lets call them v[i]), then we can easily find the value of k for which the intersection becomes empty.

To calculate these velocities, we can translate B by D (ie. k = 1), calculate another set of segments, and take the difference between the corresponding segments of the initial set as velocity.

It's clear that the intersection becomes empty when one of the segments of the first type and one of the segments of the second type have the same s.

So to find k, we find the minimum solution for

s[i] + k * v[i] = s[j] + k * v[j]
k * (v[i] - v[j]) = s[j] - s[i]
k = (s[j] - s[i]) / (v[i] - v[j])

for any i and j, where both segments are not of the same type.

I hope this is any clear. I could write some example code if you like.

[Edited by - quasar3d on November 14, 2010 7:42:33 PM]

Share this post


Link to post
Share on other sites
Thank you very much! I really appreciate your help.

I'm very busy w/ a paper submission this week, but after this is done, I will start working on implementing a solution to this problem. Ty again. :)

Share this post


Link to post
Share on other sites
I finally got around to working on this problem.

Thanks for the detailed suggestions, they've allowed me to solve the problem.

I've actually found a way of calculating the value of k precisely using the Tri-Tri intersection code from Wild Magic 5 (using triangle velocity and first contact time info):

// Input: two triangles Tri0 and Tri1 (such that they are intersecting or touching), a unit vector Direction
// Output: the minimum non-negative value k, such that after moving triangle Tri0 by k*Direction results in the two triangles no longer intersecting (within some small value)
double UnderCursorMode::ResolveTriTriCollisionAlongVector(Wm5::Triangle3d Tri0, Wm5::Triangle3d Tri1, Wm5::Vector3d Direction)
{
// TODO: Remove magic consts and calculate them based on triangle size/bounding box
const double InitialBacktrack = 10;
double EarliestContactTime = 3 + InitialBacktrack;

// Move Tri0 back before the collision could have occurred
for (int Vertex = 0; Vertex < 3; ++Vertex)
Tri0.V[Vertex] += Direction * InitialBacktrack;

Wm5::IntrTriangle3Triangle3d Intersection(Tri0, Tri1);

// Now test how much it can move forward (towards its original position) before there is a collision
bool Result = Intersection.Test(EarliestContactTime, -Direction, Wm5::Vector3d::ZERO);
if (Result) {
// Return the difference between collision time and Tri0's starting position, this is the value of k
return (InitialBacktrack - Intersection.GetContactTime());
}

// The two triangles were not intersecting at all
return 0;
}


Note that the Tri0 is the moving triangle, and Tri1 is the static one.

Edit: There was a typo in the code, which generated not quite the same output as defined in comments. I've fixed it now. Here is a unit test-case to use.

// Unit Test for ResolveTriTriCollisionAlongVector()
{
Wm5::Triangle3d Tri0(Wm5::Vector3d(-2, 0, 0), Wm5::Vector3d(2, 0, 0), Wm5::Vector3d(0, 5, 0));
Wm5::Triangle3d Tri1(Wm5::Vector3d(0, 1, -1), Wm5::Vector3d(0, 1, 1), Wm5::Vector3d(0, -10, 0));
Wm5::Vector3d Direction(0, 1, 0); Direction.Normalize();

// Input: two triangles Tri0 and Tri1 (such that they are intersecting or touching), a unit vector Direction
// Output: the minimum non-negative value k, such that after moving triangle Tri0 by k*Direction results in the two triangles no longer intersecting (within some small value)
double k = UnderCursorMode::ResolveTriTriCollisionAlongVector(Tri0, Tri1, Direction);
printf("ResolveTriTriCollisionAlongVector(Tri0, Tri1, Direction) Result: k = %f\n", k); // Should be 1.0 for input above
}


[Edited by - shurcool on December 27, 2010 7:07:36 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this