# Quadtree terrain splitting - I don't get it

Most of the papers i've read base their terrain in some form or another on a quadtree. See this at page 38:

Doesn't the first point contradict the bottom two? How can you have a fixed 33x33 vertex grid per leaf yet talk about adaptive division in a quad tree? The terminology is confusing and i'd appreciate any clarity on this!

Here are my assumptions:
Re-placing the patches everytime the quadtree changes would be a hit wouldn't it?

1. Quadtree starting at terrain bounds.
2. Iterate down to observer location.
3. Constrained version (no more than 1 level difference between neighbours)
4. Frustum cull.
5. Place terrain patch in each resulting leaf, where the scale differs but the resolution is always 33x33.
-

No, not really. If you are thinking of using a quadtree for terrain level-of-detail, the nodes you store will all usually possess the same data structure.

In your example, that structure is a 33×33 submesh that the nodes will hold. Depending on the level of the node, that 33×33 mesh will adapt (adaptive) to cover a wider area. The larger node will fill a larger space, but its submesh is still a 33×33 vertex patch.

After the tree is built you can do your frustum culling by going down the tree and discarding the nodes that don't intersect.

One thing to keep in mind, is that you will very likely need to address the cracks that come up when a larger node draws next to a smaller node. One easy way is to simply adjust (collapse) any unshared vertices between the meshes.

As for you other question about the tree being replaced, yes. Unless you want to get into data managing the tree, I suggest just making a stack and flush it out when the view moves sufficiently.

-
The issue with the visible seams at different sized tiles is explained on slide 39-40 of the presentation. Apparently they remove the T-junctions by using one of 9 possible meshes at the junctions (see slide 40). – bummzack Aug 9 '11 at 6:55
disclaimer: IDNRTFA ;-) – bitcruncher Aug 9 '11 at 21:30

The "unit" of terrain are 33x33 blocks. If you are close, that is what you will see. If you are further away, these blocks are fused into lower LOD chunks.

The reason they use fixed chunks at the lowest level (leaf), is because modern hardware is a lot faster with static geometry. Systems like ROAM, where a lot of work is performed to reduce eventual polygon count, incur into sizable performance penalties.

-
So the end leaf isn't each possible end leaf (at the smallest grid size), it's the end-leaf for that iteration, based on the distance, so some may be 16x16 and distant ones may be 256x256 (or whatever)? Doesn't that mean that everytime the quadtree changes, the patches have to be placed and scaled again? – George R Aug 8 '11 at 9:18