Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions. (English) Zbl 0843.68116
Summary: 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^2n)\) 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\).
MSC:
68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
52B11 | \(n\)-dimensional polytopes |
68P05 | Data structures |
68W10 | Parallel algorithms in computer science |
68Q25 | Analysis of algorithms and problem complexity |