BSP: Work in Progress

Over the last few days I have been implementing the BSP tree compiler, as well as traverser. Until now there has been nothing new to show except for segfaults. I can now report that my implementation works, in the sense that the program does not crash, and a subset of triangles are given to the renderer.

However, the tree traversal algorithm, which determines the set of triangles that are rendered, is currently wrong. As an example, here is a scene with BSP disabled. That is, all polygons are considered for rendering.

An overview of a large (roofless) room

If the BSP algorithm was correct, the render would look exactly the same with BSP enabled, yet the following image is produced instead.

A partially rendered overview of a large (roofless) room

The course’s lecture materials and Wikipedia have conflicting information about what to actually do with the BSP tree. The lecture slides suggest that BSP is about disregarding polygons outside of the view of the camera (such as those that are behind the camera).

Wikipedia’s description, however, suggests that BSP is about disregarding polygons that are obstructed by others, only taking into account the position of the camera, not its rotation. Perhaps there are several different ways to utilize the tree.

My current implementation is based on the lecture slides, but I don’t grasp how the logic is supposed to work, even for the example given in the slides. Also, even if the logic is correct, it’s very likely that there are errors in my implementation of that logic; in above image, all polygons are in the view of the camera, and should thus be rendered in any case.

My work continues with figuring all of this out.