Htykuut

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.

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.