Quadtree question

Started by
1 comment, last by James Trotter 18 years, 8 months ago
I have looked through about 111 pages in the Graphics programming and Theory forum and can't find a answer to my question. I'm making a terrain renderer. I understand how to create the quadtree, but I don't know how to determine which polys belong in each leaf node. I'm using tri-lists in directx for the terrain. If you need anymore details please ask. Thanks
Advertisement
Divide your terrain into patches and set AABB around each patch. Create a polygon list (better index buffer) for each patch. Then in runtime determine which patches are visible (using your quadtree and VFC test) and render all polygons within visible patches (or you can test these polygons against VFC for further polygon rejection).
Usually in terrain rendering there's a regular grid of vertices. This makes the process of dividing the faces into different nodes alot simpler, because you don't really have to split any of the faces.
If you're using heightmapped terrain, you can use a regular grid of 2^n+1 by 2^n+1 vertices. This way you can always split it down the middle, and divide it into four patches. These patches can again be split down the middle, until you get nicely sized patches, (I've seen the numbers 33x33 vertices and 65x65 vertices mentioned here on the forums). These patches are the leaf nodes, and get filled with the actual index data.
Each patch gets a bounding box, and you just descend the quadtree until you get to the leaf nodes. Then you render them.

Now, if you do it this way, obviously there are only four possible nodes into which each vertex can go. So a simple series of if-else statements should determine into which node the vertices fit.

This topic is closed to new replies.

Advertisement