Sign in to follow this  

BSP select best splitter efficiency

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

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

This topic is 4393 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.

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