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 "mmgr.h"

Go to the source code of this file.

Functions

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< ListNodeLeafList
LinkedList< ListNodePartitionList
ListNodelistnode
int numcurrentportals
int numleaves
int numpartitions
int showportals
int currentleaf


Function Documentation

void BuildBSP BSP_node   node
 

Definition at line 112 of file bsp.cpp.

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

Referenced by InitGL().

00113 {
00114     int result, front, back, polytoclassify, partplane;
00115     POLYGON output[3];
00116 
00117     partplane = SelectPartitionfromList(node->nodepolylist, node->numpolys, &front, &back);
00118 
00119     if (partplane == -1)
00120     {
00121         node->nodeid = ++numleaves;
00122         node->leaf = true;
00123         return;
00124     }
00125 
00126     node->nodeid = ++numpartitions;
00127     node->partition = node->nodepolylist[partplane];
00128 
00129     //Allocate memory for a front and back node
00130     node->frontnode = new BSP_node;
00131     node->frontnode->visible = 0;
00132     node->frontnode->leaf = 0;
00133     node->frontnode->numpolys = front;
00134     node->frontnode->nodepolylist = new POLYGON[front];
00135     node->frontnode->numportals = 0;
00136 
00137     node->backnode = new BSP_node;
00138     node->backnode->visible = 0;
00139     node->backnode->leaf = 0;
00140     node->backnode->numpolys = back;
00141     node->backnode->nodepolylist = new POLYGON[back];
00142     node->backnode->numportals = 0;
00143     //Classify each polygon in the current node with respect to the partitioning plane.
00144     front = back = 0;
00145     for (polytoclassify = 0; polytoclassify < node->numpolys; polytoclassify++)
00146     {
00147         output[0] = node->nodepolylist[polytoclassify];
00148         output[1] = node->nodepolylist[polytoclassify];
00149         output[2] = node->nodepolylist[polytoclassify];
00150 
00151         result = SplitPolygon(node->nodepolylist[polytoclassify], node->partition, output);
00152         switch (result)
00153         {
00154             case Front:
00155                 node->frontnode->nodepolylist[front] = node->nodepolylist[polytoclassify];
00156                 front++;
00157             break;
00158 
00159             case Back:
00160                 node->backnode->nodepolylist[back] = node->nodepolylist[polytoclassify];
00161                 back++;
00162             break;
00163 
00164             case TwoFrontOneBack:
00165                 node->frontnode->nodepolylist[front] = output[0];
00166                 node->frontnode->nodepolylist[front + 1] = output[1];
00167                 front += 2;
00168                 node->backnode->nodepolylist[back] = output[2];
00169                 back++;
00170             break;
00171 
00172             case OneFrontTwoBack:
00173                 node->frontnode->nodepolylist[front] = output[0];
00174                 front++;
00175                 node->backnode->nodepolylist[back] = output[1];
00176                 node->backnode->nodepolylist[back + 1] = output[2];
00177                 back += 2;
00178             break;
00179 
00180             case OneFrontOneBack:
00181                 node->frontnode->nodepolylist[front] = output[0];
00182                 front++;
00183                 node->backnode->nodepolylist[back] = output[1];
00184                 back++;
00185             break;
00186         }
00187     }
00188 
00189     node->numpolys = 0;
00190     delete[] node->nodepolylist;
00191     node->nodepolylist = 0;
00192 //    delete[] node->nodelightmaplist;
00193 
00194     BuildBSP(node->frontnode);
00195     BuildBSP(node->backnode);
00196 }

void DeleteBSP BSP_node   node
 

Definition at line 307 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.

Referenced by WndProc().

00308 {
00309     if (node->leaf == true)
00310     {
00311         delete[] node->nodepolylist;
00312         delete[] node->nodelightmaplist;
00313         for (int i = node->numportals; i > 0 ; i--)
00314         {
00315             PORTAL* temp = node->portallist.Get(i);
00316             delete[] temp->Vertex;
00317             node->portallist.Delete(i);
00318             delete temp;
00319         }
00320         node->numportals = 0;
00321         return;
00322     }
00323 
00324     DeleteBSP(node->frontnode);
00325     delete node->frontnode;
00326     DeleteBSP(node->backnode);
00327     delete node->backnode;
00328 }

