Signed volumes and GJK

Triangles

A triangle ABC with vertices a,b,c has a signed area. The sign is determined by the direction of its normal. If a is at the origin we can compute the area like so:

$\text{area}(\bigtriangleup ABC) = \text{area}(\bigtriangleup OBC) = \frac{1}{2} \cdot \begin{vmatrix} b_u & c_u\\b_v & c_v\end{vmatrix}$

Where u,v are a 2d subspace spanned by the triangle. Note that this is really just the cross product dotted with the normal of the u,v sub-space.

If a is not at the origin we can still compute its area like so:

$\text{area}(\bigtriangleup ABC) = \frac{1}{2} \cdot \begin{vmatrix} a_u & b_u & c_u\\a_v & b_v & c_v\\1&1&1\end{vmatrix}$

This expands to summing the area of three triangles that start at the origin:

$\text{area}(\bigtriangleup ABC) = \text{area}(\bigtriangleup OAB) + \text{area}(\bigtriangleup OBC) + \text{area}(\bigtriangleup OCA)$

Note that the sub triangles' winding is the same as ABC. This means that if the origin is inside ABC then the sub triangle areas will all have the same sign and will each contribute to the total area.

If the origin is outside of the triangle some sub areas will be positive and some will be negative. The outside sub-areas will cancel out leaving just the inside region giving the right total area.

Tetrahedron

The same concept applies for a tetrahedron ABCD with vertices a,b,c,d

In the case where a is at the origin we can compute the volume like so:

$\text{vol}(ABCD) = \text{vol}(OBCD) = \frac{1}{6} \cdot \begin{vmatrix} b_x & c_x & d_x\\b_y & c_y & d_y\\b_z & c_z & d_z\end{vmatrix}$

This is really just

$\frac{1}{6} \cdot b \cdot (c \times d)$

If a is not at the origin we can still compute the volume

$\text{vol}(ABCD) = \frac{1}{6} \times \begin{vmatrix}a_x & b_x & c_x & d_x\\a_y & b_y & c_y & d_y\\a_z & b_z & c_z & d_z\\1&1&1&1\end{vmatrix}$

Note that this is actually adding the volume of four tetrahedrons that start at the origin.

$\text{vol}(ABCD) = \text{vol}(OACD) + \text{vol}(OABC) +\text{vol}(OBDC) + \text{vol}(OADB)$

If the origin is inside the tetrahedron the 4 sub-volumes will all have the same sign as the signed volume of ABCD. If the origin is on the outside, some volumes will be positive and some will be negative. Just like the triangle case, the outside regions will cancel out leaving the correct total volume.

Closest point to origin

When evaluating GJK we must find the closet point to the origin on both a tetrahedron and a triangle. Using signed volumes we can determine the right voronoi regions to search. If the sub-volumes (or sub-areas) all have the same sign as the tetrahedron (or triangle) then the origin must be contained within the tetrahedron (or triangle). If any of the sub-volumes (or sub-areas) have the opposite sign then the origin is "seen" by the corresponding triangle (or edge).

It's possible to have multiple sub-volumes (or sub-areas) with the opposite sign as the original tetrahedron (or triangle). This indicates the origin is "seen" by multiple triangles (or edges). In this case we must compute the closest point for each candidate voronoi region and return the closest one. An example of a case where multiple regions need to be searched is an obtuse triangle where the origin can see two edges at once, but is ultimately closer to one of them.

Further details on using signed volumes with GJK can be found here: Improving the GJK algorithm for faster and more reliable distance queries between convex objects