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 //////////////////////////////////////////////////////////////////////
  49 // Implementation
  50 //////////////////////////////////////////////////////////////////////
  51
  52 const int BOGUS_RANGE = 4096;
  53
  54 void DWinding::AllocWinding(int points)
  55 {
  56     numpoints = points;
  57     if (p) {
  58         delete[] p;
  59     }
  60     p = new vec3_t[points];
  61 }
  62
  63 vec_t DWinding::WindingArea()
  64 {
  65     vec3_t d1, d2, cross;
  66     vec_t total;
  67
  68     total = 0;
  69     for (int i = 2; i < numpoints; i++) {
  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         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             VectorCopy(p[i], p2[nump]);
  98             nump++;
  99         }
 100     }
 101
 102     if (nump == numpoints) {
 103         return;
 104     }
 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
 122     VectorCopy(mins, p[0]);
 123     VectorCopy(maxs, p[0]);
 124
 125     for (int i = 1; i < numpoints; i++) {
 126         for (int j = 0; j < 3; j++) {
 127             vec_t v = p[i][j];
 128             if (v < mins[j]) {
 129                 mins[j] = v;
 130             }
 131             if (v > maxs[j]) {
 132                 maxs[j] = v;
 133             }
 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         vec_t d = DotProduct(p[i], normal) - dist;
 165         if (d < -ON_EPSILON) {
 166             if (front) {
 167                 return SIDE_CROSS;
 168             }
 169             back = true;
 170             continue;
 171         }
 172         if (d > ON_EPSILON) {
 173             if (back) {
 174                 return SIDE_CROSS;
 175             }
 176             front = true;
 177             continue;
 178         }
 179     }
 180
 181     if (back) {
 182         return SIDE_BACK;
 183     }
 184     if (front) {
 185         return SIDE_FRONT;
 186     }
 187     return SIDE_ON;
 188 }
 189
 190 void DWinding::CheckWinding()
 191 {
 192     vec_t *p1, *p2;
 193     vec_t edgedist;
 194     vec3_t dir, edgenormal;
 195
 196     if (numpoints < 3) {
 197         globalOutputStream() << "CheckWinding: " << numpoints << " points\n";
 198     }
 199
 200     vec_t area = WindingArea();
 201     if (area < 1) {
 202         globalOutputStream() << "CheckWinding: " << area << " area\n";
 203     }
 204
 205     DPlane *wPlane = WindingPlane();
 206     int i;
 207     for (i = 0; i < numpoints; i++) {
 208         p1 = p[i];
 209
 210         int j;
 211         for (j = 0; j < 3; j++) {
 212             if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE) {
 213                 globalOutputStream() << "CheckFace: BOGUS_RANGE: " << p1[j] << "\n";
 214             }
 215         }
 216
 217         j = i + 1 == numpoints ? 0 : i + 1;
 218
 219         // check the point is on the face plane
 220         vec_t d = DotProduct(p1, wPlane->normal) - wPlane->_d;
 221         if (d < -ON_EPSILON || d > ON_EPSILON) {
 222             globalOutputStream() << "CheckWinding: point off plane\n";
 223         }
 224
 225         // check the edge isnt degenerate
 226         p2 = p[j];
 227         VectorSubtract(p2, p1, dir);
 228
 229         if (VectorLength(dir) < ON_EPSILON) {
 230             globalOutputStream() << "CheckWinding: degenerate edge\n";
 231         }
 232
 233         CrossProduct(wPlane->normal, dir, edgenormal);
 234         VectorNormalize(edgenormal, edgenormal);
 235         edgedist = DotProduct(p1, edgenormal);
 236
 237         // all other points must be on front side
 238         for (j = 0; j < numpoints; j++) {
 239             if (j == i) {
 240                 continue;
 241             }
 242
 243             d = DotProduct(p[j], edgenormal);
 244             if (d > (edgedist + ON_EPSILON)) {
 245                 globalOutputStream() << "CheckWinding: non-convex\n";
 246             }
 247         }
 248     }
 249
 250     delete wPlane;
 251 }
 252
 253 DWinding *DWinding::ReverseWinding()
 254 {
 255     DWinding *c = new DWinding;
 256     c->AllocWinding(numpoints);
 257
 258     for (int i = 0; i < numpoints; i++)
 259         VectorCopy(p[numpoints - 1 - i], c->p[i]);
 260
 261     return c;
 262 }
 263
 264 bool DWinding::ChopWindingInPlace(DPlane *chopPlane, vec_t epsilon)
 265 {
 266     vec_t dists[MAX_POINTS_ON_WINDING + 4];
 267     int sides[MAX_POINTS_ON_WINDING + 4];
 268     int counts[3];
 269     vec_t *p1, *p2;
 270     vec3_t mid;
 271
 272     counts[0] = counts[1] = counts[2] = 0;
 273
 274 // determine sides for each point
 275     int i;
 276     for (i = 0; i < numpoints; i++) {
 277         vec_t dot = DotProduct(p[i], chopPlane->normal);
 278         dot -= chopPlane->_d;
 279         dists[i] = dot;
 280
 281         if (dot > epsilon) {
 282             sides[i] = SIDE_FRONT;
 283         } else if (dot < -epsilon) {
 284             sides[i] = SIDE_BACK;
 285         } else {
 286             sides[i] = SIDE_ON;
 287         }
 288
 289         counts[sides[i]]++;
 290     }
 291     sides[i] = sides[0];
 292     dists[i] = dists[0];
 293
 294     if (!counts[0]) {
 295         delete this;
 296         return false;
 297     }
 298
 299     if (!counts[1]) {
 300         return true;
 301     }
 302
 303     int maxpts = numpoints + 4;   // cant use counts[0]+2 because
 304     // of fp grouping errors
 305
 306     DWinding *f = new DWinding;
 307     f->AllocWinding(maxpts);
 308     f->numpoints = 0;
 309
 310     for (i = 0; i < numpoints; i++) {
 311         p1 = p[i];
 312
 313         if (sides[i] == SIDE_ON) {
 314             VectorCopy(p1, f->p[f->numpoints]);
 315             f->numpoints++;
 316             continue;
 317         }
 318
 319         if (sides[i] == SIDE_FRONT) {
 320             VectorCopy(p1, f->p[f->numpoints]);
 321             f->numpoints++;
 322         }
 323
 324         if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i]) {
 325             continue;
 326         }
 327
 328         // generate a split point
 329         p2 = p[(i + 1) % numpoints];
 330
 331         vec_t dot = dists[i] / (dists[i] - dists[i + 1]);
 332         for (int j = 0; j < 3; j++) {
 333             if (chopPlane->normal[j] == 1) {
 334                 mid[j] = chopPlane->_d;
 335             } else if (chopPlane->normal[j] == -1) {
 336                 mid[j] = -chopPlane->_d;
 337             } else {
 338                 mid[j] = p1[j] + dot * (p2[j] - p1[j]);
 339             }
 340         }
 341
 342         VectorCopy(mid, f->p[f->numpoints]);
 343         f->numpoints++;
 344     }
 345
 346     if (f->numpoints > maxpts) {
 347         globalOutputStream() << "ClipWinding: points exceeded estimate\n";
 348     }
 349     if (f->numpoints > MAX_POINTS_ON_WINDING) {
 350         globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
 351     }
 352
 353     delete[] p;
 354     p = f->p;
 355     f->p = NULL;
 356     delete f;
 357     return true;
 358 }
 359
 360 void DWinding::ClipWindingEpsilon(DPlane *chopPlane, vec_t epsilon, DWinding **front, DWinding **back)
 361 {
 362     vec_t dists[MAX_POINTS_ON_WINDING + 4];
 363     int sides[MAX_POINTS_ON_WINDING + 4];
 364     int counts[3];
 365     vec_t *p1, *p2;
 366     vec3_t mid;
 367
 368     counts[0] = counts[1] = counts[2] = 0;
 369
 370 // determine sides for each point
 371     int i;
 372     for (i = 0; i < numpoints; i++) {
 373         vec_t dot = -chopPlane->DistanceToPoint(p[i]);
 374         dists[i] = dot;
 375
 376         if (dot > epsilon) {
 377             sides[i] = SIDE_FRONT;
 378         } else if (dot < -epsilon) {
 379             sides[i] = SIDE_BACK;
 380         } else {
 381             sides[i] = SIDE_ON;
 382         }
 383
 384         counts[sides[i]]++;
 385     }
 386     sides[i] = sides[0];
 387     dists[i] = dists[0];
 388
 389     *front = *back = NULL;
 390
 391     if (!counts[0]) {
 392         *back = CopyWinding();
 393         return;
 394     }
 395     if (!counts[1]) {
 396         *front = CopyWinding();
 397         return;
 398     }
 399
 400     int maxpts = numpoints + 4;   // cant use counts[0]+2 because
 401     // of fp grouping errors
 402
 403     DWinding *f = new DWinding;
 404     DWinding *b = new DWinding;
 405
 406     f->AllocWinding(maxpts);
 407     f->numpoints = 0;
 408
 409     b->AllocWinding(maxpts);
 410     b->numpoints = 0;
 411
 412     *front = f;
 413     *back = b;
 414
 415     for (i = 0; i < numpoints; i++) {
 416         p1 = p[i];
 417
 418         if (sides[i] == SIDE_ON) {
 419             VectorCopy(p1, f->p[f->numpoints]);
 420             f->numpoints++;
 421             VectorCopy(p1, b->p[b->numpoints]);
 422             b->numpoints++;
 423             continue;
 424         }
 425
 426         if (sides[i] == SIDE_FRONT) {
 427             VectorCopy(p1, f->p[f->numpoints]);
 428             f->numpoints++;
 429         }
 430         if (sides[i] == SIDE_BACK) {
 431             VectorCopy(p1, b->p[b->numpoints]);
 432             b->numpoints++;
 433         }
 434
 435         if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i]) {
 436             continue;
 437         }
 438
 439         // generate a split point
 440         p2 = p[(i + 1) % numpoints];
 441
 442         vec_t dot = dists[i] / (dists[i] - dists[i + 1]);
 443         for (int j = 0; j < 3; j++) {
 444             if (chopPlane->normal[j] == 1) {
 445                 mid[j] = chopPlane->_d;
 446             } else if (chopPlane->normal[j] == -1) {
 447                 mid[j] = -chopPlane->_d;
 448             } else {
 449                 mid[j] = p1[j] + dot * (p2[j] - p1[j]);
 450             }
 451         }
 452
 453         VectorCopy(mid, f->p[f->numpoints]);
 454         f->numpoints++;
 455         VectorCopy(mid, b->p[b->numpoints]);
 456         b->numpoints++;
 457     }
 458
 459     if (f->numpoints > maxpts || b->numpoints > maxpts) {
 460         globalOutputStream() << "ClipWinding: points exceeded estimate\n";
 461     }
 462     if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING) {
 463         globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
 464     }
 465 }
 466
 467 bool DWinding::ChopWinding(DPlane *chopPlane)
 468 {
 469     DWinding *f, *b;
 470
 471     ClipWindingEpsilon(chopPlane, (float) ON_EPSILON, &f, &b);
 472
 473     if (b) {
 474         delete (b);
 475     }
 476
 477
 478     if (!f) {
 479         delete this;
 480         return false;
 481     }
 482
 483     delete[] p;
 484     p = f->p;
 485     f->p = NULL;
 486     numpoints = f->numpoints;
 487     delete f;
 488
 489     return true;
 490 }