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

bsp.h File Reference

#include "polygon.h"
#include "lightmap.h"
#include "portal.h"
#include "tll.h"
#include "decal.h"

Go to the source code of this file.

Compounds

class  BSP_node

Enumerations

enum  {
  Front, Back, TwoFrontOneBack, OneFrontTwoBack,
  OneFrontOneBack, PortalWasSplit, OnPartition, PolygonWasSplit,
  CoplanarFront, CoplanarBack
}

Functions

void MakeNodeLists (BSP_node *node)
int FindCurrentLeaf (VECTOR Position, BSP_node *node)
int SplitPolygon (POLYGON, POLYGON, POLYGON *)
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)


Enumeration Type Documentation

anonymous enum
 

Enumeration values:
Front 
Back 
TwoFrontOneBack 
OneFrontTwoBack 
OneFrontOneBack 
PortalWasSplit 
OnPartition 
PolygonWasSplit 
CoplanarFront 
CoplanarBack 

Definition at line 11 of file bsp.h.


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 22 of file listnode.cpp.

00023 {
00024     if (node->leaf == true)
00025     {
00026         numlistleaves++;
00027         listnode = new ListNode;
00028         listnode->node = node;
00029         listnode->linkPosition = node->nodeid;
00030         LeafList.Insert(listnode);
00031         return;
00032     }
00033     else
00034     {
00035         if (node->nodeid != 0)
00036         {
00037             numlistpartitions++;
00038             listnode = new ListNode;
00039             listnode->node = node;
00040             listnode->linkPosition = node->nodeid;
00041             PartitionList.Insert(listnode);
00042         }
00043     }
00044     MakeNodeLists(node->frontnode);
00045     MakeNodeLists(node->backnode);
00046 }

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(), BULLET::leaf, BSP_node::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, Lightmap::Texture, POLYGON::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 }

int SplitPolygon POLYGON   ,
POLYGON   ,
POLYGON  
 


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