void DrawIntersectionSphere VECTOR    coordinates
 

Definition at line 330 of file bsp.cpp.

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

00331 {
00332     float mat_ambient[] = { 0.2, 1.0, 0.1, 1.0 };
00333     float mat_diffuse[] = { 0.2, 1.0, 0.1, 1.0 };
00334     glMaterialfv(GL_FRONT, GL_AMBIENT, mat_ambient);
00335     glMaterialfv(GL_FRONT, GL_DIFFUSE, mat_diffuse);
00336     glDisable(GL_TEXTURE_2D);
00337     glPushMatrix();
00338     glTranslatef(coordinates.x, coordinates.y, coordinates.z);
00339     GLUquadricObj * sphere = gluNewQuadric();
00340     gluQuadricOrientation(sphere, GLU_OUTSIDE);
00341     gluSphere(sphere,0.3,20,20);
00342     glPopMatrix();
00343     glEnable(GL_TEXTURE_2D);
00344 }

int FindCurrentLeaf VECTOR    Position,
BSP_node   node
 

Definition at line 25 of file bsp.cpp.

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

Referenced by DrawGLScene().

00026 {
00027     if (node->leaf == true)
00028     {
00029         numcurrentportals = node->numportals;
00030         return node->nodeid;
00031     }
00032 
00033     VECTOR edge1, edge2, planeNormal, temp;
00034     // get the partitioning planes normal
00035     edge1.x = node->partition.Vertex[1].x - node->partition.Vertex[0].x;
00036     edge1.y = node->partition.Vertex[1].y - node->partition.Vertex[0].y;
00037     edge1.z = node->partition.Vertex[1].z - node->partition.Vertex[0].z;
00038     edge2.x = node->partition.Vertex[2].x - node->partition.Vertex[0].x;
00039     edge2.y = node->partition.Vertex[2].y - node->partition.Vertex[0].y;
00040     edge2.z = node->partition.Vertex[2].z - node->partition.Vertex[0].z;
00041     planeNormal = CrossVector(edge1, edge2);
00042     temp.x = node->partition.Vertex[0].x;
00043     temp.y = node->partition.Vertex[0].y;
00044     temp.z = node->partition.Vertex[0].z;
00045 
00046     int side = ClassifyPoint(Position, temp, planeNormal);
00047 
00048     if (side == 1 || side == 0)
00049     {
00050         return FindCurrentLeaf(Position, node->frontnode);
00051     }
00052     else
00053     {
00054         return FindCurrentLeaf(Position, node->backnode);
00055     }
00056 }

int RenderBSP BSP_node   node
 

Definition at line 198 of file bsp.cpp.

References BSP_node::backnode, ClassifyPoint(), CrossVector(), currentCamera, currentleaf, BSP_node::frontnode, LinkedList< PORTAL >::Get(), BSP_node::leaf, BSP_node::nodeid, BSP_node::nodelightmaplist, BSP_node::nodepolylist, BSP_node::numpolys, BSP_node::numportals, PORTAL::numVertices, VERTEX::nx, BSP_node::partition, BSP_node::portallist, POLYGON::Rotate, POLYGON::Scale, POLYGON::Shift, TEXTURE::TexID, POLYGON::Texture, Lightmap::Texture, VERTEX::u, VERTEX::v, POLYGON::Vertex, PORTAL::Vertex, Lightmap::vertex_u, Lightmap::vertex_v, VECTOR::x, VERTEX::x, VECTOR::y, VERTEX::y, VECTOR::z, and VERTEX::z.

Referenced by DrawWorld().

