View Full Version : how to implement a quad tree in terrain?

01-21-2003, 10:32 PM
I'm orienting myself on heightmaps at the moment and I've been looking in LOD techniques. I have been told that splitting up the map in a quad tree is a good way of increasing performance, but I've been wondering of how to do this.

So fast I can think of two possible ways:

1) Determining each leaf by the index of the array. Then using this index to draw the terrain. The originally loaded array is preserved and used.

2) Split up the terrain in leafs, and put all vertices of each leaf in a seperate array on load. Then render each array accordingly.

Also, what are you opinions of triangle splitting? Do you split up the leaves exactly upon each whole index (IE, split up on index 4, 8, 12, etc) or do you split up the triangles (ie: split the array on places 1.5, 3, 4.5, etc)?

Thank you!

01-21-2003, 10:51 PM

I use the way 2, mainly because whis way you get better quality with lower levels of detail. This is because in option 1 your lower LOD nodes only contain information from a subset of the original vertice, but in option 2 you can sample all the vertice and create a simplified version that more closely matches the original.

But that is not to say it's the absolutely better option. It uses a little bit more memory (about 33% I think, if you only store the heights), but on the other hand you can get better data locality this way.

I didn't really get your other question, maybe you could clarify a little?


01-21-2003, 11:19 PM
My second question has to do with loading the leafs and at what positions you split up the array.

For example, each entry of you array is 3 openGL units apart from eachother. So, entry [0][0] is at position 0,0 and entry [0][1] is at OpenGL position 0,3...
Then you make you quad tree, and you decide for some odd reason that each leaf in the quad tree has to be 4 by 4 OpenGL units.
This will cause that you have to split up polygons and recalculate vertices on where the quadtree is split.

What do you do? Do you take the hassle, and split the polygons when loading the map, or do you resize the quadtree to fit the size you have set for your terrain array?

Personally I'd resize the quadtree to fit the array. So I'd determine that the size of each leaf should be 3 by 3, instead of 4 by 4.
But I was wondering what you would do? Do you take the hassle?

I hope I was clear. This is perhaps a bit of an unlogical question but I simply like to know how far people go in making a quadtree.

01-21-2003, 11:37 PM
I have, for my each quadtree node, a fixed amount of triangles/vertice. The opengl units have nothing to do it. This way lower LOD leafs are bigger than the higher ones, and that's a good thing from many perspectives. Actually I can't imagine a quadtree without this being the case.

How many triangles that is depends on how rapidly I want the level of detail to drop. Heavier LOD requires smaller nodes to avoid holes, since in my implementation I require that for two adjacent nodes the LOD can only differ one level.


01-22-2003, 03:25 AM
I'm using an octree. octrees are better than quadtrees, if your landscape has high points... imagine you are standing on the top of a very high mountain... the quadtree will possibly cause the whole mountain to be drawn, an octree would only cause a bit of the polys under you to be drawn. needs a bit more memory, but is, in the end, a bit faster.

this won't help you implementing a quadtree, but i just wanted to say something