blue and an orange window, where the orange window is closer to the camera but should still be drawn behind the blue one, so the distance to the planes should be used instead (d0 and d1).

In this case using bsp is straightforward and cheapest. You don't need to calculate d0 and d1.

It's trivial to check which node to render first, you only need to calc single dotproduct of plane's normal and camera's direction vector.

What I'm getting from the comments so far is that BSP trees do have their use when I want to draw everything in the correct order.

Whenever I look up BSP trees, everyone is talking about planes, and I do understand how I can divide up my space if my objects are just regular planes.

But let's expand on Erik's example here. What if instead of a blue plane and orange plane, I had a blue and orange box, or better yet a blue and orange teapot.

How do i create a BSP tree for something like this? Do I define a bounding box for each item and use the bounding box' planes for creating my BSP tree, or is there some other accepted way of doing this?

I know my questions are touching on some really basic stuff here, but I can't seem to find a straightforward answer to this. Some real life example of a scene containing some 3D objects that is partitioned step by step into a BSP tree would seriously come in handy.

What a BSP really does is divide your entire world into convex volumes. If your objects have bounding-boxes that never intersect you can sortof build a BSP using just the bounding-boxes... but.. the boxes will get split even if they don't intersect if you build a tree of an entire map.. so.. it doesn't really make sense anymore.

(You can build a BSP using the triangles in a teapot, but that makes even less sense).

So, I think in your case you don't want a BSP. BSPs are all about planes, binary space partitioning, binary in the sense of every partition divides into exactly two. A plane divides space into two convex (possibly infinite) volumes, while a box divides it into one convex volume inside the box, and a concave volume outside the box. A BSP of the faces of a box actually creates 7 convex volumes, 6 outside the box and 1 inside the box.

BSP trees allow to easily traverse the scene in back to front order from any point in space, so you can render a scene without z buffering.

For a modern renderer BSP trees are too complex and restrictive. Z buffering is a lot more flexible.

BSP’s were useful in the days when geometry wasn’t so complex.

This is a good point, but from what I've seen, you can still do pretty neat things with BSPs.

If your goal is accurate rendering, you will cut triangles, increasing the triangle count, and slice geometry into multiple parts, increasing the draw-call count.

Not necessarily. I would think that BSP trees can also be used just for sorting, without necessarily having to do accurate rendering. Instead of splitting the polygons that intersect the splitting plane into the left and right branches, you can just add the same polygon to both branches. You still do the split offline, for the purpose of correct BSP compilation, but the final BSP tree will have the non-split polygons. Then, when traversing the tree, you just check that each polygon is only added to the rendering queue once. And if you still want accurate rendering, you don't have to cut all polygons - just the transparent ones that intersect with other transparent polygons, but this is usually done by CSG, so there's nothing else you have to do during BSP compilation - you'd have to do this anyway if you want correct transparency, and intersecting polygons should be a rare case anyway, because artists know to avoid it.

frame-to-frame temporal coherence

You can do this with BSPs too - you just remember which BSP cell the camera is in, and if the camera doesn't move from one frame to the other, you don't have to traverse the BSP again - you just use the geometry from the previous traversal. Also, if the camera does move, you can re-build the rendering queue only if the camera actually passed through a portal plane (from one BSP cell to another) - you can just keep the portal planes in a separate list if you want to avoid BSP traversal just to detect which portal was crossed.

since you don’t sort the actual objects in the render-queue, but rather the indices to objects in the render-queue, you can keep the indices in sorted order from last frame

You can use indexed geometry with BSP trees as well. In fact, that's exactly how the BSP tree references the actual polygons, IIRC. If all of your polygons are already in a vertx buffer, all you have to do when traversing the BSP tree is build an index buffer.

There is virtually no way a BSP tree can beat such a system. The simple act of traversing a BSP tree incurs many more draw calls, dot products, branches, and an explicit stack (to avoid recursion).

If you use indexed geometry, you can reduce the number of draw calls to 1 (for all of the opaque geometry) + number of transparent polygons. This is the minimum number of draw calls you can get away with in any case, if you want proper transparency.

Besides that, if we are talking about Direct3D 11 or OpenGL 4.0, compute shaders and order-independent rendering would be better than BSP trees.

Sorry, I'm still not convinced. Maybe I just like BSP trees too much. Besides, what would keep you from using compute shaders for BSP geometry? Although if the geomtery is static, why would you need to compute it at run-time?

geometry these days will be so heavily subdivided you will definitely create slithers

A correct render-queue will always be faster, but there can be artifacts.

render-queue easier to implement

This is actually the point I wanted to get to... The furthest I ever got with implementing BSP was a Quake III BSP loader with collision-detection I wrote from scratch. However, Quake III's BSP does have all the issues you mentioned.

So I've been reading and thinking about implementing my own BSP compiler for a few years now that gets rid of all those issues.

What I like mostly about BSP trees though, is that they're useful for collision detection - not rendering. So maybe this makes me a bit biased...

Anyway, simply because of the complexity involved in implementing proper BSP generation, I'd probably not use BSP in a professional project (unless I had a team of math geeks behind me) - and this is the only reason (at least for me).

I've been working as a programmer for several years now, so I know my way around a programming language or two. I've been doing some basic stuff with OpenGL (I worked for a company using OpenGL for their 3D cartographic applications), but as you can all probably tell, I've still got a lot to learn.

This FPS I'm developing for the moment is more of a stepping stone to get myself acquainted with game programming. The environments I'm creating contains mostly simple convex shapes (although their poly count can get a bit high at times).

From L. Spiro's comments I've deduced that using BSP trees may be a bit overkill for the purposes I have in mind. I'm also not so thrilled about cutting into my existing polygons or in other ways complicate the geometry of my scene, so I think I'll just take L. Spiro's advice and go with a render queue implementation that does some basic sorting of my objects.

Anyway, thanks for all the help. It's nice to know that there is a large community to fall back on .