# tri-tri min seperation

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

## 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 on other sites
The minimum distance between any point of one triangle to any point of another?

##### Share on other sites
Yes but I also need to know the points

##### 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 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 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 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 BI 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 on other sites
Quote:
 Original post by MotorherpI was hoping maybe there would be a purley maths solver typeway 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 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 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 BI 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 :)

• 10
• 19
• 14
• 19
• 15