Sign in to follow this  

tri-tri min seperation

This topic is 4834 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hiya peeps. Does anyone know an efficient way to determine closest points between tris in 3D or know were I could find out? The way I currently do it is to surround each tri with planes and use half space testing to determine the relation between the tris so I know which verts and edges to test against each other. This seems a bit brute force though and I'm sure there's probably some nice abstract maths way of doing this that'll be much faster. Cheers.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The minimum distance between any point of one triangle to any point of another?

Share this post


Link to post
Share on other sites
Hmmm.

Loop through each vertex of the triangle you want to test, storing the vector of their position difference with a vertex of the other triangle IF it's less than the 'current' distance (start it at something big)... at the end, the vector = the minimum distance.

Also brute force but better than using planes hopefully :S

Share this post


Link to post
Share on other sites
I wish it were that simple :). What if the closest points happen to lie on tri edges or in the middle of the tri face?? For a complete brute force method like you suggest you'd need to do 9 line segment to line segment tests and 6 vert to tri face tests which would involve projecting the vert on the plane and checking for inclusion in the tri. Nasty!! Thats why I currently use a sort of voronoi region phase first to narrow down the combinations which need checking and avoid pt in tri tests. I'm still sure there must be a quicker way though.

Share this post


Link to post
Share on other sites
Yes generalized Voronoi diagrams are nearly always the way to accelerate things. Specially if you want the complete contact informations (when, where, normal, type : d-facets concerned).

I have studied the exact predictive collision detection algo for triangle-triangle on paper this evening, mostly a draft atm. It looks very optimizable specially with SIMD.

It's although very linked to the separating plane theorem. However it's exactly the same as for any convex convex except the connexity of the d-facets is a constant and the number of cases bounded. You also only have two faces. This means that beyond the general case (convex-convex), specializing the algo can boost things up.

A few of my conclusions :

- The principle would be to track the 2 nearest d-facets all the time.

- At init, if colliding pair info is not cached from the previous frame, it takes between 1 to 6 plane tests to locate one vertex of T1 in the diagram of T0 : that is find its closest d-facet. Then connexity of T1 can then be exploited to find the two nearest d-facets. The same kind of algo is then used for collision detection in continuous time (quasi exact prediction).

For example : Imagine T0.ABC is the closest d-facet of T0 to T1.A. Then if T1.B and T1.C are more distant than T1.A from T0.ABC, the two nearest d-facets are found. Else you must check one of the edges connex to T1.A against T0 ... It's a kind of limited recursion in both connexity graphs (<=> Voronoi diagram). It always ends up with a case where minimality is easilly characterized and proven.

- A way to reduce computations could be to work mostly in 2D. I mean store a quaternion of T0 in it's local mesh coords (static data) and then work in a frame where T0 is in the plane z=0 and let T0.A be the origin. The nodes of the diagram then become 2D edges, z component discarded in most computations. This speeds things up a bit.

- This may lead to eventually a slightly different approach. Intersect T1 and z=0. Then it's a 2D problem between an edge and a triangle. A special case is when the edge is a point, that's when contact T0-T1 is face-vert.


Remember that I focus here on predictive col. det. For static (frozen time) collision requests there are many methods with quick early rejections, just Googleand you'll find many. I am more in the case, where after a swept sphere tree recursion, contact is very probable, and thus finding this contact with all relevant info is the crux of the matter.

[Edited by - Charles B on September 17, 2004 7:55:58 PM]

Share this post


Link to post
Share on other sites
Thanks for the input. I was hoping maybe there wouls be a purley maths solver type way that might have been quicker since the mathematics of triangles is well understood. From the sounds of things though maybe there isn't a significantly faster way and I'm already close to optimality. There are many things in your post that should help me squeeze some extra speed out of it since the algo I'm currently using is in a rough state at the mo. Cheers. I especially like the idea about projecting the tris onto a plane to make it a 2D case. I imagine when converting back to 3D closest points though that there may be a loss in accuracy along the projected planes normal direction. Do you know if this is the case and if so is the error acceptably small??

