Jump to content
  • Advertisement
Sign in to follow this  
FrankBoltzmann

Quad-tree neighbours, best approach for specific case

This topic is 2304 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello guys, I'm a frequent viewer but not user of this forum, since I am into game development. I didn't know where to post this since it applies to both Games Programming, graphics or anything, so I've decided it was General Programming.

I have a quad tree structure and for leaf i want to check the level of its 4 neighbours, that should also be leaf nodes.

Basically, when splitting a node into 4 children, I need to know if the neighbours of each child are of a lower level (I consider the quadtree root as level 0 and thus a node's father would be of lower level than the node) or not, depending on which neighbours are of lower level, the node is created differently. Which would be the best way to do this efficiently? I know that two of the neighbours are trivial, if a node is split into 4 of equal levels, then the NE child is going to have the NW child as West neighbour and the SE child as South neighbour, which means that the S and W neighbours will either be of equal level or higher. But what about the N and E neighbours?

Context: I'm using a quad tree to create Level of Detail, in which each node is a grid mesh of NxN vertices and each node adapts a index topology so that there's continuity between patches of different levels of detail. (without T-junctions or cracks)

Thanks in advance!

Share this post


Link to post
Share on other sites
Advertisement
I can always assume that the father of a node already has information about it's neighbours and simply ask the father's neighbour about their correspondent child that is neighbour of the node. But I think this would have to be done as a breadth first search rather than depth first, which is how I currently split the nodes.

Also, when 4 leaf brothers merge, any neighbours of similar level should be updated.

Share this post


Link to post
Share on other sites
I wrote a thesis several years back on rendering and deforming very large terrain. If I'm understanding you correctly, I believe I ran into some of these same issues.

You may be interested on the section Neighboring Nodes in the thesis here

In my multi-resolution terrain rendering, I also constructed nodes in a quadtree. In order to avoid T-junctions, neighboring nodes had to be linked together, and neighboring nodes could be of any level of detail.

Quoted from the paper:
When linking nodes together, nodes must satisfy a strict rule: A node is only allowed to point to a neighbor that is of equal LOD or higher (coarser). i.e. nodes can only point to adjacent nodes on the same level of the quadtree or above.

The most common way to re fine a mesh is via depth- first traversal of the quadtree.

However, in this way, neighboring nodes won't be linked together correctly. Instead a breadth- first traversal must be done during re nement. Whenever children nodes are created, their parent is responsible for linking them to the rest of the quadtree.[/quote]

I think you are very close to finding a good solution. Let me know if you need any further clarification of my implementation.

Share this post


Link to post
Share on other sites
I ended up implementing something rather simple due to my case not being very limiting. Most quadtree neighbour searches require a node to know the level of the neighbour at the bottom of the tree, in my program, I just need to know the neighbours of similar or greater level, which means I just need to travel to the parent, ask for the parent's neighbour and if that neighbour has children, get the mirrored quadrant, otherwise set neighbour as parent's neighbour. I assume the parent already knows all its neighbours. I basically do a Breadth-first exploration but after spitting/expanding all nodes of a level of depth, I go through the nodes of that level (since each node doesn't need to know about nodes of a lower level) and I set their neighbours as I said.

So, basically, when setting neighbours, all nodes of the same level that need to exist exist, the ones that had to be merged were already merged and all of this in the same breadth-first exploration of the tree, without traversing it again for just this. Also, since all parents already had their neighbours set, we know that we can just use the parent's neighbour of same direction and ask for its child on the mirrored quadrant, in case it doesn't exist, we use the parent's neighbour. This way, when we're done, all nodes have neighbours of equal or higher level (higher being towards the root) and thus I can fix T-junctions by having the lower nodes (with more detail) adapt to the higher nodes (with less detail). I can even tell how many levels of different exist between them (although not more than 1 level of difference occurs due to parameters).

I'll check your thesis web383 as it may help me improve what I've done, hope you understood my explanation. Thanks for the help! Edited by FrankBoltzmann

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!