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