Kurt Miller Click the name for some bio info E-Mail: kurt@flipcode.com http://www.flipcode.com/kurt/grain/

03/15/2000, Miscellaneous Jargon

   Main Window
       |__ Left Frame  (CFrameWnd)
       |      |___  Tree View (not shown)
       |      |___  Control Panel (with dialog tabs)
       |
       |__ Right Frame (CFrameWnd)
              |___  4 Views (CFormView)

Create your root node. This is a giant cube that encompasses your entire world. Find the maximum and minimum values in your world, and use the absolute max value on any axis to create a perfect cube. If you'd like, you can check that your world is centered, so that say one polygon way out in the middle of nowhere won't goof up your balance. You may find it easier to work with "cubes" as just being 2 points in 3-space (the min and max corners), which you can probably simplify further if you want since we're just talking about cubes.

For the next step in your build procedure, you need to examine your child cubes. Create the children by creating a cube half the width, half the height, and half the length of your original (root) cube. Just copy and offset that smaller cube 8 times to get your children in the right places in relation to the parent cube. You'll also need a temporary polygon list for each child (so for example create 8 new linked lists of polygons).

Now take your polygon set that was passed into the build procedure (for the root node, it should be your entire polygon set), and check them against each of the child cubes. That means you need to check if any polygon in this set is partially or completely inside any of the child cubes. If a polygon is completely inside one of the children, add it to the temporary polygon list for that child node. If a polygon is partially in more than one child cube at the same time, you need to make a choice. You can either add the polygon to both child node's polygon lists, or you can split the polygon against the cube boundaries and only add the pieces to a child node's list that are left over and thus completely "inside" that node. If you choose not to split, you can still pretty easily maintain efficiency by keeping a flag for polygons in your engine so that later on when you're processing polygons, for example rendering, you can mark them as processed. This way, the next time that same polygon shows up, you know its already been visited.

The next step is where the recursion comes in. You didn't really think you'd get away with building a tree without recursion did ya' :)? But don't worry! Recursion is fun, and in this case its very simple. What I just described in the previous steps is what pretty much makes up the build function. So now all you have to do is the exact same thing for all of your child nodes! You call the build function again for each child node, and give it the child cube and temporary polygon list for that child. It will work exactly the same as I described above for your root node, but now it'll do it for the children. In this way, the process will continue as each of the children of the children of the children... of the children does the same thing for its children. This will continue to go forever (or until your OS crashes :) unless you add stopping criteria! That's the one thing that's missing from the build function so far.

So when do we stop this process? Again, you have some choices. Some of the more popular stopping signals are either based on the number of polygons passed into the child's build function or the size of the child cube. Obviously you don't usually want to check if polygons fit in a 1x1x1 cube. But as an example, lets say that you make your recursion stop when a child node has 100 polygons or less, or the cube is less than 100 units (any direction). These constants are pretty much dependent on your data set, so use appropriate values. Now in our example, suppose the build function is called for a child with 75 polygons passed in. We would now mark this node off as a leaf and store the polygons in the node. This node will never have children. Keep in mind that you were NOT storing the polygons in each child node as we were building the tree. I tried to emphasize that you were simply creating a temporary polygon list, because only the leaf nodes will ever store polygons. When you've met your stopping criteria, you save the list of incoming polygons and return. That's about all! The rest takes care of itself if you did a good job coding it. Pretty neat, yes?

	octree_node :: build( poly_list *plist, point *min, point *max )
	{
	    if( stopping criteria )
	    {
	        save plist into this node's polygon list;
	        return;
	    }
	
	    point cubemin[8], cubemax[8];
	
	    split_up_cube( min, max, cubemin, cubemax );  // fill the arrays;
	
	    poly_list *temppoly[8]; // temporary poly list for each child;
	                            // be sure to allocate / initialize them;
	
	    for(int i=0; i<plist->get_count(); i++)
	    {
	        for(int c=0; c<8; c++)
	        {
	            if( poly_partial_in_cube( plist[i], &cubemin[c], &cubemax[c] ) )
	               add the polygon to temppoly[c] // may end up in more than one child
	        }
	    }
	
	    for(int n=0; n<8; n++)
	    {
	        if( temppoly[n]->get_count() )
	           child_node[n]->build( temppoly[n], &cubemin[n], &cubemax[n] );
	    }
	}

03/15/2000 - Miscellaneous Jargon

02/20/2000 - Bits And Particles

09/09/1999 - Interface Design Ramblings

08/16/1999 - Lightmapping Revisited (And My (Re)Introduction)