Sign in to follow this  

Navigating a Quad Tree and LOD edge problem

This topic is 1541 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 everyone, this is my first post here, I am sorry if this is the wrong place.

 

I am attempting to create a spherical Terrain, like a planet, using quad Trees. I am not new to programming but don't have too much experience and I have run into 2 issues.

 

First I define a grid, all grids are 5 by 5 vertices. I then create a cube out of 6 grids. I then map the result to a sphere and this is the result.

[attachment=17998:quadSphere.jpg]

 

So far so good. Now, I replace each grid with a quad tree, of which the leaf node has a pointer to a grid. I subdivide once on only one grid and draw only this child node. This results in the following, viewed from inside the sphere.

[attachment=17999:subDivideImage.jpg]

 

This is still correct, however I now run into this problem, which I did expect, but I cannot find information on how this is solved.

[attachment=18000:edgeProblem.jpg]

The above picture shows how the edges don't line up when different levels of detail are next to each other.

 

My other problem is simply finding a good way to quickly access the leaf Nodes of the quad tree. I have not really worked with tree structures, only linked lists etc. I would appreciate any advice or links to resources on these issues. I would also like to encourage discussion on other ways of generating similar effects as I find the whole realm of procedural generation very interesting.

 

Thanks for reading.

 

 

 

 

Share this post


Link to post
Share on other sites

This is the algorithm I use to solve the same problem. It is focused on flat grids, but there's no reason not to use it for a sphere (that's how I'm using it). http://www.gamasutra.com/view/feature/1754/binary_triangle_trees_for_terrain_.php

 

Unfortunately it's not trivial to implement. There are probably better GPU based options these days if you're targeting modern hardware.

Share this post


Link to post
Share on other sites

I'm thinking about same problem. What if is  there an algorithm to determine two nodes common side? If you know common side(west, east, etc..)and you know node's LODs then make a stitching them. Oh, man, if i'd know this algorithm..., please help.

Share this post


Link to post
Share on other sites

Yep! Girls skirts)) Unusless framekeepers stuff. But I think I resolved neighboring. Two nodes are neighbors becouse they both have the same geographical oposite sides coordinates. Every quad of terrain has a geographical extent. And if forexample right side of node A equals left side of the node B then A kith B on the east! Its realy works!

Share this post


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