Expand description
A bounding-volume hierarchy over a triangle mesh: the nearest triangle to a point, every triangle within a ball, and the first triangle along a ray.
Built once, immutable after, and shared freely across threads. Every answer is the answer brute force gives over the same triangles with the same arithmetic, ties going to the lowest triangle index, so it depends on neither the tree’s shape, the order it is walked in, nor the thread count.
§Why the answers equal brute force
A query visits a node only if the node’s box could hold a triangle that passes the query’s own test. That is decided with the triangle test’s own floating-point operations applied to the box’s corners, and rounding is monotone (a larger operand never rounds to a smaller result), so a box’s computed bound can never exclude a triangle inside it whose computed value passes:
- nearest and ball: the closest point on a triangle is clamped into the triangle’s own box before its distance is taken, so each axis gap to it is at least the computed gap to any box that holds the triangle. A filtered nearest query passes over the triangles its filter refuses before measuring them, and a box’s gap bounds the triangles it holds that pass as it bounds them all;
- ray: the ray is sheared onto the
zaxis and every vertex transformed by the same operations the box corners are, so the computed vertices of a triangle lie within the box’s computed sheared bounds. A hit is decided by the exact signs of three orientations of the origin against those computed vertices, so a hit needs the origin within their hull, and the hit’s depth is clamped into their depth range.
§Watertight rays
Two triangles that share an edge share its two vertices, so they compute the same sheared coordinates for it, and the exact orientation of the ray against it has opposite signs from the two sides. A ray through the edge (or a vertex) is therefore inside at least one of them: it cannot slip between triangles, however it is aimed.