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