The NeighborMesh is what actually makes EnhancedGJK "enhanced". It consists of a mesh and a pre-computed set of neighbors for each vertex. These neighbors will be searched when the GJK simplex is refined. Searching over just the neighbors of a particular vertex allows us to avoid repeatedly searching over every vertex in the mesh.

Note that constructing a new NeighborMesh is expensive (and unoptimized). We recommend constructing the NeighborMesh for each of your meshes ahead of time.

The enhanced GJK algorithm relies on a pre-computed set of neighbors for each vertex in the mesh. In order to use those neighbors, we have to know from which vertex to start. Specifically, we need to know the index of the vertex corresponding to the point in the GJK simplex which we are trying to improve. To do that, we introduce the notion of a Tagged point. A tagged point is just a point and some arbitrary additional data field. All of the any_inside and support_vector_max functions in this package return tagged points. For most geometries, that tag is empty (nothing). But for our NeighborMesh type, the tag is the linear index into the vertices of the mesh, which lets us look up that mesh's neighbors faster later on.

Compute all subsets of the points in the simplex in a reliable order. The order is arbitrary, but was chosen to match the implemenation in S. Cameron, “Enhancing GJK: computing minimum and penetration distances between convex polyhedra,”. Specifically, subset i contains point j iff the binary representation of i has a one at the jth bit.

normal(face::StaticVector{N, <:StaticVector{N}})

Return any N-vector normal to the face spanned by N points. The result is not necessarily normalized, nor is there any guarantee on winding.

weights = projection_weights(simplex)

This function implements Johnson's distance subalgorithm, as described in E. G. Gilbert, D. W. Johnson, and S. S. Keerthi, “A fast procedure for computing the distance between complex objects in three-dimensional space,”

1. Given a simplex (a length N+1 vector of points of dimension N), it

returns weights such that dot(weights, simplex) yields the point in the convex hull of the simplex which is closest to the origin.

This is the critical loop of the GJK algorithm, so it has been heavily optimized to precompute, inline, and unroll as much of the algorithm as possible. For a more readable (and much slower) implementation, see projectionweightsreference()