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