contrib/bobtoolz/DWinding.cpp

   1 /*\r
   2 BobToolz plugin for GtkRadiant\r
   3 Copyright (C) 2001 Gordon Biggans\r
   4 \r
   5 This library is free software; you can redistribute it and/or\r
   6 modify it under the terms of the GNU Lesser General Public\r
   7 License as published by the Free Software Foundation; either\r
   8 version 2.1 of the License, or (at your option) any later version.\r
   9 \r
  10 This library is distributed in the hope that it will be useful,\r
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\r
  13 Lesser General Public License for more details.\r
  14 \r
  15 You should have received a copy of the GNU Lesser General Public\r
  16 License along with this library; if not, write to the Free Software\r
  17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
  18 */\r
  19 \r
  20 // DWinding.cpp: implementation of the DWinding class.\r
  21 //\r
  22 //////////////////////////////////////////////////////////////////////\r
  23 \r
  24 #include "StdAfx.h"\r
  25 #include "DWinding.h"\r
  26 #include "DPlane.h"\r
  27 #include "misc.h"\r
  28 \r
  29 //////////////////////////////////////////////////////////////////////\r
  30 // Construction/Destruction\r
  31 //////////////////////////////////////////////////////////////////////\r
  32 \r
  33 DWinding::DWinding()\r
  34 {\r
  35         numpoints = 0;\r
  36         p = NULL;\r
  37 }\r
  38 \r
  39 DWinding::~DWinding()\r
  40 {\r
  41         if(p)\r
  42                 delete[] p;\r
  43 }\r
  44 \r
  45 //////////////////////////////////////////////////////////////////////\r
  46 // Implementation\r
  47 //////////////////////////////////////////////////////////////////////\r
  48 \r
  49 #define BOGUS_RANGE     4096\r
  50 \r
  51 void DWinding::AllocWinding(int points)\r
  52 {\r
  53         numpoints = points;\r
  54         if(p)\r
  55                 delete[] p;\r
  56         p = new vec3_t[points];\r
  57 }\r
  58 \r
  59 vec_t DWinding::WindingArea()\r
  60 {\r
  61         vec3_t  d1, d2, cross;\r
  62         vec_t   total;\r
  63 \r
  64         total = 0;\r
  65         for (int i = 2; i < numpoints ; i++)\r
  66         {\r
  67                 VectorSubtract (p[i-1], p[0], d1);\r
  68                 VectorSubtract (p[i], p[0], d2);\r
  69 \r
  70                 CrossProduct (d1, d2, cross);\r
  71 \r
  72                 total += 0.5f * VectorLength ( cross );\r
  73         }\r
  74 \r
  75         return total;\r
  76 }\r
  77 \r
  78 void DWinding::RemoveColinearPoints()\r
  79 {\r
  80         vec3_t  p2[MAX_POINTS_ON_WINDING];\r
  81 \r
  82         int nump = 0;\r
  83         for (int i = 0; i < numpoints; i++)\r
  84         {\r
  85                 int j = (i+1)%numpoints;\r
  86                 int k = (i+numpoints-1)%numpoints;\r
  87 \r
  88                 vec3_t  v1, v2;\r
  89                 VectorSubtract (p[j], p[i], v1);\r
  90                 VectorSubtract (p[i], p[k], v2);\r
  91                 VectorNormalize(v1, v1);\r
  92                 VectorNormalize(v2, v2);\r
  93 \r
  94                 if (DotProduct(v1, v2) < 0.999)\r
  95                 {\r
  96                         VectorCopy (p[i], p2[nump]);\r
  97                         nump++;\r
  98                 }\r
  99         }\r
 100 \r
 101         if (nump == numpoints)\r
 102                 return;\r
 103 \r
 104         AllocWinding(nump);\r
 105         memcpy (p, p2, nump*sizeof(vec3_t));\r
 106 }\r
 107 \r
 108 DPlane* DWinding::WindingPlane()\r
 109 {\r
 110         DPlane* newPlane = new DPlane(p[0], p[1], p[2], NULL);\r
 111         return newPlane;\r
 112 }\r
 113 \r
 114 void DWinding::WindingBounds(vec3_t mins, vec3_t maxs)\r
 115 {\r
 116         if(numpoints == 0)\r
 117                 return;\r
 118 \r
 119         VectorCopy(mins, p[0]);\r
 120         VectorCopy(maxs, p[0]);\r
 121 \r
 122         for (int i = 1; i < numpoints ;i++)\r
 123         {\r
 124                 for (int j = 0; j < 3; j++)\r
 125                 {\r
 126                         vec_t v = p[i][j];\r
 127                         if (v < mins[j])\r
 128                                 mins[j] = v;\r
 129                         if (v > maxs[j])\r
 130                                 maxs[j] = v;\r
 131                 }\r
 132         }\r
 133 }\r
 134 \r
 135 void DWinding::WindingCentre(vec3_t centre)\r
 136 {\r
 137         VectorCopy (vec3_origin, centre);\r
 138         for (int i = 0; i < numpoints; i++)\r
 139                 VectorAdd (p[i], centre, centre);\r
 140 \r
 141         float scale = 1.0f/numpoints;\r
 142         VectorScale (centre, scale, centre);\r
 143 }\r
 144 \r
 145 \r
 146 DWinding* DWinding::CopyWinding()\r
 147 {\r
 148         DWinding* c = new DWinding;\r
 149         c->AllocWinding(numpoints);\r
 150         memcpy (c->p, p, numpoints*sizeof(vec3_t));\r
 151         return c;\r
 152 }\r
 153 \r
 154 \r
 155 int DWinding::WindingOnPlaneSide(vec3_t normal, vec_t dist)\r
 156 {\r
 157         bool front = FALSE;\r
 158         bool back = FALSE;\r
 159 \r
 160         for (int i = 0; i < numpoints; i++)\r
 161         {\r
 162                 vec_t d = DotProduct (p[i], normal) - dist;\r
 163                 if (d < -ON_EPSILON)\r
 164                 {\r
 165                         if (front)\r
 166                                 return SIDE_CROSS;\r
 167                         back = TRUE;\r
 168                         continue;\r
 169                 }\r
 170                 if (d > ON_EPSILON)\r
 171                 {\r
 172                         if (back)\r
 173                                 return SIDE_CROSS;\r
 174                         front = TRUE;\r
 175                         continue;\r
 176                 }\r
 177         }\r
 178 \r
 179         if (back)\r
 180                 return SIDE_BACK;\r
 181         if (front)\r
 182                 return SIDE_FRONT;\r
 183         return SIDE_ON;\r
 184 }\r
 185 \r
 186 void DWinding::CheckWinding()\r
 187 {\r
 188         vec_t   *p1, *p2;\r
 189         vec_t   edgedist;\r
 190         vec3_t  dir, edgenormal;\r
 191 \r
 192         if (numpoints < 3)\r
 193                 Sys_Printf ("CheckWinding: %i points", numpoints);\r
 194         \r
 195         vec_t area = WindingArea();\r
 196         if (area < 1)\r
 197                 Sys_Printf ("CheckWinding: %f area", area);\r
 198 \r
 199         DPlane* wPlane = WindingPlane ();\r
 200         int i;\r
 201         for (i = 0; i < numpoints; i++)\r
 202         {\r
 203                 p1 = p[i];\r
 204 \r
 205                 int j;\r
 206                 for (j = 0; j < 3; j++)\r
 207                         if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)\r
 208                                 Sys_Printf ("CheckFace: BUGUS_RANGE: %f", p1[j]);\r
 209 \r
 210                 j = i + 1 == numpoints ? 0 : i + 1;\r
 211                 \r
 212                 // check the point is on the face plane\r
 213                 vec_t d = DotProduct (p1, wPlane->normal) - wPlane->_d;\r
 214                 if (d < -ON_EPSILON || d > ON_EPSILON)\r
 215                         Sys_Printf ("CheckWinding: point off plane");\r
 216         \r
 217                 // check the edge isnt degenerate\r
 218                 p2 = p[j];\r
 219                 VectorSubtract (p2, p1, dir);\r
 220                 \r
 221                 if (VectorLength (dir) < ON_EPSILON)\r
 222                         Sys_Printf ("CheckWinding: degenerate edge");\r
 223                         \r
 224                 CrossProduct (wPlane->normal, dir, edgenormal);\r
 225                 VectorNormalize (edgenormal, edgenormal);\r
 226                 edgedist = DotProduct (p1, edgenormal);\r
 227                 \r
 228                 // all other points must be on front side\r
 229                 for (j = 0 ; j < numpoints ; j++)\r
 230                 {\r
 231                         if (j == i)\r
 232                                 continue;\r
 233 \r
 234                         d = DotProduct (p[j], edgenormal);\r
 235                         if (d > (edgedist + ON_EPSILON))\r
 236                                 Sys_Printf ("CheckWinding: non-convex");\r
 237                 }\r
 238         }\r
 239 \r
 240         delete wPlane;\r
 241 }\r
 242 \r
 243 DWinding* DWinding::ReverseWinding()\r
 244 {\r
 245         DWinding* c = new DWinding;\r
 246         c->AllocWinding(numpoints);\r
 247 \r
 248         for (int i = 0; i < numpoints ; i++)\r
 249                 VectorCopy (p[numpoints-1-i], c->p[i]);\r
 250 \r
 251         return c;\r
 252 }\r
 253 \r
 254 bool DWinding::ChopWindingInPlace(DPlane* chopPlane, vec_t epsilon)\r
 255 {\r
 256         vec_t   dists[MAX_POINTS_ON_WINDING+4];\r
 257         int             sides[MAX_POINTS_ON_WINDING+4];\r
 258         int             counts[3];\r
 259         vec_t   *p1, *p2;\r
 260         vec3_t  mid;\r
 261 \r
 262         counts[0] = counts[1] = counts[2] = 0;\r
 263 \r
 264 // determine sides for each point\r
 265         int i;\r
 266         for (i = 0; i < numpoints; i++)\r
 267         {\r
 268                 vec_t dot = DotProduct (p[i], chopPlane->normal);\r
 269                 dot -= chopPlane->_d;\r
 270                 dists[i] = dot;\r
 271                 \r
 272                 if (dot > epsilon)\r
 273                         sides[i] = SIDE_FRONT;\r
 274                 else if (dot < -epsilon)\r
 275                         sides[i] = SIDE_BACK;\r
 276                 else\r
 277                         sides[i] = SIDE_ON;\r
 278 \r
 279                 counts[sides[i]]++;\r
 280         }\r
 281         sides[i] = sides[0];\r
 282         dists[i] = dists[0];\r
 283         \r
 284         if (!counts[0])\r
 285         {\r
 286                 delete this;\r
 287                 return FALSE;\r
 288         }\r
 289 \r
 290         if (!counts[1])\r
 291                 return TRUE;\r
 292 \r
 293         int maxpts = numpoints+4;       // cant use counts[0]+2 because\r
 294                                                                 // of fp grouping errors\r
 295 \r
 296         DWinding* f = new DWinding;\r
 297         f->AllocWinding(maxpts);\r
 298         f->numpoints = 0;\r
 299                 \r
 300         for (i = 0; i < numpoints; i++)\r
 301         {\r
 302                 p1 = p[i];\r
 303                 \r
 304                 if (sides[i] == SIDE_ON)\r
 305                 {\r
 306                         VectorCopy (p1, f->p[f->numpoints]);\r
 307                         f->numpoints++;\r
 308                         continue;\r
 309                 }\r
 310         \r
 311                 if (sides[i] == SIDE_FRONT)\r
 312                 {\r
 313                         VectorCopy (p1, f->p[f->numpoints]);\r
 314                         f->numpoints++;\r
 315                 }\r
 316 \r
 317                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
 318                         continue;\r
 319                         \r
 320         // generate a split point\r
 321                 p2 = p[(i+1)%numpoints];\r
 322                 \r
 323                 vec_t dot = dists[i] / (dists[i]-dists[i+1]);\r
 324                 for (int j = 0; j < 3; j++)\r
 325                 {\r
 326                         if (chopPlane->normal[j] == 1)\r
 327                                 mid[j] = chopPlane->_d;\r
 328                         else if (chopPlane->normal[j] == -1)\r
 329                                 mid[j] = -chopPlane->_d;\r
 330                         else\r
 331                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
 332                 }\r
 333                         \r
 334                 VectorCopy (mid, f->p[f->numpoints]);\r
 335                 f->numpoints++;\r
 336         }\r
 337         \r
 338         if (f->numpoints > maxpts)\r
 339                 Sys_Printf ("ClipWinding: points exceeded estimate");\r
 340         if (f->numpoints > MAX_POINTS_ON_WINDING)\r
 341                 Sys_Printf ("ClipWinding: MAX_POINTS_ON_WINDING");\r
 342 \r
 343         delete[] p;\r
 344         p = f->p;\r
 345         f->p = NULL;\r
 346         delete f;\r
 347         return TRUE;\r
 348 }\r
 349 \r
 350 void DWinding::ClipWindingEpsilon(DPlane* chopPlane, vec_t epsilon, DWinding **front, DWinding **back)\r
 351 {\r
 352         vec_t   dists[MAX_POINTS_ON_WINDING+4];\r
 353         int             sides[MAX_POINTS_ON_WINDING+4];\r
 354         int             counts[3];\r
 355         vec_t   *p1, *p2;\r
 356         vec3_t  mid;\r
 357         \r
 358         counts[0] = counts[1] = counts[2] = 0;\r
 359 \r
 360 // determine sides for each point\r
 361         int i;\r
 362         for (i = 0; i < numpoints; i++)\r
 363         {\r
 364                 vec_t dot = -chopPlane->DistanceToPoint(p[i]);\r
 365                 dists[i] = dot;\r
 366                 \r
 367                 if (dot > epsilon)\r
 368                         sides[i] = SIDE_FRONT;\r
 369                 else if (dot < -epsilon)\r
 370                         sides[i] = SIDE_BACK;\r
 371                 else\r
 372                         sides[i] = SIDE_ON;\r
 373 \r
 374                 counts[sides[i]]++;\r
 375         }\r
 376         sides[i] = sides[0];\r
 377         dists[i] = dists[0];\r
 378         \r
 379         *front = *back = NULL;\r
 380 \r
 381         if (!counts[0])\r
 382         {\r
 383                 *back = CopyWinding();\r
 384                 return;\r
 385         }\r
 386         if (!counts[1])\r
 387         {\r
 388                 *front = CopyWinding();\r
 389                 return;\r
 390         }\r
 391 \r
 392         int maxpts = numpoints+4;       // cant use counts[0]+2 because\r
 393                                                                 // of fp grouping errors\r
 394 \r
 395         DWinding* f = new DWinding;\r
 396         DWinding* b = new DWinding;\r
 397 \r
 398         f->AllocWinding(maxpts);\r
 399         f->numpoints = 0;\r
 400 \r
 401         b->AllocWinding(maxpts);\r
 402         b->numpoints = 0;\r
 403                 \r
 404         *front = f;\r
 405         *back = b;\r
 406 \r
 407         for (i = 0; i < numpoints ; i++)\r
 408         {\r
 409                 p1 = p[i];\r
 410                 \r
 411                 if (sides[i] == SIDE_ON)\r
 412                 {\r
 413                         VectorCopy (p1, f->p[f->numpoints]);\r
 414                         f->numpoints++;\r
 415                         VectorCopy (p1, b->p[b->numpoints]);\r
 416                         b->numpoints++;\r
 417                         continue;\r
 418                 }\r
 419         \r
 420                 if (sides[i] == SIDE_FRONT)\r
 421                 {\r
 422                         VectorCopy (p1, f->p[f->numpoints]);\r
 423                         f->numpoints++;\r
 424                 }\r
 425                 if (sides[i] == SIDE_BACK)\r
 426                 {\r
 427                         VectorCopy (p1, b->p[b->numpoints]);\r
 428                         b->numpoints++;\r
 429                 }\r
 430 \r
 431                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
 432                         continue;\r
 433                         \r
 434         // generate a split point\r
 435                 p2 = p[(i+1)%numpoints];\r
 436                 \r
 437                 vec_t dot = dists[i] / (dists[i]-dists[i+1]);\r
 438                 for (int j = 0; j < 3; j++)\r
 439                 {\r
 440                         if (chopPlane->normal[j] == 1)\r
 441                                 mid[j] = chopPlane->_d;\r
 442                         else if (chopPlane->normal[j] == -1)\r
 443                                 mid[j] = -chopPlane->_d;\r
 444                         else\r
 445                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
 446                 }\r
 447                         \r
 448                 VectorCopy (mid, f->p[f->numpoints]);\r
 449                 f->numpoints++;\r
 450                 VectorCopy (mid, b->p[b->numpoints]);\r
 451                 b->numpoints++;\r
 452         }\r
 453         \r
 454         if (f->numpoints > maxpts || b->numpoints > maxpts)\r
 455                 Sys_Printf ("ClipWinding: points exceeded estimate");\r
 456         if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)\r
 457                 Sys_Printf ("ClipWinding: MAX_POINTS_ON_WINDING");\r
 458 }\r
 459 \r
 460 bool DWinding::ChopWinding(DPlane* chopPlane)\r
 461 {\r
 462         DWinding *f, *b;\r
 463 \r
 464         ClipWindingEpsilon (chopPlane, (float)ON_EPSILON, &f, &b);\r
 465 \r
 466         if (b)\r
 467                 delete (b);\r
 468 \r
 469 \r
 470         if(!f)\r
 471         {\r
 472                 delete this;\r
 473                 return FALSE;\r
 474         }\r
 475 \r
 476         delete[] p;\r
 477         p = f->p;\r
 478         f->p = NULL;\r
 479         numpoints = f->numpoints;\r
 480         delete f;\r
 481 \r
 482         return TRUE;\r
 483 }\r