tools/quake3/common/polylib.c

   1 /*
   2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 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 GtkRadiant; 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 "cmdlib.h"
  24 #include "mathlib.h"
  25 #include "inout.h"
  26 #include "polylib.h"
  27 #include "qfiles.h"
  28
  29
  30 extern int numthreads;
  31
  32 // counters are only bumped when running single threaded,
  33 // because they are an awefull coherence problem
  34 int     c_active_windings;
  35 int     c_peak_windings;
  36 int     c_winding_allocs;
  37 int     c_winding_points;
  38
  39 #define BOGUS_RANGE     WORLD_SIZE
  40
  41 void pw(winding_t *w)
  42 {
  43         int             i;
  44         for (i=0 ; i<w->numpoints ; i++)
  45                 Sys_Printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
  46 }
  47
  48
  49 /*
  50 =============
  51 AllocWinding
  52 =============
  53 */
  54 winding_t       *AllocWinding (int points)
  55 {
  56         winding_t       *w;
  57         int                     s;
  58
  59   if (points >= MAX_POINTS_ON_WINDING)
  60     Error ("AllocWinding failed: MAX_POINTS_ON_WINDING exceeded");
  61
  62         if (numthreads == 1)
  63         {
  64                 c_winding_allocs++;
  65                 c_winding_points += points;
  66                 c_active_windings++;
  67                 if (c_active_windings > c_peak_windings)
  68                         c_peak_windings = c_active_windings;
  69         }
  70         s = sizeof(vec_t)*3*points + sizeof(int);
  71         w = safe_malloc (s);
  72         memset (w, 0, s);
  73         return w;
  74 }
  75
  76 void FreeWinding (winding_t *w)
  77 {
  78         if (*(unsigned *)w == 0xdeaddead)
  79                 Error ("FreeWinding: freed a freed winding");
  80         *(unsigned *)w = 0xdeaddead;
  81
  82         if (numthreads == 1)
  83                 c_active_windings--;
  84         free (w);
  85 }
  86
  87 /*
  88 ============
  89 RemoveColinearPoints
  90 ============
  91 */
  92 int     c_removed;
  93
  94 void    RemoveColinearPoints (winding_t *w)
  95 {
  96         int             i, j, k;
  97         vec3_t  v1, v2;
  98         int             nump;
  99         vec3_t  p[MAX_POINTS_ON_WINDING];
 100
 101         nump = 0;
 102         for (i=0 ; i<w->numpoints ; i++)
 103         {
 104                 j = (i+1)%w->numpoints;
 105                 k = (i+w->numpoints-1)%w->numpoints;
 106                 VectorSubtract (w->p[j], w->p[i], v1);
 107                 VectorSubtract (w->p[i], w->p[k], v2);
 108                 VectorNormalize(v1,v1);
 109                 VectorNormalize(v2,v2);
 110                 if (DotProduct(v1, v2) < 0.999)
 111                 {
 112                         VectorCopy (w->p[i], p[nump]);
 113                         nump++;
 114                 }
 115         }
 116
 117         if (nump == w->numpoints)
 118                 return;
 119
 120         if (numthreads == 1)
 121                 c_removed += w->numpoints - nump;
 122         w->numpoints = nump;
 123         memcpy (w->p, p, nump*sizeof(p[0]));
 124 }
 125
 126 /*
 127 ============
 128 WindingPlane
 129 ============
 130 */
 131 void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
 132 {
 133         vec3_t  v1, v2;
 134
 135         VectorSubtract (w->p[1], w->p[0], v1);
 136         VectorSubtract (w->p[2], w->p[0], v2);
 137         CrossProduct (v2, v1, normal);
 138         VectorNormalize (normal, normal);
 139         *dist = DotProduct (w->p[0], normal);
 140
 141 }
 142
 143 /*
 144 =============
 145 WindingArea
 146 =============
 147 */
 148 vec_t   WindingArea (winding_t *w)
 149 {
 150         int             i;
 151         vec3_t  d1, d2, cross;
 152         vec_t   total;
 153
 154         total = 0;
 155         for (i=2 ; i<w->numpoints ; i++)
 156         {
 157                 VectorSubtract (w->p[i-1], w->p[0], d1);
 158                 VectorSubtract (w->p[i], w->p[0], d2);
 159                 CrossProduct (d1, d2, cross);
 160                 total += 0.5 * VectorLength ( cross );
 161         }
 162         return total;
 163 }
 164
 165 void    WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
 166 {
 167         vec_t   v;
 168         int             i,j;
 169
 170         mins[0] = mins[1] = mins[2] = 99999;
 171         maxs[0] = maxs[1] = maxs[2] = -99999;
 172
 173         for (i=0 ; i<w->numpoints ; i++)
 174         {
 175                 for (j=0 ; j<3 ; j++)
 176                 {
 177                         v = w->p[i][j];
 178                         if (v < mins[j])
 179                                 mins[j] = v;
 180                         if (v > maxs[j])
 181                                 maxs[j] = v;
 182                 }
 183         }
 184 }
 185
 186 /*
 187 =============
 188 WindingCenter
 189 =============
 190 */
 191 void    WindingCenter (winding_t *w, vec3_t center)
 192 {
 193         int             i;
 194         float   scale;
 195
 196         VectorCopy (vec3_origin, center);
 197         for (i=0 ; i<w->numpoints ; i++)
 198                 VectorAdd (w->p[i], center, center);
 199
 200         scale = 1.0/w->numpoints;
 201         VectorScale (center, scale, center);
 202 }
 203
 204 /*
 205 =================
 206 BaseWindingForPlane
 207 =================
 208 */
 209 winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
 210 {
 211         // The goal in this function is to replicate the exact behavior that was in the original
 212         // BaseWindingForPlane() function (see below).  The only thing we're going to change is the
 213         // accuracy of the operation.  The original code gave a preference for the vup vector to start
 214         // out as (0, 0, 1), unless the normal had a dominant Z value, in which case vup started out
 215         // as (1, 0, 0).  After that, vup was "bent" [along the plane defined by normal and vup] to
 216         // become perpendicular to normal.  After that the vright vector was computed as the cross
 217         // product of vup and normal.
 218
 219         // Once these vectors are calculated, I'm constructing the winding points in exactly the same
 220         // way as was done in the original function.  Orientation is the same.
 221
 222         // Note that the 4 points in the returned winding_t may actually not be necessary (3 might
 223         // be enough).  However, I want to minimize the chance of ANY bugs popping up due to any
 224         // change in behavior of this function.  Therefore, behavior stays exactly the same, except
 225         // for precision of math.  Performance might be better in the new function as well.
 226
 227         int             x, i;
 228         vec_t           max, v;
 229         vec3_t          vright, vup, org;
 230         winding_t       *w;
 231
 232         max = -BOGUS_RANGE;
 233         x = -1;
 234         for (i = 0; i < 3; i++) {
 235                 v = fabs(normal[i]);
 236                 if (v > max) {
 237                         x = i;
 238                         max = v;
 239                 }
 240         }
 241         if (x == -1) Error("BaseWindingForPlane: no axis found");
 242
 243         switch (x) {
 244                 case 0: // Fall through to next case.
 245                 case 1:
 246                         vright[0] = -normal[1];
 247                         vright[1] = normal[0];
 248                         vright[2] = 0;
 249                         break;
 250                 case 2:
 251                         vright[0] = 0;
 252                         vright[1] = -normal[2];
 253                         vright[2] = normal[1];
 254                         break;
 255         }
 256         CrossProduct(normal, vright, vup);
 257
 258         // IMPORTANT NOTE: vright and vup are NOT unit vectors at this point.
 259         // However, normal, vup, and vright are pairwise perpendicular.
 260
 261         VectorSetLength(vup, MAX_WORLD_COORD * 2, vup);
 262         VectorSetLength(vright, MAX_WORLD_COORD * 2, vright);
 263         VectorScale(normal, dist, org);
 264
 265         w = AllocWinding(4);
 266
 267         VectorSubtract(org, vright, w->p[0]);
 268         VectorAdd(w->p[0], vup, w->p[0]);
 269
 270         VectorAdd(org, vright, w->p[1]);
 271         VectorAdd(w->p[1], vup, w->p[1]);
 272
 273         VectorAdd(org, vright, w->p[2]);
 274         VectorSubtract(w->p[2], vup, w->p[2]);
 275
 276         VectorSubtract(org, vright, w->p[3]);
 277         VectorSubtract(w->p[3], vup, w->p[3]);
 278
 279         w->numpoints = 4;
 280
 281         return w;
 282 }
 283
 284 // Old function, not used but here for reference.  Please do not modify it.
 285 // (You may remove it at some point.)
 286 winding_t *_BaseWindingForPlane_orig_(vec3_t normal, vec_t dist)
 287 {
 288         int             i, x;
 289         vec_t   max, v;
 290         vec3_t  org, vright, vup;
 291         winding_t       *w;
 292
 293 // find the major axis
 294
 295         max = -BOGUS_RANGE;
 296         x = -1;
 297         for (i=0 ; i<3; i++)
 298         {
 299                 v = fabs(normal[i]);
 300                 if (v > max)
 301                 {
 302                         x = i;
 303                         max = v;
 304                 }
 305         }
 306         if (x==-1)
 307                 Error ("BaseWindingForPlane: no axis found");
 308
 309         VectorCopy (vec3_origin, vup);
 310         switch (x)
 311         {
 312         case 0:
 313         case 1:
 314                 vup[2] = 1;
 315                 break;
 316         case 2:
 317                 vup[0] = 1;
 318                 break;
 319         }
 320
 321         v = DotProduct (vup, normal);
 322         VectorMA (vup, -v, normal, vup);
 323         VectorNormalize (vup, vup);
 324
 325         VectorScale (normal, dist, org);
 326
 327         CrossProduct (vup, normal, vright);
 328
 329         // LordHavoc: this has to use *2 because otherwise some created points may
 330         // be inside the world (think of a diagonal case), and any brush with such
 331         // points should be removed, failure to detect such cases is disasterous
 332         VectorScale (vup, MAX_WORLD_COORD*2, vup);
 333         VectorScale (vright, MAX_WORLD_COORD*2, vright);
 334
 335   // project a really big       axis aligned box onto the plane
 336         w = AllocWinding (4);
 337
 338         VectorSubtract (org, vright, w->p[0]);
 339         VectorAdd (w->p[0], vup, w->p[0]);
 340
 341         VectorAdd (org, vright, w->p[1]);
 342         VectorAdd (w->p[1], vup, w->p[1]);
 343
 344         VectorAdd (org, vright, w->p[2]);
 345         VectorSubtract (w->p[2], vup, w->p[2]);
 346
 347         VectorSubtract (org, vright, w->p[3]);
 348         VectorSubtract (w->p[3], vup, w->p[3]);
 349
 350         w->numpoints = 4;
 351
 352         return w;
 353 }
 354
 355 /*
 356 ==================
 357 CopyWinding
 358 ==================
 359 */
 360 winding_t       *CopyWinding (winding_t *w)
 361 {
 362         size_t                  size;
 363         winding_t       *c;
 364
 365         c = AllocWinding (w->numpoints);
 366         size = (size_t)((winding_t *)NULL)->p[w->numpoints];
 367         memcpy (c, w, size);
 368         return c;
 369 }
 370
 371 /*
 372 ==================
 373 ReverseWinding
 374 ==================
 375 */
 376 winding_t       *ReverseWinding (winding_t *w)
 377 {
 378         int                     i;
 379         winding_t       *c;
 380
 381         c = AllocWinding (w->numpoints);
 382         for (i=0 ; i<w->numpoints ; i++)
 383         {
 384                 VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
 385         }
 386         c->numpoints = w->numpoints;
 387         return c;
 388 }
 389
 390
 391 /*
 392 =============
 393 ClipWindingEpsilon
 394 =============
 395 */
 396 void    ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist,
 397                                 vec_t epsilon, winding_t **front, winding_t **back)
 398 {
 399         vec_t   dists[MAX_POINTS_ON_WINDING+4];
 400         int             sides[MAX_POINTS_ON_WINDING+4];
 401         int             counts[3];
 402         static  vec_t   dot;            // VC 4.2 optimizer bug if not static
 403         int             i, j;
 404         vec_t   *p1, *p2;
 405         vec3_t  mid;
 406         winding_t       *f, *b;
 407         int             maxpts;
 408
 409         counts[0] = counts[1] = counts[2] = 0;
 410
 411 // determine sides for each point
 412         for (i=0 ; i<in->numpoints ; i++)
 413   {
 414
 415                 dot = DotProduct (in->p[i], normal);
 416                 dot -= dist;
 417                 dists[i] = dot;
 418                 if (dot > epsilon)
 419                         sides[i] = SIDE_FRONT;
 420                 else if (dot < -epsilon)
 421                         sides[i] = SIDE_BACK;
 422                 else
 423                 {
 424                         sides[i] = SIDE_ON;
 425                 }
 426                 counts[sides[i]]++;
 427         }
 428         sides[i] = sides[0];
 429         dists[i] = dists[0];
 430
 431         *front = *back = NULL;
 432
 433         if (!counts[0])
 434         {
 435                 *back = CopyWinding (in);
 436                 return;
 437         }
 438         if (!counts[1])
 439         {
 440                 *front = CopyWinding (in);
 441                 return;
 442         }
 443
 444         maxpts = in->numpoints+4;       // cant use counts[0]+2 because
 445                                                                 // of fp grouping errors
 446
 447         *front = f = AllocWinding (maxpts);
 448         *back = b = AllocWinding (maxpts);
 449
 450         for (i=0 ; i<in->numpoints ; i++)
 451         {
 452                 p1 = in->p[i];
 453
 454                 if (sides[i] == SIDE_ON)
 455                 {
 456                         VectorCopy (p1, f->p[f->numpoints]);
 457                         f->numpoints++;
 458                         VectorCopy (p1, b->p[b->numpoints]);
 459                         b->numpoints++;
 460                         continue;
 461                 }
 462
 463                 if (sides[i] == SIDE_FRONT)
 464                 {
 465                         VectorCopy (p1, f->p[f->numpoints]);
 466                         f->numpoints++;
 467                 }
 468                 if (sides[i] == SIDE_BACK)
 469                 {
 470                         VectorCopy (p1, b->p[b->numpoints]);
 471                         b->numpoints++;
 472                 }
 473
 474                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 475                         continue;
 476
 477         // generate a split point
 478                 p2 = in->p[(i+1)%in->numpoints];
 479
 480                 dot = dists[i] / (dists[i]-dists[i+1]);
 481                 for (j=0 ; j<3 ; j++)
 482                 {       // avoid round off error when possible
 483                         if (normal[j] == 1)
 484                                 mid[j] = dist;
 485                         else if (normal[j] == -1)
 486                                 mid[j] = -dist;
 487                         else
 488                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
 489                 }
 490
 491                 VectorCopy (mid, f->p[f->numpoints]);
 492                 f->numpoints++;
 493                 VectorCopy (mid, b->p[b->numpoints]);
 494                 b->numpoints++;
 495         }
 496
 497         if (f->numpoints > maxpts || b->numpoints > maxpts)
 498                 Error ("ClipWinding: points exceeded estimate");
 499         if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
 500                 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
 501 }
 502
 503
 504 /*
 505 =============
 506 ChopWindingInPlace
 507 =============
 508 */
 509 void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
 510 {
 511         winding_t       *in;
 512         vec_t   dists[MAX_POINTS_ON_WINDING+4];
 513         int             sides[MAX_POINTS_ON_WINDING+4];
 514         int             counts[3];
 515         static  vec_t   dot;            // VC 4.2 optimizer bug if not static
 516         int             i, j;
 517         vec_t   *p1, *p2;
 518         vec3_t  mid;
 519         winding_t       *f;
 520         int             maxpts;
 521
 522         in = *inout;
 523         counts[0] = counts[1] = counts[2] = 0;
 524
 525 // determine sides for each point
 526         for (i=0 ; i<in->numpoints ; i++)
 527         {
 528                 dot = DotProduct (in->p[i], normal);
 529                 dot -= dist;
 530                 dists[i] = dot;
 531                 if (dot > epsilon)
 532                         sides[i] = SIDE_FRONT;
 533                 else if (dot < -epsilon)
 534                         sides[i] = SIDE_BACK;
 535                 else
 536                 {
 537                         sides[i] = SIDE_ON;
 538                 }
 539                 counts[sides[i]]++;
 540         }
 541         sides[i] = sides[0];
 542         dists[i] = dists[0];
 543
 544         if (!counts[0])
 545         {
 546                 FreeWinding (in);
 547                 *inout = NULL;
 548                 return;
 549         }
 550         if (!counts[1])
 551                 return;         // inout stays the same
 552
 553         maxpts = in->numpoints+4;       // cant use counts[0]+2 because
 554                                                                 // of fp grouping errors
 555
 556         f = AllocWinding (maxpts);
 557
 558         for (i=0 ; i<in->numpoints ; i++)
 559         {
 560                 p1 = in->p[i];
 561
 562                 if (sides[i] == SIDE_ON)
 563                 {
 564                         VectorCopy (p1, f->p[f->numpoints]);
 565                         f->numpoints++;
 566                         continue;
 567                 }
 568
 569                 if (sides[i] == SIDE_FRONT)
 570                 {
 571                         VectorCopy (p1, f->p[f->numpoints]);
 572                         f->numpoints++;
 573                 }
 574
 575                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 576                         continue;
 577
 578         // generate a split point
 579                 p2 = in->p[(i+1)%in->numpoints];
 580
 581                 dot = dists[i] / (dists[i]-dists[i+1]);
 582                 for (j=0 ; j<3 ; j++)
 583                 {       // avoid round off error when possible
 584                         if (normal[j] == 1)
 585                                 mid[j] = dist;
 586                         else if (normal[j] == -1)
 587                                 mid[j] = -dist;
 588                         else
 589                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
 590                 }
 591
 592                 VectorCopy (mid, f->p[f->numpoints]);
 593                 f->numpoints++;
 594         }
 595
 596         if (f->numpoints > maxpts)
 597                 Error ("ClipWinding: points exceeded estimate");
 598         if (f->numpoints > MAX_POINTS_ON_WINDING)
 599                 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
 600
 601         FreeWinding (in);
 602         *inout = f;
 603 }
 604
 605
 606 /*
 607 =================
 608 ChopWinding
 609
 610 Returns the fragment of in that is on the front side
 611 of the cliping plane.  The original is freed.
 612 =================
 613 */
 614 winding_t       *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
 615 {
 616         winding_t       *f, *b;
 617
 618         ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
 619         FreeWinding (in);
 620         if (b)
 621                 FreeWinding (b);
 622         return f;
 623 }
 624
 625
 626 /*
 627 =================
 628 CheckWinding
 629
 630 =================
 631 */
 632 void CheckWinding (winding_t *w)
 633 {
 634         int             i, j;
 635         vec_t   *p1, *p2;
 636         vec_t   d, edgedist;
 637         vec3_t  dir, edgenormal, facenormal;
 638         vec_t   area;
 639         vec_t   facedist;
 640
 641         if (w->numpoints < 3)
 642                 Error ("CheckWinding: %i points",w->numpoints);
 643
 644         area = WindingArea(w);
 645         if (area < 1)
 646                 Error ("CheckWinding: %f area", area);
 647
 648         WindingPlane (w, facenormal, &facedist);
 649
 650         for (i=0 ; i<w->numpoints ; i++)
 651         {
 652                 p1 = w->p[i];
 653
 654                 for (j=0 ; j<3 ; j++)
 655                         if (p1[j] > MAX_WORLD_COORD || p1[j] < MIN_WORLD_COORD)
 656                                 Error ("CheckFace: MAX_WORLD_COORD exceeded: %f",p1[j]);
 657
 658                 j = i+1 == w->numpoints ? 0 : i+1;
 659
 660         // check the point is on the face plane
 661                 d = DotProduct (p1, facenormal) - facedist;
 662                 if (d < -ON_EPSILON || d > ON_EPSILON)
 663                         Error ("CheckWinding: point off plane");
 664
 665         // check the edge isnt degenerate
 666                 p2 = w->p[j];
 667                 VectorSubtract (p2, p1, dir);
 668
 669                 if (VectorLength (dir) < ON_EPSILON)
 670                         Error ("CheckWinding: degenerate edge");
 671
 672                 CrossProduct (facenormal, dir, edgenormal);
 673                 VectorNormalize (edgenormal, edgenormal);
 674                 edgedist = DotProduct (p1, edgenormal);
 675                 edgedist += ON_EPSILON;
 676
 677         // all other points must be on front side
 678                 for (j=0 ; j<w->numpoints ; j++)
 679                 {
 680                         if (j == i)
 681                                 continue;
 682                         d = DotProduct (w->p[j], edgenormal);
 683                         if (d > edgedist)
 684                                 Error ("CheckWinding: non-convex");
 685                 }
 686         }
 687 }
 688
 689
 690 /*
 691 ============
 692 WindingOnPlaneSide
 693 ============
 694 */
 695 int             WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
 696 {
 697         qboolean        front, back;
 698         int                     i;
 699         vec_t           d;
 700
 701         front = qfalse;
 702         back = qfalse;
 703         for (i=0 ; i<w->numpoints ; i++)
 704         {
 705                 d = DotProduct (w->p[i], normal) - dist;
 706                 if (d < -ON_EPSILON)
 707                 {
 708                         if (front)
 709                                 return SIDE_CROSS;
 710                         back = qtrue;
 711                         continue;
 712                 }
 713                 if (d > ON_EPSILON)
 714                 {
 715                         if (back)
 716                                 return SIDE_CROSS;
 717                         front = qtrue;
 718                         continue;
 719                 }
 720         }
 721
 722         if (back)
 723                 return SIDE_BACK;
 724         if (front)
 725                 return SIDE_FRONT;
 726         return SIDE_ON;
 727 }
 728
 729
 730 /*
 731 =================
 732 AddWindingToConvexHull
 733
 734 Both w and *hull are on the same plane
 735 =================
 736 */
 737 #define MAX_HULL_POINTS         128
 738 void    AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) {
 739         int                     i, j, k;
 740         float           *p, *copy;
 741         vec3_t          dir;
 742         float           d;
 743         int                     numHullPoints, numNew;
 744         vec3_t          hullPoints[MAX_HULL_POINTS];
 745         vec3_t          newHullPoints[MAX_HULL_POINTS];
 746         vec3_t          hullDirs[MAX_HULL_POINTS];
 747         qboolean        hullSide[MAX_HULL_POINTS];
 748         qboolean        outside;
 749
 750         if ( !*hull ) {
 751                 *hull = CopyWinding( w );
 752                 return;
 753         }
 754
 755         numHullPoints = (*hull)->numpoints;
 756         memcpy( hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t) );
 757
 758         for ( i = 0 ; i < w->numpoints ; i++ ) {
 759                 p = w->p[i];
 760
 761                 // calculate hull side vectors
 762                 for ( j = 0 ; j < numHullPoints ; j++ ) {
 763                         k = ( j + 1 ) % numHullPoints;
 764
 765                         VectorSubtract( hullPoints[k], hullPoints[j], dir );
 766                         VectorNormalize( dir, dir );
 767                         CrossProduct( normal, dir, hullDirs[j] );
 768                 }
 769
 770                 outside = qfalse;
 771                 for ( j = 0 ; j < numHullPoints ; j++ ) {
 772                         VectorSubtract( p, hullPoints[j], dir );
 773                         d = DotProduct( dir, hullDirs[j] );
 774                         if ( d >= ON_EPSILON ) {
 775                                 outside = qtrue;
 776                         }
 777                         if ( d >= -ON_EPSILON ) {
 778                                 hullSide[j] = qtrue;
 779                         } else {
 780                                 hullSide[j] = qfalse;
 781                         }
 782                 }
 783
 784                 // if the point is effectively inside, do nothing
 785                 if ( !outside ) {
 786                         continue;
 787                 }
 788
 789                 // find the back side to front side transition
 790                 for ( j = 0 ; j < numHullPoints ; j++ ) {
 791                         if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) {
 792                                 break;
 793                         }
 794                 }
 795                 if ( j == numHullPoints ) {
 796                         continue;
 797                 }
 798
 799                 // insert the point here
 800                 VectorCopy( p, newHullPoints[0] );
 801                 numNew = 1;
 802
 803                 // copy over all points that aren't double fronts
 804                 j = (j+1)%numHullPoints;
 805                 for ( k = 0 ; k < numHullPoints ; k++ ) {
 806                         if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) {
 807                                 continue;
 808                         }
 809                         copy = hullPoints[ (j+k+1) % numHullPoints ];
 810                         VectorCopy( copy, newHullPoints[numNew] );
 811                         numNew++;
 812                 }
 813
 814                 numHullPoints = numNew;
 815                 memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) );
 816         }
 817
 818         FreeWinding( *hull );
 819         w = AllocWinding( numHullPoints );
 820         w->numpoints = numHullPoints;
 821         *hull = w;
 822         memcpy( w->p, hullPoints, numHullPoints * sizeof(vec3_t) );
 823 }
 824
 825