A new Culling System for DarkRadiant

[greebo]

The last week I could spend some thought on a new culling system for DarkRadiant, which will be needed for any future renderer anyway. Following the old discussion we had with Namespace back in 2007, I had a go at implementing an Octree.

 

The first implementation took me a while, as I'm quite new to these things, and I hit a few harder problems (due to lazy bounds evaluation and some logical mistakes on my behalf). Once I had managed to get the scene nodes sorted into the octree properly (and on the fly), I added a new method GlobalSceneGraph().foreachNodeInVolume() which can be used to traverse the scene based on the given volume test - this was easy!

 

The next step was to migrate DarkRadiant's SelectionSystem to use the new method, which went rather smooth. I had to redesign one or two algorithms, as the old traversal code sometimes made the assumption that nodes were traversed depth-first, from parent to child node, which is not true anymore when traversing the graph based on the nodes' visibility in the view. The nodes are now traversed in any order, which made some changes necessary, but this went smooth.

 

And finally, I tried replacing the ForeachVisible template with another one using the octree space partitioning system. This is not really smoothed out yet, but I was astonished by the results already: before my change, the scenegraph was traversed in the old-fashioned style, which took about ~15000+ bounding box checks in gathers.map, each frame took about 98 msecs (non-lighting mode). When using the newer (hackish) octree walker, things went down and the same scene now takes no more than 500 bounding box checks at most, which is almost two orders of magnitude less. A frame takes now about 50 msec - pretty cool considering that this is just due to the culling, without any rendering optimisation like call batching or VBOs.

[OrbWeaver]

Sounds very promising, well done. It will be an improvement to have a scenegraph and selection system that actually makes it worthwhile implementing renderer optimisations, rather than holding it back.

[New Horizon]

Wow. Wonderful work Greebo! Taking Dark Radiant into the future!

[greebo]

Just merged the changes back into the trunk (we're at revision 5000, by the way!).

 

I changed the RenderHighlighted walker to derive from scene::Graph::Walker now, and removed the unnecessary culling code from it, so this should give another small performance gain.

 

This system needs serious test-runs before the next release, so as soon as I'm running out of steam, I'm going to compile a pre-release build for internal testing. I'm sure there are quite some crashes to fix.

[Tels]

Great news and good work!

[Noisycricket]

Isn't an octree like half of a graphics engine?

[Crispy]

Short answer: Yes. Long answer: Efficient culling is a very important component of a good 3D graphics engine, and an octree is one way to improve culling efficiency.

 

So yeah, greebo has heavily refactored a major system, again. Stop it greebo, you're making the rest of us look bad.

[SneaksieDave]

[New Horizon]

Greebo's got it going on!

[7318]

Zombie posting again...

 

can't this or something similar be implemented in the idtech4 rendering engine?