My game has a terrain engine, which has a very large terrain broken down into much smaller segments.

Obviously I don't want to attempt to draw the entire terrain every frame, I only want to draw the segments that are in view.

Now I know that the normal approach here is to use a QuadTree to find which segments are in view, but I'm not a massive fan for this approach for reasons I wont go into here.

To me the obvious appraoch would be to project rays from the 4 edges of the top, left, bottom, right planes of the camera frustrum onto the base terrain. This would then give you the 4 segments on the terrain the represent the segments in the 4 corners of the screen... and then you could use a simple bressingham alogrithm to select and draw the other segments within these 4 points.

So my questions are:
1. Is this approach a well known and/or commonly used alternative to quad trees?
2. Does this approach have a name? Maybe something catchy like "Camera Frustrum Projection"?

Now for the important question...

3. how do you handle the case that the camera is at an angle such that some points do not project onto the landscape at all? For example, if the camera is horizonal then the top of the camera will be looking at the sky, not terrain segments.

It'd probably be quite easy to identify this scenario, however how do you solve it? i.e. even if we know we are in this scenario, we still need to know which segments on the horrizon are in view.

I guess maybe we need to create rays using the Left and Right planes of the frustrum but using the height of the horison instead of the Top plane?

I hope that makes sense?

Thanks
Ben

Seems like a lot of work when all you need to do is test the intersection of each segments bounding box with the camera frustum. If you don't have many segments and the world isn't huge, you can probably get away without the quad tree.

Quad trees are amazingly simple for the performance increase they provide. I've never heard of anyone using Bresenham do to what you are suggesting.

Thanks for the reply

The difference is that the quadtree approach requires more tests as the number of world segments gets larger (Although only at a rate of 2^n), whereas the frustrum projection idea would be constant time regardless of how many segments there are.

Thanks
Ben

Quote:Original post by BenS1
The difference is that the quadtree approach requires more tests as the number of world segments gets larger (Although only at a rate of 2^n), whereas the frustrum projection idea would be constant time regardless of how many segments there are.

Whilst that may be the case, it doesn't really seem like a very meaningful comparison imo. If you do (for some reason) implement this, it would be interesting to see how well it actually performs in comparison to a quadtree or octtree based approach.

Quote:Original post by 1863

Quote:Original post by BenS1
The difference is that the quadtree approach requires more tests as the number of world segments gets larger (Although only at a rate of 2^n), whereas the frustrum projection idea would be constant time regardless of how many segments there are.

Whilst that may be the case, it doesn't really seem like a very meaningful comparison imo. If you do (for some reason) implement this, it would be interesting to see how well it actually performs in comparison to a quadtree or octtree based approach.

Ok, to put it another way. My game world is massive.... instead of having lots of small levels my games is based in a single giant world (Think MMORTS).

When I say massiv , I really mean it. Technically the engine is designed to a world up to 2^30 by 2^30, i.e. 1bn by 1bn! Each segment is 512x512, so that means there could be 2097152 x 2097152 segments, which would mean the quad tree would have to be 21 levels deep! So any quad tree test could require up to 21 tests to drill down to the individual segment level.

In reality such a large world is not possible due to the shear amount of storage required, but I will be creating a world in the region of 1-2Tb in size!

I'll try using a quadtree, and if that gives me any performance issues then I'll investigate projecting the viewing frustrum ontot he ground plane further.

Thanks
Ben

I think you're making a painful assumption here - that all grid pieces have to be loaded at once. That's certainly not the case and not an efficient way to do it.

Consider this approach (yes, I know it's overboard. I like PowerPoint, what can I say?)



Get it?

Only draw a portion of the total grid cells, but move them (and load new terrain data) dynamically based on the player's movement. Move cells when they're outside of the player's radius of vision and when he's getting closer to an area where cells haven't been loaded yet. Easy, cheap, effective. Very little culling required with this method.

But if you really want to step up, I suggest reading about geometry clipmaps. I'm very much a believer in them. Here are some links if you're feeling up to it:
http://research.microsoft.com/en-us/um/people/hoppe/geomclipmap.pdf
http://research.microsoft.com/en-us/um/people/hoppe/gpugcm.pdf

However, the aforementioned method of shuffling grid pieces will work just fine for normal uses.

Thanks XeonXT, and thanks for going to the effort of drawing the diagrams for me. However it was always my intention to only hold a subset of the tiles on memory at any one time.

In my case it probably wont be quite as simple as the system you've shown as in my game I have lots of units (Think Supreme Commander or Age of Empires) that can be anywhere in the game world and so I need to be able to switch between viewing different units very quickly without having a pause to load the data off the hard drive.

The achieve this I'll just use a resource manager that will prioritise the tiles held in memory. Those within the view radius of any unit will get the highest priority. Then the tiles just outside the view radius will get a medium priority. And those out a little further again will get low priority. As we move around the tile priorities will change and if we start to become short on memory then we can unload the lowest priority tiles first,

Also note that even if I didn't need the vertex buffers for the tiles containing units elsewhere in the world, I'd still need the heightmap info for those tiles as the units will still be moving even though they are not seen, so the physics and AI engines need access to the terrain data.

Thanks
Ben

Quote:
A simpler method would be to simply take the 8 points and get the minimum and maximum x/z coordinates. Then iterate through all the cells in this region (for x in range(minX,maxX) : for z in range(minZ,maxZ) : getTile(x,z)) and test their bounding cube against the 3D frustum.

Ah yes, of course. Seems so simple now. :)

Thanks for your help

Ben