flipCode - Tech File - Kurt Miller [an error occurred while processing this directive]
Kurt Miller
Click the name for some bio info

E-Mail: kurt@flipcode.com

   03/15/2000, Miscellaneous Jargon

I tend to (or at least try to) keep my tech files pretty much focused on one topic at a time when I have time to update them, but I felt like saying a few things, so this update won't be much like the others. I got some interesting feedback on the special effects tech file I wrote a bit ago, but I still haven't managed to put any more time into the editor. In other news, here are a few things I've been up to.

New Level Editor & MFC

I started a new level editor for my engine a little while ago, and its coming along pretty well. I've only managed to put a few days work into it yet, but it allows one to view/manipulate meshes and select/apply textures. That's about all so far. The creation and selection functions aren't implemented yet, but that's just a matter of time. The editor uses MFC for its UI, which is something I don't normally use for my tools, but if it means saving time to do a nice splitter-window interface, I'm not going to complain. Here's a very early screenshot of the editor: crappy-editor-early.jpg. The new editor is far from complete, but despite the horror stories you may have heard from people about MFC, its really not bad. I set the UI up something like this (with splitters between the windows):
   Main Window
       |__ Left Frame  (CFrameWnd)
       |      |___  Tree View (not shown)
       |      |___  Control Panel (with dialog tabs)
       |__ Right Frame (CFrameWnd)
              |___  4 Views (CFormView)
This takes little effort in MFC. Each form view has a few controls for moving around the boundaries of the world, and an OpenGL window for rendering, which I switch between using wglMakeCurrent. Someone asked me once how to do 2D views of the 3D world. The easiest way that I've come across is just to ditch a dimension and use only the relevant "x" and "y" from any axis-aligned point of view. It works perfectly, so I imagine this is what most people do. For example for the "front" view, you only want to use the X and Y coordinates since Z is irrelevant. Just scale the X and Y appropriately for your grid/view and all will be well. The same goes for any other point of view (using only the 2 relevant coordinates).

Oh yeah, the map data shown in the screenshot was made by Luke Hodorowicz, using a different editor. Its really a pretty cool map if only you could see the whole thing in action. I just import the data and play around with it to test out the editor's features.

A Little On Octrees

I received several e-mails in the past few weeks from people asking me about octrees. I'm not an expert on the subject, but I have worked with them quite a bit in recent times. I'll explain a bit about how I use them so I can refer people here later on. If you have not read Jaap Suter's flipCode tutorial, an introduction to octrees, maybe you should give that a read first. Note that I'll just be covering the basics of octrees, nothing new.

Despite what you may have heard elsewhere, an octree is not by nature a 3d hidden surface removal tool, nor is it neccesarily "cooler" than a bsp tree or whatever else. People tend to get excited when they hear about a new algorithm using a "new" buzzword such as an octree. In actuality, octrees have been around for quite a while, though good documentation on the internet seems to be pretty scarce. That may be due to the fact that in and of themselves, they're very simple to work with. So what the devil is an octree? An octree is simply a data structure. Every "node" in the tree can have 8 child nodes. Try to visualize what we're talking about. Imagine a cube. Now imagine 8 other cubes, each one being half the width, half the length, and half the height of the original cube. Draw this on paper if you need to. Now stick those 8 cubes into the original cube, with 2 layers of 2x2 cubes. For example you can picture it as having 4 of the cubes in a 2x2 square configuration, sitting on top of an exact copy of itself. Here's a picture of what it should look like:

Notice how we now have 8 smaller cubes (child nodes), all perfectly fitting inside the original cube (parent node). This is of course why its called an octree. But wait, we're not done yet. Take each of the child nodes one by one, and do the exact same thing you just did with the original parent. Now each child node has 8 children (8 smaller cubes fitting in it). Now do it again. And again. And again. And again. Ad nauseum.

Now in reality, when you're using the octree, you probably won't always need to generate children for every node, but as long as you understand how the children are generated, when to stop and when to go is a matter of implementation details. Before reading on, be sure that you understand and can clearly visualize how the children are generated (each child potentially having 8 smaller children cubes), and why this is a hierarchical structure. That's the most important thing about octree "creation".

So what can this be used for? There are tons of uses, but since my work with octrees has generally been with 3D graphics, I'll talk only about a specific application of octrees (space partitioning). Just be aware however, that octrees can be used for all kinds of things completely unrelated to graphics.

Now suppose you're dealing with a set of polygons in 3-space and you want to chop up and organize these polygons in your world's space using an octree. Lets assume we're only talking about perfect cubes for all of our nodes. How do you build an octree for this scene? Here we go:
  • 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?
  • So how exactly do you code all this? Here's some psuedo-code to get your started. Its has several make-believe data structures and functions that it calls, but I wrote it just to show you one possible way to order and structure your build function.
    	octree_node :: build( poly_list *plist, point *min, point *max )
    	    if( stopping criteria )
    	        save plist into this node's polygon list;
    	    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] );
    The psuedo-code above, though a little strange, should help you grasp how you can code what was desribed above. Of course the details are there for you to fill in, but they shouldn't be very difficult. As for actually using the tree, that's also up to you. Just keep in mind that when you disregard a parent node, all of its children go with it. Say for example that you're rendering a 3d scene. Suppose you ignore all of the octree nodes that fall outside of the view frustum. Its quite possible that you'll cull off a large number of polygons because huge portions of your world might fall outside of the frustum. That's just one example. There are tons of things you can do. Take for example collision detection. The same thing applies. You can wipe out large numbers of polygons to check against.

    Though an octree does help you with various things, its not a cure-all in itself. If you're developing a visibility algorithm with an octree, you must keep in mind that the polygons in each of the leaves are not neccesarily sorted at all. The octree doesn't really help with that at all. You still have to do the occlusion culling on your own. Anyway, I hope my explanation of building the tree helped at all. It turned out a lot longer than I expected! I was considering cleaning this up, adding a bit, and making a tutorial of it, but I won't bother if this information doesn't really help anyone :]. Please let me know what you think.

    Miscellaneous Things

    up to the second nothings: computers are an addiction. college is strange. rain is neat. snow is nice. my phone is scary (as with most telephonic devices). sleep is bad. orange juice is good. daily vitamins are good. drugs are bad. mountain dew in careful doses is good. those damn credit card people constantly calling college students with their latest deals are bad. nvidia is good. win2k is good. winamp is good. sonique is good. therapy is neccesary :). grilled cheese are good. this is me venting in small, pointless, and annoying sentences. the rca lyra (portable mp3 player) is good. my memorex cd-writer and hauppauge tv card not working under win2k is a terrible thing. my lack of a wacom tablet is an annoying thing. the "original celebrated curiously strong wintergreen artificially flavored mints", altoids, are pretty good. bagels are confusing. muffins are disturbing. breakfast burritos are horrifying. this is pretty boring. eof.


    What, you thought there would be a conclusion? Hope you had fun reading this nonsense :). Later...

    Kurt Miller

  • 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)

  • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]