Sign in to follow this  
bwhiting

object culling

Recommended Posts

bwhiting    1562
hello!!!

just thought I would pose a question on object culling in 3d scenes.

what I am after is a fast way to cull individual objects without using a partitioning system or hierarchy.

the reason being I am still learning this stuff and so I would like to work from basic solutions to the more complex ones.


At the moment I am using a combination of projecting the centroid of an object all the way into screen space and checking its z value against its radius (if its behind camera then cull)

The next check is to project the bounding box vertices in the same fashion and if any of the points are inside the viewport rectangle then do not cull.

I have got bounding spheres calculated but can't think how to use them to do this more efficiently, am sure there must be better ways to cull an individual object.


If you could offer any advice, reading materials, links, ideas... on how to do it better. I'm all ears!

Share this post


Link to post
Share on other sites
alvaro    21247
I think it's easier to compute the view frustum in world coordinates and then determine if the bounding volume intersects it or not, without ever projecting to screen coordinates. Since it's OK to be conservative and occasionally not cull something that could have been culled, I would only cull objects that can be proven out of the frustum by checking against a single plane of the frustum. This check is really fast for spheres.

Share this post


Link to post
Share on other sites
bwhiting    1562
thanks for the response, will give the bounding sphere vs frustum check a whirl see how I get on. Should the 6 frustum checks be faster still than the projetion? Dont know the math off the top of my head but seems like it might be more compelex.. well I'll try it and find out!

Share this post


Link to post
Share on other sites
dpadam450    2357
Well with the projection method you have to transform the center of the object which is matrix*vector = 4 dot products, but that is simply to see if it is behind the camera. To do proper culling against what you see in view you have 1 dot product for each (left, right, up, bottom, behind, very far away). That is 6 dot products.

I currently use a bounding sphere and hold onto the last side it failed from, so if it was on the left of the screen last frame, I see if it is still outside the left edge before checking if it is behind me etc.

Share this post


Link to post
Share on other sites
bwhiting    1562
Quote:
Original post by dpadam450
I currently use a bounding sphere and hold onto the last side it failed from, so if it was on the left of the screen last frame, I see if it is still outside the left edge before checking if it is behind me etc.


neat trick, another thing to look into!

Share this post


Link to post
Share on other sites
alvaro    21247
If you end up implementing some for of hierarchy in your scene, you should determine if a bounding volume is (A) completely to one side (inside) of a frustum's plane, (B) completely to the other side (outside) or (C) if it is cut by the plane. In case A, you can obviously return without drawing anything. In the other two cases, you need to get down to the objects contained in this volume, and the difference between the two is that in case (B) you don't need to continue checking the smaller objects against this plane, because you know that all of them are inside.

In order to do this with all 6 planes, you can keep a 6-bit integer that indicates which planes you have to check against, and pass that down the recursive call to draw the scene.

I first saw this very clever trick described in "3D Game Engine Design", by Dave Eberly.

Share this post


Link to post
Share on other sites
Vilem Otte    2938
My post is just for a bit of information more, but if you'd use optimisation scheme (like BSP-tree ... especially KD-tree, or BVHs), you could also perform raytracing, where you get occlusion culling by default.

The wonderful thing is, that one can drop all ideas behind frustum culling or occlussion queries off and has them by default.

Of course on the other hand, we've got extensions to do both things today (in OpenGL), Direct3D has also occlussion queries afaik ... so one don't need to perform these computationaly heavy tests.

So you might try google occlussion queries in d3d or gl and try them.

Share this post


Link to post
Share on other sites
alvaro    21247
Quote:
Original post by Vilem Otte
So you might try google occlussion queries in d3d or gl and try them.


My understanding is that occlusion queries require flushing of everything you have sent to the graphics card, which makes them not very practical.

Actually, my first question ever in these forums was about this precisely.

Share this post


Link to post
Share on other sites
NicolasJay    96
Quote:

I think it's easier to compute the view frustum in world coordinates and then determine if the bounding volume intersects it or not


+1


void GEOM::SetupFrustrum(UINT16 fov_deg)
{
int safeframe = 2;
FOV = (float)fov_deg;
FOCAL_LENGTH = ((float)(SCREENWIDTH - safeframe) / 2.0f) / tan(FOV * RAD / 2.0f);

float horz_ang = atan2((SCREENWIDTH - safeframe) / 2.0f, FOCAL_LENGTH);
float vert_ang = atan2((SCREENHEIGHT - safeframe) / 2.0f, FOCAL_LENGTH);

float sin_horz_ang = sin(horz_ang);
float sin_vert_ang = sin(vert_ang);
float cos_horz_ang = cos(horz_ang);
float cos_vert_ang = cos(vert_ang);
//LEFT
frustrum[0].x = cos_horz_ang;
frustrum[0].y = 0;
frustrum[0].z = sin_horz_ang;
frustrum[0].w = 0;
//RIGHT
frustrum[1].x = -cos_horz_ang;
frustrum[1].y = 0;
frustrum[1].z = sin_horz_ang;
frustrum[1].w = 0;
//TOP
frustrum[2].x = 0;
frustrum[2].y = -cos_vert_ang;
frustrum[2].z = sin_vert_ang;
frustrum[2].w = 0;
//BOTTOM
frustrum[3].x = 0;
frustrum[3].y = cos_vert_ang;
frustrum[3].z = sin_vert_ang;
frustrum[3].w = 0;
//NEAR
frustrum[4].x = 0;
frustrum[4].y = 0;
frustrum[4].z = 1;
frustrum[4].w = -1;
//FAR
frustrum[5].x = 0;
frustrum[5].y = 0;
frustrum[5].z = -1;
frustrum[5].w = 2000;
}




obj[o].clip_flags[v] = 0;
if(Dot4(tvert->pos, frustrum[0]) <= 0) obj[o].clip_flags[v] |= CF_LEFT;
if(Dot4(tvert->pos, frustrum[1]) <= 0) obj[o].clip_flags[v] |= CF_RIGHT;
if(Dot4(tvert->pos, frustrum[2]) <= 0) obj[o].clip_flags[v] |= CF_TOP;
if(Dot4(tvert->pos, frustrum[3]) <= 0) obj[o].clip_flags[v] |= CF_BOTTOM;
if(Dot4(tvert->pos, frustrum[4]) <= 0) obj[o].clip_flags[v] |= CF_NEAR;
if(Dot4(tvert->pos, frustrum[5]) <= 0) obj[o].clip_flags[v] |= CF_FAR;



=D

Share this post


Link to post
Share on other sites
_the_phantom_    11250
Quote:
Original post by alvaro
Quote:
Original post by Vilem Otte
So you might try google occlussion queries in d3d or gl and try them.


My understanding is that occlusion queries require flushing of everything you have sent to the graphics card, which makes them not very practical.


Not quite; you have to wait for the query to complete before you can make a choice on it so you can't simply issue the query and then use it right away.

This has been made more useful via predicted drawing;
- issue occulsion query
- do 'other stuff'
- issue predicted draw which depends on the query return

Share this post


Link to post
Share on other sites
crowley9    226
DX10 level GPUs support predicated occlusion culling that will allow you to schedule one drawcall that depends on the results of another without flushing the software command queue. This helps some, although you should still try to batch your predicates and hierarchical predicate culling is a little tricky to get right.

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