tools/quake3/common/polylib.c

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