tools/quake3/q3map2/light_trace.c

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