00199 {
00200     int Side;
00201     VECTOR Position, edge1, edge2, planeNormal, temp;
00202 
00203     //The current position of the player/viewpoint
00204     Position.x = camera[currentCamera].Position.x;
00205     Position.y = camera[currentCamera].Position.y;
00206     Position.z = camera[currentCamera].Position.z;
00207 
00208     if (!node->leaf)
00209     {
00210         // get the partitioning planes normal
00211         edge1.x = node->partition.Vertex[1].x - node->partition.Vertex[0].x;
00212         edge1.y = node->partition.Vertex[1].y - node->partition.Vertex[0].y;
00213         edge1.z = node->partition.Vertex[1].z - node->partition.Vertex[0].z;
00214         edge2.x = node->partition.Vertex[2].x - node->partition.Vertex[0].x;
00215         edge2.y = node->partition.Vertex[2].y - node->partition.Vertex[0].y;
00216         edge2.z = node->partition.Vertex[2].z - node->partition.Vertex[0].z;
00217         planeNormal = CrossVector(edge1, edge2);
00218         temp.x = node->partition.Vertex[0].x;
00219         temp.y = node->partition.Vertex[0].y;
00220         temp.z = node->partition.Vertex[0].z;
00221         Side = ClassifyPoint(Position, temp, planeNormal);
00222 
00223         if (Side == -1)
00224         {
00225             RenderBSP(node->frontnode);
00226             RenderBSP(node->backnode);
00227         }
00228         else
00229         {
00230             RenderBSP(node->backnode);
00231             RenderBSP(node->frontnode);
00232         }
00233     }
00234 
00235     if (node->leaf)
00236     {
00237         //Draw polygons that are in the leaf
00238         for (int loop = 0; loop < node->numpolys; loop++)
00239         {
00240             glMatrixMode(GL_TEXTURE);
00241             glPushMatrix();
00242 
00243             glScalef(node->nodepolylist[loop].Scale[0], node->nodepolylist[loop].Scale[1], 1.0f);
00244             glTranslatef(node->nodepolylist[loop].Shift[0], node->nodepolylist[loop].Shift[1], 0.0f);
00245             glRotatef(node->nodepolylist[loop].Rotate, 0.0f, 0.0f, 1.0f);
00246             glBindTexture(GL_TEXTURE_2D, node->nodepolylist[loop].Texture);
00247             glBegin(GL_TRIANGLES);
00248                 glNormal3fv(&node->nodepolylist[loop].Vertex[0].nx);
00249                 glTexCoord2f(node->nodepolylist[loop].Vertex[0].u, node->nodepolylist[loop].Vertex[0].v);
00250                 glVertex3fv(&node->nodepolylist[loop].Vertex[0].x);
00251                 glTexCoord2f(node->nodepolylist[loop].Vertex[1].u, node->nodepolylist[loop].Vertex[1].v);
00252                 glVertex3fv(&node->nodepolylist[loop].Vertex[1].x);
00253                 glTexCoord2f(node->nodepolylist[loop].Vertex[2].u, node->nodepolylist[loop].Vertex[2].v);
00254                 glVertex3fv(&node->nodepolylist[loop].Vertex[2].x);
00255             glEnd();
00256             glPopMatrix();
00257             glMatrixMode(GL_MODELVIEW);
00258 
00259             glEnable(GL_BLEND);
00260             glBlendFunc(GL_DST_COLOR, GL_SRC_COLOR);
00261 
00262             glBindTexture(GL_TEXTURE_2D, node->nodelightmaplist[loop].Texture.TexID);
00263             glBegin(GL_TRIANGLES);
00264                 glNormal3fv(&node->nodepolylist[loop].Vertex[0].nx);
00265                 glTexCoord2f(node->nodelightmaplist[loop].vertex_u[0], node->nodelightmaplist[loop].vertex_v[0]);
00266                 glVertex3fv(&node->nodepolylist[loop].Vertex[0].x);
00267                 glTexCoord2f(node->nodelightmaplist[loop].vertex_u[1], node->nodelightmaplist[loop].vertex_v[1]);
00268                 glVertex3fv(&node->nodepolylist[loop].Vertex[1].x);
00269                 glTexCoord2f(node->nodelightmaplist[loop].vertex_u[2], node->nodelightmaplist[loop].vertex_v[2]);
00270                 glVertex3fv(&node->nodepolylist[loop].Vertex[2].x);
00271             glEnd();
00272             glDisable(GL_BLEND);
00273         }
00274 
00275         if (showportals)
00276         {
00277             // Draw the leaf portals
00278             glDisable(GL_TEXTURE_2D);
00279             glDisable(GL_LIGHTING);
00280             glEnable(GL_BLEND);
00281             glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
00282             glEnable(GL_ALPHA_TEST);
00283             glAlphaFunc(GL_GREATER, 0);
00284             glColor4f(1.0, 1.0, 0.0, 0.2);
00285 
00286             if (currentleaf == node->nodeid)
00287             {
00288                 for (int loop = 1; loop <= node->numportals; loop++)
00289                 {
00290                     PORTAL* tempportal = node->portallist.Get(loop);
00291                     glBegin(GL_POLYGON);
00292                         glNormal3fv(&tempportal->Vertex[0].nx);
00293                         for (int innerloop = 0; innerloop < tempportal->numVertices; innerloop++)
00294                             glVertex3f(tempportal->Vertex[innerloop].x, tempportal->Vertex[innerloop].y, tempportal->Vertex[innerloop].z);
00295                     glEnd();
00296                 }
00297             }
00298             glDisable(GL_BLEND);
00299             glDisable(GL_ALPHA_TEST);
00300             glEnable(GL_TEXTURE_2D);
00301             glEnable(GL_LIGHTING);
00302         }
00303     }
00304     return 1;
00305 }

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

