Quad Trees

I have the basis for a quad tree class implemented. When it comes to rendering the scene, each leaf node is used and the boundary (CRect) is used to construct two triangles.

This is used to render a landscape and as such is quite varied in height. I would like to be able to render different sections of the tree in more detail, as in a LOD algorithm. The problem is that I get gaps appearing in the surface and this makes it look pretty crap ! If I render the whole surface at the same LOD it is perfect, although very SLOW!

Does anyone know of an easy way that I could patch up the gaps in the surface, or even better, avoid them in the first place!


Most of the terrain rendering papers out there will tell you how to avoid cracks and T-junctions. It greatly depends on which algorithm you want to use.

Personally, I did something a while back that rendered every node as a triangle fan, and closed up gaps by making sure that the LOD difference between two neighboring nodes was at most 1. You could then close the gaps by adding a vertex in the middle of the edge that was causing the crack. It’s hard to explain without pictures, but if you look up some of the continuous LOD papers (ROAM, Rottger, Lindstrom, whatever), I’m sure you’ll find a good explanation there.


Yea, what he said… If you have questions about the article, just ask: bryan.turner@pobox.com

Although my article uses a Binary Triangle Tree rather than a Quad Tree, you may gain some understanding from it. If you would like information specifically about Quad Tree rendering just send me a note.