Testing tetrahedron-triangle intersection

1
votes

I want to determine whether a given triangle intersects a tetrahedron. I do not want to compute the solution polygon(if it exists) itself. Is there any library/package/published practical algorithm which can be used to solve this problem directly(unlike my attempt below)?

I think as a last resort I will have to use standard polygon-polygon intersection algorithm implementations to solve this problem indirectly.

My attempt on this problem:
I thought of breaking it into the problem of polygon-polygon intersection. So for each triangular face(say T1) of the tetrahedron and the given triangle T2, I thought of doing the following:

  1. Compute intersection(a line) between planes corresponding to each triangle, say L1.
  2. For each triangle:
    1. For each edge of the triangle say L2, compute point of intersection P between L1 and L2.
    2. Test(maybe using parametric form) of L2, if the point lies on the edge L2.

If for both triangles T1 and T2, there exists at least one edge on which the intersection point P lies, then it implies that the triangles(and hence the given tetrahedron and the triangle T2) do intersect.

2
algorithmcomputational-geometry
Due to the convexity of the geometric entities, you can cast the problem as a linear program in 7 positive unknowns, withd equations expressing that the admissible points belong to the inside of the tetrahedron and the triangle. Solve by the simplex algorithm. – Yves Daoust
@YvesDaoust Would you please elaborate on what those 7 unknowns will be? – Pranav
The weights of the convex combinations of vertices (3 for triangle, 4 for tetrahedron). en.wikipedia.org/wiki/Convex_combination – Yves Daoust
@YvesDaoust So as I understand your approach, this tetrahedron-triangle intersection problem can be translated into a linear feasibility problem, where the constraint equation can be of form: alphaP_{tet}=betaP_{tri}, where alpha,beta are weight vectors for points of tetrahedron and triangle respectively, P_{tet} and P_{tri} are coordinate vectors of tetrahedron and triangle respectively. – Pranav
That's it. There is an intersection iff the linear problem is feasible. Algebraically speaking, the problem is solved by evaluating the signs of a number of 4x4 determinants ("on which side of this plane am I ?" = "signed volume of simplexes") and discussing the outcomes. This is the same kind of machinery as used in my answer (possibly complemented by bounding box tests), where part of the work takes place in 2D space, using 3x3 determinants. – Yves Daoust

2 Answers

0
votes

I just found a function in CGAL library CGAL::do_intersect(Type1< Kernel > obj1,Type2< Kernel > obj2 ) for computing intersection between two geometric objects. It permits Type1 and Type2 to be Triangle_3<Kernel> and Tetrahedron_3<Kernel> respectively.

0
votes

Create an orthonormal frame based on the triangle (origin at some vertex, axis X using the direction of some side, axis Y and Z using the direction of another side and Gram-Schmidt formulas).

Transform the coordinates of the 3 + 4 vertices to the new frame.

If all Z of the 4 tetrahedron vertices are of the same sign, there is no intersection. Otherwise, find the 3 or 4 intersection point of the edges into XY, by linear interpolation on Z.

Now you need to check for intersections between a triangle and a triangle or (convex) quadrilateral, in 2D. You can solve that by means of a standard clipping algorithm, made simple by convexity of the polygons.

As an easy optimization, note that it is useless to compute the Z of the triangle vertices (=0), and the XY of the tetrahedron vertices before you know that there is a possible intersection.

You can also speedup the polygon intersection process by first using a bounding box test.