How to check if a line intersects with (triangular) cell?

Support
1

Dear all

I would like to test if a line intersects with a triangle.

If the line is not lying in the same plane as triangle this is done easily with vtkTriangle.IntersectWithLine(). But how can I detect a collision if the line is in the same plane? It looks like vtkTriangle.IntersectWithLine() does not work in this case.

Here a demonstration:

import vtk

# Construct a triangle for this demo.
points = vtk.vtkPoints()
points.InsertNextPoint([0,0,0])
points.InsertNextPoint([1,0,0])
points.InsertNextPoint([0,1,0])
triangle = vtk.vtkTriangle()
triangle.Initialize(3, [0,1,2], points)
# Alternatively, for a poly-data source:
#   cellId = 0
#   triangle = source.GetCell(cellId)

# Perform intersection.
tol = 1e-7
x = [0,0,0]                 # Intersection.
xp = [0,0,0]                # Parametric coordinates of intersection.
t = vtk.mutable(0)          # Line position, 0 ≤ t ≤ 1.
subId = vtk.mutable(0)      # subId? No idea what it is, usually not needed.
p0, p1 = [0,0,1],[1,1,-3]   # p0 and p1 define the line.

hasIntersection = triangle.IntersectWithLine(p0, p1, tol, t, x, xp, subId)
# This returns:
#   hasIntersection: 1
#   t = 0.25
#   x = [0.25, 0.25, 0]

# But what if the line is in the same plane as the triangle?
p0, p1 = [0.2,0.2,0],[0.5,0.5,0]   # Line entirely contained in triangle
p0, p1 = [1.0,1.0,0],[-1.0,-1.0,0] # Line intersects at [0.5,0.5,0] and [0,0,0]
hasIntersection = triangle.IntersectWithLine(p0, p1, tol, t, x, xp, subId)

For the case where p0 and p1 lie in the same plane as the triangle, hasIntersection is always 0. How can I easily deal with both situations, where the line is either in- or out-of-plane?

I also played with vtkTriangle.EvaluatePosition(), but was not able to find a succinct test.

2

What two cases?

3

I updated the question, it should be clearer now. If p0 and p1 lie in the triangle-plane, IntersectWithLine doesn’t work. I wondered how to detect an intersection for that case.

4

Have you tried greater tolerances (e.g. 1e-3, 1e-1, etc.)?

5

Yes, to no avail.

6

Hey folks, another try… Does anyone have an idea?

I could of course write my own intersection algorithm, no big deal. But this problem is so basic I’m sure this has been solved already in VTK.

7

Well, you can do the following:

  1. Determine whether the line lies in the triangle’s plane:
    a) Compute the cross product between two vectors that define the triangle. This yields a vector normal to the triangle;
    b) Compute the dot product of the normal vector against your the vectors that define the lines.
    c) If the dot product is zero, then the line belongs to the triangle’s plane. Proceed to 2);
  2. Determine whether the line lies within, overlaps with an edge, touches, etc the triangle:
    a) Reduce the problem to 2D by ignoring either the x,y or z coordinate (you can write a test to determine which is the best to be ignored).
    b) Use this test: https://gamedev.stackexchange.com/questions/21096/what-is-an-efficient-2d-line-segment-versus-triangle-intersection-test. It is a test written by game developers, so you can rest assured it works and it is fast.

Either this or you have to link against a specialized computational geometry library like CGAL if you want to avoid writing these tests yourself.

1 Like