Fast Robust BSP Tree Traversal Algorithm for Ray Tracing

1 January 1997

journal article
research article
Published by Taylor & Francis in Journal of Graphics Tools

Vol. 2 (4) , 15-23
https://doi.org/10.1080/10867651.1997.10487481

Abstract

An orthogonal BSP (binary space partitioning) tree is a commonly used spatial subdivision data structure for ray-tracing acceleration. While the construction of a BSP tree takes a relatively short time, the efficiency of a traversal algorithm significantly influences the overall rendering time. We propose a new fast traversal algorithm based on statistical evaluation of all possible cases occuring during the traversal of a BSP tree. More frequent cases are handled simply, while less frequent ones are more computationally expensive. The proposed traversal algorithm handles all singularities correctly, and saves between 30% and 50% of traversal time compared with the commonly-known Sung and Arvo algorithms.

Keywords

This publication has 3 references indexed in Scilit:

Heuristics for ray tracing using space subdivision
The Visual Computer, 1990
A Proposal for Standard Graphics Environments
IEEE Computer Graphics and Applications, 1987
Data structures for ray tracing
Published by Springer Nature ,1986