tools/quake2/qdata_heretic2/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 "inout.h"\r
  25 #include "mathlib.h"\r
  26 #include "polylib.h"\r
  27 \r
  28 \r
  29 extern int numthreads;\r
  30 \r
  31 // counters are only bumped when running single threaded,\r
  32 // because they are an awefull coherence problem\r
  33 int     c_active_windings;\r
  34 int     c_peak_windings;\r
  35 int     c_winding_allocs;\r
  36 int     c_winding_points;\r
  37 \r
  38 #define BOGUS_RANGE     8192\r
  39 \r
  40 void pw(winding_t *w)\r
  41 {\r
  42         int             i;\r
  43         for (i=0 ; i<w->numpoints ; i++)\r
  44                 printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);\r
  45 }\r
  46 \r
  47 \r
  48 /*\r
  49 =============\r
  50 AllocWinding\r
  51 =============\r
  52 */\r
  53 winding_t       *AllocWinding (int points)\r
  54 {\r
  55         winding_t       *w;\r
  56         int                     s;\r
  57 \r
  58         if (numthreads == 1)\r
  59         {\r
  60                 c_winding_allocs++;\r
  61                 c_winding_points += points;\r
  62                 c_active_windings++;\r
  63                 if (c_active_windings > c_peak_windings)\r
  64                         c_peak_windings = c_active_windings;\r
  65         }\r
  66         s = sizeof(vec_t)*3*points + sizeof(int);\r
  67         w = malloc (s);\r
  68         if (!w)\r
  69                 Error("AllocWinding MALLOC failed!  Could not allocate %s bytes.", s);\r
  70         memset (w, 0, s); \r
  71         return w;\r
  72 }\r
  73 \r
  74 void FreeWinding (winding_t *w)\r
  75 {\r
  76         if (*(unsigned *)w == 0xdeaddead)\r
  77                 Error ("FreeWinding: freed a freed winding");\r
  78         *(unsigned *)w = 0xdeaddead;\r
  79 \r
  80         if (numthreads == 1)\r
  81                 c_active_windings--;\r
  82         free (w);\r
  83 }\r
  84 \r
  85 /*\r
  86 ============\r
  87 RemoveColinearPoints\r
  88 ============\r
  89 */\r
  90 int     c_removed;\r
  91 \r
  92 void    RemoveColinearPoints (winding_t *w)\r
  93 {\r
  94         int             i, j, k;\r
  95         vec3_t  v1, v2;\r
  96         int             nump;\r
  97         vec3_t  p[MAX_POINTS_ON_WINDING];\r
  98 \r
  99         nump = 0;\r
 100         for (i=0 ; i<w->numpoints ; i++)\r
 101         {\r
 102                 j = (i+1)%w->numpoints;\r
 103                 k = (i+w->numpoints-1)%w->numpoints;\r
 104                 VectorSubtract (w->p[j], w->p[i], v1);\r
 105                 VectorSubtract (w->p[i], w->p[k], v2);\r
 106                 VectorNormalize(v1,v1);\r
 107                 VectorNormalize(v2,v2);\r
 108                 if (DotProduct(v1, v2) < 0.999)\r
 109                 {\r
 110                         VectorCopy (w->p[i], p[nump]);\r
 111                         nump++;\r
 112                 }\r
 113         }\r
 114 \r
 115         if (nump == w->numpoints)\r
 116                 return;\r
 117 \r
 118         if (numthreads == 1)\r
 119                 c_removed += w->numpoints - nump;\r
 120         w->numpoints = nump;\r
 121         memcpy (w->p, p, nump*sizeof(p[0]));\r
 122 }\r
 123 \r
 124 /*\r
 125 ============\r
 126 WindingPlane\r
 127 ============\r
 128 */\r
 129 void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)\r
 130 {\r
 131         vec3_t  v1, v2;\r
 132 \r
 133         VectorSubtract (w->p[1], w->p[0], v1);\r
 134         VectorSubtract (w->p[2], w->p[0], v2);\r
 135         CrossProduct (v2, v1, normal);\r
 136         VectorNormalize (normal, normal);\r
 137         *dist = DotProduct (w->p[0], normal);\r
 138 \r
 139 }\r
 140 \r
 141 /*\r
 142 =============\r
 143 WindingArea\r
 144 =============\r
 145 */\r
 146 vec_t   WindingArea (winding_t *w)\r
 147 {\r
 148         int             i;\r
 149         vec3_t  d1, d2, cross;\r
 150         vec_t   total;\r
 151 \r
 152         total = 0;\r
 153         for (i=2 ; i<w->numpoints ; i++)\r
 154         {\r
 155                 VectorSubtract (w->p[i-1], w->p[0], d1);\r
 156                 VectorSubtract (w->p[i], w->p[0], d2);\r
 157                 CrossProduct (d1, d2, cross);\r
 158                 total += 0.5 * VectorLength ( cross );\r
 159         }\r
 160         return total;\r
 161 }\r
 162 \r
 163 void    WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)\r
 164 {\r
 165         vec_t   v;\r
 166         int             i,j;\r
 167 \r
 168         mins[0] = mins[1] = mins[2] = 99999;\r
 169         maxs[0] = maxs[1] = maxs[2] = -99999;\r
 170 \r
 171         for (i=0 ; i<w->numpoints ; i++)\r
 172         {\r
 173                 for (j=0 ; j<3 ; j++)\r
 174                 {\r
 175                         v = w->p[i][j];\r
 176                         if (v < mins[j])\r
 177                                 mins[j] = v;\r
 178                         if (v > maxs[j])\r
 179                                 maxs[j] = v;\r
 180                 }\r
 181         }\r
 182 }\r
 183 \r
 184 /*\r
 185 =============\r
 186 WindingCenter\r
 187 =============\r
 188 */\r
 189 void    WindingCenter (winding_t *w, vec3_t center)\r
 190 {\r
 191         int             i;\r
 192         float   scale;\r
 193 \r
 194         VectorCopy (vec3_origin, center);\r
 195         for (i=0 ; i<w->numpoints ; i++)\r
 196                 VectorAdd (w->p[i], center, center);\r
 197 \r
 198         scale = 1.0/w->numpoints;\r
 199         VectorScale (center, scale, center);\r
 200 }\r
 201 \r
 202 /*\r
 203 =================\r
 204 BaseWindingForPlane\r
 205 =================\r
 206 */\r
 207 winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)\r
 208 {\r
 209         int             i, x;\r
 210         vec_t   max, v;\r
 211         vec3_t  org, vright, vup;\r
 212         winding_t       *w;\r
 213         \r
 214 // find the major axis\r
 215 \r
 216         max = -BOGUS_RANGE;\r
 217         x = -1;\r
 218         for (i=0 ; i<3; i++)\r
 219         {\r
 220                 v = fabs(normal[i]);\r
 221                 if (v > max)\r
 222                 {\r
 223                         x = i;\r
 224                         max = v;\r
 225                 }\r
 226         }\r
 227         if (x==-1)\r
 228                 Error ("BaseWindingForPlane: no axis found");\r
 229                 \r
 230         VectorCopy (vec3_origin, vup);  \r
 231         switch (x)\r
 232         {\r
 233         case 0:\r
 234         case 1:\r
 235                 vup[2] = 1;\r
 236                 break;          \r
 237         case 2:\r
 238                 vup[0] = 1;\r
 239                 break;          \r
 240         }\r
 241 \r
 242         v = DotProduct (vup, normal);\r
 243         VectorMA (vup, -v, normal, vup);\r
 244         VectorNormalize (vup, vup);\r
 245                 \r
 246         VectorScale (normal, dist, org);\r
 247         \r
 248         CrossProduct (vup, normal, vright);\r
 249         \r
 250         VectorScale (vup, 8192, vup);\r
 251         VectorScale (vright, 8192, vright);\r
 252 \r
 253 // project a really big axis aligned box onto the plane\r
 254         w = AllocWinding (4);\r
 255         \r
 256         VectorSubtract (org, vright, w->p[0]);\r
 257         VectorAdd (w->p[0], vup, w->p[0]);\r
 258         \r
 259         VectorAdd (org, vright, w->p[1]);\r
 260         VectorAdd (w->p[1], vup, w->p[1]);\r
 261         \r
 262         VectorAdd (org, vright, w->p[2]);\r
 263         VectorSubtract (w->p[2], vup, w->p[2]);\r
 264         \r
 265         VectorSubtract (org, vright, w->p[3]);\r
 266         VectorSubtract (w->p[3], vup, w->p[3]);\r
 267         \r
 268         w->numpoints = 4;\r
 269         \r
 270         return w;       \r
 271 }\r
 272 \r
 273 /*\r
 274 ==================\r
 275 CopyWinding\r
 276 ==================\r
 277 */\r
 278 winding_t       *CopyWinding (winding_t *w)\r
 279 {\r
 280         int                     size;\r
 281         winding_t       *c;\r
 282 \r
 283         c = AllocWinding (w->numpoints);\r
 284         size = (int)((winding_t *)0)->p[w->numpoints];\r
 285         memcpy (c, w, size);\r
 286         return c;\r
 287 }\r
 288 \r
 289 /*\r
 290 ==================\r
 291 ReverseWinding\r
 292 ==================\r
 293 */\r
 294 winding_t       *ReverseWinding (winding_t *w)\r
 295 {\r
 296         int                     i;\r
 297         winding_t       *c;\r
 298 \r
 299         c = AllocWinding (w->numpoints);\r
 300         for (i=0 ; i<w->numpoints ; i++)\r
 301         {\r
 302                 VectorCopy (w->p[w->numpoints-1-i], c->p[i]);\r
 303         }\r
 304         c->numpoints = w->numpoints;\r
 305         return c;\r
 306 }\r
 307 \r
 308 \r
 309 /*\r
 310 =============\r
 311 ClipWindingEpsilon\r
 312 =============\r
 313 */\r
 314 void    ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, \r
 315                                 vec_t epsilon, winding_t **front, winding_t **back)\r
 316 {\r
 317         vec_t   dists[MAX_POINTS_ON_WINDING+4];\r
 318         int             sides[MAX_POINTS_ON_WINDING+4];\r
 319         int             counts[3];\r
 320         vec_t   dot;            // VC 4.2 optimizer bug if not static\r
 321         int             i, j;\r
 322         vec_t   *p1, *p2;\r
 323         vec3_t  mid;\r
 324         winding_t       *f, *b;\r
 325         int             maxpts;\r
 326         \r
 327         if (in->numpoints >= MAX_POINTS_ON_WINDING-4)\r
 328                 Error ("ClipWinding: MAX_POINTS_ON_WINDING");\r
 329 \r
 330         counts[0] = counts[1] = counts[2] = 0;\r
 331 \r
 332 // determine sides for each point\r
 333         for (i=0 ; i<in->numpoints ; i++)\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         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         if (!in)\r
 446         {\r
 447                 printf ("Warning: NULL passed to ChopWindingInPlace\n");\r
 448                 return;\r
 449         }\r
 450         if (in->numpoints >= MAX_POINTS_ON_WINDING-4)\r
 451                 Error ("ChopWinding: MAX_POINTS_ON_WINDING");\r
 452 \r
 453 // determine sides for each point\r
 454         for (i=0 ; i<in->numpoints ; i++)\r
 455         {\r
 456                 dot = DotProduct (in->p[i], normal);\r
 457                 dot -= dist;\r
 458                 dists[i] = dot;\r
 459                 if (dot > epsilon)\r
 460                         sides[i] = SIDE_FRONT;\r
 461                 else if (dot < -epsilon)\r
 462                         sides[i] = SIDE_BACK;\r
 463                 else\r
 464                 {\r
 465                         sides[i] = SIDE_ON;\r
 466                 }\r
 467                 counts[sides[i]]++;\r
 468         }\r
 469         sides[i] = sides[0];\r
 470         dists[i] = dists[0];\r
 471         \r
 472         if (!counts[0])\r
 473         {\r
 474                 FreeWinding (in);\r
 475                 *inout = NULL;\r
 476                 return;\r
 477         }\r
 478         if (!counts[1])\r
 479                 return;         // inout stays the same\r
 480 \r
 481         maxpts = in->numpoints+4;       // cant use counts[0]+2 because\r
 482                                                                 // of fp grouping errors\r
 483 \r
 484         f = AllocWinding (maxpts);\r
 485                 \r
 486         for (i=0 ; i<in->numpoints ; i++)\r
 487         {\r
 488                 p1 = in->p[i];\r
 489                 \r
 490                 if (sides[i] == SIDE_ON)\r
 491                 {\r
 492                         VectorCopy (p1, f->p[f->numpoints]);\r
 493                         f->numpoints++;\r
 494                         continue;\r
 495                 }\r
 496         \r
 497                 if (sides[i] == SIDE_FRONT)\r
 498                 {\r
 499                         VectorCopy (p1, f->p[f->numpoints]);\r
 500                         f->numpoints++;\r
 501                 }\r
 502 \r
 503                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
 504                         continue;\r
 505                         \r
 506         // generate a split point\r
 507                 p2 = in->p[(i+1)%in->numpoints];\r
 508                 \r
 509                 dot = dists[i] / (dists[i]-dists[i+1]);\r
 510                 for (j=0 ; j<3 ; j++)\r
 511                 {       // avoid round off error when possible\r
 512                         if (normal[j] == 1)\r
 513                                 mid[j] = dist;\r
 514                         else if (normal[j] == -1)\r
 515                                 mid[j] = -dist;\r
 516                         else\r
 517                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
 518                 }\r
 519                         \r
 520                 VectorCopy (mid, f->p[f->numpoints]);\r
 521                 f->numpoints++;\r
 522         }\r
 523         \r
 524         if (f->numpoints > maxpts)\r
 525                 Error ("ClipWinding: points exceeded estimate");\r
 526         if (f->numpoints > MAX_POINTS_ON_WINDING)\r
 527                 Error ("ClipWinding: MAX_POINTS_ON_WINDING");\r
 528 \r
 529         FreeWinding (in);\r
 530         *inout = f;\r
 531 }\r
 532 \r
 533 \r
 534 /*\r
 535 =================\r
 536 ChopWinding\r
 537 \r
 538 Returns the fragment of in that is on the front side\r
 539 of the cliping plane.  The original is freed.\r
 540 =================\r
 541 */\r
 542 winding_t       *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)\r
 543 {\r
 544         winding_t       *f, *b;\r
 545 \r
 546         ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);\r
 547         FreeWinding (in);\r
 548         if (b)\r
 549                 FreeWinding (b);\r
 550         return f;\r
 551 }\r
 552 \r
 553 \r
 554 /*\r
 555 =================\r
 556 CheckWinding\r
 557 \r
 558 =================\r
 559 */\r
 560 void CheckWinding (winding_t *w)\r
 561 {\r
 562         int             i, j;\r
 563         vec_t   *p1, *p2;\r
 564         vec_t   d, edgedist;\r
 565         vec3_t  dir, edgenormal, facenormal;\r
 566         vec_t   area;\r
 567         vec_t   facedist;\r
 568 \r
 569         if (w->numpoints < 3)\r
 570                 Error ("CheckWinding: %i points",w->numpoints);\r
 571         \r
 572         area = WindingArea(w);\r
 573         if (area < 1)\r
 574                 Error ("CheckWinding: %f area", area);\r
 575 \r
 576         WindingPlane (w, facenormal, &facedist);\r
 577         \r
 578         for (i=0 ; i<w->numpoints ; i++)\r
 579         {\r
 580                 p1 = w->p[i];\r
 581 \r
 582                 for (j=0 ; j<3 ; j++)\r
 583                         if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)\r
 584                                 Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);\r
 585 \r
 586                 j = i+1 == w->numpoints ? 0 : i+1;\r
 587                 \r
 588         // check the point is on the face plane\r
 589                 d = DotProduct (p1, facenormal) - facedist;\r
 590                 if (d < -ON_EPSILON || d > ON_EPSILON)\r
 591                         Error ("CheckWinding: point off plane");\r
 592         \r
 593         // check the edge isnt degenerate\r
 594                 p2 = w->p[j];\r
 595                 VectorSubtract (p2, p1, dir);\r
 596                 \r
 597                 if (VectorLength (dir) < ON_EPSILON)\r
 598                         Error ("CheckWinding: degenerate edge");\r
 599                         \r
 600                 CrossProduct (facenormal, dir, edgenormal);\r
 601                 VectorNormalize (edgenormal, edgenormal);\r
 602                 edgedist = DotProduct (p1, edgenormal);\r
 603                 edgedist += ON_EPSILON;\r
 604                 \r
 605         // all other points must be on front side\r
 606                 for (j=0 ; j<w->numpoints ; j++)\r
 607                 {\r
 608                         if (j == i)\r
 609                                 continue;\r
 610                         d = DotProduct (w->p[j], edgenormal);\r
 611                         if (d > edgedist)\r
 612                                 Error ("CheckWinding: non-convex");\r
 613                 }\r
 614         }\r
 615 }\r
 616 \r
 617 \r
 618 /*\r
 619 ============\r
 620 WindingOnPlaneSide\r
 621 ============\r
 622 */\r
 623 int             WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)\r
 624 {\r
 625         qboolean        front, back;\r
 626         int                     i;\r
 627         vec_t           d;\r
 628 \r
 629         front = false;\r
 630         back = false;\r
 631         for (i=0 ; i<w->numpoints ; i++)\r
 632         {\r
 633                 d = DotProduct (w->p[i], normal) - dist;\r
 634                 if (d < -ON_EPSILON)\r
 635                 {\r
 636                         if (front)\r
 637                                 return SIDE_CROSS;\r
 638                         back = true;\r
 639                         continue;\r
 640                 }\r
 641                 if (d > ON_EPSILON)\r
 642                 {\r
 643                         if (back)\r
 644                                 return SIDE_CROSS;\r
 645                         front = true;\r
 646                         continue;\r
 647                 }\r
 648         }\r
 649 \r
 650         if (back)\r
 651                 return SIDE_BACK;\r
 652         if (front)\r
 653                 return SIDE_FRONT;\r
 654         return SIDE_ON;\r
 655 }\r
 656 \r