Framework 4 (Last updated: October 25, 2019)Framework 3 (Last updated: February 6, 2017)Framework 2 (Last updated: October 8, 2006)Framework (Last updated: October 8, 2006)Libraries (Last updated: September 16, 2004)Really old framework (Last updated: September 16, 2004)
Monday, February 6, 2017 | Permalink
Back in the early days of consumer level 3D graphics hardware, BSP trees were a common component in rendering systems. Over time it fell out of fashion as the geometric complexity increased exponentially, scenes became more dynamic, and mesh data and processing moved over to the GPU side. With that said, BSP trees do have a number of desirable properties that made them attractive solutions for the static world geometry. One such property is that one can easily traverse a BSP tree in strict visibility order. If you don't have a depth buffer, you can render things correctly by traversing it back-to-front, and if you do have one, especially with Hi-Z rejection, you can instead traverse it front-to-back and get the maximum utilization of that hardware. Now this may not be a major concern today, but sorting things for transparency is still a problem we struggle to solve properly, and for static geometry a BSP tree can solve that quite elegantly.
So what this demo does is create a BSP tree to be processed on the GPU. While logically a binary tree, the layout in memory is linearly into an array, so as to be able to place it in a plain structured buffer for the GPU to read. The root node is the first element, then each element simply stores the size of the back-tree, which is enough information to be able to traverse the tree. A compute shader then does a parallel traversal of this BSP tree given the provided camera position, thereby producing an index buffer that is properly sorted back-to-front. The scene can then be rendered as a single draw-call. This index buffer is of course also reusable, so if no dividing plane in the tree has been crossed, there's no need to call the compute shader again. So a typical frame simply has a single plain draw-call with nothing really special about it. Then occasionally there's a frame with a BSP traverse call.
While the demo tracks when it needs to update the index buffer, it also provides a checkbox to disable this, so as to demonstrate its effect. If disabled, the rendering quickly becomes the usual unsorted mess of overlapping transparent geometry as you move away from the position of the last update.