“The Area Perspective Transform: A Homogeneous Transform for Efficient In-Volume Queries” by Hunt and Johnson

A key problem in applications such as soft shadows and defocus blur is to identify points or primitives which are inside a volume of space. For example, the soft shadow computation involves finding surfaces which pass in front of an area light as viewed from a point p in the scene. The desired surfaces are those which are inside a frustum defined by the light and p, and can be found by intersecting the frustum with an acceleration structure over geometry. However, accurately computing this intersection is computationally intensive.
In this article, we introduce a homogeneous transform which reduces the computation required to determine the set of points or primitives which are inside a tetrahedral volume. The transform converts tetrahedra into axis-aligned boxes, substantially reducing the cost of intersection with an axis-aligned acceleration structure over points or primitives. We describe the application of this transform to soft shadows and defocus blur, and briefly consider potential uses of the underlying mathematical approach in higher-dimensional problems.

1. Aila, T. and Laine, S. 2004. Alias-free shadow maps. In Proceedings of the Eurographics Symposium on Rendering. Eurographics, 161–166. 
2. Assarsson, U., Dougherty, M., Mounier, M., and Akenine-Möller, T. 2003. An optimized soft shadow volume algorithm with real-time performance. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS’03). Eurographics, 33–40. 
3. Benthin, C. and Wald, I. 2009. Efficient ray traced soft shadows using multi-frusta tracing. In Proceedings of the Conference on High Performance Graphics (HPG’09). ACM Press, New York, 135–144. 
4. Boulos, S., Wald, I., and Shirley, P. 2006. Geometric and arithmetic culling methods for entire ray packets. School of Computing Tech. rep. UUCS-06-10, University of Utah.
5. Cook, R. L., Porter, T., and Carpenter, L. 1984. Distributed ray tracing. SIGGRAPH Comput. Graph. 18, 3, 137–145. 
6. Greene, N. 1994. Detecting Intersection of a Rectangular Solid and a Convex Polyhedron, P. S. Heckbert, Ed. Academic Press, Chapter I.7, 74–82. 
7. Hunt, W. A. and Mark, W. R. 2008. Ray-Specialized acceleration structures for ray tracing. In Proceedings of the IEEE/EG Symposium on Interactive Ray Tracing. 3–10.
8. Johnson, G. S., Hux, A., Burns, C. A., Hunt, W. A., Mark, W. R., and Junkins, S. 2009. Soft irregular shadow mapping: Fast, high-quality, and robust soft shadows. In Proceedings of the Symposium on Interactive 3D Graphics and Games (I3D’09). ACM Press, New York, 57–66. 
9. Johnson, G. S., Mark, W. R., and Burns, C. A. 2004. The irregular z-buffer and its application to shadow mapping. Tech. rep. TR-04-09, Department of Computer Sciences, The University of Texas at Austin.
10. Laine, S., Aila, T., Assarsson, U., Lehtinen, J., and Akenine-Möller, T. 2005. Soft shadow volumes for ray tracing. ACM Trans. Graph. 24, 3, 1156–1165.
11. Olano, M. and Greer, T. 1997. Triangle scan conversion using 2D homogeneous coordinates. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hardware. ACM Press, New York, 89–95. 
12. Sintorn, E., Eisemann, E., and Assarsson, U. 2008. Sample based visibility for soft shadows using alias-free shadow maps. In Proceedings of the Eurographics Symposium on Rendering. Eurographics, 1285–1292. Comput. Graph. Forum. 27, 4. 
13. Wald, I., Mark, W. R., Günther, J., Boulos, S., Ize, T., Hunt, W., Parker, S. G., and Shirley, P. 2007. State of the art in ray tracing animated scenes. In STAR Proceedings of Eurographics, D. Schmalstieg and J. Bittner, Eds., The Eurographics Association, 89–116.