flipcode - Octree Neighbor Nodes

Octree Neighbor Nodes
Question submitted by (17 June 2002)


	I'm currently making an Octree system for my video game . I've been confronted to the Neighbouring problem : How could I define easily the Neighbors of a Node ... I searched for 1 week and I'm so tired of this problem so I wondered if you could help me a little :) Each Node has a Parent(except the Root) and 8 children(except the last Node). Each node has too an ID : 0 is the Bottom Front Left Node, 1 the Bottom Front Right, 2 the Bottom Back Right Node, 3 the Bottom Back Left node. The 4 next are just alike the previous one ... But at the Top of the Parent Node ... The Bounding Boxes of the Node is Defined by 2 vectors : Min and Max I've read in Game Programming Gems that there are some algorithms to find out which Node is next to an other Node ... But I can't find such Algorithm ... so if you can help me ... That would be great !!! Editor's Note: This question wasn't originally submitted as an 'Ask MidNight' question, but is being posted here with the author's permission.


	I've never seen one of these algorithms myself, but I have solved the problem for myself... You can either do this on the fly, or you can pre-calculate the information (very quickly) and store it in your octree nodes. It depends on your needs. If you place two boxes side by side, so that the left side of one box is touching the right side of another box, then those boxes are neighbors. Octrees may have multiple neighbors on each side (or none, for nodes that define the exterior of the bounding volume.) So, let's consider a simple example, which can be easily extended to an octree. Take two boxes, and place one in front of the other. Place them so they are neighbors. Offset them a little bit to simulate a real-world situation. Looking at these boxes from the front, they should overlap in your view. Draw this on paper. When you draw it on paper, you turn it into a 2D problem (removing Z) -- that's fine for now. You can easily detect if these two boxes overlap in 2D. If they do, then you've solved half of the problem. Next, we'll extend the problem back into 3D and check the minimum Z of one box with the maximum Z of the other box. If they are equal (or within a tolerance), you're guaranteed that these two boxes are neighbors. So, you create code that performs a 2D box overlap (using only two coordintes from the 3D coordinates). You'll do this six times: twice for the XY coordinates (comparing for tolerance on min/max Z), twice for the YZ coordinates (comparing min/max X) and twice for the XZ coordinates (comparing min/max Y). You do this twice for each set of coordinates, because you'll use the XY coordinates to test for neighbors with both, the front and back faces of the current node. Also, when testing with the front node (i.e. the node that faces negative Z in the left-handed coordinate system), you'll compare the node's minimum Z with the potential-neighbor's maximum Z. Reverse this to test the back face. Repeat for top/bottom and left/right node tests. This isn't as bad as it sounds, because you can use the hierarchy to help you. A simple way to do this, would be to take the existing node (the one you're trying to find neighbors for) and enlarge it slightly. Traverse the tree and find all nodes that intersect this bounding box. Then you can limit your tests to only those intersecting nodes. This "enlarged node" may sound a bit like a hack, but it's really not, and here's why: When you build your octree, it's a good idea to limit your node sizes to a minimum size (otherwise, you might find yourself building an infinite tree, based on your criteria.) This means that you'll never have a node smaller than this size. Simply enlarge your node by half this size, and you're guaranteed to only intersect those nodes that are potential neighbors. The execption to this, is the neighbors that might share a single vertex with the test node. Response provided by Paul Nettle

This article was originally an entry in flipCode's Ask Midnight, a Question and Answer column with Paul Nettle that's no longer active.