# How does a BSP tree work for Z sorting?

I'm developing a 3D engine in software, and so I must compute Z sorting manually. I'm currently using the painter's algorithm to sort triangles and then drawing them back-to-front. This causes artifacts that I'm trying to correct.

1. Would using a dynamic BSP-tree ensure "correct Z sorting" of triangles? Why? Because the bounding volumes of triangles would be similar?

2. Since I would have a single "world" BSP tree, would I have to remove and re-add any moved/scaled/rotated object into the tree?

3. Is it possible to add triangles into a BSP tree without the expensive cutting process? Why do you need to cut triangles on the axis planes anyway?

4. Is it faster to traverse a BSP tree from any angle, than to sort all tris each draw like the painters algorithm?

• You will always have artefacts if you draw triangle per triangle, BSP or not. That is why the Z-Buffer became so popular in the nineties ;-) BTW, sorting triangles is usually used A) for drawing semi transparent triangles and/or B) for optimizing overdraw. Nov 17, 2011 at 8:35
• Possibly related: gamedev.stackexchange.com/questions/14365/… Nov 17, 2011 at 9:17
• @bummzack - Nice hint about quad-trees, thanks. Nov 17, 2011 at 10:44
• @Jenko Just out of curiosity: Are you implementing a Flash 3d renderer to learn about 3d graphics? Or are you unhappy with the existing 3d engines? Also since Flash player 11 is out, why not leverage the GPU APIs? Nov 18, 2011 at 8:27

1. Using a dynamic BSP tree can ensure correct z-sorting of triangles, if you draw those triangles by walking through the BSP tree, and if you have only one triangle per BSP branch. The basic idea is that each branch of your BSP tree breaks up space into two pieces (typically "in front of" and "behind" that triangle). By checking which of those two pieces of space contains your camera, and drawing the other one first (recursing into the BSP tree branch for that space, if you're not in a leaf node), then you're ensured that you always draw the tree from back to front, which is exactly what you need for the painter's algorithm.
2. Yes. Adding or moving triangles will require re-building the BSP tree, which can be very computationally expensive. Most games with moving objects do not include those moving objects as part of the BSP tree for exactly that reason, and instead build a separate BSP tree for each movable object, and then pick an order in which to draw those movable objects using a more traditional z-sorting.
3. You CAN add triangles into a BSP tree without clipping them according to your BSP planes (so triangles may have corners 'poking through' the division planes), but doing so can result in errors in the back-to-front traversal of the tree. In fact, there are many situations where it's impossible to correctly draw a set of triangles from back to front, simply because they overlap in a complicated manner (for example, it's possible to arrange three long, slender triangles in a loop such that each overlaps the next, and none is entirely "in front". In this situation, the only way to make these triangles render correctly is to split the triangles, and z-sort the triangles after the split. The BSP triangle cutting process typically handles cutting triangles which might have this problem automatically, while building the BSP tree). But you don't necessarily have to cut triangles on cardinal axis planes, as you imply -- in fact, when building your BSP tree, it's often most convenient to pick one of the existing triangles in a space, and to use the plane of that triangle as the split plane for cutting the other triangles into "front" and "back" groups.
4. It is much, much faster to traverse a BSP tree than to sort triangles naively. Traversing a BSP tree requires a vector subtraction and a dot product at each branch, while a sort requires.. well.. a sort. So one is O(n), while the other is probably O(n*logn), depending on the sort algorithm you choose. That can be a huge difference, when you're dealing with a large set of triangles.
• What a fantastic answer! Thank you very, very much Trevor! Nov 17, 2011 at 10:33
• In point 2 you said "using a more traditional z-sorting" ... what exactly are you referring to? I cannot do Z buffering in software, so do you mean sorting objects based on their center points? This is not possible because I'm trying to render many objects fitting into each other, so then I would have to use triangle sorting for those objects? Nov 17, 2011 at 10:42
• @Jenko: That's exactly the case. BSP trees are good for sorting and rendering large static geometry efficiently. Things like Doom levels, for example. As soon as you need to modify their contents in real-time, you'll likely find that the BSP creation takes up too much time to maintain a good frame rate. In a case like yours, I'd be seriously considering z-buffering or s-buffering, instead. Is there a reason you can't do z-buffering in software? All you need is a 2D array of floats to store "closest z value" into. Nov 17, 2011 at 20:42
• And yes, by "more traditional z-sorting", I meant sorting whole objects based upon their centre points. (Alternately, references to these moving objects can be inserted into appropriate branches of the level's BSP tree, and be rendered when the level rendering reaches those branches) Either way, you can absolutely get polygon draw order issues between movable objects and static geometry, but it avoids having to rebuild the whole world's BSP tree every time an object moves within it. Nov 17, 2011 at 20:48
• I could try, but I'm pretty lame working on the Flash Player. You just don't get native C++ performance. 1% of native performance is usually what you get writing in ActionScript; I could try some tricks but even the final rendering to screen is very slow if you try doing it pixel-by-pixel (a.k.a. no access to the screen back buffer, you have to work with some fancy OOP objects and the Player does the rest) .... I'm currently letting the Player render the triangles for me so its somewhat survivable. (1K tris at 25 fps?) Nov 17, 2011 at 20:48

As per request :-)

You will always have artefacts if you draw triangle per triangle, BSP or not.

That is why the Z-Buffer became so popular in the nineties ;-)

BTW, sorting triangles is usually used

A) for drawing semi transparent triangles and/or

B) for optimizing overdraw

• "sorting triangles is usually used" ?? You mean just keeping a list of triangles and sorting by barycenter per redraw? Nov 17, 2011 at 10:28
• Well, if you sort triangles at all, it is usually to do (semi)transparency or to reduce overdraw on the Z-Buffer (draw the triangles closest first). You can sort them in any way you want (closest point, centre etc.) there might always be errors. The 'sorting' is of course according to the camera position. If I didn't answer your question, please do tell, I'll try to be more specific. Nov 17, 2011 at 10:38