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