Sign in to follow this  
Quinnie

Terrain View Frustrum Culling

Recommended Posts

Hey, I'm currently implementing view frustrum culling in my terrain engine. The terrain is splitted into patches and uses GeoMipMapping. The terrain engine supports gridsizes based on the formula 2n + 1. A QuadTree algorithm however only seems to work on grid of a 2^n size. Did I misunderstand how a QuadTree should be implemented or is this a common problem? If my question is unclear or vague I'll be happy to include some sketches. Kind regards, Quinnie

Share this post


Link to post
Share on other sites
Quote:
Original post by Quinnie
The terrain is splitted into patches and uses GeoMipMapping. The terrain engine supports gridsizes based on the formula 2n + 1. A QuadTree algorithm however only seems to work on grid of a 2^n size. Did I misunderstand how a QuadTree should be implemented or is this a common problem?
The 2n + 1 formula is used for grid size (in vertices) for that very reason in that it results in 2n terrain cells (ie, the quad contained within the vertices).

ASCII Diagram Time! [smile]

The following is 5x5 (2n+1) vertices, but it results in 4x4 (2n) cells
 _ _ _ _
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
So when splitting that into a quadtree, you'd split it as follows, with each node being 3x3 (2n+1) vertices and 2x2 (2n) cells:
 _ _   _ _
|_|_| |_|_|
|_|_| |_|_|
_ _ _ _
|_|_| |_|_|
|_|_| |_|_|
Naturally it wouldn't be very good for performance if you were using a quadtree on a 5x5 grid and you would never split nodes right down to something as small as 2x2 cells, but this is just because I can't be bothered making bigger ASCII diagrams [wink]

You can then frustum cull (and maybe also use an occlusion culling technique) to get rid of the nodes you can't see [smile]

Regards,
ViLiO

Share this post


Link to post
Share on other sites
I'm sorry but I guess I was a bit unclear about the problem.

The terrain patch size in vertices is indeed 2n + 1 but the world size in patches is also 2n + 1.

I am not culling specific parts of a terrain patch but the entire terrain patch. The sketch below shows a possible situation. Each square represents a terrain patch. Because the size is 2n + 1 it can not be split into 4 pieces equally.


In your ascii example you used a 4x4 grid, this grid can be splitted correctly because 2 ^ 2 equals 4 not because 2 * 2 equals 4. Not every 2 * n grid can be recursively splitted correctly into 4 pieces, however every 2 ^ n grid can.

The entire terrain size will be adjustable from around 7x7 upto 21x21 patches. Would it be possible to simply brute force the frustrum culling and checking every patch seperatly without the use of a QuadTree?

Share this post


Link to post
Share on other sites
Quote:
Original post by Quinnie
In your ascii example you used a 4x4 grid, this grid can be splitted correctly because 2 ^ 2 equals 4 not because 2 * 2 equals 4. Not every 2 * n grid can be recursively splitted correctly into 4 pieces, however every 2 ^ n grid can.
My apologies, I had actually meant 2n + 1 and 2n and should have used superscript in my previous reply [smile]

As for your problem of your terrain gridsize not actually being 2n + 1, you are correct in saying that it will not lend itself to a regular quadtree but you could get creative and still try to bring some form of spatial hierarchy to your terrain patches by concocting some form of irregular tree that allows you to quickly dismiss chunks of patches quickly instead of testing each one in turn. Is there any reason why you cannot just use the normal 2n + 1 gridsizes?

One final thing that may be worth looking into is some form of PVS. Pre-computing visibility offline has its advantages and disadvantages, so you'll have to decide for yourself if it is a viable option. I can point you at a paper by James Stewart and an implementation of that paper called lScape which comes with source. Depending on your target hardware you could also look into other real-time occlusion techniques like some in the paper I linked to in my previous post.

All the best,
ViLiO

Share this post


Link to post
Share on other sites
The reason I don't like the 2^n + 1 gridsizes is that there are only very few sizes that apply. Everything smaller then 7x7 is to small and everything higher then 17x17 is too large.

Thanks a lot for the advice and the link to that paper. I'll look into that tomorrow.

One question remains, if I render terrain patches that are not visible will they be processed by a vertex shader/pixel shader? I assume they must be processed by a vertex shader but not by a pixel shader, is this correct?

Kind regards,

Quinnie

Share this post


Link to post
Share on other sites

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