I have a 6-sided cube. Each side of the cube is made of N individually colored quads (as you can see from the image below). Each one of these individually colored quads has the ability to perform a quadtree (recursively sub-divide itself into 4 smaller parts). In addition, every quad has a location attribute that can tell you its local and global {x,y,z} position. Also, all the quads are stored in a 1D array.

Now let's say for example I select a random quad, and that quad splits into 4 children:

Q1 → (Q1)(1), (Q1)(2), (Q1)(3), (Q1)(4)

And then I select (Q1)(1) child to split into 4.

(Q1)(1) → ((Q1)(1))(1), ((Q1)(1))(2), ((Q1)(1))(3), ((Q1)(1))(4),

And now I would like to find all ((Q1)(1))(2) neighboring quads

In general, I'm asking How do I perform neighbor finding on this data structure so that I can find any neighboring quad of a child or parent quad?

myers.m007@gmail.com said:
In general, I'm asking How do I perform neighbor finding on this data structure so that I can find any neighboring quad of a child or parent quad?

If your neighbor search is only about finding the 4 neighbors of a quad adjacent to its edges, the extra complexity is low. Beside u,v coords to address a quad, you only need a third coordinate to pick one of 6 regular grids representing your top level hierarchies. The algorithm so has a special case to deal with the boundary of those 6 grids, and you need to define some convention to orient and relate those grids to each other.
There is no single elegant convention to handle all cases. You can not prevent the issue of some boundaries mapping u to u, but others mapping u to v. So you need some ‘ugly’ switch statements to define a proper neighborhood relationship at boundaries.

If you want to process the whole 1-ring of adjacent quads, so a 3x3 region with the current at the center and 8 neighbors, things become more complicated, because quads adjacent to one of the 8 singular vertices only have 7 neighbors, not 8.
So in this case you have a second special case at those singular vertices, beside the special case at boundary edges.
If you also need some form of weighting, that's not a trivial problem. You could look at cube map filtering algorithms for an example, which would become even more complicated for a smoother cubic or gaussian filter.

Just confirming the obvious, but maybe it helps. Quadtree traversal code won't be affected, but calculating neighbor coords involves special cases.

The simple and straightforward approach is to walk up and down the tree. Given a quad Q, its potential neighbors are:

• Its siblings.
• The siblings of its ancestors, so long as Q touches one of the sides of that ancestor.
• The children of its actual neighbors.

Pseudo-code:

potential_neighbors = []
ancestor = Q.parent
while ancestor != None and shares_edge(Q, ancestor):
  potential_neighors.append(ancestor.children)
actual_neighbors = []
while not empty(potential_neighbors):
  neighbor = potential_neighbors.pop_back()
  if shares_edge(Q, neighbor):
    actual_neighbors.append(neighbor)
    potential_neighbors.append(neighbor.children)

a light breeze said:
The simple and straightforward approach is to walk up and down the tree.

I would say the ‘simple’ approach is to calculate neighbor coordinates and traverse from the root for each neighbor (which i assumed the OP already has).

I have implemented such method as you propose only once for some octree. Pretty complex. But sadly i did not compare performance against the trivial top down alternative.

I guess the top down method is faster in most cases. The up / down approach is more complex, requires more state, and near splitting planes it goes a whole way up, only to go down afterwards.
The problem is worst on the clipping planes of the root, but it also affects all other splitting planes. Thus i assume it's no win even for deep trees, and being lazy is fine.
But let me know if you know more. It's quite an interesting question.

What i sometimes use for optimization is a scrolling window of a traversal cache. If content is processed in some spatial order, most traversals can be read from the cache and avoided.

JoeJ said:

I would say the ‘simple’ approach is to calculate neighbor coordinates and traverse from the root for each neighbor (which i assumed the OP already has).

Sorry, I don't understand how that approach would work. How can you traverse from the root for each neighbor, if you don't even know how many neighbors there are until after traversing? Or do simply stop traversing when you reach the same depth as the initial quad, ignoring that two of that quad's children are neighbors and two are not?

+--------------+
|              |
| initial quad |
|              |
+------+-------|
|   A  |   B   | <-- neighbors
+------+-------|
|   C  |   D   | <-- not neighbors
+------+-------+

@a light breeze I was wondering the same thing. I did come across this solution where the author used a bit-mask. but I don't understand that algorithm.

a light breeze said:
Or do simply stop traversing when you reach the same depth as the initial quad, ignoring that two of that quad's children are neighbors and two are not?

Yes, you only traverse to the same level of the current quad. There should be never a reason to go deeper, because the neighboring deeper quads will instead find the current quad on their side, which has a higher level from their perspective.
But this applies to both options, no matter if we go up down from the current, or if we go top down for all potential 8 neighbor coordinates.

Now i think the best option would be a compromise. We can always find 3 neighbors quickly by looking just at the parent, which has low complexity, does not need a stack (e.g. recursion), and is faster than traversing from the root.
Then we only search for the parents of the remaining neighbors and do the same with them, which reduces the max number of required traversals to just 2. And we may find both neighbors already from just one parent.
By looking at the Morton code of neighbor coordinates, we also know in advance if they have a common parent, or a common ancestor at which level. May be helpful.

myers.m007@gmail.com said:
I did come across this solution where the author used a bit-mask. but I don't understand that algorithm.

Hmm, i see some flaws in the code examples: He uses if else else sequences a lot, where some bitmath or a compressed LUT in a single 32bit constant would avoid all the branches (but eventually makes the code even harder to understand).
And i assume he confuses Morton code with a hash. Big difference. Only the former contains spatial information in its bits, the latter is just a pseudo random value.

I really liked this paper, introducing quadtrees with efficiency in mind: https://www.merl.com/publications/docs/TR2002-41.pdf​

… i see it also covers neighbor search.

But that's just about quadtrees, not about dynamic LOD terrain.

There was some recent work on this using binary trees. Maybe worth a look, should be easy to find by googling this:

Experimenting with Concurrent Binary Trees for Large Scale Terrain Rendering
Thomas Deliot (Unity Technologies)
Jonathan Dupuy (Unity Technologies)
Kees Rijnen (Unity Technologies)
Xiaoling Yao (Unity Technologies)