6
$\begingroup$

I've got a rather complicated geometry problem that I'm trying to solve - how to find the intersection between two triangles in 3D space. I've looked around at other questions and answers on this site and quite a few others, but none of them seem to satisfy my question.

Anyway, given two triangles on two intersecting planes, and a line of intersection (a vector V), how would I be able to tell if any part of the intersection line is contained in both triangles?

Intersecting triangles

So far I've been able to, given two triangles, find their two planes, and the direction vector of the line where they intersect. I think I might be able to find if the line of intersection is contained in one triangle by projecting to 2D, but I'm not sure how to find if that line of intersection is contained in both triangles.

As far as I can tell, there's not much documentation on triangle to triangle collision, if anybody could tell me the step by step process to find the line of intersection between the triangles (and/or if it exists) rather than the line of intersection between the two planes, that would be great.

Btw I'm not quite looking for a "conceptual" solution (there's plenty of that out there already) but I'm wondering if anybody could enlighten me on the actual math for such an intersection test. Thanks!

EDIT: Here's an example problem - if you would be so kind as to show me a step by step solution of the problem, then thank you very much! :)

Example problem

Btw when I say "find the line of intersection between them", I mean a line segment. (sorry for the typo)

$\endgroup$
  • $\begingroup$ If you're looking for the computation, you might want to give an example that could be solved explicitly in an answer. $\endgroup$ – Michael Burr Apr 4 '15 at 20:09
  • $\begingroup$ Okay - I can do that later. :) $\endgroup$ – Superdoggy Apr 4 '15 at 20:23
  • $\begingroup$ @Michael Burr - I added a basic example that should be simple enough to easily demonstrate solving. $\endgroup$ – Superdoggy Apr 5 '15 at 0:40
  • $\begingroup$ Look at the link in my answer to this question: math.stackexchange.com/questions/1198731/… $\endgroup$ – marty cohen Apr 5 '15 at 2:04
4
$\begingroup$

Here's one way to do it:

Step 1: Determine the planes determined by the two triangles.

Step 2a: If they are the same plane, this has become a two dimensional problem.

Step 2b: If the planes are different there are many options.

Step 3: The vertices of triangle 1 cannot all be on the same side of the plane determined by triangle 2. Similarly, the vertices of triangle 2 cannot be on the same side of the plane determined by triangle 1. If either of these happen, the triangles do not intersect.

