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