Using Annotated KD-Trees to Accelerate Shadow Ray Queries

Peter Djeu and Stan Volchenok

The University of Texas at Austin, Department of Computer Sciences
Technical Report TR-08-36, August 30, 2008

Abstract

We present preliminary work on a new algorithm to accelerate shadow ray visibility queries by using a volumetric proxy representation of the original shadow caster, which we assume is specified as a polygonal mesh. The algorithm creates this proxy representation by building an annotated kd-tree over the mesh. Certain nodes in the kd-tree are marked as voxel proxies for the original mesh based on a classification heuristic. These voxel proxies are used in tandem with the original mesh to accelerate shadow ray queries while maintaining high shadow quality. In addition to proposing the algorithm, we present results on the importance of using an appropriate surface area metric during build and extend the approach to use average normals in order to reduce blockiness artifacts along the silhouette. Finally, we present some static measurements of the required computation which indicate that this work is a promising, although not-yet-fully-realized approach to improving real-time shadow ray evaluation.

Paper

Movie - Illustrates that temporal artifacts are not a problem when using annotated kd-nodes to generate hard shadows.

BibTex

@techreport{djeu:akdt:08,
  author = {Peter Djeu and Stan Volchenok},
  title  = {Using Annotated KD-Trees to Accelerate Shadow Ray Queries},
  number = {TR-08-36},
  month  = {August 30},
  year   = {2008},
  institution = {The University of Texas at Austin
                 Department of Computer Sciences}
}