Tank Fury Game Project Details

The level data, ( the world ) is organized in a bsp tree model with a few customizations. The way I approached the bsp tree at first was the generic way as follows ,

Pick a polygon , any polygon - becomes (this) root node.
Use the plane of the polygon to split all other polygons into two collective parts, the two parts become the leafs of (this).

For each part
    Pick a polygon from the part - becomes root node of the new split to follow.
    Use the plane of the polygon to split all other polygons into two parts, the two parts become the leafs of (this).

Repeat the above step subdividing the polygonal object further and further until no more polygons remain.

This worked fine, however it produced a huge amount of world data , and slowed down rendering somewhat as more polygons were generated each time the scene got cut in half, but still produced a speed gain as opposed to rendering the entire scene.

Time to put in some optimizations.
Some things to try are:

Optimize plane selection, by using brute force method of finding a polygon with least splits produced and with best balance of left vs.. right population.
This improves things reasonably to make it worth while, but it also demands long computational times, very very taxing on time.

Optimize plane selection with N depth search, this is as above but with searching for the best gain in tree balance and least splits by trying the next N level down and splitting it to see what we get (for each poly of course) and then choose the best one. This method   is superior, but the amount of Cpu power needed to accomplish the Bsp sort on a level makes it not worth the effort. It just takes too long .

Optimize by supplying a hint , what I mean by hint is to place a hidden polygon in the scene indicating the plane of the tree root, it can be very advantageous to hard code (hard model) the trees first plane.

Optimize by supplying N hints, as above, but increase the depth of pre-defined split planes for the tree, this ranks as the highest benefit on the optimization list.

Optimize by splitting the world into N depth uniform cubic shapes, this is excellent for producing a more evenly balanced tree.

There are many options to be taken as you can see, in the case of my implementation I used a combination.
Supplied 2 depths of hints , after this split the next 3 depths into uniform cubic shapes, and for the remainder I used intelligent plane selection with a rough criteria of: each branch can not be smaller than 30% of the original , or bigger than 70% and search for the least splits.
This resulted in a Bsp tree that was not too bad in terms of balance and split rate.

Finally one other optimization that I planned to make but didn't have the time, was to clump the last 4 or 5 polygons into a linked list. The benefit of further splitting a 5 polygon scene would on average produce more overhead than simply traversing the 5 polygons sequentially.

There are many other optimizations to consider, and ways to improve upon them but that's up to the coder, it boils down to a simple question you ask your self, do you want a manageable headache or a never-ending headache :)