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 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
00099 largePortal->numVertices = 4;
00100 largePortal->Vertex = new VERTEX[4];
00101
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:
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:
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:
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
00190 pointOnPlane.x = planePolygon.Vertex[0].x;
00191 pointOnPlane.y = planePolygon.Vertex[0].y;
00192 pointOnPlane.z = planePolygon.Vertex[0].z;
00193
00194
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
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
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
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
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
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
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
00354
00355
00356 planeNormal.x = plane.nx;
00357 planeNormal.y = plane.ny;
00358 planeNormal.z = plane.nz;
00359
00360
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
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
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
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
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
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
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
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
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
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
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
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
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
00604 pointOnPlane.x = planePolygon.Vertex[0].x;
00605 pointOnPlane.y = planePolygon.Vertex[0].y;
00606 pointOnPlane.z = planePolygon.Vertex[0].z;
00607
00608
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
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
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
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
00675 pointOnPlane.x = planePolygon.Vertex[0].x;
00676 pointOnPlane.y = planePolygon.Vertex[0].y;
00677 pointOnPlane.z = planePolygon.Vertex[0].z;
00678
00679
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
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
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
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
00767 pointOnPlane.x = tempportal->Vertex[0].x;
00768 pointOnPlane.y = tempportal->Vertex[0].y;
00769 pointOnPlane.z = tempportal->Vertex[0].z;
00770
00771
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);
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