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!