1 /* -------------------------------------------------------------------------------
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
6 This file is part of GtkRadiant.
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.
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.
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
22 ----------------------------------------------------------------------------------
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."
27 ------------------------------------------------------------------------------- */
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 ])
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
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
59 #define MAX_TW_VERTS 24 // vortex: increased from 12 to 24 for ability co compile some insane maps with large curve count
61 #define TRACE_ON_EPSILON 0.1f
64 #define TRACE_LEAF_SOLID -2
66 typedef struct traceVert_s
73 typedef struct traceInfo_s
76 int surfaceNum, castShadows, skipGrid;
80 typedef struct traceWinding_s
83 int infoNum, numVerts;
84 traceVert_t v[ MAX_TW_VERTS ];
88 typedef struct traceTriangle_s
96 typedef struct traceNode_s
102 int numItems, maxItems;
108 int noDrawContentFlags, noDrawSurfaceFlags, noDrawCompileFlags;
110 int numTraceInfos = 0, maxTraceInfos = 0, firstTraceInfo = 0;
111 traceInfo_t *traceInfos = NULL;
113 int numTraceWindings = 0, maxTraceWindings = 0, deadWinding = -1;
114 traceWinding_t *traceWindings = NULL;
116 int numTraceTriangles = 0, maxTraceTriangles = 0, deadTriangle = -1;
117 traceTriangle_t *traceTriangles = NULL;
119 int headNodeNum = 0, skyboxNodeNum = 0, maxTraceDepth = 0, numTraceLeafNodes = 0;
120 int numTraceNodes = 0, maxTraceNodes = 0;
121 traceNode_t *traceNodes = NULL;
125 /* -------------------------------------------------------------------------------
127 allocation and list management
129 ------------------------------------------------------------------------------- */
132 AddTraceInfo() - ydnar
133 adds a trace info structure to the pool
136 static int AddTraceInfo( traceInfo_t *ti )
142 /* find an existing info */
143 for( num = firstTraceInfo; num < numTraceInfos; num++ )
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 )
153 if( numTraceInfos >= maxTraceInfos )
155 /* allocate more room */
156 maxTraceInfos += GROW_TRACE_INFOS;
157 temp = safe_malloc( maxTraceInfos * sizeof( *traceInfos ) );
158 if( traceInfos != NULL )
160 memcpy( temp, traceInfos, numTraceInfos * sizeof( *traceInfos ) );
163 traceInfos = (traceInfo_t*) temp;
167 memcpy( &traceInfos[ num ], ti, sizeof( *traceInfos ) );
168 if( num == numTraceInfos )
171 /* return the ti number */
178 AllocTraceNode() - ydnar
179 allocates a new trace node
182 static int AllocTraceNode( void )
188 if( numTraceNodes >= maxTraceNodes )
190 /* reallocate more room */
191 maxTraceNodes += GROW_TRACE_NODES;
192 temp = safe_malloc( maxTraceNodes * sizeof( traceNode_t ) );
193 if( traceNodes != NULL )
195 memcpy( temp, traceNodes, numTraceNodes * sizeof( traceNode_t ) );
202 memset( &traceNodes[ numTraceNodes ], 0, sizeof( traceNode_t ) );
203 traceNodes[ numTraceNodes ].type = TRACE_LEAF;
204 ClearBounds( traceNodes[ numTraceNodes ].mins, traceNodes[ numTraceNodes ].maxs );
206 /* Sys_Printf("alloc node %d\n", numTraceNodes); */
210 /* return the count */
211 return (numTraceNodes - 1);
217 AddTraceWinding() - ydnar
218 adds a winding to the raytracing pool
221 static int AddTraceWinding( traceWinding_t *tw )
227 /* check for a dead winding */
228 if( deadWinding >= 0 && deadWinding < numTraceWindings )
232 /* put winding at the end of the list */
233 num = numTraceWindings;
236 if( numTraceWindings >= maxTraceWindings )
238 /* allocate more room */
239 maxTraceWindings += GROW_TRACE_WINDINGS;
240 temp = safe_malloc( maxTraceWindings * sizeof( *traceWindings ) );
241 if( traceWindings != NULL )
243 memcpy( temp, traceWindings, numTraceWindings * sizeof( *traceWindings ) );
244 free( traceWindings );
246 traceWindings = (traceWinding_t*) temp;
250 /* add the winding */
251 memcpy( &traceWindings[ num ], tw, sizeof( *traceWindings ) );
252 if( num == numTraceWindings )
256 /* return the winding number */
263 AddTraceTriangle() - ydnar
264 adds a triangle to the raytracing pool
267 static int AddTraceTriangle( traceTriangle_t *tt )
273 /* check for a dead triangle */
274 if( deadTriangle >= 0 && deadTriangle < numTraceTriangles )
278 /* put triangle at the end of the list */
279 num = numTraceTriangles;
282 if( numTraceTriangles >= maxTraceTriangles )
284 /* allocate more room */
285 maxTraceTriangles += GROW_TRACE_TRIANGLES;
286 temp = safe_malloc( maxTraceTriangles * sizeof( *traceTriangles ) );
287 if( traceTriangles != NULL )
289 memcpy( temp, traceTriangles, numTraceTriangles * sizeof( *traceTriangles ) );
290 free( traceTriangles );
292 traceTriangles = (traceTriangle_t*) temp;
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 );
300 /* add the triangle */
301 memcpy( &traceTriangles[ num ], tt, sizeof( *traceTriangles ) );
302 if( num == numTraceTriangles )
306 /* return the triangle number */
313 AddItemToTraceNode() - ydnar
314 adds an item reference (winding or triangle) to a trace node
317 static int AddItemToTraceNode( traceNode_t *node, int num )
327 if( node->numItems >= node->maxItems )
329 /* allocate more room */
330 if( node == traceNodes )
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 )
339 memcpy( temp, node->items, node->numItems * sizeof( *node->items ) );
342 node->items = (int*) temp;
346 node->items[ node->numItems ] = num;
349 /* return the count */
350 return (node->numItems - 1);
356 /* -------------------------------------------------------------------------------
360 ------------------------------------------------------------------------------- */
363 SetupTraceNodes_r() - ydnar
364 recursively create the initial trace node structure from the bsp tree
367 static int SetupTraceNodes_r( int bspNodeNum )
369 int i, nodeNum, bspLeafNum, newNode;
374 /* get bsp node and plane */
375 bspNode = &bspNodes[ bspNodeNum ];
376 plane = &bspPlanes[ bspNode->planeNum ];
378 /* allocate a new trace node */
379 nodeNum = AllocTraceNode();
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;
387 for( i = 0; i < 2; i++ )
390 if( bspNode->children[ i ] < 0 )
392 bspLeafNum = -bspNode->children[ i ] - 1;
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 */
399 if( bspLeafs[ bspLeafNum ].cluster == -1 )
400 traceNodes[ traceNodes[ nodeNum ].children[ i ] ].type = TRACE_LEAF_SOLID;
406 newNode = SetupTraceNodes_r( bspNode->children[ i ] );
407 traceNodes[ nodeNum ].children[ i ] = newNode;
410 if(traceNodes[ nodeNum ].children[ i ] == 0)
411 Error( "Invalid tracenode allocated" );
414 /* Sys_Printf("node %d children: %d %d\n", nodeNum, traceNodes[ nodeNum ].children[0], traceNodes[ nodeNum ].children[1]); */
416 /* return node number */
423 ClipTraceWinding() - ydnar
424 clips a trace winding against a plane into one or two parts
427 #define TW_ON_EPSILON 0.25f
429 void ClipTraceWinding( traceWinding_t *tw, vec4_t plane, traceWinding_t *front, traceWinding_t *back )
432 int sides[ MAX_TW_VERTS ], counts[ 3 ] = { 0, 0, 0 };
433 float dists[ MAX_TW_VERTS ];
435 traceVert_t *a, *b, mid;
438 /* clear front and back */
442 /* classify points */
443 for( i = 0; i < tw->numVerts; i++ )
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;
451 sides[ i ] = SIDE_ON;
452 counts[ sides[ i ] ]++;
455 /* entirely on front? */
456 if( counts[ SIDE_BACK ] == 0 )
457 memcpy( front, tw, sizeof( *front ) );
459 /* entirely on back? */
460 else if( counts[ SIDE_FRONT ] == 0 )
461 memcpy( back, tw, sizeof( *back ) );
463 /* straddles the plane */
466 /* setup front and back */
467 memcpy( front, tw, sizeof( *front ) );
469 memcpy( back, tw, sizeof( *back ) );
472 /* split the winding */
473 for( i = 0; i < tw->numVerts; i++ )
476 j = (i + 1) % tw->numVerts;
482 /* handle points on the splitting plane */
486 if( front->numVerts >= MAX_TW_VERTS )
487 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
488 front->v[ front->numVerts++ ] = *a;
492 if( back->numVerts >= MAX_TW_VERTS )
493 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
494 back->v[ back->numVerts++ ] = *a;
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;
505 /* check next point to see if we need to split the edge */
506 if( sides[ j ] == SIDE_ON || sides[ j ] == sides[ i ] )
510 if( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS )
511 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
513 /* generate a split point */
514 frac = dists[ i ] / (dists[ i ] - dists[ j ]);
515 for( k = 0; k < 3; k++ )
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 ];
523 mid.xyz[ k ] = a->xyz[ k ] + frac * (b->xyz[ k ] - a->xyz[ k ]);
525 /* set texture coordinates */
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 ]);
532 /* copy midpoint to front and back polygons */
533 front->v[ front->numVerts++ ] = mid;
534 back->v[ back->numVerts++ ] = mid;
542 FilterPointToTraceNodes_r() - ydnar
546 static int FilterPointToTraceNodes_r( vec3_t pt, int nodeNum )
552 if( nodeNum < 0 || nodeNum >= numTraceNodes )
555 node = &traceNodes[ nodeNum ];
557 if( node->type >= 0 )
559 dot = DotProduct( pt, node->plane ) - node->plane[ 3 ];
561 FilterPointToTraceNodes_r( pt, node->children[ 0 ] );
563 FilterPointToTraceNodes_r( pt, node->children[ 1 ] );
567 Sys_Printf( "%d ", nodeNum );
575 FilterTraceWindingIntoNodes_r() - ydnar
576 filters a trace winding into the raytracing tree
579 static void FilterTraceWindingIntoNodes_r( traceWinding_t *tw, int nodeNum )
582 vec4_t plane1, plane2, reverse;
584 traceWinding_t front, back;
587 /* don't filter if passed a bogus node (solid, etc) */
588 if( nodeNum < 0 || nodeNum >= numTraceNodes )
592 node = &traceNodes[ nodeNum ];
594 /* is this a decision node? */
595 if( node->type >= 0 )
597 /* create winding plane if necessary, filtering out bogus windings as well */
598 if( nodeNum == headNodeNum )
600 if( !PlaneFromPoints( tw->plane, tw->v[ 0 ].xyz, tw->v[ 1 ].xyz, tw->v[ 2 ].xyz ) )
604 /* validate the node */
605 if( node->children[ 0 ] == 0 || node->children[ 1 ] == 0 )
606 Error( "Invalid tracenode: %d", nodeNum );
609 Vector4Copy( node->plane, plane1 );
611 /* get winding plane */
612 Vector4Copy( tw->plane, plane2 );
614 /* invert surface plane */
615 VectorSubtract( vec3_origin, plane2, reverse );
616 reverse[ 3 ] = -plane2[ 3 ];
619 if( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f )
621 FilterTraceWindingIntoNodes_r( tw, node->children[ 0 ] );
626 if( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f )
628 FilterTraceWindingIntoNodes_r( tw, node->children[ 1 ] );
632 /* clip the winding by node plane */
633 ClipTraceWinding( tw, plane1, &front, &back );
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 ] );
641 /* return to caller */
645 /* add winding to leaf node */
646 num = AddTraceWinding( tw );
647 AddItemToTraceNode( node, num );
653 SubdivideTraceNode_r() - ydnar
654 recursively subdivides a tracing node until it meets certain size and complexity criteria
657 static void SubdivideTraceNode_r( int nodeNum, int depth )
659 int i, j, count, num, frontNum, backNum, type;
663 traceNode_t *node, *frontNode, *backNode;
664 traceWinding_t *tw, front, back;
668 if( nodeNum < 0 || nodeNum >= numTraceNodes )
672 node = &traceNodes[ nodeNum ];
674 /* runaway recursion check */
675 if( depth >= MAX_TRACE_DEPTH )
677 //% Sys_Printf( "Depth: (%d items)\n", node->numItems );
683 /* is this a decision node? */
684 if( node->type >= 0 )
686 /* subdivide children */
687 frontNum = node->children[ 0 ];
688 backNum = node->children[ 1 ];
689 SubdivideTraceNode_r( frontNum, depth );
690 SubdivideTraceNode_r( backNum, depth );
695 ClearBounds( node->mins, node->maxs );
696 VectorClear( average );
698 for( i = 0; i < node->numItems; i++ )
701 tw = &traceWindings[ node->items[ i ] ];
704 for( j = 0; j < tw->numVerts; j++ )
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 ];
714 /* check triangle limit */
715 //% if( node->numItems <= MAX_NODE_ITEMS )
716 if( (count - (node->numItems * 2)) < MAX_NODE_TRIANGLES )
718 //% Sys_Printf( "Limit: (%d triangles)\n", (count - (node->numItems * 2)) );
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 ] )
727 else if( size[ 1 ] >= size[ 0 ] && size[ 1 ] >= size[ 2 ] )
732 /* don't split small nodes */
733 if( size[ type ] <= MIN_NODE_SIZE )
735 //% Sys_Printf( "Limit: %f %f %f (%d items)\n", size[ 0 ], size[ 1 ], size[ 2 ], node->numItems );
740 /* set max trace depth */
741 if( depth > maxTraceDepth )
742 maxTraceDepth = depth;
744 /* snap the average */
745 dist = floor( average[ type ] / count );
748 if( dist <= node->mins[ type ] || dist >= node->maxs[ type ] )
749 dist = floor( 0.5f * (node->mins[ type ] + node->maxs[ type ]) );
751 /* allocate child nodes */
752 frontNum = AllocTraceNode();
753 backNum = AllocTraceNode();
756 node = &traceNodes[ nodeNum ];
757 frontNode = &traceNodes[ frontNum ];
758 backNode = &traceNodes[ backNum ];
760 /* attach children */
762 node->plane[ type ] = 1.0f;
763 node->plane[ 3 ] = dist;
764 node->children[ 0 ] = frontNum;
765 node->children[ 1 ] = backNum;
767 /* setup front node */
768 frontNode->maxItems = (node->maxItems >> 1);
769 frontNode->items = safe_malloc( frontNode->maxItems * sizeof( *frontNode->items ) );
771 /* setup back node */
772 backNode->maxItems = (node->maxItems >> 1);
773 backNode->items = safe_malloc( backNode->maxItems * sizeof( *backNode->items ) );
775 /* filter windings into child nodes */
776 for( i = 0; i < node->numItems; i++ )
779 tw = &traceWindings[ node->items[ i ] ];
781 /* clip the winding by the new split plane */
782 ClipTraceWinding( tw, node->plane, &front, &back );
784 /* kill the existing winding */
785 if( front.numVerts >= 3 || back.numVerts >= 3 )
786 deadWinding = node->items[ i ];
788 /* add front winding */
789 if( front.numVerts >= 3 )
791 num = AddTraceWinding( &front );
792 AddItemToTraceNode( frontNode, num );
795 /* add back winding */
796 if( back.numVerts >= 3 )
798 num = AddTraceWinding( &back );
799 AddItemToTraceNode( backNode, num );
803 /* free original node winding list */
810 if( frontNode->numItems <= 0 )
812 frontNode->maxItems = 0;
813 free( frontNode->items );
814 frontNode->items = NULL;
817 if( backNode->numItems <= 0 )
819 backNode->maxItems = 0;
820 free( backNode->items );
821 backNode->items = NULL;
824 /* subdivide children */
825 SubdivideTraceNode_r( frontNum, depth );
826 SubdivideTraceNode_r( backNum, depth );
832 TriangulateTraceNode_r()
833 optimizes the tracing data by changing trace windings into triangles
836 static int TriangulateTraceNode_r( int nodeNum )
838 int i, j, num, frontNum, backNum, numWindings, *windings;
845 if( nodeNum < 0 || nodeNum >= numTraceNodes )
849 node = &traceNodes[ nodeNum ];
851 /* is this a decision node? */
852 if( node->type >= 0 )
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;
863 if( node->numItems == 0 )
866 if( node->items != NULL )
868 return node->numItems;
871 /* store off winding data */
872 numWindings = node->numItems;
873 windings = node->items;
877 node->maxItems = numWindings * 2;
878 node->items = safe_malloc( node->maxItems * sizeof( tt ) );
880 /* walk winding list */
881 for( i = 0; i < numWindings; i++ )
884 tw = &traceWindings[ windings[ i ] ];
887 tt.infoNum = tw->infoNum;
888 tt.v[ 0 ] = tw->v[ 0 ];
890 /* walk vertex list */
891 for( j = 1; j + 1 < tw->numVerts; j++ )
894 tt.v[ 1 ] = tw->v[ j ];
895 tt.v[ 2 ] = tw->v[ j + 1 ];
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 );
901 /* add it to the node */
902 num = AddTraceTriangle( &tt );
903 AddItemToTraceNode( node, num );
908 if( windings != NULL )
911 /* return item count */
912 return node->numItems;
917 /* -------------------------------------------------------------------------------
919 shadow casting item setup (triangles, patches, entities)
921 ------------------------------------------------------------------------------- */
924 PopulateWithBSPModel() - ydnar
925 filters a bsp model's surfaces into the raytracing tree
928 static void PopulateWithBSPModel( bspModel_t *model, m4x4_t transform )
930 int i, j, x, y, pw[ 5 ], r, nodeNum;
931 bspDrawSurface_t *ds;
933 bspDrawVert_t *verts;
935 mesh_t srcMesh, *mesh, *subdivided;
941 if( model == NULL || transform == NULL )
944 /* walk the list of surfaces in this model and fill out the info structs */
945 for( i = 0; i < model->numBSPSurfaces; i++ )
947 /* get surface and info */
948 ds = &bspDrawSurfaces[ model->firstBSPSurface + i ];
949 info = &surfaceInfos[ model->firstBSPSurface + i ];
950 if( info->si == NULL )
954 if( !info->castShadows )
958 if( ds->surfaceType == MST_PATCH && patchShadows == qfalse )
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) )
966 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
967 if( (info->si->compileFlags & C_NODRAW) )
969 if( (info->si->compileFlags & C_TRANSLUCENT) &&
970 !(info->si->compileFlags & C_ALPHASHADOW) &&
971 !(info->si->compileFlags & C_LIGHTFILTER) )
974 /* setup trace info */
976 ti.castShadows = info->castShadows;
977 ti.surfaceNum = model->firstBSPBrush + i;
978 ti.skipGrid = (ds->surfaceType == MST_PATCH);
980 /* choose which node (normal or skybox) */
981 if( info->parentSurfaceNum >= 0 )
983 nodeNum = skyboxNodeNum;
985 /* sky surfaces in portal skies are ignored */
986 if( info->si->compileFlags & C_SKY )
990 nodeNum = headNodeNum;
992 /* setup trace winding */
993 memset( &tw, 0, sizeof( tw ) );
994 tw.infoNum = AddTraceInfo( &ti );
998 switch( ds->surfaceType )
1000 /* handle patches */
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 );
1009 /* fit it to the curve and remove colinear verts on rows/columns */
1010 PutMeshOnCurve( *subdivided );
1011 mesh = RemoveLinearMeshColumnsRows( subdivided );
1012 FreeMesh( subdivided );
1015 verts = mesh->verts;
1017 /* subdivide each quad to place the models */
1018 for( y = 0; y < (mesh->height - 1); y++ )
1020 for( x = 0; x < (mesh->width - 1); x++ )
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 ] */
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 );
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 );
1058 /* free the subdivided mesh */
1062 /* handle triangle surfaces */
1063 case MST_TRIANGLE_SOUP:
1065 /* set verts and indexes */
1066 verts = &bspDrawVerts[ ds->firstVert ];
1067 indexes = &bspDrawIndexes[ ds->firstIndex ];
1069 /* walk the triangle list */
1070 for( j = 0; j < ds->numIndexes; j += 3 )
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 );
1085 /* other surface types do not cast shadows */
1095 PopulateWithPicoModel() - ydnar
1096 filters a picomodel's surfaces into the raytracing tree
1099 static void PopulateWithPicoModel( int castShadows, picoModel_t *model, m4x4_t transform )
1101 int i, j, k, numSurfaces, numIndexes;
1102 picoSurface_t *surface;
1103 picoShader_t *shader;
1104 picoVec_t *xyz, *st;
1105 picoIndex_t *indexes;
1111 if( model == NULL || transform == NULL )
1115 numSurfaces = PicoGetModelNumSurfaces( model );
1117 /* walk the list of surfaces in this model and fill out the info structs */
1118 for( i = 0; i < numSurfaces; i++ )
1121 surface = PicoGetModelSurface( model, i );
1122 if( surface == NULL )
1125 /* only handle triangle surfaces initially (fixme: support patches) */
1126 if( PicoGetSurfaceType( surface ) != PICO_TRIANGLES )
1129 /* get shader (fixme: support shader remapping) */
1130 shader = PicoGetSurfaceShader( surface );
1131 if( shader == NULL )
1133 ti.si = ShaderInfoForShader( PicoGetShaderName( shader ) );
1137 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
1138 if( (ti.si->compileFlags & C_NODRAW) )
1140 if( (ti.si->compileFlags & C_TRANSLUCENT) &&
1141 !(ti.si->compileFlags & C_ALPHASHADOW) &&
1142 !(ti.si->compileFlags & C_LIGHTFILTER) )
1145 /* setup trace info */
1146 ti.castShadows = castShadows;
1148 ti.skipGrid = qtrue; // also ignore picomodels when skipping patches
1150 /* setup trace winding */
1151 memset( &tw, 0, sizeof( tw ) );
1152 tw.infoNum = AddTraceInfo( &ti );
1156 numIndexes = PicoGetSurfaceNumIndexes( surface );
1157 indexes = PicoGetSurfaceIndexes( surface, 0 );
1159 /* walk the triangle list */
1160 for( j = 0; j < numIndexes; j += 3, indexes += 3 )
1162 for( k = 0; k < 3; k++ )
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 );
1170 FilterTraceWindingIntoNodes_r( &tw, headNodeNum );
1178 PopulateTraceNodes() - ydnar
1179 fills the raytracing tree with world and entity occluders
1182 static void PopulateTraceNodes( void )
1184 int i, m, frame, castShadows;
1189 vec3_t origin, scale, angles;
1193 /* add worldspawn triangles */
1194 m4x4_identity( transform );
1195 PopulateWithBSPModel( &bspModels[ 0 ], transform );
1197 /* walk each entity list */
1198 for( i = 1; i < numEntities; i++ )
1203 /* get shadow flags */
1204 castShadows = ENTITY_CAST_SHADOWS;
1205 GetEntityShadowFlags( e, NULL, &castShadows, NULL );
1211 /* get entity origin */
1212 GetVectorForKey( e, "origin", origin );
1215 scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = 1.0f;
1216 temp = FloatForKey( e, "modelscale" );
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 ] );
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 ] );
1230 /* set transform matrix (thanks spog) */
1231 m4x4_identity( transform );
1232 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
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 );
1240 value = ValueForKey( e, "model" );
1242 /* switch on model type */
1243 switch( value[ 0 ] )
1251 m = atoi( &value[ 1 ] );
1252 if( m <= 0 || m >= numBSPModels )
1254 PopulateWithBSPModel( &bspModels[ m ], transform );
1257 /* external model */
1259 frame = IntForKey( e, "_frame" );
1260 model = LoadModel( (char*) value, frame );
1263 PopulateWithPicoModel( castShadows, model, transform );
1268 value = ValueForKey( e, "model2" );
1270 /* switch on model type */
1271 switch( value[ 0 ] )
1279 m = atoi( &value[ 1 ] );
1280 if( m <= 0 || m >= numBSPModels )
1282 PopulateWithBSPModel( &bspModels[ m ], transform );
1285 /* external model */
1287 frame = IntForKey( e, "_frame2" );
1288 model = LoadModel( (char*) value, frame );
1291 PopulateWithPicoModel( castShadows, model, transform );
1300 /* -------------------------------------------------------------------------------
1302 trace initialization
1304 ------------------------------------------------------------------------------- */
1307 SetupTraceNodes() - ydnar
1308 creates a balanced bsp with axis-aligned splits for efficient raytracing
1311 void SetupTraceNodes( void )
1314 Sys_FPrintf( SYS_VRB, "--- SetupTraceNodes ---\n" );
1316 /* find nodraw bit */
1317 noDrawContentFlags = noDrawSurfaceFlags = noDrawCompileFlags = 0;
1318 ApplySurfaceParm( "nodraw", &noDrawContentFlags, &noDrawSurfaceFlags, &noDrawCompileFlags );
1320 /* create the baseline raytracing tree from the bsp tree */
1321 headNodeNum = SetupTraceNodes_r( 0 );
1323 /* create outside node for skybox surfaces */
1324 skyboxNodeNum = AllocTraceNode();
1326 /* populate the tree with triangles from the world and shadow casting entities */
1327 PopulateTraceNodes();
1329 /* create the raytracing bsp */
1330 if( loMem == qfalse )
1332 SubdivideTraceNode_r( headNodeNum, 0 );
1333 SubdivideTraceNode_r( skyboxNodeNum, 0 );
1336 /* create triangles from the trace windings */
1337 TriangulateTraceNode_r( headNodeNum );
1338 TriangulateTraceNode_r( skyboxNodeNum );
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 );
1350 /* free trace windings */
1351 free( traceWindings );
1352 numTraceWindings = 0;
1353 maxTraceWindings = 0;
1356 /* debug code: write out trace triangles to an alias obj file */
1361 char filename[ 1024 ];
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" );
1372 Error( "Error opening %s for writing", filename );
1374 /* walk node list */
1375 for( i = 0; i < numTraceWindings; i++ )
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 ] );
1391 /* -------------------------------------------------------------------------------
1395 ------------------------------------------------------------------------------- */
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
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
1409 qboolean TraceTriangle( traceInfo_t *ti, traceTriangle_t *tt, trace_t *trace )
1412 float tvec[ 3 ], pvec[ 3 ], qvec[ 3 ];
1413 float det, invDet, depth;
1414 float u, v, w, s, t;
1421 /* don't double-trace against sky */
1423 if( trace->compileFlags & si->compileFlags & C_SKY )
1426 /* receive shadows from worldspawn group only */
1427 if( trace->recvShadows == 1 )
1429 if( ti->castShadows != 1 )
1433 /* receive shadows from same group and worldspawn group */
1434 else if( trace->recvShadows > 1 )
1436 if( ti->castShadows != 1 && abs( ti->castShadows ) != abs( trace->recvShadows ) )
1438 //% Sys_Printf( "%d:%d ", tt->castShadows, trace->recvShadows );
1441 /* receive shadows from the same group only (< 0) */
1444 if( abs( ti->castShadows ) != abs( trace->recvShadows ) )
1448 /* skip patches when doing the grid (FIXME this is an ugly hack) */
1455 /* begin calculating determinant - also used to calculate u parameter */
1456 CrossProduct( trace->direction, tt->edge2, pvec );
1458 /* if determinant is near zero, trace lies in plane of triangle */
1459 det = DotProduct( tt->edge1, pvec );
1461 /* the non-culling branch */
1462 if( fabs( det ) < COPLANAR_EPSILON )
1464 invDet = 1.0f / det;
1466 /* calculate distance from first vertex to ray origin */
1467 VectorSubtract( trace->origin, tt->v[ 0 ].xyz, tvec );
1469 /* calculate u parameter and test bounds */
1470 u = DotProduct( tvec, pvec ) * invDet;
1471 if( u < -BARY_EPSILON || u > (1.0f + BARY_EPSILON) )
1474 /* prepare to test v parameter */
1475 CrossProduct( tvec, tt->edge1, qvec );
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) )
1482 /* calculate t (depth) */
1483 depth = DotProduct( tt->edge2, qvec ) * invDet;
1484 if( depth <= trace->inhibitRadius || depth >= trace->distance )
1487 /* if hitpoint is really close to trace origin (sample point), then check for self-shadowing */
1488 if( depth <= SELF_SHADOW_EPSILON )
1490 /* don't self-shadow */
1491 for( i = 0; i < trace->numSurfaces; i++ )
1493 if( ti->surfaceNum == trace->surfaces[ i ] )
1498 /* stack compile flags */
1499 trace->compileFlags |= si->compileFlags;
1501 /* don't trace against sky */
1502 if( si->compileFlags & C_SKY )
1505 /* most surfaces are completely opaque */
1506 if( !(si->compileFlags & (C_ALPHASHADOW | C_LIGHTFILTER)) ||
1507 si->lightImage == NULL || si->lightImage->pixels == NULL )
1509 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1510 VectorClear( trace->color );
1511 trace->opaque = qtrue;
1515 /* try to avoid double shadows near triangle seams */
1516 if( u < -ASLF_EPSILON || u > (1.0f + ASLF_EPSILON) ||
1517 v < -ASLF_EPSILON || (u + v) > (1.0f + ASLF_EPSILON) )
1520 /* calculate w parameter */
1523 /* calculate st from uvw (barycentric) coordinates */
1524 s = w * tt->v[ 0 ].st[ 0 ] + u * tt->v[ 1 ].st[ 0 ] + v * tt->v[ 2 ].st[ 0 ];
1525 t = w * tt->v[ 0 ].st[ 1 ] + u * tt->v[ 1 ].st[ 1 ] + v * tt->v[ 2 ].st[ 1 ];
1528 is = s * si->lightImage->width;
1529 it = t * si->lightImage->height;
1532 pixel = si->lightImage->pixels + 4 * (it * si->lightImage->width + is);
1534 /* ydnar: color filter */
1535 if( si->compileFlags & C_LIGHTFILTER )
1537 /* filter by texture color */
1538 trace->color[ 0 ] *= ((1.0f / 255.0f) * pixel[ 0 ]);
1539 trace->color[ 1 ] *= ((1.0f / 255.0f) * pixel[ 1 ]);
1540 trace->color[ 2 ] *= ((1.0f / 255.0f) * pixel[ 2 ]);
1543 /* ydnar: alpha filter */
1544 if( si->compileFlags & C_ALPHASHADOW )
1546 /* filter by inverse texture alpha */
1547 shadow = (1.0f / 255.0f) * (255 - pixel[ 3 ]);
1548 trace->color[ 0 ] *= shadow;
1549 trace->color[ 1 ] *= shadow;
1550 trace->color[ 2 ] *= shadow;
1553 /* check filter for opaque */
1554 if( trace->color[ 0 ] <= 0.001f && trace->color[ 1 ] <= 0.001f && trace->color[ 2 ] <= 0.001f )
1556 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1557 trace->opaque = qtrue;
1561 /* continue tracing */
1568 TraceWinding() - ydnar
1572 qboolean TraceWinding( traceWinding_t *tw, trace_t *trace )
1579 tt.infoNum = tw->infoNum;
1580 tt.v[ 0 ] = tw->v[ 0 ];
1582 /* walk vertex list */
1583 for( i = 1; i + 1 < tw->numVerts; i++ )
1586 tt.v[ 1 ] = tw->v[ i ];
1587 tt.v[ 2 ] = tw->v[ i + 1 ];
1589 /* find vectors for two edges sharing the first vert */
1590 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
1591 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
1594 if( TraceTriangle( &traceInfos[ tt.infoNum ], &tt, trace ) )
1607 returns qtrue if something is hit and tracing can stop
1610 static qboolean TraceLine_r( int nodeNum, vec3_t origin, vec3_t end, trace_t *trace )
1614 float front, back, frac;
1619 /* bogus node number means solid, end tracing unless testing all */
1622 VectorCopy( origin, trace->hit );
1623 trace->passSolid = qtrue;
1628 node = &traceNodes[ nodeNum ];
1631 if( node->type == TRACE_LEAF_SOLID )
1633 VectorCopy( origin, trace->hit );
1634 trace->passSolid = qtrue;
1639 if( node->type < 0 )
1641 /* note leaf and return */
1642 if( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES )
1643 trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
1647 /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
1648 if( trace->testAll && node->numItems == 0 )
1651 /* classify beginning and end points */
1652 switch( node->type )
1655 front = origin[ 0 ] - node->plane[ 3 ];
1656 back = end[ 0 ] - node->plane[ 3 ];
1660 front = origin[ 1 ] - node->plane[ 3 ];
1661 back = end[ 1 ] - node->plane[ 3 ];
1665 front = origin[ 2 ] - node->plane[ 3 ];
1666 back = end[ 2 ] - node->plane[ 3 ];
1670 front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
1671 back = DotProduct( end, node->plane ) - node->plane[ 3 ];
1675 /* entirely in front side? */
1676 if( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON )
1677 return TraceLine_r( node->children[ 0 ], origin, end, trace );
1679 /* entirely on back side? */
1680 if( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON )
1681 return TraceLine_r( node->children[ 1 ], origin, end, trace );
1686 /* calculate intercept point */
1687 frac = front / (front - back);
1688 mid[ 0 ] = origin[ 0 ] + (end[ 0 ] - origin[ 0 ]) * frac;
1689 mid[ 1 ] = origin[ 1 ] + (end[ 1 ] - origin[ 1 ]) * frac;
1690 mid[ 2 ] = origin[ 2 ] + (end[ 2 ] - origin[ 2 ]) * frac;
1692 /* fixme: check inhibit radius, then solid nodes and ignore */
1694 /* set trace hit here */
1695 //% VectorCopy( mid, trace->hit );
1697 /* trace first side */
1698 r = TraceLine_r( node->children[ side ], origin, mid, trace );
1702 /* trace other side */
1703 return TraceLine_r( node->children[ !side ], mid, end, trace );
1710 rewrote this function a bit :)
1713 void TraceLine( trace_t *trace )
1717 traceTriangle_t *tt;
1721 /* setup output (note: this code assumes the input data is completely filled out) */
1722 trace->passSolid = qfalse;
1723 trace->opaque = qfalse;
1724 trace->compileFlags = 0;
1725 trace->numTestNodes = 0;
1728 if( !trace->recvShadows || !trace->testOcclusion || trace->distance <= 0.00001f )
1731 /* trace through nodes */
1732 TraceLine_r( headNodeNum, trace->origin, trace->end, trace );
1733 if( trace->passSolid && !trace->testAll )
1735 trace->opaque = qtrue;
1739 /* skip surfaces? */
1743 /* testall means trace through sky */
1744 if( trace->testAll && trace->numTestNodes < MAX_TRACE_TEST_NODES &&
1745 trace->compileFlags & C_SKY &&
1746 (trace->numSurfaces == 0 || surfaceInfos[ trace->surfaces[ 0 ] ].childSurfaceNum < 0) )
1748 //% trace->testNodes[ trace->numTestNodes++ ] = skyboxNodeNum;
1749 TraceLine_r( skyboxNodeNum, trace->origin, trace->end, trace );
1752 /* walk node list */
1753 for( i = 0; i < trace->numTestNodes; i++ )
1756 node = &traceNodes[ trace->testNodes[ i ] ];
1758 /* walk node item list */
1759 for( j = 0; j < node->numItems; j++ )
1761 tt = &traceTriangles[ node->items[ j ] ];
1762 ti = &traceInfos[ tt->infoNum ];
1763 if( TraceTriangle( ti, tt, trace ) )
1765 //% if( TraceWinding( &traceWindings[ node->items[ j ] ], trace ) )
1774 SetupTrace() - ydnar
1775 sets up certain trace values
1778 float SetupTrace( trace_t *trace )
1780 VectorSubtract( trace->end, trace->origin, trace->displacement );
1781 trace->distance = VectorNormalize( trace->displacement, trace->direction );
1782 VectorCopy( trace->origin, trace->hit );
1783 return trace->distance;