Archived

This topic is now archived and is closed to further replies.

tom76

What are BSP trees?

Recommended Posts

tom76    122
I''ve seen them mentioned here in reference to DOOM, but can anyone give me info as to what they are? No need to go into too much detail, just the basics. Thanks! Observe everything, remember more!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
BSP stands for binary space partitioning. It''s a special case of binary trees.

A binary tree is a data structure which sorts data according to a binary (true/false, yes/no, etc) relationship between nodes. When the structure is written on paper, it looks like a tree branching outwords as you move down.

The first node added to a binary tree is always the root node. When a second node is to be added, it is compared to the root node, and depending on how the relation ship is setup, is set as either the left or right node of the root. For example, suppose there is a binary tree used to sort integers. In this particular tree, everything less than or equal to the root is placed on the left, and everything else to the right. If 23 is our root, when we try to add 13 to the tree, it will be added to the left, and 63 to the right, and so on. When we try to add a node to the current root, we check to see if there is something already there. If so, that something is recursively compared tot he new node. This causes a nice recursion where we traverse through the tree until we reach an empty node (or leaf, i think). Once we find an empty node, just put the node there.

This sorting method has several advantages. 1) It''s pretty fast, and 2) It allows you to access the objects in the order defined by the tree. In the integer case from earlier, we can go through in what''s called in-order traversal to access the integers in order from least to greatest.

Where this comes into play in games like DOOM is that the engine stores the level in a binary tree which is referred to as a BSP tree. The space partitioning part is because in a BSP tree, the nodes are the actual walls of the level and their relationship has to do with being in front of or behind the root node/wall, hence partitioning space. The hard part is choosing a good initial wall. You may also have to subdivide walls to account for the wall being both in front of and behind another wall.

The BSP tree can then be used for a lot of things, such as collision detection or culling, increasing performance and producing better framerates.

I guess that''s enough ''basics'', I''m sure there are many here who know an awful lot more about BSPs than I do, so if this isn''t enough, someone else will step in. Have fun!

Share this post


Link to post
Share on other sites
tom76    122
wow thanks, that''s really useful! Thanks for that.

Anyone else got anything to add?

Observe everything, remember more!

Share this post


Link to post
Share on other sites
PredeX    122
I found this article in Pixelate Issue #1 which explains BSp Trees. You can download this issue here: http://www.allegro.cc/pixelate/issues.html

Edited by - PredeX on October 17, 2001 6:18:31 PM

Share this post


Link to post
Share on other sites