bounding boxes

Topics: Developer Forum
Apr 10, 2007 at 11:56 PM

nice component, i've been trying to get my head around using quadtrees in my terrain on a small project im working on so i have a question...

say my terrain is 1024 x 1024 and my "leaves" or squares of terrain are 64 x 64. that would make the bounding box for the one at 0,0 0,0 to 64,64 wouldn't it?

now since my culling isn't working correctly i think im missing something. in the TryCull methdod the view/proj matricies are passed in. Does this mean i have to transform the corners of my bounding box before i check if they're in front of each plane of the frustum (to cull the node)? I think thats what you might be doing in that method but i don't quite understand it.

Sorry if this isnt the right place for such questions but its my first post so be gentle )

Apr 15, 2007 at 11:28 PM
Convert your view/proj to a BoundingFrustum (xna object) and make a bound box (using the square area and the minimum height and maximum height). The BoundingFrustum will do the work for you (see BoundingFrustum in the help file). You can test for an intersection of the BoundingFrustum with the BoundingBox. Be sure you don't check children nodes if the parent node is completly inside or outside the BoundingFrustum, but DO check children if it is partially inside.
Apr 21, 2007 at 2:57 AM
Just a note on my previous post.
The BoundinBox I refer to is your nodes bounding box. Your Bounding areas for each node depends on the "Scale" that you set your areas to. If you contain 64x64 points in each node, then the x/z scale is 1.0 if you just use the index (width or height) of the heightmap as the x and z coordinate. I usually scale it to something that makes sense (so many feet or meters) per heightmap point. Then I also scale the height (y) to something relative to that.
Then the BoundingBox would be constructed from the coordinates for the start and end in x, y and z.
In the case that you are just using a scale of 1.0, then the first bounding box would be constructed like so (if it's okay to invert the x of the heightmap since XNA is righthand coordinate system):

this.boundingBox = new boundingBox(new Vector3(0,0,0), new Vector3(64,64,64));

where "this" refers to the first leaf node.
Obviously you won't hard code the vectors, but pass them in from the parent node. This gives you the idea.
Jun 21, 2007 at 12:43 PM
Thank Clyde thank makes perfect sense. I wasn't allowing for the scaling so things were going screwy.

One limitation im up against now is that i'll hit the maximum vertex index in the Draw IndexPrimitives call once my terrain gets to about 4096 x 4096...

now i could make mini vertex and index buffers for each 'leaf' of terrain but is that a sensible approach?

I'm not sure how this is usually done or if i want to be setting the index buffer and vertex buffer for every left i draw.

Jun 25, 2007 at 7:56 PM
Edited Jun 25, 2007 at 7:59 PM
The way I am doing it, is I have one index buffer, and seperate vertex buffers for each "sector" (leaf). The index buffer is the same since each leaf is the same size and order of vertices. Then you only need to set the index buffer and vertex declaration once.

You could also collect all the vertex information from the visible leafs and put them into one array before drawing them. But the less you touch things (moving them around) the better (within reason). Each draw call costs, lots of vertices in a single draw call is better than lots of draw calls (there is a balance somewhere).

(edit) another thing I do, is sort the leafs front to back, that way the depth buffer can throw some things out in the distance instead of drawing it and then redrawing it.