@PhdThesis{Havran2000:PhD,
 author = "Vlastimil Havran",
 title  = "Heuristic Ray Shooting Algorithms",
 school = "Department of Computer Science and Engineering,
           Faculty of Electrical Engineering,
           Czech Technical University in Prague",
 type   = "Ph.D. Thesis",
 year   = "2000",
 month  = "November",
 url    = "http://www.cgg.cvut.cz/~havran/phdthesis.html",
 annote = "Global illumination research aiming at the photo-realistic
    image synthesis pushes forward research in computer graphics as a
    whole. The computation of visually plausible images is
    time-consuming and far from being realtime at present. A significant
    part of computation in global illumination algorithms involves
    repetitive computing of visibility queries.
      In the thesis, we describe our results in ray shooting, which is
    a well-known problem in the field of visibility. The problem is
    difficult in spite of its simple definition: For a given oriented
    half-line and a set of objects, find out the first object
    intersected by the half-line if such an object exists. A
    na\"{\i}ve algorithm has the time complexity $O(N)$, where $N$
    is the number of objects. The na\"{\i}ve algorithm is practically
    inapplicable in global illumination applications for a scene with
    a high number of objects, due its huge time requirements. In this
    thesis we deal with heuristic ray shooting algorithms that use
    additional spatial data structures. We put stress on average-case
    complexity and we particularly investigate the ray shooting
    algorithms based on spatial hierarchies. In the thesis we deal
    with two major topics.
      In the first part of the thesis, we introduce a ray shooting
    computation model and performance model. Based on these two models
    we develop a methodology for comparing various ray shooting
    algorithms for a set of experiments performed on a set of
    scenes. Consecutively, we compare common heuristic ray shooting
    algorithms based on BSP trees, kd-trees, octrees, bounding volume
    hierarchies, uniform grids, and three types of hierarchical grids
    using a set of 30 scenes from Standard Procedural Database. We
    show that for this set of scenes the ray shooting algorithm based
    on the kd-tree is the winning candidate among all tested ray
    shooting algorithms.
      The second and major part of the thesis presents several
    techniques for decreasing the time and space complexity for ray
    shooting algorithms based on kd-tree. We deal with both kd-tree
    construction and ray traversal algorithms. In the context of kd-tree
    construction, we present new methods for adaptive construction of
    the kd-tree using empty spatial regions in the scene, termination
    criteria, general cost model for the kd-tree, and modified surface
    area heuristics for a restricted set of rays. Further, we describe
    a new version of the recursive ray traversal algorithm. In context
    of the recursive ray traversal algorithm based on the kd-tree, we
    develop the concept of the largest common traversal sequence. This
    reduces the number of hierarchical traversal steps in the kd-tree
    for certain ray sets. We also describe one technique closely related
    to computer architecture, namely mapping kd-tree nodes to memory to
    increase the cache hit ratio for processors with a large cache
    line. Most of the techniques proposed in the thesis can be used in
    combination. In practice, the average time complexity of the ray
    shooting algorithms based on the kd-tree, as presented in this thesis,
    is about $O(log N)$, where the hidden multiplicative factor
    depends on the input data. However, at present it is not known
    to have been proved theoretically for scenes with general
    distribution of objects. For these reasons our findings are
    supported by a set of experiments for the above-mentioned set of
    30 scenes.",
}