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