Jump to content

  • Log In with Google      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.

  • You cannot reply to this topic
4 replies to this topic

#1 foxcode   Members   -  Reputation: 242

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.

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.

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.

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.

 

 

 

 



Sponsor:

#2 C0lumbo   Crossbones+   -  Reputation: 2297

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.



#3 Turbochist   Members   -  Reputation: 136

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.



#4 Paradigm Shifter   Crossbones+   -  Reputation: 5380

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

#5 Turbochist   Members   -  Reputation: 136

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.



PARTNERS