Hello,
I am new here so please let me know if I placed this topic in the wrong category.
Context:
I have been studying the following paper on Triangle-triangle intersection testing : https://hal.inria.fr/inria-00072100/document and I found out on the following file VTK/vtkTriangle.cxx at master · Kitware/VTK · GitHub that you use your own version of this algorithm.
Three cases are checked in your version:
- All the vertices of triangle 1 are on the plane of triangle 2
- At least one vertex of triangle 1 is on the place of triangle 2, which qualifies it as degenerate. For each of these vertices, you check if they are comprised in triangle 2.
- General case : 1 vertex of triangle 1 on one of the half spaces defined by the plane of triangle 2 and the two others on the other halfspace, and vice versa
Problems ?
Tell me if I am wrong but it seems to me that two other cases should be treated :
4. Exactly two vertices of triangle 1 are on the plane of triangle 2. It is possible that both vertices do not lay within triangle 2, but that a part of the segment formed by these two vertices intersects triangle 2.
5. Points 2. and 4. but for triangle 2 with respect to triangle 1’s plane.
I might be wrong and maybe the first 3 conditions actually encapsulate the last two.
My second issue is that I tested the algorithm on one of my meshes and the algorithm detected some triangle triangle intersections whereas the triangles are far apart from each other.
Here is an example of two triangles that are incorrectly labeled as intersecting:
T1 :
p1 : -94.3637157777778 -22.3637157777778 -505.429755777778
q1 : -95.1414935555555 -23.1414935555556 -504.207533555556
r1 : -93.9192713333333 -23.9192713333333 -504.985311333333
T2 :
p2 : -122.030382444444 -6.03038244444444 -487.096422444444
q2 : -120.808160222222 -6.80816022222222 -487.874200222222
r2 : -121.030382444444 -7.03038244444444 -486.096422444444
The determinants computed during the algorithm.
eps = 5.6843418860808e-14
det1[0] : -6.53699e-13
det1[1] : -8.81073e-13
det1[2] : 2.22222
det2[0] : -1.36424e-12
det2[1] : 7.95808e-13
det2[2] : 2.22222
det(p1, q1, p2, q2) = -4.25930895491734e-13
det(p1, r1, r2, p2) -51.1111111111111
Both last determinants being negative, an intersection is detected.
Here are both triangles in 3D
To avoid such anomalies, one solution I found was to chose a higher eps. On this case, it would mean that the algorithm detects that two vertices of each triangle lay in the plane of the other triangle, but as I said earlier, it seems to me that this case is not well treated.
Any thoughts ?
Thanks in advance