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 12
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;
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 )
152 if( numTraceInfos >= maxTraceInfos )
154 /* allocate more room */
155 maxTraceInfos += GROW_TRACE_INFOS;
156 temp = safe_malloc( maxTraceInfos * sizeof( *traceInfos ) );
157 if( traceInfos != NULL )
159 memcpy( temp, traceInfos, numTraceInfos * sizeof( *traceInfos ) );
162 traceInfos = (traceInfo_t*) temp;
166 memcpy( &traceInfos[ num ], ti, sizeof( *traceInfos ) );
167 if( num == numTraceInfos )
170 /* return the ti number */
177 AllocTraceNode() - ydnar
178 allocates a new trace node
181 static int AllocTraceNode( void )
187 if( numTraceNodes >= maxTraceNodes )
189 /* reallocate more room */
190 maxTraceNodes += GROW_TRACE_NODES;
191 temp = safe_malloc( maxTraceNodes * sizeof( traceNode_t ) );
192 if( traceNodes != NULL )
194 memcpy( temp, traceNodes, numTraceNodes * sizeof( traceNode_t ) );
201 memset( &traceNodes[ numTraceNodes ], 0, sizeof( traceNode_t ) );
202 traceNodes[ numTraceNodes ].type = TRACE_LEAF;
203 ClearBounds( traceNodes[ numTraceNodes ].mins, traceNodes[ numTraceNodes ].maxs );
206 /* return the count */
207 return (numTraceNodes - 1);
213 AddTraceWinding() - ydnar
214 adds a winding to the raytracing pool
217 static int AddTraceWinding( traceWinding_t *tw )
223 /* check for a dead winding */
224 if( deadWinding >= 0 && deadWinding < numTraceWindings )
228 /* put winding at the end of the list */
229 num = numTraceWindings;
232 if( numTraceWindings >= maxTraceWindings )
234 /* allocate more room */
235 maxTraceWindings += GROW_TRACE_WINDINGS;
236 temp = safe_malloc( maxTraceWindings * sizeof( *traceWindings ) );
237 if( traceWindings != NULL )
239 memcpy( temp, traceWindings, numTraceWindings * sizeof( *traceWindings ) );
240 free( traceWindings );
242 traceWindings = (traceWinding_t*) temp;
246 /* add the winding */
247 memcpy( &traceWindings[ num ], tw, sizeof( *traceWindings ) );
248 if( num == numTraceWindings )
252 /* return the winding number */
259 AddTraceTriangle() - ydnar
260 adds a triangle to the raytracing pool
263 static int AddTraceTriangle( traceTriangle_t *tt )
269 /* check for a dead triangle */
270 if( deadTriangle >= 0 && deadTriangle < numTraceTriangles )
274 /* put triangle at the end of the list */
275 num = numTraceTriangles;
278 if( numTraceTriangles >= maxTraceTriangles )
280 /* allocate more room */
281 maxTraceTriangles += GROW_TRACE_TRIANGLES;
282 temp = safe_malloc( maxTraceTriangles * sizeof( *traceTriangles ) );
283 if( traceTriangles != NULL )
285 memcpy( temp, traceTriangles, numTraceTriangles * sizeof( *traceTriangles ) );
286 free( traceTriangles );
288 traceTriangles = (traceTriangle_t*) temp;
292 /* find vectors for two edges sharing the first vert */
293 VectorSubtract( tt->v[ 1 ].xyz, tt->v[ 0 ].xyz, tt->edge1 );
294 VectorSubtract( tt->v[ 2 ].xyz, tt->v[ 0 ].xyz, tt->edge2 );
296 /* add the triangle */
297 memcpy( &traceTriangles[ num ], tt, sizeof( *traceTriangles ) );
298 if( num == numTraceTriangles )
302 /* return the triangle number */
309 AddItemToTraceNode() - ydnar
310 adds an item reference (winding or triangle) to a trace node
313 static int AddItemToTraceNode( traceNode_t *node, int num )
323 if( node->numItems >= node->maxItems )
325 /* allocate more room */
326 if( node == traceNodes )
329 node->maxItems += GROW_NODE_ITEMS;
330 if( node->maxItems <= 0 )
331 node->maxItems = GROW_NODE_ITEMS;
332 temp = safe_malloc( node->maxItems * sizeof( *node->items ) );
333 if( node->items != NULL )
335 memcpy( temp, node->items, node->numItems * sizeof( *node->items ) );
338 node->items = (int*) temp;
342 node->items[ node->numItems ] = num;
345 /* return the count */
346 return (node->numItems - 1);
352 /* -------------------------------------------------------------------------------
356 ------------------------------------------------------------------------------- */
359 SetupTraceNodes_r() - ydnar
360 recursively create the initial trace node structure from the bsp tree
363 static int SetupTraceNodes_r( int bspNodeNum )
365 int i, nodeNum, bspLeafNum;
370 /* get bsp node and plane */
371 bspNode = &bspNodes[ bspNodeNum ];
372 plane = &bspPlanes[ bspNode->planeNum ];
374 /* allocate a new trace node */
375 nodeNum = AllocTraceNode();
377 /* setup trace node */
378 traceNodes[ nodeNum ].type = PlaneTypeForNormal( plane->normal );
379 VectorCopy( plane->normal, traceNodes[ nodeNum ].plane );
380 traceNodes[ nodeNum ].plane[ 3 ] = plane->dist;
383 for( i = 0; i < 2; i++ )
386 if( bspNode->children[ i ] < 0 )
388 bspLeafNum = -bspNode->children[ i ] - 1;
391 traceNodes[ nodeNum ].children[ i ] = AllocTraceNode();
392 if( bspLeafs[ bspLeafNum ].cluster == -1 )
393 traceNodes[ traceNodes[ nodeNum ].children[ i ] ].type = TRACE_LEAF_SOLID;
398 traceNodes[ nodeNum ].children[ i ] = SetupTraceNodes_r( bspNode->children[ i ] );
401 /* return node number */
408 ClipTraceWinding() - ydnar
409 clips a trace winding against a plane into one or two parts
412 #define TW_ON_EPSILON 0.25f
414 void ClipTraceWinding( traceWinding_t *tw, vec4_t plane, traceWinding_t *front, traceWinding_t *back )
417 int sides[ MAX_TW_VERTS ], counts[ 3 ] = { 0, 0, 0 };
418 float dists[ MAX_TW_VERTS ];
420 traceVert_t *a, *b, mid;
423 /* clear front and back */
427 /* classify points */
428 for( i = 0; i < tw->numVerts; i++ )
430 dists[ i ] = DotProduct( tw->v[ i ].xyz, plane ) - plane[ 3 ];
431 if( dists[ i ] < -TW_ON_EPSILON )
432 sides[ i ] = SIDE_BACK;
433 else if( dists[ i ] > TW_ON_EPSILON )
434 sides[ i ] = SIDE_FRONT;
436 sides[ i ] = SIDE_ON;
437 counts[ sides[ i ] ]++;
440 /* entirely on front? */
441 if( counts[ SIDE_BACK ] == 0 )
442 memcpy( front, tw, sizeof( *front ) );
444 /* entirely on back? */
445 else if( counts[ SIDE_FRONT ] == 0 )
446 memcpy( back, tw, sizeof( *back ) );
448 /* straddles the plane */
451 /* setup front and back */
452 memcpy( front, tw, sizeof( *front ) );
454 memcpy( back, tw, sizeof( *back ) );
457 /* split the winding */
458 for( i = 0; i < tw->numVerts; i++ )
461 j = (i + 1) % tw->numVerts;
467 /* handle points on the splitting plane */
471 if( front->numVerts >= MAX_TW_VERTS )
472 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
473 front->v[ front->numVerts++ ] = *a;
477 if( back->numVerts >= MAX_TW_VERTS )
478 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
479 back->v[ back->numVerts++ ] = *a;
483 if( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS )
484 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
485 front->v[ front->numVerts++ ] = *a;
486 back->v[ back->numVerts++ ] = *a;
490 /* check next point to see if we need to split the edge */
491 if( sides[ j ] == SIDE_ON || sides[ j ] == sides[ i ] )
495 if( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS )
496 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
498 /* generate a split point */
499 frac = dists[ i ] / (dists[ i ] - dists[ j ]);
500 for( k = 0; k < 3; k++ )
502 /* minimize fp precision errors */
503 if( plane[ k ] == 1.0f )
504 mid.xyz[ k ] = plane[ 3 ];
505 else if( plane[ k ] == -1.0f )
506 mid.xyz[ k ] = -plane[ 3 ];
508 mid.xyz[ k ] = a->xyz[ k ] + frac * (b->xyz[ k ] - a->xyz[ k ]);
510 /* set texture coordinates */
513 mid.st[ 0 ] = a->st[ 0 ] + frac * (b->st[ 0 ] - a->st[ 0 ]);
514 mid.st[ 1 ] = a->st[ 1 ] + frac * (b->st[ 1 ] - a->st[ 1 ]);
517 /* copy midpoint to front and back polygons */
518 front->v[ front->numVerts++ ] = mid;
519 back->v[ back->numVerts++ ] = mid;
527 FilterPointToTraceNodes_r() - ydnar
531 static int FilterPointToTraceNodes_r( vec3_t pt, int nodeNum )
537 if( nodeNum < 0 || nodeNum >= numTraceNodes )
540 node = &traceNodes[ nodeNum ];
542 if( node->type >= 0 )
544 dot = DotProduct( pt, node->plane ) - node->plane[ 3 ];
546 FilterPointToTraceNodes_r( pt, node->children[ 0 ] );
548 FilterPointToTraceNodes_r( pt, node->children[ 1 ] );
552 Sys_Printf( "%d ", nodeNum );
560 FilterTraceWindingIntoNodes_r() - ydnar
561 filters a trace winding into the raytracing tree
564 static void FilterTraceWindingIntoNodes_r( traceWinding_t *tw, int nodeNum )
567 vec4_t plane1, plane2, reverse;
569 traceWinding_t front, back;
572 /* don't filter if passed a bogus node (solid, etc) */
573 if( nodeNum < 0 || nodeNum >= numTraceNodes )
577 node = &traceNodes[ nodeNum ];
579 /* is this a decision node? */
580 if( node->type >= 0 )
582 /* create winding plane if necessary, filtering out bogus windings as well */
583 if( nodeNum == headNodeNum )
585 if( !PlaneFromPoints( tw->plane, tw->v[ 0 ].xyz, tw->v[ 1 ].xyz, tw->v[ 2 ].xyz ) )
589 /* validate the node */
590 if( node->children[ 0 ] == 0 || node->children[ 1 ] == 0 )
591 Error( "Invalid tracenode: %d", nodeNum );
594 Vector4Copy( node->plane, plane1 );
596 /* get winding plane */
597 Vector4Copy( tw->plane, plane2 );
599 /* invert surface plane */
600 VectorSubtract( vec3_origin, plane2, reverse );
601 reverse[ 3 ] = -plane2[ 3 ];
604 if( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f )
606 FilterTraceWindingIntoNodes_r( tw, node->children[ 0 ] );
611 if( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f )
613 FilterTraceWindingIntoNodes_r( tw, node->children[ 1 ] );
617 /* clip the winding by node plane */
618 ClipTraceWinding( tw, plane1, &front, &back );
620 /* filter by node plane */
621 if( front.numVerts >= 3 )
622 FilterTraceWindingIntoNodes_r( &front, node->children[ 0 ] );
623 if( back.numVerts >= 3 )
624 FilterTraceWindingIntoNodes_r( &back, node->children[ 1 ] );
626 /* return to caller */
630 /* add winding to leaf node */
631 num = AddTraceWinding( tw );
632 AddItemToTraceNode( node, num );
638 SubdivideTraceNode_r() - ydnar
639 recursively subdivides a tracing node until it meets certain size and complexity criteria
642 static void SubdivideTraceNode_r( int nodeNum, int depth )
644 int i, j, count, num, frontNum, backNum, type;
648 traceNode_t *node, *frontNode, *backNode;
649 traceWinding_t *tw, front, back;
653 if( nodeNum < 0 || nodeNum >= numTraceNodes )
657 node = &traceNodes[ nodeNum ];
659 /* runaway recursion check */
660 if( depth >= MAX_TRACE_DEPTH )
662 //% Sys_Printf( "Depth: (%d items)\n", node->numItems );
668 /* is this a decision node? */
669 if( node->type >= 0 )
671 /* subdivide children */
672 frontNum = node->children[ 0 ];
673 backNum = node->children[ 1 ];
674 SubdivideTraceNode_r( frontNum, depth );
675 SubdivideTraceNode_r( backNum, depth );
680 ClearBounds( node->mins, node->maxs );
681 VectorClear( average );
683 for( i = 0; i < node->numItems; i++ )
686 tw = &traceWindings[ node->items[ i ] ];
689 for( j = 0; j < tw->numVerts; j++ )
691 AddPointToBounds( tw->v[ j ].xyz, node->mins, node->maxs );
692 average[ 0 ] += tw->v[ j ].xyz[ 0 ];
693 average[ 1 ] += tw->v[ j ].xyz[ 1 ];
694 average[ 2 ] += tw->v[ j ].xyz[ 2 ];
699 /* check triangle limit */
700 //% if( node->numItems <= MAX_NODE_ITEMS )
701 if( (count - (node->numItems * 2)) < MAX_NODE_TRIANGLES )
703 //% Sys_Printf( "Limit: (%d triangles)\n", (count - (node->numItems * 2)) );
708 /* the largest dimension of the bounding box will be the split axis */
709 VectorSubtract( node->maxs, node->mins, size );
710 if( size[ 0 ] >= size[ 1 ] && size[ 0 ] >= size[ 2 ] )
712 else if( size[ 1 ] >= size[ 0 ] && size[ 1 ] >= size[ 2 ] )
717 /* don't split small nodes */
718 if( size[ type ] <= MIN_NODE_SIZE )
720 //% Sys_Printf( "Limit: %f %f %f (%d items)\n", size[ 0 ], size[ 1 ], size[ 2 ], node->numItems );
725 /* set max trace depth */
726 if( depth > maxTraceDepth )
727 maxTraceDepth = depth;
729 /* snap the average */
730 dist = floor( average[ type ] / count );
733 if( dist <= node->mins[ type ] || dist >= node->maxs[ type ] )
734 dist = floor( 0.5f * (node->mins[ type ] + node->maxs[ type ]) );
736 /* allocate child nodes */
737 frontNum = AllocTraceNode();
738 backNum = AllocTraceNode();
741 node = &traceNodes[ nodeNum ];
742 frontNode = &traceNodes[ frontNum ];
743 backNode = &traceNodes[ backNum ];
745 /* attach children */
747 node->plane[ type ] = 1.0f;
748 node->plane[ 3 ] = dist;
749 node->children[ 0 ] = frontNum;
750 node->children[ 1 ] = backNum;
752 /* setup front node */
753 frontNode->maxItems = (node->maxItems >> 1);
754 frontNode->items = safe_malloc( frontNode->maxItems * sizeof( *frontNode->items ) );
756 /* setup back node */
757 backNode->maxItems = (node->maxItems >> 1);
758 backNode->items = safe_malloc( backNode->maxItems * sizeof( *backNode->items ) );
760 /* filter windings into child nodes */
761 for( i = 0; i < node->numItems; i++ )
764 tw = &traceWindings[ node->items[ i ] ];
766 /* clip the winding by the new split plane */
767 ClipTraceWinding( tw, node->plane, &front, &back );
769 /* kill the existing winding */
770 if( front.numVerts >= 3 || back.numVerts >= 3 )
771 deadWinding = node->items[ i ];
773 /* add front winding */
774 if( front.numVerts >= 3 )
776 num = AddTraceWinding( &front );
777 AddItemToTraceNode( frontNode, num );
780 /* add back winding */
781 if( back.numVerts >= 3 )
783 num = AddTraceWinding( &back );
784 AddItemToTraceNode( backNode, num );
788 /* free original node winding list */
795 if( frontNode->numItems <= 0 )
797 frontNode->maxItems = 0;
798 free( frontNode->items );
799 frontNode->items = NULL;
802 if( backNode->numItems <= 0 )
804 backNode->maxItems = 0;
805 free( backNode->items );
806 backNode->items = NULL;
809 /* subdivide children */
810 SubdivideTraceNode_r( frontNum, depth );
811 SubdivideTraceNode_r( backNum, depth );
817 TriangulateTraceNode_r()
818 optimizes the tracing data by changing trace windings into triangles
821 static int TriangulateTraceNode_r( int nodeNum )
823 int i, j, num, frontNum, backNum, numWindings, *windings;
830 if( nodeNum < 0 || nodeNum >= numTraceNodes )
834 node = &traceNodes[ nodeNum ];
836 /* is this a decision node? */
837 if( node->type >= 0 )
839 /* triangulate children */
840 frontNum = node->children[ 0 ];
841 backNum = node->children[ 1 ];
842 node->numItems = TriangulateTraceNode_r( frontNum );
843 node->numItems += TriangulateTraceNode_r( backNum );
844 return node->numItems;
848 if( node->numItems == 0 )
851 if( node->items != NULL )
853 return node->numItems;
856 /* store off winding data */
857 numWindings = node->numItems;
858 windings = node->items;
862 node->maxItems = numWindings * 2;
863 node->items = safe_malloc( node->maxItems * sizeof( tt ) );
865 /* walk winding list */
866 for( i = 0; i < numWindings; i++ )
869 tw = &traceWindings[ windings[ i ] ];
872 tt.infoNum = tw->infoNum;
873 tt.v[ 0 ] = tw->v[ 0 ];
875 /* walk vertex list */
876 for( j = 1; j + 1 < tw->numVerts; j++ )
879 tt.v[ 1 ] = tw->v[ j ];
880 tt.v[ 2 ] = tw->v[ j + 1 ];
882 /* find vectors for two edges sharing the first vert */
883 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
884 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
886 /* add it to the node */
887 num = AddTraceTriangle( &tt );
888 AddItemToTraceNode( node, num );
893 if( windings != NULL )
896 /* return item count */
897 return node->numItems;
902 /* -------------------------------------------------------------------------------
904 shadow casting item setup (triangles, patches, entities)
906 ------------------------------------------------------------------------------- */
909 PopulateWithBSPModel() - ydnar
910 filters a bsp model's surfaces into the raytracing tree
913 static void PopulateWithBSPModel( bspModel_t *model, m4x4_t transform )
915 int i, j, x, y, pw[ 5 ], r, nodeNum;
916 bspDrawSurface_t *ds;
918 bspDrawVert_t *verts;
920 mesh_t srcMesh, *mesh, *subdivided;
926 if( model == NULL || transform == NULL )
929 /* walk the list of surfaces in this model and fill out the info structs */
930 for( i = 0; i < model->numBSPSurfaces; i++ )
932 /* get surface and info */
933 ds = &bspDrawSurfaces[ model->firstBSPSurface + i ];
934 info = &surfaceInfos[ model->firstBSPSurface + i ];
935 if( info->si == NULL )
939 if( !info->castShadows )
943 if( ds->surfaceType == MST_PATCH && patchShadows == qfalse )
946 /* some surfaces in the bsp might have been tagged as nodraw, with a bogus shader */
947 if( (bspShaders[ ds->shaderNum ].contentFlags & noDrawContentFlags) ||
948 (bspShaders[ ds->shaderNum ].surfaceFlags & noDrawSurfaceFlags) )
951 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
952 if( (info->si->compileFlags & C_NODRAW) )
954 if( (info->si->compileFlags & C_TRANSLUCENT) &&
955 !(info->si->compileFlags & C_ALPHASHADOW) &&
956 !(info->si->compileFlags & C_LIGHTFILTER) )
959 /* setup trace info */
961 ti.castShadows = info->castShadows;
962 ti.surfaceNum = model->firstBSPBrush + i;
964 /* choose which node (normal or skybox) */
965 if( info->parentSurfaceNum >= 0 )
967 nodeNum = skyboxNodeNum;
969 /* sky surfaces in portal skies are ignored */
970 if( info->si->compileFlags & C_SKY )
974 nodeNum = headNodeNum;
976 /* setup trace winding */
977 memset( &tw, 0, sizeof( tw ) );
978 tw.infoNum = AddTraceInfo( &ti );
982 switch( ds->surfaceType )
986 /* subdivide the surface */
987 srcMesh.width = ds->patchWidth;
988 srcMesh.height = ds->patchHeight;
989 srcMesh.verts = &bspDrawVerts[ ds->firstVert ];
990 //% subdivided = SubdivideMesh( srcMesh, 8, 512 );
991 subdivided = SubdivideMesh2( srcMesh, info->patchIterations );
993 /* fit it to the curve and remove colinear verts on rows/columns */
994 PutMeshOnCurve( *subdivided );
995 mesh = RemoveLinearMeshColumnsRows( subdivided );
996 FreeMesh( subdivided );
1001 /* subdivide each quad to place the models */
1002 for( y = 0; y < (mesh->height - 1); y++ )
1004 for( x = 0; x < (mesh->width - 1); x++ )
1007 pw[ 0 ] = x + (y * mesh->width);
1008 pw[ 1 ] = x + ((y + 1) * mesh->width);
1009 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
1010 pw[ 3 ] = x + 1 + (y * mesh->width);
1011 pw[ 4 ] = x + (y * mesh->width); /* same as pw[ 0 ] */
1016 /* make first triangle */
1017 VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
1018 Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
1019 VectorCopy( verts[ pw[ r + 1 ] ].xyz, tw.v[ 1 ].xyz );
1020 Vector2Copy( verts[ pw[ r + 1 ] ].st, tw.v[ 1 ].st );
1021 VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 2 ].xyz );
1022 Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 2 ].st );
1023 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1024 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1025 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1026 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1028 /* make second triangle */
1029 VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
1030 Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
1031 VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 1 ].xyz );
1032 Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 1 ].st );
1033 VectorCopy( verts[ pw[ r + 3 ] ].xyz, tw.v[ 2 ].xyz );
1034 Vector2Copy( verts[ pw[ r + 3 ] ].st, tw.v[ 2 ].st );
1035 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1036 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1037 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1038 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1042 /* free the subdivided mesh */
1046 /* handle triangle surfaces */
1047 case MST_TRIANGLE_SOUP:
1049 /* set verts and indexes */
1050 verts = &bspDrawVerts[ ds->firstVert ];
1051 indexes = &bspDrawIndexes[ ds->firstIndex ];
1053 /* walk the triangle list */
1054 for( j = 0; j < ds->numIndexes; j += 3 )
1056 VectorCopy( verts[ indexes[ j ] ].xyz, tw.v[ 0 ].xyz );
1057 Vector2Copy( verts[ indexes[ j ] ].st, tw.v[ 0 ].st );
1058 VectorCopy( verts[ indexes[ j + 1 ] ].xyz, tw.v[ 1 ].xyz );
1059 Vector2Copy( verts[ indexes[ j + 1 ] ].st, tw.v[ 1 ].st );
1060 VectorCopy( verts[ indexes[ j + 2 ] ].xyz, tw.v[ 2 ].xyz );
1061 Vector2Copy( verts[ indexes[ j + 2 ] ].st, tw.v[ 2 ].st );
1062 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1063 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1064 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1065 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1069 /* other surface types do not cast shadows */
1079 PopulateWithPicoModel() - ydnar
1080 filters a picomodel's surfaces into the raytracing tree
1083 static void PopulateWithPicoModel( int castShadows, picoModel_t *model, m4x4_t transform )
1085 int i, j, k, numSurfaces, numIndexes;
1086 picoSurface_t *surface;
1087 picoShader_t *shader;
1088 picoVec_t *xyz, *st;
1089 picoIndex_t *indexes;
1095 if( model == NULL || transform == NULL )
1099 numSurfaces = PicoGetModelNumSurfaces( model );
1101 /* walk the list of surfaces in this model and fill out the info structs */
1102 for( i = 0; i < numSurfaces; i++ )
1105 surface = PicoGetModelSurface( model, i );
1106 if( surface == NULL )
1109 /* only handle triangle surfaces initially (fixme: support patches) */
1110 if( PicoGetSurfaceType( surface ) != PICO_TRIANGLES )
1113 /* get shader (fixme: support shader remapping) */
1114 shader = PicoGetSurfaceShader( surface );
1115 if( shader == NULL )
1117 ti.si = ShaderInfoForShader( PicoGetShaderName( shader ) );
1121 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
1122 if( (ti.si->compileFlags & C_NODRAW) )
1124 if( (ti.si->compileFlags & C_TRANSLUCENT) &&
1125 !(ti.si->compileFlags & C_ALPHASHADOW) &&
1126 !(ti.si->compileFlags & C_LIGHTFILTER) )
1129 /* setup trace info */
1130 ti.castShadows = castShadows;
1133 /* setup trace winding */
1134 memset( &tw, 0, sizeof( tw ) );
1135 tw.infoNum = AddTraceInfo( &ti );
1139 numIndexes = PicoGetSurfaceNumIndexes( surface );
1140 indexes = PicoGetSurfaceIndexes( surface, 0 );
1142 /* walk the triangle list */
1143 for( j = 0; j < numIndexes; j += 3, indexes += 3 )
1145 for( k = 0; k < 3; k++ )
1147 xyz = PicoGetSurfaceXYZ( surface, indexes[ k ] );
1148 st = PicoGetSurfaceST( surface, 0, indexes[ k ] );
1149 VectorCopy( xyz, tw.v[ k ].xyz );
1150 Vector2Copy( st, tw.v[ k ].st );
1151 m4x4_transform_point( transform, tw.v[ k ].xyz );
1153 FilterTraceWindingIntoNodes_r( &tw, headNodeNum );
1161 PopulateTraceNodes() - ydnar
1162 fills the raytracing tree with world and entity occluders
1165 static void PopulateTraceNodes( void )
1167 int i, m, frame, castShadows;
1172 vec3_t origin, scale, angles;
1176 /* add worldspawn triangles */
1177 m4x4_identity( transform );
1178 PopulateWithBSPModel( &bspModels[ 0 ], transform );
1180 /* walk each entity list */
1181 for( i = 1; i < numEntities; i++ )
1186 /* get shadow flags */
1187 castShadows = ENTITY_CAST_SHADOWS;
1188 GetEntityShadowFlags( e, NULL, &castShadows, NULL );
1194 /* get entity origin */
1195 GetVectorForKey( e, "origin", origin );
1198 scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = 1.0f;
1199 temp = FloatForKey( e, "modelscale" );
1201 scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = temp;
1202 value = ValueForKey( e, "modelscale_vec" );
1203 if( value[ 0 ] != '\0' )
1204 sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );
1206 /* get "angle" (yaw) or "angles" (pitch yaw roll) */
1207 angles[ 0 ] = angles[ 1 ] = angles[ 2 ] = 0.0f;
1208 angles[ 2 ] = FloatForKey( e, "angle" );
1209 value = ValueForKey( e, "angles" );
1210 if( value[ 0 ] != '\0' )
1211 sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
1213 /* set transform matrix (thanks spog) */
1214 m4x4_identity( transform );
1215 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
1217 /* hack: Stable-1_2 and trunk have differing row/column major matrix order
1218 this transpose is necessary with Stable-1_2
1219 uncomment the following line with old m4x4_t (non 1.3/spog_branch) code */
1220 //% m4x4_transpose( transform );
1223 value = ValueForKey( e, "model" );
1225 /* switch on model type */
1226 switch( value[ 0 ] )
1234 m = atoi( &value[ 1 ] );
1235 if( m <= 0 || m >= numBSPModels )
1237 PopulateWithBSPModel( &bspModels[ m ], transform );
1240 /* external model */
1242 frame = IntForKey( e, "_frame" );
1243 model = LoadModel( (char*) value, frame );
1246 PopulateWithPicoModel( castShadows, model, transform );
1251 value = ValueForKey( e, "model2" );
1253 /* switch on model type */
1254 switch( value[ 0 ] )
1262 m = atoi( &value[ 1 ] );
1263 if( m <= 0 || m >= numBSPModels )
1265 PopulateWithBSPModel( &bspModels[ m ], transform );
1268 /* external model */
1270 frame = IntForKey( e, "_frame2" );
1271 model = LoadModel( (char*) value, frame );
1274 PopulateWithPicoModel( castShadows, model, transform );
1283 /* -------------------------------------------------------------------------------
1285 trace initialization
1287 ------------------------------------------------------------------------------- */
1290 SetupTraceNodes() - ydnar
1291 creates a balanced bsp with axis-aligned splits for efficient raytracing
1294 void SetupTraceNodes( void )
1297 Sys_FPrintf( SYS_VRB, "--- SetupTraceNodes ---\n" );
1299 /* find nodraw bit */
1300 noDrawContentFlags = noDrawSurfaceFlags = noDrawCompileFlags = 0;
1301 ApplySurfaceParm( "nodraw", &noDrawContentFlags, &noDrawSurfaceFlags, &noDrawCompileFlags );
1303 /* create the baseline raytracing tree from the bsp tree */
1304 headNodeNum = SetupTraceNodes_r( 0 );
1306 /* create outside node for skybox surfaces */
1307 skyboxNodeNum = AllocTraceNode();
1309 /* populate the tree with triangles from the world and shadow casting entities */
1310 PopulateTraceNodes();
1312 /* create the raytracing bsp */
1313 if( loMem == qfalse )
1315 SubdivideTraceNode_r( headNodeNum, 0 );
1316 SubdivideTraceNode_r( skyboxNodeNum, 0 );
1319 /* create triangles from the trace windings */
1320 TriangulateTraceNode_r( headNodeNum );
1321 TriangulateTraceNode_r( skyboxNodeNum );
1323 /* emit some stats */
1324 //% Sys_FPrintf( SYS_VRB, "%9d original triangles\n", numOriginalTriangles );
1325 Sys_FPrintf( SYS_VRB, "%9d trace windings (%.2fMB)\n", numTraceWindings, (float) (numTraceWindings * sizeof( *traceWindings )) / (1024.0f * 1024.0f) );
1326 Sys_FPrintf( SYS_VRB, "%9d trace triangles (%.2fMB)\n", numTraceTriangles, (float) (numTraceTriangles * sizeof( *traceTriangles )) / (1024.0f * 1024.0f) );
1327 Sys_FPrintf( SYS_VRB, "%9d trace nodes (%.2fMB)\n", numTraceNodes, (float) (numTraceNodes * sizeof( *traceNodes )) / (1024.0f * 1024.0f) );
1328 Sys_FPrintf( SYS_VRB, "%9d leaf nodes (%.2fMB)\n", numTraceLeafNodes, (float) (numTraceLeafNodes * sizeof( *traceNodes )) / (1024.0f * 1024.0f) );
1329 //% Sys_FPrintf( SYS_VRB, "%9d average triangles per leaf node\n", numTraceTriangles / numTraceLeafNodes );
1330 Sys_FPrintf( SYS_VRB, "%9d average windings per leaf node\n", numTraceWindings / (numTraceLeafNodes + 1) );
1331 Sys_FPrintf( SYS_VRB, "%9d max trace depth\n", maxTraceDepth );
1333 /* free trace windings */
1334 free( traceWindings );
1335 numTraceWindings = 0;
1336 maxTraceWindings = 0;
1339 /* debug code: write out trace triangles to an alias obj file */
1344 char filename[ 1024 ];
1349 strcpy( filename, source );
1350 StripExtension( filename );
1351 strcat( filename, ".lin" );
1352 Sys_Printf( "Opening light trace file %s...\n", filename );
1353 file = fopen( filename, "w" );
1355 Error( "Error opening %s for writing", filename );
1357 /* walk node list */
1358 for( i = 0; i < numTraceWindings; i++ )
1360 tw = &traceWindings[ i ];
1361 for( j = 0; j < tw->numVerts + 1; j++ )
1362 fprintf( file, "%f %f %f\n",
1363 tw->v[ j % tw->numVerts ].xyz[ 0 ], tw->v[ j % tw->numVerts ].xyz[ 1 ], tw->v[ j % tw->numVerts ].xyz[ 2 ] );
1374 /* -------------------------------------------------------------------------------
1378 ------------------------------------------------------------------------------- */
1382 based on code written by william 'spog' joseph
1383 based on code originally written by tomas moller and ben trumbore, journal of graphics tools, 2(1):21-28, 1997
1386 #define BARY_EPSILON 0.01f
1387 #define ASLF_EPSILON 0.0001f /* so to not get double shadows */
1388 #define COPLANAR_EPSILON 0.25f //% 0.000001f
1389 #define NEAR_SHADOW_EPSILON 1.5f //% 1.25f
1390 #define SELF_SHADOW_EPSILON 0.5f
1392 qboolean TraceTriangle( traceInfo_t *ti, traceTriangle_t *tt, trace_t *trace )
1395 float tvec[ 3 ], pvec[ 3 ], qvec[ 3 ];
1396 float det, invDet, depth;
1397 float u, v, w, s, t;
1404 /* don't double-trace against sky */
1406 if( trace->compileFlags & si->compileFlags & C_SKY )
1409 /* receive shadows from worldspawn group only */
1410 if( trace->recvShadows == 1 )
1412 if( ti->castShadows != 1 )
1416 /* receive shadows from same group and worldspawn group */
1417 else if( trace->recvShadows > 1 )
1419 if( ti->castShadows != 1 && abs( ti->castShadows ) != abs( trace->recvShadows ) )
1421 //% Sys_Printf( "%d:%d ", tt->castShadows, trace->recvShadows );
1424 /* receive shadows from the same group only (< 0) */
1427 if( abs( ti->castShadows ) != abs( trace->recvShadows ) )
1431 /* begin calculating determinant - also used to calculate u parameter */
1432 CrossProduct( trace->direction, tt->edge2, pvec );
1434 /* if determinant is near zero, trace lies in plane of triangle */
1435 det = DotProduct( tt->edge1, pvec );
1437 /* the non-culling branch */
1438 if( fabs( det ) < COPLANAR_EPSILON )
1440 invDet = 1.0f / det;
1442 /* calculate distance from first vertex to ray origin */
1443 VectorSubtract( trace->origin, tt->v[ 0 ].xyz, tvec );
1445 /* calculate u parameter and test bounds */
1446 u = DotProduct( tvec, pvec ) * invDet;
1447 if( u < -BARY_EPSILON || u > (1.0f + BARY_EPSILON) )
1450 /* prepare to test v parameter */
1451 CrossProduct( tvec, tt->edge1, qvec );
1453 /* calculate v parameter and test bounds */
1454 v = DotProduct( trace->direction, qvec ) * invDet;
1455 if( v < -BARY_EPSILON || (u + v) > (1.0f + BARY_EPSILON) )
1458 /* calculate t (depth) */
1459 depth = DotProduct( tt->edge2, qvec ) * invDet;
1460 if( depth <= trace->inhibitRadius || depth >= trace->distance )
1463 /* if hitpoint is really close to trace origin (sample point), then check for self-shadowing */
1464 if( depth <= SELF_SHADOW_EPSILON )
1466 /* don't self-shadow */
1467 for( i = 0; i < trace->numSurfaces; i++ )
1469 if( ti->surfaceNum == trace->surfaces[ i ] )
1474 /* stack compile flags */
1475 trace->compileFlags |= si->compileFlags;
1477 /* don't trace against sky */
1478 if( si->compileFlags & C_SKY )
1481 /* most surfaces are completely opaque */
1482 if( !(si->compileFlags & (C_ALPHASHADOW | C_LIGHTFILTER)) ||
1483 si->lightImage == NULL || si->lightImage->pixels == NULL )
1485 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1486 VectorClear( trace->color );
1487 trace->opaque = qtrue;
1491 /* try to avoid double shadows near triangle seams */
1492 if( u < -ASLF_EPSILON || u > (1.0f + ASLF_EPSILON) ||
1493 v < -ASLF_EPSILON || (u + v) > (1.0f + ASLF_EPSILON) )
1496 /* calculate w parameter */
1499 /* calculate st from uvw (barycentric) coordinates */
1500 s = w * tt->v[ 0 ].st[ 0 ] + u * tt->v[ 1 ].st[ 0 ] + v * tt->v[ 2 ].st[ 0 ];
1501 t = w * tt->v[ 0 ].st[ 1 ] + u * tt->v[ 1 ].st[ 1 ] + v * tt->v[ 2 ].st[ 1 ];
1504 is = s * si->lightImage->width;
1505 it = t * si->lightImage->height;
1508 pixel = si->lightImage->pixels + 4 * (it * si->lightImage->width + is);
1510 /* ydnar: color filter */
1511 if( si->compileFlags & C_LIGHTFILTER )
1513 /* filter by texture color */
1514 trace->color[ 0 ] *= ((1.0f / 255.0f) * pixel[ 0 ]);
1515 trace->color[ 1 ] *= ((1.0f / 255.0f) * pixel[ 1 ]);
1516 trace->color[ 2 ] *= ((1.0f / 255.0f) * pixel[ 2 ]);
1519 /* ydnar: alpha filter */
1520 if( si->compileFlags & C_ALPHASHADOW )
1522 /* filter by inverse texture alpha */
1523 shadow = (1.0f / 255.0f) * (255 - pixel[ 3 ]);
1524 trace->color[ 0 ] *= shadow;
1525 trace->color[ 1 ] *= shadow;
1526 trace->color[ 2 ] *= shadow;
1529 /* check filter for opaque */
1530 if( trace->color[ 0 ] <= 0.001f && trace->color[ 1 ] <= 0.001f && trace->color[ 2 ] <= 0.001f )
1532 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1533 trace->opaque = qtrue;
1537 /* continue tracing */
1544 TraceWinding() - ydnar
1548 qboolean TraceWinding( traceWinding_t *tw, trace_t *trace )
1555 tt.infoNum = tw->infoNum;
1556 tt.v[ 0 ] = tw->v[ 0 ];
1558 /* walk vertex list */
1559 for( i = 1; i + 1 < tw->numVerts; i++ )
1562 tt.v[ 1 ] = tw->v[ i ];
1563 tt.v[ 2 ] = tw->v[ i + 1 ];
1565 /* find vectors for two edges sharing the first vert */
1566 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
1567 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
1570 if( TraceTriangle( &traceInfos[ tt.infoNum ], &tt, trace ) )
1583 returns qtrue if something is hit and tracing can stop
1586 static qboolean TraceLine_r( int nodeNum, vec3_t origin, vec3_t end, trace_t *trace )
1590 float front, back, frac;
1595 /* bogus node number means solid, end tracing unless testing all */
1598 VectorCopy( origin, trace->hit );
1599 trace->passSolid = qtrue;
1604 node = &traceNodes[ nodeNum ];
1607 if( node->type == TRACE_LEAF_SOLID )
1609 VectorCopy( origin, trace->hit );
1610 trace->passSolid = qtrue;
1615 if( node->type < 0 )
1617 /* note leaf and return */
1618 if( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES )
1619 trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
1623 /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
1624 if( trace->testAll && node->numItems == 0 )
1627 /* classify beginning and end points */
1628 switch( node->type )
1631 front = origin[ 0 ] - node->plane[ 3 ];
1632 back = end[ 0 ] - node->plane[ 3 ];
1636 front = origin[ 1 ] - node->plane[ 3 ];
1637 back = end[ 1 ] - node->plane[ 3 ];
1641 front = origin[ 2 ] - node->plane[ 3 ];
1642 back = end[ 2 ] - node->plane[ 3 ];
1646 front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
1647 back = DotProduct( end, node->plane ) - node->plane[ 3 ];
1651 /* entirely in front side? */
1652 if( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON )
1653 return TraceLine_r( node->children[ 0 ], origin, end, trace );
1655 /* entirely on back side? */
1656 if( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON )
1657 return TraceLine_r( node->children[ 1 ], origin, end, trace );
1662 /* calculate intercept point */
1663 frac = front / (front - back);
1664 mid[ 0 ] = origin[ 0 ] + (end[ 0 ] - origin[ 0 ]) * frac;
1665 mid[ 1 ] = origin[ 1 ] + (end[ 1 ] - origin[ 1 ]) * frac;
1666 mid[ 2 ] = origin[ 2 ] + (end[ 2 ] - origin[ 2 ]) * frac;
1668 /* fixme: check inhibit radius, then solid nodes and ignore */
1670 /* set trace hit here */
1671 //% VectorCopy( mid, trace->hit );
1673 /* trace first side */
1674 r = TraceLine_r( node->children[ side ], origin, mid, trace );
1678 /* trace other side */
1679 return TraceLine_r( node->children[ !side ], mid, end, trace );
1686 rewrote this function a bit :)
1689 void TraceLine( trace_t *trace )
1693 traceTriangle_t *tt;
1697 /* setup output (note: this code assumes the input data is completely filled out) */
1698 trace->passSolid = qfalse;
1699 trace->opaque = qfalse;
1700 trace->compileFlags = 0;
1701 trace->numTestNodes = 0;
1704 if( !trace->recvShadows || !trace->testOcclusion || trace->distance <= 0.00001f )
1707 /* trace through nodes */
1708 TraceLine_r( headNodeNum, trace->origin, trace->end, trace );
1709 if( trace->passSolid && !trace->testAll )
1711 trace->opaque = qtrue;
1715 /* skip surfaces? */
1719 /* testall means trace through sky */
1720 if( trace->testAll && trace->numTestNodes < MAX_TRACE_TEST_NODES &&
1721 trace->compileFlags & C_SKY &&
1722 (trace->numSurfaces == 0 || surfaceInfos[ trace->surfaces[ 0 ] ].childSurfaceNum < 0) )
1724 //% trace->testNodes[ trace->numTestNodes++ ] = skyboxNodeNum;
1725 TraceLine_r( skyboxNodeNum, trace->origin, trace->end, trace );
1728 /* walk node list */
1729 for( i = 0; i < trace->numTestNodes; i++ )
1732 node = &traceNodes[ trace->testNodes[ i ] ];
1734 /* walk node item list */
1735 for( j = 0; j < node->numItems; j++ )
1737 tt = &traceTriangles[ node->items[ j ] ];
1738 ti = &traceInfos[ tt->infoNum ];
1739 if( TraceTriangle( ti, tt, trace ) )
1741 //% if( TraceWinding( &traceWindings[ node->items[ j ] ], trace ) )
1750 SetupTrace() - ydnar
1751 sets up certain trace values
1754 float SetupTrace( trace_t *trace )
1756 VectorSubtract( trace->end, trace->origin, trace->displacement );
1757 trace->distance = VectorNormalize( trace->displacement, trace->direction );
1758 VectorCopy( trace->origin, trace->hit );
1759 return trace->distance;