BSP Tree Generator


After playing with crafting my own OpenGL graphics engine, I realized that optimization was key in developing interactive 3D applications, such as games. One such game that facinated me during this time was Quake. I researched what techniques made this game tick, and I stumbled upon a very detailed article explaining the BSP tree algorithm. Needless to say, this project consumed me for months as I stumbled upon the tree data structure and how it could be used in order to divide geometry and render only what is visible to the camera. Using Visual Basic 6, I was able to implement:

  • 3D Mesh file import capability
  • Automatic BSP tree generation
  • BSP generation in small increments
  • Color for each node
  • Color for each triangle which divides nodes
  • A list of triangles for each

Because Visual Basic 6 has no support for pointers or dynamic memory allocation, the tree data structure had to be implemented with an array of a predefined size, with the child nodes (left and right) being indexes. This project provided me with excellent problem solving skills and additional 3D math knowledge.

Skills Used:

Visual Basic 6
Binary Trees
3D Math