Thursday, October 21, 2004

I need...more speed...

So I fixed a nasty bug in the rendering code that was causing everything in the Mars and Aqueduct worlds to run 1/2 speed. What was happening was the models that make up these scenes were being installed into the TQuadTree object twice when it was being constructed. This means every single element got rendered twice. Hence, not only did it seem like it was running at 1/2 speed - it probably was.

A TQuadTree is an object that breaks space up into four quadrants - I call them top left, top right, bottom left, and bottom right. Each of the quadrants is actually a TQuadTree itself and is in turn broken up into four quadrants. In theory, this recursion can continue infinitely, but in reality, I stop after a depth of 5. Also, if a quadrant would otherwise be empty, it is set to nil.

We actually create the TQuadTree object with the act of dropping a collection of frames into it. Each of these frames has it's own boundSphere around it, and we compare this to the size and location of each quadrant. If the object can't be put in one of the sub-quadrants because it is too large, we just leave it at the containing quadrant. Thus, each sub-frame eventually comes to rest at the quadrant that best approximates it's size.

So why deal with QuadTrees? The idea is that an object is easier to find (for picking or rendering) by traversing this tree of quadrants. Objects are placed into the TQuadTree based upon location and size. For example, if you need to find a point directly underneath you, you already know which quadrant you are in, so you can test just that one. If that fails, you can test it's subquadrants, etc., until you find an object to stand on. This is ignoring the fact that objects tend to overlap quadrant boundaries, and in fact I deal with this as well. The TQuadTree is what is known as a loose quadtree. That is a quadtree that allows overlaps, but requires that you test all of the edge quadtrees as well. This works surprisingly well, as we only need to put an object into the quadrant that contains it's center point. If you don't use a loose quadtree/octree method, you can use a strict method, but this requires you to duplicate the object in all of the quadrants it overlaps.

The other win that quadtrees like this gives you is improvements in rendering speed. If a quadrant is visible to the camera, then it is quite probable that the contents of that quadrant will be as well. More importantly, if a quadrant is NOT visible, then we have a guarantee that it's contents are not visible. The same overlapping/neighboring quadrant test applies to rendering as well.

One way to think of the process of constructing an octree is that of a collection of sieves- one on top of the other - with the ones with the larger holes on top, and smaller holes as you go down from there. The objects that make up the scene fall through the larger ones until they no longer can fit in the lower ones. When the sorting is all done, each object is at its proper location in the sieve.

One other benefit that loose quadtrees give you is it is much easier to move an object around in one of these. Since only one copy of the object exists in the tree - we need only move it from one quadrant to another when it's center point has moved across the boundary between them. Bookkeeping is extremely simple.

No comments: