Ray Shooting Amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions
Pankaj K. Agarwal, Micha Sharir · SIAM Journal on Computing · 1996
We consider the problem of ray shooting in a three-dimensional scene consisting of m (possibly intersecting) convex polyhedra or polyhedral terrains with a total of n faces, i.e., we want to preprocess them into a data structure, so that the first intersection point of a query ray and the given polyhedra can be determined quickly. We present a technique that requires $O((mn)^{2 + \varepsilon } )$ preprocessing time and storage, and can answer ray-shooting queries in $O(\log ^2 n)$ time. This is a significant improvement over previously known techniques (which require $O(n^{4 + \varepsilon }) $ space and preprocessing) if m is much smaller than n, which is often the case in practice. Next, we present a variant of the technique that requires $O(n^{1 + \varepsilon }) $ space and preprocessing, and answers queries in time $O(m^{{1 / 4}} n^{{1 / 2} + \varepsilon } )$, again a significant improvement over previous techniques when $m \ll n$.