Definition at line 58 of file bsp.cpp.

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

Referenced by BuildBSP().

00059 {
00060     int count = 0, result, absdifference = 1000000000, bestplane = 0, front, back, potentialplane, polytoclassify;
00061     VECTOR temp;
00062 
00063     // Loop through all the polygons and find the best splitting plane
00064     for(potentialplane = 0; potentialplane < numpolys; potentialplane++)
00065     {
00066         front = back = 0;
00067         for (polytoclassify = 0; polytoclassify < numpolys; polytoclassify++)
00068         {
00069             result = SplitPolygon(nodepolylist[polytoclassify], nodepolylist[potentialplane], NULL);
00070             switch (result)
00071             {
00072                 case Front:
00073                     front++;
00074                 break;
00075 
00076                 case Back:
00077                     back++;
00078                 break;
00079 
00080                 case TwoFrontOneBack:
00081                     front += 2;
00082                     back++;
00083                 break;
00084 
00085                 case OneFrontTwoBack:
00086                     front++;
00087                     back += 2;
00088                 break;
00089 
00090                 case OneFrontOneBack:
00091                     front++;
00092                     back++;
00093                 break;
00094             }
00095         }
00096         if (abs(front - back) < absdifference)
00097         {
00098             absdifference = abs(front - back);
00099             bestplane = potentialplane;
00100             *bestfront = front;
00101             *bestback = back;
00102         }
00103         if (front == 0 || back == 0)
00104             count++;
00105     }
00106     if (count == numpolys)
00107         return -1;
00108     else
00109         return bestplane;
00110 }


Variable Documentation

CAMERA* camera
 

Definition at line 14 of file bsp.cpp.

int currentCamera
 

Definition at line 15 of file bsp.cpp.

Referenced by RenderBSP().

int currentleaf
 

Definition at line 23 of file bsp.cpp.

Referenced by RenderBSP().

LinkedList<ListNode> LeafList
 

Definition at line 16 of file bsp.cpp.

ListNode* listnode
 

Definition at line 18 of file bsp.cpp.

int numcurrentportals
 

Definition at line 19 of file bsp.cpp.

Referenced by FindCurrentLeaf().

int numleaves
 

Definition at line 20 of file bsp.cpp.

Referenced by BuildBSP().

int numpartitions
 

Definition at line 21 of file bsp.cpp.

Referenced by BuildBSP().

LinkedList<ListNode> PartitionList
 

Definition at line 17 of file bsp.cpp.

int showportals
 

Definition at line 22 of file bsp.cpp.


Generated on Fri Dec 23 05:20:19 2005 for Portals by doxygen1.2.15