l_poly.c (33800B)
1 /* 2 =========================================================================== 3 Copyright (C) 1999-2005 Id Software, Inc. 4 5 This file is part of Quake III Arena source code. 6 7 Quake III Arena source code is free software; you can redistribute it 8 and/or modify it under the terms of the GNU General Public License as 9 published by the Free Software Foundation; either version 2 of the License, 10 or (at your option) any later version. 11 12 Quake III Arena source code is distributed in the hope that it will be 13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with Foobar; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 20 =========================================================================== 21 */ 22 23 #include <malloc.h> 24 #include "l_cmd.h" 25 #include "l_math.h" 26 #include "l_poly.h" 27 #include "l_log.h" 28 #include "l_mem.h" 29 30 #define BOGUS_RANGE 65535 31 32 extern int numthreads; 33 34 // counters are only bumped when running single threaded, 35 // because they are an awefull coherence problem 36 int c_active_windings; 37 int c_peak_windings; 38 int c_winding_allocs; 39 int c_winding_points; 40 int c_windingmemory; 41 int c_peak_windingmemory; 42 43 char windingerror[1024]; 44 45 void pw(winding_t *w) 46 { 47 int i; 48 for (i=0 ; i<w->numpoints ; i++) 49 printf ("(%5.3f, %5.3f, %5.3f)\n",w->p[i][0], w->p[i][1],w->p[i][2]); 50 } 51 52 53 void ResetWindings(void) 54 { 55 c_active_windings = 0; 56 c_peak_windings = 0; 57 c_winding_allocs = 0; 58 c_winding_points = 0; 59 c_windingmemory = 0; 60 c_peak_windingmemory = 0; 61 62 strcpy(windingerror, ""); 63 } //end of the function ResetWindings 64 /* 65 ============= 66 AllocWinding 67 ============= 68 */ 69 winding_t *AllocWinding (int points) 70 { 71 winding_t *w; 72 int s; 73 74 s = sizeof(vec_t)*3*points + sizeof(int); 75 w = GetMemory(s); 76 memset(w, 0, s); 77 78 if (numthreads == 1) 79 { 80 c_winding_allocs++; 81 c_winding_points += points; 82 c_active_windings++; 83 if (c_active_windings > c_peak_windings) 84 c_peak_windings = c_active_windings; 85 c_windingmemory += MemorySize(w); 86 if (c_windingmemory > c_peak_windingmemory) 87 c_peak_windingmemory = c_windingmemory; 88 } //end if 89 return w; 90 } //end of the function AllocWinding 91 92 void FreeWinding (winding_t *w) 93 { 94 if (*(unsigned *)w == 0xdeaddead) 95 Error ("FreeWinding: freed a freed winding"); 96 97 if (numthreads == 1) 98 { 99 c_active_windings--; 100 c_windingmemory -= MemorySize(w); 101 } //end if 102 103 *(unsigned *)w = 0xdeaddead; 104 105 FreeMemory(w); 106 } //end of the function FreeWinding 107 108 int WindingMemory(void) 109 { 110 return c_windingmemory; 111 } //end of the function WindingMemory 112 113 int WindingPeakMemory(void) 114 { 115 return c_peak_windingmemory; 116 } //end of the function WindingPeakMemory 117 118 int ActiveWindings(void) 119 { 120 return c_active_windings; 121 } //end of the function ActiveWindings 122 /* 123 ============ 124 RemoveColinearPoints 125 ============ 126 */ 127 int c_removed; 128 129 void RemoveColinearPoints (winding_t *w) 130 { 131 int i, j, k; 132 vec3_t v1, v2; 133 int nump; 134 vec3_t p[MAX_POINTS_ON_WINDING]; 135 136 nump = 0; 137 for (i=0 ; i<w->numpoints ; i++) 138 { 139 j = (i+1)%w->numpoints; 140 k = (i+w->numpoints-1)%w->numpoints; 141 VectorSubtract (w->p[j], w->p[i], v1); 142 VectorSubtract (w->p[i], w->p[k], v2); 143 VectorNormalize(v1); 144 VectorNormalize(v2); 145 if (DotProduct(v1, v2) < 0.999) 146 { 147 if (nump >= MAX_POINTS_ON_WINDING) 148 Error("RemoveColinearPoints: MAX_POINTS_ON_WINDING"); 149 VectorCopy (w->p[i], p[nump]); 150 nump++; 151 } 152 } 153 154 if (nump == w->numpoints) 155 return; 156 157 if (numthreads == 1) 158 c_removed += w->numpoints - nump; 159 w->numpoints = nump; 160 memcpy (w->p, p, nump*sizeof(p[0])); 161 } 162 163 /* 164 ============ 165 WindingPlane 166 ============ 167 */ 168 void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist) 169 { 170 vec3_t v1, v2; 171 int i; 172 173 //find two vectors each longer than 0.5 units 174 for (i = 0; i < w->numpoints; i++) 175 { 176 VectorSubtract(w->p[(i+1) % w->numpoints], w->p[i], v1); 177 VectorSubtract(w->p[(i+2) % w->numpoints], w->p[i], v2); 178 if (VectorLength(v1) > 0.5 && VectorLength(v2) > 0.5) break; 179 } //end for 180 CrossProduct(v2, v1, normal); 181 VectorNormalize(normal); 182 *dist = DotProduct(w->p[0], normal); 183 } //end of the function WindingPlane 184 185 /* 186 ============= 187 WindingArea 188 ============= 189 */ 190 vec_t WindingArea (winding_t *w) 191 { 192 int i; 193 vec3_t d1, d2, cross; 194 vec_t total; 195 196 total = 0; 197 for (i=2 ; i<w->numpoints ; i++) 198 { 199 VectorSubtract (w->p[i-1], w->p[0], d1); 200 VectorSubtract (w->p[i], w->p[0], d2); 201 CrossProduct (d1, d2, cross); 202 total += 0.5 * VectorLength ( cross ); 203 } 204 return total; 205 } 206 207 void WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs) 208 { 209 vec_t v; 210 int i,j; 211 212 mins[0] = mins[1] = mins[2] = 99999; 213 maxs[0] = maxs[1] = maxs[2] = -99999; 214 215 for (i=0 ; i<w->numpoints ; i++) 216 { 217 for (j=0 ; j<3 ; j++) 218 { 219 v = w->p[i][j]; 220 if (v < mins[j]) 221 mins[j] = v; 222 if (v > maxs[j]) 223 maxs[j] = v; 224 } 225 } 226 } 227 228 /* 229 ============= 230 WindingCenter 231 ============= 232 */ 233 void WindingCenter (winding_t *w, vec3_t center) 234 { 235 int i; 236 float scale; 237 238 VectorCopy (vec3_origin, center); 239 for (i=0 ; i<w->numpoints ; i++) 240 VectorAdd (w->p[i], center, center); 241 242 scale = 1.0/w->numpoints; 243 VectorScale (center, scale, center); 244 } 245 246 /* 247 ================= 248 BaseWindingForPlane 249 ================= 250 */ 251 winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist) 252 { 253 int i, x; 254 vec_t max, v; 255 vec3_t org, vright, vup; 256 winding_t *w; 257 258 // find the major axis 259 260 max = -BOGUS_RANGE; 261 x = -1; 262 for (i=0 ; i<3; i++) 263 { 264 v = fabs(normal[i]); 265 if (v > max) 266 { 267 x = i; 268 max = v; 269 } 270 } 271 if (x==-1) 272 Error ("BaseWindingForPlane: no axis found"); 273 274 VectorCopy (vec3_origin, vup); 275 switch (x) 276 { 277 case 0: 278 case 1: 279 vup[2] = 1; 280 break; 281 case 2: 282 vup[0] = 1; 283 break; 284 } 285 286 v = DotProduct (vup, normal); 287 VectorMA (vup, -v, normal, vup); 288 VectorNormalize (vup); 289 290 VectorScale (normal, dist, org); 291 292 CrossProduct (vup, normal, vright); 293 294 VectorScale (vup, BOGUS_RANGE, vup); 295 VectorScale (vright, BOGUS_RANGE, vright); 296 297 // project a really big axis aligned box onto the plane 298 w = AllocWinding (4); 299 300 VectorSubtract (org, vright, w->p[0]); 301 VectorAdd (w->p[0], vup, w->p[0]); 302 303 VectorAdd (org, vright, w->p[1]); 304 VectorAdd (w->p[1], vup, w->p[1]); 305 306 VectorAdd (org, vright, w->p[2]); 307 VectorSubtract (w->p[2], vup, w->p[2]); 308 309 VectorSubtract (org, vright, w->p[3]); 310 VectorSubtract (w->p[3], vup, w->p[3]); 311 312 w->numpoints = 4; 313 314 return w; 315 } 316 317 /* 318 ================== 319 CopyWinding 320 ================== 321 */ 322 winding_t *CopyWinding (winding_t *w) 323 { 324 int size; 325 winding_t *c; 326 327 c = AllocWinding (w->numpoints); 328 size = (int)((winding_t *)0)->p[w->numpoints]; 329 memcpy (c, w, size); 330 return c; 331 } 332 333 /* 334 ================== 335 ReverseWinding 336 ================== 337 */ 338 winding_t *ReverseWinding (winding_t *w) 339 { 340 int i; 341 winding_t *c; 342 343 c = AllocWinding (w->numpoints); 344 for (i=0 ; i<w->numpoints ; i++) 345 { 346 VectorCopy (w->p[w->numpoints-1-i], c->p[i]); 347 } 348 c->numpoints = w->numpoints; 349 return c; 350 } 351 352 353 /* 354 ============= 355 ClipWindingEpsilon 356 ============= 357 */ 358 void ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, 359 vec_t epsilon, winding_t **front, winding_t **back) 360 { 361 vec_t dists[MAX_POINTS_ON_WINDING+4]; 362 int sides[MAX_POINTS_ON_WINDING+4]; 363 int counts[3]; 364 //MrElusive: DOH can't use statics when unsing multithreading!!! 365 vec_t dot; // VC 4.2 optimizer bug if not static 366 int i, j; 367 vec_t *p1, *p2; 368 vec3_t mid; 369 winding_t *f, *b; 370 int maxpts; 371 372 counts[0] = counts[1] = counts[2] = 0; 373 374 // determine sides for each point 375 for (i=0 ; i<in->numpoints ; i++) 376 { 377 dot = DotProduct (in->p[i], normal); 378 dot -= dist; 379 dists[i] = dot; 380 if (dot > epsilon) 381 sides[i] = SIDE_FRONT; 382 else if (dot < -epsilon) 383 sides[i] = SIDE_BACK; 384 else 385 { 386 sides[i] = SIDE_ON; 387 } 388 counts[sides[i]]++; 389 } 390 sides[i] = sides[0]; 391 dists[i] = dists[0]; 392 393 *front = *back = NULL; 394 395 if (!counts[0]) 396 { 397 *back = CopyWinding (in); 398 return; 399 } 400 if (!counts[1]) 401 { 402 *front = CopyWinding (in); 403 return; 404 } 405 406 maxpts = in->numpoints+4; // cant use counts[0]+2 because 407 // of fp grouping errors 408 409 *front = f = AllocWinding (maxpts); 410 *back = b = AllocWinding (maxpts); 411 412 for (i=0 ; i<in->numpoints ; i++) 413 { 414 p1 = in->p[i]; 415 416 if (sides[i] == SIDE_ON) 417 { 418 VectorCopy (p1, f->p[f->numpoints]); 419 f->numpoints++; 420 VectorCopy (p1, b->p[b->numpoints]); 421 b->numpoints++; 422 continue; 423 } 424 425 if (sides[i] == SIDE_FRONT) 426 { 427 VectorCopy (p1, f->p[f->numpoints]); 428 f->numpoints++; 429 } 430 if (sides[i] == SIDE_BACK) 431 { 432 VectorCopy (p1, b->p[b->numpoints]); 433 b->numpoints++; 434 } 435 436 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) 437 continue; 438 439 // generate a split point 440 p2 = in->p[(i+1)%in->numpoints]; 441 442 dot = dists[i] / (dists[i]-dists[i+1]); 443 for (j=0 ; j<3 ; j++) 444 { // avoid round off error when possible 445 if (normal[j] == 1) 446 mid[j] = dist; 447 else if (normal[j] == -1) 448 mid[j] = -dist; 449 else 450 mid[j] = p1[j] + dot*(p2[j]-p1[j]); 451 } 452 453 VectorCopy (mid, f->p[f->numpoints]); 454 f->numpoints++; 455 VectorCopy (mid, b->p[b->numpoints]); 456 b->numpoints++; 457 } 458 459 if (f->numpoints > maxpts || b->numpoints > maxpts) 460 Error ("ClipWinding: points exceeded estimate"); 461 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING) 462 Error ("ClipWinding: MAX_POINTS_ON_WINDING"); 463 } 464 465 466 /* 467 ============= 468 ChopWindingInPlace 469 ============= 470 */ 471 void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon) 472 { 473 winding_t *in; 474 vec_t dists[MAX_POINTS_ON_WINDING+4]; 475 int sides[MAX_POINTS_ON_WINDING+4]; 476 int counts[3]; 477 //MrElusive: DOH can't use statics when unsing multithreading!!! 478 vec_t dot; // VC 4.2 optimizer bug if not static 479 int i, j; 480 vec_t *p1, *p2; 481 vec3_t mid; 482 winding_t *f; 483 int maxpts; 484 485 in = *inout; 486 counts[0] = counts[1] = counts[2] = 0; 487 488 // determine sides for each point 489 for (i=0 ; i<in->numpoints ; i++) 490 { 491 dot = DotProduct (in->p[i], normal); 492 dot -= dist; 493 dists[i] = dot; 494 if (dot > epsilon) 495 sides[i] = SIDE_FRONT; 496 else if (dot < -epsilon) 497 sides[i] = SIDE_BACK; 498 else 499 { 500 sides[i] = SIDE_ON; 501 } 502 counts[sides[i]]++; 503 } 504 sides[i] = sides[0]; 505 dists[i] = dists[0]; 506 507 if (!counts[0]) 508 { 509 FreeWinding (in); 510 *inout = NULL; 511 return; 512 } 513 if (!counts[1]) 514 return; // inout stays the same 515 516 maxpts = in->numpoints+4; // cant use counts[0]+2 because 517 // of fp grouping errors 518 519 f = AllocWinding (maxpts); 520 521 for (i=0 ; i<in->numpoints ; i++) 522 { 523 p1 = in->p[i]; 524 525 if (sides[i] == SIDE_ON) 526 { 527 VectorCopy (p1, f->p[f->numpoints]); 528 f->numpoints++; 529 continue; 530 } 531 532 if (sides[i] == SIDE_FRONT) 533 { 534 VectorCopy (p1, f->p[f->numpoints]); 535 f->numpoints++; 536 } 537 538 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) 539 continue; 540 541 // generate a split point 542 p2 = in->p[(i+1)%in->numpoints]; 543 544 dot = dists[i] / (dists[i]-dists[i+1]); 545 for (j=0 ; j<3 ; j++) 546 { // avoid round off error when possible 547 if (normal[j] == 1) 548 mid[j] = dist; 549 else if (normal[j] == -1) 550 mid[j] = -dist; 551 else 552 mid[j] = p1[j] + dot*(p2[j]-p1[j]); 553 } 554 555 VectorCopy (mid, f->p[f->numpoints]); 556 f->numpoints++; 557 } 558 559 if (f->numpoints > maxpts) 560 Error ("ClipWinding: points exceeded estimate"); 561 if (f->numpoints > MAX_POINTS_ON_WINDING) 562 Error ("ClipWinding: MAX_POINTS_ON_WINDING"); 563 564 FreeWinding (in); 565 *inout = f; 566 } 567 568 569 /* 570 ================= 571 ChopWinding 572 573 Returns the fragment of in that is on the front side 574 of the cliping plane. The original is freed. 575 ================= 576 */ 577 winding_t *ChopWinding (winding_t *in, vec3_t normal, vec_t dist) 578 { 579 winding_t *f, *b; 580 581 ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b); 582 FreeWinding (in); 583 if (b) 584 FreeWinding (b); 585 return f; 586 } 587 588 589 /* 590 ================= 591 CheckWinding 592 593 ================= 594 */ 595 void CheckWinding (winding_t *w) 596 { 597 int i, j; 598 vec_t *p1, *p2; 599 vec_t d, edgedist; 600 vec3_t dir, edgenormal, facenormal; 601 vec_t area; 602 vec_t facedist; 603 604 if (w->numpoints < 3) 605 Error ("CheckWinding: %i points",w->numpoints); 606 607 area = WindingArea(w); 608 if (area < 1) 609 Error ("CheckWinding: %f area", area); 610 611 WindingPlane (w, facenormal, &facedist); 612 613 for (i=0 ; i<w->numpoints ; i++) 614 { 615 p1 = w->p[i]; 616 617 for (j=0 ; j<3 ; j++) 618 if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE) 619 Error ("CheckWinding: BUGUS_RANGE: %f",p1[j]); 620 621 j = i+1 == w->numpoints ? 0 : i+1; 622 623 // check the point is on the face plane 624 d = DotProduct (p1, facenormal) - facedist; 625 if (d < -ON_EPSILON || d > ON_EPSILON) 626 Error ("CheckWinding: point off plane"); 627 628 // check the edge isnt degenerate 629 p2 = w->p[j]; 630 VectorSubtract (p2, p1, dir); 631 632 if (VectorLength (dir) < ON_EPSILON) 633 Error ("CheckWinding: degenerate edge"); 634 635 CrossProduct (facenormal, dir, edgenormal); 636 VectorNormalize (edgenormal); 637 edgedist = DotProduct (p1, edgenormal); 638 edgedist += ON_EPSILON; 639 640 // all other points must be on front side 641 for (j=0 ; j<w->numpoints ; j++) 642 { 643 if (j == i) 644 continue; 645 d = DotProduct (w->p[j], edgenormal); 646 if (d > edgedist) 647 Error ("CheckWinding: non-convex"); 648 } 649 } 650 } 651 652 653 /* 654 ============ 655 WindingOnPlaneSide 656 ============ 657 */ 658 int WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist) 659 { 660 qboolean front, back; 661 int i; 662 vec_t d; 663 664 front = false; 665 back = false; 666 for (i=0 ; i<w->numpoints ; i++) 667 { 668 d = DotProduct (w->p[i], normal) - dist; 669 if (d < -ON_EPSILON) 670 { 671 if (front) 672 return SIDE_CROSS; 673 back = true; 674 continue; 675 } 676 if (d > ON_EPSILON) 677 { 678 if (back) 679 return SIDE_CROSS; 680 front = true; 681 continue; 682 } 683 } 684 685 if (back) 686 return SIDE_BACK; 687 if (front) 688 return SIDE_FRONT; 689 return SIDE_ON; 690 } 691 692 //#ifdef ME 693 #define CONTINUOUS_EPSILON 0.005 694 //#else 695 // #define CONTINUOUS_EPSILON 0.001 696 //#endif 697 698 /* 699 ============= 700 TryMergeWinding 701 702 If two polygons share a common edge and the edges that meet at the 703 common points are both inside the other polygons, merge them 704 705 Returns NULL if the faces couldn't be merged, or the new face. 706 The originals will NOT be freed. 707 ============= 708 */ 709 710 winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, vec3_t planenormal) 711 { 712 vec_t *p1, *p2, *p3, *p4, *back; 713 winding_t *newf; 714 int i, j, k, l; 715 vec3_t normal, delta; 716 vec_t dot; 717 qboolean keep1, keep2; 718 719 720 // 721 // find a common edge 722 // 723 p1 = p2 = NULL; // stop compiler warning 724 j = 0; // 725 726 for (i = 0; i < f1->numpoints; i++) 727 { 728 p1 = f1->p[i]; 729 p2 = f1->p[(i+1) % f1->numpoints]; 730 for (j = 0; j < f2->numpoints; j++) 731 { 732 p3 = f2->p[j]; 733 p4 = f2->p[(j+1) % f2->numpoints]; 734 for (k = 0; k < 3; k++) 735 { 736 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME 737 break; 738 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME 739 break; 740 } //end for 741 if (k==3) 742 break; 743 } //end for 744 if (j < f2->numpoints) 745 break; 746 } //end for 747 748 if (i == f1->numpoints) 749 return NULL; // no matching edges 750 751 // 752 // check slope of connected lines 753 // if the slopes are colinear, the point can be removed 754 // 755 back = f1->p[(i+f1->numpoints-1)%f1->numpoints]; 756 VectorSubtract (p1, back, delta); 757 CrossProduct (planenormal, delta, normal); 758 VectorNormalize (normal); 759 760 back = f2->p[(j+2)%f2->numpoints]; 761 VectorSubtract (back, p1, delta); 762 dot = DotProduct (delta, normal); 763 if (dot > CONTINUOUS_EPSILON) 764 return NULL; // not a convex polygon 765 keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON); 766 767 back = f1->p[(i+2)%f1->numpoints]; 768 VectorSubtract (back, p2, delta); 769 CrossProduct (planenormal, delta, normal); 770 VectorNormalize (normal); 771 772 back = f2->p[(j+f2->numpoints-1)%f2->numpoints]; 773 VectorSubtract (back, p2, delta); 774 dot = DotProduct (delta, normal); 775 if (dot > CONTINUOUS_EPSILON) 776 return NULL; // not a convex polygon 777 keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON); 778 779 // 780 // build the new polygon 781 // 782 newf = AllocWinding (f1->numpoints + f2->numpoints); 783 784 // copy first polygon 785 for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints) 786 { 787 if (k==(i+1)%f1->numpoints && !keep2) 788 continue; 789 790 VectorCopy (f1->p[k], newf->p[newf->numpoints]); 791 newf->numpoints++; 792 } 793 794 // copy second polygon 795 for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints) 796 { 797 if (l==(j+1)%f2->numpoints && !keep1) 798 continue; 799 VectorCopy (f2->p[l], newf->p[newf->numpoints]); 800 newf->numpoints++; 801 } 802 803 return newf; 804 } 805 806 //#ifdef ME 807 //=========================================================================== 808 // 809 // Parameter: - 810 // Returns: - 811 // Changes Globals: - 812 //=========================================================================== 813 winding_t *MergeWindings(winding_t *w1, winding_t *w2, vec3_t planenormal) 814 { 815 winding_t *neww; 816 float dist; 817 int i, j, n, found, insertafter; 818 int sides[MAX_POINTS_ON_WINDING+4]; 819 vec3_t newp[MAX_POINTS_ON_WINDING+4]; 820 int numpoints; 821 vec3_t edgevec, sepnormal, v; 822 823 RemoveEqualPoints(w1, 0.2); 824 numpoints = w1->numpoints; 825 memcpy(newp, w1->p, w1->numpoints * sizeof(vec3_t)); 826 // 827 for (i = 0; i < w2->numpoints; i++) 828 { 829 VectorCopy(w2->p[i], v); 830 for (j = 0; j < numpoints; j++) 831 { 832 VectorSubtract(newp[(j+1)%numpoints], 833 newp[(j)%numpoints], edgevec); 834 CrossProduct(edgevec, planenormal, sepnormal); 835 VectorNormalize(sepnormal); 836 if (VectorLength(sepnormal) < 0.9) 837 { 838 //remove the point from the new winding 839 for (n = j; n < numpoints-1; n++) 840 { 841 VectorCopy(newp[n+1], newp[n]); 842 sides[n] = sides[n+1]; 843 } //end for 844 numpoints--; 845 j--; 846 Log_Print("MergeWindings: degenerate edge on winding %f %f %f\n", sepnormal[0], 847 sepnormal[1], 848 sepnormal[2]); 849 continue; 850 } //end if 851 dist = DotProduct(newp[(j)%numpoints], sepnormal); 852 if (DotProduct(v, sepnormal) - dist < -0.1) sides[j] = SIDE_BACK; 853 else sides[j] = SIDE_FRONT; 854 } //end for 855 //remove all unnecesary points 856 for (j = 0; j < numpoints;) 857 { 858 if (sides[j] == SIDE_BACK 859 && sides[(j+1)%numpoints] == SIDE_BACK) 860 { 861 //remove the point from the new winding 862 for (n = (j+1)%numpoints; n < numpoints-1; n++) 863 { 864 VectorCopy(newp[n+1], newp[n]); 865 sides[n] = sides[n+1]; 866 } //end for 867 numpoints--; 868 } //end if 869 else 870 { 871 j++; 872 } //end else 873 } //end for 874 // 875 found = false; 876 for (j = 0; j < numpoints; j++) 877 { 878 if (sides[j] == SIDE_FRONT 879 && sides[(j+1)%numpoints] == SIDE_BACK) 880 { 881 if (found) Log_Print("Warning: MergeWindings: front to back found twice\n"); 882 found = true; 883 } //end if 884 } //end for 885 // 886 for (j = 0; j < numpoints; j++) 887 { 888 if (sides[j] == SIDE_FRONT 889 && sides[(j+1)%numpoints] == SIDE_BACK) 890 { 891 insertafter = (j+1)%numpoints; 892 //insert the new point after j+1 893 for (n = numpoints-1; n > insertafter; n--) 894 { 895 VectorCopy(newp[n], newp[n+1]); 896 } //end for 897 numpoints++; 898 VectorCopy(v, newp[(insertafter+1)%numpoints]); 899 break; 900 } //end if 901 } //end for 902 } //end for 903 neww = AllocWinding(numpoints); 904 neww->numpoints = numpoints; 905 memcpy(neww->p, newp, numpoints * sizeof(vec3_t)); 906 RemoveColinearPoints(neww); 907 return neww; 908 } //end of the function MergeWindings 909 //=========================================================================== 910 // 911 // Parameter: - 912 // Returns: - 913 // Changes Globals: - 914 //=========================================================================== 915 char *WindingErrorString(void) 916 { 917 return windingerror; 918 } //end of the function WindingErrorString 919 //=========================================================================== 920 // 921 // Parameter: - 922 // Returns: - 923 // Changes Globals: - 924 //=========================================================================== 925 int WindingError(winding_t *w) 926 { 927 int i, j; 928 vec_t *p1, *p2; 929 vec_t d, edgedist; 930 vec3_t dir, edgenormal, facenormal; 931 vec_t area; 932 vec_t facedist; 933 934 if (w->numpoints < 3) 935 { 936 sprintf(windingerror, "winding %i points", w->numpoints); 937 return WE_NOTENOUGHPOINTS; 938 } //end if 939 940 area = WindingArea(w); 941 if (area < 1) 942 { 943 sprintf(windingerror, "winding %f area", area); 944 return WE_SMALLAREA; 945 } //end if 946 947 WindingPlane (w, facenormal, &facedist); 948 949 for (i=0 ; i<w->numpoints ; i++) 950 { 951 p1 = w->p[i]; 952 953 for (j=0 ; j<3 ; j++) 954 { 955 if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE) 956 { 957 sprintf(windingerror, "winding point %d BUGUS_RANGE \'%f %f %f\'", j, p1[0], p1[1], p1[2]); 958 return WE_POINTBOGUSRANGE; 959 } //end if 960 } //end for 961 962 j = i+1 == w->numpoints ? 0 : i+1; 963 964 // check the point is on the face plane 965 d = DotProduct (p1, facenormal) - facedist; 966 if (d < -ON_EPSILON || d > ON_EPSILON) 967 { 968 sprintf(windingerror, "winding point %d off plane", i); 969 return WE_POINTOFFPLANE; 970 } //end if 971 972 // check the edge isnt degenerate 973 p2 = w->p[j]; 974 VectorSubtract (p2, p1, dir); 975 976 if (VectorLength (dir) < ON_EPSILON) 977 { 978 sprintf(windingerror, "winding degenerate edge %d-%d", i, j); 979 return WE_DEGENERATEEDGE; 980 } //end if 981 982 CrossProduct (facenormal, dir, edgenormal); 983 VectorNormalize (edgenormal); 984 edgedist = DotProduct (p1, edgenormal); 985 edgedist += ON_EPSILON; 986 987 // all other points must be on front side 988 for (j=0 ; j<w->numpoints ; j++) 989 { 990 if (j == i) 991 continue; 992 d = DotProduct (w->p[j], edgenormal); 993 if (d > edgedist) 994 { 995 sprintf(windingerror, "winding non-convex"); 996 return WE_NONCONVEX; 997 } //end if 998 } //end for 999 } //end for 1000 return WE_NONE; 1001 } //end of the function WindingError 1002 //=========================================================================== 1003 // 1004 // Parameter: - 1005 // Returns: - 1006 // Changes Globals: - 1007 //=========================================================================== 1008 void RemoveEqualPoints(winding_t *w, float epsilon) 1009 { 1010 int i, nump; 1011 vec3_t v; 1012 vec3_t p[MAX_POINTS_ON_WINDING]; 1013 1014 VectorCopy(w->p[0], p[0]); 1015 nump = 1; 1016 for (i = 1; i < w->numpoints; i++) 1017 { 1018 VectorSubtract(w->p[i], p[nump-1], v); 1019 if (VectorLength(v) > epsilon) 1020 { 1021 if (nump >= MAX_POINTS_ON_WINDING) 1022 Error("RemoveColinearPoints: MAX_POINTS_ON_WINDING"); 1023 VectorCopy (w->p[i], p[nump]); 1024 nump++; 1025 } //end if 1026 } //end for 1027 1028 if (nump == w->numpoints) 1029 return; 1030 1031 w->numpoints = nump; 1032 memcpy(w->p, p, nump * sizeof(p[0])); 1033 } //end of the function RemoveEqualPoints 1034 //=========================================================================== 1035 // adds the given point to a winding at the given spot 1036 // (for instance when spot is zero then the point is added at position zero) 1037 // the original winding is NOT freed 1038 // 1039 // Parameter: - 1040 // Returns: the new winding with the added point 1041 // Changes Globals: - 1042 //=========================================================================== 1043 winding_t *AddWindingPoint(winding_t *w, vec3_t point, int spot) 1044 { 1045 int i, j; 1046 winding_t *neww; 1047 1048 if (spot > w->numpoints) 1049 { 1050 Error("AddWindingPoint: num > w->numpoints"); 1051 } //end if 1052 if (spot < 0) 1053 { 1054 Error("AddWindingPoint: num < 0"); 1055 } //end if 1056 neww = AllocWinding(w->numpoints + 1); 1057 neww->numpoints = w->numpoints + 1; 1058 for (i = 0, j = 0; i < neww->numpoints; i++) 1059 { 1060 if (i == spot) 1061 { 1062 VectorCopy(point, neww->p[i]); 1063 } //end if 1064 else 1065 { 1066 VectorCopy(w->p[j], neww->p[i]); 1067 j++; 1068 } //end else 1069 } //end for 1070 return neww; 1071 } //end of the function AddWindingPoint 1072 //=========================================================================== 1073 // the position where the new point should be added in the winding is 1074 // stored in *spot 1075 // 1076 // Parameter: - 1077 // Returns: true if the point is on the winding 1078 // Changes Globals: - 1079 //=========================================================================== 1080 #define MELT_ON_EPSILON 0.2 1081 1082 int PointOnWinding(winding_t *w, vec3_t normal, float dist, vec3_t point, int *spot) 1083 { 1084 int i, j; 1085 vec3_t v1, v2; 1086 vec3_t edgenormal, edgevec; 1087 float edgedist, dot; 1088 1089 *spot = 0; 1090 //the point must be on the winding plane 1091 dot = DotProduct(point, normal) - dist; 1092 if (dot < -MELT_ON_EPSILON || dot > MELT_ON_EPSILON) return false; 1093 // 1094 for (i = 0; i < w->numpoints; i++) 1095 { 1096 j = (i+1) % w->numpoints; 1097 //get a plane orthogonal to the winding plane through the edge 1098 VectorSubtract(w->p[j], w->p[i], edgevec); 1099 CrossProduct(normal, edgevec, edgenormal); 1100 VectorNormalize(edgenormal); 1101 edgedist = DotProduct(edgenormal, w->p[i]); 1102 //point must be not too far from the plane 1103 dot = DotProduct(point, edgenormal) - edgedist; 1104 if (dot < -MELT_ON_EPSILON || dot > MELT_ON_EPSILON) continue; 1105 //vector from first point of winding to the point to test 1106 VectorSubtract(point, w->p[i], v1); 1107 //vector from second point of winding to the point to test 1108 VectorSubtract(point, w->p[j], v2); 1109 //if the length of the vector is not larger than 0.5 units then 1110 //the point is assumend to be the same as one of the winding points 1111 if (VectorNormalize(v1) < 0.5) return false; 1112 if (VectorNormalize(v2) < 0.5) return false; 1113 //point must be between the two winding points 1114 //(the two vectors must be directed towards each other, and on the 1115 //same straight line) 1116 if (DotProduct(v1, v2) < -0.99) 1117 { 1118 *spot = i + 1; 1119 return true; 1120 } //end if 1121 } //end for 1122 return false; 1123 } //end of the function PointOnWinding 1124 //=========================================================================== 1125 // 1126 // Parameter: - 1127 // Returns: - 1128 // Changes Globals: - 1129 //=========================================================================== 1130 int FindPlaneSeperatingWindings(winding_t *w1, winding_t *w2, vec3_t dir, 1131 vec3_t normal, float *dist) 1132 { 1133 int i, i2, j, j2, n; 1134 int sides1[3], sides2[3]; 1135 float dist1, dist2, dot, diff; 1136 vec3_t normal1, normal2; 1137 vec3_t v1, v2; 1138 1139 for (i = 0; i < w1->numpoints; i++) 1140 { 1141 i2 = (i+1) % w1->numpoints; 1142 // 1143 VectorSubtract(w1->p[i2], w1->p[i], v1); 1144 if (VectorLength(v1) < 0.1) 1145 { 1146 //Log_Write("FindPlaneSeperatingWindings: winding1 with degenerate edge\r\n"); 1147 continue; 1148 } //end if 1149 CrossProduct(v1, dir, normal1); 1150 VectorNormalize(normal1); 1151 dist1 = DotProduct(normal1, w1->p[i]); 1152 // 1153 for (j = 0; j < w2->numpoints; j++) 1154 { 1155 j2 = (j+1) % w2->numpoints; 1156 // 1157 VectorSubtract(w2->p[j2], w2->p[j], v2); 1158 if (VectorLength(v2) < 0.1) 1159 { 1160 //Log_Write("FindPlaneSeperatingWindings: winding2 with degenerate edge\r\n"); 1161 continue; 1162 } //end if 1163 CrossProduct(v2, dir, normal2); 1164 VectorNormalize(normal2); 1165 dist2 = DotProduct(normal2, w2->p[j]); 1166 // 1167 diff = dist1 - dist2; 1168 if (diff < -0.1 || diff > 0.1) 1169 { 1170 dist2 = -dist2; 1171 VectorNegate(normal2, normal2); 1172 diff = dist1 - dist2; 1173 if (diff < -0.1 || diff > 0.1) continue; 1174 } //end if 1175 //check if the normal vectors are equal 1176 for (n = 0; n < 3; n++) 1177 { 1178 diff = normal1[n] - normal2[n]; 1179 if (diff < -0.0001 || diff > 0.0001) break; 1180 } //end for 1181 if (n != 3) continue; 1182 //check on which side of the seperating plane the points of 1183 //the first winding are 1184 sides1[0] = sides1[1] = sides1[2] = 0; 1185 for (n = 0; n < w1->numpoints; n++) 1186 { 1187 dot = DotProduct(w1->p[n], normal1) - dist1; 1188 if (dot > 0.1) sides1[0]++; 1189 else if (dot < -0.1) sides1[1]++; 1190 else sides1[2]++; 1191 } //end for 1192 //check on which side of the seperating plane the points of 1193 //the second winding are 1194 sides2[0] = sides2[1] = sides2[2] = 0; 1195 for (n = 0; n < w2->numpoints; n++) 1196 { 1197 //used normal1 and dist1 (they are equal to normal2 and dist2) 1198 dot = DotProduct(w2->p[n], normal1) - dist1; 1199 if (dot > 0.1) sides2[0]++; 1200 else if (dot < -0.1) sides2[1]++; 1201 else sides2[2]++; 1202 } //end for 1203 //if the first winding has points at both sides 1204 if (sides1[0] && sides1[1]) 1205 { 1206 Log_Write("FindPlaneSeperatingWindings: winding1 non-convex\r\n"); 1207 continue; 1208 } //end if 1209 //if the second winding has points at both sides 1210 if (sides2[0] && sides2[1]) 1211 { 1212 Log_Write("FindPlaneSeperatingWindings: winding2 non-convex\r\n"); 1213 continue; 1214 } //end if 1215 // 1216 if ((!sides1[0] && !sides1[1]) || (!sides2[0] && !sides2[1])) 1217 { 1218 //don't use one of the winding planes as the seperating plane 1219 continue; 1220 } //end if 1221 //the windings must be at different sides of the seperating plane 1222 if ((!sides1[0] && !sides2[1]) || (!sides1[1] && !sides2[0])) 1223 { 1224 VectorCopy(normal1, normal); 1225 *dist = dist1; 1226 return true; 1227 } //end if 1228 } //end for 1229 } //end for 1230 return false; 1231 } //end of the function FindPlaneSeperatingWindings 1232 //=========================================================================== 1233 // 1234 // Parameter: - 1235 // Returns: - 1236 // Changes Globals: - 1237 //=========================================================================== 1238 #define WCONVEX_EPSILON 0.2 1239 1240 int WindingsNonConvex(winding_t *w1, winding_t *w2, 1241 vec3_t normal1, vec3_t normal2, 1242 float dist1, float dist2) 1243 { 1244 int i; 1245 1246 if (!w1 || !w2) return false; 1247 1248 //check if one of the points of face1 is at the back of the plane of face2 1249 for (i = 0; i < w1->numpoints; i++) 1250 { 1251 if (DotProduct(normal2, w1->p[i]) - dist2 > WCONVEX_EPSILON) return true; 1252 } //end for 1253 //check if one of the points of face2 is at the back of the plane of face1 1254 for (i = 0; i < w2->numpoints; i++) 1255 { 1256 if (DotProduct(normal1, w2->p[i]) - dist1 > WCONVEX_EPSILON) return true; 1257 } //end for 1258 1259 return false; 1260 } //end of the function WindingsNonConvex 1261 //=========================================================================== 1262 // 1263 // Parameter: - 1264 // Returns: - 1265 // Changes Globals: - 1266 //=========================================================================== 1267 /* 1268 #define VERTEX_EPSILON 0.5 1269 1270 qboolean EqualVertexes(vec3_t v1, vec3_t v2) 1271 { 1272 float diff; 1273 1274 diff = v1[0] - v2[0]; 1275 if (diff > -VERTEX_EPSILON && diff < VERTEX_EPSILON) 1276 { 1277 diff = v1[1] - v2[1]; 1278 if (diff > -VERTEX_EPSILON && diff < VERTEX_EPSILON) 1279 { 1280 diff = v1[2] - v2[2]; 1281 if (diff > -VERTEX_EPSILON && diff < VERTEX_EPSILON) 1282 { 1283 return true; 1284 } //end if 1285 } //end if 1286 } //end if 1287 return false; 1288 } //end of the function EqualVertexes 1289 1290 #define CONTINUOUS_EPSILON 0.001 1291 1292 winding_t *AAS_MergeWindings(winding_t *w1, winding_t *w2, vec3_t windingnormal) 1293 { 1294 int n, i, k; 1295 vec3_t normal, delta; 1296 winding_t *winding, *neww; 1297 float dist, dot; 1298 int p1, p2; 1299 int points[2][64]; 1300 int numpoints[2] = {0, 0}; 1301 int newnumpoints; 1302 int keep[2]; 1303 1304 if (!FindPlaneSeperatingWindings(w1, w2, windingnormal, normal, &dist)) return NULL; 1305 1306 //for both windings 1307 for (n = 0; n < 2; n++) 1308 { 1309 if (n == 0) winding = w1; 1310 else winding = w2; 1311 //get the points of the winding which are on the seperating plane 1312 for (i = 0; i < winding->numpoints; i++) 1313 { 1314 dot = DotProduct(winding->p[i], normal) - dist; 1315 if (dot > -ON_EPSILON && dot < ON_EPSILON) 1316 { 1317 //don't allow more than 64 points on the seperating plane 1318 if (numpoints[n] >= 64) Error("AAS_MergeWindings: more than 64 points on seperating plane\n"); 1319 points[n][numpoints[n]++] = i; 1320 } //end if 1321 } //end for 1322 //there must be at least two points of each winding on the seperating plane 1323 if (numpoints[n] < 2) return NULL; 1324 } //end for 1325 1326 //if the first point of winding1 (which is on the seperating plane) is unequal 1327 //to the last point of winding2 (which is on the seperating plane) 1328 if (!EqualVertexes(w1->p[points[0][0]], w2->p[points[1][numpoints[1]-1]])) 1329 { 1330 return NULL; 1331 } //end if 1332 //if the last point of winding1 (which is on the seperating plane) is unequal 1333 //to the first point of winding2 (which is on the seperating plane) 1334 if (!EqualVertexes(w1->p[points[0][numpoints[0]-1]], w2->p[points[1][0]])) 1335 { 1336 return NULL; 1337 } //end if 1338 // 1339 // check slope of connected lines 1340 // if the slopes are colinear, the point can be removed 1341 // 1342 //first point of winding1 which is on the seperating plane 1343 p1 = points[0][0]; 1344 //point before p1 1345 p2 = (p1 + w1->numpoints - 1) % w1->numpoints; 1346 VectorSubtract(w1->p[p1], w1->p[p2], delta); 1347 CrossProduct(windingnormal, delta, normal); 1348 VectorNormalize(normal, normal); 1349 1350 //last point of winding2 which is on the seperating plane 1351 p1 = points[1][numpoints[1]-1]; 1352 //point after p1 1353 p2 = (p1 + 1) % w2->numpoints; 1354 VectorSubtract(w2->p[p2], w2->p[p1], delta); 1355 dot = DotProduct(delta, normal); 1356 if (dot > CONTINUOUS_EPSILON) return NULL; //merging would create a non-convex polygon 1357 keep[0] = (qboolean)(dot < -CONTINUOUS_EPSILON); 1358 1359 //first point of winding2 which is on the seperating plane 1360 p1 = points[1][0]; 1361 //point before p1 1362 p2 = (p1 + w2->numpoints - 1) % w2->numpoints; 1363 VectorSubtract(w2->p[p1], w2->p[p2], delta); 1364 CrossProduct(windingnormal, delta, normal); 1365 VectorNormalize(normal, normal); 1366 1367 //last point of winding1 which is on the seperating plane 1368 p1 = points[0][numpoints[0]-1]; 1369 //point after p1 1370 p2 = (p1 + 1) % w1->numpoints; 1371 VectorSubtract(w1->p[p2], w1->p[p1], delta); 1372 dot = DotProduct(delta, normal); 1373 if (dot > CONTINUOUS_EPSILON) return NULL; //merging would create a non-convex polygon 1374 keep[1] = (qboolean)(dot < -CONTINUOUS_EPSILON); 1375 1376 //number of points on the new winding 1377 newnumpoints = w1->numpoints - numpoints[0] + w2->numpoints - numpoints[1] + 2; 1378 //allocate the winding 1379 neww = AllocWinding(newnumpoints); 1380 neww->numpoints = newnumpoints; 1381 //copy all the points 1382 k = 0; 1383 //for both windings 1384 for (n = 0; n < 2; n++) 1385 { 1386 if (n == 0) winding = w1; 1387 else winding = w2; 1388 //copy the points of the winding starting with the last point on the 1389 //seperating plane and ending before the first point on the seperating plane 1390 for (i = points[n][numpoints[n]-1]; i != points[n][0]; i = (i+1)%winding->numpoints) 1391 { 1392 if (k >= newnumpoints) 1393 { 1394 Log_Print("numpoints[0] = %d\n", numpoints[0]); 1395 Log_Print("numpoints[1] = %d\n", numpoints[1]); 1396 Error("AAS_MergeWindings: k = %d >= newnumpoints = %d\n", k, newnumpoints); 1397 } //end if 1398 VectorCopy(winding->p[i], neww->p[k]); 1399 k++; 1400 } //end for 1401 } //end for 1402 RemoveEqualPoints(neww); 1403 if (!WindingIsOk(neww, 1)) 1404 { 1405 Log_Print("AAS_MergeWindings: winding not ok after merging\n"); 1406 FreeWinding(neww); 1407 return NULL; 1408 } //end if 1409 return neww; 1410 } //end of the function AAS_MergeWindings*/ 1411 //#endif //ME