Premium
Ray Tracing an Octree: Numerical Evaluation of the First Intersection
Author(s) -
Gargantini I.,
Atkinson H. H.
Publication year - 1993
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.1240199
Subject(s) - octree , computer science , rendering (computer graphics) , intersection (aeronautics) , ray tracing (physics) , octant (instrument) , data structure , algorithm , computer graphics (images) , physics , quantum mechanics , astronomy , engineering , programming language , aerospace engineering
An algorithm is presented which finds the first intersection of a directed semi‐infinite straight‐line (called ray) with an octree, without resorting to the evaluation of neighbouring nodes. Given a pointer‐based region octree, intersections of the ray with a node's bisecting planes are first evaluated to determine in which sub‐octants the ray‐node intersections may lie; a local ordering then determines the sequence in which these sub‐octants should be examined so that the intersection closest to the ray's origin can be selected. This idea is applied recursively starting from the root of the octree; the novelty of the approach consists of the fact that the choice of each node's child in the octree is directly derived from the intersection of the ray‐segment within the tested sub‐octant, thus avoiding searching for any neighbouring nodes. The problem of selecting the correct octant while using the commonly available floating‐point arithmetic is also addressed in a ray tracing environment. Comparisons of this approach with the method given by Samet 17 are carried out in a variety of cases involving millions of voxels. The improvement ranged from 32% to 62% in terms of execution time.