Quote:
Original post by Charles B
I am more in the case, where after a swept sphere tree recursion, contact is very probable, and thus finding this contact with all relevant info is the crux of the matter.


Excellent cause this is what I'm currently dealing with. I've managed to compress my sphere trees quite a bit which lets me have a higher depth than previously. Hence when I get down to closest tri point determination I think its sensible to assume that they will collide and they're currently close enough to just treat them as static. I'm not totaly convinced by all my assumptions though since I got my first test of this system running last night (just bouncing two objects of each other) and they tend to kick rather violently. This might just be a simple maths error/bug or maybe it indicates a serious problem with my method. I havn't had time to look into that close yet but if you can think of any potential flaws in this system that might cause this I'd appreciate the input. Cheers for all your help.

Share this post


Link to post
Share on other sites
Quote:
Original post by Motorherp
I was hoping maybe there would be a purley maths solver type
way that might have been quicker since the mathematics of triangles is well understood.

There are quicker ways for bool Intersect(Geom, Geom) like functions. But for physics such functions are not very useful as they do not return nearest points or distances. They are more suited for clipping : merging arbitrary meshes (Triangle, Triangle), view frustum clipping (Sphere, Convex) or (AABox, Convex), etc...

Quote:

I especially like the idea about projecting the tris onto a plane to make it a 2D case.

It's not exactly projecting onto a plane. It's changing of frames so that most z components are removed. Triangle DEF is still 3D, but in practice, za=zb=zc=0 will remove many computations, as if we were in 2D.

Example:

Seeking the nearest d-facet to D

. .
. . E
A.
. /\ D .
. / \ . F
./____\.
C. .B
. .

Testing AB :

AB is the d-facet of (ABC) closest to D iff :

(it's in the Voronoi region of AB)

AB * perp(AD) > 0
&& AB * AD > 0
&& AB * DB > 0

If it's the case, the min distance is :
AD * normalize(perp(AB))


Every vector here haz z removed (since AB.z=0). But in 3D the result would be the same. BTW this can help you vizualize your algo in 2D for a unitary test aimed at solidifying your algo and code. For micro optimizations, 3DNow could be very useful in this case. SSE could let you process two segment boundaries (<=> planes boundaries) at once.

Quote:

I imagine when converting back to 3D closest points though that there may be a loss in accuracy along the projected planes normal direction. Do you know if this is the case and if so is the error acceptably small??


There is absolutely no reason for loosing precision. We are in a simplified 3D frame which may be even better for precision BTW. Usually triangles are part of meshes. Thus you have to compute in the local frame of one arbitrarilly chosen meshe. This implies multiplying matrices or quaternions. Here you just push a bit further and require to be in 'the frame' of one triangle. You can choose A as origin and AB colinear with X, Z to the normal. BTW this simplifies computations on edge AB.

When you test triangle ABC against several others, temporarilly cache the transfo of ABC in it's 'own' frame. Then you only have to transform DEF to the local coords then by translation -A and Quat(ABC). This is a concatenation of affine rotations. A quat*quat takes 20 cycles in my library. Then a quat*vert is as speedy as a matrix*vert (if you simply transformed to local mesh coords). So it only costs one quat*quat and one quat*vert in the transformation concatenation stage. I imagine the benefits later are worth this overhead. In fact we 'cache' one of the properties of the problem : ABC is planar. Let's 'anihilate' the computations due to this plane.

Quote:

I havn't had time to look into that close yet but if you can think of any potential flaws in this system that might cause this I'd appreciate the input. Cheers for all your help.

I can not answer blindly. There are many possibilities to add bugs in geometric algos. Maybe you can send your code sample via mail and if I can find a bug in a quick glance, I will feed-back.

[Edited by - Charles B on September 18, 2004 8:48:10 AM]

Share this post


Link to post
Share on other sites
I use the separation axis algorithm. I take the separation axis which as the minimum projected distance. Or in case of an intersection, I take the axis with the minimum projected intersection distance.

If the triangles are translating, the same principle can apply. calculate the time of intersection on each projected axis (calculate 1D intervals for each triangles like in the static case, and project the velocity on the axis and calculate the time the intervals 'hit'), take the minimum positive. If minimum positive greater than the timestep, no collision. Else, this is your jrojected time of collision.

If all negative, you have an intersection already, then take the maximum negative as the intersection data.

For the dynamic case, the separation axes are the same as in the static case (where you have to test 11 axes if I remember correctly, in the case of tri-tri tests), plus you have to add the velocity vector as an extra separation axis to test.

the index of the separation axis selected gives you which feature collided/intersected/are the closest.

Share this post


Link to post
Share on other sites
Cheers for all the info Charles. It looks like from here on in though its only small optimisations that can be made and I might be better putting my efforts else where for the time being. Still its always good to come back and optimise these types of base routines as much as possible when time allows since you'll feel the advantage in any code you write that uses that library.
Quote:
Original post by Charles B
I can not answer blindly. There are many possibilities to add bugs in geometric algos. Maybe you can send your code sample via mail and if I can find a bug in a quick glance, I will feed-back.

Don't worry I'd never ask anyone else to debug my code, I was more asking if you are aware of any general collision issues from using this method that might result in that behaviour.

Hi Oliii. I hadn't realised seperating axis could be used to predict collision between moving objects. I might look into this further since it'll let me remove the restriction that leaf nodes have to be small enough that the assumption that tris are close enough they can be considered colliding holds.

Cheers for your help everyone :)

