vertical ray shooting for fat objects
We describe a data structure for vertical ray shooting in a set of n convex fat polyhedra of constant complexity in 3-space. The structure has O(log 2 n) query time, and it uses O(n log 3 n(log log n) 2 ) storage. It can also be used for fat objects with curved boundaries, at the cost of a small increase in storage.
ray shooting fat objects geometric data structures realistic input models