Leafy BSP-Trees

[Jan]

I am working on my new engine and now i have a question about how i should do my BSP-Tree:

Should i store the polys in the tree nodes or only in the leafs? Up to now i stored them in the tree nodes, which makes the tree much smaller. However i read something about "Leafy BSP-Trees", where the polys are only stored in the leafs. I heard Quake uses this because it also uses PVS. So is it necessary to use leafy BSP-Trees to be able to use PVS or can i do this as well with "normal" BSP-Trees?
I am a bit confused because i am thinking of how to create a leafy BSP-Tree. It doesn´t seem to work, because the way i would do it, i always get more than one (not coplanar) poly in some leafs, which is wrong.

Thanks in advance.
Jan.

[dorbie]

It's not wrong to have >1 poly in the leaves. A node is defined by a polygon but each leaf is a volume surrounded by several nodes/polygons. The way Quake did the visibility was that in addition to every polygon being stored in a leaf, each leaf had a list of other leaves visible from the leaf the eye is inserted into. This means that once you insert the eye into the tree (by testing against nodes) you instantly get a list of visible leaves containing all the polygons you need to draw. With zbuffers you don't need span sorting or painters sort for example, but quickly eliminating most of your non visible geometry helps a lot.

[witcomb]

You may find it best to just store a chunk of polygons in the leafs. Let me explain a little bit better. Starting with the full polygon soup, start splitting as you would normally and keep only the splitting plane information an the tree nodes. When determining when to stop the splitting, use the number of polygons for a given leaf. If the number of polygons is small (ie. 100 or so) then say that this is acceptable.

The reason I suggest this is that when rendering this small polygon collection can then the tossed into a vertex array for rendering. You may end up rendering polygons which are not visible but this will let the graphics card deal with this problem. You will ofcourse have to use depth testing, unless you insist that the leaf nodes are convex hulls. This will basically be breaking your world down so that you will know what in general must be rendered and not what exactly must be rendered.

If you are going to be doing the rendering in software, this probably won't be a good idea, but for hardware this will work well.

Hope this helps,
Neil Witcomb