a technical blog

7DFPS – Day 2 – Binary Space Partition

leave a comment »

After all the coding for Day 1 i actually was a little exhausted and my brain still needed to digest some of the reading. So, I started the day of with a nice bicycle ride. That actually helped a lot. I had my moment of zen regarding Binary Space Partition on the bike: I think now i get how it will later help me for the static visibility calculations; i.e. Potential Visible Sets.

Anyway; the day again consisted of a lot of reading:

  • BSP Tree generation and how it can be used for visibility calculations, lighting and physics is really nicely described in this thesis. At the moment it is my main source of information on BSP and even though it is mentioned nowhere, I cannot help but wonder how closely the concepts are to what quake is using. But no mention whatsoever…
  • Some tips on BSP tree details are described in this rather simple txt file.
  • And before I forget it: My first introduction to BSP tree was from Michael Abrash’s Graphics Programming Black-book. It describes the concepts in 2d, but the above mentioned paper gives the full details on how to do it in 3D with all the necessary operations on Points, Planes and Polygons to actually classify faces and cut up the world.

My first result of a BSPed world that actually looked like this:


Turning of the z-Buffer, it actually rendered the world correctly in back to front order. Reason enough the algorithm is correct. But obviously, the world was partitioned to much. All the detail architecture like stairs and boxes contributed to the world partition. Which is not what e.g. Quake 2 is doing. There is a distinction between structural and detail architecture. The BSP is generated from the structural architecture alone and then the detail architecture is justed pushed into the leaves of the BSP tree. If the choice of the split planes is good, the partitions of the world should end up in almost each convex room of the world ending up in a leave of its own.

The main problem I found out that the map editor Trenchbroom is for Quake 1 and it did not seem to have supported detailed brushes yet. So, no way to set this property. Also I was already thinking about texturing the world; and as all the map editors are inherently tied to id softwares WAD file format, I decided to switch to Blender for modelling the map. There already exists an export plugin to the .map file format and some great introductions in how to use Blender for modelling levels for this format. Check here and here.

The Blender export plugin actually also did not support detailed brushes but I knew enough about the python API to add this feature. Here a better split:

bsp_detailYou can see in the screenshot that the room is still unnecessary split. That’s because my split plane algorithm is rather naive and just takes a random face/plane.

What I still wanted to do but will push until tomorrow is the algorithm and the metric for choosing a good splitting plane in the BSP creation and visualization of the AABBs of the BSP tree leaves for debugging purposes. As all that will come next relies heavily on the BSP, this might be a helpful debugging tool…

After that, tomorrow consists of collision detection and simple physics or the visibility/PVS algorithm.

Written by 38leinad

August 11, 2013 at 8:54 pm

Posted in Uncategorized

Any thoughts?

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: