radiant/winding.cpp

   1 /*
   2    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3    For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5    This file is part of GtkRadiant.
   6
   7    GtkRadiant is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    GtkRadiant is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GtkRadiant; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  */
  21
  22
  23
  24 #include "stdafx.h"
  25 #include <assert.h>
  26 #include "winding.h"
  27
  28 #define BOGUS_RANGE ( g_MaxWorldCoord + 1 )
  29
  30 /*
  31    =============
  32    Plane_Equal
  33    =============
  34  */
  35 #define NORMAL_EPSILON  0.0001
  36 #define DIST_EPSILON    0.02
  37
  38 int Plane_Equal( plane_t *a, plane_t *b, int flip ){
  39         vec3_t normal;
  40         float dist;
  41
  42         if ( flip ) {
  43                 normal[0] = -b->normal[0];
  44                 normal[1] = -b->normal[1];
  45                 normal[2] = -b->normal[2];
  46                 dist = -b->dist;
  47         }
  48         else {
  49                 normal[0] = b->normal[0];
  50                 normal[1] = b->normal[1];
  51                 normal[2] = b->normal[2];
  52                 dist = b->dist;
  53         }
  54         if (
  55                 fabs( a->normal[0] - normal[0] ) < NORMAL_EPSILON
  56                 && fabs( a->normal[1] - normal[1] ) < NORMAL_EPSILON
  57                 && fabs( a->normal[2] - normal[2] ) < NORMAL_EPSILON
  58                 && fabs( a->dist - dist ) < DIST_EPSILON ) {
  59                 return true;
  60         }
  61         return false;
  62 }
  63
  64 /*
  65    ============
  66    Plane_FromPoints
  67    ============
  68  */
  69 int Plane_FromPoints( vec3_t p1, vec3_t p2, vec3_t p3, plane_t *plane ){
  70         vec3_t v1, v2;
  71
  72         VectorSubtract( p2, p1, v1 );
  73         VectorSubtract( p3, p1, v2 );
  74         //CrossProduct(v2, v1, plane->normal);
  75         CrossProduct( v1, v2, plane->normal );
  76         if ( VectorNormalize( plane->normal, plane->normal ) < 0.1 ) {
  77                 return false;
  78         }
  79         plane->dist = DotProduct( p1, plane->normal );
  80         return true;
  81 }
  82
  83 /*
  84    =================
  85    Point_Equal
  86    =================
  87  */
  88 int Point_Equal( vec3_t p1, vec3_t p2, float epsilon ){
  89         int i;
  90
  91         for ( i = 0; i < 3; i++ )
  92         {
  93                 if ( fabs( p1[i] - p2[i] ) > epsilon ) {
  94                         return false;
  95                 }
  96         }
  97         return true;
  98 }
  99
 100
 101 /*
 102    =================
 103    Winding_BaseForPlane
 104    =================
 105  */
 106 //#define DBG_WNDG
 107 winding_t *Winding_BaseForPlane( plane_t *p ){
 108         int i, x;
 109         vec_t max, v;
 110         vec3_t org, vright, vup;
 111         winding_t   *w;
 112
 113         // find the major axis
 114 #ifdef DBG_WNDG
 115         Sys_Printf( "Winding_BaseForPlane %p\n",p );
 116 #endif
 117
 118         max = -BOGUS_RANGE;
 119         x = -1;
 120         for ( i = 0 ; i < 3; i++ )
 121         {
 122                 v = fabs( p->normal[i] );
 123                 if ( v > max ) {
 124                         x = i;
 125                         max = v;
 126                 }
 127         }
 128         if ( x == -1 ) {
 129                 Error( "Winding_BaseForPlane: no axis found" );
 130         }
 131
 132         VectorCopy( vec3_origin, vup );
 133         switch ( x )
 134         {
 135         case 0:
 136         case 1:
 137                 vup[2] = 1;
 138                 break;
 139         case 2:
 140                 vup[0] = 1;
 141                 break;
 142         }
 143
 144
 145         v = DotProduct( vup, p->normal );
 146         VectorMA( vup, -v, p->normal, vup );
 147         VectorNormalize( vup, vup );
 148
 149         VectorScale( p->normal, p->dist, org );
 150
 151         CrossProduct( vup, p->normal, vright );
 152
 153         VectorScale( vup, BOGUS_RANGE, vup );
 154         VectorScale( vright, BOGUS_RANGE, vright );
 155
 156         // project a really big axis aligned box onto the plane
 157         w = Winding_Alloc( 4 );
 158
 159         VectorSubtract( org, vright, w->points[0] );
 160         VectorAdd( w->points[0], vup, w->points[0] );
 161
 162         VectorAdd( org, vright, w->points[1] );
 163         VectorAdd( w->points[1], vup, w->points[1] );
 164
 165         VectorAdd( org, vright, w->points[2] );
 166         VectorSubtract( w->points[2], vup, w->points[2] );
 167
 168         VectorSubtract( org, vright, w->points[3] );
 169         VectorSubtract( w->points[3], vup, w->points[3] );
 170
 171         w->numpoints = 4;
 172
 173         return w;
 174 }
 175
 176 // macro to compute winding size
 177 #define WINDING_SIZE( pt ) ( sizeof( int )*2 + sizeof( float )*5*( pt ) )
 178
 179 /*
 180    ==================
 181    Winding_Alloc
 182    ==================
 183  */
 184 winding_t *Winding_Alloc( int points ){
 185         winding_t   *w;
 186         int size;
 187
 188         if ( points > MAX_POINTS_ON_WINDING ) {
 189                 Error( "Winding_Alloc: %i points", points );
 190         }
 191
 192 //      size = (int)((winding_t *)0)->points[points];
 193         size = WINDING_SIZE( points );
 194         w = (winding_t*) malloc( size );
 195         memset( w, 0, size );
 196         w->maxpoints = points;
 197
 198         return w;
 199 }
 200
 201 void Winding_Free( winding_t *w ){
 202         free( w );
 203 }
 204
 205 /*
 206    ==================
 207    Winding_Clone
 208    ==================
 209  */
 210 winding_t *Winding_Clone( winding_t *w ){
 211         int size;
 212         winding_t   *c;
 213
 214 //      size = (int)((winding_t *)0)->points[w->numpoints];
 215         size = WINDING_SIZE( w->numpoints );
 216         c = (winding_t*)qmalloc( size );
 217         memcpy( c, w, size );
 218         return c;
 219 }
 220
 221 /*
 222    ==================
 223    ReverseWinding
 224    ==================
 225  */
 226 winding_t *Winding_Reverse( winding_t *w ){
 227         int i;
 228         winding_t   *c;
 229
 230         c = Winding_Alloc( w->numpoints );
 231         for ( i = 0; i < w->numpoints; i++ )
 232         {
 233                 VectorCopy( w->points[w->numpoints - 1 - i], c->points[i] );
 234         }
 235         c->numpoints = w->numpoints;
 236         return c;
 237 }
 238
 239 /*
 240    ==============
 241    Winding_RemovePoint
 242    ==============
 243  */
 244 void Winding_RemovePoint( winding_t *w, int point ){
 245         if ( point < 0 || point >= w->numpoints ) {
 246                 Error( "Winding_RemovePoint: point out of range" );
 247         }
 248
 249         if ( point < w->numpoints - 1 ) {
 250                 memmove( &w->points[point], &w->points[point + 1], (size_t)( (winding_t *)0 )->points[w->numpoints - point - 1] );
 251         }
 252         w->numpoints--;
 253 }
 254
 255 /*
 256    =============
 257    Winding_InsertPoint
 258    =============
 259  */
 260 winding_t *Winding_InsertPoint( winding_t *w, vec3_t point, int spot ){
 261         int i, j;
 262         winding_t *neww;
 263
 264         if ( spot > w->numpoints ) {
 265                 Error( "Winding_InsertPoint: spot > w->numpoints" );
 266         } //end if
 267         if ( spot < 0 ) {
 268                 Error( "Winding_InsertPoint: spot < 0" );
 269         } //end if
 270         neww = Winding_Alloc( w->numpoints + 1 );
 271         neww->numpoints = w->numpoints + 1;
 272         for ( i = 0, j = 0; i < neww->numpoints; i++ )
 273         {
 274                 if ( i == spot ) {
 275                         VectorCopy( point, neww->points[i] );
 276                 }
 277                 else
 278                 {
 279                         VectorCopy( w->points[j], neww->points[i] );
 280                         j++;
 281                 }
 282         }
 283         return neww;
 284 }
 285
 286 /*
 287    ==============
 288    Winding_IsTiny
 289    ==============
 290  */
 291 #define EDGE_LENGTH 0.2
 292
 293 int Winding_IsTiny( winding_t *w ){
 294         int i, j;
 295         vec_t len;
 296         vec3_t delta;
 297         int edges;
 298
 299         edges = 0;
 300         for ( i = 0 ; i < w->numpoints ; i++ )
 301         {
 302                 j = i == w->numpoints - 1 ? 0 : i + 1;
 303                 VectorSubtract( w->points[j], w->points[i], delta );
 304                 len = VectorLength( delta );
 305                 if ( len > EDGE_LENGTH ) {
 306                         if ( ++edges == 3 ) {
 307                                 return false;
 308                         }
 309                 }
 310         }
 311         return true;
 312 }
 313
 314 /*
 315    ==============
 316    Winding_IsHuge
 317    ==============
 318  */
 319 int Winding_IsHuge( winding_t *w ){
 320         int i, j;
 321
 322         for ( i = 0 ; i < w->numpoints ; i++ )
 323         {
 324                 for ( j = 0 ; j < 3 ; j++ )
 325                         if ( w->points[i][j] < -BOGUS_RANGE + 1 || w->points[i][j] > BOGUS_RANGE - 1 ) {
 326                                 return true;
 327                         }
 328         }
 329         return false;
 330 }
 331
 332 /*
 333    =============
 334    Winding_PlanesConcave
 335    =============
 336  */
 337 #define WCONVEX_EPSILON     0.2
 338
 339 int Winding_PlanesConcave( winding_t *w1, winding_t *w2,
 340                                                    vec3_t normal1, vec3_t normal2,
 341                                                    float dist1, float dist2 ){
 342         int i;
 343
 344         if ( !w1 || !w2 ) {
 345                 return false;
 346         }
 347
 348         // check if one of the points of winding 1 is at the back of the plane of winding 2
 349         for ( i = 0; i < w1->numpoints; i++ )
 350         {
 351                 if ( DotProduct( normal2, w1->points[i] ) - dist2 > WCONVEX_EPSILON ) {
 352                         return true;
 353                 }
 354         }
 355         // check if one of the points of winding 2 is at the back of the plane of winding 1
 356         for ( i = 0; i < w2->numpoints; i++ )
 357         {
 358                 if ( DotProduct( normal1, w2->points[i] ) - dist1 > WCONVEX_EPSILON ) {
 359                         return true;
 360                 }
 361         }
 362
 363         return false;
 364 }
 365
 366 /*
 367    ==================
 368    Winding_Clip
 369
 370    Clips the winding to the plane, returning the new winding on the positive side
 371    Frees the input winding.
 372    If keepon is true, an exactly on-plane winding will be saved, otherwise
 373    it will be clipped away.
 374    ==================
 375  */
 376 winding_t *Winding_Clip( winding_t *in, plane_t *split, qboolean keepon ){
 377         vec_t dists[MAX_POINTS_ON_WINDING];
 378         int sides[MAX_POINTS_ON_WINDING];
 379         int counts[3];
 380         vec_t dot;
 381         int i, j;
 382         vec_t   *p1, *p2;
 383         vec3_t mid;
 384         winding_t   *neww;
 385         int maxpts;
 386
 387         counts[0] = counts[1] = counts[2] = 0;
 388
 389         // determine sides for each point
 390         for ( i = 0 ; i < in->numpoints ; i++ )
 391         {
 392                 dot = DotProduct( in->points[i], split->normal );
 393                 dot -= split->dist;
 394                 dists[i] = dot;
 395                 if ( dot > ON_EPSILON ) {
 396                         sides[i] = SIDE_FRONT;
 397                 }
 398                 else if ( dot < -ON_EPSILON ) {
 399                         sides[i] = SIDE_BACK;
 400                 }
 401                 else
 402                 {
 403                         sides[i] = SIDE_ON;
 404                 }
 405                 counts[sides[i]]++;
 406         }
 407         sides[i] = sides[0];
 408         dists[i] = dists[0];
 409
 410         if ( keepon && !counts[0] && !counts[1] ) {
 411                 return in;
 412         }
 413
 414         if ( !counts[0] ) {
 415                 Winding_Free( in );
 416                 return NULL;
 417         }
 418         if ( !counts[1] ) {
 419                 return in;
 420         }
 421
 422         maxpts = in->numpoints + 4;   // can't use counts[0]+2 because
 423                                       // of fp grouping errors
 424         neww = Winding_Alloc( maxpts );
 425
 426         for ( i = 0 ; i < in->numpoints ; i++ )
 427         {
 428                 p1 = in->points[i];
 429
 430                 if ( sides[i] == SIDE_ON ) {
 431                         VectorCopy( p1, neww->points[neww->numpoints] );
 432                         neww->numpoints++;
 433                         continue;
 434                 }
 435
 436                 if ( sides[i] == SIDE_FRONT ) {
 437                         VectorCopy( p1, neww->points[neww->numpoints] );
 438                         neww->numpoints++;
 439                 }
 440
 441                 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
 442                         continue;
 443                 }
 444
 445                 // generate a split point
 446                 p2 = in->points[( i + 1 ) % in->numpoints];
 447
 448                 dot = dists[i] / ( dists[i] - dists[i + 1] );
 449                 for ( j = 0 ; j < 3 ; j++ )
 450                 {   // avoid round off error when possible
 451                         if ( split->normal[j] == 1 ) {
 452                                 mid[j] = split->dist;
 453                         }
 454                         else if ( split->normal[j] == -1 ) {
 455                                 mid[j] = -split->dist;
 456                         }
 457                         else{
 458                                 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
 459                         }
 460                 }
 461
 462                 VectorCopy( mid, neww->points[neww->numpoints] );
 463                 neww->numpoints++;
 464         }
 465
 466         if ( neww->numpoints > maxpts ) {
 467                 Error( "Winding_Clip: points exceeded estimate" );
 468         }
 469
 470         // free the original winding
 471         Winding_Free( in );
 472
 473         return neww;
 474 }
 475
 476 /*
 477    =============
 478    Winding_SplitEpsilon
 479
 480    split the input winding with the plane
 481    the input winding stays untouched
 482    =============
 483  */
 484 void Winding_SplitEpsilon( winding_t *in, vec3_t normal, double dist,
 485                                                    vec_t epsilon, winding_t **front, winding_t **back ){
 486         vec_t dists[MAX_POINTS_ON_WINDING + 4];
 487         int sides[MAX_POINTS_ON_WINDING + 4];
 488         int counts[3];
 489         vec_t dot;
 490         int i, j;
 491         vec_t   *p1, *p2;
 492         vec3_t mid;
 493         winding_t   *f, *b;
 494         int maxpts;
 495
 496         counts[0] = counts[1] = counts[2] = 0;
 497
 498         // determine sides for each point
 499         for ( i = 0; i < in->numpoints; i++ )
 500         {
 501                 dot = DotProduct( in->points[i], normal );
 502                 dot -= dist;
 503                 dists[i] = dot;
 504                 if ( dot > epsilon ) {
 505                         sides[i] = SIDE_FRONT;
 506                 }
 507                 else if ( dot < -epsilon ) {
 508                         sides[i] = SIDE_BACK;
 509                 }
 510                 else
 511                 {
 512                         sides[i] = SIDE_ON;
 513                 }
 514                 counts[sides[i]]++;
 515         }
 516         sides[i] = sides[0];
 517         dists[i] = dists[0];
 518
 519         *front = *back = NULL;
 520
 521         if ( !counts[0] ) {
 522                 *back = Winding_Clone( in );
 523                 return;
 524         }
 525         if ( !counts[1] ) {
 526                 *front = Winding_Clone( in );
 527                 return;
 528         }
 529
 530         maxpts = in->numpoints + 4;   // cant use counts[0]+2 because
 531                                       // of fp grouping errors
 532
 533         *front = f = Winding_Alloc( maxpts );
 534         *back = b = Winding_Alloc( maxpts );
 535
 536         for ( i = 0; i < in->numpoints; i++ )
 537         {
 538                 p1 = in->points[i];
 539
 540                 if ( sides[i] == SIDE_ON ) {
 541                         VectorCopy( p1, f->points[f->numpoints] );
 542                         f->numpoints++;
 543                         VectorCopy( p1, b->points[b->numpoints] );
 544                         b->numpoints++;
 545                         continue;
 546                 }
 547
 548                 if ( sides[i] == SIDE_FRONT ) {
 549                         VectorCopy( p1, f->points[f->numpoints] );
 550                         f->numpoints++;
 551                 }
 552                 if ( sides[i] == SIDE_BACK ) {
 553                         VectorCopy( p1, b->points[b->numpoints] );
 554                         b->numpoints++;
 555                 }
 556
 557                 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
 558                         continue;
 559                 }
 560
 561                 // generate a split point
 562                 p2 = in->points[( i + 1 ) % in->numpoints];
 563
 564                 dot = dists[i] / ( dists[i] - dists[i + 1] );
 565                 for ( j = 0; j < 3; j++ )
 566                 {
 567                         // avoid round off error when possible
 568                         if ( normal[j] == 1 ) {
 569                                 mid[j] = dist;
 570                         }
 571                         else if ( normal[j] == -1 ) {
 572                                 mid[j] = -dist;
 573                         }
 574                         else{
 575                                 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
 576                         }
 577                 }
 578
 579                 VectorCopy( mid, f->points[f->numpoints] );
 580                 f->numpoints++;
 581                 VectorCopy( mid, b->points[b->numpoints] );
 582                 b->numpoints++;
 583         }
 584
 585         if ( f->numpoints > maxpts || b->numpoints > maxpts ) {
 586                 Error( "Winding_Clip: points exceeded estimate" );
 587         }
 588         if ( f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING ) {
 589                 Error( "Winding_Clip: MAX_POINTS_ON_WINDING" );
 590         }
 591 }
 592
 593 /*
 594    =============
 595    Winding_TryMerge
 596
 597    If two windings share a common edge and the edges that meet at the
 598    common points are both inside the other polygons, merge them
 599
 600    Returns NULL if the windings couldn't be merged, or the new winding.
 601    The originals will NOT be freed.
 602
 603    if keep is true no points are ever removed
 604    =============
 605  */
 606 #define CONTINUOUS_EPSILON  0.005
 607
 608 winding_t *Winding_TryMerge( winding_t *f1, winding_t *f2, vec3_t planenormal, int keep ){
 609         vec_t       *p1, *p2, *p3, *p4, *back;
 610         winding_t   *newf;
 611         int i, j, k, l;
 612         vec3_t normal, delta;
 613         vec_t dot;
 614         qboolean keep1, keep2;
 615
 616
 617         //
 618         // find a common edge
 619         //
 620         p1 = p2 = NULL; // stop compiler warning
 621         j = 0;          //
 622
 623         for ( i = 0; i < f1->numpoints; i++ )
 624         {
 625                 p1 = f1->points[i];
 626                 p2 = f1->points[( i + 1 ) % f1->numpoints];
 627                 for ( j = 0; j < f2->numpoints; j++ )
 628                 {
 629                         p3 = f2->points[j];
 630                         p4 = f2->points[( j + 1 ) % f2->numpoints];
 631                         for ( k = 0; k < 3; k++ )
 632                         {
 633                                 if ( fabs( p1[k] - p4[k] ) > 0.1 ) { //EQUAL_EPSILON) //ME
 634                                         break;
 635                                 }
 636                                 if ( fabs( p2[k] - p3[k] ) > 0.1 ) { //EQUAL_EPSILON) //ME
 637                                         break;
 638                                 }
 639                         } //end for
 640                         if ( k == 3 ) {
 641                                 break;
 642                         }
 643                 } //end for
 644                 if ( j < f2->numpoints ) {
 645                         break;
 646                 }
 647         } //end for
 648
 649         if ( i == f1->numpoints ) {
 650                 return NULL;            // no matching edges
 651
 652         }
 653         //
 654         // check slope of connected lines
 655         // if the slopes are colinear, the point can be removed
 656         //
 657         back = f1->points[( i + f1->numpoints - 1 ) % f1->numpoints];
 658         VectorSubtract( p1, back, delta );
 659         CrossProduct( planenormal, delta, normal );
 660         VectorNormalize( normal, normal );
 661
 662         back = f2->points[( j + 2 ) % f2->numpoints];
 663         VectorSubtract( back, p1, delta );
 664         dot = DotProduct( delta, normal );
 665         if ( dot > CONTINUOUS_EPSILON ) {
 666                 return NULL;            // not a convex polygon
 667         }
 668         keep1 = (qboolean)( dot < -CONTINUOUS_EPSILON );
 669
 670         back = f1->points[( i + 2 ) % f1->numpoints];
 671         VectorSubtract( back, p2, delta );
 672         CrossProduct( planenormal, delta, normal );
 673         VectorNormalize( normal, normal );
 674
 675         back = f2->points[( j + f2->numpoints - 1 ) % f2->numpoints];
 676         VectorSubtract( back, p2, delta );
 677         dot = DotProduct( delta, normal );
 678         if ( dot > CONTINUOUS_EPSILON ) {
 679                 return NULL;            // not a convex polygon
 680         }
 681         keep2 = (qboolean)( dot < -CONTINUOUS_EPSILON );
 682
 683         //
 684         // build the new polygon
 685         //
 686         newf = Winding_Alloc( f1->numpoints + f2->numpoints );
 687
 688         // copy first polygon
 689         for ( k = ( i + 1 ) % f1->numpoints ; k != i ; k = ( k + 1 ) % f1->numpoints )
 690         {
 691                 if ( !keep && k == ( i + 1 ) % f1->numpoints && !keep2 ) {
 692                         continue;
 693                 }
 694
 695                 VectorCopy( f1->points[k], newf->points[newf->numpoints] );
 696                 newf->numpoints++;
 697         }
 698
 699         // copy second polygon
 700         for ( l = ( j + 1 ) % f2->numpoints ; l != j ; l = ( l + 1 ) % f2->numpoints )
 701         {
 702                 if ( !keep && l == ( j + 1 ) % f2->numpoints && !keep1 ) {
 703                         continue;
 704                 }
 705                 VectorCopy( f2->points[l], newf->points[newf->numpoints] );
 706                 newf->numpoints++;
 707         }
 708
 709         return newf;
 710 }
 711
 712 /*
 713    ============
 714    Winding_Plane
 715    ============
 716  */
 717 void Winding_Plane( winding_t *w, vec3_t normal, double *dist ){
 718         vec3_t v1, v2;
 719         int i;
 720
 721         //find two vectors each longer than 0.5 units
 722         for ( i = 0; i < w->numpoints; i++ )
 723         {
 724                 VectorSubtract( w->points[( i + 1 ) % w->numpoints], w->points[i], v1 );
 725                 VectorSubtract( w->points[( i + 2 ) % w->numpoints], w->points[i], v2 );
 726                 if ( VectorLength( v1 ) > 0.5 && VectorLength( v2 ) > 0.5 ) {
 727                         break;
 728                 }
 729         }
 730         CrossProduct( v2, v1, normal );
 731         VectorNormalize( normal, normal );
 732         *dist = DotProduct( w->points[0], normal );
 733 }
 734
 735 /*
 736    =============
 737    Winding_Area
 738    =============
 739  */
 740 float Winding_Area( winding_t *w ){
 741         int i;
 742         vec3_t d1, d2, cross;
 743         float total;
 744
 745         total = 0;
 746         for ( i = 2 ; i < w->numpoints ; i++ )
 747         {
 748                 VectorSubtract( w->points[i - 1], w->points[0], d1 );
 749                 VectorSubtract( w->points[i], w->points[0], d2 );
 750                 CrossProduct( d1, d2, cross );
 751                 total += 0.5 * VectorLength( cross );
 752         }
 753         return total;
 754 }
 755
 756 /*
 757    =============
 758    Winding_Bounds
 759    =============
 760  */
 761 void Winding_Bounds( winding_t *w, vec3_t mins, vec3_t maxs ){
 762         vec_t v;
 763         int i,j;
 764
 765         mins[0] = mins[1] = mins[2] = 99999;
 766         maxs[0] = maxs[1] = maxs[2] = -99999;
 767
 768         for ( i = 0 ; i < w->numpoints ; i++ )
 769         {
 770                 for ( j = 0 ; j < 3 ; j++ )
 771                 {
 772                         v = w->points[i][j];
 773                         if ( v < mins[j] ) {
 774                                 mins[j] = v;
 775                         }
 776                         if ( v > maxs[j] ) {
 777                                 maxs[j] = v;
 778                         }
 779                 }
 780         }
 781 }
 782
 783
 784 /*
 785    =================
 786    Winding_PointInside
 787    =================
 788  */
 789 int Winding_PointInside( winding_t *w, plane_t *plane, vec3_t point, float epsilon ){
 790         int i;
 791         vec3_t dir, normal, pointvec;
 792
 793         for ( i = 0; i < w->numpoints; i++ )
 794         {
 795                 VectorSubtract( w->points[( i + 1 ) % w->numpoints], w->points[i], dir );
 796                 VectorSubtract( point, w->points[i], pointvec );
 797                 //
 798                 CrossProduct( dir, plane->normal, normal );
 799                 //
 800                 if ( DotProduct( pointvec, normal ) < -epsilon ) {
 801                         return false;
 802                 }
 803         }
 804         return true;
 805 }
 806
 807 /*
 808    =================
 809    Winding_VectorIntersect
 810    =================
 811  */
 812 int Winding_VectorIntersect( winding_t *w, plane_t *plane, vec3_t p1, vec3_t p2, float epsilon ){
 813         float front, back, frac;
 814         vec3_t mid;
 815
 816         front = DotProduct( p1, plane->normal ) - plane->dist;
 817         back = DotProduct( p2, plane->normal ) - plane->dist;
 818         //if both points at the same side of the plane
 819         if ( front < -epsilon && back < -epsilon ) {
 820                 return false;
 821         }
 822         if ( front > epsilon && back > epsilon ) {
 823                 return false;
 824         }
 825         //get point of intersection with winding plane
 826         if ( fabs( front - back ) < 0.001 ) {
 827                 VectorCopy( p2, mid );
 828         }
 829         else
 830         {
 831                 frac = front / ( front - back );
 832                 mid[0] = p1[0] + ( p2[0] - p1[0] ) * frac;
 833                 mid[1] = p1[1] + ( p2[1] - p1[1] ) * frac;
 834                 mid[2] = p1[2] + ( p2[2] - p1[2] ) * frac;
 835         }
 836         return Winding_PointInside( w, plane, mid, epsilon );
 837 }