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 ){
141 /* find an existing info */
142 for ( num = firstTraceInfo; num < numTraceInfos; num++ )
144 if ( traceInfos[ num ].si == ti->si &&
145 traceInfos[ num ].surfaceNum == ti->surfaceNum &&
146 traceInfos[ num ].castShadows == ti->castShadows &&
147 traceInfos[ num ].skipGrid == ti->skipGrid ) {
153 if ( numTraceInfos >= maxTraceInfos ) {
154 /* allocate more room */
155 maxTraceInfos += GROW_TRACE_INFOS;
156 temp = safe_malloc( maxTraceInfos * sizeof( *traceInfos ) );
157 if ( traceInfos != NULL ) {
158 memcpy( temp, traceInfos, numTraceInfos * sizeof( *traceInfos ) );
161 traceInfos = (traceInfo_t*) temp;
165 memcpy( &traceInfos[ num ], ti, sizeof( *traceInfos ) );
166 if ( num == numTraceInfos ) {
170 /* return the ti number */
177 AllocTraceNode() - ydnar
178 allocates a new trace node
181 static int AllocTraceNode( void ){
186 if ( numTraceNodes >= maxTraceNodes ) {
187 /* reallocate more room */
188 maxTraceNodes += GROW_TRACE_NODES;
189 temp = safe_malloc( maxTraceNodes * sizeof( traceNode_t ) );
190 if ( traceNodes != NULL ) {
191 memcpy( temp, traceNodes, numTraceNodes * sizeof( traceNode_t ) );
198 memset( &traceNodes[ numTraceNodes ], 0, sizeof( traceNode_t ) );
199 traceNodes[ numTraceNodes ].type = TRACE_LEAF;
200 ClearBounds( traceNodes[ numTraceNodes ].mins, traceNodes[ numTraceNodes ].maxs );
202 /* Sys_Printf("alloc node %d\n", numTraceNodes); */
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 ){
222 /* check for a dead winding */
223 if ( deadWinding >= 0 && deadWinding < numTraceWindings ) {
228 /* put winding at the end of the list */
229 num = numTraceWindings;
232 if ( numTraceWindings >= maxTraceWindings ) {
233 /* allocate more room */
234 maxTraceWindings += GROW_TRACE_WINDINGS;
235 temp = safe_malloc( maxTraceWindings * sizeof( *traceWindings ) );
236 if ( traceWindings != NULL ) {
237 memcpy( temp, traceWindings, numTraceWindings * sizeof( *traceWindings ) );
238 free( traceWindings );
240 traceWindings = (traceWinding_t*) temp;
244 /* add the winding */
245 memcpy( &traceWindings[ num ], tw, sizeof( *traceWindings ) );
246 if ( num == numTraceWindings ) {
251 /* return the winding number */
258 AddTraceTriangle() - ydnar
259 adds a triangle to the raytracing pool
262 static int AddTraceTriangle( traceTriangle_t *tt ){
267 /* check for a dead triangle */
268 if ( deadTriangle >= 0 && deadTriangle < numTraceTriangles ) {
273 /* put triangle at the end of the list */
274 num = numTraceTriangles;
277 if ( numTraceTriangles >= maxTraceTriangles ) {
278 /* allocate more room */
279 maxTraceTriangles += GROW_TRACE_TRIANGLES;
280 temp = safe_malloc( maxTraceTriangles * sizeof( *traceTriangles ) );
281 if ( traceTriangles != NULL ) {
282 memcpy( temp, traceTriangles, numTraceTriangles * sizeof( *traceTriangles ) );
283 free( traceTriangles );
285 traceTriangles = (traceTriangle_t*) temp;
289 /* find vectors for two edges sharing the first vert */
290 VectorSubtract( tt->v[ 1 ].xyz, tt->v[ 0 ].xyz, tt->edge1 );
291 VectorSubtract( tt->v[ 2 ].xyz, tt->v[ 0 ].xyz, tt->edge2 );
293 /* add the triangle */
294 memcpy( &traceTriangles[ num ], tt, sizeof( *traceTriangles ) );
295 if ( num == numTraceTriangles ) {
300 /* return the triangle number */
307 AddItemToTraceNode() - ydnar
308 adds an item reference (winding or triangle) to a trace node
311 static int AddItemToTraceNode( traceNode_t *node, int num ){
321 if ( node->numItems >= node->maxItems ) {
322 /* allocate more room */
323 if ( node == traceNodes ) {
327 node->maxItems += GROW_NODE_ITEMS;
329 if ( node->maxItems <= 0 ) {
330 node->maxItems = GROW_NODE_ITEMS;
332 temp = safe_malloc( node->maxItems * sizeof( *node->items ) );
333 if ( node->items != NULL ) {
334 memcpy( temp, node->items, node->numItems * sizeof( *node->items ) );
337 node->items = (int*) temp;
341 node->items[ node->numItems ] = num;
344 /* return the count */
345 return ( node->numItems - 1 );
351 /* -------------------------------------------------------------------------------
355 ------------------------------------------------------------------------------- */
358 SetupTraceNodes_r() - ydnar
359 recursively create the initial trace node structure from the bsp tree
362 static int SetupTraceNodes_r( int bspNodeNum ){
363 int i, nodeNum, bspLeafNum, newNode;
368 /* get bsp node and plane */
369 bspNode = &bspNodes[ bspNodeNum ];
370 plane = &bspPlanes[ bspNode->planeNum ];
372 /* allocate a new trace node */
373 nodeNum = AllocTraceNode();
375 /* setup trace node */
376 traceNodes[ nodeNum ].type = PlaneTypeForNormal( plane->normal );
377 VectorCopy( plane->normal, traceNodes[ nodeNum ].plane );
378 traceNodes[ nodeNum ].plane[ 3 ] = plane->dist;
381 for ( i = 0; i < 2; i++ )
384 if ( bspNode->children[ i ] < 0 ) {
385 bspLeafNum = -bspNode->children[ i ] - 1;
388 newNode = AllocTraceNode();
389 traceNodes[ nodeNum ].children[ i ] = newNode;
390 /* have to do this separately, as gcc first executes LHS, then RHS, and if a realloc took place, this fails */
392 if ( bspLeafs[ bspLeafNum ].cluster == -1 ) {
393 traceNodes[ traceNodes[ nodeNum ].children[ i ] ].type = TRACE_LEAF_SOLID;
400 newNode = SetupTraceNodes_r( bspNode->children[ i ] );
401 traceNodes[ nodeNum ].children[ i ] = newNode;
404 if ( traceNodes[ nodeNum ].children[ i ] == 0 ) {
405 Error( "Invalid tracenode allocated" );
409 /* Sys_Printf("node %d children: %d %d\n", nodeNum, traceNodes[ nodeNum ].children[0], traceNodes[ nodeNum ].children[1]); */
411 /* return node number */
418 ClipTraceWinding() - ydnar
419 clips a trace winding against a plane into one or two parts
422 #define TW_ON_EPSILON 0.25f
424 void ClipTraceWinding( traceWinding_t *tw, vec4_t plane, traceWinding_t *front, traceWinding_t *back ){
426 int sides[ MAX_TW_VERTS ], counts[ 3 ] = { 0, 0, 0 };
427 float dists[ MAX_TW_VERTS ];
429 traceVert_t *a, *b, mid;
432 /* clear front and back */
436 /* classify points */
437 for ( i = 0; i < tw->numVerts; i++ )
439 dists[ i ] = DotProduct( tw->v[ i ].xyz, plane ) - plane[ 3 ];
440 if ( dists[ i ] < -TW_ON_EPSILON ) {
441 sides[ i ] = SIDE_BACK;
443 else if ( dists[ i ] > TW_ON_EPSILON ) {
444 sides[ i ] = SIDE_FRONT;
447 sides[ i ] = SIDE_ON;
449 counts[ sides[ i ] ]++;
452 /* entirely on front? */
453 if ( counts[ SIDE_BACK ] == 0 ) {
454 memcpy( front, tw, sizeof( *front ) );
457 /* entirely on back? */
458 else if ( counts[ SIDE_FRONT ] == 0 ) {
459 memcpy( back, tw, sizeof( *back ) );
462 /* straddles the plane */
465 /* setup front and back */
466 memcpy( front, tw, sizeof( *front ) );
468 memcpy( back, tw, sizeof( *back ) );
471 /* split the winding */
472 for ( i = 0; i < tw->numVerts; i++ )
475 j = ( i + 1 ) % tw->numVerts;
481 /* handle points on the splitting plane */
482 switch ( sides[ i ] )
485 if ( front->numVerts >= MAX_TW_VERTS ) {
486 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 );
495 back->v[ back->numVerts++ ] = *a;
499 if ( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS ) {
500 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
502 front->v[ front->numVerts++ ] = *a;
503 back->v[ back->numVerts++ ] = *a;
507 /* check next point to see if we need to split the edge */
508 if ( sides[ j ] == SIDE_ON || sides[ j ] == sides[ i ] ) {
513 if ( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS ) {
514 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
517 /* generate a split point */
518 frac = dists[ i ] / ( dists[ i ] - dists[ j ] );
519 for ( k = 0; k < 3; k++ )
521 /* minimize fp precision errors */
522 if ( plane[ k ] == 1.0f ) {
523 mid.xyz[ k ] = plane[ 3 ];
525 else if ( plane[ k ] == -1.0f ) {
526 mid.xyz[ k ] = -plane[ 3 ];
529 mid.xyz[ k ] = a->xyz[ k ] + frac * ( b->xyz[ k ] - a->xyz[ k ] );
532 /* set texture coordinates */
533 mid.st[ 0 ] = a->st[ 0 ] + frac * ( b->st[ 0 ] - a->st[ 0 ] );
534 mid.st[ 1 ] = a->st[ 1 ] + frac * ( b->st[ 1 ] - a->st[ 1 ] );
536 /* copy midpoint to front and back polygons */
537 front->v[ front->numVerts++ ] = mid;
538 back->v[ back->numVerts++ ] = mid;
546 FilterTraceWindingIntoNodes_r() - ydnar
547 filters a trace winding into the raytracing tree
550 static void FilterTraceWindingIntoNodes_r( traceWinding_t *tw, int nodeNum ){
552 vec4_t plane1, plane2, reverse;
554 traceWinding_t front, back;
557 /* don't filter if passed a bogus node (solid, etc) */
558 if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
563 node = &traceNodes[ nodeNum ];
565 /* is this a decision node? */
566 if ( node->type >= 0 ) {
567 /* create winding plane if necessary, filtering out bogus windings as well */
568 if ( nodeNum == headNodeNum ) {
569 if ( !PlaneFromPoints( tw->plane, tw->v[ 0 ].xyz, tw->v[ 1 ].xyz, tw->v[ 2 ].xyz ) ) {
574 /* validate the node */
575 if ( node->children[ 0 ] == 0 || node->children[ 1 ] == 0 ) {
576 Error( "Invalid tracenode: %d", nodeNum );
580 Vector4Copy( node->plane, plane1 );
582 /* get winding plane */
583 Vector4Copy( tw->plane, plane2 );
585 /* invert surface plane */
586 VectorSubtract( vec3_origin, plane2, reverse );
587 reverse[ 3 ] = -plane2[ 3 ];
590 if ( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f ) {
591 FilterTraceWindingIntoNodes_r( tw, node->children[ 0 ] );
596 if ( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f ) {
597 FilterTraceWindingIntoNodes_r( tw, node->children[ 1 ] );
601 /* clip the winding by node plane */
602 ClipTraceWinding( tw, plane1, &front, &back );
604 /* filter by node plane */
605 if ( front.numVerts >= 3 ) {
606 FilterTraceWindingIntoNodes_r( &front, node->children[ 0 ] );
608 if ( back.numVerts >= 3 ) {
609 FilterTraceWindingIntoNodes_r( &back, node->children[ 1 ] );
612 /* return to caller */
616 /* add winding to leaf node */
617 num = AddTraceWinding( tw );
618 AddItemToTraceNode( node, num );
624 SubdivideTraceNode_r() - ydnar
625 recursively subdivides a tracing node until it meets certain size and complexity criteria
628 static void SubdivideTraceNode_r( int nodeNum, int depth ){
629 int i, j, count, num, frontNum, backNum, type;
633 traceNode_t *node, *frontNode, *backNode;
634 traceWinding_t *tw, front, back;
638 if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
643 node = &traceNodes[ nodeNum ];
645 /* runaway recursion check */
646 if ( depth >= MAX_TRACE_DEPTH ) {
647 //% Sys_Printf( "Depth: (%d items)\n", node->numItems );
653 /* is this a decision node? */
654 if ( node->type >= 0 ) {
655 /* subdivide children */
656 frontNum = node->children[ 0 ];
657 backNum = node->children[ 1 ];
658 SubdivideTraceNode_r( frontNum, depth );
659 SubdivideTraceNode_r( backNum, depth );
664 ClearBounds( node->mins, node->maxs );
665 VectorClear( average );
667 for ( i = 0; i < node->numItems; i++ )
670 tw = &traceWindings[ node->items[ i ] ];
673 for ( j = 0; j < tw->numVerts; j++ )
675 AddPointToBounds( tw->v[ j ].xyz, node->mins, node->maxs );
676 average[ 0 ] += tw->v[ j ].xyz[ 0 ];
677 average[ 1 ] += tw->v[ j ].xyz[ 1 ];
678 average[ 2 ] += tw->v[ j ].xyz[ 2 ];
683 /* check triangle limit */
684 //% if( node->numItems <= MAX_NODE_ITEMS )
685 if ( ( count - ( node->numItems * 2 ) ) < MAX_NODE_TRIANGLES ) {
686 //% Sys_Printf( "Limit: (%d triangles)\n", (count - (node->numItems * 2)) );
691 /* the largest dimension of the bounding box will be the split axis */
692 VectorSubtract( node->maxs, node->mins, size );
693 if ( size[ 0 ] >= size[ 1 ] && size[ 0 ] >= size[ 2 ] ) {
696 else if ( size[ 1 ] >= size[ 0 ] && size[ 1 ] >= size[ 2 ] ) {
703 /* don't split small nodes */
704 if ( size[ type ] <= MIN_NODE_SIZE ) {
705 //% Sys_Printf( "Limit: %f %f %f (%d items)\n", size[ 0 ], size[ 1 ], size[ 2 ], node->numItems );
710 /* set max trace depth */
711 if ( depth > maxTraceDepth ) {
712 maxTraceDepth = depth;
715 /* snap the average */
716 dist = floor( average[ type ] / count );
719 if ( dist <= node->mins[ type ] || dist >= node->maxs[ type ] ) {
720 dist = floor( 0.5f * ( node->mins[ type ] + node->maxs[ type ] ) );
723 /* allocate child nodes */
724 frontNum = AllocTraceNode();
725 backNum = AllocTraceNode();
728 node = &traceNodes[ nodeNum ];
729 frontNode = &traceNodes[ frontNum ];
730 backNode = &traceNodes[ backNum ];
732 /* attach children */
734 node->plane[ type ] = 1.0f;
735 node->plane[ 3 ] = dist;
736 node->children[ 0 ] = frontNum;
737 node->children[ 1 ] = backNum;
739 /* setup front node */
740 frontNode->maxItems = ( node->maxItems >> 1 );
741 frontNode->items = safe_malloc( frontNode->maxItems * sizeof( *frontNode->items ) );
743 /* setup back node */
744 backNode->maxItems = ( node->maxItems >> 1 );
745 backNode->items = safe_malloc( backNode->maxItems * sizeof( *backNode->items ) );
747 /* filter windings into child nodes */
748 for ( i = 0; i < node->numItems; i++ )
751 tw = &traceWindings[ node->items[ i ] ];
753 /* clip the winding by the new split plane */
754 ClipTraceWinding( tw, node->plane, &front, &back );
756 /* kill the existing winding */
757 if ( front.numVerts >= 3 || back.numVerts >= 3 ) {
758 deadWinding = node->items[ i ];
761 /* add front winding */
762 if ( front.numVerts >= 3 ) {
763 num = AddTraceWinding( &front );
764 AddItemToTraceNode( frontNode, num );
767 /* add back winding */
768 if ( back.numVerts >= 3 ) {
769 num = AddTraceWinding( &back );
770 AddItemToTraceNode( backNode, num );
774 /* free original node winding list */
781 if ( frontNode->numItems <= 0 ) {
782 frontNode->maxItems = 0;
783 free( frontNode->items );
784 frontNode->items = NULL;
787 if ( backNode->numItems <= 0 ) {
788 backNode->maxItems = 0;
789 free( backNode->items );
790 backNode->items = NULL;
793 /* subdivide children */
794 SubdivideTraceNode_r( frontNum, depth );
795 SubdivideTraceNode_r( backNum, depth );
801 TriangulateTraceNode_r()
802 optimizes the tracing data by changing trace windings into triangles
805 static int TriangulateTraceNode_r( int nodeNum ){
806 int i, j, num, frontNum, backNum, numWindings, *windings;
813 if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
818 node = &traceNodes[ nodeNum ];
820 /* is this a decision node? */
821 if ( node->type >= 0 ) {
822 /* triangulate children */
823 frontNum = node->children[ 0 ];
824 backNum = node->children[ 1 ];
825 node->numItems = TriangulateTraceNode_r( frontNum );
826 node->numItems += TriangulateTraceNode_r( backNum );
827 return node->numItems;
831 if ( node->numItems == 0 ) {
833 if ( node->items != NULL ) {
836 return node->numItems;
839 /* store off winding data */
840 numWindings = node->numItems;
841 windings = node->items;
845 node->maxItems = numWindings * 2;
846 node->items = safe_malloc( node->maxItems * sizeof( tt ) );
848 /* walk winding list */
849 for ( i = 0; i < numWindings; i++ )
852 tw = &traceWindings[ windings[ i ] ];
855 tt.infoNum = tw->infoNum;
856 tt.v[ 0 ] = tw->v[ 0 ];
858 /* walk vertex list */
859 for ( j = 1; j + 1 < tw->numVerts; j++ )
862 tt.v[ 1 ] = tw->v[ j ];
863 tt.v[ 2 ] = tw->v[ j + 1 ];
865 /* find vectors for two edges sharing the first vert */
866 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
867 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
869 /* add it to the node */
870 num = AddTraceTriangle( &tt );
871 AddItemToTraceNode( node, num );
876 if ( windings != NULL ) {
880 /* return item count */
881 return node->numItems;
886 /* -------------------------------------------------------------------------------
888 shadow casting item setup (triangles, patches, entities)
890 ------------------------------------------------------------------------------- */
893 PopulateWithBSPModel() - ydnar
894 filters a bsp model's surfaces into the raytracing tree
897 static void PopulateWithBSPModel( bspModel_t *model, m4x4_t transform ){
898 int i, j, x, y, pw[ 5 ], r, nodeNum;
899 bspDrawSurface_t *ds;
901 bspDrawVert_t *verts;
903 mesh_t srcMesh, *mesh, *subdivided;
909 if ( model == NULL || transform == NULL ) {
913 /* walk the list of surfaces in this model and fill out the info structs */
914 for ( i = 0; i < model->numBSPSurfaces; i++ )
916 /* get surface and info */
917 ds = &bspDrawSurfaces[ model->firstBSPSurface + i ];
918 info = &surfaceInfos[ model->firstBSPSurface + i ];
919 if ( info->si == NULL ) {
924 if ( !info->castShadows ) {
929 if ( ds->surfaceType == MST_PATCH && patchShadows == qfalse ) {
933 /* some surfaces in the bsp might have been tagged as nodraw, with a bogus shader */
934 if ( ( bspShaders[ ds->shaderNum ].contentFlags & noDrawContentFlags ) ||
935 ( bspShaders[ ds->shaderNum ].surfaceFlags & noDrawSurfaceFlags ) ) {
939 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
940 if ( ( info->si->compileFlags & C_NODRAW ) ) {
943 if ( ( info->si->compileFlags & C_TRANSLUCENT ) &&
944 !( info->si->compileFlags & C_ALPHASHADOW ) &&
945 !( info->si->compileFlags & C_LIGHTFILTER ) ) {
949 /* setup trace info */
951 ti.castShadows = info->castShadows;
952 ti.surfaceNum = model->firstBSPBrush + i;
953 ti.skipGrid = ( ds->surfaceType == MST_PATCH );
955 /* choose which node (normal or skybox) */
956 if ( info->parentSurfaceNum >= 0 ) {
957 nodeNum = skyboxNodeNum;
959 /* sky surfaces in portal skies are ignored */
960 if ( info->si->compileFlags & C_SKY ) {
965 nodeNum = headNodeNum;
968 /* setup trace winding */
969 memset( &tw, 0, sizeof( tw ) );
970 tw.infoNum = AddTraceInfo( &ti );
974 switch ( ds->surfaceType )
978 /* subdivide the surface */
979 srcMesh.width = ds->patchWidth;
980 srcMesh.height = ds->patchHeight;
981 srcMesh.verts = &bspDrawVerts[ ds->firstVert ];
982 //% subdivided = SubdivideMesh( srcMesh, 8, 512 );
983 subdivided = SubdivideMesh2( srcMesh, info->patchIterations );
985 /* fit it to the curve and remove colinear verts on rows/columns */
986 PutMeshOnCurve( *subdivided );
987 mesh = RemoveLinearMeshColumnsRows( subdivided );
988 FreeMesh( subdivided );
993 /* subdivide each quad to place the models */
994 for ( y = 0; y < ( mesh->height - 1 ); y++ )
996 for ( x = 0; x < ( mesh->width - 1 ); x++ )
999 pw[ 0 ] = x + ( y * mesh->width );
1000 pw[ 1 ] = x + ( ( y + 1 ) * mesh->width );
1001 pw[ 2 ] = x + 1 + ( ( y + 1 ) * mesh->width );
1002 pw[ 3 ] = x + 1 + ( y * mesh->width );
1003 pw[ 4 ] = x + ( y * mesh->width ); /* same as pw[ 0 ] */
1008 /* make first triangle */
1009 VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
1010 Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
1011 VectorCopy( verts[ pw[ r + 1 ] ].xyz, tw.v[ 1 ].xyz );
1012 Vector2Copy( verts[ pw[ r + 1 ] ].st, tw.v[ 1 ].st );
1013 VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 2 ].xyz );
1014 Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 2 ].st );
1015 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1016 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1017 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1018 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1020 /* make second triangle */
1021 VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
1022 Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
1023 VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 1 ].xyz );
1024 Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 1 ].st );
1025 VectorCopy( verts[ pw[ r + 3 ] ].xyz, tw.v[ 2 ].xyz );
1026 Vector2Copy( verts[ pw[ r + 3 ] ].st, tw.v[ 2 ].st );
1027 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1028 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1029 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1030 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1034 /* free the subdivided mesh */
1038 /* handle triangle surfaces */
1039 case MST_TRIANGLE_SOUP:
1041 /* set verts and indexes */
1042 verts = &bspDrawVerts[ ds->firstVert ];
1043 indexes = &bspDrawIndexes[ ds->firstIndex ];
1045 /* walk the triangle list */
1046 for ( j = 0; j < ds->numIndexes; j += 3 )
1048 VectorCopy( verts[ indexes[ j ] ].xyz, tw.v[ 0 ].xyz );
1049 Vector2Copy( verts[ indexes[ j ] ].st, tw.v[ 0 ].st );
1050 VectorCopy( verts[ indexes[ j + 1 ] ].xyz, tw.v[ 1 ].xyz );
1051 Vector2Copy( verts[ indexes[ j + 1 ] ].st, tw.v[ 1 ].st );
1052 VectorCopy( verts[ indexes[ j + 2 ] ].xyz, tw.v[ 2 ].xyz );
1053 Vector2Copy( verts[ indexes[ j + 2 ] ].st, tw.v[ 2 ].st );
1054 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1055 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1056 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1057 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1061 /* other surface types do not cast shadows */
1071 PopulateWithPicoModel() - ydnar
1072 filters a picomodel's surfaces into the raytracing tree
1075 static void PopulateWithPicoModel( int castShadows, picoModel_t *model, m4x4_t transform ){
1076 int i, j, k, numSurfaces, numIndexes;
1077 picoSurface_t *surface;
1078 picoShader_t *shader;
1079 picoVec_t *xyz, *st;
1080 picoIndex_t *indexes;
1086 if ( model == NULL || transform == NULL ) {
1091 numSurfaces = PicoGetModelNumSurfaces( model );
1093 /* walk the list of surfaces in this model and fill out the info structs */
1094 for ( i = 0; i < numSurfaces; i++ )
1097 surface = PicoGetModelSurface( model, i );
1098 if ( surface == NULL ) {
1102 /* only handle triangle surfaces initially (fixme: support patches) */
1103 if ( PicoGetSurfaceType( surface ) != PICO_TRIANGLES ) {
1107 /* get shader (fixme: support shader remapping) */
1108 shader = PicoGetSurfaceShader( surface );
1109 if ( shader == NULL ) {
1112 ti.si = ShaderInfoForShaderNull( PicoGetShaderName( shader ) );
1113 if ( ti.si == NULL ) {
1117 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
1118 if ( ( ti.si->compileFlags & C_NODRAW ) ) {
1121 if ( ( ti.si->compileFlags & C_TRANSLUCENT ) &&
1122 !( ti.si->compileFlags & C_ALPHASHADOW ) &&
1123 !( ti.si->compileFlags & C_LIGHTFILTER ) ) {
1127 /* setup trace info */
1128 ti.castShadows = castShadows;
1130 ti.skipGrid = qtrue; // also ignore picomodels when skipping patches
1132 /* setup trace winding */
1133 memset( &tw, 0, sizeof( tw ) );
1134 tw.infoNum = AddTraceInfo( &ti );
1138 numIndexes = PicoGetSurfaceNumIndexes( surface );
1139 indexes = PicoGetSurfaceIndexes( surface, 0 );
1141 /* walk the triangle list */
1142 for ( j = 0; j < numIndexes; j += 3, indexes += 3 )
1144 for ( k = 0; k < 3; k++ )
1146 xyz = PicoGetSurfaceXYZ( surface, indexes[ k ] );
1147 st = PicoGetSurfaceST( surface, 0, indexes[ k ] );
1148 VectorCopy( xyz, tw.v[ k ].xyz );
1149 Vector2Copy( st, tw.v[ k ].st );
1150 m4x4_transform_point( transform, tw.v[ k ].xyz );
1152 FilterTraceWindingIntoNodes_r( &tw, headNodeNum );
1160 PopulateTraceNodes() - ydnar
1161 fills the raytracing tree with world and entity occluders
1164 static void PopulateTraceNodes( void ){
1165 int i, m, frame, castShadows;
1170 vec3_t origin, scale, angles;
1174 /* add worldspawn triangles */
1175 m4x4_identity( transform );
1176 PopulateWithBSPModel( &bspModels[ 0 ], transform );
1178 /* walk each entity list */
1179 for ( i = 1; i < numEntities; i++ )
1184 /* get shadow flags */
1185 castShadows = ENTITY_CAST_SHADOWS;
1186 GetEntityShadowFlags( e, NULL, &castShadows, NULL );
1189 if ( !castShadows ) {
1193 /* get entity origin */
1194 GetVectorForKey( e, "origin", origin );
1197 scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = 1.0f;
1198 temp = FloatForKey( e, "modelscale" );
1199 if ( temp != 0.0f ) {
1200 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 ] );
1207 /* get "angle" (yaw) or "angles" (pitch yaw roll) */
1208 angles[ 0 ] = angles[ 1 ] = angles[ 2 ] = 0.0f;
1209 angles[ 2 ] = FloatForKey( e, "angle" );
1210 value = ValueForKey( e, "angles" );
1211 if ( value[ 0 ] != '\0' ) {
1212 sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
1215 /* set transform matrix (thanks spog) */
1216 m4x4_identity( transform );
1217 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
1219 /* hack: Stable-1_2 and trunk have differing row/column major matrix order
1220 this transpose is necessary with Stable-1_2
1221 uncomment the following line with old m4x4_t (non 1.3/spog_branch) code */
1222 //% m4x4_transpose( transform );
1225 value = ValueForKey( e, "model" );
1227 /* switch on model type */
1228 switch ( value[ 0 ] )
1236 m = atoi( &value[ 1 ] );
1237 if ( m <= 0 || m >= numBSPModels ) {
1240 PopulateWithBSPModel( &bspModels[ m ], transform );
1243 /* external model */
1246 if ( strcmp( "", ValueForKey( e, "_frame" ) ) ) {
1247 frame = IntForKey( e, "_frame" );
1249 else if ( strcmp( "", ValueForKey( e, "frame" ) ) ) {
1250 frame = IntForKey( e, "frame" );
1252 model = LoadModel( value, frame );
1253 if ( model == NULL ) {
1256 PopulateWithPicoModel( castShadows, model, transform );
1261 value = ValueForKey( e, "model2" );
1263 /* switch on model type */
1264 switch ( value[ 0 ] )
1272 m = atoi( &value[ 1 ] );
1273 if ( m <= 0 || m >= numBSPModels ) {
1276 PopulateWithBSPModel( &bspModels[ m ], transform );
1279 /* external model */
1281 frame = IntForKey( e, "_frame2" );
1282 model = LoadModel( value, frame );
1283 if ( model == NULL ) {
1286 PopulateWithPicoModel( castShadows, model, transform );
1295 /* -------------------------------------------------------------------------------
1297 trace initialization
1299 ------------------------------------------------------------------------------- */
1302 SetupTraceNodes() - ydnar
1303 creates a balanced bsp with axis-aligned splits for efficient raytracing
1306 void SetupTraceNodes( void ){
1308 Sys_FPrintf( SYS_VRB, "--- SetupTraceNodes ---\n" );
1310 /* find nodraw bit */
1311 noDrawContentFlags = noDrawSurfaceFlags = noDrawCompileFlags = 0;
1312 ApplySurfaceParm( "nodraw", &noDrawContentFlags, &noDrawSurfaceFlags, &noDrawCompileFlags );
1314 /* create the baseline raytracing tree from the bsp tree */
1315 headNodeNum = SetupTraceNodes_r( 0 );
1317 /* create outside node for skybox surfaces */
1318 skyboxNodeNum = AllocTraceNode();
1320 /* populate the tree with triangles from the world and shadow casting entities */
1321 PopulateTraceNodes();
1323 /* create the raytracing bsp */
1324 if ( loMem == qfalse ) {
1325 SubdivideTraceNode_r( headNodeNum, 0 );
1326 SubdivideTraceNode_r( skyboxNodeNum, 0 );
1329 /* create triangles from the trace windings */
1330 TriangulateTraceNode_r( headNodeNum );
1331 TriangulateTraceNode_r( skyboxNodeNum );
1333 /* emit some stats */
1334 //% Sys_FPrintf( SYS_VRB, "%9d original triangles\n", numOriginalTriangles );
1335 Sys_FPrintf( SYS_VRB, "%9d trace windings (%.2fMB)\n", numTraceWindings, (float) ( numTraceWindings * sizeof( *traceWindings ) ) / ( 1024.0f * 1024.0f ) );
1336 Sys_FPrintf( SYS_VRB, "%9d trace triangles (%.2fMB)\n", numTraceTriangles, (float) ( numTraceTriangles * sizeof( *traceTriangles ) ) / ( 1024.0f * 1024.0f ) );
1337 Sys_FPrintf( SYS_VRB, "%9d trace nodes (%.2fMB)\n", numTraceNodes, (float) ( numTraceNodes * sizeof( *traceNodes ) ) / ( 1024.0f * 1024.0f ) );
1338 Sys_FPrintf( SYS_VRB, "%9d leaf nodes (%.2fMB)\n", numTraceLeafNodes, (float) ( numTraceLeafNodes * sizeof( *traceNodes ) ) / ( 1024.0f * 1024.0f ) );
1339 //% Sys_FPrintf( SYS_VRB, "%9d average triangles per leaf node\n", numTraceTriangles / numTraceLeafNodes );
1340 Sys_FPrintf( SYS_VRB, "%9d average windings per leaf node\n", numTraceWindings / ( numTraceLeafNodes + 1 ) );
1341 Sys_FPrintf( SYS_VRB, "%9d max trace depth\n", maxTraceDepth );
1343 /* free trace windings */
1344 free( traceWindings );
1345 numTraceWindings = 0;
1346 maxTraceWindings = 0;
1349 /* debug code: write out trace triangles to an alias obj file */
1354 char filename[ 1024 ];
1359 strcpy( filename, source );
1360 StripExtension( filename );
1361 strcat( filename, ".lin" );
1362 Sys_Printf( "Opening light trace file %s...\n", filename );
1363 file = fopen( filename, "w" );
1364 if ( file == NULL ) {
1365 Error( "Error opening %s for writing", filename );
1368 /* walk node list */
1369 for ( i = 0; i < numTraceWindings; i++ )
1371 tw = &traceWindings[ i ];
1372 for ( j = 0; j < tw->numVerts + 1; j++ )
1373 fprintf( file, "%f %f %f\n",
1374 tw->v[ j % tw->numVerts ].xyz[ 0 ], tw->v[ j % tw->numVerts ].xyz[ 1 ], tw->v[ j % tw->numVerts ].xyz[ 2 ] );
1385 /* -------------------------------------------------------------------------------
1389 ------------------------------------------------------------------------------- */
1393 based on code written by william 'spog' joseph
1394 based on code originally written by tomas moller and ben trumbore, journal of graphics tools, 2(1):21-28, 1997
1397 #define BARY_EPSILON 0.01f
1398 #define ASLF_EPSILON 0.0001f /* so to not get double shadows */
1399 #define COPLANAR_EPSILON 0.25f //% 0.000001f
1400 #define NEAR_SHADOW_EPSILON 1.5f //% 1.25f
1401 #define SELF_SHADOW_EPSILON 0.5f
1403 qboolean TraceTriangle( traceInfo_t *ti, traceTriangle_t *tt, trace_t *trace ){
1405 float tvec[ 3 ], pvec[ 3 ], qvec[ 3 ];
1406 float det, invDet, depth;
1407 float u, v, w, s, t;
1414 /* don't double-trace against sky */
1416 if ( trace->compileFlags & si->compileFlags & C_SKY ) {
1420 /* receive shadows from worldspawn group only */
1421 if ( trace->recvShadows == 1 ) {
1422 if ( ti->castShadows != 1 ) {
1427 /* receive shadows from same group and worldspawn group */
1428 else if ( trace->recvShadows > 1 ) {
1429 if ( ti->castShadows != 1 && abs( ti->castShadows ) != abs( trace->recvShadows ) ) {
1432 //% Sys_Printf( "%d:%d ", tt->castShadows, trace->recvShadows );
1435 /* receive shadows from the same group only (< 0) */
1438 if ( abs( ti->castShadows ) != abs( trace->recvShadows ) ) {
1443 /* skip patches when doing the grid (FIXME this is an ugly hack) */
1445 if ( ti->skipGrid ) {
1450 /* begin calculating determinant - also used to calculate u parameter */
1451 CrossProduct( trace->direction, tt->edge2, pvec );
1453 /* if determinant is near zero, trace lies in plane of triangle */
1454 det = DotProduct( tt->edge1, pvec );
1456 /* the non-culling branch */
1457 if ( fabs( det ) < COPLANAR_EPSILON ) {
1460 invDet = 1.0f / det;
1462 /* calculate distance from first vertex to ray origin */
1463 VectorSubtract( trace->origin, tt->v[ 0 ].xyz, tvec );
1465 /* calculate u parameter and test bounds */
1466 u = DotProduct( tvec, pvec ) * invDet;
1467 if ( u < -BARY_EPSILON || u > ( 1.0f + BARY_EPSILON ) ) {
1471 /* prepare to test v parameter */
1472 CrossProduct( tvec, tt->edge1, qvec );
1474 /* calculate v parameter and test bounds */
1475 v = DotProduct( trace->direction, qvec ) * invDet;
1476 if ( v < -BARY_EPSILON || ( u + v ) > ( 1.0f + BARY_EPSILON ) ) {
1480 /* calculate t (depth) */
1481 depth = DotProduct( tt->edge2, qvec ) * invDet;
1482 if ( depth <= trace->inhibitRadius || depth >= trace->distance ) {
1486 /* if hitpoint is really close to trace origin (sample point), then check for self-shadowing */
1487 if ( depth <= SELF_SHADOW_EPSILON ) {
1488 /* don't self-shadow */
1489 for ( i = 0; i < trace->numSurfaces; i++ )
1491 if ( ti->surfaceNum == trace->surfaces[ i ] ) {
1497 /* stack compile flags */
1498 trace->compileFlags |= si->compileFlags;
1500 /* don't trace against sky */
1501 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 ) {
1508 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1509 VectorClear( trace->color );
1510 trace->opaque = qtrue;
1514 /* force subsampling because the lighting is texture dependent */
1515 trace->forceSubsampling = 1.0;
1517 /* try to avoid double shadows near triangle seams */
1518 if ( u < -ASLF_EPSILON || u > ( 1.0f + ASLF_EPSILON ) ||
1519 v < -ASLF_EPSILON || ( u + v ) > ( 1.0f + ASLF_EPSILON ) ) {
1523 /* calculate w parameter */
1524 w = 1.0f - ( u + v );
1526 /* calculate st from uvw (barycentric) coordinates */
1527 s = w * tt->v[ 0 ].st[ 0 ] + u * tt->v[ 1 ].st[ 0 ] + v * tt->v[ 2 ].st[ 0 ];
1528 t = w * tt->v[ 0 ].st[ 1 ] + u * tt->v[ 1 ].st[ 1 ] + v * tt->v[ 2 ].st[ 1 ];
1531 is = s * si->lightImage->width;
1532 it = t * si->lightImage->height;
1536 if ( is > si->lightImage->width - 1 ) {
1537 is = si->lightImage->width - 1;
1542 if ( it > si->lightImage->height - 1 ) {
1543 it = si->lightImage->height - 1;
1547 pixel = si->lightImage->pixels + 4 * ( it * si->lightImage->width + is );
1549 /* ydnar: color filter */
1550 if ( si->compileFlags & C_LIGHTFILTER ) {
1551 /* filter by texture color */
1552 trace->color[ 0 ] *= ( ( 1.0f / 255.0f ) * pixel[ 0 ] );
1553 trace->color[ 1 ] *= ( ( 1.0f / 255.0f ) * pixel[ 1 ] );
1554 trace->color[ 2 ] *= ( ( 1.0f / 255.0f ) * pixel[ 2 ] );
1557 /* ydnar: alpha filter */
1558 if ( si->compileFlags & C_ALPHASHADOW ) {
1559 /* filter by inverse texture alpha */
1560 shadow = ( 1.0f / 255.0f ) * ( 255 - pixel[ 3 ] );
1561 trace->color[ 0 ] *= shadow;
1562 trace->color[ 1 ] *= shadow;
1563 trace->color[ 2 ] *= shadow;
1566 /* check filter for opaque */
1567 if ( trace->color[ 0 ] <= 0.001f && trace->color[ 1 ] <= 0.001f && trace->color[ 2 ] <= 0.001f ) {
1568 VectorClear( trace->color );
1569 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1570 trace->opaque = qtrue;
1574 /* continue tracing */
1581 TraceWinding() - ydnar
1585 qboolean TraceWinding( traceWinding_t *tw, trace_t *trace ){
1591 tt.infoNum = tw->infoNum;
1592 tt.v[ 0 ] = tw->v[ 0 ];
1594 /* walk vertex list */
1595 for ( i = 1; i + 1 < tw->numVerts; i++ )
1598 tt.v[ 1 ] = tw->v[ i ];
1599 tt.v[ 2 ] = tw->v[ i + 1 ];
1601 /* find vectors for two edges sharing the first vert */
1602 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
1603 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
1606 if ( TraceTriangle( &traceInfos[ tt.infoNum ], &tt, trace ) ) {
1620 returns qtrue if something is hit and tracing can stop
1623 static qboolean TraceLine_r( int nodeNum, vec3_t origin, vec3_t end, trace_t *trace ){
1626 float front, back, frac;
1631 /* bogus node number means solid, end tracing unless testing all */
1632 if ( nodeNum < 0 ) {
1633 VectorCopy( origin, trace->hit );
1634 trace->passSolid = qtrue;
1639 node = &traceNodes[ nodeNum ];
1642 if ( node->type == TRACE_LEAF_SOLID ) {
1643 VectorCopy( origin, trace->hit );
1644 trace->passSolid = qtrue;
1649 if ( node->type < 0 ) {
1650 /* note leaf and return */
1651 if ( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES ) {
1652 trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
1657 /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
1658 if ( trace->testAll && node->numItems == 0 ) {
1662 /* classify beginning and end points */
1663 switch ( node->type )
1666 front = origin[ 0 ] - node->plane[ 3 ];
1667 back = end[ 0 ] - node->plane[ 3 ];
1671 front = origin[ 1 ] - node->plane[ 3 ];
1672 back = end[ 1 ] - node->plane[ 3 ];
1676 front = origin[ 2 ] - node->plane[ 3 ];
1677 back = end[ 2 ] - node->plane[ 3 ];
1681 front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
1682 back = DotProduct( end, node->plane ) - node->plane[ 3 ];
1686 /* entirely in front side? */
1687 if ( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON ) {
1688 return TraceLine_r( node->children[ 0 ], origin, end, trace );
1691 /* entirely on back side? */
1692 if ( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON ) {
1693 return TraceLine_r( node->children[ 1 ], origin, end, trace );
1699 /* calculate intercept point */
1700 frac = front / ( front - back );
1701 mid[ 0 ] = origin[ 0 ] + ( end[ 0 ] - origin[ 0 ] ) * frac;
1702 mid[ 1 ] = origin[ 1 ] + ( end[ 1 ] - origin[ 1 ] ) * frac;
1703 mid[ 2 ] = origin[ 2 ] + ( end[ 2 ] - origin[ 2 ] ) * frac;
1705 /* fixme: check inhibit radius, then solid nodes and ignore */
1707 /* set trace hit here */
1708 //% VectorCopy( mid, trace->hit );
1710 /* trace first side */
1711 r = TraceLine_r( node->children[ side ], origin, mid, trace );
1716 /* trace other side */
1717 return TraceLine_r( node->children[ !side ], mid, end, trace );
1724 rewrote this function a bit :)
1727 void TraceLine( trace_t *trace ){
1730 traceTriangle_t *tt;
1734 /* setup output (note: this code assumes the input data is completely filled out) */
1735 trace->passSolid = qfalse;
1736 trace->opaque = qfalse;
1737 trace->compileFlags = 0;
1738 trace->numTestNodes = 0;
1741 if ( !trace->recvShadows || !trace->testOcclusion || trace->distance <= 0.00001f ) {
1745 /* trace through nodes */
1746 TraceLine_r( headNodeNum, trace->origin, trace->end, trace );
1747 if ( trace->passSolid && !trace->testAll ) {
1748 trace->opaque = qtrue;
1752 /* skip surfaces? */
1757 /* testall means trace through sky */
1758 if ( trace->testAll && trace->numTestNodes < MAX_TRACE_TEST_NODES &&
1759 trace->compileFlags & C_SKY &&
1760 ( trace->numSurfaces == 0 || surfaceInfos[ trace->surfaces[ 0 ] ].childSurfaceNum < 0 ) ) {
1761 //% trace->testNodes[ trace->numTestNodes++ ] = skyboxNodeNum;
1762 TraceLine_r( skyboxNodeNum, trace->origin, trace->end, trace );
1765 /* walk node list */
1766 for ( i = 0; i < trace->numTestNodes; i++ )
1769 node = &traceNodes[ trace->testNodes[ i ] ];
1771 /* walk node item list */
1772 for ( j = 0; j < node->numItems; j++ )
1774 tt = &traceTriangles[ node->items[ j ] ];
1775 ti = &traceInfos[ tt->infoNum ];
1776 if ( TraceTriangle( ti, tt, trace ) ) {
1779 //% if( TraceWinding( &traceWindings[ node->items[ j ] ], trace ) )
1788 SetupTrace() - ydnar
1789 sets up certain trace values
1792 float SetupTrace( trace_t *trace ){
1793 VectorSubtract( trace->end, trace->origin, trace->displacement );
1794 trace->distance = VectorNormalize( trace->displacement, trace->direction );
1795 VectorCopy( trace->origin, trace->hit );
1796 return trace->distance;