How xyzdist works :
It uses a Bounding Volume Hierarchy (BVH) data structure, which consists of a tree of boxes. At the top, there’s effectively a bounding box containing everything, at each level, each box splits into 4 (hopefully) smaller boxes, and at the bottom, there’s a box for each primitive, (multiple for some primitives).
First, VEX has to build and cache the BVH. Then, it traverses the tree, visiting boxes that are close to the query point, finding the closest points on primitives in those boxes, and then visiting boxes that are a bit farther, until the closest point in a box is farther than the closest point found so far, and then it exits.
As for individual primitives, it varies, but for a triangle, the BVH caches the triangle’s normal, so if a line on the query point in the direction of the normal intersects the triangle, that’s the closest point on the triangle, and if not, it projects the query point onto each edge to find the closest there, and if those are all out of bounds, it finds the closest corner position to the query point, and that’s the closest point on a triangle.
Thought it’s quite interesting. Above is from the Dev, Neil D
