frustum culling large chunks of the game world

Started by
4 comments, last by Norman Barrows 10 years, 11 months ago

i'm interested in frustum culling large chunks of the game world.

in this case a "chunk" is 26400 x 26400 in size, and the frustum is just 300 units deep.

so a simple AABB frustum cull that checks BBox corners won't work, due to chunks that entirely span the frustum.

so i'm thinking calculate relative headings to chunk centers and corners, and compare them to the horiz FOV. perhaps combined with some range checks. i don't really need to clip to the upper or lower planes, i'm just trying to figure out which chunks are "not in front of" the camera, so i can skip drawing them entirely. so i don't really care about the y component.

in most cases, only the chunk the player is in will be visible. but adjacent chunks can be visible when the player is near the edge or corner of a chunk.

any other (possibly less ugly) approaches come to mind?

i know that i could convert the chunk into a quad of 2 triangles then edge clip them to the frustum, then check what's left of them to see if the chunk is in the frustum (as though i was drawing and clipping 2 tris myself), but that seems like overkill.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

Advertisement

culling large chunks is always alot more problematic than culling smaller chunks. It's one of those things where a balance must be struck between chunks that are too big and too many little chunks. My suggestion is to make medium sized chunks.

You can still check bbox corners: the critical thing is not that all corners are outside the frustum, it's that all corners are outside for the same plane.

In the case of a box that's larger than your frustum, consider that for each frustum plane some of the corners will be on one side of it (inside the frustum for that plane), some on the other (outside the frustum for that plane) - in other words the box intersects the frustum for that plane. The reject case is only for boxes that are outside the frustum; intersection or fully inside are accept cases, so frustum culling still works.

A picture may help make this clearer. Here the frustum is green, the object is red, I've flattened it to 2D for simplicity (although the principle is the same in 3D) and numbered each frustum plane (F1, etc) and box corner (C1, etc).

xb01t3.png

Starting with F1, we check the box corners and we see that C1 and C2 are on one side of the plane, whereas C3 and C4 are on the other side of it. Therefore the box intersects this frustum plane; it's partially inside and partially outside. Move on to F2 and we see similar - C2 and C3 on one side, C1 and C4 on the other, also intersects. Repeat for all planes and we find that the box intersects them all. Since the only reject case is for all box corners to be outside a plane, the box is accepted.

Direct3D has need of instancing, but we do not. We have plenty of glVertexAttrib calls.

You can still check bbox corners: the critical thing is not that all corners are outside the frustum, it's that all corners are outside for the same plane.

yes, this will work quite nicely.

the far plane is 300

a chunk is 26400

a sub chunk is 800

i only need to clip in x and z.

so i clip if all 4 corners are left of left, right of right, behind near, or beyond far. clever, brilliant, - elegant.

thanks! i appreciate that. could have taken me half a day to realize that.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

mhagain, as I discovered when looking at a large terrain from above, that method won't cull this edge case

VvxPxVh.png


My solution is to perform the same tests using the points from the frustum and the planes from the box; this roughly doubles the cost of a frustum-box query, so I use spheres as much as possible

EDIT: This is the gist of the separating axis theorem, right?

when looking at a large terrain from above, that method won't cull this edge case

you mean when the red object lies between near and far, but outside of side planes?

right now i'm using spheres for small objects, and the above mentioned method for large chunks.

i'm wondering if there isn't one cull that might do it all. but since we're talking spheres and BBoxes, i suppose not.

it would be nice if there was one cull algo that worked for both smaller than frustum and larger than frustum objects.

when implementing the chunks cull algo, cases such as you mentioned occurred to me. at that time i decided not to worry about it , but also came to the conclusion that the thing to do was to apply just the camera's y rotation, and not x rotation, IE keep it looking straight ahead, not up or down, then calculate the frustum planes and clip the chunk to those. granted, the case may be that the chunk still ought to be clipped by the upper or lower planes. i still have yet to play around with it seriously, so i haven't thought it through all the way yet.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

This topic is closed to new replies.

Advertisement