CODEWITHSUNDEEP
algorithmcomputational-geometry
Pranav
Pranav

Reputation: 475

Testing tetrahedron-triangle intersection

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.

Upvotes: 1

Views: 1493

Answers (2)

user1196549
user1196549

Reputation:

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.

Upvotes: 1

Pranav
Pranav

Reputation: 475

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.

Upvotes: 0

Related Questions