Step 4: Consider the line of intersection of the two planes. This line intersects both triangles by step 3. Now, compute the intersection (a two dimensional problem, the intersection is a segment determined by the intersection of the intersection of the line with the lines determined by the edges of the triangles.

Step 5: Determine if the segments (which are on the same line) intersect.

$\endgroup$
  • $\begingroup$ Aha, never thought about doing the same-side-check with the triangle vertices and the planes. I am somewhat unfamiliar with some of these concepts though - can you expand on what you mean with "Now, compute the intersection (a two dimensional problem, the intersection is a segment determined by the intersection of the intersection of the line with the lines determined by the edges of the triangles." I'm not entirely sure how I'm supposed to find the intersection of the edges of triangles with the line of intersection... $\endgroup$ – Superdoggy Apr 4 '15 at 18:06
  • $\begingroup$ Map the plane onto the $x$-$y$ plane via a projection. This takes lines to lines and triangles to triangles, so you can solve the problem there. $\endgroup$ – Michael Burr Apr 4 '15 at 19:01
  • $\begingroup$ Okay, so will I be projecting both triangles and the line of intersection to a single plane? (Also does it matter which plane, I think I need to project it to one that won't lead to degenerate triangles, right?) Anyway I'll look up some line-segment triangle intersection in 2D, that shouldn't be too hard, thanks. $\endgroup$ – Superdoggy Apr 4 '15 at 19:07
  • $\begingroup$ Don't project them both at the same time, only project the line and the triangle. $\endgroup$ – Michael Burr Apr 4 '15 at 19:09
  • $\begingroup$ Hmm... then I'm having a hard time seeing how I'm going to make the connection between the intersections between the line of intersection and the different triangles - since I'll be making projections I'll have to avoid degenerate triangles - what should I do in the case that I have to project the triangles with the line onto different planes? That might make step five a little difficult. $\endgroup$ – Superdoggy Apr 4 '15 at 19:21
0
$\begingroup$

There is a calculation error in this that I haven't found, but the idea will work. The main tools that I will use consist of elements of linear algebra and multivariate calculus. Many of these calculations can be done in two ways and I'll pick whichever one I like best. For programming situations, some of these operations are less stable than others, so you might need to replace some of these steps with other options.

Let $v_1=(0,5,0)$, $v_2=(0,0,0)$, and $v_3=(8,0,0)$ be the vertices of triangle $O$. Let $w_1=(6,8,3)$, $w_2=(6,8,-2)$, and $w_3=(6,-4,-2)$ be the vertices of triangle $Y$.

Step 1: We begin by determining the planes that contain these triangles. The normal to the plane containing $O$ is given by $$ (v_2-v_1)\times(v_3-v_1)=(0,5,0)\times(8,0,0)=(0,0,-40). $$ Therefore, the plane containing $O$ is $$ 0(x-0)+0(y-0)-40(z-0)=0. $$ In other words, $z=0$.

The normal to the plane containing $Y$ is given by $$ (w_2-w_1)\times(w_3-w_1)=(0,0,-5)\times(0,-12,-5)=(-60,0,0). $$ Therefore, the plane containing $Y$ is $$ -60(x-6)+0(y-8)+0(z-3)=0. $$ In other words, $x=6$.

Step 2: Now, let's determine the line of intersection of these planes. The line must satisfy $z=0$ and $x=6$, so, as an augmented matrix, we have $$ \begin{bmatrix} 1&0&0&6\\0&0&1&0 \end{bmatrix} $$ This matrix is already in reduced row echelon form with $x=6$, $y$ a free variable, and $z=0$. Therefore, the line of intersection is $(6,t,0)$.

Computing the rref is not always a numerically stable operation, so you might want to replace this step with taking the cross product of the normal vectors of the planes to get the direction of the line of intersection and finding a nice point on the line of intersection.

Step 3: Find the intersection of the line and triangle $O$. The line containing $v_1$ and $v_2$ has direction $v_2-v_1=(0,5,0)$ and passes through the point $(0,0,0)$, so its formula is $$ (0+0s,0+5s,0+0s)=(0,5s,0). $$ (I changed variables because I already used $t$ in the previous formula). The other sides of the triangle are given by the lines $$ (0+8s,0+0s,0+0s)=(8s,0,0) $$ and $$ (8-8s,5s,0)=(8-8s,5s,0). $$ (Be careful about setting this up, you really want to write $sv_1+(1-s)v_2$ so that when $s=0$, you get one of the endpoints and when $s=1$, you get the other endpoint.)

To find intersection points, we must solve three systems of equations. The first is to intersect the line of intersection with the first side of the triangle. The first system of equations is $$ 6=0\qquad t=5s\qquad 0=0 $$ The matrix form is $$ \begin{bmatrix} 0&0&6\\ 1&-5&0\\ 0&0&0 \end{bmatrix} $$ This system has no solution, so there is no intersection point.

The second system is $$ 6=8s\qquad t=0\qquad 0=0 $$ The matrix form is $$ \begin{bmatrix} 0&8&6\\ 1&0&0\\ 0&0&0 \end{bmatrix} $$ The solution to this system is $t=0$ and $s=\frac{6}{8}=\frac{3}{4}$. Since the $s$-value is between $0$ and $1$, this point lies on the side of the triangle. This point is $(6,0,0)$.

The third system is $$ 6=8-8s\qquad t=5s\qquad 0=0 $$ The corresponding matrix is $$ \begin{bmatrix} 0&8&2\\ 1&5&0\\ 0&0&0\\ \end{bmatrix} $$ This system has a solution, $s=\frac{1}{4}$ and $t=\frac{5}{4}$. Therefore, the point of intersection is $(6,\frac{5}{4},0)$.

Therefore, the segment on the first triangle is between $(6,0,0)$ and $(6,\frac{5}{4},0)$. This is between $t=0$ and $t=\frac{5}{4}$.

For triangle $Y$, I won't show all the work, but give the highlights. The lines for the sides of the triangles are given by $(6,8,3-5s)$, $(6,8-12s,3-5s)$, and $(6,8-12s,-2)$.

The first line intersects at $t=8$ and $s=\frac{3}{5}$, which corresponds to the point $(6,8,0)$. The second line intersects at $t=\frac{4}{5}$ and $s=\frac{3}{5}$, which corresponds to the point $(6,\frac{4}{5},0)$. The third line does not intersect the intersections of the planes.

Now, the first triangle intersects the line of interest between $t=0$ and $t=\frac{5}{4}$ while the second triangle intersects between $t=\frac{4}{5}$ and $t=8$. Intersecting these two segments gives the intersection between $t=\frac{4}{5}$ and $t=\frac{5}{4}$ (this isn't right, I'll search for the error).

$\endgroup$
  • $\begingroup$ I'm pretty sure in my example problem the line (segment) of intersection goes from (6 ,5/4, 0) to (6, 0, 0)... thanks for all this work though. I'll look through it in the morning. $\endgroup$ – Superdoggy Apr 5 '15 at 2:49
  • $\begingroup$ Yeah, I made a computation error (that's why I said that it isn't right), but the idea is sound - there's just a computation error somewhere. I've found one of the errors and am looking for the second. $\endgroup$ – Michael Burr Apr 5 '15 at 2:55
  • $\begingroup$ Actually, $(6,0,0)$ is not inside the triangle $Y$. If you solve $a(6,8,3)+b(6,8,-2)+c(6,-4,-2)=(6,0,0)$ you'll find that $b=-2/30$, which means that the point $(6,0,0)$ is outside the convex hull of the vertices of $Y$. Therefore, $(6,0,0)$ is NOT in the intersection. $\endgroup$ – Michael Burr Apr 5 '15 at 3:02
  • $\begingroup$ Draw the triangle $(8,3)$, (8,-2)$, and $(-4,-2)$ (ignoring the constant 6 in the first coordinate) and you'll see that $(0,0)$ is NOT in the triangle. $\endgroup$ – Michael Burr Apr 5 '15 at 3:03
  • $\begingroup$ Yeah, I see - you're right - I think I drew my example graph wrong - so when I made a 2 second geometric analysis to find the segment (just before bed) I guess I shouldn't have assumed that I drew it correctly. :P $\endgroup$ – Superdoggy Apr 5 '15 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.