Quad Tree Algorithm

Can someone explain how to implement a quad tree algorithm. It will be used for eliminating terrain. Also some links to some papers on it would be appreciated. I’d prefer a layman terms tutorial rather than a profesors. However send me as much info as you can . Last if anyone who know how to do it and wouldn’t mind stepping me through it please say so and i’ll email you. Thanks.

Frank

As far as I know, quad trees are 2d, so if your world is reasonably flat then go with quad trees, otherwise you should look into octrees.

Quadtrees basically create one quad covering the entire world, and then you divide this quad by 4 to get four quads, and divide each of these quads by 4 and so on. Coz its recursive.

You get the polygons in each quad, and index them. If the quad has too little polys in it or it is to small, then this quad doesn’t continue on.
You will have to decide on a minimum polygon limit and a minimum polygon count yourself so it suits the world.

When you draw the world, its simply one rule. If the parent quad isn’t in the view, don’t bother checking it’s children quads.

Check www.flipcode.com for an octree tutorial. It’s not a quadtree tutorial, but they both use the same principle.

Hope this helps