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

Generated on Fri Dec 23 05:19:53 2005 for Particles by doxygen1.2.15