0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Linear interpolation using the endpoints of the three sides will give you the endpoints of the segment. $\endgroup$ – amd Dec 7 '18 at 0:59
1
$\begingroup$

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.

$\endgroup$

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.