8
$\begingroup$

First, I am far from a mathematician, and this question may be easy, if that's the case, please don't hesitate to let me know.

Suppose I have 2 tetrahedra (2 3D simplex), with known ABCD and DEFG coordinates in euclidean space.

Is there an algorithm/approach to known whether this tetrahedra intersect, and if so know the volume of that intersection in a general case?

I can imagine that the first question is not hard to solve, e.g. checking if the 4 vertices of a tetrahedron are inside the other one, but there may be smarter approaches, hence I will leave the question there.

EDIT: As pointed out in the comments, the intersection may be a bit more complicated than I assumed.

$\endgroup$
6
  • 1
    $\begingroup$ It is possible for two tetrahedra to intersect even if neither has a corner that is inside the other one. For example, connect every other corner of a cube to form a tetrahedron, and then connect the remaining corners to form a different tetrahedron. $\endgroup$ Jan 13, 2015 at 17:14
  • $\begingroup$ @HenningMakholm Indeed, but in that case the volume of the intersection would be zero, and that's what I am actually looking for. Nice observation though! $\endgroup$ Jan 13, 2015 at 18:04
  • $\begingroup$ No, the intersection in that case is the octahedron with vertices in the center at each side of the cube. That does have positive volume. $\endgroup$ Jan 13, 2015 at 18:06
  • 1
    $\begingroup$ This (computationally complex) problem has been dealt with before many times. Just google "intersection of two tetrahedra". It should be specified in the question whether regular tetrahedra are meant or just $3$-simplices in ${\mathbb R}^3$. $\endgroup$ Jan 13, 2015 at 18:37
  • 1
    $\begingroup$ @ChristianBlatter actually, I failed to find proper information goggleing (and in stackexchange), I tried before posting. I definitely will continue with the search by my own, but I thought it was an appropriate question in here! Thanks for the correction, I added the information you suggested, however my limited knowledge of maths doesn't get me to the difference between tetrahedral and 3-simplex. Actually wikipedia tell's that a 3-simplex is a tetrahedral. $\endgroup$ Jan 13, 2015 at 20:44

1 Answer 1

2
$\begingroup$

Here is a method which is not optimal in terms of the number of things to check, but is easy to implement...

To detect ANY intersection between tetrahedrons A and B, you just have to make sure that A lies on the outside of any half-space defined by the 4 facets of B, and vice versa. If this is not the case, then there is an intersection. This test can be accomplished by the orient3d predicate give here. This is equivalent to applying the Hyperplane separation theorem. A faster method is here with code.

To compute the volume of intersection, you need the boundary representation of the intersection volume (in terms of vertices, edges, facets, etc. rather than intersection of halfspaces which doesn't tell you anything about the vertices and how they are connected). The most straightforward thing I can think of is to consider all 6 edges of B, and intersect them against A, resulting in 6 new, possibly shorter and non-connecting segments. The segment-tetrahedron intersection is very straightforward: intersect the segment against the plane containing the facet and keep the part that is on the interior. Now, consider the 12 endpoints of those 6 segments and compute the convex hull of those points. For this, I would use some existing library code like QHull. Alternatively you can try to implement it yourself using the incremental method or something else. The volume can be found by standard summation over facets once you have computed the intersection boundary representation.

$\endgroup$
1
  • $\begingroup$ Hi, thanks for the answer, quite interesting indeed, and some useful links! Could you (please) elaborate a bit more in the volume calculation? I think I got the idea, just to make sure... $\endgroup$ Jan 14, 2015 at 11:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .