Main Page   Namespace List   Class Hierarchy   Compound List   File List   Compound Members   File Members  

bsp.cpp

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

Generated on Fri Dec 23 05:15:46 2005 for Constructive Solid Geometry by doxygen1.2.15