Hi again, another quadtree question - this time about neighbour finding in a set of 6 planar quadtrees forming a cube.

At the moment, I've got a single quadtree in the XZ plane so finding neighbouring nodes of the same level is easy - e.g. If a top-left node wants to know it's left-hand neighbour, all it has to do is get a reference to the top-right child of its parent's left-hand neighbour.

This still works for nodes contained on the same side of the cube, but it fails if I want to know a neighbour across the boundary between two different quadtrees in the cube. It doesn't work because the definition of up, left, down or right depends on which border you're querying across so asking for your left-hand neighbor using the above logic will only return the correct cell for some of the faces.

Can anyone think of a way to get this simple system to work for a cube, or will it have to be more complicated? I can't think of a way to make it work without having horrible edge cases resulting in a very inflexible system.

Perhaps I will just have to ignore neighbours across the boundaries and hence have small gaps in the terrain there.

Thanks for the help

What about  left-hand orientation for all faces. Then we only have to decide about the up-vector. Opposing faces haver counter up. 3 faces of one vertex have no common up. The rest can be modelled by a few "if".

1 hour ago, george7378 said:

At the moment, I've got a single quadtree in the XZ plane so finding neighbouring nodes of the same level is easy - e.g. If a top-left node wants to know it's left-hand neighbour, all it has to do is get a reference to the top-right child of its parent's left-hand neighbour.

But this shoud fail for the same reason. Assume you have a very small node near the center of the tree. To get the neighbour cross the center, the common parent is only the root, but not the parent of the initial small cell. So you need to add the complexity anyways to handle this.

Thanks again for the inputs  I decided to add properties to each root node which describe the rotations that need to be done in order to extract the correct neighbour node in each direction. These are passed around to any relevant child nodes which also touch the root border, and the end result is something that requires minimal 'if' statements and does most of the work itself provided you set the root nodes up properly.