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;
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
00079 largePortal->numVertices = 4;
00080 largePortal->Vertex = new VERTEX[4];
00081
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:
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:
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:
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
00170 pointOnPlane = planePolygon.Vertex[0].coords;
00171
00172
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
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
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
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
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
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
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
00303 planeNormal = plane.normal;
00304
00305
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
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
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
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
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
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
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
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
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
00488 pointOnPlane = planePolygon.Vertex[0].coords;
00489
00490
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
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
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
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
00545 pointOnPlane = planePolygon.Vertex[0].coords;
00546
00547
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
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
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
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
00620 pointOnPlane = tempportal->Vertex[0].coords;
00621
00622
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);
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 }