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 ?

Dmatter, that really seem to be a good idea. I'll try that first.

Hammackj, I used my own function profiler. In which forum should I put my question?