CSG Rendering and the Computational Power of
Two-Sided Depth Tests on the GPU
Abstract:
Recent advances in the design of graphics rendering hardware (the GPU) has led to a wide array of work exploiting the GPU to solve various general purpose computing problems. In this paper, we suggest approaches to analyzing the computational power of the graphics pipeline from a formal point of view.
We revisit the problem of rendering objects described by CSG (Constructive Solid Geometry) operations. In an earlier work we had shown that the shadow mapping hardware in modern GPUs can be exploited to provide faster algorithms. The shadow mapping test, along with the usual \emph{z-}buffer test, is known as the \emph{two-sided depth test}. We improve upon the algorithm and, further, show in a formal setting that the current algorithm is asymptotically the best possible. We implement this algorithm and demonstrate its efficacy in practice in comparison with the best known approaches for CSG rendering.
We also consider the problem of selecting specific depth layers (which we call \emph{depth picking}) in a scene, without going through the layers one by one. We give an algorithm and an implementation which achieves the goal in $O(\log n)$ rendering passes. Once again, we prove that this algorithm is the best possible in a formal sense. We also implement this algorithm on standard graphics hardware and show that its practical performance agrees with the formal analysis.
Example Images
Sample CSG objects from Bradley Fighting Vehicle (Courtesy: Army Research Labs)
Levels 1, 2 and 7 of the Voronoi diagram arrangement for a point set