Sign in to follow this  
george7378

3D Neighbour nodes on a cube

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

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Announcements

  • Forum Statistics

    • Total Topics
      628346
    • Total Posts
      2982201
  • Similar Content

    • By G-Dot
      Hello everybody! I've got a little problem. I need to create jetpack action. The main target is when I will press some button on my keybord my character will fly in the sky and stay here for some time then he will remove to the ground. I'm working with Unreal Engine 4 with blueprints.
    • By OpaqueEncounter
      I have a very simple vertex/pixel shader for rendering a bunch of instances with a very simple lighting model.
      When testing, I noticed that the instances were becoming dimmer as the world transform scaling was increasing. I determined that this was due to the fact that the the value of float3 normal = mul(input.Normal, WorldInverseTranspose); was shrinking with the increased scaling of the world transform, but the unit portion of it appeared to be correct. To address this, I had to add normal = normalize(normal);. 
      I do not, for the life of me, understand why. The WorldInverseTranspose contains all of the components of the world transform (SetValueTranspose(Matrix.Invert(world * modelTransforms[mesh.ParentBone.Index]))) and the calculation appears to be correct as is.
      Why is the value requiring normalization? under);
      );
      float4 CalculatePositionInWorldViewProjection(float4 position, matrix world, matrix view, matrix projection) { float4 worldPosition = mul(position, world); float4 viewPosition = mul(worldPosition, view); return mul(viewPosition, projection); } VertexShaderOutput VS(VertexShaderInput input) { VertexShaderOutput output; matrix instanceWorldTransform = mul(World, transpose(input.InstanceTransform)); output.Position = CalculatePositionInWorldViewProjection(input.Position, instanceWorldTransform, View, Projection); float3 normal = mul(input.Normal, WorldInverseTranspose); normal = normalize(normal); float lightIntensity = -dot(normal, DiffuseLightDirection); output.Color = float4(saturate(DiffuseColor * DiffuseIntensity).xyz * lightIntensity, 1.0f); output.TextureCoordinate = SpriteSheetBoundsToTextureCoordinate(input.TextureCoordinate, input.SpriteSheetBounds); return output; } float4 PS(VertexShaderOutput input) : SV_Target { return Texture.Sample(Sampler, input.TextureCoordinate) * input.Color; }  
    • By pristondev
      Hey, Im using directx allocate hierarchy from dx9 to use a skinned mesh system.
      one mesh will be only the skeleton with all animations others meshes will be armor, head etc, already skinned with skeleton above. No animation, idle position with skin, thats all I want to use the animation from skeleton to other meshes, so this way I can customize character with different head, armor etc. What I was thinking its copy bone matrices from skeleton mesh to others meshes, but Im a bit confused yet what way I can do this.
       
      Thanks.
    • By G-Dot
      This is some fotages of enemies for my first game project. I used 3ds Max to model them, substance painter for PBR texturing, Marmoset for rendering. Probably this is he first version of them but not the last.
    • By G-Dot
      This is some fotages of enemies for my first game project. I used 3ds Max to model them, substance painter for PBR texturing, Marmoset for rendering. Probably this is he first version of them but not the last.
  • Popular Now