Sign in to follow this  
Shnoutz

BSP select best splitter efficiency

Recommended Posts

I am analysing the complexity and running time of some parts of my BSP compiler code. Surprising at first, the slowest part of my code is my "selectSplitter" function that select a polygon to split the BSP polygons. These are the profiler results for the "selectSplitter" function -------------------------------------------- Profiler results : Test : Build BSP tree Occurence : 682 Accumulated time : 0.154053 Minimum time : 0.000000 Maximum time : 0.010376 Average time : 0.000226 Test : BSP select splitter Occurence : 26647 Accumulated time : 28.070801 Minimum time : 0.000000 Maximum time : 4.949219 Average time : 0.001053 Test : BSP classify polygons Occurence : 26647 Accumulated time : 0.153320 Minimum time : 0.000000 Maximum time : 0.001587 Average time : 0.000006 -------------------------------------------- This is the function code :
ovoid Tree::selectSplitter (ocpplane pPlane, PolygonList * const pPolygons)
{
	// Get first polygon
	Polygon const * pPolygon = pPolygons->getFront ();
	// Define best splitter polygon pointer
	Polygon const * pSelectedSplitter = onull;
	// Define best splitter score
	oint32 iBestScore = omaxint32;

	// Loop all polygons
	while (pPolygon)
	{
		// If the polygon is not already a splitter
		if (!pPolygon->bIsSplitter)
		{
			// Define front vertex count
			oint32 iFrontCount = 0;
			// Define back vertex count
			oint32 iBackCount = 0;
			// Define on plane vertex count
			oint32 iSpanningCount = 0;								
			// Loop all polygons
			Polygon * pCurrentPolygon = pPolygons->getFront ();
			do
			{
				// Classify the current polygon against the polygon plane
				switch (pCurrentPolygon->shape.classify (&pPolygon->shape.plane))
				{
					// Increment front count
					case CS_FRONT : ++iFrontCount; break;
					// Increment back count
					case CS_BACK : ++iBackCount; break;
					// Increment spanning count
					case CS_SPANNING : ++iSpanningCount; break;
				}
				// Get next polygon
				pCurrentPolygon = pCurrentPolygon->getNext ();
			}
			while (pCurrentPolygon);
				
			// Claculate the polygon score
			ocint32 iScore = Math::abs (iFrontCount - iBackCount) + (iSpanningCount * iSplitTreshold);
					
			// If score is lower than best score
			if (iScore < iBestScore)
			{
				// Define new best score
				iBestScore = iScore;
				// Set best splitter polygone pointer
				pSelectedSplitter = pPolygon;
				// Set the splitter plane
				*pPlane = pSelectedSplitter->shape.plane;
			}
		}	
		//Get next polygon
		pPolygon = pPolygon->getNext ();
	}
}
Ouch ! 29 secs to select splitters... So I changed my implementation to something like this :
ovoid Tree::selectSplitter (ocpplane pPlane, PolygonList * const pPolygons)
{
	// Get first polygon
	Polygon const * pPolygon = pPolygons->getFront ();
	// Loop all polygons
	while (pPolygon)
	{
		// If the polygon is not already a splitter
		if (!pPolygon->bIsSplitter)
		{
			*pPlane = pPolygon->shape.plane;
			return;
		}
		//Get next polygon
		pPolygon = pPolygon->getNext ();
	}
}
I get thoses profiler results : -------------------------------------------- Profiler results : Test : Build BSP tree Occurence : 682 Accumulated time : 0.424805 Minimum time : 0.000000 Maximum time : 0.049805 Average time : 0.000623 Test : BSP select splitter Occurence : 24162 Accumulated time : 0.016602 Minimum time : 0.000000 Maximum time : 0.000488 Average time : 0.000001 Test : BSP classify polygons Occurence : 24162 Accumulated time : 0.621582 Minimum time : 0.000000 Maximum time : 0.008301 Average time : 0.000026 -------------------------------------------- Mush better.. but as expected, the BSP has been splitted a lot more generating about 6 time the polygon count.. My first implementation of selectSplitter was O(n^2) where n is the number of triangle... Is there another/faster way to select a splitter while keeping the choice reasonable ?

Share this post


Link to post
Share on other sites
first thought:
your method iterates every polygon each time, have you considered separating polygons into two arrays, one for polygons that are still viable splitters and one for used/useless splitters. For example polygons that make up the outer walls of your scene would make be useless as splitters. Rather than flag a polygon as a splitter just move it (or a pointer to it) over to the discard array.

second thought:
Have you looked at ID's own work in quake series?

third thought:
[google]


happy coding

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