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

portal.cpp

Go to the documentation of this file.
00001 #include <windows.h>
00002 #include "portal.h"
00003 #include "locmath.h"
00004 #include "listnode.h"
00005 #include "collision.h"
00006 #include "general.h"
00007 #include "bsp.h"
00008 #include "tll.h"
00009 #include "plane.h"
00010 #include "mmgr.h"
00011 
00012 extern float Min_X, Min_Y, Min_Z, Max_X, Max_Y, Max_Z; // The bounding box variables
00013 extern int numpartitions;
00014 extern BSP_node* listnode;
00015 extern LinkedList<BSP_node> LeafList;
00016 extern LinkedList<BSP_node> PartitionList;
00017 extern LinkedList<PORTAL> PortalList;
00018 extern int numportals;
00019 extern PORTAL* portal;
00020 extern BSP_node* root;
00021 
00022 PORTAL::PORTAL()
00023 {
00024 }
00025 
00026 PORTAL::~PORTAL()
00027 {
00028 }
00029 
00030 int PORTAL::Compare(const PORTAL& Portal)
00031 {
00032     if (linkPosition < Portal.linkPosition)
00033             return smaller;
00034       if (linkPosition > Portal.linkPosition)
00035             return bigger;
00036       else
00037             return same;
00038 }
00039 
00040 VECTOR PORTAL::GetNormal()
00041 {
00042         VECTOR temp;
00043         VECTOR u;
00044         VECTOR v;
00045           u = Vertex[1].coords - Vertex[0].coords;
00046           v = Vertex[2].coords - Vertex[0].coords;
00047           temp.x = (u.y*v.z)-(v.y*u.z);
00048           temp.y = (u.z*v.x)-(v.z*u.x);
00049           temp.z = (u.x*v.y)-(v.x*u.y);
00050         return temp;
00051 }
00052 
00053 void PORTAL::SetNormal()
00054 {
00055         VECTOR u;
00056         VECTOR v;
00057           u = Vertex[1].coords - Vertex[0].coords;
00058           v = Vertex[2].coords - Vertex[0].coords;
00059           Vertex[0].normal.x = (u.y*v.z)-(v.y*u.z);
00060           Vertex[0].normal.y = (u.z*v.x)-(v.z*u.x);
00061           Vertex[0].normal.z = (u.x*v.y)-(v.x*u.y);
00062         Vertex[1].normal = Vertex[0].normal;
00063           Vertex[2].normal = Vertex[0].normal;
00064 }
00065 
00066 PORTAL* CopyPortal(PORTAL* portal)
00067 {
00068     PORTAL* tempportal = new PORTAL;
00069     *tempportal = *portal;
00070     tempportal->Vertex = new VERTEX[portal->numVertices];
00071     for (int loop = 0; loop < portal->numVertices; loop++)
00072         tempportal->Vertex[loop] = portal->Vertex[loop];
00073     return tempportal;
00074 }
00075 
00076 void CreateLargePortal(POLYGON splittingPolygon, PORTAL* largePortal)
00077 {
00078 // Make large portal using planar mapping
00079     largePortal->numVertices = 4;
00080     largePortal->Vertex = new VERTEX[4];
00081     // find the primary axis plane
00082     int flag = 0;
00083     VECTOR poly_normal = splittingPolygon.GetNormal();
00084     poly_normal.Normalize();
00085 
00086     if (fabs(poly_normal.x) > fabs(poly_normal.y) && fabs(poly_normal.x) > fabs(poly_normal.z))
00087     {
00088         flag = 1;
00089         largePortal->Vertex[0].coords.y = Min_Y;
00090         largePortal->Vertex[0].coords.z = Max_Z;
00091         largePortal->Vertex[1].coords.y = Min_Y;
00092         largePortal->Vertex[1].coords.z = Min_Z;
00093         largePortal->Vertex[2].coords.y = Max_Y;
00094         largePortal->Vertex[2].coords.z = Min_Z;
00095         largePortal->Vertex[3].coords.y = Max_Y;
00096         largePortal->Vertex[3].coords.z = Max_Z;
00097     }
00098     else if (fabs(poly_normal.y) > fabs(poly_normal.x) && fabs(poly_normal.y) > fabs(poly_normal.z))
00099     {
00100         flag = 2;
00101         largePortal->Vertex[0].coords.x = Min_X;
00102         largePortal->Vertex[0].coords.z = Max_Z;
00103         largePortal->Vertex[1].coords.x = Max_X;
00104         largePortal->Vertex[1].coords.z = Max_Z;
00105         largePortal->Vertex[2].coords.x = Max_X;
00106         largePortal->Vertex[2].coords.z = Min_Z;
00107         largePortal->Vertex[3].coords.x = Min_X;
00108         largePortal->Vertex[3].coords.z = Min_Z;
00109     }
00110     else
00111     {
00112         flag = 3;
00113         largePortal->Vertex[0].coords.x = Min_X;
00114         largePortal->Vertex[0].coords.y = Min_Y;
00115         largePortal->Vertex[1].coords.x = Max_X;
00116         largePortal->Vertex[1].coords.y = Min_Y;
00117         largePortal->Vertex[2].coords.x = Max_X;
00118         largePortal->Vertex[2].coords.y = Max_Y;
00119         largePortal->Vertex[3].coords.x = Min_X;
00120         largePortal->Vertex[3].coords.y = Max_Y;
00121     }
00122 
00123     float X, Y, Z;
00124     float Distance = - (poly_normal.x * splittingPolygon.Vertex[0].coords.x + poly_normal.y * splittingPolygon.Vertex[0].coords.y + poly_normal.z * splittingPolygon.Vertex[0].coords.z);
00125     switch (flag)
00126     {
00127         case 1: //YZ Plane
00128             X = - (poly_normal.y * Min_Y + poly_normal.z * Max_Z + Distance ) / poly_normal.x;
00129             largePortal->Vertex[0].coords.x = X;
00130             X = - (poly_normal.y * Min_Y + poly_normal.z * Min_Z + Distance ) / poly_normal.x;
00131             largePortal->Vertex[1].coords.x = X;
00132             X = - (poly_normal.y * Max_Y + poly_normal.z * Min_Z + Distance ) / poly_normal.x;
00133             largePortal->Vertex[2].coords.x = X;
00134             X = - (poly_normal.y * Max_Y + poly_normal.z * Max_Z + Distance ) / poly_normal.x;
00135             largePortal->Vertex[3].coords.x = X;
00136         break;
00137         case 2: //XZ Plane
00138             Y = - (poly_normal.x * Min_X + poly_normal.z * Max_Z + Distance ) / poly_normal.y;
00139             largePortal->Vertex[0].coords.y = Y;
00140             Y = - (poly_normal.x * Max_X + poly_normal.z * Max_Z + Distance ) / poly_normal.y;
00141             largePortal->Vertex[1].coords.y = Y;
00142             Y = - (poly_normal.x * Max_X + poly_normal.z * Min_Z + Distance ) / poly_normal.y;
00143             largePortal->Vertex[2].coords.y = Y;
00144             Y = - (poly_normal.x * Min_X + poly_normal.z * Min_Z + Distance ) / poly_normal.y;
00145             largePortal->Vertex[3].coords.y = Y;
00146         break;
00147         case 3: //XY Plane
00148             Z = - (poly_normal.x * Min_X + poly_normal.y * Min_Y + Distance ) / poly_normal.z;
00149             largePortal->Vertex[0].coords.z = Z;
00150             Z = - (poly_normal.x * Max_X + poly_normal.y * Min_Y + Distance ) / poly_normal.z;
00151             largePortal->Vertex[1].coords.z = Z;
00152             Z = - (poly_normal.x * Max_X + poly_normal.y * Max_Y + Distance ) / poly_normal.z;
00153             largePortal->Vertex[2].coords.z = Z;
00154             Z = - (poly_normal.x * Min_X + poly_normal.y * Max_Y + Distance ) / poly_normal.z;
00155             largePortal->Vertex[3].coords.z = Z;
00156         break;
00157     }
00158     largePortal->SetNormal();
00159 }
00160 
00161 int SplitPortal(PORTAL* portalToSplit, POLYGON planePolygon, PORTAL* front, PORTAL* back)
00162 {
00163     const int MaxVerts = 100;
00164     int numVerts = portalToSplit->numVertices;
00165     int count = 0, out_c = 0, in_c = 0, sideA, sideB, loop;
00166     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00167     VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
00168 
00169     // get a point on the plane
00170     pointOnPlane = planePolygon.Vertex[0].coords;
00171 
00172     // get the splitting planes normal
00173     edge1 = planePolygon.Vertex[1].coords - planePolygon.Vertex[0].coords;
00174     edge2 = planePolygon.Vertex[2].coords - planePolygon.Vertex[0].coords;
00175     planeNormal = CrossVector(edge1, edge2);
00176 
00177     // get the normal of the portal to split
00178     edge1 = portalToSplit->Vertex[1].coords - portalToSplit->Vertex[0].coords;
00179     edge2 = portalToSplit->Vertex[2].coords - portalToSplit->Vertex[0].coords;
00180     polysNormal = CrossVector(edge1, edge2);
00181 
00182     // check if the portal lies on the plane
00183     for (int loop = 0; loop < numVerts; loop++)
00184     {
00185         temp = portalToSplit->Vertex[loop].coords;
00186         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00187             count++;
00188         else
00189             break;
00190     }
00191     if (count == numVerts)
00192     {
00193         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00194             return Front;
00195         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00196             return Back;
00197     }
00198 
00199     // find if all of the points are infront of or behind the plane
00200     int frontcount = 0, backcount = 0;
00201     for (int loop = 0; loop < numVerts; loop++)
00202     {
00203         temp = portalToSplit->Vertex[loop].coords;
00204         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00205         {
00206             frontcount++;
00207             backcount++;
00208         }
00209         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00210             frontcount++;
00211         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00212             backcount++;
00213     }
00214     if (frontcount == numVerts)
00215             return Front;
00216     if (backcount == numVerts)
00217             return Back;
00218 
00219     // try to split the portal
00220     ptA = portalToSplit->Vertex[numVerts - 1];
00221     temp = ptA.coords;
00222     sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00223     for (int i = -1; ++i < numVerts;)
00224     {
00225         ptB = portalToSplit->Vertex[i];
00226         temp = ptB.coords;
00227         sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00228         if (sideB > 0)
00229         {
00230             if (sideA < 0)
00231             {
00232                 // find intersection
00233                 edge1 = ptA.coords;
00234                 edge2 = ptB.coords;
00235 
00236                 temp = GetEdgeIntersection(edge1, edge2, planePolygon);
00237                 intersection.coords = temp;
00238 
00239                 outpts[out_c++] = inpts[in_c++] = intersection;
00240             }
00241             inpts[in_c++] = ptB;
00242         }
00243         else if (sideB < 0)
00244         {
00245             if (sideA > 0)
00246             {
00247                 // find intersection
00248                 edge1 = ptA.coords;
00249                 edge2 = ptB.coords;
00250 
00251                 temp = GetEdgeIntersection(edge1, edge2, planePolygon);
00252                 intersection.coords = temp;
00253 
00254                 outpts[out_c++] = inpts[in_c++] = intersection;
00255             }
00256             outpts[out_c++] = ptB;
00257         }
00258         else
00259             outpts[out_c++] = inpts[in_c++] = ptB;
00260         ptA = ptB;
00261         sideA = sideB;
00262     }
00263 
00264     if (out_c == 0 || in_c == 0)
00265     {
00266         int side;
00267 
00268         for (int loop = 0; loop < numVerts; loop++)
00269         {
00270             temp = portalToSplit->Vertex[loop].coords;
00271             side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00272             if (side == 1)
00273                 return Front;
00274             else if (side == -1)
00275                 return Back;
00276         }
00277     }
00278     else
00279     {
00280         front->Vertex = new VERTEX[in_c];
00281         back->Vertex = new VERTEX[out_c];
00282         front->numVertices = in_c;
00283         back->numVertices = out_c;
00284 
00285         for (loop = 0; loop < in_c; loop++)
00286             front->Vertex[loop] = inpts[loop];
00287         for (loop = 0; loop < out_c; loop++)
00288             back->Vertex[loop] = outpts[loop];
00289         return PortalWasSplit;
00290     }
00291     return 0;
00292 }
00293 
00294 int SplitPortal(PORTAL* portalToSplit, PLANE plane, VECTOR pointOnPlane, PORTAL* front, PORTAL* back)
00295 {
00296     const int MaxVerts = 100;
00297     int numVerts = portalToSplit->numVertices;
00298     int count = 0, out_c = 0, in_c = 0, sideA, sideB, loop;
00299     VECTOR planeNormal, polysNormal, edge1, edge2, temp;
00300     VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
00301 
00302     // get the splitting planes normal
00303     planeNormal = plane.normal;
00304 
00305     // get the normal of the portal to split
00306     edge1 = portalToSplit->Vertex[1].coords - portalToSplit->Vertex[0].coords;
00307     edge2 = portalToSplit->Vertex[2].coords - portalToSplit->Vertex[0].coords;
00308     polysNormal = CrossVector(edge1, edge2);
00309 
00310     // check if the portal lies on the plane
00311     for (int loop = 0; loop < numVerts; loop++)
00312     {
00313         temp = portalToSplit->Vertex[loop].coords;
00314         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00315             count++;
00316         else
00317             break;
00318     }
00319     if (count == numVerts)
00320     {
00321         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00322             return Front;
00323         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00324             return Back;
00325     }
00326 
00327     // find if all of the points are infront of or behind the plane
00328     int frontcount = 0, backcount = 0;
00329     for (int loop = 0; loop < numVerts; loop++)
00330     {
00331         temp = portalToSplit->Vertex[loop].coords;
00332         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00333         {
00334             frontcount++;
00335             backcount++;
00336         }
00337         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00338             frontcount++;
00339         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00340             backcount++;
00341     }
00342     if (frontcount == numVerts)
00343             return Front;
00344     if (backcount == numVerts)
00345             return Back;
00346 
00347     // try to split the portal
00348     ptA = portalToSplit->Vertex[numVerts - 1];
00349     temp = ptA.coords;
00350     sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00351     for (int i = -1; ++i < numVerts;)
00352     {
00353         ptB = portalToSplit->Vertex[i];
00354         temp = ptB.coords;
00355         sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00356         if (sideB > 0)
00357         {
00358             if (sideA < 0)
00359             {
00360                 // find intersection
00361                 edge1 = ptA.coords;
00362                 edge2 = ptB.coords;
00363 
00364                 temp = GetEdgeIntersection(edge1, edge2, plane, pointOnPlane);
00365                 intersection.coords = temp;
00366 
00367                 outpts[out_c++] = inpts[in_c++] = intersection;
00368             }
00369             inpts[in_c++] = ptB;
00370         }
00371         else if (sideB < 0)
00372         {
00373             if (sideA > 0)
00374             {
00375                 // find intersection
00376                 edge1 = ptA.coords;
00377                 edge2 = ptB.coords;
00378 
00379                 temp = GetEdgeIntersection(edge1, edge2, plane, pointOnPlane);
00380                 intersection.coords = temp;
00381 
00382                 outpts[out_c++] = inpts[in_c++] = intersection;
00383             }
00384             outpts[out_c++] = ptB;
00385         }
00386         else
00387             outpts[out_c++] = inpts[in_c++] = ptB;
00388         ptA = ptB;
00389         sideA = sideB;
00390     }
00391 
00392     if (out_c == 0 || in_c == 0)
00393     {
00394         int side;
00395 
00396         for (int loop = 0; loop < numVerts; loop++)
00397         {
00398             temp = portalToSplit->Vertex[loop].coords;
00399             side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00400             if (side == 1)
00401                 return Front;
00402             else if (side == -1)
00403                 return Back;
00404         }
00405     }
00406     else
00407     {
00408         front->Vertex = new VERTEX[in_c];
00409         back->Vertex = new VERTEX[out_c];
00410         front->numVertices = in_c;
00411         back->numVertices = out_c;
00412 
00413         for (loop = 0; loop < in_c; loop++)
00414             front->Vertex[loop] = inpts[loop];
00415         for (loop = 0; loop < out_c; loop++)
00416             back->Vertex[loop] = outpts[loop];
00417         return PortalWasSplit;
00418     }
00419     return 0;
00420 }
00421 
00422 void MakePortalList()
00423 {
00424     // Create the large portals
00425     for (int loop = 1; loop <= PartitionList.numObjects; loop++)
00426     {
00427         listnode = PartitionList.Get(loop);
00428         portal = new PORTAL;
00429         portal->linkPosition = loop;
00430         portal->PartitionNodeId = loop;
00431         CreateLargePortal(listnode->partition, portal);
00432         PortalList.Insert(portal);
00433     }
00434 
00435     // Split the large portals into potential portals
00436     PortalList.numObjects = PartitionList.numObjects;
00437     int result, portalToSplit;
00438     PORTAL* frontportal;
00439     PORTAL* backportal;
00440     for (int partition = 1; partition <= numpartitions; partition++)
00441     {
00442         listnode = PartitionList.Get(partition);
00443         portalToSplit = PortalList.numObjects;
00444         while (portalToSplit > 0)
00445         {
00446             frontportal = new PORTAL;
00447             backportal = new PORTAL;
00448 
00449             portal = PortalList.Get(portalToSplit);
00450             result = SplitPortal(portal, listnode->partition, frontportal, backportal);
00451 
00452             if (result == PortalWasSplit)
00453             {
00454                 frontportal->linkPosition = ++PortalList.numObjects;
00455                 frontportal->PartitionNodeId = portal->PartitionNodeId;
00456                 PortalList.Insert(frontportal);
00457                 backportal->linkPosition = ++PortalList.numObjects;
00458                 backportal->PartitionNodeId = portal->PartitionNodeId;
00459                 PortalList.Insert(backportal);
00460 
00461                 delete[] portal->Vertex;
00462                 PortalList.Delete(portalToSplit);
00463                 PortalList.numObjects--;
00464             }
00465             else
00466             {
00467                 delete frontportal;
00468                 delete backportal;
00469             }
00470             portalToSplit--;
00471         }
00472     }
00473     // Loop through the portals and assign a unique id
00474     for (int loop = 1; loop <= PortalList.numObjects; loop++)
00475     {
00476         portal = PortalList.Get(loop);
00477         portal->PortalId = loop;
00478     }
00479 }
00480 
00481 int ClassifyPortal(PORTAL* portal, POLYGON planePolygon)
00482 {
00483     int numVerts = portal->numVertices;
00484     int count = 0;
00485     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00486 
00487     // get a point on the plane
00488     pointOnPlane = planePolygon.Vertex[0].coords;
00489 
00490     // get the planes normal
00491     edge1 = planePolygon.Vertex[1].coords - planePolygon.Vertex[0].coords;
00492     edge2 = planePolygon.Vertex[2].coords - planePolygon.Vertex[0].coords;
00493     planeNormal = CrossVector(edge1, edge2);
00494 
00495     // get the normal of the portal
00496     edge1 = portal->Vertex[1].coords - portal->Vertex[0].coords;
00497     edge2 = portal->Vertex[2].coords - portal->Vertex[0].coords;
00498     polysNormal = CrossVector(edge1, edge2);
00499 
00500     // check if the portal lies on the plane
00501     for (int loop = 0; loop < numVerts; loop++)
00502     {
00503         temp = portal->Vertex[loop].coords;
00504         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00505             count++;
00506         else
00507             break;
00508     }
00509     if (count == numVerts)
00510             return OnPartition;
00511 
00512     // find if all of the points are infront of or behind the plane
00513     int result, frontcount = 0, backcount = 0;
00514     for (int loop = 0; loop < numVerts; loop++)
00515     {
00516         temp = portal->Vertex[loop].coords;
00517         result = ClassifyPoint(temp, pointOnPlane, planeNormal);
00518         if (result == 0)
00519         {
00520             frontcount++;
00521             backcount++;
00522         }
00523         else
00524             if (result == 1)
00525                 frontcount++;
00526         else
00527             if (result == -1)
00528                 backcount++;
00529     }
00530     if (frontcount == numVerts)
00531             return Front;
00532     if (backcount == numVerts)
00533             return Back;
00534 
00535     return 0;
00536 }
00537 
00538 int ClassifyInvertedPortal(PORTAL* portal, POLYGON planePolygon)
00539 {
00540     int numVerts = portal->numVertices;
00541     int count = 0;
00542     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00543 
00544     // get a point on the plane
00545     pointOnPlane = planePolygon.Vertex[0].coords;
00546 
00547     // get the planes normal
00548     edge1 = planePolygon.Vertex[1].coords - planePolygon.Vertex[0].coords;
00549     edge2 = planePolygon.Vertex[2].coords - planePolygon.Vertex[0].coords;
00550     planeNormal = CrossVector(edge1, edge2);
00551 
00552     // get the normal of the portal
00553     edge1 = portal->Vertex[1].coords - portal->Vertex[0].coords;
00554     edge2 = portal->Vertex[2].coords - portal->Vertex[0].coords;
00555     polysNormal = CrossVector(edge1, edge2);
00556     polysNormal.x *= -1;
00557     polysNormal.y *= -1;
00558     polysNormal.z *= -1;
00559 
00560     // check if the portal lies on the plane
00561     for (int loop = 0; loop < numVerts; loop++)
00562     {
00563         temp = portal->Vertex[loop].coords;
00564         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00565             count++;
00566         else
00567             break;
00568     }
00569     if (count == numVerts)
00570     {
00571         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00572             return Front;
00573         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00574             return Back;
00575     }
00576 
00577     // find if all of the points are infront of or behind the plane
00578     int result, frontcount = 0, backcount = 0;
00579     for (int loop = 0; loop < numVerts; loop++)
00580     {
00581         temp = portal->Vertex[loop].coords;
00582         result = ClassifyPoint(temp, pointOnPlane, planeNormal);
00583         if (result == 0)
00584         {
00585             frontcount++;
00586             backcount++;
00587         }
00588         else
00589             if (result == 1)
00590                 frontcount++;
00591         else
00592             if (result == -1)
00593                 backcount++;
00594     }
00595     if (frontcount == numVerts)
00596             return Front;
00597     if (backcount == numVerts)
00598             return Back;
00599 
00600     return 0;
00601 }
00602 
00603 void InvertPortal(PORTAL* portal)
00604 {
00605     PORTAL* tempportal = CopyPortal(portal);
00606     int numverts = portal->numVertices;
00607     for (int loop = 0; loop < numverts; loop++)
00608         portal->Vertex[loop] = tempportal->Vertex[(numverts - 1) - loop];
00609     return;
00610 }
00611 
00612 void InvertPortals(BSP_node* node)
00613 {
00614     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00615     int flag;
00616     for (int loop = 1; loop <= node->numportals; loop++)
00617     {
00618         PORTAL* tempportal = node->portallist.Get(loop);
00619         // get a point on the plane
00620         pointOnPlane = tempportal->Vertex[0].coords;
00621 
00622         // get the normal of the portals plane
00623         edge1 = tempportal->Vertex[1].coords - tempportal->Vertex[0].coords;
00624         edge2 = tempportal->Vertex[2].coords - tempportal->Vertex[0].coords;
00625         planeNormal = CrossVector(edge1, edge2);
00626 
00627         flag = 0;
00628         for (int polygon = 0; polygon < node->numpolys; polygon++)
00629         {
00630             for (int vert = 0; vert < 3; vert++)
00631             {
00632                 temp = node->nodepolylist[polygon].Vertex[vert].coords;
00633 
00634                 flag = ClassifyPoint(temp, pointOnPlane, planeNormal);
00635                 if (flag == -1)
00636                 {
00637                     InvertPortal(tempportal);
00638                 }
00639                 if (flag == 1 || flag == -1)
00640                 {
00641                     if (tempportal->frontleaf->nodeid != node->nodeid)
00642                     {
00643                         BSP_node* tempnode = tempportal->backleaf;
00644                         tempportal->backleaf = tempportal->frontleaf;
00645                         tempportal->frontleaf = tempnode;
00646                     }
00647                     break;
00648                 }
00649             }
00650             if (flag == 1 || flag == -1)
00651                 break;
00652         }
00653     }
00654 }
00655 
00656 void AddPortal(PORTAL* thisportal, BSP_node* node)
00657 {
00658     if (node->leaf == true)
00659     {
00660         node->numportals++;
00661         thisportal->linkPosition = node->numportals;
00662         node->portallist.Insert(thisportal);
00663         return;
00664     }
00665 
00666     int side = ClassifyPortal(thisportal, node->partition);
00667     if (side == Front)
00668     {
00669         AddPortal(thisportal, node->frontnode);
00670     }
00671     if (side == Back)
00672     {
00673         AddPortal(thisportal, node->backnode);
00674     }
00675     if (side == OnPartition)
00676     {
00677         AddPortal(thisportal, node->frontnode);
00678         PORTAL* tempportal = CopyPortal(thisportal);
00679         AddPortal(tempportal, node->backnode);
00680     }
00681     return;
00682 }
00683 
00684 void AddPortalsToLeaves(BSP_node* node)
00685 {
00686     for (int loop = 1; loop <= PortalList.numObjects; loop++)
00687     {
00688         PORTAL* tempportal = CopyPortal(PortalList.Get(loop));
00689         AddPortal(tempportal, node);
00690     }
00691 }
00692 
00693 int ClipPortalToFrontLeaf(PORTAL* portal)
00694 {
00695     int result, returnvalue = 0;
00696     for (int polygon = 0; polygon < portal->frontleaf->numpolys; polygon++)
00697     {
00698         PORTAL* front = new PORTAL;
00699         PORTAL* back = new PORTAL;
00700         result = SplitPortal(portal, portal->frontleaf->nodepolylist[polygon], front, back);
00701 
00702         if (result == PortalWasSplit)
00703         {
00704             returnvalue = PortalWasSplit;
00705             delete[] back->Vertex;
00706             delete back;
00707             delete[] portal->Vertex;
00708             portal->numVertices = front->numVertices;
00709             portal->Vertex = front->Vertex;
00710             delete front;
00711         }
00712 
00713         else
00714         {
00715             delete back;
00716             delete front;
00717         }
00718     }
00719     return returnvalue;
00720 }
00721 
00722 int ClipPortalToBackLeaf(PORTAL* portal)
00723 {
00724     int result, returnvalue = 0;
00725     for (int polygon = 0; polygon < portal->backleaf->numpolys; polygon++)
00726     {
00727         PORTAL* front = new PORTAL;
00728         PORTAL* back = new PORTAL;
00729         result = SplitPortal(portal, portal->backleaf->nodepolylist[polygon], front, back);
00730 
00731         if (result == PortalWasSplit)
00732         {
00733             returnvalue = PortalWasSplit;
00734             delete[] back->Vertex;
00735             delete back;
00736             delete[] portal->Vertex;
00737             portal->numVertices = front->numVertices;
00738             portal->Vertex = front->Vertex;
00739             delete front;
00740         }
00741         else
00742         {
00743             delete back;
00744             delete front;
00745         }
00746     }
00747     return returnvalue;
00748 }
00749 
00750 void CheckForSinglePortals(BSP_node* node, BSP_node* originalnode, PORTAL* portal, int* flag)
00751 {
00752     PORTAL* tempportal;
00753     if (node->leaf == true)
00754     {
00755         if (node->nodeid != originalnode->nodeid)
00756         {
00757             for (int portalnum = node->numportals; portalnum > 0; portalnum--)
00758             {
00759                 tempportal = node->portallist.Get(portalnum);
00760                 if (tempportal->PortalId == portal->PortalId)
00761                 {
00762                     portal->frontleaf = originalnode;
00763                     portal->backleaf = node;
00764                     *flag += 1;
00765                 }
00766             }
00767         }
00768         return;
00769     }
00770     else
00771     {
00772         CheckForSinglePortals(node->frontnode, originalnode, portal, flag);
00773         CheckForSinglePortals(node->backnode, originalnode, portal, flag);
00774         return;
00775     }
00776 }
00777 
00778 int RemoveExtraPortals(PORTAL* portal)
00779 {
00780     int result, count = 0;
00781     POLYGON temppoly;
00782     BSP_node* tempnode = portal->backleaf;
00783     for (int loop = 0; loop < tempnode->numpolys; loop++)
00784     {
00785         temppoly = tempnode->nodepolylist[loop];
00786         result = ClassifyInvertedPortal(portal, temppoly);
00787         if (result == Front)
00788             count++;
00789     }
00790     if (count != portal->backleaf->numpolys)
00791         return true;
00792     else
00793         return false;
00794 }
00795 
00796 void FindTruePortals(BSP_node* node)
00797 {
00798     int flag;
00799     if (node->leaf == true)
00800     {
00801         for (int portalnumber = node->numportals; portalnumber > 0; portalnumber--)
00802         {
00803             flag = 0;
00804             PORTAL* tempportal = node->portallist.Get(portalnumber);
00805             CheckForSinglePortals(root, node, tempportal, &flag);
00806             if (flag == 0)
00807             {
00808                 delete[] tempportal->Vertex;
00809                 node->portallist.Delete(portalnumber);
00810                 node->numportals--;
00811             }
00812             else
00813             {
00814                 ClipPortalToFrontLeaf(tempportal);
00815                 ClipPortalToBackLeaf(tempportal);
00816             }
00817         }
00818 
00819         InvertPortals(node);    // also inverts the front and back leaf pointers if necessary
00820 
00821         for (int portalnumber = node->numportals; portalnumber > 0; portalnumber--)
00822         {
00823             PORTAL* tempportal = node->portallist.Get(portalnumber);
00824             flag = RemoveExtraPortals(tempportal);
00825             if (flag == true)
00826             {
00827                 delete[] tempportal->Vertex;
00828                 node->portallist.Delete(portalnumber);
00829                 node->numportals--;
00830             }
00831         }
00832         return;
00833     }
00834     else
00835     {
00836         FindTruePortals(node->frontnode);
00837         FindTruePortals(node->backnode);
00838         return;
00839     }
00840 }

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