• Advertisement
Sign in to follow this  

Comments on Frustum Culling Method?

This topic is 2997 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

This code uses an object's bounding sphere and some testing to determine if it is inside the frustum. The bounding sphere is created at load time, then transformed with the scene. The Z near and far are tested by z coordinates, then the distance from each of the four other planes is calculated. comments, suggestions, are appreciated. ty
bool IsInFrustum(OBJECT *object)
{
	if(object->tcenter.z > (Z_FAR + object->bound_radius))
		return false;
	if(object->tcenter.z < (Z_NEAR - object->bound_radius))
		return false;

	float vlen = sqrt(object->tcenter.x*object->tcenter.x + object->tcenter.y*object->tcenter.y + object->tcenter.z*object->tcenter.z);
	
	object->tcenter.x /= vlen;
	object->tcenter.y /= vlen;
	object->tcenter.z /= vlen;

	for(int pl = 0; pl < 4; pl++)
		if(  (D3DXVec3Dot((D3DXVECTOR3*)&object->tcenter, (D3DXVECTOR3*)&frustum[pl]) * vlen) < -object->bound_radius  )
			return false;

	return true;
}

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by CPPNick
The bounding sphere is created at load time, then transformed with the scene.
I take this to mean that the bounding sphere has been transformed into view space?

I am not clear whether that optimisation is worth making. Rather than the 6 planes of the view frustum into world space, you transform N bounding spheres into view space - all to save 2 dot products per intersection test.

Share this post


Link to post
Share on other sites
Im not sure what you mean. I transform the object's centers to view space, and then test them against 4 of the frustum planes, because two(znear, and zfar) are parallel to the viewing plane.

here is the render loop.

for(UINT p = 0; p < dxtechdesc.Passes; ++p)
{
for(int ob = 0; ob < ocount; ob++)
{
D3DXVec4Transform(&objects[ob].tcenter, &objects[ob].center, &objects[ob].mtxworld);
D3DXVec4Transform(&objects[ob].tcenter, &objects[ob].tcenter, &mtxview);

if(IsInFrustum(&objects[ob]) == false)
continue;

dxfxdiffusetexture->SetResource(dxrvtexture[ob]);
fxmtxworld->SetMatrix((float*)&objects[ob].mtxworld);
dxfxselfillum->SetBool(objects[ob].SelfIllum);

dxfxtechnique->GetPassByIndex(p)->Apply(0);
objects[ob].mesh->DrawSubset(0);
}
}
dxsc->Present(0, 0);


Share this post


Link to post
Share on other sites
Quote:
Original post by CPPNick
Im not sure what you mean. I transform the object's centers to view space, and then test them against 4 of the frustum planes, because two(znear, and zfar) are parallel to the viewing plane.

I guess the point is that it makes more sense to transform the planes to world coordinates and do the test there.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaroI guess the point is that it makes more sense to transform the planes to world coordinates and do the test there.


If I understand what you mean, It would mean I had to transform the frustrum by the inverse view matrix. If I did that, then I would not be able to get the distance from the plane properly here:

if(  (D3DXVec3Dot((D3DXVECTOR3*)&object->tcenter, (D3DXVECTOR3*)&frustum[pl]) * vlen) < -object->bound_radius  )


The reason being that the planes of the frustrum would no longer pass through (0,0,0).

does that make sense?

Share this post


Link to post
Share on other sites
Quote:
Original post by CPPNick
Quote:
Original post by alvaroI guess the point is that it makes more sense to transform the planes to world coordinates and do the test there.


If I understand what you mean, It would mean I had to transform the frustrum by the inverse view matrix. If I did that, then I would not be able to get the distance from the plane properly here:

*** Source Snippet Removed ***
The reason being that the planes of the frustrum would no longer pass through (0,0,0).

does that make sense?


You'd just have to subtract the camera position from the center, or something trivial like that.

EDIT: Also, if you have your scene in a hierarchy you should consider returning three value for each intersection with a plane: "outside", "inside" and "in between". That way, you can keep a mask indicating what planes of the frustum need to be checked. I don't know if there is a name for this technique, so I can't find you an online reference. I learned about it in one of David Eberly's books. It seems to be described here.

Share this post


Link to post
Share on other sites
I read that article once through, but didn't catch this the first time:


bool IsInFrustum(OBJECT *object)
{
if(object->tcenter.z > (Z_FAR + object->bound_radius))
return false;
if(object->tcenter.z < (Z_NEAR - object->bound_radius))
return false;

float vlen = sqrt(object->tcenter.x*object->tcenter.x + object->tcenter.y*object->tcenter.y + object->tcenter.z*object->tcenter.z);

//object->tcenter.x /= vlen;
//object->tcenter.y /= vlen;
//object->tcenter.z /= vlen;

for(int pl = 0; pl < 4; pl++)
//if( (D3DXVec3Dot((D3DXVECTOR3*)&object->tcenter, (D3DXVECTOR3*)&frustum[pl]) * vlen) < -object->bound_radius )
if( D3DXVec3Dot((D3DXVECTOR3*)&object->tcenter, (D3DXVECTOR3*)&frustum[pl]) < -object->bound_radius )
return false;

return true;







The new code works just the same, but I commented out the redundant math.

thanks for reminding me of that article.. that coulda costed me 3 nasty divs AND a sqrt per object......eww.

Share this post


Link to post
Share on other sites
also, mine is faster right now because I am skipping the two dot products when I check the near and far plane. I think I understand about the hierarchy now though. If a bounding sphere of a model of a human was to intersect the frustum, I may then have to check the bounding sphere of each of the limbs...right?

Share this post


Link to post
Share on other sites
Quote:
Original post by CPPNick
also, mine is faster right now because I am skipping the two dot products when I check the near and far plane.
Sure, it is faster in isolation. However, you have to transform the bounding sphere into view space before testing, which costs a matrix multiply per sphere (considerably more than the cost of two dot products).

I also don't think you can handle non-uniform scale with your approach - although you may not need that anyway.

Share this post


Link to post
Share on other sites

Hi,

You should test different methods also, such as frustum - axis aligned bounding box or object oriented bounding box, to find out how much it matters which frustum culling method is implemented.

Problem with a bounding sphere is that it may contain "lots of empty space".
For example, consider a very thin and long object inside a sphere bound. This puts more stress on other parts of the engine. Of course, other shapes may fail as well with other kind of geometry.

I would take the advice and implement frustum culling in world space. It takes more time to transform between spaces than to do the actual visibility calculation. You could implement several bounding volume shapes to optimize the culling.

Good luck!

Share this post


Link to post
Share on other sites
One thing that works well for culling is using a bounding volume that is described as the convex hull of a small number of spheres. You can easily test if the volume is entirely on one side of a plane by checking that all the spheres are on the same side. If there is one sphere that intersects the plane or if there is at least one sphere on each side, you know that the plane intersects the volume. That is actually all you need in order to do frustum culling, and your volumes can be much tighter than using a single sphere (for instance for long objects, as kauna points out).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement