   BSP select best splitter efficiency
  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 treeOccurence : 682Accumulated time : 0.154053Minimum time : 0.000000Maximum time : 0.010376Average time : 0.000226Test : BSP select splitterOccurence : 26647Accumulated time : 28.070801Minimum time : 0.000000Maximum time : 4.949219Average time : 0.001053Test : BSP classify polygonsOccurence : 26647Accumulated time : 0.153320Minimum time : 0.000000Maximum time : 0.001587Average time : 0.000006--------------------------------------------This is the function code :ovoid Tree::selectSplitter (ocpplane pPlane, PolygonList * const pPolygons){// Get first polygonPolygon const * pPolygon = pPolygons->getFront ();// Define best splitter polygon pointerPolygon const * pSelectedSplitter = onull;// Define best splitter scoreoint32 iBestScore = omaxint32;// Loop all polygonswhile (pPolygon){// If the polygon is not already a splitterif (!pPolygon->bIsSplitter){// Define front vertex countoint32 iFrontCount = 0;// Define back vertex countoint32 iBackCount = 0;// Define on plane vertex countoint32 iSpanningCount = 0;// Loop all polygonsPolygon * pCurrentPolygon = pPolygons->getFront ();do{// Classify the current polygon against the polygon planeswitch (pCurrentPolygon->shape.classify (&pPolygon->shape.plane)){// Increment front countcase CS_FRONT : ++iFrontCount; break;// Increment back countcase CS_BACK : ++iBackCount; break;// Increment spanning countcase CS_SPANNING : ++iSpanningCount; break;}// Get next polygonpCurrentPolygon = pCurrentPolygon->getNext ();}while (pCurrentPolygon);// Claculate the polygon scoreocint32 iScore = Math::abs (iFrontCount - iBackCount) + (iSpanningCount * iSplitTreshold);// If score is lower than best scoreif (iScore < iBestScore){// Define new best scoreiBestScore = iScore;// Set best splitter polygone pointerpSelectedSplitter = pPolygon;// Set the splitter plane*pPlane = pSelectedSplitter->shape.plane;}}//Get next polygonpPolygon = 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 polygonPolygon const * pPolygon = pPolygons->getFront ();// Loop all polygonswhile (pPolygon){// If the polygon is not already a splitterif (!pPolygon->bIsSplitter){*pPlane = pPolygon->shape.plane;return;}//Get next polygonpPolygon = pPolygon->getNext ();}}I get thoses profiler results :--------------------------------------------Profiler results :Test : Build BSP treeOccurence : 682Accumulated time : 0.424805Minimum time : 0.000000Maximum time : 0.049805Average time : 0.000623Test : BSP select splitterOccurence : 24162Accumulated time : 0.016602Minimum time : 0.000000Maximum time : 0.000488Average time : 0.000001Test : BSP classify polygonsOccurence : 24162Accumulated time : 0.621582Minimum time : 0.000000Maximum time : 0.008301Average 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 ?   
  offtopic but, what profiler did you use?   ;  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   ;  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?   ;  no he meant his question "Which profiler did u use" is off from your topic..IE he didnt answer ur question, instead he asked one in return   