RAY SHOOTING AMIDST CONVEX POLYHEDRA AND POLYHEDRAL TERRAINS IN 3 DIMENSIONS

We consider the problem of ray shooting in a three-dimensional scene c onsisting of m (possibly intersecting) convex polyhedra or polyhedral terrains with a total of n faces, i.e., we want to preprocess them int o a data structure, so that the first intersection point of a query ra y and the given polyhedra can be determined quickly. We present a tech nique that requires O((mn)(2+epsilon)) preprocessing time and storage, and can answer ray-shooting queries in O(log(2)n) time. This is a sig nificant improvement over previously known techniques (which require O (n(4+epsilon)) space and preprocessing) if m is much smaller than n, w hich is often the case in practice. Next, we present a variant of the technique that requires O(n(1+epsilon)) space and preprocessing, and a nswers queries in time O(m(1/4)n(1/2+epsilon)), again a significant im provement over previous techniques when m << n.