Sign in to follow this  

Limiting which parts of a terrain to draw

This topic is 2664 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Start by checking nodes at a course level. If the node is entirely within the view frustum, no further testing is required. If the node is partially within the frustum, you could further check the node's child nodes, but this really isn't necessary.

Using bounding spheres would be perfect for this and the test is almost free.

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Quote:
Original post by BenS1
Now I know that the normal approach here is to use a QuadTree to find which segments are in view, but...
If you've got a uniform 2D grid of cells, then using a 'flat' scheme like you propose instead of a hierachical culling scheme like a quad-tree is fine.
There's no memory overhead for the tree (it can all be parametric) and you can instantly derive the 'interesting' area without traversing a hierarchy.
Quote:
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... 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.
Take the 8 corners of the frustum and project them all onto the 2D grid. Take the 4 outer-most points that form a convex polygon (enclosing the other 4 points) and use them as your 'culling polygon'.

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.
Quote:
Original post by XeonXT
I think you're making a painful assumption here - that all grid pieces have to be loaded at once.
I don't think he's assuming that all 11 quintillion cells will be loaded at once...
The culling method from your picture would be another 'grid based' one though (not a 'hierarchy based' one) - in yours, you'd take the bouding sphere of the camera, determine the min/max x/z coordinates and determine your sub-set of cells as above. Seeing you're assuming the view-distance is "cellWidth*1.5" you can hard-code this search area to be minX=curX-2, maxX=curX+2, etc...

This actually demonstrates the usefulness of the flat grid over the hierarchy -- no matter how large the world is (with XeonXT's assumptions on cell-size/view-distance) you can instantly reduce your search to only 16 cells! With a tree you'd have to traverse a number of levels that is proportional to the size of the world.

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Quote:
Original post by BenS1
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

Ah, this is the problem with my mindset. I am capable of thinking only in terms of RPGs ;) and in RPGs, everything else in the world can be suspended or slowed while the player enjoys his local scenery. Unfortunately, as you pointed out, that's quite different for an RTS.

Best of luck.

Share this post


Link to post
Share on other sites
Quote:
Original post by XeonXT
Ah, this is the problem with my mindset. I am capable of thinking only in terms of RPGs ;) and in RPGs, everything else in the world can be suspended or slowed while the player enjoys his local scenery. Unfortunately, as you pointed out, that's quite different for an RTS.

Best of luck.


Thanks XeonXT

Share this post


Link to post
Share on other sites

This topic is 2664 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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