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