frustrum culling optimization?

[ZeRaW]

every time we move the camera, the engine recalculates the view frustrum.
in the irrlich implementation, an aabb is used to represent the frustrum.
the aabb is defined by 2 points a min and a max (MinEdge and MaxEdge).
so the frustrum iaabb is calculated using this function:

Code: Select all

inline void SViewFrustrum::recalculateBoundingBox()
{
      core::aabbox3d<f32> box(cameraPosition);

	box.addInternalPoint(getFarLeftUp());
	box.addInternalPoint(getFarRightUp());
	box.addInternalPoint(getFarLeftDown());
	box.addInternalPoint(getFarRightDown());

	boundingBox = box;
}

the 1st thing we see is that the min value will have the minimum on the plane containing the cameraposition where it should be the near plane.
thus a small thing would be changed and instead of contructing the aabb witht the cameraposition, it should be the intersection between the view direction and the near plane which will give a more exact result.


The second thing we notice that each calculation of the points in the far plane is an intersection between 3 planes which has a bit of calculations.



The third point is that aabb is a normal box but the frustrum is not. so the aabb test will return a box inside while it might be outside.




Now i will introduce an alternative method which i implemented in irrlicht:
first lets comment the content of the recalculateBoundingBox function found in SViewFrustrum.h

Code: Select all

inline void SViewFrustrum::recalculateBoundingBox()
{
	/*core::aabbox3d<f32> box(cameraPosition);

	box.addInternalPoint(getFarLeftUp());
	box.addInternalPoint(getFarRightUp());
	box.addInternalPoint(getFarLeftDown());
	box.addInternalPoint(getFarRightDown());

	boundingBox = box;*/
}

so now the engine will not calculate the aabb each game loop.

next in CSceneManager.cpp:
in the functuion bool CSceneManager::isCulled(ISceneNode* node)

the method used was the line:

Code: Select all

return !(tbox.intersectsWithBox(cam->getViewFrustrum()->boundingBox));

comment the above line and continue with the alternative:

Code: Select all

core::vector3d<f32> nearest;
for (int i=0;i<6;i++)
{
	if(cam->getViewFrustrum()->planes[i].Normal.X <= 0)
		nearest.X = tbox.MinEdge.X;
	else
		nearest.X = tbox.MaxEdge.X;

	if(cam->getViewFrustrum()->planes[i].Normal.Y <= 0)
		nearest.Y = tbox.MinEdge.Y;
	else
		nearest.Y = tbox.MaxEdge.Y;


	if(cam->getViewFrustrum()->planes[i].Normal.Z <= 0)
		nearest.Z = tbox.MinEdge.Z;
	else
		nearest.Z = tbox.MaxEdge.Z;

	if(cam->getViewFrustrum()->planes[i].getDistanceTo(nearest)<0)
		return false;
}

return true; //is culled

the above will loop on the planes, for every plane, it will get the point (between the aabb min and max) which is nearest to that plane and then test the distance.
if 1 point is indside the box is inside.

the calculation is fairly simpler then intersections between 3 planes. and more precise than a big aabb.

another optimization in the above code is to add an index to the node aabb.
every time we test with a plane and it gives us outside we save that index.
so next time we test the same aabb we test with the saved index first cuz in 1 game loop usually we do not change from side to side quickly.
then we continue testing with the other planes.

I did the above but my machine is fairly fast (i get 12-15fps with burning's software renderer) and didnt notice any fps gain or loss. i think it is in precision gain.


this FILE contains the includes, libs and dlls for ppl who do not want to re do everyth manually. (Note Dll does not support dx8 so dt run with dx8 )

hopefully some1 has the time and a large scene to test . cuz i dt have any big scenes. or if u can provide me with 1 it would be good.

[burningreggae]

hey!. i'm glad you focus on culling!!!;-)


it's not easy;-). i can understand why you do not have any speed gain or loose.. you are using to much if's...

floating point branching after comparison kills every speed.

but please keep on going;-)
if you manage to increase frame rate in burnings video ( oh yeah mann, i'm shining when i see that people using it;-)) i would be glad if you would show me how;-)

to you have version 1.2b already from svn?.
burningvideo should have a enormous speed-gain.. (culling is the glue;))
could you please post your speed-gain since version1.1?

oki!, keep on going.. it's nice to discuss about culling on lazy christmas holydays.. ( no work this week. Yuhuuuu!)

[dawiki]

Hi!

I tried your code but it didn't work for me. But anyway I did implement your idea in another way.

It works great for me all I did was to recode the CSceneManager::isCulled method like this

Code: Select all

//! returns if node is culled
bool CSceneManager::isCulled(ISceneNode* node)
{
	if (!node->getAutomaticCulling())
		return false;

	ICameraSceneNode* cam = getActiveCamera();
	if (!cam)
		return false;

	const SViewFrustrum* frustrum = cam->getViewFrustrum();
	
	irr::core::vector3df position = node->getPosition();
    f64 length = node->getBoundingBox().MaxEdge.getLength();

	for (int i=0;i<SViewFrustrum::VF_PLANE_COUNT;i++)
	{
		irr::core::plane3d<f32> plane=frustrum->planes[i];
	
		irr::core::EIntersectionRelation3D status= plane.classifyPointRelation(position);
		if(status == irr::core::EIntersectionRelation3D::ISREL3D_BACK)
		{
		    if (plane.getDistanceTo(position) > length)
		    {
		 		return true; //is culled 
		    }
		}
	}

	return false; 
}

Maybe I should say that I'm not a good C/C++ coder as I work most with C#

Hope this would help anybody with similar performance problems

[Cristian]

I tried to optimize your code (if else part). Sorry if this was useless.

Code: Select all

core::vector3d<f32> nearest; 

for (int i=0;i<6;i++) 
{ 
   nearest.X = tbox.MaxEdge.X; 
   if(cam->getViewFrustrum()->planes[i].Normal.X <= 0) 
      nearest.X = tbox.MinEdge.X; 
  
   nearest.Y = tbox.MaxEdge.Y; 
   if(cam->getViewFrustrum()->planes[i].Normal.Y <= 0) 
      nearest.Y = tbox.MinEdge.Y;

   nearest.Z = tbox.MaxEdge.Z;
   if(cam->getViewFrustrum()->planes[i].Normal.Z <= 0) 
      nearest.Z = tbox.MinEdge.Z; 
      
   if(cam->getViewFrustrum()->planes[i].getDistanceTo(nearest)<0) 
      return false; 
} 

return true; //is culled

this seemed to pick up more speed having gotten rid of else branching