BSP Tree Hierarchies - Real-Time Collision Detection - page 362

// Given a vector of polygons, attempts to compute a good splitting plane
Plane PickSplittingPlane(std::vector<Polygon *> &polygons)
{
// Blend factor for optimizing for balance or splits (should be tweaked)
const float K = 0.8f;
// Variables for tracking best splitting plane seen so far
Plane bestPlane;
float bestScore = FLT_MAX;
// Try the plane of each polygon as a dividing plane
for(inti=0;i<polygons.size(); i++) {
int numInFront = 0, numBehind = 0, numStraddling = 0;
Plane plane = GetPlaneFromPolygon(polygons[i]);
// Test against all other polygons
for(intj=0;j<polygons.size(); j++) {
// Ignore testing against self
if (i == j) continue;
// Keep standing count of the various poly-plane relationships
switch (ClassifyPolygonToPlane(polygons[j], plane)) {
case POLYGON_COPLANAR_WITH_PLANE:
/* Coplanar polygons treated as being in front of plane */
case POLYGON_IN_FRONT_OF_PLANE:
numInFront++;
break;
case POLYGON_BEHIND_PLANE:
numBehind++;
break;
case POLYGON_STRADDLING_PLANE:
numStraddling++;
break;
}
}
// Compute score as a weighted combination (based on K, with K in range
// 0..1) between balance and splits (lower score is better)
float score=K*numStraddling + (1.0f - K) * Abs(numInFront - numBehind);
if (score < bestScore) {
bestScore = score;
bestPlane = plane;
}
}
return bestPlane;
}