Share this post


Link to post
Share on other sites
Oii, in the case of convex/convex Voronoi based algos are just an extension of the separation plane.

BTW, semantically I prefer saying plane than axis (normal of the said plane, because it adds the info where in affine space. It helps thinking in terms of infinite half spaces instead of 1D projections which is equivalent. Usually the plane is a support plane or at least attached to an edge of one of the convexes.

Next Voronoi is just a way to use connexity info to speed up the search of the 2 nearest d-facets (equivalently axis) in static case with no info cached from previous frame. It also greatly helps once a separating plane is invalidated.

For triangle triangle the raw power axis search requires to find a maximum (of minima) for :
- 9 edge/edge axes
- 2 face/vert axes
11 you are right. In each case you need 3*2 vertices be checked.
So 66 dot products. Am I right ?

The generalized Voronoi 3D algo takes 1-6 dot products to find the cell of (ABC) closest to D. Then connexity usually sorts E,F in a few iterations more (say 2-6). So it's probably 5 times faster 'algorithmically' in the triangle/triangle case.


More, this connexity info is particularilly useful when you want to deal with non translating movements, including fast rotations and parabolic movements of the mass center. Then it's easier to make a robust algo that will not miss any potential penetration that would happen during a short duration.

When you are in a Voronoi cell of d-facet Fa of A only 3 types of events happen to the nearest d-facet Fb of B and you treat whichever happens first :
a) Fb is beaten by one of its neighbours Fb', seek(Fa, Fb').
b) Fb goes out of cell(Fa), seek(Fa', Fb).
c) Fb hits Fa : all algo done, first contact found.

'Your' method deals very badly with cases a) and b). I know that in general c) happens first, specially if triangles are translating. But for a) and b), you need to compute the 66 dot products don't you ?

Share this post


Link to post
Share on other sites
... although you have to be careful in degenerate cases. I prioritise the axes, so that in case I got a degenerate case, or if two axes return the same intersection depth/collision time, I use the most sensible.

goes like something like this...


