Skip to main content
gamedev.net
🔒 Locked

object culling

Started by bwhiting Dec 1, 2010 at 3:47 PM 9 replies 3.6k views
Original Post
bwhiting
bwhiting
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!
alvaro
alvaro
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.

bwhiting
bwhiting
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!
dpadam450
dpadam450
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.
NBA2K, Madden, Maneater, Killing Floor, Sims 
bwhiting
bwhiting
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!
alvaro
alvaro
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.

Vilem Otte
Vilem Otte
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.
alvaro
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.

Actually, my first question ever in these forums was about this precisely.
NicolasJay
NicolasJay
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
_the_phantom_
_the_phantom_
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

crowley9
crowley9
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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.