# DistancePointToTriangle Struct Template Reference [XEngineMath Library]

List of all members.

## Detailed Description

### template<unsigned int Dimension> struct XEngine::Math::DistanceAlgorithms::DistancePointToTriangle< Dimension >

Returns the distance of the given point to the given triangle.

```	Given a point P and a triangle T(s, t) = B + s * E0 + t * E1 with s and t
in [0, 1] and s + t <= 1 we want to find the closest distance of P to T.
We want to find the parameter pair (s, t) that gives us the closest point on
the triangle to P. To do so we have to minimze the squared-distance function
Q(s, t) = |T - P|^2
This function is quadratic in s and t and is of the form
Q(s, t) = as^2 + 2bst + ct^2 + 2ds + 2et + f
with
a = E0 * E0
b = E0 * E1
c = E1 * E1
d = E0 * (B - P)
e = E1 * (B - P)
f = (B - P) * (B - P)
Quadratics are classified by the sign of the determinant
ac - b^2 = (E0 * E0) * (E1 * E1) - (E0 * E1)^2 = |E0 x E1|^2 > 0
The determinant is always > 0 since E0 and E1 are linearly independent
and thus the cross product of the two vectors always yields a nonzero
vector.
The minimum of Q(s, t) either occurs at an interior point or at a
boundary of the domain of T(s, t). So we minimize Q(s, t) by determining
the gradient dQ(s, t) and calculating s and t where dQ = (0, 0)
dQ(s, t) = (2as + 2bt + 2d, 2bs + 2ct + 2e) = (0, 0)
which is at
s = (be - cd) / (ac - b^2)
t = (bd - ae) / (ac - b^2)
If (s, t) is an interior point we have found the minimum. Otherwise
we must determine the correct boundary of the triangle where the
minimum occurs. Consider the following figure:

t

\ 2|
\ |
\|
|\
| \  1
|  \
3 | 0 \
|    \
--------------- s
4 | 5    \ 6
|       \
|        \

If (s, t) is in region 0 we have found the minimum. If (s, t) is
in region 1 we intersect the graph with the plane s + t = 1 and
get the parabola F(s) = Q(s, 1 - s) for s in [0, 1] as curve of
intersection that we can minimize. Either the minimum occurs at
F'(s) = 0 or at an end point where s = 0 or s = 1. Regions 3 and
5 are handled similarly.
If (s, t) is in region 2 the minimum could be on the edge s + t = 1
or s = 0. Because the global minimum occurs in region 2 the gradient
at the corner (0, 1) cannot point inside the triangle.
If dQ = (Qs, Qt) with Qs and Qt being the respective partial derivatives
of Q, it must be that (0, -1) * dQ(0, 1) and (1, -1) * dQ(0, 1)
cannot both be negative and the signs of these values can be used
to determine the correct edge. (0, -1) and (1, -1) are direction vectors
for the edges s = 0 and s + t = 1. Similar arguments apply to
regions 4 and 6.
```

The documentation for this struct was generated from the following files:
• XDistanceAlgorithms.h
• XDistanceAlgorithms.cpp

 Created with doxygen on: Thu Jan 6 14:12:15 2005 Copyright © by Martin Ecker