   frustum culling a tiled terrain
  Hey.I have a terrain consisting of at least 128x128 objects (not a heightmap because im going for something very specific)and at any givin time only about 12x12 of these tiles (objects) wil be in the view frustum (fully or partialy).I define a sphere with a radius of 7 units around the center of each object for use in the frustum cull test.This works wel and it greatly increases the performance of my application BUT doing 16384 (128x128) cull testseach frame is putting quite a strain on the CPU so even though my application runs faster in total itcan stil go alot faster (also this isnt very scalable, when I increase the size of the terrain to 256x256 it becomes extremely slow)so what im thinking of doing is th following.create 1 object as the center of the terrain.create 4 objects relitive to the center object and position them around the center objectfor each of the 4   objects created above create 4 objects and position them around the previous objects for each of the 16  objects created above create 4 objects and position them around the previous objects for each of the 64  objects created above create 4 objects and position them around the previous objects for each of the 256 objects created above create 4 objects and position them around the previous objects etc. etc. until i have all 16384 (128x128) tiles nicely in a object hierachy. The center object will have a bounding sphere thatencloses the the entire 128x128 terrain. Every level below that wil half the radius. Il also need to be able to reference the last levelof objects in a nice 128x128 array so i can easily reference them at an later stage.i hope my explanation makes sense...if anyone here has done something similar before? please give some advice (or a link) since im strugling to get my mind around it.Thnx!   
  Are your objects equally spaced (like in a regular grid)? Then I'd do the opposite, and take the frustum bounding box instead, to find what objects are intersecting. Taking the bounding box, you can find what object is intersecting your frustum bounding box in O(1) (like this).if your objects are arbitrary placed, then you need some form of spatial sorting (loose KD tree comes to mind).[Edited by - oliii on May 27, 2009 10:38:49 AM];  Is your world reasonably flat?I wrote a reply to a similar question a while back that might help you, it's the fifth reply in this thread:http://www.gamedev.net/community/forums/topic.asp?topic_id=531400;  As oliii suggested, if your objects are on a regular grid, you should use some type of spatial structure. Usually Quad Trees / Octrees are good choices for terrains.   ;  the terrain is perfectly flat (wel certian tiles is a bit longer but they all have a Y value of 0) and it forms a 128x128 grid of eqauly sized tiles (on X and Z)i already have frustum culling implemented in my engine so what im actualy strugling with is just building up the hierachy. but il check the links u gave me as soon as i get home a bit alter tnight thnx   ;  ok i understand your explanation(Erik). determine the 4 tiles that intersect with the corners of the view frustum and then only render the tiles that lie between them. good idea and i might use it but i want to try and make a more general solution that fits in with the way i already do frustum culling in my engine. ive googled up "Quad tree" (as berserk mentioned) and that seems like its exactly what i want.http://en.wikipedia.org/wiki/Quadtreenow my problem is building the quad tree. as ive explained in my OP i have 128x128 and from that i want to create a complete quadtree with the correct bounding box/sphere at each level so my engine frustum culling can eliminate large portions of the map with just one cull testi have frustum culling fully implemented in my engine' scene graph so now so its just a matter of building the quad tree. i almoust feel like hard coding all the nodes but that would be a bit insane considering the lowest level would have 16384 (128x128) nodes ;/Thnx!   ;  It sounds like you're doing something similar to a quadtree now (with the circles), although not strictly speaking so since the geometry of sub-circles probably extends outside the larger, parent circle and overlap sibling circles to some degree. Also, circles aren't particularly efficient containers for regular grids [grin]A Quad-Tree would be the typical algorithmic approach, but a simpler system of a grid -- say, breaking the world up into 8x8 grids, and doing the culling test using the corners of each of these would result in only 256 frustrum tests. Equally, perhaps more-so, practical is to simply "clip" your world to the viewport -- A similar problem in my software renderer is to choose a subsection of a larger image to be displayed -- most often this is to avoid drawing outside the clipping box. Its a simple matter of transforming the viewing box into world space, and then choosing the left edge to be MAX(World.Left, View.Left), top edge to be MAX(World.Top, View.Top), right edge to be MIN(World.Right, View.Right) and bottom edge to be MIN(World.Bottom, View.Bottom) -- This can be done very, very quickly.   ;  il replace my spheres with boxes but for now thats fine as it is, a little bit of overlapping isnt that bad at the moment changing it to boxes isnt that hard either but thats not what im concerned about at the moment.  sure making 8x8 subsections of the map and then testing the subsection before testing the individual tiles with the hope of disgarding the whole subsection is a good idea and if all else fails that is what im going to do but i would idealy like to have more than just 2 levels.idealy i want1 big cubesplit into 4 cubessplit into 16split into 64 cubessplit into 256 cubessplit into 1024 cubessplit into 4096 cubessplit into 16384 cubes each containing an tile modelso thats 8 levels in total for my ideal terrain whereas the nodes on the last level wil represent the actual objectswhat im strugling with is figuring out the logic il need to create this. My engine's node class is functional enough for my application to implement this.so i need to using some clever looping to create a total of (1+4+16+42+256+1024+4096+16384) node objects and give them all the correct parent, local transformation and bounding cube.additionaly i want pointers to the 16384 nodes on the lowest level to be loaded into a 128x128 array for easy access.il probely be able to get it right eventualy just wondering if anyone here have done something very similar to this? or il just stick to 2 levels of256 cubessplit into 16384 cubes each containing a tile model, like Ravyne suggested   ;  i got it working :Pi wrote some methods that starts at the top and works its way down the quad tree to create all the nodes with the correct relitive positions and culling information.Thnx for all the input   