Function BuildBSPTree

Descent3/bsp.cpp:780–936

Builds a bsp tree for the indoor rooms

// Builds a bsp tree for the indoor rooms
void BuildBSPTree() {
  int i, t, k, j, x;
  int numpolys = 0;
  int check;

  if (!UseBSP)
    return;

  // Check to see if we even need to build a new tree
  check = BSPGetMineChecksum();

  if (check == BSPChecksum) {
    mprintf(0, "BSP tree already built!\n");
    return; // The BSP tree has already been built for this mine
  }

  BSPChecksum = check;

  // Free up any BSP trees that we might have lying around
  InitDefaultBSP();

  MineBSP.root = NewBSPNode();
  ASSERT(MineBSP.root);

  mprintf(0, "Building BSP Tree...\n");

  mprintf(0, "Adding polygons to tree\n");

  // Go through the whole mine and add each polygon to the possible BSP
  // partition list.  Don't include portals...
  for (i = 0; i <= Highest_room_index; i++) {
    bsppolygon *newpoly;

    if (Rooms[i].used == 0 || (Rooms[i].flags & RF_EXTERNAL))
      continue;

    room *rp = &Rooms[i];

    for (t = rp->objects; (t != -1); t = Objects[t].next) {
      object *obj = &Objects[t];

      if (obj->type == OBJ_NONE)
        continue;

      if (OBJECT_OUTSIDE(obj))
        continue;

      if (obj->lighting_render_type == LRT_LIGHTMAPS) {
        poly_model *po = &Poly_models[obj->rtype.pobj_info.model_num];

        if (!po->new_style)
          continue;

        for (k = 0; k < po->n_models; k++) {
          bsp_info *sm = &po->submodel[k];

          if (IsNonRenderableSubmodel(po, k))
            continue;