contrib/bobtoolz/DWinding.cpp

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