How would I create Dynamic LOD with Quad Trees

Question

I would like to be able to create something like the following http://www.youtube.com/watch?v=LxZhWrSmrOY&feature=player_embedded how would I create something like it? I understand I will have to use quad trees and cube to sphere projection, but I don't even know how I will structure the program or even create the sphere.

1. I would like to know how I would structure the program (an interface of the members I would need particularly in the quad-tree class, and the class which holds the quad-treesm etc)
2. How do I make it so dynamic like that?
3. How would I create the quad tree structure and how would it work (and interact with other objects)?
4. Any other information/things you can provide me with :3
5. How to create the sphere, etc.

Eventually I would like to be able to create something like this: http://www.youtube.com/watch?v=rL8zDgTlXso but I guess creating this (the first thing mentioned) is a part of it?

Anything would be appreciated.

Edit:

I found the source code for the first project at https://github.com/unconed/NFSpace the only problem is, is that it is in C++ and Orge, and I don't really understand any of it, help please! :)

Answer 1

Here are a few links you may find useful; General Linking Page, Hugues Hoppe

These should provide you with a huge amount of information so hopefully you can find something in there to get you going.

Quad-trees and oct-trees are references to particular methods of spatially partitioning the world into smaller and easier to handle chunks. Because terrain tends to be just a skin, then it makes sense to break it up into quad trees (which are useful in 2D applications) but you could also use other trees, such as the oct-tree or a bsp.

Quad trees are fairly simple. Start with one huge square which encompasses everything and call it the root node. Then divide it into 4 equal sized pieces, and those 4 pieces into 4 more and those 4 into... Do this until either you think you've gone far enough or each square encompasses a maximum of n polygons/items.

Now what you have is a set of data grouped in a box, and it's easier to deal with that one box than all of those pieces of data. From here on it stays pretty simple. Check if a box is visible (see if it's within the view frustum). If it is, check to see if the 4 boxes it contains are visible and, for each one that is, check the 4 ... again a bit of recursion here. Ignore any box and all of it's child boxes if its not visible. Now you've dropped a whole bunch of data by quite simply culling data so you only have roughly what fits inside the view frustum (visible area).

Now, there's a detail I missed earlier. Once you've made the smallest boxes you want to have and put data in them, try averaging that data out and bubbling it up to the parent box. So, for example, a box at the bottom of the tree might have 2 polygons to make a square, find the point furthest from the parents center and bubble it up. repeat this for each child box. The parent will then get one point from each child box and 4 points gives you another quad, but one which should be the same area as the 4 more detailed quads in the child nodes. In other words you get one quad which covers the 4 in the child boxes. Again, repeat this and eventually what you'll have is a tree in which every layer contains more polygon data.

So now, when your checking if a box is visible, if it is, then check how far away it is. If it's quite far away, maybe you don't want to bother checking the child boxes of that node and just use the less detailed data it contains. So you don't go any further down that part of the tree.

Now you have culled loads of data and your also cutting down the detail for far away boxes. But there is one last issue which is quite difficult. When a box of low detail sits next to a box of higher detail, the polygons don't match. There are various ways to fix this, but you'll find that in the articles in the links posted at the top of this answer.