tools/quake3/q3map2/light_trace.c

   1 /* -------------------------------------------------------------------------------
   2
   3    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   4    For a list of contributors, see the accompanying CONTRIBUTORS file.
   5
   6    This file is part of GtkRadiant.
   7
   8    GtkRadiant is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    GtkRadiant is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with GtkRadiant; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21
  22    ----------------------------------------------------------------------------------
  23
  24    This code has been altered significantly from its original form, to support
  25    several games based on the Quake III Arena engine, in the form of "Q3Map2."
  26
  27    ------------------------------------------------------------------------------- */
  28
  29
  30
  31 /* marker */
  32 #define LIGHT_TRACE_C
  33
  34
  35
  36 /* dependencies */
  37 #include "q3map2.h"
  38
  39
  40 /* dependencies */
  41 #include "q3map2.h"
  42
  43
  44
  45 #define Vector2Copy( a, b )     ( ( b )[ 0 ] = ( a )[ 0 ], ( b )[ 1 ] = ( a )[ 1 ] )
  46 #define Vector4Copy( a, b )     ( ( b )[ 0 ] = ( a )[ 0 ], ( b )[ 1 ] = ( a )[ 1 ], ( b )[ 2 ] = ( a )[ 2 ], ( b )[ 3 ] = ( a )[ 3 ] )
  47
  48 #define MAX_NODE_ITEMS          5
  49 #define MAX_NODE_TRIANGLES      5
  50 #define MAX_TRACE_DEPTH         32
  51 #define MIN_NODE_SIZE           32.0f
  52
  53 #define GROW_TRACE_INFOS        32768       //% 4096
  54 #define GROW_TRACE_WINDINGS     65536       //% 32768
  55 #define GROW_TRACE_TRIANGLES    131072      //% 32768
  56 #define GROW_TRACE_NODES        16384       //% 16384
  57 #define GROW_NODE_ITEMS         16          //% 256
  58
  59 // vortex: increased from 12 to 24 for ability co compile some insane maps with large curve count
  60 #define MAX_TW_VERTS            24
  61
  62 #define TRACE_ON_EPSILON        0.1f
  63
  64 #define TRACE_LEAF              -1
  65 #define TRACE_LEAF_SOLID        -2
  66
  67 typedef struct traceVert_s
  68 {
  69         vec3_t xyz;
  70         float st[ 2 ];
  71 }
  72 traceVert_t;
  73
  74 typedef struct traceInfo_s
  75 {
  76         shaderInfo_t                *si;
  77         int surfaceNum, castShadows, skipGrid;
  78 }
  79 traceInfo_t;
  80
  81 typedef struct traceWinding_s
  82 {
  83         vec4_t plane;
  84         int infoNum, numVerts;
  85         traceVert_t v[ MAX_TW_VERTS ];
  86 }
  87 traceWinding_t;
  88
  89 typedef struct traceTriangle_s
  90 {
  91         vec3_t edge1, edge2;
  92         int infoNum;
  93         traceVert_t v[ 3 ];
  94 }
  95 traceTriangle_t;
  96
  97 typedef struct traceNode_s
  98 {
  99         int type;
 100         vec4_t plane;
 101         vec3_t mins, maxs;
 102         int children[ 2 ];
 103         int numItems, maxItems;
 104         int                         *items;
 105 }
 106 traceNode_t;
 107
 108
 109 int noDrawContentFlags, noDrawSurfaceFlags, noDrawCompileFlags;
 110
 111 int numTraceInfos = 0, maxTraceInfos = 0, firstTraceInfo = 0;
 112 traceInfo_t                     *traceInfos = NULL;
 113
 114 int numTraceWindings = 0, maxTraceWindings = 0, deadWinding = -1;
 115 traceWinding_t                  *traceWindings = NULL;
 116
 117 int numTraceTriangles = 0, maxTraceTriangles = 0, deadTriangle = -1;
 118 traceTriangle_t                 *traceTriangles = NULL;
 119
 120 int headNodeNum = 0, skyboxNodeNum = 0, maxTraceDepth = 0, numTraceLeafNodes = 0;
 121 int numTraceNodes = 0, maxTraceNodes = 0;
 122 traceNode_t                     *traceNodes = NULL;
 123
 124
 125
 126 /* -------------------------------------------------------------------------------
 127
 128    allocation and list management
 129
 130    ------------------------------------------------------------------------------- */
 131
 132 /*
 133    AddTraceInfo() - ydnar
 134    adds a trace info structure to the pool
 135  */
 136
 137 static int AddTraceInfo( traceInfo_t *ti ){
 138         int num;
 139         void    *temp;
 140
 141
 142         /* find an existing info */
 143         for ( num = firstTraceInfo; num < numTraceInfos; num++ )
 144         {
 145                 if ( traceInfos[ num ].si == ti->si &&
 146                          traceInfos[ num ].surfaceNum == ti->surfaceNum &&
 147                          traceInfos[ num ].castShadows == ti->castShadows &&
 148                          traceInfos[ num ].skipGrid == ti->skipGrid ) {
 149                         return num;
 150                 }
 151         }
 152
 153         /* enough space? */
 154         if ( numTraceInfos >= maxTraceInfos ) {
 155                 /* allocate more room */
 156                 maxTraceInfos += GROW_TRACE_INFOS;
 157                 temp = safe_malloc( maxTraceInfos * sizeof( *traceInfos ) );
 158                 if ( traceInfos != NULL ) {
 159                         memcpy( temp, traceInfos, numTraceInfos * sizeof( *traceInfos ) );
 160                         free( traceInfos );
 161                 }
 162                 traceInfos = (traceInfo_t*) temp;
 163         }
 164
 165         /* add the info */
 166         memcpy( &traceInfos[ num ], ti, sizeof( *traceInfos ) );
 167         if ( num == numTraceInfos ) {
 168                 numTraceInfos++;
 169         }
 170
 171         /* return the ti number */
 172         return num;
 173 }
 174
 175
 176
 177 /*
 178    AllocTraceNode() - ydnar
 179    allocates a new trace node
 180  */
 181
 182 static int AllocTraceNode( void ){
 183         traceNode_t *temp;
 184
 185
 186         /* enough space? */
 187         if ( numTraceNodes >= maxTraceNodes ) {
 188                 /* reallocate more room */
 189                 maxTraceNodes += GROW_TRACE_NODES;
 190                 temp = safe_malloc( maxTraceNodes * sizeof( traceNode_t ) );
 191                 if ( traceNodes != NULL ) {
 192                         memcpy( temp, traceNodes, numTraceNodes * sizeof( traceNode_t ) );
 193                         free( traceNodes );
 194                 }
 195                 traceNodes = temp;
 196         }
 197
 198         /* add the node */
 199         memset( &traceNodes[ numTraceNodes ], 0, sizeof( traceNode_t ) );
 200         traceNodes[ numTraceNodes ].type = TRACE_LEAF;
 201         ClearBounds( traceNodes[ numTraceNodes ].mins, traceNodes[ numTraceNodes ].maxs );
 202         numTraceNodes++;
 203
 204         /* return the count */
 205         return ( numTraceNodes - 1 );
 206 }
 207
 208
 209
 210 /*
 211    AddTraceWinding() - ydnar
 212    adds a winding to the raytracing pool
 213  */
 214
 215 static int AddTraceWinding( traceWinding_t *tw ){
 216         int num;
 217         void    *temp;
 218
 219
 220         /* check for a dead winding */
 221         if ( deadWinding >= 0 && deadWinding < numTraceWindings ) {
 222                 num = deadWinding;
 223         }
 224         else
 225         {
 226                 /* put winding at the end of the list */
 227                 num = numTraceWindings;
 228
 229                 /* enough space? */
 230                 if ( numTraceWindings >= maxTraceWindings ) {
 231                         /* allocate more room */
 232                         maxTraceWindings += GROW_TRACE_WINDINGS;
 233                         temp = safe_malloc( maxTraceWindings * sizeof( *traceWindings ) );
 234                         if ( traceWindings != NULL ) {
 235                                 memcpy( temp, traceWindings, numTraceWindings * sizeof( *traceWindings ) );
 236                                 free( traceWindings );
 237                         }
 238                         traceWindings = (traceWinding_t*) temp;
 239                 }
 240         }
 241
 242         /* add the winding */
 243         memcpy( &traceWindings[ num ], tw, sizeof( *traceWindings ) );
 244         if ( num == numTraceWindings ) {
 245                 numTraceWindings++;
 246         }
 247         deadWinding = -1;
 248
 249         /* return the winding number */
 250         return num;
 251 }
 252
 253
 254
 255 /*
 256    AddTraceTriangle() - ydnar
 257    adds a triangle to the raytracing pool
 258  */
 259
 260 static int AddTraceTriangle( traceTriangle_t *tt ){
 261         int num;
 262         void    *temp;
 263
 264
 265         /* check for a dead triangle */
 266         if ( deadTriangle >= 0 && deadTriangle < numTraceTriangles ) {
 267                 num = deadTriangle;
 268         }
 269         else
 270         {
 271                 /* put triangle at the end of the list */
 272                 num = numTraceTriangles;
 273
 274                 /* enough space? */
 275                 if ( numTraceTriangles >= maxTraceTriangles ) {
 276                         /* allocate more room */
 277                         maxTraceTriangles += GROW_TRACE_TRIANGLES;
 278                         temp = safe_malloc( maxTraceTriangles * sizeof( *traceTriangles ) );
 279                         if ( traceTriangles != NULL ) {
 280                                 memcpy( temp, traceTriangles, numTraceTriangles * sizeof( *traceTriangles ) );
 281                                 free( traceTriangles );
 282                         }
 283                         traceTriangles = (traceTriangle_t*) temp;
 284                 }
 285         }
 286
 287         /* find vectors for two edges sharing the first vert */
 288         VectorSubtract( tt->v[ 1 ].xyz, tt->v[ 0 ].xyz, tt->edge1 );
 289         VectorSubtract( tt->v[ 2 ].xyz, tt->v[ 0 ].xyz, tt->edge2 );
 290
 291         /* add the triangle */
 292         memcpy( &traceTriangles[ num ], tt, sizeof( *traceTriangles ) );
 293         if ( num == numTraceTriangles ) {
 294                 numTraceTriangles++;
 295         }
 296         deadTriangle = -1;
 297
 298         /* return the triangle number */
 299         return num;
 300 }
 301
 302
 303
 304 /*
 305    AddItemToTraceNode() - ydnar
 306    adds an item reference (winding or triangle) to a trace node
 307  */
 308
 309 static int AddItemToTraceNode( traceNode_t *node, int num ){
 310         void            *temp;
 311
 312
 313         /* dummy check */
 314         if ( num < 0 ) {
 315                 return -1;
 316         }
 317
 318         /* enough space? */
 319         if ( node->numItems >= node->maxItems ) {
 320                 /* allocate more room */
 321                 if ( node == traceNodes ) {
 322                         node->maxItems *= 2;
 323                 }
 324                 else{
 325                         node->maxItems += GROW_NODE_ITEMS;
 326                 }
 327                 if ( node->maxItems <= 0 ) {
 328                         node->maxItems = GROW_NODE_ITEMS;
 329                 }
 330                 temp = safe_malloc( node->maxItems * sizeof( *node->items ) );
 331                 if ( node->items != NULL ) {
 332                         memcpy( temp, node->items, node->numItems * sizeof( *node->items ) );
 333                         free( node->items );
 334                 }
 335                 node->items = (int*) temp;
 336         }
 337
 338         /* add the poly */
 339         node->items[ node->numItems ] = num;
 340         node->numItems++;
 341
 342         /* return the count */
 343         return ( node->numItems - 1 );
 344 }
 345
 346
 347
 348
 349 /* -------------------------------------------------------------------------------
 350
 351    trace node setup
 352
 353    ------------------------------------------------------------------------------- */
 354
 355 /*
 356    SetupTraceNodes_r() - ydnar
 357    recursively create the initial trace node structure from the bsp tree
 358  */
 359
 360 static int SetupTraceNodes_r( int bspNodeNum ){
 361         int i, nodeNum, bspLeafNum, newNode;
 362         bspPlane_t      *plane;
 363         bspNode_t       *bspNode;
 364
 365
 366         /* get bsp node and plane */
 367         bspNode = &bspNodes[ bspNodeNum ];
 368         plane = &bspPlanes[ bspNode->planeNum ];
 369
 370         /* allocate a new trace node */
 371         nodeNum = AllocTraceNode();
 372
 373         /* setup trace node */
 374         traceNodes[ nodeNum ].type = PlaneTypeForNormal( plane->normal );
 375         VectorCopy( plane->normal, traceNodes[ nodeNum ].plane );
 376         traceNodes[ nodeNum ].plane[ 3 ] = plane->dist;
 377
 378         /* setup children */
 379         for ( i = 0; i < 2; i++ )
 380         {
 381                 /* leafnode */
 382                 if ( bspNode->children[ i ] < 0 ) {
 383                         bspLeafNum = -bspNode->children[ i ] - 1;
 384
 385                         /* new code */
 386                         newNode = AllocTraceNode();
 387                         traceNodes[ nodeNum ].children[ i ] = newNode;
 388                         /* have to do this separately, as gcc first executes LHS, then RHS, and if a realloc took place, this fails */
 389
 390                         if ( bspLeafs[ bspLeafNum ].cluster == -1 ) {
 391                                 traceNodes[ traceNodes[ nodeNum ].children[ i ] ].type = TRACE_LEAF_SOLID;
 392                         }
 393                 }
 394
 395                 /* normal node */
 396                 else
 397                 {
 398                         newNode = SetupTraceNodes_r( bspNode->children[ i ] );
 399                         traceNodes[ nodeNum ].children[ i ] = newNode;
 400                 }
 401
 402                 if ( traceNodes[ nodeNum ].children[ i ] == 0 ) {
 403                         Error( "Invalid tracenode allocated" );
 404                 }
 405         }
 406
 407         /* return node number */
 408         return nodeNum;
 409 }
 410
 411
 412
 413 /*
 414    ClipTraceWinding() - ydnar
 415    clips a trace winding against a plane into one or two parts
 416  */
 417
 418 #define TW_ON_EPSILON   0.25f
 419
 420 void ClipTraceWinding( traceWinding_t *tw, vec4_t plane, traceWinding_t *front, traceWinding_t *back ){
 421         int i, j, k;
 422         int sides[ MAX_TW_VERTS ], counts[ 3 ] = { 0, 0, 0 };
 423         float dists[ MAX_TW_VERTS ];
 424         float frac;
 425         traceVert_t     *a, *b, mid;
 426
 427
 428         /* clear front and back */
 429         front->numVerts = 0;
 430         back->numVerts = 0;
 431
 432         /* classify points */
 433         for ( i = 0; i < tw->numVerts; i++ )
 434         {
 435                 dists[ i ] = DotProduct( tw->v[ i ].xyz, plane ) - plane[ 3 ];
 436                 if ( dists[ i ] < -TW_ON_EPSILON ) {
 437                         sides[ i ] = SIDE_BACK;
 438                 }
 439                 else if ( dists[ i ] > TW_ON_EPSILON ) {
 440                         sides[ i ] = SIDE_FRONT;
 441                 }
 442                 else{
 443                         sides[ i ] = SIDE_ON;
 444                 }
 445                 counts[ sides[ i ] ]++;
 446         }
 447
 448         /* entirely on front? */
 449         if ( counts[ SIDE_BACK ] == 0 ) {
 450                 memcpy( front, tw, sizeof( *front ) );
 451         }
 452
 453         /* entirely on back? */
 454         else if ( counts[ SIDE_FRONT ] == 0 ) {
 455                 memcpy( back, tw, sizeof( *back ) );
 456         }
 457
 458         /* straddles the plane */
 459         else
 460         {
 461                 /* setup front and back */
 462                 memcpy( front, tw, sizeof( *front ) );
 463                 front->numVerts = 0;
 464                 memcpy( back, tw, sizeof( *back ) );
 465                 back->numVerts = 0;
 466
 467                 /* split the winding */
 468                 for ( i = 0; i < tw->numVerts; i++ )
 469                 {
 470                         /* radix */
 471                         j = ( i + 1 ) % tw->numVerts;
 472
 473                         /* get verts */
 474                         a = &tw->v[ i ];
 475                         b = &tw->v[ j ];
 476
 477                         /* handle points on the splitting plane */
 478                         switch ( sides[ i ] )
 479                         {
 480                         case SIDE_FRONT:
 481                                 if ( front->numVerts >= MAX_TW_VERTS ) {
 482                                         Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
 483                                 }
 484                                 front->v[ front->numVerts++ ] = *a;
 485                                 break;
 486
 487                         case SIDE_BACK:
 488                                 if ( back->numVerts >= MAX_TW_VERTS ) {
 489                                         Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
 490                                 }
 491                                 back->v[ back->numVerts++ ] = *a;
 492                                 break;
 493
 494                         case SIDE_ON:
 495                                 if ( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS ) {
 496                                         Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
 497                                 }
 498                                 front->v[ front->numVerts++ ] = *a;
 499                                 back->v[ back->numVerts++ ] = *a;
 500                                 continue;
 501                         }
 502
 503                         /* check next point to see if we need to split the edge */
 504                         if ( sides[ j ] == SIDE_ON || sides[ j ] == sides[ i ] ) {
 505                                 continue;
 506                         }
 507
 508                         /* check limit */
 509                         if ( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS ) {
 510                                 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
 511                         }
 512
 513                         /* generate a split point */
 514                         frac = dists[ i ] / ( dists[ i ] - dists[ j ] );
 515                         for ( k = 0; k < 3; k++ )
 516                         {
 517                                 /* minimize fp precision errors */
 518                                 if ( plane[ k ] == 1.0f ) {
 519                                         mid.xyz[ k ] = plane[ 3 ];
 520                                 }
 521                                 else if ( plane[ k ] == -1.0f ) {
 522                                         mid.xyz[ k ] = -plane[ 3 ];
 523                                 }
 524                                 else{
 525                                         mid.xyz[ k ] = a->xyz[ k ] + frac * ( b->xyz[ k ] - a->xyz[ k ] );
 526                                 }
 527                         }
 528                         /* set texture coordinates */
 529                         mid.st[ 0 ] = a->st[ 0 ] + frac * ( b->st[ 0 ] - a->st[ 0 ] );
 530                         mid.st[ 1 ] = a->st[ 1 ] + frac * ( b->st[ 1 ] - a->st[ 1 ] );
 531
 532                         /* copy midpoint to front and back polygons */
 533                         front->v[ front->numVerts++ ] = mid;
 534                         back->v[ back->numVerts++ ] = mid;
 535                 }
 536         }
 537 }
 538
 539
 540
 541 /*
 542    FilterTraceWindingIntoNodes_r() - ydnar
 543    filters a trace winding into the raytracing tree
 544  */
 545
 546 static void FilterTraceWindingIntoNodes_r( traceWinding_t *tw, int nodeNum ){
 547         int num;
 548         vec4_t plane1, plane2, reverse;
 549         traceNode_t     *node;
 550         traceWinding_t front, back;
 551
 552
 553         /* don't filter if passed a bogus node (solid, etc) */
 554         if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
 555                 return;
 556         }
 557
 558         /* get node */
 559         node = &traceNodes[ nodeNum ];
 560
 561         /* is this a decision node? */
 562         if ( node->type >= 0 ) {
 563                 /* create winding plane if necessary, filtering out bogus windings as well */
 564                 if ( nodeNum == headNodeNum ) {
 565                         if ( !PlaneFromPoints( tw->plane, tw->v[ 0 ].xyz, tw->v[ 1 ].xyz, tw->v[ 2 ].xyz ) ) {
 566                                 return;
 567                         }
 568                 }
 569
 570                 /* validate the node */
 571                 if ( node->children[ 0 ] == 0 || node->children[ 1 ] == 0 ) {
 572                         Error( "Invalid tracenode: %d", nodeNum );
 573                 }
 574
 575                 /* get node plane */
 576                 Vector4Copy( node->plane, plane1 );
 577
 578                 /* get winding plane */
 579                 Vector4Copy( tw->plane, plane2 );
 580
 581                 /* invert surface plane */
 582                 VectorSubtract( vec3_origin, plane2, reverse );
 583                 reverse[ 3 ] = -plane2[ 3 ];
 584
 585                 /* front only */
 586                 if ( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f ) {
 587                         FilterTraceWindingIntoNodes_r( tw, node->children[ 0 ] );
 588                         return;
 589                 }
 590
 591                 /* back only */
 592                 if ( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f ) {
 593                         FilterTraceWindingIntoNodes_r( tw, node->children[ 1 ] );
 594                         return;
 595                 }
 596
 597                 /* clip the winding by node plane */
 598                 ClipTraceWinding( tw, plane1, &front, &back );
 599
 600                 /* filter by node plane */
 601                 if ( front.numVerts >= 3 ) {
 602                         FilterTraceWindingIntoNodes_r( &front, node->children[ 0 ] );
 603                 }
 604                 if ( back.numVerts >= 3 ) {
 605                         FilterTraceWindingIntoNodes_r( &back, node->children[ 1 ] );
 606                 }
 607
 608                 /* return to caller */
 609                 return;
 610         }
 611
 612         /* add winding to leaf node */
 613         num = AddTraceWinding( tw );
 614         AddItemToTraceNode( node, num );
 615 }
 616
 617
 618
 619 /*
 620    SubdivideTraceNode_r() - ydnar
 621    recursively subdivides a tracing node until it meets certain size and complexity criteria
 622  */
 623
 624 static void SubdivideTraceNode_r( int nodeNum, int depth ){
 625         int i, j, count, num, frontNum, backNum, type;
 626         vec3_t size;
 627         float dist;
 628         double average[ 3 ];
 629         traceNode_t     *node, *frontNode, *backNode;
 630         traceWinding_t  *tw, front, back;
 631
 632
 633         /* dummy check */
 634         if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
 635                 return;
 636         }
 637
 638         /* get node */
 639         node = &traceNodes[ nodeNum ];
 640
 641         /* runaway recursion check */
 642         if ( depth >= MAX_TRACE_DEPTH ) {
 643                 //%     Sys_Printf( "Depth: (%d items)\n", node->numItems );
 644                 numTraceLeafNodes++;
 645                 return;
 646         }
 647         depth++;
 648
 649         /* is this a decision node? */
 650         if ( node->type >= 0 ) {
 651                 /* subdivide children */
 652                 frontNum = node->children[ 0 ];
 653                 backNum = node->children[ 1 ];
 654                 SubdivideTraceNode_r( frontNum, depth );
 655                 SubdivideTraceNode_r( backNum, depth );
 656                 return;
 657         }
 658
 659         /* bound the node */
 660         ClearBounds( node->mins, node->maxs );
 661         VectorClear( average );
 662         count = 0;
 663         for ( i = 0; i < node->numItems; i++ )
 664         {
 665                 /* get winding */
 666                 tw = &traceWindings[ node->items[ i ] ];
 667
 668                 /* walk its verts */
 669                 for ( j = 0; j < tw->numVerts; j++ )
 670                 {
 671                         AddPointToBounds( tw->v[ j ].xyz, node->mins, node->maxs );
 672                         average[ 0 ] += tw->v[ j ].xyz[ 0 ];
 673                         average[ 1 ] += tw->v[ j ].xyz[ 1 ];
 674                         average[ 2 ] += tw->v[ j ].xyz[ 2 ];
 675                         count++;
 676                 }
 677         }
 678
 679         /* check triangle limit */
 680         //%     if( node->numItems <= MAX_NODE_ITEMS )
 681         if ( ( count - ( node->numItems * 2 ) ) < MAX_NODE_TRIANGLES ) {
 682                 //%     Sys_Printf( "Limit: (%d triangles)\n", (count - (node->numItems * 2)) );
 683                 numTraceLeafNodes++;
 684                 return;
 685         }
 686
 687         /* the largest dimension of the bounding box will be the split axis */
 688         VectorSubtract( node->maxs, node->mins, size );
 689         if ( size[ 0 ] >= size[ 1 ] && size[ 0 ] >= size[ 2 ] ) {
 690                 type = PLANE_X;
 691         }
 692         else if ( size[ 1 ] >= size[ 0 ] && size[ 1 ] >= size[ 2 ] ) {
 693                 type = PLANE_Y;
 694         }
 695         else{
 696                 type = PLANE_Z;
 697         }
 698
 699         /* don't split small nodes */
 700         if ( size[ type ] <= MIN_NODE_SIZE ) {
 701                 //%     Sys_Printf( "Limit: %f %f %f (%d items)\n", size[ 0 ], size[ 1 ], size[ 2 ], node->numItems );
 702                 numTraceLeafNodes++;
 703                 return;
 704         }
 705
 706         /* set max trace depth */
 707         if ( depth > maxTraceDepth ) {
 708                 maxTraceDepth = depth;
 709         }
 710
 711         /* snap the average */
 712         dist = floor( average[ type ] / count );
 713
 714         /* dummy check it */
 715         if ( dist <= node->mins[ type ] || dist >= node->maxs[ type ] ) {
 716                 dist = floor( 0.5f * ( node->mins[ type ] + node->maxs[ type ] ) );
 717         }
 718
 719         /* allocate child nodes */
 720         frontNum = AllocTraceNode();
 721         backNum = AllocTraceNode();
 722
 723         /* reset pointers */
 724         node = &traceNodes[ nodeNum ];
 725         frontNode = &traceNodes[ frontNum ];
 726         backNode = &traceNodes[ backNum ];
 727
 728         /* attach children */
 729         node->type = type;
 730         node->plane[ type ] = 1.0f;
 731         node->plane[ 3 ] = dist;
 732         node->children[ 0 ] = frontNum;
 733         node->children[ 1 ] = backNum;
 734
 735         /* setup front node */
 736         frontNode->maxItems = ( node->maxItems >> 1 );
 737         frontNode->items = safe_malloc( frontNode->maxItems * sizeof( *frontNode->items ) );
 738
 739         /* setup back node */
 740         backNode->maxItems = ( node->maxItems >> 1 );
 741         backNode->items = safe_malloc( backNode->maxItems * sizeof( *backNode->items ) );
 742
 743         /* filter windings into child nodes */
 744         for ( i = 0; i < node->numItems; i++ )
 745         {
 746                 /* get winding */
 747                 tw = &traceWindings[ node->items[ i ] ];
 748
 749                 /* clip the winding by the new split plane */
 750                 ClipTraceWinding( tw, node->plane, &front, &back );
 751
 752                 /* kill the existing winding */
 753                 if ( front.numVerts >= 3 || back.numVerts >= 3 ) {
 754                         deadWinding = node->items[ i ];
 755                 }
 756
 757                 /* add front winding */
 758                 if ( front.numVerts >= 3 ) {
 759                         num = AddTraceWinding( &front );
 760                         AddItemToTraceNode( frontNode, num );
 761                 }
 762
 763                 /* add back winding */
 764                 if ( back.numVerts >= 3 ) {
 765                         num = AddTraceWinding( &back );
 766                         AddItemToTraceNode( backNode, num );
 767                 }
 768         }
 769
 770         /* free original node winding list */
 771         node->numItems = 0;
 772         node->maxItems = 0;
 773         free( node->items );
 774         node->items = NULL;
 775
 776         /* check children */
 777         if ( frontNode->numItems <= 0 ) {
 778                 frontNode->maxItems = 0;
 779                 free( frontNode->items );
 780                 frontNode->items = NULL;
 781         }
 782
 783         if ( backNode->numItems <= 0 ) {
 784                 backNode->maxItems = 0;
 785                 free( backNode->items );
 786                 backNode->items = NULL;
 787         }
 788
 789         /* subdivide children */
 790         SubdivideTraceNode_r( frontNum, depth );
 791         SubdivideTraceNode_r( backNum, depth );
 792 }
 793
 794
 795
 796 /*
 797    TriangulateTraceNode_r()
 798    optimizes the tracing data by changing trace windings into triangles
 799  */
 800
 801 static int TriangulateTraceNode_r( int nodeNum ){
 802         int i, j, num, frontNum, backNum, numWindings, *windings;
 803         traceNode_t     *node;
 804         traceWinding_t  *tw;
 805         traceTriangle_t tt;
 806
 807
 808         /* dummy check */
 809         if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
 810                 return 0;
 811         }
 812
 813         /* get node */
 814         node = &traceNodes[ nodeNum ];
 815
 816         /* is this a decision node? */
 817         if ( node->type >= 0 ) {
 818                 /* triangulate children */
 819                 frontNum = node->children[ 0 ];
 820                 backNum = node->children[ 1 ];
 821                 node->numItems = TriangulateTraceNode_r( frontNum );
 822                 node->numItems += TriangulateTraceNode_r( backNum );
 823                 return node->numItems;
 824         }
 825
 826         /* empty node? */
 827         if ( node->numItems == 0 ) {
 828                 node->maxItems = 0;
 829                 if ( node->items != NULL ) {
 830                         free( node->items );
 831                 }
 832                 return node->numItems;
 833         }
 834
 835         /* store off winding data */
 836         numWindings = node->numItems;
 837         windings = node->items;
 838
 839         /* clear it */
 840         node->numItems = 0;
 841         node->maxItems = numWindings * 2;
 842         node->items = safe_malloc( node->maxItems * sizeof( tt ) );
 843
 844         /* walk winding list */
 845         for ( i = 0; i < numWindings; i++ )
 846         {
 847                 /* get winding */
 848                 tw = &traceWindings[ windings[ i ] ];
 849
 850                 /* initial setup */
 851                 tt.infoNum = tw->infoNum;
 852                 tt.v[ 0 ] = tw->v[ 0 ];
 853
 854                 /* walk vertex list */
 855                 for ( j = 1; j + 1 < tw->numVerts; j++ )
 856                 {
 857                         /* set verts */
 858                         tt.v[ 1 ] = tw->v[ j ];
 859                         tt.v[ 2 ] = tw->v[ j + 1 ];
 860
 861                         /* find vectors for two edges sharing the first vert */
 862                         VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
 863                         VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
 864
 865                         /* add it to the node */
 866                         num = AddTraceTriangle( &tt );
 867                         AddItemToTraceNode( node, num );
 868                 }
 869         }
 870
 871         /* free windings */
 872         if ( windings != NULL ) {
 873                 free( windings );
 874         }
 875
 876         /* return item count */
 877         return node->numItems;
 878 }
 879
 880
 881
 882 /* -------------------------------------------------------------------------------
 883
 884    shadow casting item setup (triangles, patches, entities)
 885
 886    ------------------------------------------------------------------------------- */
 887
 888 /*
 889    PopulateWithBSPModel() - ydnar
 890    filters a bsp model's surfaces into the raytracing tree
 891  */
 892
 893 static void PopulateWithBSPModel( bspModel_t *model, m4x4_t transform ){
 894         int i, j, x, y, pw[ 5 ], r, nodeNum;
 895         bspDrawSurface_t    *ds;
 896         surfaceInfo_t       *info;
 897         bspDrawVert_t       *verts;
 898         int                 *indexes;
 899         mesh_t srcMesh, *mesh, *subdivided;
 900         traceInfo_t ti;
 901         traceWinding_t tw;
 902
 903
 904         /* dummy check */
 905         if ( model == NULL || transform == NULL ) {
 906                 return;
 907         }
 908
 909         /* walk the list of surfaces in this model and fill out the info structs */
 910         for ( i = 0; i < model->numBSPSurfaces; i++ )
 911         {
 912                 /* get surface and info */
 913                 ds = &bspDrawSurfaces[ model->firstBSPSurface + i ];
 914                 info = &surfaceInfos[ model->firstBSPSurface + i ];
 915                 if ( info->si == NULL ) {
 916                         continue;
 917                 }
 918
 919                 /* no shadows */
 920                 if ( !info->castShadows ) {
 921                         continue;
 922                 }
 923
 924                 /* patchshadows? */
 925                 if ( ds->surfaceType == MST_PATCH && patchShadows == qfalse ) {
 926                         continue;
 927                 }
 928
 929                 /* some surfaces in the bsp might have been tagged as nodraw, with a bogus shader */
 930                 if ( ( bspShaders[ ds->shaderNum ].contentFlags & noDrawContentFlags ) ||
 931                          ( bspShaders[ ds->shaderNum ].surfaceFlags & noDrawSurfaceFlags ) ) {
 932                         continue;
 933                 }
 934
 935                 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
 936                 if ( ( info->si->compileFlags & C_NODRAW ) ) {
 937                         continue;
 938                 }
 939                 if ( ( info->si->compileFlags & C_TRANSLUCENT ) &&
 940                          !( info->si->compileFlags & C_ALPHASHADOW ) &&
 941                          !( info->si->compileFlags & C_LIGHTFILTER ) ) {
 942                         continue;
 943                 }
 944
 945                 /* setup trace info */
 946                 ti.si = info->si;
 947                 ti.castShadows = info->castShadows;
 948                 ti.surfaceNum = model->firstBSPBrush + i;
 949                 ti.skipGrid = ( ds->surfaceType == MST_PATCH );
 950
 951                 /* choose which node (normal or skybox) */
 952                 if ( info->parentSurfaceNum >= 0 ) {
 953                         nodeNum = skyboxNodeNum;
 954
 955                         /* sky surfaces in portal skies are ignored */
 956                         if ( info->si->compileFlags & C_SKY ) {
 957                                 continue;
 958                         }
 959                 }
 960                 else{
 961                         nodeNum = headNodeNum;
 962                 }
 963
 964                 /* setup trace winding */
 965                 memset( &tw, 0, sizeof( tw ) );
 966                 tw.infoNum = AddTraceInfo( &ti );
 967                 tw.numVerts = 3;
 968
 969                 /* switch on type */
 970                 switch ( ds->surfaceType )
 971                 {
 972                 /* handle patches */
 973                 case MST_PATCH:
 974                         /* subdivide the surface */
 975                         srcMesh.width = ds->patchWidth;
 976                         srcMesh.height = ds->patchHeight;
 977                         srcMesh.verts = &bspDrawVerts[ ds->firstVert ];
 978                         //%     subdivided = SubdivideMesh( srcMesh, 8, 512 );
 979                         subdivided = SubdivideMesh2( srcMesh, info->patchIterations );
 980
 981                         /* fit it to the curve and remove colinear verts on rows/columns */
 982                         PutMeshOnCurve( *subdivided );
 983                         mesh = RemoveLinearMeshColumnsRows( subdivided );
 984                         FreeMesh( subdivided );
 985
 986                         /* set verts */
 987                         verts = mesh->verts;
 988
 989                         /* subdivide each quad to place the models */
 990                         for ( y = 0; y < ( mesh->height - 1 ); y++ )
 991                         {
 992                                 for ( x = 0; x < ( mesh->width - 1 ); x++ )
 993                                 {
 994                                         /* set indexes */
 995                                         pw[ 0 ] = x + ( y * mesh->width );
 996                                         pw[ 1 ] = x + ( ( y + 1 ) * mesh->width );
 997                                         pw[ 2 ] = x + 1 + ( ( y + 1 ) * mesh->width );
 998                                         pw[ 3 ] = x + 1 + ( y * mesh->width );
 999                                         pw[ 4 ] = x + ( y * mesh->width );      /* same as pw[ 0 ] */
1000
1001                                         /* set radix */
1002                                         r = ( x + y ) & 1;
1003
1004                                         /* make first triangle */
1005                                         VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
1006                                         Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
1007                                         VectorCopy( verts[ pw[ r + 1 ] ].xyz, tw.v[ 1 ].xyz );
1008                                         Vector2Copy( verts[ pw[ r + 1 ] ].st, tw.v[ 1 ].st );
1009                                         VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 2 ].xyz );
1010                                         Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 2 ].st );
1011                                         m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1012                                         m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1013                                         m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1014                                         FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1015
1016                                         /* make second triangle */
1017                                         VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
1018                                         Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
1019                                         VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 1 ].xyz );
1020                                         Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 1 ].st );
1021                                         VectorCopy( verts[ pw[ r + 3 ] ].xyz, tw.v[ 2 ].xyz );
1022                                         Vector2Copy( verts[ pw[ r + 3 ] ].st, tw.v[ 2 ].st );
1023                                         m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1024                                         m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1025                                         m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1026                                         FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1027                                 }
1028                         }
1029
1030                         /* free the subdivided mesh */
1031                         FreeMesh( mesh );
1032                         break;
1033
1034                 /* handle triangle surfaces */
1035                 case MST_TRIANGLE_SOUP:
1036                 case MST_PLANAR:
1037                         /* set verts and indexes */
1038                         verts = &bspDrawVerts[ ds->firstVert ];
1039                         indexes = &bspDrawIndexes[ ds->firstIndex ];
1040
1041                         /* walk the triangle list */
1042                         for ( j = 0; j < ds->numIndexes; j += 3 )
1043                         {
1044                                 VectorCopy( verts[ indexes[ j ] ].xyz, tw.v[ 0 ].xyz );
1045                                 Vector2Copy( verts[ indexes[ j ] ].st, tw.v[ 0 ].st );
1046                                 VectorCopy( verts[ indexes[ j + 1 ] ].xyz, tw.v[ 1 ].xyz );
1047                                 Vector2Copy( verts[ indexes[ j + 1 ] ].st, tw.v[ 1 ].st );
1048                                 VectorCopy( verts[ indexes[ j + 2 ] ].xyz, tw.v[ 2 ].xyz );
1049                                 Vector2Copy( verts[ indexes[ j + 2 ] ].st, tw.v[ 2 ].st );
1050                                 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1051                                 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1052                                 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1053                                 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1054                         }
1055                         break;
1056
1057                 /* other surface types do not cast shadows */
1058                 default:
1059                         break;
1060                 }
1061         }
1062 }
1063
1064
1065
1066 /*
1067    PopulateWithPicoModel() - ydnar
1068    filters a picomodel's surfaces into the raytracing tree
1069  */
1070
1071 static void PopulateWithPicoModel( int castShadows, picoModel_t *model, m4x4_t transform ){
1072         int i, j, k, numSurfaces, numIndexes;
1073         picoSurface_t       *surface;
1074         picoShader_t        *shader;
1075         picoVec_t           *xyz, *st;
1076         picoIndex_t         *indexes;
1077         traceInfo_t ti;
1078         traceWinding_t tw;
1079
1080
1081         /* dummy check */
1082         if ( model == NULL || transform == NULL ) {
1083                 return;
1084         }
1085
1086         /* get info */
1087         numSurfaces = PicoGetModelNumSurfaces( model );
1088
1089         /* walk the list of surfaces in this model and fill out the info structs */
1090         for ( i = 0; i < numSurfaces; i++ )
1091         {
1092                 /* get surface */
1093                 surface = PicoGetModelSurface( model, i );
1094                 if ( surface == NULL ) {
1095                         continue;
1096                 }
1097
1098                 /* only handle triangle surfaces initially (fixme: support patches) */
1099                 if ( PicoGetSurfaceType( surface ) != PICO_TRIANGLES ) {
1100                         continue;
1101                 }
1102
1103                 /* get shader (fixme: support shader remapping) */
1104                 shader = PicoGetSurfaceShader( surface );
1105                 if ( shader == NULL ) {
1106                         continue;
1107                 }
1108                 ti.si = ShaderInfoForShaderNull( PicoGetShaderName( shader ) );
1109                 if ( ti.si == NULL ) {
1110                         continue;
1111                 }
1112
1113                 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
1114                 if ( ( ti.si->compileFlags & C_NODRAW ) ) {
1115                         continue;
1116                 }
1117                 if ( ( ti.si->compileFlags & C_TRANSLUCENT ) &&
1118                          !( ti.si->compileFlags & C_ALPHASHADOW ) &&
1119                          !( ti.si->compileFlags & C_LIGHTFILTER ) ) {
1120                         continue;
1121                 }
1122
1123                 /* setup trace info */
1124                 ti.castShadows = castShadows;
1125                 ti.surfaceNum = -1;
1126                 ti.skipGrid = qtrue; // also ignore picomodels when skipping patches
1127
1128                 /* setup trace winding */
1129                 memset( &tw, 0, sizeof( tw ) );
1130                 tw.infoNum = AddTraceInfo( &ti );
1131                 tw.numVerts = 3;
1132
1133                 /* get info */
1134                 numIndexes = PicoGetSurfaceNumIndexes( surface );
1135                 indexes = PicoGetSurfaceIndexes( surface, 0 );
1136
1137                 /* walk the triangle list */
1138                 for ( j = 0; j < numIndexes; j += 3, indexes += 3 )
1139                 {
1140                         for ( k = 0; k < 3; k++ )
1141                         {
1142                                 xyz = PicoGetSurfaceXYZ( surface, indexes[ k ] );
1143                                 st = PicoGetSurfaceST( surface, 0, indexes[ k ] );
1144                                 VectorCopy( xyz, tw.v[ k ].xyz );
1145                                 Vector2Copy( st, tw.v[ k ].st );
1146                                 m4x4_transform_point( transform, tw.v[ k ].xyz );
1147                         }
1148                         FilterTraceWindingIntoNodes_r( &tw, headNodeNum );
1149                 }
1150         }
1151 }
1152
1153
1154
1155 /*
1156    PopulateTraceNodes() - ydnar
1157    fills the raytracing tree with world and entity occluders
1158  */
1159
1160 static void PopulateTraceNodes( void ){
1161         int i, m, frame, castShadows;
1162         float temp;
1163         entity_t        *e;
1164         const char      *value;
1165         picoModel_t     *model;
1166         vec3_t origin, scale, angles;
1167         m4x4_t transform;
1168
1169
1170         /* add worldspawn triangles */
1171         m4x4_identity( transform );
1172         PopulateWithBSPModel( &bspModels[ 0 ], transform );
1173
1174         /* walk each entity list */
1175         for ( i = 1; i < numEntities; i++ )
1176         {
1177                 /* get entity */
1178                 e = &entities[ i ];
1179
1180                 /* get shadow flags */
1181                 castShadows = ENTITY_CAST_SHADOWS;
1182                 GetEntityShadowFlags( e, NULL, &castShadows, NULL );
1183
1184                 /* early out? */
1185                 if ( !castShadows ) {
1186                         continue;
1187                 }
1188
1189                 /* get entity origin */
1190                 GetVectorForKey( e, "origin", origin );
1191
1192                 /* get scale */
1193                 scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = 1.0f;
1194                 temp = FloatForKey( e, "modelscale" );
1195                 if ( temp != 0.0f ) {
1196                         scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = temp;
1197                 }
1198                 value = ValueForKey( e, "modelscale_vec" );
1199                 if ( value[ 0 ] != '\0' ) {
1200                         sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );
1201                 }
1202
1203                 /* get "angle" (yaw) or "angles" (pitch yaw roll) */
1204                 angles[ 0 ] = angles[ 1 ] = angles[ 2 ] = 0.0f;
1205                 angles[ 2 ] = FloatForKey( e, "angle" );
1206                 value = ValueForKey( e, "angles" );
1207                 if ( value[ 0 ] != '\0' ) {
1208                         sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
1209                 }
1210
1211                 /* set transform matrix (thanks spog) */
1212                 m4x4_identity( transform );
1213                 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
1214
1215                 /* hack: Stable-1_2 and trunk have differing row/column major matrix order
1216                    this transpose is necessary with Stable-1_2
1217                    uncomment the following line with old m4x4_t (non 1.3/spog_branch) code */
1218                 //%     m4x4_transpose( transform );
1219
1220                 /* get model */
1221                 value = ValueForKey( e, "model" );
1222
1223                 /* switch on model type */
1224                 switch ( value[ 0 ] )
1225                 {
1226                 /* no model */
1227                 case '\0':
1228                         break;
1229
1230                 /* bsp model */
1231                 case '*':
1232                         m = atoi( &value[ 1 ] );
1233                         if ( m <= 0 || m >= numBSPModels ) {
1234                                 continue;
1235                         }
1236                         PopulateWithBSPModel( &bspModels[ m ], transform );
1237                         break;
1238
1239                 /* external model */
1240                 default:
1241                         frame = 0;
1242                         if ( strcmp( "", ValueForKey( e, "_frame" ) ) ) {
1243                                 frame = IntForKey( e, "_frame" );
1244                         }
1245                         else if ( strcmp( "", ValueForKey( e, "frame" ) ) ) {
1246                                 frame = IntForKey( e, "frame" );
1247                         }
1248                         model = LoadModel( value, frame );
1249                         if ( model == NULL ) {
1250                                 continue;
1251                         }
1252                         PopulateWithPicoModel( castShadows, model, transform );
1253                         continue;
1254                 }
1255
1256                 /* get model2 */
1257                 value = ValueForKey( e, "model2" );
1258
1259                 /* switch on model type */
1260                 switch ( value[ 0 ] )
1261                 {
1262                 /* no model */
1263                 case '\0':
1264                         break;
1265
1266                 /* bsp model */
1267                 case '*':
1268                         m = atoi( &value[ 1 ] );
1269                         if ( m <= 0 || m >= numBSPModels ) {
1270                                 continue;
1271                         }
1272                         PopulateWithBSPModel( &bspModels[ m ], transform );
1273                         break;
1274
1275                 /* external model */
1276                 default:
1277                         frame = IntForKey( e, "_frame2" );
1278                         model = LoadModel( value, frame );
1279                         if ( model == NULL ) {
1280                                 continue;
1281                         }
1282                         PopulateWithPicoModel( castShadows, model, transform );
1283                         continue;
1284                 }
1285         }
1286 }
1287
1288
1289
1290
1291 /* -------------------------------------------------------------------------------
1292
1293    trace initialization
1294
1295    ------------------------------------------------------------------------------- */
1296
1297 /*
1298    SetupTraceNodes() - ydnar
1299    creates a balanced bsp with axis-aligned splits for efficient raytracing
1300  */
1301
1302 void SetupTraceNodes( void ){
1303         /* note it */
1304         Sys_FPrintf( SYS_VRB, "--- SetupTraceNodes ---\n" );
1305
1306         /* find nodraw bit */
1307         noDrawContentFlags = noDrawSurfaceFlags = noDrawCompileFlags = 0;
1308         ApplySurfaceParm( "nodraw", &noDrawContentFlags, &noDrawSurfaceFlags, &noDrawCompileFlags );
1309
1310         /* create the baseline raytracing tree from the bsp tree */
1311         headNodeNum = SetupTraceNodes_r( 0 );
1312
1313         /* create outside node for skybox surfaces */
1314         skyboxNodeNum = AllocTraceNode();
1315
1316         /* populate the tree with triangles from the world and shadow casting entities */
1317         PopulateTraceNodes();
1318
1319         /* create the raytracing bsp */
1320         if ( loMem == qfalse ) {
1321                 SubdivideTraceNode_r( headNodeNum, 0 );
1322                 SubdivideTraceNode_r( skyboxNodeNum, 0 );
1323         }
1324
1325         /* create triangles from the trace windings */
1326         TriangulateTraceNode_r( headNodeNum );
1327         TriangulateTraceNode_r( skyboxNodeNum );
1328
1329         /* emit some stats */
1330         //%     Sys_FPrintf( SYS_VRB, "%9d original triangles\n", numOriginalTriangles );
1331         Sys_FPrintf( SYS_VRB, "%9d trace windings (%.2fMB)\n", numTraceWindings, (float) ( numTraceWindings * sizeof( *traceWindings ) ) / ( 1024.0f * 1024.0f ) );
1332         Sys_FPrintf( SYS_VRB, "%9d trace triangles (%.2fMB)\n", numTraceTriangles, (float) ( numTraceTriangles * sizeof( *traceTriangles ) ) / ( 1024.0f * 1024.0f ) );
1333         Sys_FPrintf( SYS_VRB, "%9d trace nodes (%.2fMB)\n", numTraceNodes, (float) ( numTraceNodes * sizeof( *traceNodes ) ) / ( 1024.0f * 1024.0f ) );
1334         Sys_FPrintf( SYS_VRB, "%9d leaf nodes (%.2fMB)\n", numTraceLeafNodes, (float) ( numTraceLeafNodes * sizeof( *traceNodes ) ) / ( 1024.0f * 1024.0f ) );
1335         //%     Sys_FPrintf( SYS_VRB, "%9d average triangles per leaf node\n", numTraceTriangles / numTraceLeafNodes );
1336         Sys_FPrintf( SYS_VRB, "%9d average windings per leaf node\n", numTraceWindings / ( numTraceLeafNodes + 1 ) );
1337         Sys_FPrintf( SYS_VRB, "%9d max trace depth\n", maxTraceDepth );
1338
1339         /* free trace windings */
1340         free( traceWindings );
1341         numTraceWindings = 0;
1342         maxTraceWindings = 0;
1343         deadWinding = -1;
1344
1345         /* debug code: write out trace triangles to an alias obj file */
1346         #if 0
1347         {
1348                 int i, j;
1349                 FILE            *file;
1350                 char filename[ 1024 ];
1351                 traceWinding_t  *tw;
1352
1353
1354                 /* open the file */
1355                 strcpy( filename, source );
1356                 StripExtension( filename );
1357                 strcat( filename, ".lin" );
1358                 Sys_Printf( "Opening light trace file %s...\n", filename );
1359                 file = fopen( filename, "w" );
1360                 if ( file == NULL ) {
1361                         Error( "Error opening %s for writing", filename );
1362                 }
1363
1364                 /* walk node list */
1365                 for ( i = 0; i < numTraceWindings; i++ )
1366                 {
1367                         tw = &traceWindings[ i ];
1368                         for ( j = 0; j < tw->numVerts + 1; j++ )
1369                                 fprintf( file, "%f %f %f\n",
1370                                                  tw->v[ j % tw->numVerts ].xyz[ 0 ], tw->v[ j % tw->numVerts ].xyz[ 1 ], tw->v[ j % tw->numVerts ].xyz[ 2 ] );
1371                 }
1372
1373                 /* close it */
1374                 fclose( file );
1375         }
1376         #endif
1377 }
1378
1379
1380
1381 /* -------------------------------------------------------------------------------
1382
1383    raytracer
1384
1385    ------------------------------------------------------------------------------- */
1386
1387 /*
1388    TraceTriangle()
1389    based on code written by william 'spog' joseph
1390    based on code originally written by tomas moller and ben trumbore, journal of graphics tools, 2(1):21-28, 1997
1391  */
1392
1393 #define BARY_EPSILON            0.01f
1394 #define ASLF_EPSILON            0.0001f /* so to not get double shadows */
1395 #define COPLANAR_EPSILON        0.25f   //%     0.000001f
1396 #define NEAR_SHADOW_EPSILON     1.5f    //%     1.25f
1397 #define SELF_SHADOW_EPSILON     0.5f
1398
1399 qboolean TraceTriangle( traceInfo_t *ti, traceTriangle_t *tt, trace_t *trace ){
1400         int i;
1401         float tvec[ 3 ], pvec[ 3 ], qvec[ 3 ];
1402         float det, invDet, depth;
1403         float u, v, w, s, t;
1404         int is, it;
1405         byte            *pixel;
1406         float shadow;
1407         shaderInfo_t    *si;
1408
1409
1410         /* don't double-trace against sky */
1411         si = ti->si;
1412         if ( trace->compileFlags & si->compileFlags & C_SKY ) {
1413                 return qfalse;
1414         }
1415
1416         /* receive shadows from worldspawn group only */
1417         if ( trace->recvShadows == 1 ) {
1418                 if ( ti->castShadows != 1 ) {
1419                         return qfalse;
1420                 }
1421         }
1422
1423         /* receive shadows from same group and worldspawn group */
1424         else if ( trace->recvShadows > 1 ) {
1425                 if ( ti->castShadows != 1 && abs( ti->castShadows ) != abs( trace->recvShadows ) ) {
1426                         return qfalse;
1427                 }
1428                 //%     Sys_Printf( "%d:%d ", tt->castShadows, trace->recvShadows );
1429         }
1430
1431         /* receive shadows from the same group only (< 0) */
1432         else
1433         {
1434                 if ( abs( ti->castShadows ) != abs( trace->recvShadows ) ) {
1435                         return qfalse;
1436                 }
1437         }
1438
1439         /* skip patches when doing the grid (FIXME this is an ugly hack) */
1440         if ( inGrid ) {
1441                 if ( ti->skipGrid ) {
1442                         return qfalse;
1443                 }
1444         }
1445
1446         /* begin calculating determinant - also used to calculate u parameter */
1447         CrossProduct( trace->direction, tt->edge2, pvec );
1448
1449         /* if determinant is near zero, trace lies in plane of triangle */
1450         det = DotProduct( tt->edge1, pvec );
1451
1452         /* the non-culling branch */
1453         if ( fabs( det ) < COPLANAR_EPSILON ) {
1454                 return qfalse;
1455         }
1456         invDet = 1.0f / det;
1457
1458         /* calculate distance from first vertex to ray origin */
1459         VectorSubtract( trace->origin, tt->v[ 0 ].xyz, tvec );
1460
1461         /* calculate u parameter and test bounds */
1462         u = DotProduct( tvec, pvec ) * invDet;
1463         if ( u < -BARY_EPSILON || u > ( 1.0f + BARY_EPSILON ) ) {
1464                 return qfalse;
1465         }
1466
1467         /* prepare to test v parameter */
1468         CrossProduct( tvec, tt->edge1, qvec );
1469
1470         /* calculate v parameter and test bounds */
1471         v = DotProduct( trace->direction, qvec ) * invDet;
1472         if ( v < -BARY_EPSILON || ( u + v ) > ( 1.0f + BARY_EPSILON ) ) {
1473                 return qfalse;
1474         }
1475
1476         /* calculate t (depth) */
1477         depth = DotProduct( tt->edge2, qvec ) * invDet;
1478         if ( depth <= trace->inhibitRadius || depth >= trace->distance ) {
1479                 return qfalse;
1480         }
1481
1482         /* if hitpoint is really close to trace origin (sample point), then check for self-shadowing */
1483         if ( depth <= SELF_SHADOW_EPSILON ) {
1484                 /* don't self-shadow */
1485                 for ( i = 0; i < trace->numSurfaces; i++ )
1486                 {
1487                         if ( ti->surfaceNum == trace->surfaces[ i ] ) {
1488                                 return qfalse;
1489                         }
1490                 }
1491         }
1492
1493         /* stack compile flags */
1494         trace->compileFlags |= si->compileFlags;
1495
1496         /* don't trace against sky */
1497         if ( si->compileFlags & C_SKY ) {
1498                 return qfalse;
1499         }
1500
1501         /* most surfaces are completely opaque */
1502         if ( !( si->compileFlags & ( C_ALPHASHADOW | C_LIGHTFILTER ) ) ||
1503                  si->lightImage == NULL || si->lightImage->pixels == NULL ) {
1504                 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1505                 VectorClear( trace->color );
1506                 trace->opaque = qtrue;
1507                 return qtrue;
1508         }
1509
1510         /* force subsampling because the lighting is texture dependent */
1511         trace->forceSubsampling = 1.0;
1512
1513         /* try to avoid double shadows near triangle seams */
1514         if ( u < -ASLF_EPSILON || u > ( 1.0f + ASLF_EPSILON ) ||
1515                  v < -ASLF_EPSILON || ( u + v ) > ( 1.0f + ASLF_EPSILON ) ) {
1516                 return qfalse;
1517         }
1518
1519         /* calculate w parameter */
1520         w = 1.0f - ( u + v );
1521
1522         /* calculate st from uvw (barycentric) coordinates */
1523         s = w * tt->v[ 0 ].st[ 0 ] + u * tt->v[ 1 ].st[ 0 ] + v * tt->v[ 2 ].st[ 0 ];
1524         t = w * tt->v[ 0 ].st[ 1 ] + u * tt->v[ 1 ].st[ 1 ] + v * tt->v[ 2 ].st[ 1 ];
1525         s = s - floor( s );
1526         t = t - floor( t );
1527         is = s * si->lightImage->width;
1528         it = t * si->lightImage->height;
1529         if ( is < 0 ) {
1530                 is = 0;
1531         }
1532         if ( is > si->lightImage->width - 1 ) {
1533                 is = si->lightImage->width - 1;
1534         }
1535         if ( it < 0 ) {
1536                 it = 0;
1537         }
1538         if ( it > si->lightImage->height - 1 ) {
1539                 it = si->lightImage->height - 1;
1540         }
1541
1542         /* get pixel */
1543         pixel = si->lightImage->pixels + 4 * ( it * si->lightImage->width + is );
1544
1545         /* ydnar: color filter */
1546         if ( si->compileFlags & C_LIGHTFILTER ) {
1547                 /* filter by texture color */
1548                 trace->color[ 0 ] *= ( ( 1.0f / 255.0f ) * pixel[ 0 ] );
1549                 trace->color[ 1 ] *= ( ( 1.0f / 255.0f ) * pixel[ 1 ] );
1550                 trace->color[ 2 ] *= ( ( 1.0f / 255.0f ) * pixel[ 2 ] );
1551         }
1552
1553         /* ydnar: alpha filter */
1554         if ( si->compileFlags & C_ALPHASHADOW ) {
1555                 /* filter by inverse texture alpha */
1556                 shadow = ( 1.0f / 255.0f ) * ( 255 - pixel[ 3 ] );
1557                 trace->color[ 0 ] *= shadow;
1558                 trace->color[ 1 ] *= shadow;
1559                 trace->color[ 2 ] *= shadow;
1560         }
1561
1562         /* check filter for opaque */
1563         if ( trace->color[ 0 ] <= 0.001f && trace->color[ 1 ] <= 0.001f && trace->color[ 2 ] <= 0.001f ) {
1564                 VectorClear( trace->color );
1565                 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1566                 trace->opaque = qtrue;
1567                 return qtrue;
1568         }
1569
1570         /* continue tracing */
1571         return qfalse;
1572 }
1573
1574
1575
1576 /*
1577    TraceWinding() - ydnar
1578    temporary hack
1579  */
1580
1581 qboolean TraceWinding( traceWinding_t *tw, trace_t *trace ){
1582         int i;
1583         traceTriangle_t tt;
1584
1585
1586         /* initial setup */
1587         tt.infoNum = tw->infoNum;
1588         tt.v[ 0 ] = tw->v[ 0 ];
1589
1590         /* walk vertex list */
1591         for ( i = 1; i + 1 < tw->numVerts; i++ )
1592         {
1593                 /* set verts */
1594                 tt.v[ 1 ] = tw->v[ i ];
1595                 tt.v[ 2 ] = tw->v[ i + 1 ];
1596
1597                 /* find vectors for two edges sharing the first vert */
1598                 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
1599                 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
1600
1601                 /* trace it */
1602                 if ( TraceTriangle( &traceInfos[ tt.infoNum ], &tt, trace ) ) {
1603                         return qtrue;
1604                 }
1605         }
1606
1607         /* done */
1608         return qfalse;
1609 }
1610
1611
1612
1613
1614 /*
1615    TraceLine_r()
1616    returns qtrue if something is hit and tracing can stop
1617
1618    SmileTheory: made half-iterative
1619  */
1620
1621 #define TRACELINE_R_HALF_ITERATIVE 1
1622
1623 #if TRACELINE_R_HALF_ITERATIVE
1624 static qboolean TraceLine_r( int nodeNum, const vec3_t start, const vec3_t end, trace_t *trace )
1625 #else
1626 static qboolean TraceLine_r( int nodeNum, const vec3_t origin, const vec3_t end, trace_t *trace )
1627 #endif
1628 {
1629         traceNode_t     *node;
1630         int side;
1631         float front, back, frac;
1632         vec3_t mid;
1633
1634 #if TRACELINE_R_HALF_ITERATIVE
1635         vec3_t origin;
1636         VectorCopy( start, origin );
1637
1638         while ( 1 )
1639 #endif
1640         {
1641                 /* bogus node number means solid, end tracing unless testing all */
1642                 if ( nodeNum < 0 ) {
1643                         VectorCopy( origin, trace->hit );
1644                         trace->passSolid = qtrue;
1645                         return qtrue;
1646                 }
1647
1648                 /* get node */
1649                 node = &traceNodes[ nodeNum ];
1650
1651                 /* solid? */
1652                 if ( node->type == TRACE_LEAF_SOLID ) {
1653                         VectorCopy( origin, trace->hit );
1654                         trace->passSolid = qtrue;
1655                         return qtrue;
1656                 }
1657
1658                 /* leafnode? */
1659                 if ( node->type < 0 ) {
1660                         /* note leaf and return */
1661                         if ( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES ) {
1662                                 trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
1663                         }
1664                         return qfalse;
1665                 }
1666
1667                 /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
1668                 if ( trace->testAll && node->numItems == 0 ) {
1669                         return qfalse;
1670                 }
1671
1672                 /* classify beginning and end points */
1673                 switch ( node->type )
1674                 {
1675                 case PLANE_X:
1676                         front = origin[ 0 ] - node->plane[ 3 ];
1677                         back = end[ 0 ] - node->plane[ 3 ];
1678                         break;
1679
1680                 case PLANE_Y:
1681                         front = origin[ 1 ] - node->plane[ 3 ];
1682                         back = end[ 1 ] - node->plane[ 3 ];
1683                         break;
1684
1685                 case PLANE_Z:
1686                         front = origin[ 2 ] - node->plane[ 3 ];
1687                         back = end[ 2 ] - node->plane[ 3 ];
1688                         break;
1689
1690                 default:
1691                         front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
1692                         back = DotProduct( end, node->plane ) - node->plane[ 3 ];
1693                         break;
1694                 }
1695
1696                 /* entirely in front side? */
1697                 if ( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON ) {
1698 #if TRACELINE_R_HALF_ITERATIVE
1699                         nodeNum = node->children[ 0 ];
1700                         continue;
1701 #else
1702                         return TraceLine_r( node->children[ 0 ], origin, end, trace );
1703 #endif
1704                 }
1705
1706                 /* entirely on back side? */
1707                 if ( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON ) {
1708 #if TRACELINE_R_HALF_ITERATIVE
1709                         nodeNum = node->children[ 1 ];
1710                         continue;
1711 #else
1712                         return TraceLine_r( node->children[ 1 ], origin, end, trace );
1713 #endif
1714                 }
1715
1716                 /* select side */
1717                 side = front < 0;
1718
1719                 /* calculate intercept point */
1720                 frac = front / ( front - back );
1721                 mid[ 0 ] = origin[ 0 ] + ( end[ 0 ] - origin[ 0 ] ) * frac;
1722                 mid[ 1 ] = origin[ 1 ] + ( end[ 1 ] - origin[ 1 ] ) * frac;
1723                 mid[ 2 ] = origin[ 2 ] + ( end[ 2 ] - origin[ 2 ] ) * frac;
1724
1725                 /* fixme: check inhibit radius, then solid nodes and ignore */
1726
1727                 /* set trace hit here */
1728                 //%     VectorCopy( mid, trace->hit );
1729
1730                 /* trace first side */
1731                 if ( TraceLine_r( node->children[ side ], origin, mid, trace ) ) {
1732                         return qtrue;
1733                 }
1734
1735                 /* trace other side */
1736 #if TRACELINE_R_HALF_ITERATIVE
1737                 nodeNum = node->children[ !side ];
1738                 VectorCopy( mid, origin );
1739 #else
1740                 return TraceLine_r( node->children[ !side ], mid, end, trace );
1741 #endif
1742         }
1743 }
1744
1745
1746
1747 /*
1748    TraceLine() - ydnar
1749    rewrote this function a bit :)
1750  */
1751
1752 void TraceLine( trace_t *trace ){
1753         int i, j;
1754         traceNode_t     *node;
1755         traceTriangle_t *tt;
1756         traceInfo_t     *ti;
1757
1758
1759         /* setup output (note: this code assumes the input data is completely filled out) */
1760         trace->passSolid = qfalse;
1761         trace->opaque = qfalse;
1762         trace->compileFlags = 0;
1763         trace->numTestNodes = 0;
1764
1765         /* early outs */
1766         if ( !trace->recvShadows || !trace->testOcclusion || trace->distance <= 0.00001f ) {
1767                 return;
1768         }
1769
1770         /* trace through nodes */
1771         TraceLine_r( headNodeNum, trace->origin, trace->end, trace );
1772         if ( trace->passSolid && !trace->testAll ) {
1773                 trace->opaque = qtrue;
1774                 return;
1775         }
1776
1777         /* skip surfaces? */
1778         if ( noSurfaces ) {
1779                 return;
1780         }
1781
1782         /* testall means trace through sky */
1783         if ( trace->testAll && trace->numTestNodes < MAX_TRACE_TEST_NODES &&
1784                  trace->compileFlags & C_SKY &&
1785                  ( trace->numSurfaces == 0 || surfaceInfos[ trace->surfaces[ 0 ] ].childSurfaceNum < 0 ) ) {
1786                 //%     trace->testNodes[ trace->numTestNodes++ ] = skyboxNodeNum;
1787                 TraceLine_r( skyboxNodeNum, trace->origin, trace->end, trace );
1788         }
1789
1790         /* walk node list */
1791         for ( i = 0; i < trace->numTestNodes; i++ )
1792         {
1793                 /* get node */
1794                 node = &traceNodes[ trace->testNodes[ i ] ];
1795
1796                 /* walk node item list */
1797                 for ( j = 0; j < node->numItems; j++ )
1798                 {
1799                         tt = &traceTriangles[ node->items[ j ] ];
1800                         ti = &traceInfos[ tt->infoNum ];
1801                         if ( TraceTriangle( ti, tt, trace ) ) {
1802                                 return;
1803                         }
1804                         //%     if( TraceWinding( &traceWindings[ node->items[ j ] ], trace ) )
1805                         //%             return;
1806                 }
1807         }
1808 }
1809
1810
1811
1812 /*
1813    SetupTrace() - ydnar
1814    sets up certain trace values
1815  */
1816
1817 float SetupTrace( trace_t *trace ){
1818         VectorSubtract( trace->end, trace->origin, trace->displacement );
1819         trace->distance = VectorFastNormalize( trace->displacement, trace->direction );
1820         VectorCopy( trace->origin, trace->hit );
1821         return trace->distance;
1822 }