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