bsp.cpp Source File

00001 // BSP functions    by Alan Baylis 2001
00002 
00003 #include "shared.h"
00004 #include "listnode.h"
00005 #include "bsp.h"
00006 #include "locmath.h"
00007 #include "polygon.h"
00008 #include "camera.h"
00009 #include "collision.h"
00010 #include "lightmap.h"
00011 #include "tll.h"
00012 #include "mmgr.h"
00013 
00014 extern CAMERA* camera;
00015 extern int currentCamera;
00016 extern LinkedList<ListNode> LeafList;
00017 extern LinkedList<ListNode> PartitionList;
00018 extern ListNode* listnode;
00019 extern int numcurrentportals;
00020 extern int numleaves;
00021 extern int numpartitions;
00022 extern int showportals;
00023 extern int currentleaf;
00024 
00025 int FindCurrentLeaf(VECTOR Position, BSP_node* node)
00026 {
00027     if (node->leaf == true)
00028     {
00029         numcurrentportals = node->numportals;
00030         return node->nodeid;
00031     }
00032 
00033     VECTOR edge1, edge2, planeNormal, temp;
00034     // get the partitioning planes normal
00035     edge1.x = node->partition.Vertex[1].x - node->partition.Vertex[0].x;
00036     edge1.y = node->partition.Vertex[1].y - node->partition.Vertex[0].y;
00037     edge1.z = node->partition.Vertex[1].z - node->partition.Vertex[0].z;
00038     edge2.x = node->partition.Vertex[2].x - node->partition.Vertex[0].x;
00039     edge2.y = node->partition.Vertex[2].y - node->partition.Vertex[0].y;
00040     edge2.z = node->partition.Vertex[2].z - node->partition.Vertex[0].z;
00041     planeNormal = CrossVector(edge1, edge2);
00042     temp.x = node->partition.Vertex[0].x;
00043     temp.y = node->partition.Vertex[0].y;
00044     temp.z = node->partition.Vertex[0].z;
00045 
00046     int side = ClassifyPoint(Position, temp, planeNormal);
00047 
00048     if (side == 1 || side == 0)
00049     {
00050         return FindCurrentLeaf(Position, node->frontnode);
00051     }
00052     else
00053     {
00054         return FindCurrentLeaf(Position, node->backnode);
00055     }
00056 }
00057 
00058 int SelectPartitionfromList(POLYGON* nodepolylist, int numpolys, int* bestfront, int* bestback)
00059 {
00060     int count = 0, result, absdifference = 1000000000, bestplane = 0, front, back, potentialplane, polytoclassify;
00061     VECTOR temp;
00062 
00063     // Loop through all the polygons and find the best splitting plane
00064     for(potentialplane = 0; potentialplane < numpolys; potentialplane++)
00065     {
00066         front = back = 0;
00067         for (polytoclassify = 0; polytoclassify < numpolys; polytoclassify++)
00068         {
00069             result = SplitPolygon(nodepolylist[polytoclassify], nodepolylist[potentialplane], NULL);
00070             switch (result)
00071             {
00072                 case Front:
00073                     front++;
00074                 break;
00075 
00076                 case Back:
00077                     back++;
00078                 break;
00079 
00080                 case TwoFrontOneBack:
00081                     front += 2;
00082                     back++;
00083                 break;
00084 
00085                 case OneFrontTwoBack:
00086                     front++;
00087                     back += 2;
00088                 break;
00089 
00090                 case OneFrontOneBack:
00091                     front++;
00092                     back++;
00093                 break;
00094             }
00095         }
00096         if (abs(front - back) < absdifference)
00097         {
00098             absdifference = abs(front - back);
00099             bestplane = potentialplane;
00100             *bestfront = front;
00101             *bestback = back;
00102         }
00103         if (front == 0 || back == 0)
00104             count++;
00105     }
00106     if (count == numpolys)
00107         return -1;
00108     else
00109         return bestplane;
00110 }
00111 
00112 void BuildBSP(BSP_node *node)
00113 {
00114     int result, front, back, polytoclassify, partplane;
00115     POLYGON output[3];
00116 
00117     partplane = SelectPartitionfromList(node->nodepolylist, node->numpolys, &front, &back);
00118 
00119     if (partplane == -1)
00120     {
00121         node->nodeid = ++numleaves;
00122         node->leaf = true;
00123         return;
00124     }
00125 
00126     node->nodeid = ++numpartitions;
00127     node->partition = node->nodepolylist[partplane];
00128 
00129     //Allocate memory for a front and back node
00130     node->frontnode = new BSP_node;
00131     node->frontnode->visible = 0;
00132     node->frontnode->leaf = 0;
00133     node->frontnode->numpolys = front;
00134     node->frontnode->nodepolylist = new POLYGON[front];
00135     node->frontnode->numportals = 0;
00136 
00137     node->backnode = new BSP_node;
00138     node->backnode->visible = 0;
00139     node->backnode->leaf = 0;
00140     node->backnode->numpolys = back;
00141     node->backnode->nodepolylist = new POLYGON[back];
00142     node->backnode->numportals = 0;
00143     //Classify each polygon in the current node with respect to the partitioning plane.
00144     front = back = 0;
00145     for (polytoclassify = 0; polytoclassify < node->numpolys; polytoclassify++)
00146     {
00147         output[0] = node->nodepolylist[polytoclassify];
00148         output[1] = node->nodepolylist[polytoclassify];
00149         output[2] = node->nodepolylist[polytoclassify];
00150 
00151         result = SplitPolygon(node->nodepolylist[polytoclassify], node->partition, output);
00152         switch (result)
00153         {
00154             case Front:
00155                 node->frontnode->nodepolylist[front] = node->nodepolylist[polytoclassify];
00156                 front++;
00157             break;
00158 
00159             case Back:
00160                 node->backnode->nodepolylist[back] = node->nodepolylist[polytoclassify];
00161                 back++;
00162             break;
00163 
00164             case TwoFrontOneBack:
00165                 node->frontnode->nodepolylist[front] = output[0];
00166                 node->frontnode->nodepolylist[front + 1] = output[1];
00167                 front += 2;
00168                 node->backnode->nodepolylist[back] = output[2];
00169                 back++;
00170             break;
00171 
00172             case OneFrontTwoBack:
00173                 node->frontnode->nodepolylist[front] = output[0];
00174                 front++;
00175                 node->backnode->nodepolylist[back] = output[1];
00176                 node->backnode->nodepolylist[back + 1] = output[2];
00177                 back += 2;
00178             break;
00179 
00180             case OneFrontOneBack:
00181                 node->frontnode->nodepolylist[front] = output[0];
00182                 front++;
00183                 node->backnode->nodepolylist[back] = output[1];
00184                 back++;
00185             break;
00186         }
00187     }
00188 
00189     node->numpolys = 0;
00190     delete[] node->nodepolylist;
00191     node->nodepolylist = 0;
00192 //    delete[] node->nodelightmaplist;
00193 
00194     BuildBSP(node->frontnode);
00195     BuildBSP(node->backnode);
00196 }
00197 
00198 int RenderBSP(BSP_node *node)
00199 {
00200     int Side;
00201     VECTOR Position, edge1, edge2, planeNormal, temp;
00202 
00203     //The current position of the player/viewpoint
00204     Position.x = camera[currentCamera].Position.x;
00205     Position.y = camera[currentCamera].Position.y;
00206     Position.z = camera[currentCamera].Position.z;
00207 
00208     if (!node->leaf)
00209     {
00210         // get the partitioning planes normal
00211         edge1.x = node->partition.Vertex[1].x - node->partition.Vertex[0].x;
00212         edge1.y = node->partition.Vertex[1].y - node->partition.Vertex[0].y;
00213         edge1.z = node->partition.Vertex[1].z - node->partition.Vertex[0].z;
00214         edge2.x = node->partition.Vertex[2].x - node->partition.Vertex[0].x;
00215         edge2.y = node->partition.Vertex[2].y - node->partition.Vertex[0].y;
00216         edge2.z = node->partition.Vertex[2].z - node->partition.Vertex[0].z;
00217         planeNormal = CrossVector(edge1, edge2);
00218         temp.x = node->partition.Vertex[0].x;
00219         temp.y = node->partition.Vertex[0].y;
00220         temp.z = node->partition.Vertex[0].z;
00221         Side = ClassifyPoint(Position, temp, planeNormal);
00222 
00223         if (Side == -1)
00224         {
00225             RenderBSP(node->frontnode);
00226             RenderBSP(node->backnode);
00227         }
00228         else
00229         {
00230             RenderBSP(node->backnode);
00231             RenderBSP(node->frontnode);
00232         }
00233     }
00234 
00235     if (node->leaf && node->visible)
00236     {
00237         node->visible = false;
00238         //Draw polygons that are in the leaf
00239         for (int loop = 0; loop < node->numpolys; loop++)
00240         {
00241             glMatrixMode(GL_TEXTURE);
00242             glPushMatrix();
00243 
00244             glScalef(node->nodepolylist[loop].Scale[0], node->nodepolylist[loop].Scale[1], 1.0f);
00245             glTranslatef(node->nodepolylist[loop].Shift[0], node->nodepolylist[loop].Shift[1], 0.0f);
00246             glRotatef(node->nodepolylist[loop].Rotate, 0.0f, 0.0f, 1.0f);
00247             glBindTexture(GL_TEXTURE_2D, node->nodepolylist[loop].Texture);
00248             glBegin(GL_TRIANGLES);
00249                 glNormal3fv(&node->nodepolylist[loop].Vertex[0].nx);
00250                 glTexCoord2f(node->nodepolylist[loop].Vertex[0].u, node->nodepolylist[loop].Vertex[0].v);
00251                 glVertex3fv(&node->nodepolylist[loop].Vertex[0].x);
00252                 glTexCoord2f(node->nodepolylist[loop].Vertex[1].u, node->nodepolylist[loop].Vertex[1].v);
00253                 glVertex3fv(&node->nodepolylist[loop].Vertex[1].x);
00254                 glTexCoord2f(node->nodepolylist[loop].Vertex[2].u, node->nodepolylist[loop].Vertex[2].v);
00255                 glVertex3fv(&node->nodepolylist[loop].Vertex[2].x);
00256             glEnd();
00257             glPopMatrix();
00258             glMatrixMode(GL_MODELVIEW);
00259 
00260             glEnable(GL_BLEND);
00261             glBlendFunc(GL_DST_COLOR, GL_SRC_COLOR);
00262 
00263             glBindTexture(GL_TEXTURE_2D, node->nodelightmaplist[loop].Texture.TexID);
00264             glBegin(GL_TRIANGLES);
00265                 glNormal3fv(&node->nodepolylist[loop].Vertex[0].nx);
00266                 glTexCoord2f(node->nodelightmaplist[loop].vertex_u[0], node->nodelightmaplist[loop].vertex_v[0]);
00267                 glVertex3fv(&node->nodepolylist[loop].Vertex[0].x);
00268                 glTexCoord2f(node->nodelightmaplist[loop].vertex_u[1], node->nodelightmaplist[loop].vertex_v[1]);
00269                 glVertex3fv(&node->nodepolylist[loop].Vertex[1].x);
00270                 glTexCoord2f(node->nodelightmaplist[loop].vertex_u[2], node->nodelightmaplist[loop].vertex_v[2]);
00271                 glVertex3fv(&node->nodepolylist[loop].Vertex[2].x);
00272             glEnd();
00273             glDisable(GL_BLEND);
00274         }
00275 
00276         if (showportals)
00277         {
00278             // Draw the leaf portals
00279             glDisable(GL_TEXTURE_2D);
00280             glDisable(GL_LIGHTING);
00281             glEnable(GL_BLEND);
00282             glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
00283             glEnable(GL_ALPHA_TEST);
00284             glAlphaFunc(GL_GREATER, 0);
00285             glColor4f(1.0, 1.0, 0.0, 0.2);
00286 
00287             if (currentleaf == node->nodeid)
00288             {
00289                 for (int loop = 1; loop <= node->numportals; loop++)
00290                 {
00291                     PORTAL* tempportal = node->portallist.Get(loop);
00292                     glBegin(GL_POLYGON);
00293                         glNormal3fv(&tempportal->Vertex[0].nx);
00294                         for (int innerloop = 0; innerloop < tempportal->numVertices; innerloop++)
00295                             glVertex3f(tempportal->Vertex[innerloop].x, tempportal->Vertex[innerloop].y, tempportal->Vertex[innerloop].z);
00296                     glEnd();
00297                 }
00298             }
00299             glDisable(GL_BLEND);
00300             glDisable(GL_ALPHA_TEST);
00301             glEnable(GL_TEXTURE_2D);
00302             glEnable(GL_LIGHTING);
00303         }
00304     }
00305     return 1;
00306 }
00307 
00308 void DeleteBSP(BSP_node *node)
00309 {
00310     if (node->leaf == true)
00311     {
00312         delete[] node->nodepolylist;
00313         delete[] node->nodelightmaplist;
00314         for (int i = node->numportals; i > 0 ; i--)
00315         {
00316             PORTAL* temp = node->portallist.Get(i);
00317             delete[] temp->Vertex;
00318             node->portallist.Delete(i);
00319             delete temp;
00320         }
00321         node->numportals = 0;
00322         return;
00323     }
00324 
00325     DeleteBSP(node->frontnode);
00326     delete node->frontnode;
00327     DeleteBSP(node->backnode);
00328     delete node->backnode;
00329 }
00330 
00331 void DrawIntersectionSphere(VECTOR coordinates)
00332 {
00333     float mat_ambient[] = { 0.2, 1.0, 0.1, 1.0 };
00334     float mat_diffuse[] = { 0.2, 1.0, 0.1, 1.0 };
00335     glMaterialfv(GL_FRONT, GL_AMBIENT, mat_ambient);
00336     glMaterialfv(GL_FRONT, GL_DIFFUSE, mat_diffuse);
00337     glDisable(GL_TEXTURE_2D);
00338     glPushMatrix();
00339     glTranslatef(coordinates.x, coordinates.y, coordinates.z);
00340     GLUquadricObj * sphere = gluNewQuadric();
00341     gluQuadricOrientation(sphere, GLU_OUTSIDE);
00342     gluSphere(sphere,0.3,20,20);
00343     glPopMatrix();
00344     glEnable(GL_TEXTURE_2D);
00345 }