# Triangle-triangle intersection detects incorrect intersection.

**URL:** https://discourse.vtk.org/t/triangle-triangle-intersection-detects-incorrect-intersection/6258
**Category:** Development
**Created:** [July 28, 2021, 9:00am UTC](https://discourse.vtk.org/t/triangle-triangle-intersection-detects-incorrect-intersection/6258 "2021-07-28T09:00:52Z")
**Posts on this page:** 1
**Page:** 1

<div class="post-metadata">

### Author: ![antomaxi](https://discourse.vtk.org/user_avatar/discourse.vtk.org/antomaxi/32/3714_2.png) [@antomaxi](https://discourse.vtk.org/u/antomaxi)
#### Post date: [July 28, 2021, 9:00am UTC](https://discourse.vtk.org/t/triangle-triangle-intersection-detects-incorrect-intersection/6258/1 "2021-07-28T09:00:52Z")

</div>

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](https://hal.inria.fr/inria-00072100/document) and I found out on the following file [VTK/vtkTriangle.cxx at master · Kitware/VTK · GitHub](https://github.com/Kitware/VTK/blob/master/Common/DataModel/vtkTriangle.cxx) that you use your own version of this algorithm.

Three cases are checked in your version:

1. All the vertices of triangle 1 are on the plane of triangle 2
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.
3. 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

 ![Capture d’écran 2021-07-28 à 10.55.39](https://discourse.vtk.org/uploads/default/original/2X/7/7143bf09a22a023a838627199c537c4acb7d4eee.png)

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