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

bsp.cpp File Reference

#include "shared.h"
#include "listnode.h"
#include "bsp.h"
#include "locmath.h"
#include "polygon.h"
#include "camera.h"
#include "collision.h"
#include "lightmap.h"
#include "tll.h"
#include "bullet.h"
#include "particle.h"
#include "mmgr.h"

Go to the source code of this file.

Functions

void MakeNodeLists (BSP_node *node)
int FindCurrentLeaf (VECTOR Position, BSP_node *node)
int SelectPartitionfromList (POLYGON *nodepolylist, int numpolys, int *bestfront, int *bestback)
void BuildBSP (BSP_node *node)
int RenderBSP (BSP_node *node)
void DeleteBSP (BSP_node *node)
void DrawIntersectionSphere (VECTOR coordinates)

Variables

CAMERAcamera
int currentCamera
LinkedList< BSP_nodeLeafList
LinkedList< BSP_nodePartitionList
BSP_nodelistnode
int numcurrentportals
int numleaves
int numpartitions
int showportals
int currentleaf
int SphereSector
VECTOR SpherePosition
int numBullets
BULLETbullet


Function Documentation

void BuildBSP BSP_node   node
 

Definition at line 142 of file bsp.cpp.

References Back, BSP_node::backnode, Front, BSP_node::frontnode, BSP_node::leaf, BSP_node::nodeid, BSP_node::nodepolylist, BSP_node::numdecals, numleaves, numpartitions, BSP_node::numpolys, BSP_node::numportals, OneFrontOneBack, OneFrontTwoBack, BSP_node::partition, SelectPartitionfromList(), SplitTriangle(), TwoFrontOneBack, and BSP_node::visible.

Referenced by InitGL().

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 }

void DeleteBSP BSP_node   node
 

Definition at line 367 of file bsp.cpp.

References BSP_node::backnode, LinkedList< PORTAL >::Delete(), BSP_node::frontnode, LinkedList< PORTAL >::Get(), BSP_node::leaf, BSP_node::nodelightmaplist, BSP_node::nodepolylist, BSP_node::numportals, BSP_node::portallist, and PORTAL::Vertex.

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 }

void DrawIntersectionSphere VECTOR    coordinates
 

Definition at line 390 of file bsp.cpp.

References VECTOR::x, VECTOR::y, and VECTOR::z.

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 }

int FindCurrentLeaf VECTOR    Position,
BSP_node   node
 

Definition at line 61 of file bsp.cpp.

References BSP_node::backnode, ClassifyPoint(), VERTEX::coords, CrossVector(), BSP_node::frontnode, BSP_node::leaf, BSP_node::nodeid, numcurrentportals, BSP_node::numportals, BSP_node::partition, and POLYGON::Vertex.

Referenced by CheckForParticleCollision(), DrawGLScene(), ParticleManager::Update(), and UpdateBullets().

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 }

void MakeNodeLists BSP_node   node
 

Definition at line 41 of file bsp.cpp.

References BSP_node::backnode, BSP_node::frontnode, LinkedList< T >::Insert(), BSP_node::leaf, BSP_node::linkPosition, MakeNodeLists(), BSP_node::nodeid, and LinkedList< T >::numObjects.

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 }

int RenderBSP BSP_node   node
 

Definition at line 229 of file bsp.cpp.

References BULLET::active, BSP_node::backnode, ClassifyPoint(), VERTEX::coords, DECAL::counter, CrossVector(), currentCamera, BSP_node::decallist, LinkedList< DECAL >::Delete(), BULLET::Draw(), BSP_node::frontnode, LinkedList< DECAL >::Get(), BSP_node::leaf, BULLET::leaf, BSP_node::nodeid, BSP_node::nodelightmaplist, BSP_node::nodepolylist, VERTEX::normal, numBullets, BSP_node::numdecals, BSP_node::numpolys, BSP_node::partition, RenderBulletDecal(), RenderBurnDecal(), RenderParticles(), POLYGON::Rotate, POLYGON::Scale, POLYGON::Shift, TEXTURE::TexID, POLYGON::Texture, Lightmap::Texture, DECAL::type, VERTEX::u, VERTEX::v, POLYGON::Vertex, Lightmap::vertex_u, Lightmap::vertex_v, BSP_node::visible, and VECTOR::x.

Referenced by DrawWorld().

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 }

int SelectPartitionfromList POLYGON   nodepolylist,
int    numpolys,
int *    bestfront,
int *    bestback
 

Definition at line 88 of file bsp.cpp.

References Back, Front, OneFrontOneBack, OneFrontTwoBack, SplitTriangle(), and TwoFrontOneBack.

Referenced by BuildBSP().

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 }


Variable Documentation

BULLET* bullet
 

Definition at line 29 of file bsp.cpp.

CAMERA* camera
 

Definition at line 16 of file bsp.cpp.

int currentCamera
 

Definition at line 17 of file bsp.cpp.

Referenced by RenderBSP().

int currentleaf
 

Definition at line 25 of file bsp.cpp.

LinkedList<BSP_node> LeafList
 

Definition at line 18 of file bsp.cpp.

BSP_node* listnode
 

Definition at line 20 of file bsp.cpp.

int numBullets
 

Definition at line 28 of file bsp.cpp.

Referenced by RenderBSP().

int numcurrentportals
 

Definition at line 21 of file bsp.cpp.

Referenced by FindCurrentLeaf().

int numleaves
 

Definition at line 22 of file bsp.cpp.

Referenced by BuildBSP().

int numpartitions
 

Definition at line 23 of file bsp.cpp.

Referenced by BuildBSP().

LinkedList<BSP_node> PartitionList
 

Definition at line 19 of file bsp.cpp.

int showportals
 

Definition at line 24 of file bsp.cpp.

VECTOR SpherePosition
 

Definition at line 27 of file bsp.cpp.

int SphereSector
 

Definition at line 26 of file bsp.cpp.


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