Main Page | Modules | Namespace List | Class Hierarchy | Class List | Directories | Namespace Members | Class Members | Related Pages

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: