tools/quake3/q3map2/light_trace.c

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