Function SelectPlane

Descent3/bsp.cpp:456–528

Selects the best plane to partition with, returning the pointer to polygon to split with

// Selects the best plane to partition with, returning the pointer to polygon to split with
bsppolygon *SelectPlane(listnode **polylist) {
  listnode *outer, *inner;
  bsppolygon *outerpoly, *innerpoly, *bestpoly;
  int splits, front, back, planar, result, balance;
  float score, bestscore;
  float g_kbalance = 1.0;
  float g_ksplit = 0.0;
  float g_kplanar = 0.0;
  int checked = 0;

  bestscore = 9999999.0;
  bestpoly = NULL;

  /*	Iterate through every polygon, checking its plane against all
   * the other polygons. But don't check it against itself
   */

  mprintf_at(2, 4, 0, "Plane = %c", Twirly[(Plane_twirl++) % 4]);

  for (outer = *polylist; outer != NULL; outer = outer->next) {
    outerpoly = (bsppolygon *)outer->data;
    splits = front = back = planar = 0;
    score = 0.0;

    if (outerpoly->plane.used)
      continue;

    // Only check 300 times
    if (checked >= 300)
      return bestpoly;

    for (inner = *polylist; inner != NULL; inner = inner->next) {
      innerpoly = (bsppolygon *)inner->data;
      if (innerpoly != outerpoly) {
        result = ClassifyPolygon(&outerpoly->plane, innerpoly);
        switch (result) {
        case BSP_SPANNING:
          splits++;
          break;
        case BSP_IN_FRONT:
          front++;
          break;
        case BSP_BEHIND:
          back++;
          break;
        case BSP_COINCIDENT:
          planar++;
          break;
        }
      }
    }

    /* Calculate the score. If we have a "perfect" tree, ie
     * it has either no splits, or is perfectly balanced,
     * return the plane to the caller
     */

    balance = abs(front - back);