How BSP and other optimizations work ?

Newbie & Debugging Questions
#1

Hello everyone,

I’d like to ask a few questions about BSP trees, or generally about any methods that split the scene into more parts :wink: I’ve studied these methods in theory,but never used. Now I have my own OpenGL engine written in Java and I’d like to use these optimalizations.

  1. WHEN is the world split into more areas ? Does this happen when you export your map out of your editor ? Or does the engine load the map and does the splitting ?

  2. Is it ok to test an object placed in more BSP logical parts of the scene in every one of them ? Or is there a different approach ?

  3. Are there any good tutorials HOW EDITORS work ? I still wonder what’s the difference between 3DMax and GTK Radiant. I can import my models to GTK, but game maps seem to be made of much less polygons … Is the engine support related ? Is it connected with BSP ?

Thank you for your replies. :slight_smile:

#2

  1. Depends. For Octrees(fixed node), it’s usually a set number of polygons per node. For KD Trees(balanced octrees), the same as octrees but the number of node depends on the number of polys on a scene. For BSP trees (a non-axis alingned KD tree), well, same as a KD tree but with addition of a thing called PVS (Polygon Visibility Set).

  2. Collisions(assuming this is what you mean) is also dependent upon the spatial partitioning you use. For octrees, I just do a sphere to cube intersection for each node and if the sphere intersects a node, collide with all the polys inside the intersected node using the “plane equation”.

  3. I cannot help you there since I cannot make 3d models if my life depended on it. But basically just import (obj is the easiest) read the model and construct your octree, kd tree or bsp tree. You can save your tree on a file or calculate on the fly.

Tute (trees and quadtrees):
http://rel.phatcode.net/mytutes/octreetute/octree_tute.zip

Binary and source for an octree:
http://rel.phatcode.net/junk.php?id=88

PS. Are you sure BSP trees are what you need? Octrees and KD trees beat the crap out of BSPs in scenes that don’t have lots of walls. ie. Outside scenes. BSP trees work best in dungeon type scenes.

#3

BSPs got popular because Doom then quake used them. Back when doom was doing it, it was because you can do the painters algo pretty easy and add some tricks to that to improve things even more. Remember that Opengl was something only million dollar machines had at the time…Well at least a few 100k.

The painters algo is simply drawing things far away first. BSP allow you to easily traverse in a depth order from where ever the viewer is quickly.

They are perhaps not really a good match for modern hardware, but then again it depends.

I wrote one way back when i was still young. There are a few tricks to make sure the BSP is balanced. Also you need to “cut” large flat surfaces a lot when there are lots of little surfaces. So there are lots degenerate cases that you must consider. BSP take in triangle, for each triangle the space is cut into 2, the side “above” the triangle and the side below the triangle. As you can imagine, there are some triangles that are both above and below. These need to be cut.

So yea. Can’t see why one would use BSP these days. Perhaps there are some cases where you can “compile” the map and then make some of the drawing code faster. But i can’t see it being easier or better than some of the other spacial tree structures theses days.

#4

For highly occluded scenes: cell & portals = win.

#5

I would still think something like a quad/oct tree would work better. It can partition the space at wall/room boundaries.

#6

Plus, you can sort the nodes from near to far so that rendering is near first. That way, fillrate would astronomically be lower.

#7

There’s no mutual exclusion here. Spatial partitioning is great at spatial queries, so “tell me all geometry within the frustum” should be a fast operation. What most are very pretty poor at is the hard part of generating a near minimal potentially visible set: “tell me the (close to) minimal set of visible geometry”. Cell & portal’s trivially handle that problem. So the cells store the spatial partitioned data (as individual sets) and portals are the connection graph.