radiant/winding.cpp

   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 \r
  24 #include "stdafx.h"\r
  25 #include <assert.h>\r
  26 #include "winding.h"\r
  27 \r
  28 #define BOGUS_RANGE (g_MaxWorldCoord+1)\r
  29 \r
  30 /*\r
  31 =============\r
  32 Plane_Equal\r
  33 =============\r
  34 */\r
  35 #define NORMAL_EPSILON  0.0001\r
  36 #define DIST_EPSILON    0.02\r
  37 \r
  38 int Plane_Equal(plane_t *a, plane_t *b, int flip)\r
  39 {\r
  40         vec3_t normal;\r
  41         float dist;\r
  42 \r
  43         if (flip) {\r
  44                 normal[0] = - b->normal[0];\r
  45                 normal[1] = - b->normal[1];\r
  46                 normal[2] = - b->normal[2];\r
  47                 dist = - b->dist;\r
  48         }\r
  49         else {\r
  50                 normal[0] = b->normal[0];\r
  51                 normal[1] = b->normal[1];\r
  52                 normal[2] = b->normal[2];\r
  53                 dist = b->dist;\r
  54         }\r
  55         if (\r
  56            fabs(a->normal[0] - normal[0]) < NORMAL_EPSILON\r
  57         && fabs(a->normal[1] - normal[1]) < NORMAL_EPSILON\r
  58         && fabs(a->normal[2] - normal[2]) < NORMAL_EPSILON\r
  59         && fabs(a->dist - dist) < DIST_EPSILON )\r
  60                 return true;\r
  61         return false;\r
  62 }\r
  63 \r
  64 /*\r
  65 ============\r
  66 Plane_FromPoints\r
  67 ============\r
  68 */\r
  69 int Plane_FromPoints(vec3_t p1, vec3_t p2, vec3_t p3, plane_t *plane)\r
  70 {\r
  71         vec3_t v1, v2;\r
  72 \r
  73         VectorSubtract(p2, p1, v1);\r
  74         VectorSubtract(p3, p1, v2);\r
  75         //CrossProduct(v2, v1, plane->normal);\r
  76         CrossProduct(v1, v2, plane->normal);\r
  77         if (VectorNormalize(plane->normal, plane->normal) < 0.1) return false;\r
  78         plane->dist = DotProduct(p1, plane->normal);\r
  79         return true;\r
  80 }\r
  81 \r
  82 /*\r
  83 =================\r
  84 Point_Equal\r
  85 =================\r
  86 */\r
  87 int Point_Equal(vec3_t p1, vec3_t p2, float epsilon)\r
  88 {\r
  89         int i;\r
  90 \r
  91         for (i = 0; i < 3; i++)\r
  92         {\r
  93                 if (fabs(p1[i] - p2[i]) > epsilon) return false;\r
  94         }\r
  95         return true;\r
  96 }\r
  97 \r
  98 \r
  99 /*\r
 100 =================\r
 101 Winding_BaseForPlane\r
 102 =================\r
 103 */\r
 104 //#define DBG_WNDG\r
 105 winding_t *Winding_BaseForPlane (plane_t *p)\r
 106 {\r
 107         int             i, x;\r
 108         vec_t   max, v;\r
 109         vec3_t  org, vright, vup;\r
 110         winding_t       *w;\r
 111         \r
 112         // find the major axis\r
 113 #ifdef DBG_WNDG\r
 114   Sys_Printf("Winding_BaseForPlane %p\n",p);\r
 115 #endif\r
 116 \r
 117   max = -BOGUS_RANGE;\r
 118         x = -1;\r
 119         for (i=0 ; i<3; i++)\r
 120         {\r
 121                 v = fabs(p->normal[i]);\r
 122                 if (v > max)\r
 123                 {\r
 124                         x = i;\r
 125                         max = v;\r
 126                 }\r
 127         }\r
 128         if (x==-1)\r
 129                 Error ("Winding_BaseForPlane: no axis found");\r
 130                 \r
 131         VectorCopy (vec3_origin, vup);  \r
 132         switch (x)\r
 133         {\r
 134         case 0:\r
 135         case 1:\r
 136                 vup[2] = 1;\r
 137                 break;          \r
 138         case 2:\r
 139                 vup[0] = 1;\r
 140                 break;          \r
 141         }\r
 142 \r
 143 \r
 144         v = DotProduct (vup, p->normal);\r
 145         VectorMA (vup, -v, p->normal, vup);\r
 146         VectorNormalize (vup, vup);\r
 147                 \r
 148         VectorScale (p->normal, p->dist, org);\r
 149         \r
 150         CrossProduct (vup, p->normal, vright);\r
 151         \r
 152         VectorScale (vup, BOGUS_RANGE, vup);\r
 153         VectorScale (vright, BOGUS_RANGE, vright);\r
 154 \r
 155   // project a really big       axis aligned box onto the plane\r
 156         w = Winding_Alloc (4);\r
 157         \r
 158         VectorSubtract (org, vright, w->points[0]);\r
 159         VectorAdd (w->points[0], vup, w->points[0]);\r
 160         \r
 161         VectorAdd (org, vright, w->points[1]);\r
 162         VectorAdd (w->points[1], vup, w->points[1]);\r
 163         \r
 164         VectorAdd (org, vright, w->points[2]);\r
 165         VectorSubtract (w->points[2], vup, w->points[2]);\r
 166         \r
 167         VectorSubtract (org, vright, w->points[3]);\r
 168         VectorSubtract (w->points[3], vup, w->points[3]);\r
 169         \r
 170         w->numpoints = 4;\r
 171 \r
 172         return w;       \r
 173 }\r
 174 \r
 175 // macro to compute winding size\r
 176 #define WINDING_SIZE(pt) (sizeof(int)*2+sizeof(float)*5*(pt))\r
 177 \r
 178 /*\r
 179 ==================\r
 180 Winding_Alloc\r
 181 ==================\r
 182 */\r
 183 winding_t *Winding_Alloc (int points)\r
 184 {\r
 185         winding_t       *w;\r
 186         int                     size;\r
 187         \r
 188         if (points > MAX_POINTS_ON_WINDING)\r
 189                 Error ("Winding_Alloc: %i points", points);\r
 190         \r
 191 //      size = (int)((winding_t *)0)->points[points];\r
 192   size = WINDING_SIZE(points);\r
 193         w = (winding_t*) malloc (size);\r
 194         memset (w, 0, size);\r
 195         w->maxpoints = points;\r
 196         \r
 197         return w;\r
 198 }\r
 199 \r
 200 void Winding_Free (winding_t *w)\r
 201 {\r
 202         free(w);\r
 203 }\r
 204 \r
 205 /*\r
 206 ==================\r
 207 Winding_Clone\r
 208 ==================\r
 209 */\r
 210 winding_t *Winding_Clone(winding_t *w)\r
 211 {\r
 212         int                     size;\r
 213         winding_t       *c;\r
 214         \r
 215 //      size = (int)((winding_t *)0)->points[w->numpoints];\r
 216   size = WINDING_SIZE(w->numpoints);\r
 217         c = (winding_t*)qmalloc (size);\r
 218         memcpy (c, w, size);\r
 219         return c;\r
 220 }\r
 221 \r
 222 /*\r
 223 ==================\r
 224 ReverseWinding\r
 225 ==================\r
 226 */\r
 227 winding_t *Winding_Reverse(winding_t *w)\r
 228 {\r
 229         int                     i;\r
 230         winding_t       *c;\r
 231 \r
 232         c = Winding_Alloc(w->numpoints);\r
 233         for (i = 0; i < w->numpoints; i++)\r
 234         {\r
 235                 VectorCopy (w->points[w->numpoints-1-i], c->points[i]);\r
 236         }\r
 237         c->numpoints = w->numpoints;\r
 238         return c;\r
 239 }\r
 240 \r
 241 /*\r
 242 ==============\r
 243 Winding_RemovePoint\r
 244 ==============\r
 245 */\r
 246 void Winding_RemovePoint(winding_t *w, int point)\r
 247 {\r
 248         if (point < 0 || point >= w->numpoints)\r
 249                 Error("Winding_RemovePoint: point out of range");\r
 250 \r
 251         if (point < w->numpoints-1)\r
 252         {\r
 253                 memmove(&w->points[point], &w->points[point+1], (int)((winding_t *)0)->points[w->numpoints - point - 1]);\r
 254         }\r
 255         w->numpoints--;\r
 256 }\r
 257 \r
 258 /*\r
 259 =============\r
 260 Winding_InsertPoint\r
 261 =============\r
 262 */\r
 263 winding_t *Winding_InsertPoint(winding_t *w, vec3_t point, int spot)\r
 264 {\r
 265         int i, j;\r
 266         winding_t *neww;\r
 267 \r
 268         if (spot > w->numpoints)\r
 269         {\r
 270                 Error("Winding_InsertPoint: spot > w->numpoints");\r
 271         } //end if\r
 272         if (spot < 0)\r
 273         {\r
 274                 Error("Winding_InsertPoint: spot < 0");\r
 275         } //end if\r
 276         neww = Winding_Alloc(w->numpoints + 1);\r
 277         neww->numpoints = w->numpoints + 1;\r
 278         for (i = 0, j = 0; i < neww->numpoints; i++)\r
 279         {\r
 280                 if (i == spot)\r
 281                 {\r
 282                         VectorCopy(point, neww->points[i]);\r
 283                 }\r
 284                 else\r
 285                 {\r
 286                         VectorCopy(w->points[j], neww->points[i]);\r
 287                         j++;\r
 288                 }\r
 289         }\r
 290         return neww;\r
 291 }\r
 292 \r
 293 /*\r
 294 ==============\r
 295 Winding_IsTiny\r
 296 ==============\r
 297 */\r
 298 #define EDGE_LENGTH     0.2\r
 299 \r
 300 int Winding_IsTiny (winding_t *w)\r
 301 {\r
 302         int             i, j;\r
 303         vec_t   len;\r
 304         vec3_t  delta;\r
 305         int             edges;\r
 306 \r
 307         edges = 0;\r
 308         for (i=0 ; i<w->numpoints ; i++)\r
 309         {\r
 310                 j = i == w->numpoints - 1 ? 0 : i+1;\r
 311                 VectorSubtract (w->points[j], w->points[i], delta);\r
 312                 len = VectorLength (delta);\r
 313                 if (len > EDGE_LENGTH)\r
 314                 {\r
 315                         if (++edges == 3)\r
 316                                 return false;\r
 317                 }\r
 318         }\r
 319         return true;\r
 320 }\r
 321 \r
 322 /*\r
 323 ==============\r
 324 Winding_IsHuge\r
 325 ==============\r
 326 */\r
 327 int Winding_IsHuge(winding_t *w)\r
 328 {\r
 329         int             i, j;\r
 330 \r
 331         for (i=0 ; i<w->numpoints ; i++)\r
 332         {\r
 333                 for (j=0 ; j<3 ; j++)\r
 334                         if (w->points[i][j] < -BOGUS_RANGE+1 || w->points[i][j] > BOGUS_RANGE-1)\r
 335                                 return true;\r
 336         }\r
 337         return false;\r
 338 }\r
 339 \r
 340 /*\r
 341 =============\r
 342 Winding_PlanesConcave\r
 343 =============\r
 344 */\r
 345 #define WCONVEX_EPSILON         0.2\r
 346 \r
 347 int Winding_PlanesConcave(winding_t *w1, winding_t *w2,\r
 348                                                          vec3_t normal1, vec3_t normal2,\r
 349                                                          float dist1, float dist2)\r
 350 {\r
 351         int i;\r
 352 \r
 353         if (!w1 || !w2) return false;\r
 354 \r
 355         // check if one of the points of winding 1 is at the back of the plane of winding 2\r
 356         for (i = 0; i < w1->numpoints; i++)\r
 357         {\r
 358                 if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return true;\r
 359         }\r
 360         // check if one of the points of winding 2 is at the back of the plane of winding 1\r
 361         for (i = 0; i < w2->numpoints; i++)\r
 362         {\r
 363                 if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return true;\r
 364         }\r
 365 \r
 366         return false;\r
 367 }\r
 368 \r
 369 /*\r
 370 ==================\r
 371 Winding_Clip\r
 372 \r
 373 Clips the winding to the plane, returning the new winding on the positive side\r
 374 Frees the input winding.\r
 375 If keepon is true, an exactly on-plane winding will be saved, otherwise\r
 376 it will be clipped away.\r
 377 ==================\r
 378 */\r
 379 winding_t *Winding_Clip (winding_t *in, plane_t *split, qboolean keepon)\r
 380 {\r
 381         vec_t   dists[MAX_POINTS_ON_WINDING];\r
 382         int             sides[MAX_POINTS_ON_WINDING];\r
 383         int             counts[3];\r
 384         vec_t   dot;\r
 385         int             i, j;\r
 386         vec_t   *p1, *p2;\r
 387         vec3_t  mid;\r
 388         winding_t       *neww;\r
 389         int             maxpts;\r
 390         \r
 391         counts[0] = counts[1] = counts[2] = 0;\r
 392 \r
 393         // determine sides for each point\r
 394         for (i=0 ; i<in->numpoints ; i++)\r
 395         {\r
 396                 dot = DotProduct (in->points[i], split->normal);\r
 397                 dot -= split->dist;\r
 398                 dists[i] = dot;\r
 399                 if (dot > ON_EPSILON)\r
 400                         sides[i] = SIDE_FRONT;\r
 401                 else if (dot < -ON_EPSILON)\r
 402                         sides[i] = SIDE_BACK;\r
 403                 else\r
 404                 {\r
 405                         sides[i] = SIDE_ON;\r
 406                 }\r
 407                 counts[sides[i]]++;\r
 408         }\r
 409         sides[i] = sides[0];\r
 410         dists[i] = dists[0];\r
 411         \r
 412         if (keepon && !counts[0] && !counts[1])\r
 413                 return in;\r
 414                 \r
 415         if (!counts[0])\r
 416         {\r
 417                 Winding_Free (in);\r
 418                 return NULL;\r
 419         }\r
 420         if (!counts[1])\r
 421                 return in;\r
 422         \r
 423         maxpts = in->numpoints+4;       // can't use counts[0]+2 because\r
 424                                                                 // of fp grouping errors\r
 425         neww = Winding_Alloc (maxpts);\r
 426                 \r
 427         for (i=0 ; i<in->numpoints ; i++)\r
 428         {\r
 429                 p1 = in->points[i];\r
 430                 \r
 431                 if (sides[i] == SIDE_ON)\r
 432                 {\r
 433                         VectorCopy (p1, neww->points[neww->numpoints]);\r
 434                         neww->numpoints++;\r
 435                         continue;\r
 436                 }\r
 437         \r
 438                 if (sides[i] == SIDE_FRONT)\r
 439                 {\r
 440                         VectorCopy (p1, neww->points[neww->numpoints]);\r
 441                         neww->numpoints++;\r
 442                 }\r
 443                 \r
 444                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
 445                         continue;\r
 446                         \r
 447                 // generate a split point\r
 448                 p2 = in->points[(i+1)%in->numpoints];\r
 449                 \r
 450                 dot = dists[i] / (dists[i]-dists[i+1]);\r
 451                 for (j=0 ; j<3 ; j++)\r
 452                 {       // avoid round off error when possible\r
 453                         if (split->normal[j] == 1)\r
 454                                 mid[j] = split->dist;\r
 455                         else if (split->normal[j] == -1)\r
 456                                 mid[j] = -split->dist;\r
 457                         else\r
 458                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
 459                 }\r
 460                         \r
 461                 VectorCopy (mid, neww->points[neww->numpoints]);\r
 462                 neww->numpoints++;\r
 463         }\r
 464         \r
 465         if (neww->numpoints > maxpts)\r
 466                 Error ("Winding_Clip: points exceeded estimate");\r
 467                 \r
 468         // free the original winding\r
 469         Winding_Free (in);\r
 470         \r
 471         return neww;\r
 472 }\r
 473 \r
 474 /*\r
 475 =============\r
 476 Winding_SplitEpsilon\r
 477 \r
 478   split the input winding with the plane\r
 479   the input winding stays untouched\r
 480 =============\r
 481 */\r
 482 void Winding_SplitEpsilon (winding_t *in, vec3_t normal, double dist, \r
 483                                 vec_t epsilon, winding_t **front, winding_t **back)\r
 484 {\r
 485         vec_t   dists[MAX_POINTS_ON_WINDING+4];\r
 486         int             sides[MAX_POINTS_ON_WINDING+4];\r
 487         int             counts[3];\r
 488         vec_t   dot;\r
 489         int             i, j;\r
 490         vec_t   *p1, *p2;\r
 491         vec3_t  mid;\r
 492         winding_t       *f, *b;\r
 493         int             maxpts;\r
 494         \r
 495         counts[0] = counts[1] = counts[2] = 0;\r
 496 \r
 497         // determine sides for each point\r
 498         for (i = 0; i < in->numpoints; i++)\r
 499         {\r
 500                 dot = DotProduct (in->points[i], normal);\r
 501                 dot -= dist;\r
 502                 dists[i] = dot;\r
 503                 if (dot > epsilon)\r
 504                         sides[i] = SIDE_FRONT;\r
 505                 else if (dot < -epsilon)\r
 506                         sides[i] = SIDE_BACK;\r
 507                 else\r
 508                 {\r
 509                         sides[i] = SIDE_ON;\r
 510                 }\r
 511                 counts[sides[i]]++;\r
 512         }\r
 513         sides[i] = sides[0];\r
 514         dists[i] = dists[0];\r
 515         \r
 516         *front = *back = NULL;\r
 517 \r
 518         if (!counts[0])\r
 519         {\r
 520                 *back = Winding_Clone(in);\r
 521                 return;\r
 522         }\r
 523         if (!counts[1])\r
 524         {\r
 525                 *front = Winding_Clone(in);\r
 526                 return;\r
 527         }\r
 528 \r
 529         maxpts = in->numpoints+4;       // cant use counts[0]+2 because\r
 530                                                                 // of fp grouping errors\r
 531 \r
 532         *front = f = Winding_Alloc (maxpts);\r
 533         *back = b = Winding_Alloc (maxpts);\r
 534                 \r
 535         for (i = 0; i < in->numpoints; i++)\r
 536         {\r
 537                 p1 = in->points[i];\r
 538                 \r
 539                 if (sides[i] == SIDE_ON)\r
 540                 {\r
 541                         VectorCopy (p1, f->points[f->numpoints]);\r
 542                         f->numpoints++;\r
 543                         VectorCopy (p1, b->points[b->numpoints]);\r
 544                         b->numpoints++;\r
 545                         continue;\r
 546                 }\r
 547         \r
 548                 if (sides[i] == SIDE_FRONT)\r
 549                 {\r
 550                         VectorCopy (p1, f->points[f->numpoints]);\r
 551                         f->numpoints++;\r
 552                 }\r
 553                 if (sides[i] == SIDE_BACK)\r
 554                 {\r
 555                         VectorCopy (p1, b->points[b->numpoints]);\r
 556                         b->numpoints++;\r
 557                 }\r
 558 \r
 559                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
 560                         continue;\r
 561                         \r
 562                 // generate a split point\r
 563                 p2 = in->points[(i+1)%in->numpoints];\r
 564                 \r
 565                 dot = dists[i] / (dists[i]-dists[i+1]);\r
 566                 for (j = 0; j < 3; j++)\r
 567                 {\r
 568                         // avoid round off error when possible\r
 569                         if (normal[j] == 1)\r
 570                                 mid[j] = dist;\r
 571                         else if (normal[j] == -1)\r
 572                                 mid[j] = -dist;\r
 573                         else\r
 574                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
 575                 }\r
 576                         \r
 577                 VectorCopy (mid, f->points[f->numpoints]);\r
 578                 f->numpoints++;\r
 579                 VectorCopy (mid, b->points[b->numpoints]);\r
 580                 b->numpoints++;\r
 581         }\r
 582         \r
 583         if (f->numpoints > maxpts || b->numpoints > maxpts)\r
 584                 Error ("Winding_Clip: points exceeded estimate");\r
 585         if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)\r
 586                 Error ("Winding_Clip: MAX_POINTS_ON_WINDING");\r
 587 }\r
 588 \r
 589 /*\r
 590 =============\r
 591 Winding_TryMerge\r
 592 \r
 593 If two windings share a common edge and the edges that meet at the\r
 594 common points are both inside the other polygons, merge them\r
 595 \r
 596 Returns NULL if the windings couldn't be merged, or the new winding.\r
 597 The originals will NOT be freed.\r
 598 \r
 599 if keep is true no points are ever removed\r
 600 =============\r
 601 */\r
 602 #define CONTINUOUS_EPSILON      0.005\r
 603 \r
 604 winding_t *Winding_TryMerge(winding_t *f1, winding_t *f2, vec3_t planenormal, int keep)\r
 605 {\r
 606         vec_t           *p1, *p2, *p3, *p4, *back;\r
 607         winding_t       *newf;\r
 608         int                     i, j, k, l;\r
 609         vec3_t          normal, delta;\r
 610         vec_t           dot;\r
 611         qboolean        keep1, keep2;\r
 612         \r
 613 \r
 614         //\r
 615         // find a common edge\r
 616         //      \r
 617         p1 = p2 = NULL; // stop compiler warning\r
 618         j = 0;                  // \r
 619         \r
 620         for (i = 0; i < f1->numpoints; i++)\r
 621         {\r
 622                 p1 = f1->points[i];\r
 623                 p2 = f1->points[(i+1) % f1->numpoints];\r
 624                 for (j = 0; j < f2->numpoints; j++)\r
 625                 {\r
 626                         p3 = f2->points[j];\r
 627                         p4 = f2->points[(j+1) % f2->numpoints];\r
 628                         for (k = 0; k < 3; k++)\r
 629                         {\r
 630                                 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME\r
 631                                         break;\r
 632                                 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME\r
 633                                         break;\r
 634                         } //end for\r
 635                         if (k==3)\r
 636                                 break;\r
 637                 } //end for\r
 638                 if (j < f2->numpoints)\r
 639                         break;\r
 640         } //end for\r
 641         \r
 642         if (i == f1->numpoints)\r
 643                 return NULL;                    // no matching edges\r
 644 \r
 645         //\r
 646         // check slope of connected lines\r
 647         // if the slopes are colinear, the point can be removed\r
 648         //\r
 649         back = f1->points[(i+f1->numpoints-1)%f1->numpoints];\r
 650         VectorSubtract (p1, back, delta);\r
 651         CrossProduct (planenormal, delta, normal);\r
 652         VectorNormalize (normal, normal);\r
 653         \r
 654         back = f2->points[(j+2)%f2->numpoints];\r
 655         VectorSubtract (back, p1, delta);\r
 656         dot = DotProduct (delta, normal);\r
 657         if (dot > CONTINUOUS_EPSILON)\r
 658                 return NULL;                    // not a convex polygon\r
 659         keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);\r
 660         \r
 661         back = f1->points[(i+2)%f1->numpoints];\r
 662         VectorSubtract (back, p2, delta);\r
 663         CrossProduct (planenormal, delta, normal);\r
 664         VectorNormalize (normal, normal);\r
 665 \r
 666         back = f2->points[(j+f2->numpoints-1)%f2->numpoints];\r
 667         VectorSubtract (back, p2, delta);\r
 668         dot = DotProduct (delta, normal);\r
 669         if (dot > CONTINUOUS_EPSILON)\r
 670                 return NULL;                    // not a convex polygon\r
 671         keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);\r
 672 \r
 673         //\r
 674         // build the new polygon\r
 675         //\r
 676         newf = Winding_Alloc (f1->numpoints + f2->numpoints);\r
 677         \r
 678         // copy first polygon\r
 679         for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)\r
 680         {\r
 681                 if (!keep && k==(i+1)%f1->numpoints && !keep2)\r
 682                         continue;\r
 683                 \r
 684                 VectorCopy (f1->points[k], newf->points[newf->numpoints]);\r
 685                 newf->numpoints++;\r
 686         }\r
 687         \r
 688         // copy second polygon\r
 689         for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)\r
 690         {\r
 691                 if (!keep && l==(j+1)%f2->numpoints && !keep1)\r
 692                         continue;\r
 693                 VectorCopy (f2->points[l], newf->points[newf->numpoints]);\r
 694                 newf->numpoints++;\r
 695         }\r
 696 \r
 697         return newf;\r
 698 }\r
 699 \r
 700 /*\r
 701 ============\r
 702 Winding_Plane\r
 703 ============\r
 704 */\r
 705 void Winding_Plane (winding_t *w, vec3_t normal, double *dist)\r
 706 {\r
 707         vec3_t v1, v2;\r
 708         int i;\r
 709 \r
 710         //find two vectors each longer than 0.5 units\r
 711         for (i = 0; i < w->numpoints; i++)\r
 712         {\r
 713                 VectorSubtract(w->points[(i+1) % w->numpoints], w->points[i], v1);\r
 714                 VectorSubtract(w->points[(i+2) % w->numpoints], w->points[i], v2);\r
 715                 if (VectorLength(v1) > 0.5 && VectorLength(v2) > 0.5) break;\r
 716         }\r
 717         CrossProduct(v2, v1, normal);\r
 718         VectorNormalize(normal, normal);\r
 719         *dist = DotProduct(w->points[0], normal);\r
 720 }\r
 721 \r
 722 /*\r
 723 =============\r
 724 Winding_Area\r
 725 =============\r
 726 */\r
 727 float Winding_Area (winding_t *w)\r
 728 {\r
 729         int             i;\r
 730         vec3_t  d1, d2, cross;\r
 731         float   total;\r
 732 \r
 733         total = 0;\r
 734         for (i=2 ; i<w->numpoints ; i++)\r
 735         {\r
 736                 VectorSubtract (w->points[i-1], w->points[0], d1);\r
 737                 VectorSubtract (w->points[i], w->points[0], d2);\r
 738                 CrossProduct (d1, d2, cross);\r
 739                 total += 0.5 * VectorLength ( cross );\r
 740         }\r
 741         return total;\r
 742 }\r
 743 \r
 744 /*\r
 745 =============\r
 746 Winding_Bounds\r
 747 =============\r
 748 */\r
 749 void Winding_Bounds (winding_t *w, vec3_t mins, vec3_t maxs)\r
 750 {\r
 751         vec_t   v;\r
 752         int             i,j;\r
 753 \r
 754         mins[0] = mins[1] = mins[2] = 99999;\r
 755         maxs[0] = maxs[1] = maxs[2] = -99999;\r
 756 \r
 757         for (i=0 ; i<w->numpoints ; i++)\r
 758         {\r
 759                 for (j=0 ; j<3 ; j++)\r
 760                 {\r
 761                         v = w->points[i][j];\r
 762                         if (v < mins[j])\r
 763                                 mins[j] = v;\r
 764                         if (v > maxs[j])\r
 765                                 maxs[j] = v;\r
 766                 }\r
 767         }\r
 768 }\r
 769 \r
 770 \r
 771 /*\r
 772 =================\r
 773 Winding_PointInside\r
 774 =================\r
 775 */\r
 776 int Winding_PointInside(winding_t *w, plane_t *plane, vec3_t point, float epsilon)\r
 777 {\r
 778         int i;\r
 779         vec3_t dir, normal, pointvec;\r
 780 \r
 781         for (i = 0; i < w->numpoints; i++)\r
 782         {\r
 783                 VectorSubtract(w->points[(i+1) % w->numpoints], w->points[i], dir);\r
 784                 VectorSubtract(point, w->points[i], pointvec);\r
 785                 //\r
 786                 CrossProduct(dir, plane->normal, normal);\r
 787                 //\r
 788                 if (DotProduct(pointvec, normal) < -epsilon) return false;\r
 789         }\r
 790         return true;\r
 791 }\r
 792 \r
 793 /*\r
 794 =================\r
 795 Winding_VectorIntersect\r
 796 =================\r
 797 */\r
 798 int Winding_VectorIntersect(winding_t *w, plane_t *plane, vec3_t p1, vec3_t p2, float epsilon)\r
 799 {\r
 800         float front, back, frac;\r
 801         vec3_t mid;\r
 802 \r
 803         front = DotProduct(p1, plane->normal) - plane->dist;\r
 804         back = DotProduct(p2, plane->normal) - plane->dist;\r
 805         //if both points at the same side of the plane\r
 806         if (front < -epsilon && back < -epsilon) return false;\r
 807         if (front > epsilon && back > epsilon) return false;\r
 808         //get point of intersection with winding plane\r
 809         if (fabs(front-back) < 0.001)\r
 810         {\r
 811                 VectorCopy(p2, mid);\r
 812         }\r
 813         else\r
 814         {\r
 815                 frac = front/(front-back);\r
 816                 mid[0] = p1[0] + (p2[0] - p1[0]) * frac;\r
 817                 mid[1] = p1[1] + (p2[1] - p1[1]) * frac;\r
 818                 mid[2] = p1[2] + (p2[2] - p1[2]) * frac;\r
 819         }\r
 820         return Winding_PointInside(w, plane, mid, epsilon);\r
 821 }\r
 822 \r