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 ListNode* listnode;
00015 extern LinkedList<ListNode> LeafList;
00016 extern LinkedList<ListNode> 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         float ux;
00044         float uy;
00045         float uz;
00046         float vx;
00047         float vy;
00048         float vz;
00049           ux = Vertex[1].x - Vertex[0].x;
00050           uy = Vertex[1].y - Vertex[0].y;
00051           uz = Vertex[1].z - Vertex[0].z;
00052           vx = Vertex[2].x - Vertex[0].x;
00053           vy = Vertex[2].y - Vertex[0].y;
00054           vz = Vertex[2].z - Vertex[0].z;
00055           temp.x = (uy*vz)-(vy*uz);
00056           temp.y = (uz*vx)-(vz*ux);
00057           temp.z = (ux*vy)-(vx*uy);
00058         return temp;
00059 }
00060 
00061 void PORTAL::SetNormal()
00062 {
00063         float ux;
00064         float uy;
00065         float uz;
00066         float vx;
00067         float vy;
00068         float vz;
00069           ux = Vertex[1].x - Vertex[0].x;
00070           uy = Vertex[1].y - Vertex[0].y;
00071           uz = Vertex[1].z - Vertex[0].z;
00072           vx = Vertex[2].x - Vertex[0].x;
00073           vy = Vertex[2].y - Vertex[0].y;
00074           vz = Vertex[2].z - Vertex[0].z;
00075           Vertex[0].nx = (uy*vz)-(vy*uz);
00076           Vertex[0].ny = (uz*vx)-(vz*ux);
00077           Vertex[0].nz = (ux*vy)-(vx*uy);
00078         Vertex[1].nx = Vertex[0].nx;
00079           Vertex[1].ny = Vertex[0].ny;
00080           Vertex[1].nz = Vertex[0].nz;
00081           Vertex[2].nx = Vertex[0].nx;
00082           Vertex[2].ny = Vertex[0].ny;
00083           Vertex[2].nz = Vertex[0].nz;
00084 }
00085 
00086 PORTAL* CopyPortal(PORTAL* portal)
00087 {
00088     PORTAL* tempportal = new PORTAL;
00089     *tempportal = *portal;
00090     tempportal->Vertex = new VERTEX[portal->numVertices];
00091     for (int loop = 0; loop < portal->numVertices; loop++)
00092         tempportal->Vertex[loop] = portal->Vertex[loop];
00093     return tempportal;
00094 }
00095 
00096 void CreateLargePortal(POLYGON splittingPolygon, PORTAL* largePortal)
00097 {
00098 // Make large portal using planar mapping
00099     largePortal->numVertices = 4;
00100     largePortal->Vertex = new VERTEX[4];
00101     // find the primary axis plane
00102     int flag = 0;
00103     VECTOR poly_normal = splittingPolygon.GetNormal();
00104     poly_normal.Normalize();
00105 
00106     if (fabs(poly_normal.x) > fabs(poly_normal.y) && fabs(poly_normal.x) > fabs(poly_normal.z))
00107     {
00108         flag = 1;
00109         largePortal->Vertex[0].y = Min_Y;
00110         largePortal->Vertex[0].z = Max_Z;
00111         largePortal->Vertex[1].y = Min_Y;
00112         largePortal->Vertex[1].z = Min_Z;
00113         largePortal->Vertex[2].y = Max_Y;
00114         largePortal->Vertex[2].z = Min_Z;
00115         largePortal->Vertex[3].y = Max_Y;
00116         largePortal->Vertex[3].z = Max_Z;
00117     }
00118     else if (fabs(poly_normal.y) > fabs(poly_normal.x) && fabs(poly_normal.y) > fabs(poly_normal.z))
00119     {
00120         flag = 2;
00121         largePortal->Vertex[0].x = Min_X;
00122         largePortal->Vertex[0].z = Max_Z;
00123         largePortal->Vertex[1].x = Max_X;
00124         largePortal->Vertex[1].z = Max_Z;
00125         largePortal->Vertex[2].x = Max_X;
00126         largePortal->Vertex[2].z = Min_Z;
00127         largePortal->Vertex[3].x = Min_X;
00128         largePortal->Vertex[3].z = Min_Z;
00129     }
00130     else
00131     {
00132         flag = 3;
00133         largePortal->Vertex[0].x = Min_X;
00134         largePortal->Vertex[0].y = Min_Y;
00135         largePortal->Vertex[1].x = Max_X;
00136         largePortal->Vertex[1].y = Min_Y;
00137         largePortal->Vertex[2].x = Max_X;
00138         largePortal->Vertex[2].y = Max_Y;
00139         largePortal->Vertex[3].x = Min_X;
00140         largePortal->Vertex[3].y = Max_Y;
00141     }
00142 
00143     float X, Y, Z;
00144     float Distance = - (poly_normal.x * splittingPolygon.Vertex[0].x + poly_normal.y * splittingPolygon.Vertex[0].y + poly_normal.z * splittingPolygon.Vertex[0].z);
00145     switch (flag)
00146     {
00147         case 1: //YZ Plane
00148             X = - ( poly_normal.y * Min_Y + poly_normal.z * Max_Z + Distance ) / poly_normal.x;
00149             largePortal->Vertex[0].x = X;
00150             X = - ( poly_normal.y * Min_Y + poly_normal.z * Min_Z + Distance ) / poly_normal.x;
00151             largePortal->Vertex[1].x = X;
00152             X = - ( poly_normal.y * Max_Y + poly_normal.z * Min_Z + Distance ) / poly_normal.x;
00153             largePortal->Vertex[2].x = X;
00154             X = - ( poly_normal.y * Max_Y + poly_normal.z * Max_Z + Distance ) / poly_normal.x;
00155             largePortal->Vertex[3].x = X;
00156         break;
00157         case 2: //XZ Plane
00158             Y = - ( poly_normal.x * Min_X + poly_normal.z * Max_Z + Distance ) / poly_normal.y;
00159             largePortal->Vertex[0].y = Y;
00160             Y = - ( poly_normal.x * Max_X + poly_normal.z * Max_Z + Distance ) / poly_normal.y;
00161             largePortal->Vertex[1].y = Y;
00162             Y = - ( poly_normal.x * Max_X + poly_normal.z * Min_Z + Distance ) / poly_normal.y;
00163             largePortal->Vertex[2].y = Y;
00164             Y = - ( poly_normal.x * Min_X + poly_normal.z * Min_Z + Distance ) / poly_normal.y;
00165             largePortal->Vertex[3].y = Y;
00166         break;
00167         case 3: //XY Plane
00168             Z = - ( poly_normal.x * Min_X + poly_normal.y * Min_Y + Distance ) / poly_normal.z;
00169             largePortal->Vertex[0].z = Z;
00170             Z = - ( poly_normal.x * Max_X + poly_normal.y * Min_Y + Distance ) / poly_normal.z;
00171             largePortal->Vertex[1].z = Z;
00172             Z = - ( poly_normal.x * Max_X + poly_normal.y * Max_Y + Distance ) / poly_normal.z;
00173             largePortal->Vertex[2].z = Z;
00174             Z = - ( poly_normal.x * Min_X + poly_normal.y * Max_Y + Distance ) / poly_normal.z;
00175             largePortal->Vertex[3].z = Z;
00176         break;
00177     }
00178     largePortal->SetNormal();
00179 }
00180 
00181 int SplitPortal(PORTAL* portalToSplit, POLYGON planePolygon, PORTAL* front, PORTAL* back)
00182 {
00183     const int MaxVerts = 100;
00184     int numVerts = portalToSplit->numVertices;
00185     int count = 0, out_c = 0, in_c = 0, sideA, sideB, loop;
00186     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00187     VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
00188 
00189     // get a point on the plane
00190     pointOnPlane.x = planePolygon.Vertex[0].x;
00191     pointOnPlane.y = planePolygon.Vertex[0].y;
00192     pointOnPlane.z = planePolygon.Vertex[0].z;
00193 
00194     // get the splitting planes normal
00195     edge1.x = planePolygon.Vertex[1].x - planePolygon.Vertex[0].x;
00196     edge1.y = planePolygon.Vertex[1].y - planePolygon.Vertex[0].y;
00197     edge1.z = planePolygon.Vertex[1].z - planePolygon.Vertex[0].z;
00198     edge2.x = planePolygon.Vertex[2].x - planePolygon.Vertex[0].x;
00199     edge2.y = planePolygon.Vertex[2].y - planePolygon.Vertex[0].y;
00200     edge2.z = planePolygon.Vertex[2].z - planePolygon.Vertex[0].z;
00201     planeNormal = CrossVector(edge1, edge2);
00202 
00203     // get the normal of the portal to split
00204     edge1.x = portalToSplit->Vertex[1].x - portalToSplit->Vertex[0].x;
00205     edge1.y = portalToSplit->Vertex[1].y - portalToSplit->Vertex[0].y;
00206     edge1.z = portalToSplit->Vertex[1].z - portalToSplit->Vertex[0].z;
00207     edge2.x = portalToSplit->Vertex[2].x - portalToSplit->Vertex[0].x;
00208     edge2.y = portalToSplit->Vertex[2].y - portalToSplit->Vertex[0].y;
00209     edge2.z = portalToSplit->Vertex[2].z - portalToSplit->Vertex[0].z;
00210     polysNormal = CrossVector(edge1, edge2);
00211 
00212     // check if the portal lies on the plane
00213     for (int loop = 0; loop < numVerts; loop++)
00214     {
00215         temp.x = portalToSplit->Vertex[loop].x;
00216         temp.y = portalToSplit->Vertex[loop].y;
00217         temp.z = portalToSplit->Vertex[loop].z;
00218         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00219             count++;
00220         else
00221             break;
00222     }
00223     if (count == numVerts)
00224     {
00225         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00226             return Front;
00227         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00228             return Back;
00229     }
00230 
00231     // find if all of the points are infront of or behind the plane
00232     int frontcount = 0, backcount = 0;
00233     for (int loop = 0; loop < numVerts; loop++)
00234     {
00235         temp.x = portalToSplit->Vertex[loop].x;
00236         temp.y = portalToSplit->Vertex[loop].y;
00237         temp.z = portalToSplit->Vertex[loop].z;
00238         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00239         {
00240             frontcount++;
00241             backcount++;
00242         }
00243         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00244             frontcount++;
00245         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00246             backcount++;
00247     }
00248     if (frontcount == numVerts)
00249             return Front;
00250     if (backcount == numVerts)
00251             return Back;
00252 
00253     // try to split the portal
00254     ptA = portalToSplit->Vertex[numVerts - 1];
00255     temp.x = ptA.x;
00256     temp.y = ptA.y;
00257     temp.z = ptA.z;
00258     sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00259     for (int i = -1; ++i < numVerts;)
00260     {
00261         ptB = portalToSplit->Vertex[i];
00262         temp.x = ptB.x;
00263         temp.y = ptB.y;
00264         temp.z = ptB.z;
00265         sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00266         if (sideB > 0)
00267         {
00268             if (sideA < 0)
00269             {
00270                 // find intersection
00271                 edge1.x = ptA.x;
00272                 edge1.y = ptA.y;
00273                 edge1.z = ptA.z;
00274                 edge2.x = ptB.x;
00275                 edge2.y = ptB.y;
00276                 edge2.z = ptB.z;
00277 
00278                 temp = GetEdgeIntersection(edge1, edge2, planePolygon);
00279                 intersection.x = temp.x;
00280                 intersection.y = temp.y;
00281                 intersection.z = temp.z;
00282 
00283                 outpts[out_c++] = inpts[in_c++] = intersection;
00284             }
00285             inpts[in_c++] = ptB;
00286         }
00287         else if (sideB < 0)
00288         {
00289             if (sideA > 0)
00290             {
00291                 // find intersection
00292                 edge1.x = ptA.x;
00293                 edge1.y = ptA.y;
00294                 edge1.z = ptA.z;
00295                 edge2.x = ptB.x;
00296                 edge2.y = ptB.y;
00297                 edge2.z = ptB.z;
00298 
00299                 temp = GetEdgeIntersection(edge1, edge2, planePolygon);
00300                 intersection.x = temp.x;
00301                 intersection.y = temp.y;
00302                 intersection.z = temp.z;
00303 
00304                 outpts[out_c++] = inpts[in_c++] = intersection;
00305             }
00306             outpts[out_c++] = ptB;
00307         }
00308         else
00309             outpts[out_c++] = inpts[in_c++] = ptB;
00310         ptA = ptB;
00311         sideA = sideB;
00312     }
00313 
00314     if (out_c == 0 || in_c == 0)
00315     {
00316         int side;
00317 
00318         for (int loop = 0; loop < numVerts; loop++)
00319         {
00320             temp.x = portalToSplit->Vertex[loop].x;
00321             temp.y = portalToSplit->Vertex[loop].y;
00322             temp.z = portalToSplit->Vertex[loop].z;
00323             side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00324             if (side == 1)
00325                 return Front;
00326             else if (side == -1)
00327                 return Back;
00328         }
00329     }
00330     else
00331     {
00332         front->Vertex = new VERTEX[in_c];
00333         back->Vertex = new VERTEX[out_c];
00334         front->numVertices = in_c;
00335         back->numVertices = out_c;
00336 
00337         for (loop = 0; loop < in_c; loop++)
00338             front->Vertex[loop] = inpts[loop];
00339         for (loop = 0; loop < out_c; loop++)
00340             back->Vertex[loop] = outpts[loop];
00341         return PortalWasSplit;
00342     }
00343     return 0;
00344 }
00345 
00346 int SplitPortal(PORTAL* portalToSplit, PLANE plane, VECTOR pointOnPlane, PORTAL* front, PORTAL* back)
00347 {
00348     const int MaxVerts = 100;
00349     int numVerts = portalToSplit->numVertices;
00350     int count = 0, out_c = 0, in_c = 0, sideA, sideB, loop;
00351     VECTOR planeNormal, polysNormal, edge1, edge2, temp;
00352     VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
00353 //    float x1, x2, y1, y2, z1, z2, u1, u2, v1, v2, scale; // texture calculation variables
00354 
00355     // get the splitting planes normal
00356     planeNormal.x = plane.nx;
00357     planeNormal.y = plane.ny;
00358     planeNormal.z = plane.nz;
00359 
00360     // get the normal of the portal to split
00361     edge1.x = portalToSplit->Vertex[1].x - portalToSplit->Vertex[0].x;
00362     edge1.y = portalToSplit->Vertex[1].y - portalToSplit->Vertex[0].y;
00363     edge1.z = portalToSplit->Vertex[1].z - portalToSplit->Vertex[0].z;
00364     edge2.x = portalToSplit->Vertex[2].x - portalToSplit->Vertex[0].x;
00365     edge2.y = portalToSplit->Vertex[2].y - portalToSplit->Vertex[0].y;
00366     edge2.z = portalToSplit->Vertex[2].z - portalToSplit->Vertex[0].z;
00367     polysNormal = CrossVector(edge1, edge2);
00368 
00369     // check if the portal lies on the plane
00370     for (int loop = 0; loop < numVerts; loop++)
00371     {
00372         temp.x = portalToSplit->Vertex[loop].x;
00373         temp.y = portalToSplit->Vertex[loop].y;
00374         temp.z = portalToSplit->Vertex[loop].z;
00375         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00376             count++;
00377         else
00378             break;
00379     }
00380     if (count == numVerts)
00381     {
00382         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00383             return Front;
00384         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00385             return Back;
00386     }
00387 
00388     // find if all of the points are infront of or behind the plane
00389     int frontcount = 0, backcount = 0;
00390     for (int loop = 0; loop < numVerts; loop++)
00391     {
00392         temp.x = portalToSplit->Vertex[loop].x;
00393         temp.y = portalToSplit->Vertex[loop].y;
00394         temp.z = portalToSplit->Vertex[loop].z;
00395         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00396         {
00397             frontcount++;
00398             backcount++;
00399         }
00400         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00401             frontcount++;
00402         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00403             backcount++;
00404     }
00405     if (frontcount == numVerts)
00406             return Front;
00407     if (backcount == numVerts)
00408             return Back;
00409 
00410     // try to split the portal
00411     ptA = portalToSplit->Vertex[numVerts - 1];
00412     temp.x = ptA.x;
00413     temp.y = ptA.y;
00414     temp.z = ptA.z;
00415     sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00416     for (int i = -1; ++i < numVerts;)
00417     {
00418         ptB = portalToSplit->Vertex[i];
00419         temp.x = ptB.x;
00420         temp.y = ptB.y;
00421         temp.z = ptB.z;
00422         sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00423         if (sideB > 0)
00424         {
00425             if (sideA < 0)
00426             {
00427                 // find intersection
00428                 edge1.x = ptA.x;
00429                 edge1.y = ptA.y;
00430                 edge1.z = ptA.z;
00431                 edge2.x = ptB.x;
00432                 edge2.y = ptB.y;
00433                 edge2.z = ptB.z;
00434 
00435                 temp = GetEdgeIntersection(edge1, edge2, plane, pointOnPlane);
00436                 intersection.x = temp.x;
00437                 intersection.y = temp.y;
00438                 intersection.z = temp.z;
00439 /*
00440                 // find the new texture coordinates
00441                 x1 = ptB.x - ptA.x;
00442                 y1 = ptB.y - ptA.y;
00443                 z1 = ptB.z - ptA.z;
00444                 x2 = intersection.x - ptA.x;
00445                 y2 = intersection.y - ptA.y;
00446                 z2 = intersection.z - ptA.z;
00447                 u1 = ptA.u;
00448                 u2 = ptB.u;
00449                 v1 = ptA.v;
00450                 v2 = ptB.v;
00451                 scale = sqrt(x2*x2+y2*y2+z2*z2)/sqrt(x1*x1+y1*y1+z1*z1);
00452                 intersection.u = u1 + (u2-u1) * scale;
00453                 intersection.v = v1 + (v2-v1) * scale;
00454 */
00455                 outpts[out_c++] = inpts[in_c++] = intersection;
00456             }
00457             inpts[in_c++] = ptB;
00458         }
00459         else if (sideB < 0)
00460         {
00461             if (sideA > 0)
00462             {
00463                 // find intersection
00464                 edge1.x = ptA.x;
00465                 edge1.y = ptA.y;
00466                 edge1.z = ptA.z;
00467                 edge2.x = ptB.x;
00468                 edge2.y = ptB.y;
00469                 edge2.z = ptB.z;
00470 
00471                 temp = GetEdgeIntersection(edge1, edge2, plane, pointOnPlane);
00472                 intersection.x = temp.x;
00473                 intersection.y = temp.y;
00474                 intersection.z = temp.z;
00475 /*
00476                 // find the new texture coordinates
00477                 x1 = ptB.x - ptA.x;
00478                 y1 = ptB.y - ptA.y;
00479                 z1 = ptB.z - ptA.z;
00480                 x2 = intersection.x - ptA.x;
00481                 y2 = intersection.y - ptA.y;
00482                 z2 = intersection.z - ptA.z;
00483                 u1 = ptA.u;
00484                 u2 = ptB.u;
00485                 v1 = ptA.v;
00486                 v2 = ptB.v;
00487                 scale = sqrt(x2*x2+y2*y2+z2*z2)/sqrt(x1*x1+y1*y1+z1*z1);
00488                 intersection.u = u1 + (u2-u1) * scale;
00489                 intersection.v = v1 + (v2-v1) * scale;
00490 */
00491                 outpts[out_c++] = inpts[in_c++] = intersection;
00492             }
00493             outpts[out_c++] = ptB;
00494         }
00495         else
00496             outpts[out_c++] = inpts[in_c++] = ptB;
00497         ptA = ptB;
00498         sideA = sideB;
00499     }
00500 
00501     if (out_c == 0 || in_c == 0)
00502     {
00503         int side;
00504 
00505         for (int loop = 0; loop < numVerts; loop++)
00506         {
00507             temp.x = portalToSplit->Vertex[loop].x;
00508             temp.y = portalToSplit->Vertex[loop].y;
00509             temp.z = portalToSplit->Vertex[loop].z;
00510             side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00511             if (side == 1)
00512                 return Front;
00513             else if (side == -1)
00514                 return Back;
00515         }
00516     }
00517     else
00518     {
00519         front->Vertex = new VERTEX[in_c];
00520         back->Vertex = new VERTEX[out_c];
00521         front->numVertices = in_c;
00522         back->numVertices = out_c;
00523 
00524         for (loop = 0; loop < in_c; loop++)
00525             front->Vertex[loop] = inpts[loop];
00526         for (loop = 0; loop < out_c; loop++)
00527             back->Vertex[loop] = outpts[loop];
00528         return PortalWasSplit;
00529     }
00530     return 0;
00531 }
00532 
00533 void MakePortalList()
00534 {
00535     // Create the large portals
00536     for (int loop = 1; loop <= numpartitions; loop++)
00537     {
00538         listnode = PartitionList.Get(loop);
00539         portal = new PORTAL;
00540         portal->Vertex = 0;
00541         portal->linkPosition = loop;
00542         portal->PartitionNodeId = loop;
00543         CreateLargePortal(listnode->node->partition, portal);
00544         PortalList.Insert(portal);
00545     }
00546 
00547     // Split the large portals into potential portals
00548     numportals = numpartitions;
00549     int result, portalToSplit;
00550     PORTAL* frontportal;
00551     PORTAL* backportal;
00552     for (int partition = 1; partition <= numpartitions; partition++)
00553     {
00554         listnode = PartitionList.Get(partition);
00555         portalToSplit = numportals;
00556         while (portalToSplit > 0)
00557         {
00558             frontportal = new PORTAL;
00559             backportal = new PORTAL;
00560 
00561             portal = PortalList.Get(portalToSplit);
00562             result = SplitPortal(portal, listnode->node->partition, frontportal, backportal);
00563 
00564             if (result == PortalWasSplit)
00565             {
00566                 frontportal->PartitionNodeId = portal->PartitionNodeId;
00567                 backportal->PartitionNodeId = portal->PartitionNodeId;
00568 
00569                 delete[] portal->Vertex;
00570                 portal->Vertex = 0;
00571                 PortalList.Delete(portalToSplit);
00572                 delete portal;
00573                 numportals--;
00574 
00575                 frontportal->linkPosition = ++numportals;
00576                 PortalList.Insert(frontportal);
00577                 backportal->linkPosition = ++numportals;
00578                 PortalList.Insert(backportal);
00579             }
00580             else
00581             {
00582                 delete frontportal;
00583                 delete backportal;
00584             }
00585             portalToSplit--;
00586         }
00587     }
00588 
00589     // Loop through the portals and assign a unique id
00590     for (int loop = 1; loop <= numportals; loop++)
00591     {
00592         portal = PortalList.Get(loop);
00593         portal->PortalId = loop;
00594     }
00595 }
00596 
00597 int ClassifyPortal(PORTAL* portal, POLYGON planePolygon)
00598 {
00599     int numVerts = portal->numVertices;
00600     int count = 0;
00601     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00602 
00603     // get a point on the plane
00604     pointOnPlane.x = planePolygon.Vertex[0].x;
00605     pointOnPlane.y = planePolygon.Vertex[0].y;
00606     pointOnPlane.z = planePolygon.Vertex[0].z;
00607 
00608     // get the planes normal
00609     edge1.x = planePolygon.Vertex[1].x - planePolygon.Vertex[0].x;
00610     edge1.y = planePolygon.Vertex[1].y - planePolygon.Vertex[0].y;
00611     edge1.z = planePolygon.Vertex[1].z - planePolygon.Vertex[0].z;
00612     edge2.x = planePolygon.Vertex[2].x - planePolygon.Vertex[0].x;
00613     edge2.y = planePolygon.Vertex[2].y - planePolygon.Vertex[0].y;
00614     edge2.z = planePolygon.Vertex[2].z - planePolygon.Vertex[0].z;
00615     planeNormal = CrossVector(edge1, edge2);
00616 
00617     // get the normal of the portal
00618     edge1.x = portal->Vertex[1].x - portal->Vertex[0].x;
00619     edge1.y = portal->Vertex[1].y - portal->Vertex[0].y;
00620     edge1.z = portal->Vertex[1].z - portal->Vertex[0].z;
00621     edge2.x = portal->Vertex[2].x - portal->Vertex[0].x;
00622     edge2.y = portal->Vertex[2].y - portal->Vertex[0].y;
00623     edge2.z = portal->Vertex[2].z - portal->Vertex[0].z;
00624     polysNormal = CrossVector(edge1, edge2);
00625 
00626     // check if the portal lies on the plane
00627     for (int loop = 0; loop < numVerts; loop++)
00628     {
00629         temp.x = portal->Vertex[loop].x;
00630         temp.y = portal->Vertex[loop].y;
00631         temp.z = portal->Vertex[loop].z;
00632         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00633             count++;
00634         else
00635             break;
00636     }
00637     if (count == numVerts)
00638             return OnPartition;
00639 
00640     // find if all of the points are infront of or behind the plane
00641     int result, frontcount = 0, backcount = 0;
00642     for (int loop = 0; loop < numVerts; loop++)
00643     {
00644         temp.x = portal->Vertex[loop].x;
00645         temp.y = portal->Vertex[loop].y;
00646         temp.z = portal->Vertex[loop].z;
00647         result = ClassifyPoint(temp, pointOnPlane, planeNormal);
00648         if (result == 0)
00649         {
00650             frontcount++;
00651             backcount++;
00652         }
00653         else
00654             if (result == 1)
00655                 frontcount++;
00656         else
00657             if (result == -1)
00658                 backcount++;
00659     }
00660     if (frontcount == numVerts)
00661             return Front;
00662     if (backcount == numVerts)
00663             return Back;
00664 
00665     return 0;
00666 }
00667 
00668 int ClassifyInvertedPortal(PORTAL* portal, POLYGON planePolygon)
00669 {
00670     int numVerts = portal->numVertices;
00671     int count = 0;
00672     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00673 
00674     // get a point on the plane
00675     pointOnPlane.x = planePolygon.Vertex[0].x;
00676     pointOnPlane.y = planePolygon.Vertex[0].y;
00677     pointOnPlane.z = planePolygon.Vertex[0].z;
00678 
00679     // get the planes normal
00680     edge1.x = planePolygon.Vertex[1].x - planePolygon.Vertex[0].x;
00681     edge1.y = planePolygon.Vertex[1].y - planePolygon.Vertex[0].y;
00682     edge1.z = planePolygon.Vertex[1].z - planePolygon.Vertex[0].z;
00683     edge2.x = planePolygon.Vertex[2].x - planePolygon.Vertex[0].x;
00684     edge2.y = planePolygon.Vertex[2].y - planePolygon.Vertex[0].y;
00685     edge2.z = planePolygon.Vertex[2].z - planePolygon.Vertex[0].z;
00686     planeNormal = CrossVector(edge1, edge2);
00687 
00688     // get the normal of the portal
00689     edge1.x = portal->Vertex[1].x - portal->Vertex[0].x;
00690     edge1.y = portal->Vertex[1].y - portal->Vertex[0].y;
00691     edge1.z = portal->Vertex[1].z - portal->Vertex[0].z;
00692     edge2.x = portal->Vertex[2].x - portal->Vertex[0].x;
00693     edge2.y = portal->Vertex[2].y - portal->Vertex[0].y;
00694     edge2.z = portal->Vertex[2].z - portal->Vertex[0].z;
00695     polysNormal = CrossVector(edge1, edge2);
00696     polysNormal.x *= -1;
00697     polysNormal.y *= -1;
00698     polysNormal.z *= -1;
00699 
00700     // check if the portal lies on the plane
00701     for (int loop = 0; loop < numVerts; loop++)
00702     {
00703         temp.x = portal->Vertex[loop].x;
00704         temp.y = portal->Vertex[loop].y;
00705         temp.z = portal->Vertex[loop].z;
00706         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00707             count++;
00708         else
00709             break;
00710     }
00711     if (count == numVerts)
00712     {
00713         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00714             return Front;
00715         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00716             return Back;
00717     }
00718 
00719     // find if all of the points are infront of or behind the plane
00720     int result, frontcount = 0, backcount = 0;
00721     for (int loop = 0; loop < numVerts; loop++)
00722     {
00723         temp.x = portal->Vertex[loop].x;
00724         temp.y = portal->Vertex[loop].y;
00725         temp.z = portal->Vertex[loop].z;
00726         result = ClassifyPoint(temp, pointOnPlane, planeNormal);
00727         if (result == 0)
00728         {
00729             frontcount++;
00730             backcount++;
00731         }
00732         else
00733             if (result == 1)
00734                 frontcount++;
00735         else
00736             if (result == -1)
00737                 backcount++;
00738     }
00739     if (frontcount == numVerts)
00740             return Front;
00741     if (backcount == numVerts)
00742             return Back;
00743 
00744     return 0;
00745 }
00746 
00747 void InvertPortal(PORTAL* portal)
00748 {
00749     PORTAL* tempportal = CopyPortal(portal);
00750     int numverts = portal->numVertices;
00751     for (int loop = 0; loop < numverts; loop++)
00752         portal->Vertex[loop] = tempportal->Vertex[(numverts - 1) - loop];
00753     delete[] tempportal->Vertex;
00754     tempportal->Vertex = 0;
00755     delete tempportal;
00756     return;
00757 }
00758 
00759 void InvertPortals(BSP_node* node)
00760 {
00761     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00762     int flag;
00763     for (int loop = 1; loop <= node->numportals; loop++)
00764     {
00765         PORTAL* tempportal = node->portallist.Get(loop);
00766         // get a point on the plane
00767         pointOnPlane.x = tempportal->Vertex[0].x;
00768         pointOnPlane.y = tempportal->Vertex[0].y;
00769         pointOnPlane.z = tempportal->Vertex[0].z;
00770 
00771         // get the normal of the portals plane
00772         edge1.x = tempportal->Vertex[1].x - tempportal->Vertex[0].x;
00773         edge1.y = tempportal->Vertex[1].y - tempportal->Vertex[0].y;
00774         edge1.z = tempportal->Vertex[1].z - tempportal->Vertex[0].z;
00775         edge2.x = tempportal->Vertex[2].x - tempportal->Vertex[0].x;
00776         edge2.y = tempportal->Vertex[2].y - tempportal->Vertex[0].y;
00777         edge2.z = tempportal->Vertex[2].z - tempportal->Vertex[0].z;
00778         planeNormal = CrossVector(edge1, edge2);
00779 
00780         flag = 0;
00781         for (int polygon = 0; polygon < node->numpolys; polygon++)
00782         {
00783             for (int vert = 0; vert < 3; vert++)
00784             {
00785                 temp.x = node->nodepolylist[polygon].Vertex[vert].x;
00786                 temp.y = node->nodepolylist[polygon].Vertex[vert].y;
00787                 temp.z = node->nodepolylist[polygon].Vertex[vert].z;
00788 
00789                 flag = ClassifyPoint(temp, pointOnPlane, planeNormal);
00790                 if (flag == -1)
00791                 {
00792                     InvertPortal(tempportal);
00793                 }
00794                 if (flag == 1 || flag == -1)
00795                 {
00796                     if (tempportal->frontleaf->nodeid != node->nodeid)
00797                     {
00798                         BSP_node* tempnode = tempportal->backleaf;
00799                         tempportal->backleaf = tempportal->frontleaf;
00800                         tempportal->frontleaf = tempnode;
00801                     }
00802                     break;
00803                 }
00804             }
00805             if (flag == 1 || flag == -1)
00806                 break;
00807         }
00808     }
00809 }
00810 
00811 void AddPortal(PORTAL* thisportal, BSP_node* node)
00812 {
00813     if (node->leaf == true)
00814     {
00815         node->numportals++;
00816         thisportal->linkPosition = node->numportals;
00817         node->portallist.Insert(thisportal);
00818         return;
00819     }
00820 
00821     int side = ClassifyPortal(thisportal, node->partition);
00822     if (side == Front)
00823     {
00824         AddPortal(thisportal, node->frontnode);
00825     }
00826     if (side == Back)
00827     {
00828         AddPortal(thisportal, node->backnode);
00829     }
00830     if (side == OnPartition)
00831     {
00832         AddPortal(thisportal, node->frontnode);
00833         PORTAL* tempportal = CopyPortal(thisportal);
00834         AddPortal(tempportal, node->backnode);
00835     }
00836     return;
00837 }
00838 
00839 void AddPortalsToLeaves(BSP_node* root)
00840 {
00841     for (int loop = 1; loop <= numportals; loop++)
00842     {
00843         PORTAL* tempportal = CopyPortal(PortalList.Get(loop));
00844         AddPortal(tempportal, root);
00845     }
00846 }
00847 
00848 int ClipPortalToFrontLeaf(PORTAL* portal)
00849 {
00850     int result, returnvalue = 0;
00851     for (int polygon = 0; polygon < portal->frontleaf->numpolys; polygon++)
00852     {
00853         PORTAL* front = new PORTAL;
00854         PORTAL* back = new PORTAL;
00855         result = SplitPortal(portal, portal->frontleaf->nodepolylist[polygon], front, back);
00856 
00857         if (result == PortalWasSplit)
00858         {
00859             returnvalue = PortalWasSplit;
00860             delete[] back->Vertex;
00861             back->Vertex = 0;
00862             delete back;
00863             delete[] portal->Vertex;
00864             portal->Vertex = 0;
00865             portal->numVertices = front->numVertices; 
00866             portal->Vertex = front->Vertex;
00867             delete front;
00868         }
00869 
00870         else
00871         {
00872             delete back;
00873             delete front;
00874         }
00875     }
00876     return returnvalue;
00877 }
00878 
00879 int ClipPortalToBackLeaf(PORTAL* portal)
00880 {
00881     int result, returnvalue = 0;
00882     for (int polygon = 0; polygon < portal->backleaf->numpolys; polygon++)
00883     {
00884         PORTAL* front = new PORTAL;
00885         PORTAL* back = new PORTAL;
00886         result = SplitPortal(portal, portal->backleaf->nodepolylist[polygon], front, back);
00887 
00888         if (result == PortalWasSplit)
00889         {
00890             returnvalue = PortalWasSplit;
00891             delete[] back->Vertex;
00892             back->Vertex = 0;
00893             delete back;
00894             delete[] portal->Vertex;
00895             portal->Vertex = 0;
00896             portal->numVertices = front->numVertices;
00897             portal->Vertex = front->Vertex;
00898             delete front;
00899         }
00900         else
00901         {
00902             delete back;
00903             delete front;
00904         }
00905     }
00906     return returnvalue;
00907 }
00908 
00909 void CheckForSinglePortals(BSP_node* node, BSP_node* originalnode, PORTAL* portal, int* flag)
00910 {
00911     PORTAL* tempportal;
00912     if (node->leaf == true)
00913     {
00914         if (node->nodeid != originalnode->nodeid)
00915         {
00916             for (int portalnum = node->numportals; portalnum > 0; portalnum--)
00917             {
00918                 tempportal = node->portallist.Get(portalnum);
00919                 if (tempportal->PortalId == portal->PortalId)
00920                 {
00921                     portal->frontleaf = originalnode;
00922                     portal->backleaf = node;
00923                     *flag += 1;
00924                 }
00925             }
00926         }
00927         return;
00928     }
00929     else
00930     {
00931         CheckForSinglePortals(node->frontnode, originalnode, portal, flag);
00932         CheckForSinglePortals(node->backnode, originalnode, portal, flag);
00933         return;
00934     }
00935 }
00936 
00937 int RemoveExtraPortals(PORTAL* portal)
00938 {
00939     int result, count = 0;
00940     POLYGON temppoly;
00941     BSP_node* tempnode = portal->backleaf;
00942     for (int loop = 0; loop < tempnode->numpolys; loop++)
00943     {
00944         temppoly = tempnode->nodepolylist[loop];
00945         result = ClassifyInvertedPortal(portal, temppoly);
00946         if (result == Front)
00947             count++;
00948     }
00949     if (count != portal->backleaf->numpolys)
00950         return true;
00951     else
00952         return false;
00953 }
00954 
00955 void FindTruePortals(BSP_node* node)
00956 {
00957     int flag;
00958     if (node->leaf == true)
00959     {
00960         for (int portalnumber = node->numportals; portalnumber > 0; portalnumber--)
00961         {
00962             flag = 0;
00963             PORTAL* tempportal = node->portallist.Get(portalnumber);
00964             CheckForSinglePortals(root, node, tempportal, &flag);
00965             if (flag == 0)
00966             {
00967                 delete[] tempportal->Vertex;
00968                 tempportal->Vertex = 0;
00969                 node->portallist.Delete(portalnumber);
00970                 delete tempportal;
00971                 node->numportals--;
00972             }
00973             else
00974             {
00975                 ClipPortalToFrontLeaf(tempportal);
00976                 ClipPortalToBackLeaf(tempportal);
00977             }
00978         }
00979 
00980         InvertPortals(node);    // also inverts the front and back leaf pointers if necessary
00981 
00982         for (int portalnumber = node->numportals; portalnumber > 0; portalnumber--)
00983         {
00984             PORTAL* tempportal = node->portallist.Get(portalnumber);
00985             flag = RemoveExtraPortals(tempportal);
00986             if (flag == true)
00987             {
00988                 delete[] tempportal->Vertex;
00989                 tempportal->Vertex = 0;
00990                 node->portallist.Delete(portalnumber);
00991                 delete tempportal;
00992                 node->numportals--;
00993             }
00994         }
00995         return;
00996     }
00997     else
00998     {
00999         FindTruePortals(node->frontnode);
01000         FindTruePortals(node->backnode);
01001         return;
01002     }
01003 }
01004 

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