The planetary terrain guy

Topics: User Forum
Dec 31, 2006 at 1:01 AM
I think that's going to end up being my unofficial nickname wherever I go regarding XNA.

So here's the deal: I'm a beginning 3D programmer obsessed with recreating his own version of Frontier. Full scale planets, accurately moving solar systems, and the seamless transition between space and surface are my obsessions.

I've read dozens of articles on terrain engines and they all come back to quadtrees. I understand the concept of what it is: a way of breaking up the world into standard-sized chunks to quickly calculate a player's position or determine how to distribute triangles for LOD calculations.

I've done all the tutorials on terrain I can find, but none of the concepts are making it through my incredibly dense skull (or they're not explaining it so well). Is there a better explanation for how to use quadtrees to generate and store terrain out there?

I am very desperate for a guide to this sort of thing that makes sense and helps me reach my goal (and, optimally, is designed to run in C# with the advantage of Microsoft's new XNA tools). Thank you in advance for your help (or, alternately, for not flaming this poor n00b).
Dec 31, 2006 at 4:17 AM
That's been my goal too. To fly in from outerspace, through the clouds and turbulence, to see the distant landscape and zoomd down on the unsuspecting enemy and take them out. All without a hitch, pause or glitch.

Quadtrees are not hard, but they are recursive, which means, getting your head around how they work is like your mouth telling your mouth to tell your mouth to say something :)

okay, i'll give it a go.....

quad means 4. thats where the name quadtrees comes from. (you know this).
divide the landscape (whatever size) into 4 pieces, that is, divide it in half so you have north/south peices then those in half for east/west peices, thats 4, NW NE SW SE.
Now, what divided it? It's a class called a QuadtreeNode. and what does it do with it? it gives it to 4 children that are what? QuadtreeNodes. Why? cause they are going to each divide their chunk into 4 more peices for their 4 QuadtreeNode children.
Each QuadtreeNode divides their chunk up until they say. Hey, I can handle this chucnk by myself (don't need children to do it). That last QuadtreeNode that refuses to give up it's chunk it what's call a leaf node (has no children) is the leaf on the branch at the tip.
Now, why would we do this?
When i need to find a spot on the map to look at, I say, I'm here and I'm looking over there. I pass that information in a view and projection matrix. That gets passed to the root of the quadtree. The one that owns the whole landscape. He says, are you in my space or are looking at my space? if so, pass it down to my 4 children and let them see if you are looking at them. Well, chances are you aren't looking all all 4 of them. So, when one of them says, no, your not looking at me, he then says, so you can't be looking at any of my children. That culls out that whole branch in one fail swoop. Not only the landscape, but anything (buildings, tanks, cars, roads, rocks, etc...) on that part of the landscape. No need to check further down the tree.
And also, if one of the children says, you can see all of me, then it knows that you can see all of his children, no need to even ask them.

Does this rambling help?

Dec 31, 2006 at 2:36 PM
Yes... yes, that is helpful. Okay, next step: how does the quadtree relate to the terrain? Do you store the triangles themselves in the quadtree, or do you just store information about the triangles there?
Dec 31, 2006 at 3:55 PM
Okay, at each of the leaf nodes I store the vertices and indices that are needed to render that section of the landscape. It also maintains the original heightmap information for other purposes (whatever that might be, cause you can figiure out a lot of things from it without having to read the vertex and index buffers).
Dec 31, 2006 at 6:09 PM
Alright, so the vertex and index information is stored at the leaf level. Makes sense (finally, something does!). Could you tell me a little more about the heightmap? Is that a set of verticies or indicies, or the grayscale map used to generate the terrain in most cases?
Dec 31, 2006 at 6:48 PM
Quadtree allows for 2 types of heightmaps. An 2d array of floats, or a Texture2D (yes a regular heightmap).
In the case of Texture2D, only one (of R,G,B) color component is used (ie, treats as greyscale in a 16million color image.
In the case of floats, it allows you to define how the heightmap info is generated. It also gives more control of the height.
When a texture is loaded, only 256 possible values can be used (0-255). So the height difference from low-land and high-land and the variation in between are somewhat limited. Using floats, the variations are limited only by values that can be stored in a float and the "tool" used to create that 2d array of floats.

Mar 9, 2007 at 3:37 PM
Hey how bout for inspiration you check out:

It's some pretty amazing stuff. He has a dev-diary of sorts. Maybe he can shed some light on some of the challenges?
Mar 12, 2007 at 6:44 AM
Check out the following page :

There is some cool demos with source code, and links to articles about procedural planets.
Mar 19, 2007 at 12:47 PM

saladinct wrote:
Check out the following page :

There is some cool demos with source code, and links to articles about procedural planets.

Fantastic stuff, is hard to find good examples of procedural generation of prett much anything, anything anyone does they usually keep tight to their chest!.
Good find

May 22, 2007 at 10:57 PM