Geometric Toolkit II

Problem: Given a triangle $x_1\ x_2\ x_3$ and a point $p$, all in 3D, what is the distance from $p$ to the closest point on the triangle?

Let's suppose, for now, that $p$ lies on the plane of the triangle, so we really have a 2D problem in the plane. This is almost never the case, but we'll deal with that later.

Define $\widehat{p} = p - x_1$, $u = x_2-x_1$, and $v = x_3-x_1$.

Then we can write $\widehat{p}$ as a linear combination of $u$ and $v$ $$\widehat{p} = \alpha\ u + \beta\ v$$

for some coefficients $\alpha$ and $\beta$:

So we have $$\begin{array}{rcl} \widehat{p} &=& \alpha\ u + \beta\ v \\ p - x_1 &=& \alpha\ (x_2-x_1) + \beta\ (x_3-x_1) \\ p &=& (1-\alpha-\beta)\ x_1 + \alpha\ x_2 + \beta\ x_3 \\ p &=& \gamma\ x_1 + \alpha\ x_2 + \beta\ x_3 \end{array}$$

for $\gamma = 1-\alpha-\beta$.

The $(\gamma,\alpha,\beta)$ are the Barycentric coordinates of $p$ with respect to $x_1, x_2, x_3$.

The signs of the Barycentric coordinates tell us which area of the plane $p$ lies in:

For example, the sign of $\alpha$, which is the coefficient on $u$, is positive on the right side of the line of $v$, and negative on the left side of the line of $v$.

To compute the point-to-triangle distance, there are three cases:

• If the signs are $(+,+,+)$, $p$ is closest to the triangle interior, so we compute the point-to-plane distance of $p$ to the plane of the triangle.
• If the signs have two minuses and a plus, $p$ is closest to one of the corners, and we compute the point-to-point distance using that corner.
• If the signs have two plusses and a minus, $p$ is in an area associated with an edge segment (let's say it's $x_1 x_2$) and we compute the parameter, $t$, of the projection of $p$ onto that segment (as described in the previous lecture).

  If $t \in [0,1]$, we compute the point-to-point distance between $p$ and $x_1 + t\ (x_2-x_1)$. If $t > 1$, the projection of $p$ is beyond $x_2$, so we compute the $p$-to-$x_2$ distance. Otherwise, $t < 0$ and we compute the $p$-to-$x_1$ distance.

We need to find $\alpha$ and $\beta$ such that $$\widehat{p} = \alpha\ u + \beta\ v$$

This can be written in matrix form: $$ \left[\begin{array}{cc} \vdots & \vdots \\ u & v \\ \vdots & \vdots \end{array}\right] \left[\begin{array}{c} \alpha \\ \beta \end{array}\right] = \left[\begin{array}{c} \vdots \\ \widehat{p} \\ \vdots \end{array}\right] $$

If $u$, $v$, and $\widehat{p}$ were 2D vectors, it would be easy to invert the $2 \times 2$ matrix, $\left[ u\ v \right]$, and solve for $\alpha$ and $\beta$.

However, these are 3D vectors and (undoing our assumption above) $\widehat{p}$ is very likely not in the plane of the triangle.

The solution is to find $\alpha$ and $\beta$ such that $\alpha\ u + \beta\ v$ is as close to $\widehat{p}$ as possible. The point on the plane closest to $\widehat{p}$ is the perpendicular projection of $\widehat{p}$ onto the plane.

So we need to find a solution that minimizes the error (in a least squares sense) of $$| \widehat{p} - (\alpha\ u + \beta\ v) |$$

This is done using the "normal form" in which each side of the original equation is projected onto the $\langle u, v \rangle$ subspace: $$ \left[\begin{array}{c} \cdots u \cdots \\ \cdots v \cdots \\ \end{array}\right] \left[\begin{array}{cc} \vdots & \vdots \\ u & v \\ \vdots & \vdots \end{array}\right] \left[\begin{array}{c} \alpha \\ \beta \end{array}\right] = \left[\begin{array}{c} \cdots u \cdots \\ \cdots v \cdots \\ \end{array}\right] \left[\begin{array}{c} \vdots \\ \widehat{p} \\ \vdots \end{array}\right] $$

Then the problem becomes $$ \left[\begin{array}{cc} u \cdot u & u \cdot v \\ v \cdot u & v \cdot v \\ \end{array}\right] \left[\begin{array}{c} \alpha \\ \beta \end{array}\right] = \left[\begin{array}{cc} u \cdot \widehat{p} \\ v \cdot \widehat{p} \\ \end{array}\right] $$

Now we have a $2 \times 2$ matrix and can invert it to find $\alpha$ and $\beta$.

Note 1: This "normal form" is equivalent to the "pseudoinverse" that we'll be discussing in the next lecture.

Note 2: For a $2 \times 2$ matrix $\left[\begin{array}{cc} a & b \\ c & d \end{array}\right]$ the inverse is $\displaystyle {1 \over ad-bc}\ \left[\begin{array}{cc} d & -b \\ -c & a \end{array}\right]$.