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         numpoints = 0;
  37         p = NULL;
  38 }
  39
  40 DWinding::~DWinding(){
  41         if ( p ) {
  42                 delete[] p;
  43         }
  44 }
  45
  46 //////////////////////////////////////////////////////////////////////
  47 // Implementation
  48 //////////////////////////////////////////////////////////////////////
  49
  50 #define BOGUS_RANGE 4096
  51
  52 void DWinding::AllocWinding( int points ){
  53         numpoints = points;
  54         if ( p ) {
  55                 delete[] p;
  56         }
  57         p = new vec3_t[points];
  58 }
  59
  60 vec_t DWinding::WindingArea(){
  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         vec3_t p2[MAX_POINTS_ON_WINDING];
  80
  81         int nump = 0;
  82         for ( int i = 0; i < numpoints; i++ )
  83         {
  84                 int j = ( i + 1 ) % numpoints;
  85                 int k = ( i + numpoints - 1 ) % numpoints;
  86
  87                 vec3_t v1, v2;
  88                 VectorSubtract( p[j], p[i], v1 );
  89                 VectorSubtract( p[i], p[k], v2 );
  90                 VectorNormalize( v1, v1 );
  91                 VectorNormalize( v2, v2 );
  92
  93                 if ( DotProduct( v1, v2 ) < 0.999 ) {
  94                         VectorCopy( p[i], p2[nump] );
  95                         nump++;
  96                 }
  97         }
  98
  99         if ( nump == numpoints ) {
 100                 return;
 101         }
 102
 103         AllocWinding( nump );
 104         memcpy( p, p2, nump * sizeof( vec3_t ) );
 105 }
 106
 107 DPlane* DWinding::WindingPlane(){
 108         DPlane* newPlane = new DPlane( p[0], p[1], p[2], NULL );
 109         return newPlane;
 110 }
 111
 112 void DWinding::WindingBounds( vec3_t mins, vec3_t maxs ){
 113         if ( numpoints == 0 ) {
 114                 return;
 115         }
 116
 117         VectorCopy( mins, p[0] );
 118         VectorCopy( maxs, p[0] );
 119
 120         for ( int i = 1; i < numpoints ; i++ )
 121         {
 122                 for ( int j = 0; j < 3; j++ )
 123                 {
 124                         vec_t v = p[i][j];
 125                         if ( v < mins[j] ) {
 126                                 mins[j] = v;
 127                         }
 128                         if ( v > maxs[j] ) {
 129                                 maxs[j] = v;
 130                         }
 131                 }
 132         }
 133 }
 134
 135 void DWinding::WindingCentre( vec3_t centre ){
 136         VectorCopy( vec3_origin, centre );
 137         for ( int i = 0; i < numpoints; i++ )
 138                 VectorAdd( p[i], centre, centre );
 139
 140         float scale = 1.0f / numpoints;
 141         VectorScale( centre, scale, centre );
 142 }
 143
 144
 145 DWinding* DWinding::CopyWinding(){
 146         DWinding* c = new DWinding;
 147         c->AllocWinding( numpoints );
 148         memcpy( c->p, p, numpoints * sizeof( vec3_t ) );
 149         return c;
 150 }
 151
 152
 153 int DWinding::WindingOnPlaneSide( vec3_t normal, vec_t dist ){
 154         bool front = false;
 155         bool back = false;
 156
 157         for ( int i = 0; i < numpoints; i++ )
 158         {
 159                 vec_t d = DotProduct( p[i], normal ) - dist;
 160                 if ( d < -ON_EPSILON ) {
 161                         if ( front ) {
 162                                 return SIDE_CROSS;
 163                         }
 164                         back = true;
 165                         continue;
 166                 }
 167                 if ( d > ON_EPSILON ) {
 168                         if ( back ) {
 169                                 return SIDE_CROSS;
 170                         }
 171                         front = true;
 172                         continue;
 173                 }
 174         }
 175
 176         if ( back ) {
 177                 return SIDE_BACK;
 178         }
 179         if ( front ) {
 180                 return SIDE_FRONT;
 181         }
 182         return SIDE_ON;
 183 }
 184
 185 void DWinding::CheckWinding(){
 186         vec_t   *p1, *p2;
 187         vec_t edgedist;
 188         vec3_t dir, edgenormal;
 189
 190         if ( numpoints < 3 ) {
 191                 globalOutputStream() << "CheckWinding: " << numpoints << " points\n";
 192         }
 193
 194         vec_t area = WindingArea();
 195         if ( area < 1 ) {
 196                 globalOutputStream() << "CheckWinding: " << area << " area\n";
 197         }
 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                                 globalOutputStream() << "CheckFace: BOGUS_RANGE: " << p1[j] << "\n";
 209                         }
 210
 211                 j = i + 1 == numpoints ? 0 : i + 1;
 212
 213                 // check the point is on the face plane
 214                 vec_t d = DotProduct( p1, wPlane->normal ) - wPlane->_d;
 215                 if ( d < -ON_EPSILON || d > ON_EPSILON ) {
 216                         globalOutputStream() << "CheckWinding: point off plane\n";
 217                 }
 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
 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
 238                         d = DotProduct( p[j], edgenormal );
 239                         if ( d > ( edgedist + ON_EPSILON ) ) {
 240                                 globalOutputStream() << "CheckWinding: non-convex\n";
 241                         }
 242                 }
 243         }
 244
 245         delete wPlane;
 246 }
 247
 248 DWinding* DWinding::ReverseWinding(){
 249         DWinding* c = new DWinding;
 250         c->AllocWinding( numpoints );
 251
 252         for ( int i = 0; i < numpoints ; i++ )
 253                 VectorCopy( p[numpoints - 1 - i], c->p[i] );
 254
 255         return c;
 256 }
 257
 258 bool DWinding::ChopWindingInPlace( DPlane* chopPlane, vec_t epsilon ){
 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                 }
 278                 else if ( dot < -epsilon ) {
 279                         sides[i] = SIDE_BACK;
 280                 }
 281                 else{
 282                         sides[i] = SIDE_ON;
 283                 }
 284
 285                 counts[sides[i]]++;
 286         }
 287         sides[i] = sides[0];
 288         dists[i] = dists[0];
 289
 290         if ( !counts[0] ) {
 291                 delete this;
 292                 return false;
 293         }
 294
 295         if ( !counts[1] ) {
 296                 return true;
 297         }
 298
 299         int maxpts = numpoints + 4;   // cant use counts[0]+2 because
 300                                       // of fp grouping errors
 301
 302         DWinding* f = new DWinding;
 303         f->AllocWinding( maxpts );
 304         f->numpoints = 0;
 305
 306         for ( i = 0; i < numpoints; i++ )
 307         {
 308                 p1 = p[i];
 309
 310                 if ( sides[i] == SIDE_ON ) {
 311                         VectorCopy( p1, f->p[f->numpoints] );
 312                         f->numpoints++;
 313                         continue;
 314                 }
 315
 316                 if ( sides[i] == SIDE_FRONT ) {
 317                         VectorCopy( p1, f->p[f->numpoints] );
 318                         f->numpoints++;
 319                 }
 320
 321                 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
 322                         continue;
 323                 }
 324
 325                 // generate a split point
 326                 p2 = p[( i + 1 ) % numpoints];
 327
 328                 vec_t dot = dists[i] / ( dists[i] - dists[i + 1] );
 329                 for ( int j = 0; j < 3; j++ )
 330                 {
 331                         if ( chopPlane->normal[j] == 1 ) {
 332                                 mid[j] = chopPlane->_d;
 333                         }
 334                         else if ( chopPlane->normal[j] == -1 ) {
 335                                 mid[j] = -chopPlane->_d;
 336                         }
 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         vec_t dists[MAX_POINTS_ON_WINDING + 4];
 362         int sides[MAX_POINTS_ON_WINDING + 4];
 363         int counts[3];
 364         vec_t   *p1, *p2;
 365         vec3_t mid;
 366
 367         counts[0] = counts[1] = counts[2] = 0;
 368
 369 // determine sides for each point
 370         int i;
 371         for ( i = 0; i < numpoints; i++ )
 372         {
 373                 vec_t dot = -chopPlane->DistanceToPoint( p[i] );
 374                 dists[i] = dot;
 375
 376                 if ( dot > epsilon ) {
 377                         sides[i] = SIDE_FRONT;
 378                 }
 379                 else if ( dot < -epsilon ) {
 380                         sides[i] = SIDE_BACK;
 381                 }
 382                 else{
 383                         sides[i] = SIDE_ON;
 384                 }
 385
 386                 counts[sides[i]]++;
 387         }
 388         sides[i] = sides[0];
 389         dists[i] = dists[0];
 390
 391         *front = *back = NULL;
 392
 393         if ( !counts[0] ) {
 394                 *back = CopyWinding();
 395                 return;
 396         }
 397         if ( !counts[1] ) {
 398                 *front = CopyWinding();
 399                 return;
 400         }
 401
 402         int maxpts = numpoints + 4;   // cant use counts[0]+2 because
 403                                       // of fp grouping errors
 404
 405         DWinding* f = new DWinding;
 406         DWinding* b = new DWinding;
 407
 408         f->AllocWinding( maxpts );
 409         f->numpoints = 0;
 410
 411         b->AllocWinding( maxpts );
 412         b->numpoints = 0;
 413
 414         *front = f;
 415         *back = b;
 416
 417         for ( i = 0; i < numpoints ; i++ )
 418         {
 419                 p1 = p[i];
 420
 421                 if ( sides[i] == SIDE_ON ) {
 422                         VectorCopy( p1, f->p[f->numpoints] );
 423                         f->numpoints++;
 424                         VectorCopy( p1, b->p[b->numpoints] );
 425                         b->numpoints++;
 426                         continue;
 427                 }
 428
 429                 if ( sides[i] == SIDE_FRONT ) {
 430                         VectorCopy( p1, f->p[f->numpoints] );
 431                         f->numpoints++;
 432                 }
 433                 if ( sides[i] == SIDE_BACK ) {
 434                         VectorCopy( p1, b->p[b->numpoints] );
 435                         b->numpoints++;
 436                 }
 437
 438                 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
 439                         continue;
 440                 }
 441
 442                 // generate a split point
 443                 p2 = p[( i + 1 ) % numpoints];
 444
 445                 vec_t dot = dists[i] / ( dists[i] - dists[i + 1] );
 446                 for ( int j = 0; j < 3; j++ )
 447                 {
 448                         if ( chopPlane->normal[j] == 1 ) {
 449                                 mid[j] = chopPlane->_d;
 450                         }
 451                         else if ( chopPlane->normal[j] == -1 ) {
 452                                 mid[j] = -chopPlane->_d;
 453                         }
 454                         else{
 455                                 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
 456                         }
 457                 }
 458
 459                 VectorCopy( mid, f->p[f->numpoints] );
 460                 f->numpoints++;
 461                 VectorCopy( mid, b->p[b->numpoints] );
 462                 b->numpoints++;
 463         }
 464
 465         if ( f->numpoints > maxpts || b->numpoints > maxpts ) {
 466                 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
 467         }
 468         if ( f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING ) {
 469                 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
 470         }
 471 }
 472
 473 bool DWinding::ChopWinding( DPlane* chopPlane ){
 474         DWinding *f, *b;
 475
 476         ClipWindingEpsilon( chopPlane, (float)ON_EPSILON, &f, &b );
 477
 478         if ( b ) {
 479                 delete ( b );
 480         }
 481
 482
 483         if ( !f ) {
 484                 delete this;
 485                 return false;
 486         }
 487
 488         delete[] p;
 489         p = f->p;
 490         f->p = NULL;
 491         numpoints = f->numpoints;
 492         delete f;
 493
 494         return true;
 495 }