Octrees with near optimal cost for ray-shooting
The ray-shooting problem consists in finding the first object in the scene which is intersected by the given ray. To increase the efficiency of visibility algorithms, which are based on ray-shooting, a suitable space decomposition of the scene is used -- a quadtree in the plane or an octree in the space. The authors are interested in the construction of trees with a guaranteed approximation ratio without increasing the cost too much. The suggested procedure constructs the octree with cost \(O(M)\), where \(M\) is a lower bound on the cost of any tree for the given scene. Here, the scene that consist of solids represented by their boundaries are considered. The boundaries of the solids can be subdivided into elements of constant combinatorial complexity. In the article, the effect of rebalancing the tree on the cost measure is examined, too. Adjacent cells of the balanced tree have the same size. The authors prove that rebalancing only increases the cost by a constant multiplicative factor.
- Cost-driven octree construction schemes: An experimental study
- Compact storage for octtrees in a fast ray-tracing algorithm
- Cost prediction for ray shooting in octrees
- Statistical optimization of octree searches
- scientific article; zbMATH DE number 1217742 (Why is no real title available?)
- A local search algorithm for ray-convex polyhedron intersection
- An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
- Cost prediction for ray shooting
- Cost-driven octree construction schemes
- LATIN 2004: Theoretical Informatics
This page was built for publication: Octrees with near optimal cost for ray-shooting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2495948)
