Continuing in my tradition of working on things which can’t have screenshots taken of them…

I’ve recently begun a short-term goal of putting a forest of thousands of trees into MMORPG Tycoon 2.  This task has two obvious sub-tasks, and a few non-obvious sub-tasks.

The obvious sub-tasks are (1) create a tree model — preferably using the procedural geometry creation systems which I’ve already built, so that we can have a couple of different types of trees without any extra labour on my part.  And (2), put lots of copies of those tree models into the world.

The big non-obvious sub-task is that I need to come up with a mechanism so that I won’t be sending every tree in the world to the graphics card to be rendered every frame — only the ones which could potentially be visible right now.  But at the same time, I don’t want the CPU to overload itself, testing each individual tree to see whether it might be visible.

In video games, the usual approach to this sort of problem is to divide up space, and then test the different bits of space for visibility, instead of testing each individual object.  You can think of it a little like arranging lots of small objects on a chess board — instead of checking each tiny object to see whether it could be visible, you instead can check each square of the chess board to see whether that square might be visible, and if so, then draw every object inside that square.

This approach is usually a pretty good compromise between spending a lot of time on the CPU determining precisely what objects will be visible when drawn by the graphics card, and between spending a lot of time on the graphics card drawing objects which turn out not to even have been in front of the camera.

The particular scheme that I’ve just finished implementing today is an “Octree“;  you can think of it a little bit like a chess board where each square contains another whole chess board (except in 3D!).  While I haven’t built any trees yet, I’ve converted the MMORPG buildings over to render through the octree, and tomorrow I’ll spend an hour or two moving several other types of objects over into the octree as well.  Theoretically, the 3D cursor should be a good deal faster to calculate via the octree as well, but I’ll probably leave that optimisation for later on.

But for now, I need to grab some rest.  Didn’t get nearly enough sleep last night!