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 // vortex: increased from 12 to 24 for ability co compile some insane maps with large curve count
60 #define MAX_TW_VERTS 24
62 #define TRACE_ON_EPSILON 0.1f
65 #define TRACE_LEAF_SOLID -2
67 typedef struct traceVert_s
74 typedef struct traceInfo_s
77 int surfaceNum, castShadows, skipGrid;
81 typedef struct traceWinding_s
84 int infoNum, numVerts;
85 traceVert_t v[ MAX_TW_VERTS ];
89 typedef struct traceTriangle_s
97 typedef struct traceNode_s
103 int numItems, maxItems;
109 int noDrawContentFlags, noDrawSurfaceFlags, noDrawCompileFlags;
111 int numTraceInfos = 0, maxTraceInfos = 0, firstTraceInfo = 0;
112 traceInfo_t *traceInfos = NULL;
114 int numTraceWindings = 0, maxTraceWindings = 0, deadWinding = -1;
115 traceWinding_t *traceWindings = NULL;
117 int numTraceTriangles = 0, maxTraceTriangles = 0, deadTriangle = -1;
118 traceTriangle_t *traceTriangles = NULL;
120 int headNodeNum = 0, skyboxNodeNum = 0, maxTraceDepth = 0, numTraceLeafNodes = 0;
121 int numTraceNodes = 0, maxTraceNodes = 0;
122 traceNode_t *traceNodes = NULL;
126 /* -------------------------------------------------------------------------------
128 allocation and list management
130 ------------------------------------------------------------------------------- */
133 AddTraceInfo() - ydnar
134 adds a trace info structure to the pool
137 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 ) {
154 if ( numTraceInfos >= maxTraceInfos ) {
155 /* allocate more room */
156 maxTraceInfos += GROW_TRACE_INFOS;
157 temp = safe_malloc( maxTraceInfos * sizeof( *traceInfos ) );
158 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 ) {
171 /* return the ti number */
178 AllocTraceNode() - ydnar
179 allocates a new trace node
182 static int AllocTraceNode( void ){
187 if ( numTraceNodes >= maxTraceNodes ) {
188 /* reallocate more room */
189 maxTraceNodes += GROW_TRACE_NODES;
190 temp = safe_malloc( maxTraceNodes * sizeof( traceNode_t ) );
191 if ( traceNodes != NULL ) {
192 memcpy( temp, traceNodes, numTraceNodes * sizeof( traceNode_t ) );
199 memset( &traceNodes[ numTraceNodes ], 0, sizeof( traceNode_t ) );
200 traceNodes[ numTraceNodes ].type = TRACE_LEAF;
201 ClearBounds( traceNodes[ numTraceNodes ].mins, traceNodes[ numTraceNodes ].maxs );
204 /* return the count */
205 return ( numTraceNodes - 1 );
211 AddTraceWinding() - ydnar
212 adds a winding to the raytracing pool
215 static int AddTraceWinding( traceWinding_t *tw ){
220 /* check for a dead winding */
221 if ( deadWinding >= 0 && deadWinding < numTraceWindings ) {
226 /* put winding at the end of the list */
227 num = numTraceWindings;
230 if ( numTraceWindings >= maxTraceWindings ) {
231 /* allocate more room */
232 maxTraceWindings += GROW_TRACE_WINDINGS;
233 temp = safe_malloc( maxTraceWindings * sizeof( *traceWindings ) );
234 if ( traceWindings != NULL ) {
235 memcpy( temp, traceWindings, numTraceWindings * sizeof( *traceWindings ) );
236 free( traceWindings );
238 traceWindings = (traceWinding_t*) temp;
242 /* add the winding */
243 memcpy( &traceWindings[ num ], tw, sizeof( *traceWindings ) );
244 if ( num == numTraceWindings ) {
249 /* return the winding number */
256 AddTraceTriangle() - ydnar
257 adds a triangle to the raytracing pool
260 static int AddTraceTriangle( traceTriangle_t *tt ){
265 /* check for a dead triangle */
266 if ( deadTriangle >= 0 && deadTriangle < numTraceTriangles ) {
271 /* put triangle at the end of the list */
272 num = numTraceTriangles;
275 if ( numTraceTriangles >= maxTraceTriangles ) {
276 /* allocate more room */
277 maxTraceTriangles += GROW_TRACE_TRIANGLES;
278 temp = safe_malloc( maxTraceTriangles * sizeof( *traceTriangles ) );
279 if ( traceTriangles != NULL ) {
280 memcpy( temp, traceTriangles, numTraceTriangles * sizeof( *traceTriangles ) );
281 free( traceTriangles );
283 traceTriangles = (traceTriangle_t*) temp;
287 /* find vectors for two edges sharing the first vert */
288 VectorSubtract( tt->v[ 1 ].xyz, tt->v[ 0 ].xyz, tt->edge1 );
289 VectorSubtract( tt->v[ 2 ].xyz, tt->v[ 0 ].xyz, tt->edge2 );
291 /* add the triangle */
292 memcpy( &traceTriangles[ num ], tt, sizeof( *traceTriangles ) );
293 if ( num == numTraceTriangles ) {
298 /* return the triangle number */
305 AddItemToTraceNode() - ydnar
306 adds an item reference (winding or triangle) to a trace node
309 static int AddItemToTraceNode( traceNode_t *node, int num ){
319 if ( node->numItems >= node->maxItems ) {
320 /* allocate more room */
321 if ( node == traceNodes ) {
325 node->maxItems += GROW_NODE_ITEMS;
327 if ( node->maxItems <= 0 ) {
328 node->maxItems = GROW_NODE_ITEMS;
330 temp = safe_malloc( node->maxItems * sizeof( *node->items ) );
331 if ( node->items != NULL ) {
332 memcpy( temp, node->items, node->numItems * sizeof( *node->items ) );
335 node->items = (int*) temp;
339 node->items[ node->numItems ] = num;
342 /* return the count */
343 return ( node->numItems - 1 );
349 /* -------------------------------------------------------------------------------
353 ------------------------------------------------------------------------------- */
356 SetupTraceNodes_r() - ydnar
357 recursively create the initial trace node structure from the bsp tree
360 static int SetupTraceNodes_r( int bspNodeNum ){
361 int i, nodeNum, bspLeafNum, newNode;
366 /* get bsp node and plane */
367 bspNode = &bspNodes[ bspNodeNum ];
368 plane = &bspPlanes[ bspNode->planeNum ];
370 /* allocate a new trace node */
371 nodeNum = AllocTraceNode();
373 /* setup trace node */
374 traceNodes[ nodeNum ].type = PlaneTypeForNormal( plane->normal );
375 VectorCopy( plane->normal, traceNodes[ nodeNum ].plane );
376 traceNodes[ nodeNum ].plane[ 3 ] = plane->dist;
379 for ( i = 0; i < 2; i++ )
382 if ( bspNode->children[ i ] < 0 ) {
383 bspLeafNum = -bspNode->children[ i ] - 1;
386 newNode = AllocTraceNode();
387 traceNodes[ nodeNum ].children[ i ] = newNode;
388 /* have to do this separately, as gcc first executes LHS, then RHS, and if a realloc took place, this fails */
390 if ( bspLeafs[ bspLeafNum ].cluster == -1 ) {
391 traceNodes[ traceNodes[ nodeNum ].children[ i ] ].type = TRACE_LEAF_SOLID;
398 newNode = SetupTraceNodes_r( bspNode->children[ i ] );
399 traceNodes[ nodeNum ].children[ i ] = newNode;
402 if ( traceNodes[ nodeNum ].children[ i ] == 0 ) {
403 Error( "Invalid tracenode allocated" );
407 /* return node number */
414 ClipTraceWinding() - ydnar
415 clips a trace winding against a plane into one or two parts
418 #define TW_ON_EPSILON 0.25f
420 void ClipTraceWinding( traceWinding_t *tw, vec4_t plane, traceWinding_t *front, traceWinding_t *back ){
422 int sides[ MAX_TW_VERTS ], counts[ 3 ] = { 0, 0, 0 };
423 float dists[ MAX_TW_VERTS ];
425 traceVert_t *a, *b, mid;
428 /* clear front and back */
432 /* classify points */
433 for ( i = 0; i < tw->numVerts; i++ )
435 dists[ i ] = DotProduct( tw->v[ i ].xyz, plane ) - plane[ 3 ];
436 if ( dists[ i ] < -TW_ON_EPSILON ) {
437 sides[ i ] = SIDE_BACK;
439 else if ( dists[ i ] > TW_ON_EPSILON ) {
440 sides[ i ] = SIDE_FRONT;
443 sides[ i ] = SIDE_ON;
445 counts[ sides[ i ] ]++;
448 /* entirely on front? */
449 if ( counts[ SIDE_BACK ] == 0 ) {
450 memcpy( front, tw, sizeof( *front ) );
453 /* entirely on back? */
454 else if ( counts[ SIDE_FRONT ] == 0 ) {
455 memcpy( back, tw, sizeof( *back ) );
458 /* straddles the plane */
461 /* setup front and back */
462 memcpy( front, tw, sizeof( *front ) );
464 memcpy( back, tw, sizeof( *back ) );
467 /* split the winding */
468 for ( i = 0; i < tw->numVerts; i++ )
471 j = ( i + 1 ) % tw->numVerts;
477 /* handle points on the splitting plane */
478 switch ( sides[ i ] )
481 if ( front->numVerts >= MAX_TW_VERTS ) {
482 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
484 front->v[ front->numVerts++ ] = *a;
488 if ( back->numVerts >= MAX_TW_VERTS ) {
489 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
491 back->v[ back->numVerts++ ] = *a;
495 if ( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS ) {
496 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
498 front->v[ front->numVerts++ ] = *a;
499 back->v[ back->numVerts++ ] = *a;
503 /* check next point to see if we need to split the edge */
504 if ( sides[ j ] == SIDE_ON || sides[ j ] == sides[ i ] ) {
509 if ( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS ) {
510 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 ];
521 else if ( plane[ k ] == -1.0f ) {
522 mid.xyz[ k ] = -plane[ 3 ];
525 mid.xyz[ k ] = a->xyz[ k ] + frac * ( b->xyz[ k ] - a->xyz[ k ] );
528 /* set texture coordinates */
529 mid.st[ 0 ] = a->st[ 0 ] + frac * ( b->st[ 0 ] - a->st[ 0 ] );
530 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 FilterTraceWindingIntoNodes_r() - ydnar
543 filters a trace winding into the raytracing tree
546 static void FilterTraceWindingIntoNodes_r( traceWinding_t *tw, int nodeNum ){
548 vec4_t plane1, plane2, reverse;
550 traceWinding_t front, back;
553 /* don't filter if passed a bogus node (solid, etc) */
554 if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
559 node = &traceNodes[ nodeNum ];
561 /* is this a decision node? */
562 if ( node->type >= 0 ) {
563 /* create winding plane if necessary, filtering out bogus windings as well */
564 if ( nodeNum == headNodeNum ) {
565 if ( !PlaneFromPoints( tw->plane, tw->v[ 0 ].xyz, tw->v[ 1 ].xyz, tw->v[ 2 ].xyz ) ) {
570 /* validate the node */
571 if ( node->children[ 0 ] == 0 || node->children[ 1 ] == 0 ) {
572 Error( "Invalid tracenode: %d", nodeNum );
576 Vector4Copy( node->plane, plane1 );
578 /* get winding plane */
579 Vector4Copy( tw->plane, plane2 );
581 /* invert surface plane */
582 VectorSubtract( vec3_origin, plane2, reverse );
583 reverse[ 3 ] = -plane2[ 3 ];
586 if ( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f ) {
587 FilterTraceWindingIntoNodes_r( tw, node->children[ 0 ] );
592 if ( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f ) {
593 FilterTraceWindingIntoNodes_r( tw, node->children[ 1 ] );
597 /* clip the winding by node plane */
598 ClipTraceWinding( tw, plane1, &front, &back );
600 /* filter by node plane */
601 if ( front.numVerts >= 3 ) {
602 FilterTraceWindingIntoNodes_r( &front, node->children[ 0 ] );
604 if ( back.numVerts >= 3 ) {
605 FilterTraceWindingIntoNodes_r( &back, node->children[ 1 ] );
608 /* return to caller */
612 /* add winding to leaf node */
613 num = AddTraceWinding( tw );
614 AddItemToTraceNode( node, num );
620 SubdivideTraceNode_r() - ydnar
621 recursively subdivides a tracing node until it meets certain size and complexity criteria
624 static void SubdivideTraceNode_r( int nodeNum, int depth ){
625 int i, j, count, num, frontNum, backNum, type;
629 traceNode_t *node, *frontNode, *backNode;
630 traceWinding_t *tw, front, back;
634 if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
639 node = &traceNodes[ nodeNum ];
641 /* runaway recursion check */
642 if ( depth >= MAX_TRACE_DEPTH ) {
643 //% Sys_Printf( "Depth: (%d items)\n", node->numItems );
649 /* is this a decision node? */
650 if ( node->type >= 0 ) {
651 /* subdivide children */
652 frontNum = node->children[ 0 ];
653 backNum = node->children[ 1 ];
654 SubdivideTraceNode_r( frontNum, depth );
655 SubdivideTraceNode_r( backNum, depth );
660 ClearBounds( node->mins, node->maxs );
661 VectorClear( average );
663 for ( i = 0; i < node->numItems; i++ )
666 tw = &traceWindings[ node->items[ i ] ];
669 for ( j = 0; j < tw->numVerts; j++ )
671 AddPointToBounds( tw->v[ j ].xyz, node->mins, node->maxs );
672 average[ 0 ] += tw->v[ j ].xyz[ 0 ];
673 average[ 1 ] += tw->v[ j ].xyz[ 1 ];
674 average[ 2 ] += tw->v[ j ].xyz[ 2 ];
679 /* check triangle limit */
680 //% if( node->numItems <= MAX_NODE_ITEMS )
681 if ( ( count - ( node->numItems * 2 ) ) < MAX_NODE_TRIANGLES ) {
682 //% Sys_Printf( "Limit: (%d triangles)\n", (count - (node->numItems * 2)) );
687 /* the largest dimension of the bounding box will be the split axis */
688 VectorSubtract( node->maxs, node->mins, size );
689 if ( size[ 0 ] >= size[ 1 ] && size[ 0 ] >= size[ 2 ] ) {
692 else if ( size[ 1 ] >= size[ 0 ] && size[ 1 ] >= size[ 2 ] ) {
699 /* don't split small nodes */
700 if ( size[ type ] <= MIN_NODE_SIZE ) {
701 //% Sys_Printf( "Limit: %f %f %f (%d items)\n", size[ 0 ], size[ 1 ], size[ 2 ], node->numItems );
706 /* set max trace depth */
707 if ( depth > maxTraceDepth ) {
708 maxTraceDepth = depth;
711 /* snap the average */
712 dist = floor( average[ type ] / count );
715 if ( dist <= node->mins[ type ] || dist >= node->maxs[ type ] ) {
716 dist = floor( 0.5f * ( node->mins[ type ] + node->maxs[ type ] ) );
719 /* allocate child nodes */
720 frontNum = AllocTraceNode();
721 backNum = AllocTraceNode();
724 node = &traceNodes[ nodeNum ];
725 frontNode = &traceNodes[ frontNum ];
726 backNode = &traceNodes[ backNum ];
728 /* attach children */
730 node->plane[ type ] = 1.0f;
731 node->plane[ 3 ] = dist;
732 node->children[ 0 ] = frontNum;
733 node->children[ 1 ] = backNum;
735 /* setup front node */
736 frontNode->maxItems = ( node->maxItems >> 1 );
737 frontNode->items = safe_malloc( frontNode->maxItems * sizeof( *frontNode->items ) );
739 /* setup back node */
740 backNode->maxItems = ( node->maxItems >> 1 );
741 backNode->items = safe_malloc( backNode->maxItems * sizeof( *backNode->items ) );
743 /* filter windings into child nodes */
744 for ( i = 0; i < node->numItems; i++ )
747 tw = &traceWindings[ node->items[ i ] ];
749 /* clip the winding by the new split plane */
750 ClipTraceWinding( tw, node->plane, &front, &back );
752 /* kill the existing winding */
753 if ( front.numVerts >= 3 || back.numVerts >= 3 ) {
754 deadWinding = node->items[ i ];
757 /* add front winding */
758 if ( front.numVerts >= 3 ) {
759 num = AddTraceWinding( &front );
760 AddItemToTraceNode( frontNode, num );
763 /* add back winding */
764 if ( back.numVerts >= 3 ) {
765 num = AddTraceWinding( &back );
766 AddItemToTraceNode( backNode, num );
770 /* free original node winding list */
777 if ( frontNode->numItems <= 0 ) {
778 frontNode->maxItems = 0;
779 free( frontNode->items );
780 frontNode->items = NULL;
783 if ( backNode->numItems <= 0 ) {
784 backNode->maxItems = 0;
785 free( backNode->items );
786 backNode->items = NULL;
789 /* subdivide children */
790 SubdivideTraceNode_r( frontNum, depth );
791 SubdivideTraceNode_r( backNum, depth );
797 TriangulateTraceNode_r()
798 optimizes the tracing data by changing trace windings into triangles
801 static int TriangulateTraceNode_r( int nodeNum ){
802 int i, j, num, frontNum, backNum, numWindings, *windings;
809 if ( nodeNum < 0 || nodeNum >= numTraceNodes ) {
814 node = &traceNodes[ nodeNum ];
816 /* is this a decision node? */
817 if ( node->type >= 0 ) {
818 /* triangulate children */
819 frontNum = node->children[ 0 ];
820 backNum = node->children[ 1 ];
821 node->numItems = TriangulateTraceNode_r( frontNum );
822 node->numItems += TriangulateTraceNode_r( backNum );
823 return node->numItems;
827 if ( node->numItems == 0 ) {
829 if ( node->items != NULL ) {
832 return node->numItems;
835 /* store off winding data */
836 numWindings = node->numItems;
837 windings = node->items;
841 node->maxItems = numWindings * 2;
842 node->items = safe_malloc( node->maxItems * sizeof( tt ) );
844 /* walk winding list */
845 for ( i = 0; i < numWindings; i++ )
848 tw = &traceWindings[ windings[ i ] ];
851 tt.infoNum = tw->infoNum;
852 tt.v[ 0 ] = tw->v[ 0 ];
854 /* walk vertex list */
855 for ( j = 1; j + 1 < tw->numVerts; j++ )
858 tt.v[ 1 ] = tw->v[ j ];
859 tt.v[ 2 ] = tw->v[ j + 1 ];
861 /* find vectors for two edges sharing the first vert */
862 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
863 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
865 /* add it to the node */
866 num = AddTraceTriangle( &tt );
867 AddItemToTraceNode( node, num );
872 if ( windings != NULL ) {
876 /* return item count */
877 return node->numItems;
882 /* -------------------------------------------------------------------------------
884 shadow casting item setup (triangles, patches, entities)
886 ------------------------------------------------------------------------------- */
889 PopulateWithBSPModel() - ydnar
890 filters a bsp model's surfaces into the raytracing tree
893 static void PopulateWithBSPModel( bspModel_t *model, m4x4_t transform ){
894 int i, j, x, y, pw[ 5 ], r, nodeNum;
895 bspDrawSurface_t *ds;
897 bspDrawVert_t *verts;
899 mesh_t srcMesh, *mesh, *subdivided;
905 if ( model == NULL || transform == NULL ) {
909 /* walk the list of surfaces in this model and fill out the info structs */
910 for ( i = 0; i < model->numBSPSurfaces; i++ )
912 /* get surface and info */
913 ds = &bspDrawSurfaces[ model->firstBSPSurface + i ];
914 info = &surfaceInfos[ model->firstBSPSurface + i ];
915 if ( info->si == NULL ) {
920 if ( !info->castShadows ) {
925 if ( ds->surfaceType == MST_PATCH && patchShadows == qfalse ) {
929 /* some surfaces in the bsp might have been tagged as nodraw, with a bogus shader */
930 if ( ( bspShaders[ ds->shaderNum ].contentFlags & noDrawContentFlags ) ||
931 ( bspShaders[ ds->shaderNum ].surfaceFlags & noDrawSurfaceFlags ) ) {
935 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
936 if ( ( info->si->compileFlags & C_NODRAW ) ) {
939 if ( ( info->si->compileFlags & C_TRANSLUCENT ) &&
940 !( info->si->compileFlags & C_ALPHASHADOW ) &&
941 !( info->si->compileFlags & C_LIGHTFILTER ) ) {
945 /* setup trace info */
947 ti.castShadows = info->castShadows;
948 ti.surfaceNum = model->firstBSPBrush + i;
949 ti.skipGrid = ( ds->surfaceType == MST_PATCH );
951 /* choose which node (normal or skybox) */
952 if ( info->parentSurfaceNum >= 0 ) {
953 nodeNum = skyboxNodeNum;
955 /* sky surfaces in portal skies are ignored */
956 if ( info->si->compileFlags & C_SKY ) {
961 nodeNum = headNodeNum;
964 /* setup trace winding */
965 memset( &tw, 0, sizeof( tw ) );
966 tw.infoNum = AddTraceInfo( &ti );
970 switch ( ds->surfaceType )
974 /* subdivide the surface */
975 srcMesh.width = ds->patchWidth;
976 srcMesh.height = ds->patchHeight;
977 srcMesh.verts = &bspDrawVerts[ ds->firstVert ];
978 //% subdivided = SubdivideMesh( srcMesh, 8, 512 );
979 subdivided = SubdivideMesh2( srcMesh, info->patchIterations );
981 /* fit it to the curve and remove colinear verts on rows/columns */
982 PutMeshOnCurve( *subdivided );
983 mesh = RemoveLinearMeshColumnsRows( subdivided );
984 FreeMesh( subdivided );
989 /* subdivide each quad to place the models */
990 for ( y = 0; y < ( mesh->height - 1 ); y++ )
992 for ( x = 0; x < ( mesh->width - 1 ); x++ )
995 pw[ 0 ] = x + ( y * mesh->width );
996 pw[ 1 ] = x + ( ( y + 1 ) * mesh->width );
997 pw[ 2 ] = x + 1 + ( ( y + 1 ) * mesh->width );
998 pw[ 3 ] = x + 1 + ( y * mesh->width );
999 pw[ 4 ] = x + ( y * mesh->width ); /* same as pw[ 0 ] */
1004 /* make first triangle */
1005 VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
1006 Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
1007 VectorCopy( verts[ pw[ r + 1 ] ].xyz, tw.v[ 1 ].xyz );
1008 Vector2Copy( verts[ pw[ r + 1 ] ].st, tw.v[ 1 ].st );
1009 VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 2 ].xyz );
1010 Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 2 ].st );
1011 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1012 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1013 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1014 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1016 /* make second 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 + 2 ] ].xyz, tw.v[ 1 ].xyz );
1020 Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 1 ].st );
1021 VectorCopy( verts[ pw[ r + 3 ] ].xyz, tw.v[ 2 ].xyz );
1022 Vector2Copy( verts[ pw[ r + 3 ] ].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 );
1030 /* free the subdivided mesh */
1034 /* handle triangle surfaces */
1035 case MST_TRIANGLE_SOUP:
1037 /* set verts and indexes */
1038 verts = &bspDrawVerts[ ds->firstVert ];
1039 indexes = &bspDrawIndexes[ ds->firstIndex ];
1041 /* walk the triangle list */
1042 for ( j = 0; j < ds->numIndexes; j += 3 )
1044 VectorCopy( verts[ indexes[ j ] ].xyz, tw.v[ 0 ].xyz );
1045 Vector2Copy( verts[ indexes[ j ] ].st, tw.v[ 0 ].st );
1046 VectorCopy( verts[ indexes[ j + 1 ] ].xyz, tw.v[ 1 ].xyz );
1047 Vector2Copy( verts[ indexes[ j + 1 ] ].st, tw.v[ 1 ].st );
1048 VectorCopy( verts[ indexes[ j + 2 ] ].xyz, tw.v[ 2 ].xyz );
1049 Vector2Copy( verts[ indexes[ j + 2 ] ].st, tw.v[ 2 ].st );
1050 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1051 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1052 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1053 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1057 /* other surface types do not cast shadows */
1067 PopulateWithPicoModel() - ydnar
1068 filters a picomodel's surfaces into the raytracing tree
1071 static void PopulateWithPicoModel( int castShadows, picoModel_t *model, m4x4_t transform ){
1072 int i, j, k, numSurfaces, numIndexes;
1073 picoSurface_t *surface;
1074 picoShader_t *shader;
1075 picoVec_t *xyz, *st;
1076 picoIndex_t *indexes;
1082 if ( model == NULL || transform == NULL ) {
1087 numSurfaces = PicoGetModelNumSurfaces( model );
1089 /* walk the list of surfaces in this model and fill out the info structs */
1090 for ( i = 0; i < numSurfaces; i++ )
1093 surface = PicoGetModelSurface( model, i );
1094 if ( surface == NULL ) {
1098 /* only handle triangle surfaces initially (fixme: support patches) */
1099 if ( PicoGetSurfaceType( surface ) != PICO_TRIANGLES ) {
1103 /* get shader (fixme: support shader remapping) */
1104 shader = PicoGetSurfaceShader( surface );
1105 if ( shader == NULL ) {
1108 ti.si = ShaderInfoForShaderNull( PicoGetShaderName( shader ) );
1109 if ( ti.si == NULL ) {
1113 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
1114 if ( ( ti.si->compileFlags & C_NODRAW ) ) {
1117 if ( ( ti.si->compileFlags & C_TRANSLUCENT ) &&
1118 !( ti.si->compileFlags & C_ALPHASHADOW ) &&
1119 !( ti.si->compileFlags & C_LIGHTFILTER ) ) {
1123 /* setup trace info */
1124 ti.castShadows = castShadows;
1126 ti.skipGrid = qtrue; // also ignore picomodels when skipping patches
1128 /* setup trace winding */
1129 memset( &tw, 0, sizeof( tw ) );
1130 tw.infoNum = AddTraceInfo( &ti );
1134 numIndexes = PicoGetSurfaceNumIndexes( surface );
1135 indexes = PicoGetSurfaceIndexes( surface, 0 );
1137 /* walk the triangle list */
1138 for ( j = 0; j < numIndexes; j += 3, indexes += 3 )
1140 for ( k = 0; k < 3; k++ )
1142 xyz = PicoGetSurfaceXYZ( surface, indexes[ k ] );
1143 st = PicoGetSurfaceST( surface, 0, indexes[ k ] );
1144 VectorCopy( xyz, tw.v[ k ].xyz );
1145 Vector2Copy( st, tw.v[ k ].st );
1146 m4x4_transform_point( transform, tw.v[ k ].xyz );
1148 FilterTraceWindingIntoNodes_r( &tw, headNodeNum );
1156 PopulateTraceNodes() - ydnar
1157 fills the raytracing tree with world and entity occluders
1160 static void PopulateTraceNodes( void ){
1161 int i, m, frame, castShadows;
1166 vec3_t origin, scale, angles;
1170 /* add worldspawn triangles */
1171 m4x4_identity( transform );
1172 PopulateWithBSPModel( &bspModels[ 0 ], transform );
1174 /* walk each entity list */
1175 for ( i = 1; i < numEntities; i++ )
1180 /* get shadow flags */
1181 castShadows = ENTITY_CAST_SHADOWS;
1182 GetEntityShadowFlags( e, NULL, &castShadows, NULL );
1185 if ( !castShadows ) {
1189 /* get entity origin */
1190 GetVectorForKey( e, "origin", origin );
1193 scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = 1.0f;
1194 temp = FloatForKey( e, "modelscale" );
1195 if ( temp != 0.0f ) {
1196 scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = temp;
1198 value = ValueForKey( e, "modelscale_vec" );
1199 if ( value[ 0 ] != '\0' ) {
1200 sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );
1203 /* get "angle" (yaw) or "angles" (pitch yaw roll) */
1204 angles[ 0 ] = angles[ 1 ] = angles[ 2 ] = 0.0f;
1205 angles[ 2 ] = FloatForKey( e, "angle" );
1206 value = ValueForKey( e, "angles" );
1207 if ( value[ 0 ] != '\0' ) {
1208 sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
1211 /* set transform matrix (thanks spog) */
1212 m4x4_identity( transform );
1213 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
1215 /* hack: Stable-1_2 and trunk have differing row/column major matrix order
1216 this transpose is necessary with Stable-1_2
1217 uncomment the following line with old m4x4_t (non 1.3/spog_branch) code */
1218 //% m4x4_transpose( transform );
1221 value = ValueForKey( e, "model" );
1223 /* switch on model type */
1224 switch ( value[ 0 ] )
1232 m = atoi( &value[ 1 ] );
1233 if ( m <= 0 || m >= numBSPModels ) {
1236 PopulateWithBSPModel( &bspModels[ m ], transform );
1239 /* external model */
1242 if ( strcmp( "", ValueForKey( e, "_frame" ) ) ) {
1243 frame = IntForKey( e, "_frame" );
1245 else if ( strcmp( "", ValueForKey( e, "frame" ) ) ) {
1246 frame = IntForKey( e, "frame" );
1248 model = LoadModel( value, frame );
1249 if ( model == NULL ) {
1252 PopulateWithPicoModel( castShadows, model, transform );
1257 value = ValueForKey( e, "model2" );
1259 /* switch on model type */
1260 switch ( value[ 0 ] )
1268 m = atoi( &value[ 1 ] );
1269 if ( m <= 0 || m >= numBSPModels ) {
1272 PopulateWithBSPModel( &bspModels[ m ], transform );
1275 /* external model */
1277 frame = IntForKey( e, "_frame2" );
1278 model = LoadModel( value, frame );
1279 if ( model == NULL ) {
1282 PopulateWithPicoModel( castShadows, model, transform );
1291 /* -------------------------------------------------------------------------------
1293 trace initialization
1295 ------------------------------------------------------------------------------- */
1298 SetupTraceNodes() - ydnar
1299 creates a balanced bsp with axis-aligned splits for efficient raytracing
1302 void SetupTraceNodes( void ){
1304 Sys_FPrintf( SYS_VRB, "--- SetupTraceNodes ---\n" );
1306 /* find nodraw bit */
1307 noDrawContentFlags = noDrawSurfaceFlags = noDrawCompileFlags = 0;
1308 ApplySurfaceParm( "nodraw", &noDrawContentFlags, &noDrawSurfaceFlags, &noDrawCompileFlags );
1310 /* create the baseline raytracing tree from the bsp tree */
1311 headNodeNum = SetupTraceNodes_r( 0 );
1313 /* create outside node for skybox surfaces */
1314 skyboxNodeNum = AllocTraceNode();
1316 /* populate the tree with triangles from the world and shadow casting entities */
1317 PopulateTraceNodes();
1319 /* create the raytracing bsp */
1320 if ( loMem == qfalse ) {
1321 SubdivideTraceNode_r( headNodeNum, 0 );
1322 SubdivideTraceNode_r( skyboxNodeNum, 0 );
1325 /* create triangles from the trace windings */
1326 TriangulateTraceNode_r( headNodeNum );
1327 TriangulateTraceNode_r( skyboxNodeNum );
1329 /* emit some stats */
1330 //% Sys_FPrintf( SYS_VRB, "%9d original triangles\n", numOriginalTriangles );
1331 Sys_FPrintf( SYS_VRB, "%9d trace windings (%.2fMB)\n", numTraceWindings, (float) ( numTraceWindings * sizeof( *traceWindings ) ) / ( 1024.0f * 1024.0f ) );
1332 Sys_FPrintf( SYS_VRB, "%9d trace triangles (%.2fMB)\n", numTraceTriangles, (float) ( numTraceTriangles * sizeof( *traceTriangles ) ) / ( 1024.0f * 1024.0f ) );
1333 Sys_FPrintf( SYS_VRB, "%9d trace nodes (%.2fMB)\n", numTraceNodes, (float) ( numTraceNodes * sizeof( *traceNodes ) ) / ( 1024.0f * 1024.0f ) );
1334 Sys_FPrintf( SYS_VRB, "%9d leaf nodes (%.2fMB)\n", numTraceLeafNodes, (float) ( numTraceLeafNodes * sizeof( *traceNodes ) ) / ( 1024.0f * 1024.0f ) );
1335 //% Sys_FPrintf( SYS_VRB, "%9d average triangles per leaf node\n", numTraceTriangles / numTraceLeafNodes );
1336 Sys_FPrintf( SYS_VRB, "%9d average windings per leaf node\n", numTraceWindings / ( numTraceLeafNodes + 1 ) );
1337 Sys_FPrintf( SYS_VRB, "%9d max trace depth\n", maxTraceDepth );
1339 /* free trace windings */
1340 free( traceWindings );
1341 numTraceWindings = 0;
1342 maxTraceWindings = 0;
1345 /* debug code: write out trace triangles to an alias obj file */
1350 char filename[ 1024 ];
1355 strcpy( filename, source );
1356 StripExtension( filename );
1357 strcat( filename, ".lin" );
1358 Sys_Printf( "Opening light trace file %s...\n", filename );
1359 file = fopen( filename, "w" );
1360 if ( file == NULL ) {
1361 Error( "Error opening %s for writing", filename );
1364 /* walk node list */
1365 for ( i = 0; i < numTraceWindings; i++ )
1367 tw = &traceWindings[ i ];
1368 for ( j = 0; j < tw->numVerts + 1; j++ )
1369 fprintf( file, "%f %f %f\n",
1370 tw->v[ j % tw->numVerts ].xyz[ 0 ], tw->v[ j % tw->numVerts ].xyz[ 1 ], tw->v[ j % tw->numVerts ].xyz[ 2 ] );
1381 /* -------------------------------------------------------------------------------
1385 ------------------------------------------------------------------------------- */
1389 based on code written by william 'spog' joseph
1390 based on code originally written by tomas moller and ben trumbore, journal of graphics tools, 2(1):21-28, 1997
1393 #define BARY_EPSILON 0.01f
1394 #define ASLF_EPSILON 0.0001f /* so to not get double shadows */
1395 #define COPLANAR_EPSILON 0.25f //% 0.000001f
1396 #define NEAR_SHADOW_EPSILON 1.5f //% 1.25f
1397 #define SELF_SHADOW_EPSILON 0.5f
1399 qboolean TraceTriangle( traceInfo_t *ti, traceTriangle_t *tt, trace_t *trace ){
1401 float tvec[ 3 ], pvec[ 3 ], qvec[ 3 ];
1402 float det, invDet, depth;
1403 float u, v, w, s, t;
1410 /* don't double-trace against sky */
1412 if ( trace->compileFlags & si->compileFlags & C_SKY ) {
1416 /* receive shadows from worldspawn group only */
1417 if ( trace->recvShadows == 1 ) {
1418 if ( ti->castShadows != 1 ) {
1423 /* receive shadows from same group and worldspawn group */
1424 else if ( trace->recvShadows > 1 ) {
1425 if ( ti->castShadows != 1 && abs( ti->castShadows ) != abs( trace->recvShadows ) ) {
1428 //% Sys_Printf( "%d:%d ", tt->castShadows, trace->recvShadows );
1431 /* receive shadows from the same group only (< 0) */
1434 if ( abs( ti->castShadows ) != abs( trace->recvShadows ) ) {
1439 /* skip patches when doing the grid (FIXME this is an ugly hack) */
1441 if ( ti->skipGrid ) {
1446 /* begin calculating determinant - also used to calculate u parameter */
1447 CrossProduct( trace->direction, tt->edge2, pvec );
1449 /* if determinant is near zero, trace lies in plane of triangle */
1450 det = DotProduct( tt->edge1, pvec );
1452 /* the non-culling branch */
1453 if ( fabs( det ) < COPLANAR_EPSILON ) {
1456 invDet = 1.0f / det;
1458 /* calculate distance from first vertex to ray origin */
1459 VectorSubtract( trace->origin, tt->v[ 0 ].xyz, tvec );
1461 /* calculate u parameter and test bounds */
1462 u = DotProduct( tvec, pvec ) * invDet;
1463 if ( u < -BARY_EPSILON || u > ( 1.0f + BARY_EPSILON ) ) {
1467 /* prepare to test v parameter */
1468 CrossProduct( tvec, tt->edge1, qvec );
1470 /* calculate v parameter and test bounds */
1471 v = DotProduct( trace->direction, qvec ) * invDet;
1472 if ( v < -BARY_EPSILON || ( u + v ) > ( 1.0f + BARY_EPSILON ) ) {
1476 /* calculate t (depth) */
1477 depth = DotProduct( tt->edge2, qvec ) * invDet;
1478 if ( depth <= trace->inhibitRadius || depth >= trace->distance ) {
1482 /* if hitpoint is really close to trace origin (sample point), then check for self-shadowing */
1483 if ( depth <= SELF_SHADOW_EPSILON ) {
1484 /* don't self-shadow */
1485 for ( i = 0; i < trace->numSurfaces; i++ )
1487 if ( ti->surfaceNum == trace->surfaces[ i ] ) {
1493 /* stack compile flags */
1494 trace->compileFlags |= si->compileFlags;
1496 /* don't trace against sky */
1497 if ( si->compileFlags & C_SKY ) {
1501 /* most surfaces are completely opaque */
1502 if ( !( si->compileFlags & ( C_ALPHASHADOW | C_LIGHTFILTER ) ) ||
1503 si->lightImage == NULL || si->lightImage->pixels == NULL ) {
1504 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1505 VectorClear( trace->color );
1506 trace->opaque = qtrue;
1510 /* force subsampling because the lighting is texture dependent */
1511 trace->forceSubsampling = 1.0;
1513 /* try to avoid double shadows near triangle seams */
1514 if ( u < -ASLF_EPSILON || u > ( 1.0f + ASLF_EPSILON ) ||
1515 v < -ASLF_EPSILON || ( u + v ) > ( 1.0f + ASLF_EPSILON ) ) {
1519 /* calculate w parameter */
1520 w = 1.0f - ( u + v );
1522 /* calculate st from uvw (barycentric) coordinates */
1523 s = w * tt->v[ 0 ].st[ 0 ] + u * tt->v[ 1 ].st[ 0 ] + v * tt->v[ 2 ].st[ 0 ];
1524 t = w * tt->v[ 0 ].st[ 1 ] + u * tt->v[ 1 ].st[ 1 ] + v * tt->v[ 2 ].st[ 1 ];
1527 is = s * si->lightImage->width;
1528 it = t * si->lightImage->height;
1532 if ( is > si->lightImage->width - 1 ) {
1533 is = si->lightImage->width - 1;
1538 if ( it > si->lightImage->height - 1 ) {
1539 it = si->lightImage->height - 1;
1543 pixel = si->lightImage->pixels + 4 * ( it * si->lightImage->width + is );
1545 /* ydnar: color filter */
1546 if ( si->compileFlags & C_LIGHTFILTER ) {
1547 /* filter by texture color */
1548 trace->color[ 0 ] *= ( ( 1.0f / 255.0f ) * pixel[ 0 ] );
1549 trace->color[ 1 ] *= ( ( 1.0f / 255.0f ) * pixel[ 1 ] );
1550 trace->color[ 2 ] *= ( ( 1.0f / 255.0f ) * pixel[ 2 ] );
1553 /* ydnar: alpha filter */
1554 if ( si->compileFlags & C_ALPHASHADOW ) {
1555 /* filter by inverse texture alpha */
1556 shadow = ( 1.0f / 255.0f ) * ( 255 - pixel[ 3 ] );
1557 trace->color[ 0 ] *= shadow;
1558 trace->color[ 1 ] *= shadow;
1559 trace->color[ 2 ] *= shadow;
1562 /* check filter for opaque */
1563 if ( trace->color[ 0 ] <= 0.001f && trace->color[ 1 ] <= 0.001f && trace->color[ 2 ] <= 0.001f ) {
1564 VectorClear( trace->color );
1565 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1566 trace->opaque = qtrue;
1570 /* continue tracing */
1577 TraceWinding() - ydnar
1581 qboolean TraceWinding( traceWinding_t *tw, trace_t *trace ){
1587 tt.infoNum = tw->infoNum;
1588 tt.v[ 0 ] = tw->v[ 0 ];
1590 /* walk vertex list */
1591 for ( i = 1; i + 1 < tw->numVerts; i++ )
1594 tt.v[ 1 ] = tw->v[ i ];
1595 tt.v[ 2 ] = tw->v[ i + 1 ];
1597 /* find vectors for two edges sharing the first vert */
1598 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
1599 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
1602 if ( TraceTriangle( &traceInfos[ tt.infoNum ], &tt, trace ) ) {
1616 returns qtrue if something is hit and tracing can stop
1618 SmileTheory: made half-iterative
1621 #define TRACELINE_R_HALF_ITERATIVE 1
1623 #if TRACELINE_R_HALF_ITERATIVE
1624 static qboolean TraceLine_r( int nodeNum, const vec3_t start, const vec3_t end, trace_t *trace )
1626 static qboolean TraceLine_r( int nodeNum, const vec3_t origin, const vec3_t end, trace_t *trace )
1631 float front, back, frac;
1635 #if TRACELINE_R_HALF_ITERATIVE
1636 VectorCopy( start, origin );
1641 /* bogus node number means solid, end tracing unless testing all */
1642 if ( nodeNum < 0 ) {
1643 VectorCopy( origin, trace->hit );
1644 trace->passSolid = qtrue;
1649 node = &traceNodes[ nodeNum ];
1652 if ( node->type == TRACE_LEAF_SOLID ) {
1653 VectorCopy( origin, trace->hit );
1654 trace->passSolid = qtrue;
1659 if ( node->type < 0 ) {
1660 /* note leaf and return */
1661 if ( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES ) {
1662 trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
1667 /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
1668 if ( trace->testAll && node->numItems == 0 ) {
1672 /* classify beginning and end points */
1673 switch ( node->type )
1676 front = origin[ 0 ] - node->plane[ 3 ];
1677 back = end[ 0 ] - node->plane[ 3 ];
1681 front = origin[ 1 ] - node->plane[ 3 ];
1682 back = end[ 1 ] - node->plane[ 3 ];
1686 front = origin[ 2 ] - node->plane[ 3 ];
1687 back = end[ 2 ] - node->plane[ 3 ];
1691 front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
1692 back = DotProduct( end, node->plane ) - node->plane[ 3 ];
1696 /* entirely in front side? */
1697 if ( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON ) {
1698 #if TRACELINE_R_HALF_ITERATIVE
1699 nodeNum = node->children[ 0 ];
1702 return TraceLine_r( node->children[ 0 ], origin, end, trace );
1706 /* entirely on back side? */
1707 if ( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON ) {
1708 #if TRACELINE_R_HALF_ITERATIVE
1709 nodeNum = node->children[ 1 ];
1712 return TraceLine_r( node->children[ 1 ], origin, end, trace );
1719 /* calculate intercept point */
1720 frac = front / ( front - back );
1721 mid[ 0 ] = origin[ 0 ] + ( end[ 0 ] - origin[ 0 ] ) * frac;
1722 mid[ 1 ] = origin[ 1 ] + ( end[ 1 ] - origin[ 1 ] ) * frac;
1723 mid[ 2 ] = origin[ 2 ] + ( end[ 2 ] - origin[ 2 ] ) * frac;
1725 /* fixme: check inhibit radius, then solid nodes and ignore */
1727 /* set trace hit here */
1728 //% VectorCopy( mid, trace->hit );
1730 /* trace first side */
1731 if ( TraceLine_r( node->children[ side ], origin, mid, trace ) ) {
1735 /* trace other side */
1736 #if TRACELINE_R_HALF_ITERATIVE
1737 nodeNum = node->children[ !side ];
1738 VectorCopy( mid, origin );
1740 return TraceLine_r( node->children[ !side ], mid, end, trace );
1749 rewrote this function a bit :)
1752 void TraceLine( trace_t *trace ){
1755 traceTriangle_t *tt;
1759 /* setup output (note: this code assumes the input data is completely filled out) */
1760 trace->passSolid = qfalse;
1761 trace->opaque = qfalse;
1762 trace->compileFlags = 0;
1763 trace->numTestNodes = 0;
1766 if ( !trace->recvShadows || !trace->testOcclusion || trace->distance <= 0.00001f ) {
1770 /* trace through nodes */
1771 TraceLine_r( headNodeNum, trace->origin, trace->end, trace );
1772 if ( trace->passSolid && !trace->testAll ) {
1773 trace->opaque = qtrue;
1777 /* skip surfaces? */
1782 /* testall means trace through sky */
1783 if ( trace->testAll && trace->numTestNodes < MAX_TRACE_TEST_NODES &&
1784 trace->compileFlags & C_SKY &&
1785 ( trace->numSurfaces == 0 || surfaceInfos[ trace->surfaces[ 0 ] ].childSurfaceNum < 0 ) ) {
1786 //% trace->testNodes[ trace->numTestNodes++ ] = skyboxNodeNum;
1787 TraceLine_r( skyboxNodeNum, trace->origin, trace->end, trace );
1790 /* walk node list */
1791 for ( i = 0; i < trace->numTestNodes; i++ )
1794 node = &traceNodes[ trace->testNodes[ i ] ];
1796 /* walk node item list */
1797 for ( j = 0; j < node->numItems; j++ )
1799 tt = &traceTriangles[ node->items[ j ] ];
1800 ti = &traceInfos[ tt->infoNum ];
1801 if ( TraceTriangle( ti, tt, trace ) ) {
1804 //% if( TraceWinding( &traceWindings[ node->items[ j ] ], trace ) )
1813 SetupTrace() - ydnar
1814 sets up certain trace values
1817 float SetupTrace( trace_t *trace ){
1818 VectorSubtract( trace->end, trace->origin, trace->displacement );
1819 trace->distance = VectorFastNormalize( trace->displacement, trace->direction );
1820 VectorCopy( trace->origin, trace->hit );
1821 return trace->distance;