BSP ray tracing

From CGAFaq

Ray tracing with a BSP tree is very similar to hidden surface removal with a BSP tree. The algorithm is a simple forward tree walk, with a few additions that apply to ray casting. See Jim Arvo's voxel walking algorithm for ray tracing from Ray Tracing News.

Implementation notes

Probably the biggest difference between ray tracing and other applications of BSP trees is that ray tracing does not require splitting of primitives to obtain correct results. This means that the hyperplanes can, and should, be chosen strictly for tree balance.

A large improvement can be made over the voxel walking algorithm for recursive ray tracing by using the parent node of the ray origin as a hint.

Because ray tracing is a spatial classification problem, balancing is the key to performance. Most spatial partitioning schemes for accellerating ray tracing use a criteria called "occupancy", which refers to the number of primitives residing in each partition. A BSP tree which has approximately the same occupancy for all partitions is balanced.

Balancing is discussed elsewhere in this document.

Initial content for this page from the BSP tree FAQ, included with permission of its maintainer, Bretton Wade.