Function BuildBSPNode

Descent3/bsp.cpp:531–739

This is the routine that recursively builds the bsptree

// This is the routine that recursively builds the bsptree
int BuildBSPNode(bspnode *tree, listnode **polylist, int numpolys) {
  bsppolygon *partition_poly;
  listnode *lnode = *polylist;
  listnode *next;
  bspnode *frontnode, *backnode;
  listnode *frontlist = NULL, *backlist = NULL;
  bspplane partition_plane;
  int numfront = 0, numback = 0, numsplits = 0;

  ASSERT(numpolys > 0);
  partition_poly = SelectPlane(polylist);

  mprintf_at(2, 5, 0, "Node = %c", Twirly[(Node_twirl++) % 4]);

  if (partition_poly == NULL) {
    // We hit a leaf!  Fill in the appropriate leaf stuff

    /*vector center;
    int total=0;

    vm_MakeZero (&center);

    for (int i=0;i<numpolys;i++)
    {
            bsppolygon *poly=(bsppolygon *)GetListItem (polylist,i);
            ASSERT (poly!=NULL);
            AddListItem (&tree->polylist,poly);
            tree->num_polys++;
            vector polycenter;

            ConvexPolys++;
            vm_MakeZero (&polycenter);

            // Find out if this is a solid or empty leaf
            // This routine may cause some problems because of convex subspace
            for (int t=0;t<poly->nv;t++)
            {
                    polycenter+=poly->verts[t];

            }

            polycenter/=poly->nv;
            center+=polycenter;

    }

    center/=numpolys;
    int ins=0,outs=0;

    for (i=0;i<numpolys;i++)
    {
            bsppolygon *thispoly=(bsppolygon *)GetListItem (polylist,i);
            int fate=ClassifyVector (&thispoly->plane,&center);

            if (fate==BSP_IN_FRONT || fate==BSP_ON_PLANE)
            {
                    outs++;
            }