bsp.cpp

//
// CS 4143
// Final Project
// James Haley
//
// BSP Generation code
//

#include <stdlib.h>
#include <iostream.h>
#include <vector>
#include "geometry.h"
#include "bsp.h"
#include "input.h"
#include "OutBuffer.h"

// Globals

vector<T_Polygon> polygons;

//
// BSP Generation functions
//

BSPNode treeRoot;

void BSPNode::setPartition()
{
   if(polygons.empty())
   {
      BSPGen_Error("Error: cannot set partition for an empty BSP node");
   }

   // use first vertex of first polygon to solve for plane normal d
   T_Vector normal = polygons[0].getNormal();
   T_Point  vert   = polygons[0][0];

   double d = 
      -normal[0] * vert[0] - normal[1] * vert[1] - normal[2] * vert[2];

   partition = T_Plane(normal[0], normal[1], normal[2], d);
}

void BSPNode::BuildTree(BSPNode *tree, vector<T_Polygon> &plist)
{
   // simply use first polygon in list as partition

   T_Polygon root = plist[0];

   // insert this polygon into the root's polygon list, and set
   // the root's partition plane using the polygon's normal
   tree->polygons.push_back(root);
   tree->setPartition();

   vector<T_Polygon> front_list;
   vector<T_Polygon> back_list;
   T_Polygon temp;

   // classify all polygons with respect to the partition
   for(int i = 1; i < plist.size(); i++)
   {
      temp = plist[i];

      int result = tree->partition.classifyPolygon(temp);

      switch(result)
      {
      case PC_BEHIND:
         back_list.push_back(temp);
         break;
      case PC_INFRONT:
         front_list.push_back(temp);
         break;
      case PC_ON:
         tree->polygons.push_back(temp);
         break;
      case PC_INTERSECT:
         T_Polygon *frontp, *backp;
         temp.split(tree->partition, &frontp, &backp);
         front_list.push_back(*frontp);
         back_list.push_back(*backp);

         // note: freeing the split polygons is the client's
         // responsibility
         delete frontp;
         delete backp;
         break;
      }
   }

   // recursively build children if corresponding lists are not
   // empty
   if(!front_list.empty())
   {
      tree->front = new BSPNode;
      BuildTree(tree->front, front_list);
   }

   if(!back_list.empty())
   {
      tree->back = new BSPNode;
      BuildTree(tree->back, back_list);
   }
}

int curnum;

void BSPNode::EnumerateNodes(BSPNode *tree)
{
   // number nodes with a pre-order traversal to prepare for
   // serialization

   tree->num = curnum++;

   if(tree->front)
      EnumerateNodes(tree->front);
   if(tree->back)
      EnumerateNodes(tree->back);
}

void BSPNode::pack(OutBuffer &ob)
{
   ob.beginRecord(); // start record
   ob.pushScope();   // open global scope
   {
      ob.pack(); // pack a lone opening delimiter

      // step 1: pack the serial number of this node
      ob.packInt("NUM", num);
      
      // step 2: pack the partition plane
      ob.pushScope();
      {
         ob.pack("PARTITION");
         ob.packDouble("A", partition.getA());
         ob.packDouble("B", partition.getB());
         ob.packDouble("C", partition.getC());
         ob.packDouble("D", partition.getD());
      }
      ob.popScope();

      int fNum = -1;
      int bNum = -1;

      // step 3: pack the serial numbers of the front and back nodes,
      // or -1 if none exist
      if(front)
      {
         fNum = front->num;
      }
      if(back)
      {
         bNum = back->num;
      }

      ob.packInt("FRONT", fNum);
      ob.packInt("BACK", bNum);

      // step 4: pack each polygon in the coincident list
      for(int i = 0; i < polygons.size(); i++)
      {
         float *color = polygons[i].getColor();
         int numVertices = polygons[i].getNumVertices();

         ob.pushScope();
         {
            ob.pack("POLYGON");

            ob.pushScope();
            {
               ob.pack("COLOR");
               ob.packDouble("R", color[0]);
               ob.packDouble("G", color[1]);
               ob.packDouble("B", color[2]);
            }
            ob.popScope();
            
            ob.packInt("NUMVERTICES", numVertices);
            
            for(int j = 0; j < numVertices; j++)
            {
               ob.pushScope();
               {
                  ob.pack("VERTEX");
                  ob.packDouble("X", polygons[i][j][0]);
                  ob.packDouble("Y", polygons[i][j][1]);
                  ob.packDouble("Z", polygons[i][j][2]);
               }
               ob.popScope();
            }
         }
         ob.popScope();
      }
   }
   ob.popScope();    // close global scope
   ob.endRecord();   // close the record
}

void BSPNode::SerializeTree(BSPNode *tree, OutBuffer &ob)
{
   // pack root
   tree->pack(ob);

   // pack children if they exist
   if(tree->front)
      SerializeTree(tree->front, ob);
   if(tree->back)
      SerializeTree(tree->back, ob);
}

//
// main program functions
//

void BSPGen_Error(const char *msg)
{
   cerr << msg << endl;
   exit(-1);
}

int main(int argc, char *argv[])
{
   if(argc < 3)
   {
      cout << "Usage: bspgen inputfile outputfile" << endl;
      return 0;
   }

   // parse input
   ParseInputFile(argv[1]);

   // build the BSP tree
   BSPNode::BuildTree(&treeRoot, polygons);

   // enumerate the BSP nodes
   curnum = 0;
   BSPNode::EnumerateNodes(&treeRoot);

   // create output buffer and serialize the tree
   OutBuffer ob(4096, argv[2]);

   BSPNode::SerializeTree(&treeRoot, ob);

   // write out the output buffer
   ob.write();

   return 0;
}