•      Sign In
• Create Account

## Navigating a Quad Tree and LOD edge problem

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

4 replies to this topic

### #1foxcode  Members

299
Like
0Likes
Like

Posted 21 September 2013 - 08:03 AM

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.

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.

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.

### #2C0lumbo  Members

4073
Like
2Likes
Like

Posted 21 September 2013 - 10:30 AM

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.

### #3Turbochist  Members

236
Like
0Likes
Like

Posted 28 October 2013 - 06:08 AM

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.

### #4Paradigm Shifter  Members

5832
Like
0Likes
Like

Posted 28 October 2013 - 06:18 AM

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

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #5Turbochist  Members

236
Like
0Likes
Like

Posted 29 October 2013 - 09:46 AM

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!

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.