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