PDA

View Full Version : Distance between two triangles



CatDog
12-02-2008, 08:02 AM
Hi,

I need to know the distance between two triangles ABC and DEF. To be precise, I just want to know whether the distance between two triangles exceeds a fixed threshold c. First idea is of course to compute the two closest points and check their distance against the threshold. That's easy, but I have the feeling that there must be better (=faster) solutions.

Since there are some sophisticated algorithms for testing if two triangles touch (distance=0), maybe there's also one that fits my requirements (distance<=c)?

(Oh, and as OpenGLs basic drawing primitives are triangles, this is totally on-topic, isn't it? :) )

CatDog

Budric
12-02-2008, 09:47 AM
First you have to define what you mean by distance between two triangles. You could compute the centroid for each triangle and take a distance between that. That's a valid distance between two triangles.

I can't prove it but I suspect any definition of distance you choose won't help you decide if two triangles intersect. Look up "separating axis theorem" if you want to check intersection.

I think GL_QUADS is a primitive opengl can rasterize directly without converting to triangles...so no. But that's just a guess.

CatDog
12-02-2008, 12:23 PM
First you have to define what you mean by distance between two triangles.
Ok, lets assume the triangles T1 and T2 are disjoint and NOT intersecting. (Eliminating the special cases.)

- Now find the two closest points P1 and P2 of the two triangles. That's not too difficult, but very expensive (you need in fact 6 vertex-triangle tests and 9 edge-edge tests).

- Then compare the distance of P1-P2 with the threshold c. If it is lower, the result is "true".

That works. But it's a lot of computation, so it's slow! My question is: can this be done any faster?

*edit*
It boils down to this function:
// Results false if two triangles are farther away then MaxDist
function TestTriangleDistance( A,B,C: Vec3; D,E,F: Vec3; MaxDist: Float ): Bool;

*edit2*
In "Real-Time Rendering" (Akenine-Möller/Haines), 2nd Ed., ch. 14.7.3 this kind of test is called tolerance verification. But they only give an informal description for convex polyhedra, the general case.

CatDog

Komat
12-02-2008, 03:50 PM
What about early out in the "they are certainly closer" (distance of centroids is smaller than limit) and "they are certainly further" (distance of bounding spheres with centers in centroids is bigger than limit) and using the precise algorithm on the rest.

Jackis
12-03-2008, 06:31 AM
Maybe this could help:

http://www.realtimerendering.com/intersections.html
http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/opttritri.txt

[EDIT]
By the way, Komat is right. If you want to improve verification, it's quite important to use some "early" tests. Like computing centroid first, getting bound sphere radius and testing spheres, which is very fast and can discard lots of future work.

CatDog
12-03-2008, 07:04 AM
Heck I didn't know they did a 3rd edition of "Real-Time Rendering" in the meantime! Anybody knows if it's worth it, compared to the 2nd?

As listed in the link, there are a number of very fast intersection tests around, but I can't find one for that "tolerance verification" of triangles. (Other than my naive method.)

Yes, early outs are always used. This routine is the very last test of a collision hierarchy, so all the easy bounding tests and such have been already performed. Testing if the distance of centroids is smaller than the limit sounds like a good addition!

CatDog

Jackis
12-03-2008, 09:26 AM
CatDog,

It's a little bit offtop about RTR book, but if you want to know, what's new - so look here: http://www.realtimerendering.com/book.html