+++ /dev/null
-/* -------------------------------------------------------------------------------
-
-Copyright (C) 1999-2007 id Software, Inc. and contributors.
-For a list of contributors, see the accompanying CONTRIBUTORS file.
-
-This file is part of GtkRadiant.
-
-GtkRadiant is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2 of the License, or
-(at your option) any later version.
-
-GtkRadiant is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GtkRadiant; if not, write to the Free Software
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
-
-----------------------------------------------------------------------------------
-
-This code has been altered significantly from its original form, to support
-several games based on the Quake III Arena engine, in the form of "Q3Map2."
-
-------------------------------------------------------------------------------- */
-
-
-
-/* marker */
-#define LIGHT_TRACE_C
-
-
-
-/* dependencies */
-#include "q3map2.h"
-
-
-/* dependencies */
-#include "q3map2.h"
-
-
-
-#define Vector2Copy( a, b ) ((b)[ 0 ] = (a)[ 0 ], (b)[ 1 ] = (a)[ 1 ])
-#define Vector4Copy( a, b ) ((b)[ 0 ] = (a)[ 0 ], (b)[ 1 ] = (a)[ 1 ], (b)[ 2 ] = (a)[ 2 ], (b)[ 3 ] = (a)[ 3 ])
-
-#define MAX_NODE_ITEMS 5
-#define MAX_NODE_TRIANGLES 5
-#define MAX_TRACE_DEPTH 32
-#define MIN_NODE_SIZE 32.0f
-
-#define GROW_TRACE_INFOS 32768 //% 4096
-#define GROW_TRACE_WINDINGS 65536 //% 32768
-#define GROW_TRACE_TRIANGLES 131072 //% 32768
-#define GROW_TRACE_NODES 16384 //% 16384
-#define GROW_NODE_ITEMS 16 //% 256
-
-#define MAX_TW_VERTS 24 // vortex: increased from 12 to 24 for ability co compile some insane maps with large curve count
-
-#define TRACE_ON_EPSILON 0.1f
-
-#define TRACE_LEAF -1
-#define TRACE_LEAF_SOLID -2
-
-typedef struct traceVert_s
-{
- vec3_t xyz;
- float st[ 2 ];
-}
-traceVert_t;
-
-typedef struct traceInfo_s
-{
- shaderInfo_t *si;
- int surfaceNum, castShadows, skipGrid;
-}
-traceInfo_t;
-
-typedef struct traceWinding_s
-{
- vec4_t plane;
- int infoNum, numVerts;
- traceVert_t v[ MAX_TW_VERTS ];
-}
-traceWinding_t;
-
-typedef struct traceTriangle_s
-{
- vec3_t edge1, edge2;
- int infoNum;
- traceVert_t v[ 3 ];
-}
-traceTriangle_t;
-
-typedef struct traceNode_s
-{
- int type;
- vec4_t plane;
- vec3_t mins, maxs;
- int children[ 2 ];
- int numItems, maxItems;
- int *items;
-}
-traceNode_t;
-
-
-int noDrawContentFlags, noDrawSurfaceFlags, noDrawCompileFlags;
-
-int numTraceInfos = 0, maxTraceInfos = 0, firstTraceInfo = 0;
-traceInfo_t *traceInfos = NULL;
-
-int numTraceWindings = 0, maxTraceWindings = 0, deadWinding = -1;
-traceWinding_t *traceWindings = NULL;
-
-int numTraceTriangles = 0, maxTraceTriangles = 0, deadTriangle = -1;
-traceTriangle_t *traceTriangles = NULL;
-
-int headNodeNum = 0, skyboxNodeNum = 0, maxTraceDepth = 0, numTraceLeafNodes = 0;
-int numTraceNodes = 0, maxTraceNodes = 0;
-traceNode_t *traceNodes = NULL;
-
-
-
-/* -------------------------------------------------------------------------------
-
-allocation and list management
-
-------------------------------------------------------------------------------- */
-
-/*
-AddTraceInfo() - ydnar
-adds a trace info structure to the pool
-*/
-
-static int AddTraceInfo( traceInfo_t *ti )
-{
- int num;
- void *temp;
-
-
- /* find an existing info */
- for( num = firstTraceInfo; num < numTraceInfos; num++ )
- {
- if( traceInfos[ num ].si == ti->si &&
- traceInfos[ num ].surfaceNum == ti->surfaceNum &&
- traceInfos[ num ].castShadows == ti->castShadows &&
- traceInfos[ num ].skipGrid == ti->skipGrid )
- return num;
- }
-
- /* enough space? */
- if( numTraceInfos >= maxTraceInfos )
- {
- /* allocate more room */
- maxTraceInfos += GROW_TRACE_INFOS;
- temp = safe_malloc( maxTraceInfos * sizeof( *traceInfos ) );
- if( traceInfos != NULL )
- {
- memcpy( temp, traceInfos, numTraceInfos * sizeof( *traceInfos ) );
- free( traceInfos );
- }
- traceInfos = (traceInfo_t*) temp;
- }
-
- /* add the info */
- memcpy( &traceInfos[ num ], ti, sizeof( *traceInfos ) );
- if( num == numTraceInfos )
- numTraceInfos++;
-
- /* return the ti number */
- return num;
-}
-
-
-
-/*
-AllocTraceNode() - ydnar
-allocates a new trace node
-*/
-
-static int AllocTraceNode( void )
-{
- traceNode_t *temp;
-
-
- /* enough space? */
- if( numTraceNodes >= maxTraceNodes )
- {
- /* reallocate more room */
- maxTraceNodes += GROW_TRACE_NODES;
- temp = safe_malloc( maxTraceNodes * sizeof( traceNode_t ) );
- if( traceNodes != NULL )
- {
- memcpy( temp, traceNodes, numTraceNodes * sizeof( traceNode_t ) );
- free( traceNodes );
- }
- traceNodes = temp;
- }
-
- /* add the node */
- memset( &traceNodes[ numTraceNodes ], 0, sizeof( traceNode_t ) );
- traceNodes[ numTraceNodes ].type = TRACE_LEAF;
- ClearBounds( traceNodes[ numTraceNodes ].mins, traceNodes[ numTraceNodes ].maxs );
-
- /* Sys_Printf("alloc node %d\n", numTraceNodes); */
-
- numTraceNodes++;
-
- /* return the count */
- return (numTraceNodes - 1);
-}
-
-
-
-/*
-AddTraceWinding() - ydnar
-adds a winding to the raytracing pool
-*/
-
-static int AddTraceWinding( traceWinding_t *tw )
-{
- int num;
- void *temp;
-
-
- /* check for a dead winding */
- if( deadWinding >= 0 && deadWinding < numTraceWindings )
- num = deadWinding;
- else
- {
- /* put winding at the end of the list */
- num = numTraceWindings;
-
- /* enough space? */
- if( numTraceWindings >= maxTraceWindings )
- {
- /* allocate more room */
- maxTraceWindings += GROW_TRACE_WINDINGS;
- temp = safe_malloc( maxTraceWindings * sizeof( *traceWindings ) );
- if( traceWindings != NULL )
- {
- memcpy( temp, traceWindings, numTraceWindings * sizeof( *traceWindings ) );
- free( traceWindings );
- }
- traceWindings = (traceWinding_t*) temp;
- }
- }
-
- /* add the winding */
- memcpy( &traceWindings[ num ], tw, sizeof( *traceWindings ) );
- if( num == numTraceWindings )
- numTraceWindings++;
- deadWinding = -1;
-
- /* return the winding number */
- return num;
-}
-
-
-
-/*
-AddTraceTriangle() - ydnar
-adds a triangle to the raytracing pool
-*/
-
-static int AddTraceTriangle( traceTriangle_t *tt )
-{
- int num;
- void *temp;
-
-
- /* check for a dead triangle */
- if( deadTriangle >= 0 && deadTriangle < numTraceTriangles )
- num = deadTriangle;
- else
- {
- /* put triangle at the end of the list */
- num = numTraceTriangles;
-
- /* enough space? */
- if( numTraceTriangles >= maxTraceTriangles )
- {
- /* allocate more room */
- maxTraceTriangles += GROW_TRACE_TRIANGLES;
- temp = safe_malloc( maxTraceTriangles * sizeof( *traceTriangles ) );
- if( traceTriangles != NULL )
- {
- memcpy( temp, traceTriangles, numTraceTriangles * sizeof( *traceTriangles ) );
- free( traceTriangles );
- }
- traceTriangles = (traceTriangle_t*) temp;
- }
- }
-
- /* find vectors for two edges sharing the first vert */
- VectorSubtract( tt->v[ 1 ].xyz, tt->v[ 0 ].xyz, tt->edge1 );
- VectorSubtract( tt->v[ 2 ].xyz, tt->v[ 0 ].xyz, tt->edge2 );
-
- /* add the triangle */
- memcpy( &traceTriangles[ num ], tt, sizeof( *traceTriangles ) );
- if( num == numTraceTriangles )
- numTraceTriangles++;
- deadTriangle = -1;
-
- /* return the triangle number */
- return num;
-}
-
-
-
-/*
-AddItemToTraceNode() - ydnar
-adds an item reference (winding or triangle) to a trace node
-*/
-
-static int AddItemToTraceNode( traceNode_t *node, int num )
-{
- void *temp;
-
-
- /* dummy check */
- if( num < 0 )
- return -1;
-
- /* enough space? */
- if( node->numItems >= node->maxItems )
- {
- /* allocate more room */
- if( node == traceNodes )
- node->maxItems *= 2;
- else
- node->maxItems += GROW_NODE_ITEMS;
- if( node->maxItems <= 0 )
- node->maxItems = GROW_NODE_ITEMS;
- temp = safe_malloc( node->maxItems * sizeof( *node->items ) );
- if( node->items != NULL )
- {
- memcpy( temp, node->items, node->numItems * sizeof( *node->items ) );
- free( node->items );
- }
- node->items = (int*) temp;
- }
-
- /* add the poly */
- node->items[ node->numItems ] = num;
- node->numItems++;
-
- /* return the count */
- return (node->numItems - 1);
-}
-
-
-
-
-/* -------------------------------------------------------------------------------
-
-trace node setup
-
-------------------------------------------------------------------------------- */
-
-/*
-SetupTraceNodes_r() - ydnar
-recursively create the initial trace node structure from the bsp tree
-*/
-
-static int SetupTraceNodes_r( int bspNodeNum )
-{
- int i, nodeNum, bspLeafNum, newNode;
- bspPlane_t *plane;
- bspNode_t *bspNode;
-
-
- /* get bsp node and plane */
- bspNode = &bspNodes[ bspNodeNum ];
- plane = &bspPlanes[ bspNode->planeNum ];
-
- /* allocate a new trace node */
- nodeNum = AllocTraceNode();
-
- /* setup trace node */
- traceNodes[ nodeNum ].type = PlaneTypeForNormal( plane->normal );
- VectorCopy( plane->normal, traceNodes[ nodeNum ].plane );
- traceNodes[ nodeNum ].plane[ 3 ] = plane->dist;
-
- /* setup children */
- for( i = 0; i < 2; i++ )
- {
- /* leafnode */
- if( bspNode->children[ i ] < 0 )
- {
- bspLeafNum = -bspNode->children[ i ] - 1;
-
- /* new code */
- newNode = AllocTraceNode();
- traceNodes[ nodeNum ].children[ i ] = newNode;
- /* have to do this separately, as gcc first executes LHS, then RHS, and if a realloc took place, this fails */
-
- if( bspLeafs[ bspLeafNum ].cluster == -1 )
- traceNodes[ traceNodes[ nodeNum ].children[ i ] ].type = TRACE_LEAF_SOLID;
- }
-
- /* normal node */
- else
- {
- newNode = SetupTraceNodes_r( bspNode->children[ i ] );
- traceNodes[ nodeNum ].children[ i ] = newNode;
- }
-
- if(traceNodes[ nodeNum ].children[ i ] == 0)
- Error( "Invalid tracenode allocated" );
- }
-
- /* Sys_Printf("node %d children: %d %d\n", nodeNum, traceNodes[ nodeNum ].children[0], traceNodes[ nodeNum ].children[1]); */
-
- /* return node number */
- return nodeNum;
-}
-
-
-
-/*
-ClipTraceWinding() - ydnar
-clips a trace winding against a plane into one or two parts
-*/
-
-#define TW_ON_EPSILON 0.25f
-
-void ClipTraceWinding( traceWinding_t *tw, vec4_t plane, traceWinding_t *front, traceWinding_t *back )
-{
- int i, j, k;
- int sides[ MAX_TW_VERTS ], counts[ 3 ] = { 0, 0, 0 };
- float dists[ MAX_TW_VERTS ];
- float frac;
- traceVert_t *a, *b, mid;
-
-
- /* clear front and back */
- front->numVerts = 0;
- back->numVerts = 0;
-
- /* classify points */
- for( i = 0; i < tw->numVerts; i++ )
- {
- dists[ i ] = DotProduct( tw->v[ i ].xyz, plane ) - plane[ 3 ];
- if( dists[ i ] < -TW_ON_EPSILON )
- sides[ i ] = SIDE_BACK;
- else if( dists[ i ] > TW_ON_EPSILON )
- sides[ i ] = SIDE_FRONT;
- else
- sides[ i ] = SIDE_ON;
- counts[ sides[ i ] ]++;
- }
-
- /* entirely on front? */
- if( counts[ SIDE_BACK ] == 0 )
- memcpy( front, tw, sizeof( *front ) );
-
- /* entirely on back? */
- else if( counts[ SIDE_FRONT ] == 0 )
- memcpy( back, tw, sizeof( *back ) );
-
- /* straddles the plane */
- else
- {
- /* setup front and back */
- memcpy( front, tw, sizeof( *front ) );
- front->numVerts = 0;
- memcpy( back, tw, sizeof( *back ) );
- back->numVerts = 0;
-
- /* split the winding */
- for( i = 0; i < tw->numVerts; i++ )
- {
- /* radix */
- j = (i + 1) % tw->numVerts;
-
- /* get verts */
- a = &tw->v[ i ];
- b = &tw->v[ j ];
-
- /* handle points on the splitting plane */
- switch( sides[ i ] )
- {
- case SIDE_FRONT:
- if( front->numVerts >= MAX_TW_VERTS )
- Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
- front->v[ front->numVerts++ ] = *a;
- break;
-
- case SIDE_BACK:
- if( back->numVerts >= MAX_TW_VERTS )
- Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
- back->v[ back->numVerts++ ] = *a;
- break;
-
- case SIDE_ON:
- if( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS )
- Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
- front->v[ front->numVerts++ ] = *a;
- back->v[ back->numVerts++ ] = *a;
- continue;
- }
-
- /* check next point to see if we need to split the edge */
- if( sides[ j ] == SIDE_ON || sides[ j ] == sides[ i ] )
- continue;
-
- /* check limit */
- if( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS )
- Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
-
- /* generate a split point */
- frac = dists[ i ] / (dists[ i ] - dists[ j ]);
- for( k = 0; k < 3; k++ )
- {
- /* minimize fp precision errors */
- if( plane[ k ] == 1.0f )
- mid.xyz[ k ] = plane[ 3 ];
- else if( plane[ k ] == -1.0f )
- mid.xyz[ k ] = -plane[ 3 ];
- else
- mid.xyz[ k ] = a->xyz[ k ] + frac * (b->xyz[ k ] - a->xyz[ k ]);
- }
- /* set texture coordinates */
- mid.st[ 0 ] = a->st[ 0 ] + frac * (b->st[ 0 ] - a->st[ 0 ]);
- mid.st[ 1 ] = a->st[ 1 ] + frac * (b->st[ 1 ] - a->st[ 1 ]);
-
- /* copy midpoint to front and back polygons */
- front->v[ front->numVerts++ ] = mid;
- back->v[ back->numVerts++ ] = mid;
- }
- }
-}
-
-
-
-/*
-FilterTraceWindingIntoNodes_r() - ydnar
-filters a trace winding into the raytracing tree
-*/
-
-static void FilterTraceWindingIntoNodes_r( traceWinding_t *tw, int nodeNum )
-{
- int num;
- vec4_t plane1, plane2, reverse;
- traceNode_t *node;
- traceWinding_t front, back;
-
-
- /* don't filter if passed a bogus node (solid, etc) */
- if( nodeNum < 0 || nodeNum >= numTraceNodes )
- return;
-
- /* get node */
- node = &traceNodes[ nodeNum ];
-
- /* is this a decision node? */
- if( node->type >= 0 )
- {
- /* create winding plane if necessary, filtering out bogus windings as well */
- if( nodeNum == headNodeNum )
- {
- if( !PlaneFromPoints( tw->plane, tw->v[ 0 ].xyz, tw->v[ 1 ].xyz, tw->v[ 2 ].xyz ) )
- return;
- }
-
- /* validate the node */
- if( node->children[ 0 ] == 0 || node->children[ 1 ] == 0 )
- Error( "Invalid tracenode: %d", nodeNum );
-
- /* get node plane */
- Vector4Copy( node->plane, plane1 );
-
- /* get winding plane */
- Vector4Copy( tw->plane, plane2 );
-
- /* invert surface plane */
- VectorSubtract( vec3_origin, plane2, reverse );
- reverse[ 3 ] = -plane2[ 3 ];
-
- /* front only */
- if( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f )
- {
- FilterTraceWindingIntoNodes_r( tw, node->children[ 0 ] );
- return;
- }
-
- /* back only */
- if( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f )
- {
- FilterTraceWindingIntoNodes_r( tw, node->children[ 1 ] );
- return;
- }
-
- /* clip the winding by node plane */
- ClipTraceWinding( tw, plane1, &front, &back );
-
- /* filter by node plane */
- if( front.numVerts >= 3 )
- FilterTraceWindingIntoNodes_r( &front, node->children[ 0 ] );
- if( back.numVerts >= 3 )
- FilterTraceWindingIntoNodes_r( &back, node->children[ 1 ] );
-
- /* return to caller */
- return;
- }
-
- /* add winding to leaf node */
- num = AddTraceWinding( tw );
- AddItemToTraceNode( node, num );
-}
-
-
-
-/*
-SubdivideTraceNode_r() - ydnar
-recursively subdivides a tracing node until it meets certain size and complexity criteria
-*/
-
-static void SubdivideTraceNode_r( int nodeNum, int depth )
-{
- int i, j, count, num, frontNum, backNum, type;
- vec3_t size;
- float dist;
- double average[ 3 ];
- traceNode_t *node, *frontNode, *backNode;
- traceWinding_t *tw, front, back;
-
-
- /* dummy check */
- if( nodeNum < 0 || nodeNum >= numTraceNodes )
- return;
-
- /* get node */
- node = &traceNodes[ nodeNum ];
-
- /* runaway recursion check */
- if( depth >= MAX_TRACE_DEPTH )
- {
- //% Sys_Printf( "Depth: (%d items)\n", node->numItems );
- numTraceLeafNodes++;
- return;
- }
- depth++;
-
- /* is this a decision node? */
- if( node->type >= 0 )
- {
- /* subdivide children */
- frontNum = node->children[ 0 ];
- backNum = node->children[ 1 ];
- SubdivideTraceNode_r( frontNum, depth );
- SubdivideTraceNode_r( backNum, depth );
- return;
- }
-
- /* bound the node */
- ClearBounds( node->mins, node->maxs );
- VectorClear( average );
- count = 0;
- for( i = 0; i < node->numItems; i++ )
- {
- /* get winding */
- tw = &traceWindings[ node->items[ i ] ];
-
- /* walk its verts */
- for( j = 0; j < tw->numVerts; j++ )
- {
- AddPointToBounds( tw->v[ j ].xyz, node->mins, node->maxs );
- average[ 0 ] += tw->v[ j ].xyz[ 0 ];
- average[ 1 ] += tw->v[ j ].xyz[ 1 ];
- average[ 2 ] += tw->v[ j ].xyz[ 2 ];
- count++;
- }
- }
-
- /* check triangle limit */
- //% if( node->numItems <= MAX_NODE_ITEMS )
- if( (count - (node->numItems * 2)) < MAX_NODE_TRIANGLES )
- {
- //% Sys_Printf( "Limit: (%d triangles)\n", (count - (node->numItems * 2)) );
- numTraceLeafNodes++;
- return;
- }
-
- /* the largest dimension of the bounding box will be the split axis */
- VectorSubtract( node->maxs, node->mins, size );
- if( size[ 0 ] >= size[ 1 ] && size[ 0 ] >= size[ 2 ] )
- type = PLANE_X;
- else if( size[ 1 ] >= size[ 0 ] && size[ 1 ] >= size[ 2 ] )
- type = PLANE_Y;
- else
- type = PLANE_Z;
-
- /* don't split small nodes */
- if( size[ type ] <= MIN_NODE_SIZE )
- {
- //% Sys_Printf( "Limit: %f %f %f (%d items)\n", size[ 0 ], size[ 1 ], size[ 2 ], node->numItems );
- numTraceLeafNodes++;
- return;
- }
-
- /* set max trace depth */
- if( depth > maxTraceDepth )
- maxTraceDepth = depth;
-
- /* snap the average */
- dist = floor( average[ type ] / count );
-
- /* dummy check it */
- if( dist <= node->mins[ type ] || dist >= node->maxs[ type ] )
- dist = floor( 0.5f * (node->mins[ type ] + node->maxs[ type ]) );
-
- /* allocate child nodes */
- frontNum = AllocTraceNode();
- backNum = AllocTraceNode();
-
- /* reset pointers */
- node = &traceNodes[ nodeNum ];
- frontNode = &traceNodes[ frontNum ];
- backNode = &traceNodes[ backNum ];
-
- /* attach children */
- node->type = type;
- node->plane[ type ] = 1.0f;
- node->plane[ 3 ] = dist;
- node->children[ 0 ] = frontNum;
- node->children[ 1 ] = backNum;
-
- /* setup front node */
- frontNode->maxItems = (node->maxItems >> 1);
- frontNode->items = safe_malloc( frontNode->maxItems * sizeof( *frontNode->items ) );
-
- /* setup back node */
- backNode->maxItems = (node->maxItems >> 1);
- backNode->items = safe_malloc( backNode->maxItems * sizeof( *backNode->items ) );
-
- /* filter windings into child nodes */
- for( i = 0; i < node->numItems; i++ )
- {
- /* get winding */
- tw = &traceWindings[ node->items[ i ] ];
-
- /* clip the winding by the new split plane */
- ClipTraceWinding( tw, node->plane, &front, &back );
-
- /* kill the existing winding */
- if( front.numVerts >= 3 || back.numVerts >= 3 )
- deadWinding = node->items[ i ];
-
- /* add front winding */
- if( front.numVerts >= 3 )
- {
- num = AddTraceWinding( &front );
- AddItemToTraceNode( frontNode, num );
- }
-
- /* add back winding */
- if( back.numVerts >= 3 )
- {
- num = AddTraceWinding( &back );
- AddItemToTraceNode( backNode, num );
- }
- }
-
- /* free original node winding list */
- node->numItems = 0;
- node->maxItems = 0;
- free( node->items );
- node->items = NULL;
-
- /* check children */
- if( frontNode->numItems <= 0 )
- {
- frontNode->maxItems = 0;
- free( frontNode->items );
- frontNode->items = NULL;
- }
-
- if( backNode->numItems <= 0 )
- {
- backNode->maxItems = 0;
- free( backNode->items );
- backNode->items = NULL;
- }
-
- /* subdivide children */
- SubdivideTraceNode_r( frontNum, depth );
- SubdivideTraceNode_r( backNum, depth );
-}
-
-
-
-/*
-TriangulateTraceNode_r()
-optimizes the tracing data by changing trace windings into triangles
-*/
-
-static int TriangulateTraceNode_r( int nodeNum )
-{
- int i, j, num, frontNum, backNum, numWindings, *windings;
- traceNode_t *node;
- traceWinding_t *tw;
- traceTriangle_t tt;
-
-
- /* dummy check */
- if( nodeNum < 0 || nodeNum >= numTraceNodes )
- return 0;
-
- /* get node */
- node = &traceNodes[ nodeNum ];
-
- /* is this a decision node? */
- if( node->type >= 0 )
- {
- /* triangulate children */
- frontNum = node->children[ 0 ];
- backNum = node->children[ 1 ];
- node->numItems = TriangulateTraceNode_r( frontNum );
- node->numItems += TriangulateTraceNode_r( backNum );
- return node->numItems;
- }
-
- /* empty node? */
- if( node->numItems == 0 )
- {
- node->maxItems = 0;
- if( node->items != NULL )
- free( node->items );
- return node->numItems;
- }
-
- /* store off winding data */
- numWindings = node->numItems;
- windings = node->items;
-
- /* clear it */
- node->numItems = 0;
- node->maxItems = numWindings * 2;
- node->items = safe_malloc( node->maxItems * sizeof( tt ) );
-
- /* walk winding list */
- for( i = 0; i < numWindings; i++ )
- {
- /* get winding */
- tw = &traceWindings[ windings[ i ] ];
-
- /* initial setup */
- tt.infoNum = tw->infoNum;
- tt.v[ 0 ] = tw->v[ 0 ];
-
- /* walk vertex list */
- for( j = 1; j + 1 < tw->numVerts; j++ )
- {
- /* set verts */
- tt.v[ 1 ] = tw->v[ j ];
- tt.v[ 2 ] = tw->v[ j + 1 ];
-
- /* find vectors for two edges sharing the first vert */
- VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
- VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
-
- /* add it to the node */
- num = AddTraceTriangle( &tt );
- AddItemToTraceNode( node, num );
- }
- }
-
- /* free windings */
- if( windings != NULL )
- free( windings );
-
- /* return item count */
- return node->numItems;
-}
-
-
-
-/* -------------------------------------------------------------------------------
-
-shadow casting item setup (triangles, patches, entities)
-
-------------------------------------------------------------------------------- */
-
-/*
-PopulateWithBSPModel() - ydnar
-filters a bsp model's surfaces into the raytracing tree
-*/
-
-static void PopulateWithBSPModel( bspModel_t *model, m4x4_t transform )
-{
- int i, j, x, y, pw[ 5 ], r, nodeNum;
- bspDrawSurface_t *ds;
- surfaceInfo_t *info;
- bspDrawVert_t *verts;
- int *indexes;
- mesh_t srcMesh, *mesh, *subdivided;
- traceInfo_t ti;
- traceWinding_t tw;
-
-
- /* dummy check */
- if( model == NULL || transform == NULL )
- return;
-
- /* walk the list of surfaces in this model and fill out the info structs */
- for( i = 0; i < model->numBSPSurfaces; i++ )
- {
- /* get surface and info */
- ds = &bspDrawSurfaces[ model->firstBSPSurface + i ];
- info = &surfaceInfos[ model->firstBSPSurface + i ];
- if( info->si == NULL )
- continue;
-
- /* no shadows */
- if( !info->castShadows )
- continue;
-
- /* patchshadows? */
- if( ds->surfaceType == MST_PATCH && patchShadows == qfalse )
- continue;
-
- /* some surfaces in the bsp might have been tagged as nodraw, with a bogus shader */
- if( (bspShaders[ ds->shaderNum ].contentFlags & noDrawContentFlags) ||
- (bspShaders[ ds->shaderNum ].surfaceFlags & noDrawSurfaceFlags) )
- continue;
-
- /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
- if( (info->si->compileFlags & C_NODRAW) )
- continue;
- if( (info->si->compileFlags & C_TRANSLUCENT) &&
- !(info->si->compileFlags & C_ALPHASHADOW) &&
- !(info->si->compileFlags & C_LIGHTFILTER) )
- continue;
-
- /* setup trace info */
- ti.si = info->si;
- ti.castShadows = info->castShadows;
- ti.surfaceNum = model->firstBSPBrush + i;
- ti.skipGrid = (ds->surfaceType == MST_PATCH);
-
- /* choose which node (normal or skybox) */
- if( info->parentSurfaceNum >= 0 )
- {
- nodeNum = skyboxNodeNum;
-
- /* sky surfaces in portal skies are ignored */
- if( info->si->compileFlags & C_SKY )
- continue;
- }
- else
- nodeNum = headNodeNum;
-
- /* setup trace winding */
- memset( &tw, 0, sizeof( tw ) );
- tw.infoNum = AddTraceInfo( &ti );
- tw.numVerts = 3;
-
- /* switch on type */
- switch( ds->surfaceType )
- {
- /* handle patches */
- case MST_PATCH:
- /* subdivide the surface */
- srcMesh.width = ds->patchWidth;
- srcMesh.height = ds->patchHeight;
- srcMesh.verts = &bspDrawVerts[ ds->firstVert ];
- //% subdivided = SubdivideMesh( srcMesh, 8, 512 );
- subdivided = SubdivideMesh2( srcMesh, info->patchIterations );
-
- /* fit it to the curve and remove colinear verts on rows/columns */
- PutMeshOnCurve( *subdivided );
- mesh = RemoveLinearMeshColumnsRows( subdivided );
- FreeMesh( subdivided );
-
- /* set verts */
- verts = mesh->verts;
-
- /* subdivide each quad to place the models */
- for( y = 0; y < (mesh->height - 1); y++ )
- {
- for( x = 0; x < (mesh->width - 1); x++ )
- {
- /* set indexes */
- pw[ 0 ] = x + (y * mesh->width);
- pw[ 1 ] = x + ((y + 1) * mesh->width);
- pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
- pw[ 3 ] = x + 1 + (y * mesh->width);
- pw[ 4 ] = x + (y * mesh->width); /* same as pw[ 0 ] */
-
- /* set radix */
- r = (x + y) & 1;
-
- /* make first triangle */
- VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
- Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
- VectorCopy( verts[ pw[ r + 1 ] ].xyz, tw.v[ 1 ].xyz );
- Vector2Copy( verts[ pw[ r + 1 ] ].st, tw.v[ 1 ].st );
- VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 2 ].xyz );
- Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 2 ].st );
- m4x4_transform_point( transform, tw.v[ 0 ].xyz );
- m4x4_transform_point( transform, tw.v[ 1 ].xyz );
- m4x4_transform_point( transform, tw.v[ 2 ].xyz );
- FilterTraceWindingIntoNodes_r( &tw, nodeNum );
-
- /* make second triangle */
- VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
- Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
- VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 1 ].xyz );
- Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 1 ].st );
- VectorCopy( verts[ pw[ r + 3 ] ].xyz, tw.v[ 2 ].xyz );
- Vector2Copy( verts[ pw[ r + 3 ] ].st, tw.v[ 2 ].st );
- m4x4_transform_point( transform, tw.v[ 0 ].xyz );
- m4x4_transform_point( transform, tw.v[ 1 ].xyz );
- m4x4_transform_point( transform, tw.v[ 2 ].xyz );
- FilterTraceWindingIntoNodes_r( &tw, nodeNum );
- }
- }
-
- /* free the subdivided mesh */
- FreeMesh( mesh );
- break;
-
- /* handle triangle surfaces */
- case MST_TRIANGLE_SOUP:
- case MST_PLANAR:
- /* set verts and indexes */
- verts = &bspDrawVerts[ ds->firstVert ];
- indexes = &bspDrawIndexes[ ds->firstIndex ];
-
- /* walk the triangle list */
- for( j = 0; j < ds->numIndexes; j += 3 )
- {
- VectorCopy( verts[ indexes[ j ] ].xyz, tw.v[ 0 ].xyz );
- Vector2Copy( verts[ indexes[ j ] ].st, tw.v[ 0 ].st );
- VectorCopy( verts[ indexes[ j + 1 ] ].xyz, tw.v[ 1 ].xyz );
- Vector2Copy( verts[ indexes[ j + 1 ] ].st, tw.v[ 1 ].st );
- VectorCopy( verts[ indexes[ j + 2 ] ].xyz, tw.v[ 2 ].xyz );
- Vector2Copy( verts[ indexes[ j + 2 ] ].st, tw.v[ 2 ].st );
- m4x4_transform_point( transform, tw.v[ 0 ].xyz );
- m4x4_transform_point( transform, tw.v[ 1 ].xyz );
- m4x4_transform_point( transform, tw.v[ 2 ].xyz );
- FilterTraceWindingIntoNodes_r( &tw, nodeNum );
- }
- break;
-
- /* other surface types do not cast shadows */
- default:
- break;
- }
- }
-}
-
-
-
-/*
-PopulateWithPicoModel() - ydnar
-filters a picomodel's surfaces into the raytracing tree
-*/
-
-static void PopulateWithPicoModel( int castShadows, picoModel_t *model, m4x4_t transform )
-{
- int i, j, k, numSurfaces, numIndexes;
- picoSurface_t *surface;
- picoShader_t *shader;
- picoVec_t *xyz, *st;
- picoIndex_t *indexes;
- traceInfo_t ti;
- traceWinding_t tw;
-
-
- /* dummy check */
- if( model == NULL || transform == NULL )
- return;
-
- /* get info */
- numSurfaces = PicoGetModelNumSurfaces( model );
-
- /* walk the list of surfaces in this model and fill out the info structs */
- for( i = 0; i < numSurfaces; i++ )
- {
- /* get surface */
- surface = PicoGetModelSurface( model, i );
- if( surface == NULL )
- continue;
-
- /* only handle triangle surfaces initially (fixme: support patches) */
- if( PicoGetSurfaceType( surface ) != PICO_TRIANGLES )
- continue;
-
- /* get shader (fixme: support shader remapping) */
- shader = PicoGetSurfaceShader( surface );
- if( shader == NULL )
- continue;
- ti.si = ShaderInfoForShader( PicoGetShaderName( shader ) );
- if( ti.si == NULL )
- continue;
-
- /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
- if( (ti.si->compileFlags & C_NODRAW) )
- continue;
- if( (ti.si->compileFlags & C_TRANSLUCENT) &&
- !(ti.si->compileFlags & C_ALPHASHADOW) &&
- !(ti.si->compileFlags & C_LIGHTFILTER) )
- continue;
-
- /* setup trace info */
- ti.castShadows = castShadows;
- ti.surfaceNum = -1;
- ti.skipGrid = qtrue; // also ignore picomodels when skipping patches
-
- /* setup trace winding */
- memset( &tw, 0, sizeof( tw ) );
- tw.infoNum = AddTraceInfo( &ti );
- tw.numVerts = 3;
-
- /* get info */
- numIndexes = PicoGetSurfaceNumIndexes( surface );
- indexes = PicoGetSurfaceIndexes( surface, 0 );
-
- /* walk the triangle list */
- for( j = 0; j < numIndexes; j += 3, indexes += 3 )
- {
- for( k = 0; k < 3; k++ )
- {
- xyz = PicoGetSurfaceXYZ( surface, indexes[ k ] );
- st = PicoGetSurfaceST( surface, 0, indexes[ k ] );
- VectorCopy( xyz, tw.v[ k ].xyz );
- Vector2Copy( st, tw.v[ k ].st );
- m4x4_transform_point( transform, tw.v[ k ].xyz );
- }
- FilterTraceWindingIntoNodes_r( &tw, headNodeNum );
- }
- }
-}
-
-
-
-/*
-PopulateTraceNodes() - ydnar
-fills the raytracing tree with world and entity occluders
-*/
-
-static void PopulateTraceNodes( void )
-{
- int i, m, frame, castShadows;
- float temp;
- entity_t *e;
- const char *value;
- picoModel_t *model;
- vec3_t origin, scale, angles;
- m4x4_t transform;
-
-
- /* add worldspawn triangles */
- m4x4_identity( transform );
- PopulateWithBSPModel( &bspModels[ 0 ], transform );
-
- /* walk each entity list */
- for( i = 1; i < numEntities; i++ )
- {
- /* get entity */
- e = &entities[ i ];
-
- /* get shadow flags */
- castShadows = ENTITY_CAST_SHADOWS;
- GetEntityShadowFlags( e, NULL, &castShadows, NULL );
-
- /* early out? */
- if( !castShadows )
- continue;
-
- /* get entity origin */
- GetVectorForKey( e, "origin", origin );
-
- /* get scale */
- scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = 1.0f;
- temp = FloatForKey( e, "modelscale" );
- if( temp != 0.0f )
- scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = temp;
- value = ValueForKey( e, "modelscale_vec" );
- if( value[ 0 ] != '\0' )
- sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );
-
- /* get "angle" (yaw) or "angles" (pitch yaw roll) */
- angles[ 0 ] = angles[ 1 ] = angles[ 2 ] = 0.0f;
- angles[ 2 ] = FloatForKey( e, "angle" );
- value = ValueForKey( e, "angles" );
- if( value[ 0 ] != '\0' )
- sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
-
- /* set transform matrix (thanks spog) */
- m4x4_identity( transform );
- m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
-
- /* hack: Stable-1_2 and trunk have differing row/column major matrix order
- this transpose is necessary with Stable-1_2
- uncomment the following line with old m4x4_t (non 1.3/spog_branch) code */
- //% m4x4_transpose( transform );
-
- /* get model */
- value = ValueForKey( e, "model" );
-
- /* switch on model type */
- switch( value[ 0 ] )
- {
- /* no model */
- case '\0':
- break;
-
- /* bsp model */
- case '*':
- m = atoi( &value[ 1 ] );
- if( m <= 0 || m >= numBSPModels )
- continue;
- PopulateWithBSPModel( &bspModels[ m ], transform );
- break;
-
- /* external model */
- default:
- frame = IntForKey( e, "_frame" );
- model = LoadModel( value, frame );
- if( model == NULL )
- continue;
- PopulateWithPicoModel( castShadows, model, transform );
- continue;
- }
-
- /* get model2 */
- value = ValueForKey( e, "model2" );
-
- /* switch on model type */
- switch( value[ 0 ] )
- {
- /* no model */
- case '\0':
- break;
-
- /* bsp model */
- case '*':
- m = atoi( &value[ 1 ] );
- if( m <= 0 || m >= numBSPModels )
- continue;
- PopulateWithBSPModel( &bspModels[ m ], transform );
- break;
-
- /* external model */
- default:
- frame = IntForKey( e, "_frame2" );
- model = LoadModel( value, frame );
- if( model == NULL )
- continue;
- PopulateWithPicoModel( castShadows, model, transform );
- continue;
- }
- }
-}
-
-
-
-
-/* -------------------------------------------------------------------------------
-
-trace initialization
-
-------------------------------------------------------------------------------- */
-
-/*
-SetupTraceNodes() - ydnar
-creates a balanced bsp with axis-aligned splits for efficient raytracing
-*/
-
-void SetupTraceNodes( void )
-{
- /* note it */
- Sys_FPrintf( SYS_VRB, "--- SetupTraceNodes ---\n" );
-
- /* find nodraw bit */
- noDrawContentFlags = noDrawSurfaceFlags = noDrawCompileFlags = 0;
- ApplySurfaceParm( "nodraw", &noDrawContentFlags, &noDrawSurfaceFlags, &noDrawCompileFlags );
-
- /* create the baseline raytracing tree from the bsp tree */
- headNodeNum = SetupTraceNodes_r( 0 );
-
- /* create outside node for skybox surfaces */
- skyboxNodeNum = AllocTraceNode();
-
- /* populate the tree with triangles from the world and shadow casting entities */
- PopulateTraceNodes();
-
- /* create the raytracing bsp */
- if( loMem == qfalse )
- {
- SubdivideTraceNode_r( headNodeNum, 0 );
- SubdivideTraceNode_r( skyboxNodeNum, 0 );
- }
-
- /* create triangles from the trace windings */
- TriangulateTraceNode_r( headNodeNum );
- TriangulateTraceNode_r( skyboxNodeNum );
-
- /* emit some stats */
- //% Sys_FPrintf( SYS_VRB, "%9d original triangles\n", numOriginalTriangles );
- Sys_FPrintf( SYS_VRB, "%9d trace windings (%.2fMB)\n", numTraceWindings, (float) (numTraceWindings * sizeof( *traceWindings )) / (1024.0f * 1024.0f) );
- Sys_FPrintf( SYS_VRB, "%9d trace triangles (%.2fMB)\n", numTraceTriangles, (float) (numTraceTriangles * sizeof( *traceTriangles )) / (1024.0f * 1024.0f) );
- Sys_FPrintf( SYS_VRB, "%9d trace nodes (%.2fMB)\n", numTraceNodes, (float) (numTraceNodes * sizeof( *traceNodes )) / (1024.0f * 1024.0f) );
- Sys_FPrintf( SYS_VRB, "%9d leaf nodes (%.2fMB)\n", numTraceLeafNodes, (float) (numTraceLeafNodes * sizeof( *traceNodes )) / (1024.0f * 1024.0f) );
- //% Sys_FPrintf( SYS_VRB, "%9d average triangles per leaf node\n", numTraceTriangles / numTraceLeafNodes );
- Sys_FPrintf( SYS_VRB, "%9d average windings per leaf node\n", numTraceWindings / (numTraceLeafNodes + 1) );
- Sys_FPrintf( SYS_VRB, "%9d max trace depth\n", maxTraceDepth );
-
- /* free trace windings */
- free( traceWindings );
- numTraceWindings = 0;
- maxTraceWindings = 0;
- deadWinding = -1;
-
- /* debug code: write out trace triangles to an alias obj file */
- #if 0
- {
- int i, j;
- FILE *file;
- char filename[ 1024 ];
- traceWinding_t *tw;
-
-
- /* open the file */
- strcpy( filename, source );
- StripExtension( filename );
- strcat( filename, ".lin" );
- Sys_Printf( "Opening light trace file %s...\n", filename );
- file = fopen( filename, "w" );
- if( file == NULL )
- Error( "Error opening %s for writing", filename );
-
- /* walk node list */
- for( i = 0; i < numTraceWindings; i++ )
- {
- tw = &traceWindings[ i ];
- for( j = 0; j < tw->numVerts + 1; j++ )
- fprintf( file, "%f %f %f\n",
- tw->v[ j % tw->numVerts ].xyz[ 0 ], tw->v[ j % tw->numVerts ].xyz[ 1 ], tw->v[ j % tw->numVerts ].xyz[ 2 ] );
- }
-
- /* close it */
- fclose( file );
- }
- #endif
-}
-
-
-
-/* -------------------------------------------------------------------------------
-
-raytracer
-
-------------------------------------------------------------------------------- */
-
-/*
-TraceTriangle()
-based on code written by william 'spog' joseph
-based on code originally written by tomas moller and ben trumbore, journal of graphics tools, 2(1):21-28, 1997
-*/
-
-#define BARY_EPSILON 0.01f
-#define ASLF_EPSILON 0.0001f /* so to not get double shadows */
-#define COPLANAR_EPSILON 0.25f //% 0.000001f
-#define NEAR_SHADOW_EPSILON 1.5f //% 1.25f
-#define SELF_SHADOW_EPSILON 0.5f
-
-qboolean TraceTriangle( traceInfo_t *ti, traceTriangle_t *tt, trace_t *trace )
-{
- int i;
- float tvec[ 3 ], pvec[ 3 ], qvec[ 3 ];
- float det, invDet, depth;
- float u, v, w, s, t;
- int is, it;
- byte *pixel;
- float shadow;
- shaderInfo_t *si;
-
-
- /* don't double-trace against sky */
- si = ti->si;
- if( trace->compileFlags & si->compileFlags & C_SKY )
- return qfalse;
-
- /* receive shadows from worldspawn group only */
- if( trace->recvShadows == 1 )
- {
- if( ti->castShadows != 1 )
- return qfalse;
- }
-
- /* receive shadows from same group and worldspawn group */
- else if( trace->recvShadows > 1 )
- {
- if( ti->castShadows != 1 && abs( ti->castShadows ) != abs( trace->recvShadows ) )
- return qfalse;
- //% Sys_Printf( "%d:%d ", tt->castShadows, trace->recvShadows );
- }
-
- /* receive shadows from the same group only (< 0) */
- else
- {
- if( abs( ti->castShadows ) != abs( trace->recvShadows ) )
- return qfalse;
- }
-
- /* skip patches when doing the grid (FIXME this is an ugly hack) */
- if( inGrid )
- {
- if (ti->skipGrid)
- return qfalse;
- }
-
- /* begin calculating determinant - also used to calculate u parameter */
- CrossProduct( trace->direction, tt->edge2, pvec );
-
- /* if determinant is near zero, trace lies in plane of triangle */
- det = DotProduct( tt->edge1, pvec );
-
- /* the non-culling branch */
- if( fabs( det ) < COPLANAR_EPSILON )
- return qfalse;
- invDet = 1.0f / det;
-
- /* calculate distance from first vertex to ray origin */
- VectorSubtract( trace->origin, tt->v[ 0 ].xyz, tvec );
-
- /* calculate u parameter and test bounds */
- u = DotProduct( tvec, pvec ) * invDet;
- if( u < -BARY_EPSILON || u > (1.0f + BARY_EPSILON) )
- return qfalse;
-
- /* prepare to test v parameter */
- CrossProduct( tvec, tt->edge1, qvec );
-
- /* calculate v parameter and test bounds */
- v = DotProduct( trace->direction, qvec ) * invDet;
- if( v < -BARY_EPSILON || (u + v) > (1.0f + BARY_EPSILON) )
- return qfalse;
-
- /* calculate t (depth) */
- depth = DotProduct( tt->edge2, qvec ) * invDet;
- if( depth <= trace->inhibitRadius || depth >= trace->distance )
- return qfalse;
-
- /* if hitpoint is really close to trace origin (sample point), then check for self-shadowing */
- if( depth <= SELF_SHADOW_EPSILON )
- {
- /* don't self-shadow */
- for( i = 0; i < trace->numSurfaces; i++ )
- {
- if( ti->surfaceNum == trace->surfaces[ i ] )
- return qfalse;
- }
- }
-
- /* stack compile flags */
- trace->compileFlags |= si->compileFlags;
-
- /* don't trace against sky */
- if( si->compileFlags & C_SKY )
- return qfalse;
-
- /* most surfaces are completely opaque */
- if( !(si->compileFlags & (C_ALPHASHADOW | C_LIGHTFILTER)) ||
- si->lightImage == NULL || si->lightImage->pixels == NULL )
- {
- VectorMA( trace->origin, depth, trace->direction, trace->hit );
- VectorClear( trace->color );
- trace->opaque = qtrue;
- return qtrue;
- }
-
- /* force subsampling because the lighting is texture dependent */
- trace->forceSubsampling = 1.0;
-
- /* try to avoid double shadows near triangle seams */
- if( u < -ASLF_EPSILON || u > (1.0f + ASLF_EPSILON) ||
- v < -ASLF_EPSILON || (u + v) > (1.0f + ASLF_EPSILON) )
- return qfalse;
-
- /* calculate w parameter */
- w = 1.0f - (u + v);
-
- /* calculate st from uvw (barycentric) coordinates */
- s = w * tt->v[ 0 ].st[ 0 ] + u * tt->v[ 1 ].st[ 0 ] + v * tt->v[ 2 ].st[ 0 ];
- t = w * tt->v[ 0 ].st[ 1 ] + u * tt->v[ 1 ].st[ 1 ] + v * tt->v[ 2 ].st[ 1 ];
- s = s - floor( s );
- t = t - floor( t );
- is = s * si->lightImage->width;
- it = t * si->lightImage->height;
-
- /* get pixel */
- pixel = si->lightImage->pixels + 4 * (it * si->lightImage->width + is);
-
- /* ydnar: color filter */
- if( si->compileFlags & C_LIGHTFILTER )
- {
- /* filter by texture color */
- trace->color[ 0 ] *= ((1.0f / 255.0f) * pixel[ 0 ]);
- trace->color[ 1 ] *= ((1.0f / 255.0f) * pixel[ 1 ]);
- trace->color[ 2 ] *= ((1.0f / 255.0f) * pixel[ 2 ]);
- }
-
- /* ydnar: alpha filter */
- if( si->compileFlags & C_ALPHASHADOW )
- {
- /* filter by inverse texture alpha */
- shadow = (1.0f / 255.0f) * (255 - pixel[ 3 ]);
- trace->color[ 0 ] *= shadow;
- trace->color[ 1 ] *= shadow;
- trace->color[ 2 ] *= shadow;
- }
-
- /* check filter for opaque */
- if( trace->color[ 0 ] <= 0.001f && trace->color[ 1 ] <= 0.001f && trace->color[ 2 ] <= 0.001f )
- {
- VectorClear( trace->color );
- VectorMA( trace->origin, depth, trace->direction, trace->hit );
- trace->opaque = qtrue;
- return qtrue;
- }
-
- /* continue tracing */
- return qfalse;
-}
-
-
-
-/*
-TraceWinding() - ydnar
-temporary hack
-*/
-
-qboolean TraceWinding( traceWinding_t *tw, trace_t *trace )
-{
- int i;
- traceTriangle_t tt;
-
-
- /* initial setup */
- tt.infoNum = tw->infoNum;
- tt.v[ 0 ] = tw->v[ 0 ];
-
- /* walk vertex list */
- for( i = 1; i + 1 < tw->numVerts; i++ )
- {
- /* set verts */
- tt.v[ 1 ] = tw->v[ i ];
- tt.v[ 2 ] = tw->v[ i + 1 ];
-
- /* find vectors for two edges sharing the first vert */
- VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
- VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
-
- /* trace it */
- if( TraceTriangle( &traceInfos[ tt.infoNum ], &tt, trace ) )
- return qtrue;
- }
-
- /* done */
- return qfalse;
-}
-
-
-
-
-/*
-TraceLine_r()
-returns qtrue if something is hit and tracing can stop
-*/
-
-static qboolean TraceLine_r( int nodeNum, vec3_t origin, vec3_t end, trace_t *trace )
-{
- traceNode_t *node;
- int side;
- float front, back, frac;
- vec3_t mid;
- qboolean r;
-
-
- /* bogus node number means solid, end tracing unless testing all */
- if( nodeNum < 0 )
- {
- VectorCopy( origin, trace->hit );
- trace->passSolid = qtrue;
- return qtrue;
- }
-
- /* get node */
- node = &traceNodes[ nodeNum ];
-
- /* solid? */
- if( node->type == TRACE_LEAF_SOLID )
- {
- VectorCopy( origin, trace->hit );
- trace->passSolid = qtrue;
- return qtrue;
- }
-
- /* leafnode? */
- if( node->type < 0 )
- {
- /* note leaf and return */
- if( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES )
- trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
- return qfalse;
- }
-
- /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
- if( trace->testAll && node->numItems == 0 )
- return qfalse;
-
- /* classify beginning and end points */
- switch( node->type )
- {
- case PLANE_X:
- front = origin[ 0 ] - node->plane[ 3 ];
- back = end[ 0 ] - node->plane[ 3 ];
- break;
-
- case PLANE_Y:
- front = origin[ 1 ] - node->plane[ 3 ];
- back = end[ 1 ] - node->plane[ 3 ];
- break;
-
- case PLANE_Z:
- front = origin[ 2 ] - node->plane[ 3 ];
- back = end[ 2 ] - node->plane[ 3 ];
- break;
-
- default:
- front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
- back = DotProduct( end, node->plane ) - node->plane[ 3 ];
- break;
- }
-
- /* entirely in front side? */
- if( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON )
- return TraceLine_r( node->children[ 0 ], origin, end, trace );
-
- /* entirely on back side? */
- if( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON )
- return TraceLine_r( node->children[ 1 ], origin, end, trace );
-
- /* select side */
- side = front < 0;
-
- /* calculate intercept point */
- frac = front / (front - back);
- mid[ 0 ] = origin[ 0 ] + (end[ 0 ] - origin[ 0 ]) * frac;
- mid[ 1 ] = origin[ 1 ] + (end[ 1 ] - origin[ 1 ]) * frac;
- mid[ 2 ] = origin[ 2 ] + (end[ 2 ] - origin[ 2 ]) * frac;
-
- /* fixme: check inhibit radius, then solid nodes and ignore */
-
- /* set trace hit here */
- //% VectorCopy( mid, trace->hit );
-
- /* trace first side */
- r = TraceLine_r( node->children[ side ], origin, mid, trace );
- if( r )
- return r;
-
- /* trace other side */
- return TraceLine_r( node->children[ !side ], mid, end, trace );
-}
-
-
-
-/*
-TraceLine() - ydnar
-rewrote this function a bit :)
-*/
-
-void TraceLine( trace_t *trace )
-{
- int i, j;
- traceNode_t *node;
- traceTriangle_t *tt;
- traceInfo_t *ti;
-
-
- /* setup output (note: this code assumes the input data is completely filled out) */
- trace->passSolid = qfalse;
- trace->opaque = qfalse;
- trace->compileFlags = 0;
- trace->numTestNodes = 0;
-
- /* early outs */
- if( !trace->recvShadows || !trace->testOcclusion || trace->distance <= 0.00001f )
- return;
-
- /* trace through nodes */
- TraceLine_r( headNodeNum, trace->origin, trace->end, trace );
- if( trace->passSolid && !trace->testAll )
- {
- trace->opaque = qtrue;
- return;
- }
-
- /* skip surfaces? */
- if( noSurfaces )
- return;
-
- /* testall means trace through sky */
- if( trace->testAll && trace->numTestNodes < MAX_TRACE_TEST_NODES &&
- trace->compileFlags & C_SKY &&
- (trace->numSurfaces == 0 || surfaceInfos[ trace->surfaces[ 0 ] ].childSurfaceNum < 0) )
- {
- //% trace->testNodes[ trace->numTestNodes++ ] = skyboxNodeNum;
- TraceLine_r( skyboxNodeNum, trace->origin, trace->end, trace );
- }
-
- /* walk node list */
- for( i = 0; i < trace->numTestNodes; i++ )
- {
- /* get node */
- node = &traceNodes[ trace->testNodes[ i ] ];
-
- /* walk node item list */
- for( j = 0; j < node->numItems; j++ )
- {
- tt = &traceTriangles[ node->items[ j ] ];
- ti = &traceInfos[ tt->infoNum ];
- if( TraceTriangle( ti, tt, trace ) )
- return;
- //% if( TraceWinding( &traceWindings[ node->items[ j ] ], trace ) )
- //% return;
- }
- }
-}
-
-
-
-/*
-SetupTrace() - ydnar
-sets up certain trace values
-*/
-
-float SetupTrace( trace_t *trace )
-{
- VectorSubtract( trace->end, trace->origin, trace->displacement );
- trace->distance = VectorNormalize( trace->displacement, trace->direction );
- VectorCopy( trace->origin, trace->hit );
- return trace->distance;
-}
projects / voretournament / voretournament.git / blobdiff