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