#include <gjk_simplex.h>

Public Types
typedef vector3_type::value_traits	value_traits
typedef vector3_type::value_type	real_type
Public Member Functions
	Simplex ()
Public Attributes
int	m_bitmask
vector3_type	m_v [4]
	The simplex vertices.
real_type	m_w [4]
	Barycentric coordinates for the closest point on the simplex wrt. the simplex vertices.
vector3_type	m_a [4]
	The support points from object A corresponding to the simplex vertices.
vector3_type	m_b [4]
	The support points from object B corresponding to the simplex vertices.

Detailed Description

template<typename vector3_type>
class OpenTissue::gjk::Simplex< vector3_type >

Simplex Type. This class defines a minimal set of data that defines a simplex. The class is specifically tailored to be used in the GJK algorithm. That means it is limited completely to a singleton simplex in a three dimensional space.

Further the class contains storage for barycentric coordinates and the original support points used to generate the simplex vertices.

Notice that the barycentric coordinates are really only needed when one wants to re-construct the two closest points between two convex sets. This is explained in detail below. In the general distance between point and convex set algorithm there is no need for these coordinates. However, for our specific purpose we need to store them.

The simplex vertices are obtained from a support function for the Minikowsky difference between two convex point sets $A$ and $B$ .

The Minikowsky Difference is defined as

$A \ominus B = \{a-b | a \in A, b \in B \}$

One can show that the support function, $S_{A \ominus B}$ , of the Minikowsky Difference can be evaluated as

$S_{A \ominus B}( v ) = S_{A}( v ) - S_{B}( -v )$

This is used in the GJK algorithm to generate the simplex vertices. Thus for every simplex vertex, $v_i$ , there exist a corresponding support point, $a_i$ , for $A$ and one, $b_i$ , for $B$ . Thus we have

$v_i = a_i - b_i$

Having found the cloest point, $q$ , on the simplex to the origin. Then by the very nature of the simplex we can write $q$ as a convex linear combination. That is

$q = w_1 v_1 + \cdots + w_n v_n$

where the $v_i$ 's are the simplex vertices and $w_i$ 's are scalar weights such that

$w_1 + \cdots + w_n = 1$

and $0 \leq w_i \leq 1$ . Thus one immediately recognize the scalar weights as the bary-centric coordinates of q.

It is rather straightforward to compute the weights. Once we know them we can use these to obtain the closest points between the two convex sets $A$ and $B$ . This is done as follows:

$q = w_1 v_1 + \cdots + w_n v_n = w_1 (a_1 - b_1) + \cdots + w_n (a_n - b_n)$

Next re-order

$q = \underbrace{ (w_1 a_1 + \cdots + w_n a_n ) }_{q_a} - \underbrace{ (w_1 b_1 + \cdots + w_n b_n ) }_{q_b}$

By convexity of $A$ and $B$ we know

$\[ q_a \in A \qquad \text{and} \qquad q_b \in B \end{align*}$

Thus we have found to members of $A$ and $B$ that gives the minimum norm point in the Minikowsky difference. In other words we have found two closest points between $A$ and $B$ .