Jump to content
  • Advertisement
Sign in to follow this  
george7378

3D Neighbour nodes on a cube

This topic is 416 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

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

Share this post


Link to post
Share on other sites
Advertisement

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".

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!