Quadtrees

I''m not sure what you mean by block based simplification, but let me explain my understanding of the algorithm here...

First of all, there are two variations... One where the tree is built in advance for the entire map, which uses gobs of ram but is fastest, and the second, which builds a subset of the tree based on your current viewport each frame.

I''ll talk about the second, but they are almost the same case.

Step 1. Start building the tree. Quadratically recurse your map by subdivision, isolating all the polygons you are interested in.

Step 2. Decide where to add detail. Depending on the distance from the viewer, or a corner-point-height-variation test, the detail level for a given sub-section is determined. The corner test I metionned simply puts a 3d box (virtual) around the quadrant in question and tests the maximum height. If the height is large, then more detail is added there, regardless of whether we are considering this area "far away". This way, imporant detail is not left out in the distance.

Step 3. Refine your tree. If more detail is desired in one quadrant, add a point to the side you want (the middle point is always there). If this were the right hand side, you would add two leaves to your tree for the topright and bottomright new quadrants. You would have to add two more to the right hand neighbor as well (to the parent neighbor) because there would be a crack in the mesh.

Step 4. Recurse your tree and render it.

Let me know where in these steps you get lost and I''ll try to go into more detail.

I hope I didn''t confuse you more!

Cheers malachii that is really useful. I didn''t understand step 2 before, but I think I do now. One question though: Do you have check each point in your virtual box to see if it is the heighest?



---

Fleejay