# Navigating a Quad Tree and LOD edge problem

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

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

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.

##### 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 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 on other sites

You need to make thin triangles along the edges of the LOD changeover to overcome the problem. It's a bit of a pain.

##### 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!

• 21
• 13
• 9
• 17
• 13