This triangle is in 2.5D, how could we adapt this algorithm to shapes that change in all x/y/z dimensions?
Bananya
I believe this algorithm is in 3D, and the picture shows that we will do a half-space test after projecting the point onto the plane of triangle instead of a half-plane test.
Heisenberg
How do we get N for half plane test? is it the cross product of the plane's normal and the line's tangent?
CMUScottie
We can get N by cross product of two edges of the triangle.
keenan
@Heisenberg Exactly---that's a nice way of computing it. Explicitly, if you have a triangle with vertices $x_i$, $x_j$, $x_k$, then the (non-unit) normal is given by $n = (x_j - x_i) \times (x_k - x_i)$ and the (non-unit) vector along an edge $ij$ is $e_{ij} = x_j - x_i$. Since $e_{ij}$ is a vector in the plane perpendicular to $n$, taking a cross product with $n$ will give a 90-degree rotation in this plane. For instance, $t_{ij} = n \times e_{ij}$ will be a vector orthogonal to edge $ij$, in the plane of the triangle. The half space associated with this edge is the set of all points $x \in \mathbb{R}^3$ such that
$$\langle t_{ij}, x \rangle = \langle t_{ij}, x_i\rangle,$$
i.e., whose distance along the direction $t_{ij}$ is the same as the distance of $x$ along $t_{ij}$. So, to check for containment in this halfspace you can just check if the left-hand side is bigger or smaller than the right-hand side.
This triangle is in 2.5D, how could we adapt this algorithm to shapes that change in all x/y/z dimensions?
I believe this algorithm is in 3D, and the picture shows that we will do a half-space test after projecting the point onto the plane of triangle instead of a half-plane test.
How do we get N for half plane test? is it the cross product of the plane's normal and the line's tangent?
We can get N by cross product of two edges of the triangle.
@Heisenberg Exactly---that's a nice way of computing it. Explicitly, if you have a triangle with vertices $x_i$, $x_j$, $x_k$, then the (non-unit) normal is given by $n = (x_j - x_i) \times (x_k - x_i)$ and the (non-unit) vector along an edge $ij$ is $e_{ij} = x_j - x_i$. Since $e_{ij}$ is a vector in the plane perpendicular to $n$, taking a cross product with $n$ will give a 90-degree rotation in this plane. For instance, $t_{ij} = n \times e_{ij}$ will be a vector orthogonal to edge $ij$, in the plane of the triangle. The half space associated with this edge is the set of all points $x \in \mathbb{R}^3$ such that
$$\langle t_{ij}, x \rangle = \langle t_{ij}, x_i\rangle,$$
i.e., whose distance along the direction $t_{ij}$ is the same as the distance of $x$ along $t_{ij}$. So, to check for containment in this halfspace you can just check if the left-hand side is bigger or smaller than the right-hand side.