Sign in to follow this  
Matthew123

Quadtree question

Recommended Posts

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

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this