Octrees with near optimal cost for ray-shooting (Q2495948)

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.