00001 #include <windows.h>
00002 #include "polygon.h"
00003 #include "tll.h"
00004 #include "locmath.h"
00005 #include "collision.h"
00006 #include "bsp.h"
00007 #include "mmgr.h"
00008
00009 POLYGON::POLYGON()
00010 {
00011 NextPoly = NULL;
00012 numVertices = 0;
00013 Texture = 0;
00014 }
00015
00016 POLYGON::~POLYGON()
00017 {
00018 }
00019
00020 bool POLYGON::IsLast()
00021 {
00022 if (NextPoly == NULL)
00023 return true;
00024 else
00025 return false;
00026 }
00027
00028 POLYGON* POLYGON::GetNext()
00029 {
00030 if (!IsLast())
00031 return NextPoly;
00032 else
00033 return NULL;
00034 }
00035
00036 void POLYGON::SetNext(POLYGON* Poly)
00037 {
00038 if (IsLast())
00039 {
00040 NextPoly = Poly;
00041 return;
00042 }
00043
00044
00045 POLYGON* TempPoly = Poly;
00046
00047 while (!TempPoly->IsLast())
00048 TempPoly = TempPoly->GetNext();
00049
00050 TempPoly->SetNext(NextPoly);
00051 NextPoly = Poly;
00052 }
00053
00054 POLYGON* POLYGON::CopyList()
00055 {
00056 POLYGON* TempPoly = new POLYGON;
00057
00058 TempPoly->Texture = Texture;
00059
00060 TempPoly->numVertices = numVertices;
00061
00062 for (int loop = 0; loop < numVertices; loop++)
00063 TempPoly->Vertex[loop] = Vertex[loop];
00064
00065 if (!IsLast())
00066 TempPoly->AddPolygon(NextPoly->CopyList());
00067
00068 return TempPoly;
00069 }
00070
00071 void POLYGON::AddPolygon(POLYGON* Poly)
00072 {
00073 if (Poly != NULL)
00074 {
00075 if (IsLast())
00076 {
00077 NextPoly = Poly;
00078 return;
00079 }
00080
00081 POLYGON* TempPoly = NextPoly;
00082
00083 while (!TempPoly->IsLast())
00084 TempPoly = TempPoly->GetNext();
00085
00086 TempPoly->NextPoly = Poly;
00087 }
00088 }
00089
00090 int POLYGON::Compare(const POLYGON& Polygon)
00091 {
00092 if (linkPosition < Polygon.linkPosition)
00093 return smaller;
00094 if (linkPosition > Polygon.linkPosition)
00095 return bigger;
00096 else
00097 return same;
00098 }
00099
00100 VECTOR POLYGON::GetNormal()
00101 {
00102 VECTOR temp, u, v;
00103 u = Vertex[1].coords - Vertex[0].coords;
00104 v = Vertex[2].coords - Vertex[0].coords;
00105 temp.x = (u.y*v.z)-(v.y*u.z);
00106 temp.y = (u.z*v.x)-(v.z*u.x);
00107 temp.z = (u.x*v.y)-(v.x*u.y);
00108 return temp;
00109 }
00110
00111 void POLYGON::SetNormal()
00112 {
00113 VECTOR u;
00114 VECTOR v;
00115 VERTEX tempVertex;
00116 u = Vertex[1].coords - Vertex[0].coords;
00117 v = Vertex[2].coords - Vertex[0].coords;
00118 tempVertex.normal.x = (u.y*v.z)-(v.y*u.z);
00119 tempVertex.normal.y = (u.z*v.x)-(v.z*u.x);
00120 tempVertex.normal.z = (u.x*v.y)-(v.x*u.y);
00121 for (int loop = 0; loop < maxPolygonVerts; loop++)
00122 {
00123 Vertex[loop].normal = tempVertex.normal;
00124 }
00125 }
00126
00127 VECTOR GetEdgeIntersection(VECTOR point0, VECTOR point1, POLYGON planePolygon)
00128 {
00129 VECTOR edge1, edge2, planeNormal, pointOnPlane, intersection, temp;
00130 float numerator, denominator, t;
00131
00132
00133 pointOnPlane = planePolygon.Vertex[0].coords;
00134
00135
00136 edge1 = planePolygon.Vertex[1].coords - planePolygon.Vertex[0].coords;
00137 edge2 = planePolygon.Vertex[2].coords - planePolygon.Vertex[0].coords;
00138 planeNormal = CrossVector(edge1, edge2);
00139
00140
00141
00142
00143
00144
00145 temp = pointOnPlane - point0;
00146 numerator = DotProduct(planeNormal, temp);
00147
00148
00149 temp = point1 - point0;
00150 denominator = DotProduct(planeNormal, temp);
00151
00152 if (denominator)
00153 t = numerator / denominator;
00154 else
00155 t = 0.0;
00156
00157 intersection.x = point0.x + temp.x * t;
00158 intersection.y = point0.y + temp.y * t;
00159 intersection.z = point0.z + temp.z * t;
00160
00161 return intersection;
00162 }
00163
00164 void DeleteList(POLYGON* Poly)
00165 {
00166 if (Poly->IsLast())
00167 {
00168 delete Poly;
00169 return;
00170 }
00171
00172 DeleteList(Poly->GetNext());
00173 delete Poly;
00174 }
00175
00176 int SplitPolygon(POLYGON* PolygonToSplit, POLYGON inputplanePolygon, POLYGON* front, POLYGON* back)
00177 {
00178 const int MaxVerts = 100;
00179 int numVerts = PolygonToSplit->numVertices;
00180 int count = 0, out_c = 0, in_c = 0, sideA, sideB, loop;
00181 VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00182 VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
00183 VERTEX texvert1, texvert2;
00184 VECTOR t1, t2;
00185 float scale;
00186 int PolygonNumber = PolygonToSplit->Vertex[0].polyNumber;
00187 int Removable = PolygonToSplit->removable;
00188 GLuint Tex = PolygonToSplit->Texture;
00189
00190
00191 pointOnPlane = inputplanePolygon.Vertex[0].coords;
00192
00193
00194 edge1 = inputplanePolygon.Vertex[1].coords - inputplanePolygon.Vertex[0].coords;
00195 edge2 = inputplanePolygon.Vertex[2].coords - inputplanePolygon.Vertex[0].coords;
00196 planeNormal = CrossVector(edge1, edge2);
00197
00198
00199 edge1 = PolygonToSplit->Vertex[1].coords - PolygonToSplit->Vertex[0].coords;
00200 edge2 = PolygonToSplit->Vertex[2].coords - PolygonToSplit->Vertex[0].coords;
00201 polysNormal = CrossVector(edge1, edge2);
00202
00203
00204 for (int loop = 0; loop < numVerts; loop++)
00205 {
00206 temp = PolygonToSplit->Vertex[loop].coords;
00207 if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00208 count++;
00209 else
00210 break;
00211 }
00212
00213 if (count == numVerts)
00214 return OnPartition;
00215
00216
00217 int frontcount = 0, backcount = 0;
00218 for (int loop = 0; loop < numVerts; loop++)
00219 {
00220 temp = PolygonToSplit->Vertex[loop].coords;
00221 if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00222 {
00223 frontcount++;
00224 backcount++;
00225 }
00226 else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00227 frontcount++;
00228 else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00229 backcount++;
00230 }
00231 if (frontcount == numVerts)
00232 return Front;
00233 if (backcount == numVerts)
00234 return Back;
00235
00236
00237 ptA = PolygonToSplit->Vertex[numVerts - 1];
00238 temp = ptA.coords;
00239 sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00240 for (int i = -1; ++i < numVerts;)
00241 {
00242 ptB = PolygonToSplit->Vertex[i];
00243 temp = ptB.coords;
00244 sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00245 if (sideB > 0)
00246 {
00247 if (sideA < 0)
00248 {
00249
00250 edge1 = ptA.coords;
00251 edge2 = ptB.coords;
00252
00253 temp = GetEdgeIntersection(edge1, edge2, inputplanePolygon);
00254 intersection.coords = temp;
00255
00256
00257 texvert1.coords = ptB.coords - ptA.coords;
00258 texvert2.coords = intersection.coords - ptA.coords;
00259 texvert1.u = ptA.u;
00260 texvert2.u = ptB.u;
00261 texvert1.v = ptA.v;
00262 texvert2.v = ptB.v;
00263 t1 = texvert1.coords;
00264 t2 = texvert2.coords;
00265 scale = sqrt(t2.x*t2.x+t2.y*t2.y+t2.z*t2.z)/sqrt(t1.x*t1.x+t1.y*t1.y+t1.z*t1.z);
00266 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00267 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00268
00269 outpts[out_c++] = inpts[in_c++] = intersection;
00270 }
00271 inpts[in_c++] = ptB;
00272 }
00273 else if (sideB < 0)
00274 {
00275 if (sideA > 0)
00276 {
00277
00278 edge1 = ptA.coords;
00279 edge2 = ptB.coords;
00280
00281 temp = GetEdgeIntersection(edge1, edge2, inputplanePolygon);
00282 intersection.coords = temp;
00283
00284
00285 texvert1.coords = ptB.coords - ptA.coords;
00286 texvert2.coords = intersection.coords - ptA.coords;
00287 texvert1.u = ptA.u;
00288 texvert2.u = ptB.u;
00289 texvert1.v = ptA.v;
00290 texvert2.v = ptB.v;
00291 t1 = texvert1.coords;
00292 t2 = texvert2.coords;
00293 scale = sqrt(t2.x*t2.x+t2.y*t2.y+t2.z*t2.z)/sqrt(t1.x*t1.x+t1.y*t1.y+t1.z*t1.z);
00294 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00295 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00296
00297 outpts[out_c++] = inpts[in_c++] = intersection;
00298 }
00299 outpts[out_c++] = ptB;
00300 }
00301 else
00302 outpts[out_c++] = inpts[in_c++] = ptB;
00303 ptA = ptB;
00304 sideA = sideB;
00305 }
00306
00307 if (out_c == 0 || in_c == 0)
00308 {
00309 int side;
00310
00311 for (int loop = 0; loop < numVerts; loop++)
00312 {
00313 temp = PolygonToSplit->Vertex[loop].coords;
00314 side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00315 if (side == 1)
00316 return Front;
00317 else if (side == -1)
00318 return Back;
00319 }
00320 }
00321 else
00322 {
00323 front->numVertices = in_c;
00324 back->numVertices = out_c;
00325
00326 for (int loop = 0; loop < in_c; loop++)
00327 {
00328 front->Vertex[loop] = inpts[loop];
00329 front->Vertex[loop].polyNumber = PolygonNumber;
00330 }
00331 for (int loop = 0; loop < out_c; loop++)
00332 {
00333 back->Vertex[loop] = outpts[loop];
00334 back->Vertex[loop].polyNumber = PolygonNumber;
00335 }
00336 front->removable = Removable;
00337 front->Texture = Tex;
00338 front->SetNormal();
00339 back->removable = Removable;
00340 back->Texture = Tex;
00341 back->SetNormal();
00342 return PolygonWasSplit;
00343 }
00344
00345 return 0;
00346 }
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363 int SplitTriangle(POLYGON triangleToSplit, POLYGON planeTriangle, POLYGON* triangles)
00364 {
00365 VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00366 VERTEX ptA, ptB, outpts[4], inpts[4], intersection;
00367 int count = 0, out_c = 0, in_c = 0, sideA, sideB, outputFlag;
00368 VERTEX texvert1, texvert2;
00369 VECTOR t1, t2;
00370 float scale;
00371
00372
00373 pointOnPlane = planeTriangle.Vertex[0].coords;
00374
00375
00376 edge1 = planeTriangle.Vertex[1].coords - planeTriangle.Vertex[0].coords;
00377 edge2 = planeTriangle.Vertex[2].coords - planeTriangle.Vertex[0].coords;
00378 planeNormal = CrossVector(edge1, edge2);
00379
00380
00381 edge1 = triangleToSplit.Vertex[1].coords - triangleToSplit.Vertex[0].coords;
00382 edge2 = triangleToSplit.Vertex[2].coords - triangleToSplit.Vertex[0].coords;
00383 polysNormal = CrossVector(edge1, edge2);
00384
00385
00386 for (int loop = 0; loop < 3; loop++)
00387 {
00388 temp = triangleToSplit.Vertex[loop].coords;
00389 if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00390 count++;
00391 else
00392 break;
00393 }
00394 if (count == 3)
00395 {
00396 if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00397 return Front;
00398 if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00399 return Back;
00400 }
00401
00402
00403 int frontcount = 0, backcount = 0;
00404 for (int loop = 0; loop < 3; loop++)
00405 {
00406 temp = triangleToSplit.Vertex[loop].coords;
00407 if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00408 {
00409 frontcount++;
00410 backcount++;
00411 }
00412 else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00413 frontcount++;
00414 else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00415 backcount++;
00416 }
00417 if (frontcount == 3)
00418 return Front;
00419 if (backcount == 3)
00420 return Back;
00421
00422
00423 ptA = triangleToSplit.Vertex[2];
00424 temp = ptA.coords;
00425 sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00426 for (int i = -1; ++i < 3;)
00427 {
00428 ptB = triangleToSplit.Vertex[i];
00429 temp = ptB.coords;
00430 sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00431 if (sideB > 0)
00432 {
00433 if (sideA < 0)
00434 {
00435
00436 edge1 = ptA.coords;
00437 edge2 = ptB.coords;
00438
00439 temp = GetEdgeIntersection(edge1, edge2, planeTriangle);
00440 intersection.coords = temp;
00441
00442
00443 texvert1.coords = ptB.coords - ptA.coords;
00444 texvert2.coords = intersection.coords - ptA.coords;
00445 texvert1.u = ptA.u;
00446 texvert2.u = ptB.u;
00447 texvert1.v = ptA.v;
00448 texvert2.v = ptB.v;
00449 t1 = texvert1.coords;
00450 t2 = texvert2.coords;
00451 scale = sqrt(t2.x*t2.x+t2.y*t2.y+t2.z*t2.z)/sqrt(t1.x*t1.x+t1.y*t1.y+t1.z*t1.z);
00452 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00453 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * 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
00464 edge1 = ptA.coords;
00465 edge2 = ptB.coords;
00466
00467 temp = GetEdgeIntersection(edge1, edge2, planeTriangle);
00468 intersection.coords = temp;
00469
00470
00471 texvert1.coords = ptB.coords - ptA.coords;
00472 texvert2.coords = intersection.coords - ptA.coords;
00473 texvert1.u = ptA.u;
00474 texvert2.u = ptB.u;
00475 texvert1.v = ptA.v;
00476 texvert2.v = ptB.v;
00477 t1 = texvert1.coords;
00478 t2 = texvert2.coords;
00479 scale = sqrt(t2.x*t2.x+t2.y*t2.y+t2.z*t2.z)/sqrt(t1.x*t1.x+t1.y*t1.y+t1.z*t1.z);
00480 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00481 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00482
00483 outpts[out_c++] = inpts[in_c++] = intersection;
00484 }
00485 outpts[out_c++] = ptB;
00486 }
00487 else
00488 outpts[out_c++] = inpts[in_c++] = ptB;
00489 ptA = ptB;
00490 sideA = sideB;
00491 }
00492
00493 if (in_c == 4)
00494 {
00495 outputFlag = TwoFrontOneBack;
00496 if (triangles)
00497 {
00498 triangles[0].Vertex[0] = inpts[0];
00499 triangles[0].Vertex[1] = inpts[1];
00500 triangles[0].Vertex[2] = inpts[2];
00501 triangles[0].numVertices = 3;
00502 triangles[0].SetNormal();
00503 triangles[1].Vertex[0] = inpts[0];
00504 triangles[1].Vertex[1] = inpts[2];
00505 triangles[1].Vertex[2] = inpts[3];
00506 triangles[1].numVertices = 3;
00507 triangles[1].SetNormal();
00508 triangles[2].Vertex[0] = outpts[0];
00509 triangles[2].Vertex[1] = outpts[1];
00510 triangles[2].Vertex[2] = outpts[2];
00511 triangles[2].numVertices = 3;
00512 triangles[2].SetNormal();
00513 }
00514 }
00515 else if (out_c == 4)
00516 {
00517 outputFlag = OneFrontTwoBack;
00518 if (triangles)
00519 {
00520 triangles[0].Vertex[0] = inpts[0];
00521 triangles[0].Vertex[1] = inpts[1];
00522 triangles[0].Vertex[2] = inpts[2];
00523 triangles[0].numVertices = 3;
00524 triangles[0].SetNormal();
00525 triangles[1].Vertex[0] = outpts[0];
00526 triangles[1].Vertex[1] = outpts[1];
00527 triangles[1].Vertex[2] = outpts[2];
00528 triangles[1].numVertices = 3;
00529 triangles[1].SetNormal();
00530 triangles[2].Vertex[0] = outpts[0];
00531 triangles[2].Vertex[1] = outpts[2];
00532 triangles[2].Vertex[2] = outpts[3];
00533 triangles[2].numVertices = 3;
00534 triangles[2].SetNormal();
00535 }
00536 }
00537 else if (in_c == 3 && out_c == 3)
00538 {
00539 outputFlag = OneFrontOneBack;
00540 if (triangles)
00541 {
00542 triangles[0].Vertex[0] = inpts[0];
00543 triangles[0].Vertex[1] = inpts[1];
00544 triangles[0].Vertex[2] = inpts[2];
00545 triangles[0].numVertices = 3;
00546 triangles[0].SetNormal();
00547 triangles[1].Vertex[0] = outpts[0];
00548 triangles[1].Vertex[1] = outpts[1];
00549 triangles[1].Vertex[2] = outpts[2];
00550 triangles[1].numVertices = 3;
00551 triangles[1].SetNormal();
00552 }
00553 }
00554 else
00555 {
00556 int side;
00557
00558 for (int loop = 0; loop < 3; loop++)
00559 {
00560 temp = triangleToSplit.Vertex[loop].coords;
00561 side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00562 if (side == 1)
00563 {
00564 outputFlag = Front;
00565 break;
00566 }
00567 else if (side == -1)
00568 {
00569 outputFlag = Back;
00570 break;
00571 }
00572 }
00573 }
00574 return outputFlag;
00575 }
00576
00577 int ClassifyPolygon(POLYGON* Polygon, POLYGON planePolygon)
00578 {
00579 int numVerts = Polygon->numVertices;
00580 int count = 0;
00581 VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00582
00583
00584 pointOnPlane = planePolygon.Vertex[0].coords;
00585
00586
00587 edge1 = planePolygon.Vertex[1].coords - planePolygon.Vertex[0].coords;
00588 edge2 = planePolygon.Vertex[2].coords - planePolygon.Vertex[0].coords;
00589 planeNormal = CrossVector(edge1, edge2);
00590
00591
00592 edge1 = Polygon->Vertex[1].coords - Polygon->Vertex[0].coords;
00593 edge2 = Polygon->Vertex[2].coords - Polygon->Vertex[0].coords;
00594 polysNormal = CrossVector(edge1, edge2);
00595
00596
00597 for (int loop = 0; loop < numVerts; loop++)
00598 {
00599 temp = Polygon->Vertex[loop].coords;
00600 if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00601 count++;
00602 else
00603 break;
00604 }
00605 if (count == numVerts)
00606 return OnPartition;
00607
00608
00609 int result, frontcount = 0, backcount = 0;
00610 for (int loop = 0; loop < numVerts; loop++)
00611 {
00612 temp = Polygon->Vertex[loop].coords;
00613 result = ClassifyPoint(temp, pointOnPlane, planeNormal);
00614 if (result == 0)
00615 {
00616 frontcount++;
00617 backcount++;
00618 }
00619 else
00620 if (result == 1)
00621 frontcount++;
00622 else
00623 if (result == -1)
00624 backcount++;
00625 }
00626 if (frontcount == numVerts)
00627 return Front;
00628 if (backcount == numVerts)
00629 return Back;
00630
00631 return PolygonWasSplit;
00632 }
00633
00634 void InvertPolygon(POLYGON* Polygon)
00635 {
00636 POLYGON temppolygon = *Polygon;
00637 for (int loop = 0; loop < Polygon->numVertices; loop++)
00638 Polygon->Vertex[loop] = temppolygon.Vertex[(Polygon->numVertices - 1) - loop];
00639 Polygon->SetNormal();
00640 return;
00641 }