bool Collide(CTri Tri1, CTri Tri2, Vector Velocity, float &fCollParam, Vector& vCollNormal)
{
// max of 12 axes to tests.
// there are several types of test we can perform
// depending on the triangle configuration. axes are
//------------------------
// static case
//------------------------
// Tri1.Normal
// Tri2.Normal
// Tri1.E0 x Tri2.E0
// Tri1.E0 x Tri2.E1
// Tri1.E0 x Tri2.E2
// Tri1.E1 x Tri2.E0
// Tri1.E1 x Tri2.E1
// Tri1.E1 x Tri2.E2
// Tri1.E2 x Tri2.E0
// Tri1.E2 x Tri2.E1
// Tri1.E2 x Tri2.E2
//------------------------
// dynamic case (most frequent)
//------------------------
// Tri1.Normal
// Tri2.Normal
// Velocity
// Tri1.E0 x Tri2.E0
// Tri1.E0 x Tri2.E1
// Tri1.E0 x Tri2.E2
// Tri1.E1 x Tri2.E0
// Tri1.E1 x Tri2.E1
// Tri1.E1 x Tri2.E2
// Tri1.E2 x Tri2.E0
// Tri1.E2 x Tri2.E1
// Tri1.E2 x Tri2.E2
//------------------------
// coplanar tris, static case
//------------------------
// Tri1.Normal
// Tri1.E0 x Tri1.Normal
// Tri1.E1 x Tri1.Normal
// Tri1.E2 x Tri1.Normal
// Tri2.E0 x Tri1.Normal
// Tri2.E1 x Tri1.Normal
// Tri2.E2 x Tri1.Normal
//------------------------
// coplanar tris, dynamic case
//------------------------
// Tri1.Normal
// Velocity
// Tri1.E0 x Tri1.Normal
// Tri1.E1 x Tri1.Normal
// Tri1.E2 x Tri1.Normal
// Tri2.E0 x Tri1.Normal
// Tri2.E1 x Tri1.Normal
// Tri2.E2 x Tri1.Normal

Vector vAxes[12];
float fSep[12];
int iNumAxes;

if (!CalculateCollisions(Tri1, Tri2, Velocity, vAxes, fSep, iNumAxes))
return false;

int iSepAxis=-1;
float fSepD;
Vector fSepNormal;

for(int i = 0; i < iNumAxes; i ++)
{
float a2 = vAxes[i] * vAxes[i];

if (a2 < 0.000001f) // degenerate
continue;

float d = fSep[i] / a2; // normalise the axis parameter

bool bCandidate = false;

// the first valid axis we found. use it
if (iSepAxis == -1)
{
bCandidate = true;
}
else
{
// we are dealing with interections?
if(fSepD < 0.0f)
{
if (d > fSepD)
bCandidate = true;
}
// we have found at least one collision
else
{
if (d >= 0.0f && d < fSepD)
bCandidate = true;
}
}
if (bCandidate)
{
iSepAxis = i;
fSepD = d;
vSepNormal = vAxes[i] / sqrt(a2); // normalise axis
}
}

if (iSepAxis == -1)
return false;

fCollParam = fSepD;
vCollNormal = vSepNormal;
return true;
}

Share this post


Link to post
Share on other sites
I don't usually need to calculate the distance all the time, merely if they collide, and how. I guess I'm therefore off-topic. I'll read into that Voronoi stuff. It looks better for general convex structures than just triangles. I must say the

I prefer axis than plane, because ultimately, you end up doing 1D calculations, therefore along a line :) So I'm all the way round.

I think V-clip uses Voronoi regions. Well, another thing to research.

Share this post


Link to post
Share on other sites
Indeed V-Clip does use voronoi regions extensively. I've tried creating a V-Clip algo of my own but its really not easy to implement. I almost got it working with all my feature walking going in the right directions. The only problem was I became unstuck when verts lie very close or on region boundaries and math error could cause my feature walking to step back and forth accross this boundary in an infinite loop. Eventually I was about to throw my laptop through the window and so put it on the back burner. Maybe I'll come back to it sometime in the future though. If you're interested though:

http://www.merl.com/reports/docs/TR97-05.pdf

PS: Cheers for the code snippet. Much appreciated :)

Share this post


Link to post
Share on other sites

This topic is 4834 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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