tech
/
worldspawn
2
0
Fork 0
Code Issues 16 Pull Requests Projects Releases Wiki Activity
worldspawn/tools/vmap/light_trace.c

1807 lines
45 KiB
C
Raw Permalink Blame History

/* -------------------------------------------------------------------------------
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 "vmap.h"
/* dependencies */
#include "vmap.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
// vortex: increased from 12 to 24 for ability co compile some insane maps with large curve count
#define MAX_TW_VERTS 24
#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 );
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" );
}
}
/* 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||ds->surfaceType == MST_PATCHFIXED) && 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 || ds->surfaceType == MST_PATCHFIXED );
/* 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:
case MST_PATCHFIXED:
/* subdivide the surface */
if (ds->surfaceType == MST_PATCHFIXED)
{
srcMesh.width = ds->patchWidth&0xffff;
srcMesh.height = ds->patchHeight&0xffff;
srcMesh.subdiv_x = ds->patchWidth>>16;
srcMesh.subdiv_y = ds->patchHeight>>16;
}
else
{
srcMesh.width = ds->patchWidth;
srcMesh.height = ds->patchHeight;
srcMesh.subdiv_x = -1;
srcMesh.subdiv_y = -1;
}
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 = ShaderInfoForShaderNull( 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 = 0;
if ( strcmp( "", ValueForKey( e, "_frame" ) ) ) {
frame = IntForKey( e, "_frame" );
}
else if ( strcmp( "", ValueForKey( e, "frame" ) ) ) {
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;
if ( is < 0 ) {
is = 0;
}
if ( is > si->lightImage->width - 1 ) {
is = si->lightImage->width - 1;
}
if ( it < 0 ) {
it = 0;
}
if ( it > si->lightImage->height - 1 ) {
it = si->lightImage->height - 1;
}
/* 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;
}
Reference in New Issue View Git Blame Copy Permalink