Name
Abstract | ||
|---|---|---|
We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, 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 describe data structures that require preprocessing time and storage (where the $ notation hides polylogarithmic factors), and have polylogarithmic query time, for several special instances of the problem. These include the case when the ray origins are restricted to lie on a fixed line ℓ 0, but the directions of the rays are arbitrary, the more general case when the supporting lines of the rays pass through ℓ 0, and the case of rays orthogonal to some fixed line with arbitrary origins and orientations. We also present a simpler solution for the case of vertical ray-shooting with arbitrary origins. In all cases, this is a significant improvement over previously known techniques (which require Ω(n 2) storage, even when k ≪ n). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00453-008-9220-0 | ESA |
Keywords | DocType | Volume |
Computational geometry,Lines in space,Convex polyhedra,Ray-shooting | Journal | 55 |
Issue | ISSN | ISBN |
2 | 0178-4617 | 3-540-75519-5 |
Citations | PageRank | References |
4 | 0.45 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haim Kaplan | 1 | 3581 | 263.96 |
| Natan Rubin | 2 | 92 | 11.03 |
| Micha Sharir | 3 | 8405 | 1183.84 |