A Stupidly Simple, Fast Octree Traversal Algorithm for Ray Intersection
I’ve been doing some game dev stuff lately and I needed to intersect a ray with an octree of triangles, for collision detection. I first implemented a naive algorithm that simply checked if the AABB of each octant intersected the ray, then found the closest point. This was devastatingly slow, as you might expect. I then implemented the algorithm described by Revelles et al which is a nice algorithm, but limited (all octants must be half the size of their parents, for instance; this means it can work only on true octrees and not “loose octrees” or k-d trees) and fairly complicated.
Today I had a random thought while doing day-job work: what if I treat the octree divisions as splitting planes and essentially do a binary search? By knowing which plane my ray is closest to at a given step, I know which nodes I need to search. To my surprise – and slight horror, because it’s never a...