Patching QuadTree(picture)

If it's an arbitrary mesh, but is terrain-like (i.e. existing primarily in a plane, but with variations in height), you can use a quadtree, but with a general implementation.

Basically you just want to implement a standard multi-reference (i.e. tris can be referenced by more than one leaf) or 'loose' quadtree. Most of the references you will find on these subjects will refer to octrees, but the concepts will be the same - in fact, you could just sort your triangles into the tree by their x and y values (or x and z or whatever) and ignore the height component.

Ah I see what you mean, so as long as my tris are pretty lininer with their xz values I could just implement it without having to cut them up into square.

What I am worried about is the big triangels, tips of them might not be checked in the viewing cone and I might have to make the cone much bigger then needed, but at least this is good place to start. Thank you!

First generate your quadtree nodes - thats dead easy by just recursivly dividing the area into smaller nodes until you reach some kind of threashold.

Then you need to figure out which polys intersect each node and deal with them accordingly. If a poly is entirely within a leaf node then add it to the leaf. If it stradles an edge you can either split it into two (along the edge) or store multiple references.

Splitting means you don't end up having duplicate references, which would probably make rendering and collision checking easier. But obviously you could end up with much more than your original poly count. If you store multiple references you've got to be aware of that and remove any duplicate entries in your rendering etc. routines.

Which one is better probably depends on your app. I'm inclined to try the multiple references way first and see how that goes for you.

Quote:

Original post by MetaKnight What I am worried about is the big triangels, tips of them might not be checked in the viewing cone and I might have to make the cone much bigger then needed, but at least this is good place to start. Thank you!

If you make your quadtree correctly that won't be a problem. The big tris get referenced from all leafs that they intersect with, so if your view frustum intersects any of those leaves then the poly gets drawn.