Can you compute line segment that crosses a triangle?

Question

I have a triangle with corner vertices (x1, y1, z1), (x2, y2, z2), (x3, y3, z3). I also have a height H which is between min(z1, z2, z3) and max(z1, z2, z3) and I'm looking to find the coordinates of the line segment that crosses the triangle horizontally and has height H. Here's a little diagram:

https://www.dropbox.com/s/y3527zf1916yfss/Screenshot%202018-12-06%2015.41.09.png?dl=0

Context: I have mesh of triangles and am trying to draw the contour at a certain height H. I've found the triangles that the contour lines passes through, but not sure how to find the specific lines through each triangle.

Answer 1

Let $$\bbox{ \vec{v}_1 = \left [ \begin{matrix} x_1 \\ y_1 \\ z_1 \end{matrix} \right ] } \quad \text{and} \quad \bbox{ \vec{v}_2 = \left [ \begin{matrix} x_2 \\ y_2 \\ z_2 \end{matrix} \right ] } , \quad \bbox{ z_1 \lt z \lt z_2 }$$ then the contour at $z$ intersects the line segment between $\vec{v}_1$ and $\vec{v}_2$ at $\vec{p}$, $$\bbox{ \vec{p} = \frac{z_2 - z}{z_2 - z_1}\vec{v}_1 + \frac{z - z_1}{z_2 - z_1}\vec{v}_2 }$$

In a triangle with vertices $\vec{v}_1$, $\vec{v}_2$, and $\vec{v}_3$, with $\min(z_1 , z_2 , z_3) \lt z \lt \max(z_1 , z_2 , z_3)$ there are exactly two such intersections; draw the line between those.

If we use $\vec{e}_{12}$ for the intersection point between vertices $\vec{v}_1$ and $\vec{v}_2$, $\vec{e}_{13}$ for the intersection point between vertices $\vec{v}_1$ and $\vec{v}_3$, and $\vec{e}_{23}$ for the intersection point between vertices $\vec{v}_2$ and $\vec{v}_2$, calculated using the above formula for $\vec{p}$ for each respective pair of vertices, the complete table of possible cases is $$\begin{array}{c|c|c|c} z_1 & z_2 & z_3 & z \text{ contour line or (point) } \\ \hline z_1 \lt z & z_2 \lt z & z_3 \lt z & \text{None} \\ z_1 = z & z_2 \lt z & z_3 \lt z & (\vec{v}_1) \\ z_1 \gt z & z_2 \lt z & z_3 \lt z & \vec{e}_{12} - \vec{e}_{13} \\ z_1 \lt z & z_2 = z & z_3 \lt z & (\vec{v}_2) \\ z_1 = z & z_2 = z & z_3 \lt z & \vec{v}_1 - \vec{v}_2 \\ z_1 \gt z & z_2 = z & z_3 \lt z & \vec{v}_2 - \vec{e}_{13} \\ z_1 \lt z & z_2 \gt z & z_3 \lt z & \vec{e}_{12} - \vec{e}_{23} \\ z_1 = z & z_2 \gt z & z_3 \lt z & \vec{v}_1 - \vec{e}_{23} \\ z_1 \gt z & z_2 \gt z & z_3 \lt z & \vec{e}_{13} - \vec{e}_{23} \\ z_1 \lt z & z_2 \lt z & z_3 = z & (\vec{v}_3) \\ z_1 = z & z_2 \lt z & z_3 = z & \vec{v}_1 - \vec{v}_3 \\ z_1 \gt z & z_2 \lt z & z_3 = z & \vec{v}_3 - \vec{e}_{12} \\ z_1 \lt z & z_2 = z & z_3 = z & \vec{v}_2 - \vec{v}_3 \\ z_1 = z & z_2 = z & z_3 = z & \text{ Entire triangle } \\ z_1 \gt z & z_2 = z & z_3 = z & \vec{v}_2 - \vec{v}_3 \\ z_1 \lt z & z_2 \gt z & z_3 = z & \vec{v}_3 - \vec{e}_{12} \\ z_1 = z & z_2 \gt z & z_3 = z & \vec{v}_1 - \vec{v}_3 \\ z_1 \gt z & z_2 \gt z & z_3 = z & (\vec{v}_3) \\ z_1 \lt z & z_2 \lt z & z_3 \gt z & \vec{e}_{13} - \vec{e}_{23} \\ z_1 = z & z_2 \lt z & z_3 \gt z & \vec{v}_1 - \vec{e}_{23} \\ z_1 \gt z & z_2 \lt z & z_3 \gt z & \vec{e}_{12} - \vec{e}_{23} \\ z_1 \lt z & z_2 = z & z_3 \gt z & \vec{v}_2 - \vec{e}_{13} \\ z_1 = z & z_2 = z & z_3 \gt z & \vec{v}_1 - \vec{v}_2 \\ z_1 \gt z & z_2 = z & z_3 \gt z & (\vec{v}_2) \\ z_1 \lt z & z_2 \gt z & z_3 \gt z & \vec{e}_{12} - \vec{e}_{13} \\ z_1 = z & z_2 \gt z & z_3 \gt z & (\vec{v}_1) \\ z_1 \gt z & z_2 \gt z & z_3 \gt z & \text{None} \\ \end{array}$$ There is absolutely nothing surprising in the table.

In practice, you can implement pseudocode similar to

Function z_contour(x1, y1, z1, x2, y2, z2, x3, y3, z3, z)
    Let  x = [0, 0, 0]
    Let  y = [0, 0, 0]
    Let  n = 0

    If z1 == z:
        x[n] = x1
        y[n] = y1
        n = n + 1

    If z2 == z:
        x[n] = x2
        y[n] = y2
        n = n + 1

    If z3 == z:
        x[n] = x3
        y[n] = y3
        n = n + 1

    If (z1 < z and z2 > z) or (z1 > z and z2 < z):
        x[n] = ( (z2 - z)*x1 + (z - z1)*x2 ) / (z2 - z1)
        y[n] = ( (z2 - z)*y1 + (z - z1)*y2 ) / (z2 - z1)
        n = n + 1

    If (z1 < z and z3 > z) or (z1 > z and z3 < z):
        x[n] = ( (z3 - z)*x1 + (z - z1)*x3 ) / (z3 - z1)
        y[n] = ( (z3 - z)*y1 + (z - z1)*y3 ) / (z3 - z1)
        n = n + 1

    If (z2 < z and z3 > z) or (z2 > z and z3 < z):
        x[n] = ( (z3 - z)*x2 + (z - z2)*x3 ) / (z3 - z2)
        y[n] = ( (z3 - z)*y2 + (z - z2)*y3 ) / (z3 - z2)
        n = n + 1

    If n == 0:
        Return (None)
    Else
    If n == 1:
        Return Point(x[0], y[0], z)
    Else
    If n == 2:
        Return Line(x[0], y[0], z, x[1], y[1], z)
    Else:
        Return Triangle(x1, y1, z, x2, y2, z, x3, y3, z)

End Function

to compute the intersection of the contour $z$ and the triangle.