One of the weird rabbitholes I fell into while working on the GJK implementation was figuring out how to find the nearest point on a tetrahedron to a query point. This also relates tightly to the idea of finding which Voronoi region a given point corresponds to–in fact, I elected to update my projection routine to also report which region a given point fell into.
The implementation of the thing itself is a bit annoying, since we have to calculate a bunch of barycoords and then figure out which domain (in increasing dimensionality) we may be falling into, but testing them is even more frought.
So, for the sake of the next poor dumb bastard that decides to implement this sort of thing for scractch, I figured I should publish my test data and see if it helps folks.
First, let’s define the tetrahedron we’ll be working with:
| Point | Coordsinates |
|---|---|
| A | {0, 0, 0} |
| B | {0, 0, 1} |
| C | {1, 0, 0} |
| D | {0, 1, 0} |
Using this, we will generate a tetrahedron with faces ABD, ACB, BCD, and CAD. Note that all of these faces are wound counterclockwise about their outward-facing normal. We’re also in a right-handed coordinate system, so X x Y = Z.
We’ll have two sets of test cases, one for points near (usually right-on the region boundary) and one for points far to the region (like, clearly inside the region). Then, we’ll have a test point, and the expected nearest point in the tetrahedron, and the region that that point should be classified to.
| Region | Near Point | Far point | Projected point |
|---|---|---|---|
| A | {0, 0, 0} | {-1, -1, -1} | {0, 0, 0} |
| B | {0, 0, 1} | {-0.1, -0.1, 1.5} | {0, 0, 1} |
| C | {1, 0, 0} | {1.5, -0.1, -0.1} | {1, 0, 0} |
| D | {0, 1, 0} | {-0.1, 1.5, -0.1} | {0, 1, 0} |
| AB | {0, 0, 0.5} | {-0.1, -0.1, 0.5} | {0, 0, 0.5} |
| AC | {0.5, 0, 0} | {0.5, -0.1, -0.1} | {0.5, 0, 0} |
| AD | {0, 0.5, 0} | {-0.1, 0.5, -0.1} | {0, 0.5, 0} |
| BC | {0.5, 0, 0.5} | {0.5, -0.1, 0.5} | {0.5, 0, 0.5} |
| BD | {0, 0.5, 0.5} | {-0.1, 0.5, 0.5} | {0, 0.5, 0.5} |
| CD | {0.5, 0.5, 0} | {0.5, 0.5, -1.0} | {0.5, 0.5, 0} |
| ABC | {1/3, 0, 1/3} | {1/3, -1, 1/3} | {1/3, 0, 1/3} |
| ABD | {0, 1/3, 1/3} | {-1, 1/3, 1/3} | {0, 1/3, 1/3} |
| BCD | {1/3, 1/3, 1/3} | {4/3, 4/3, 4/3} | {1/3, 1/3, 1/3} |
| CAD | {1/3, 1/3, 0} | {1/3, 1/3, -2} | {1/3, 1/3, 0} |
| ABCD | {0.1, 0.1, 0.1} | n/a | {0.1, 0.1, 0.1} |
The above was developed as part of the test suite for my tetrahedron routines. Note that when you actually go to implement these things, order of which region gets tested first is very important.
Good luck!