The BSP Tree project implements the basics of a strategy game interface to showcase data structures in C++ using DirectX 9 for graphics. The largest of the data structures included in the project is the BSP Tree used to calculate the objects which need to be rendered. In addition, the project utilizes the factory structure of the KLibrary, which is used to load texture and model files without repetition.
While writing the coding, I implemented functionality which uses frustums for selection when the user selects a rectangle on the screen, as well as to selectively render only those objects which are visible. For the selection, four planes are calculated from the four corners of the square the user sets, and then the dot product between each plane and the location of the object is calculated. If all four of the planes return a dot product greater than or equal to 0, the object is inside the frustum and the object is selected. If any of the dot products is negative, the object is outside and is not selected. A similar methodology is used to determine which objects are inside the render frustum, however the BSP Tree also checks if the division planes are inside the frustum, and determines which sides of the plane should be further checked. The BSP can also be used to implement occluders in the 3-D world.
