aboutsummaryrefslogtreecommitdiffstats
path: root/q3map/light_trace.c
diff options
context:
space:
mode:
Diffstat (limited to 'q3map/light_trace.c')
-rwxr-xr-xq3map/light_trace.c1846
1 files changed, 923 insertions, 923 deletions
diff --git a/q3map/light_trace.c b/q3map/light_trace.c
index f8a51e7..2c78575 100755
--- a/q3map/light_trace.c
+++ b/q3map/light_trace.c
@@ -19,926 +19,926 @@ along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
===========================================================================
*/
-#include "light.h"
-
-
-
-#define CURVE_FACET_ERROR 8
-
-int c_totalTrace;
-int c_cullTrace, c_testTrace;
-int c_testFacets;
-
-surfaceTest_t *surfaceTest[MAX_MAP_DRAW_SURFS];
-
-/*
-=====================
-CM_GenerateBoundaryForPoints
-=====================
-*/
-void CM_GenerateBoundaryForPoints( float boundary[4], float plane[4], vec3_t a, vec3_t b ) {
- vec3_t d1;
-
- // amke a perpendicular vector to the edge and the surface
- VectorSubtract( b, a, d1 );
- CrossProduct( plane, d1, boundary );
- VectorNormalize( boundary, boundary );
- boundary[3] = DotProduct( a, boundary );
-}
-
-/*
-=====================
-TextureMatrixFromPoints
-=====================
-*/
-void TextureMatrixFromPoints( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) {
- int i, j;
- float t;
- float m[3][4];
- float s;
-
- // This is an incredibly stupid way of solving a three variable equation
- for ( i = 0 ; i < 2 ; i++ ) {
-
- m[0][0] = a->xyz[0];
- m[0][1] = a->xyz[1];
- m[0][2] = a->xyz[2];
- m[0][3] = a->st[i];
-
- m[1][0] = b->xyz[0];
- m[1][1] = b->xyz[1];
- m[1][2] = b->xyz[2];
- m[1][3] = b->st[i];
-
- m[2][0] = c->xyz[0];
- m[2][1] = c->xyz[1];
- m[2][2] = c->xyz[2];
- m[2][3] = c->st[i];
-
- if ( fabs(m[1][0]) > fabs(m[0][0]) && fabs(m[1][0]) > fabs(m[2][0]) ) {
- for ( j = 0 ; j < 4 ; j ++ ) {
- t = m[0][j];
- m[0][j] = m[1][j];
- m[1][j] = t;
- }
- } else if ( fabs(m[2][0]) > fabs(m[0][0]) && fabs(m[2][0]) > fabs(m[1][0]) ) {
- for ( j = 0 ; j < 4 ; j ++ ) {
- t = m[0][j];
- m[0][j] = m[2][j];
- m[2][j] = t;
- }
- }
-
- s = 1.0 / m[0][0];
- m[0][0] *= s;
- m[0][1] *= s;
- m[0][2] *= s;
- m[0][3] *= s;
-
- s = m[1][0];
- m[1][0] -= m[0][0] * s;
- m[1][1] -= m[0][1] * s;
- m[1][2] -= m[0][2] * s;
- m[1][3] -= m[0][3] * s;
-
- s = m[2][0];
- m[2][0] -= m[0][0] * s;
- m[2][1] -= m[0][1] * s;
- m[2][2] -= m[0][2] * s;
- m[2][3] -= m[0][3] * s;
-
- if ( fabs(m[2][1]) > fabs(m[1][1]) ) {
- for ( j = 0 ; j < 4 ; j ++ ) {
- t = m[1][j];
- m[1][j] = m[2][j];
- m[2][j] = t;
- }
- }
-
- s = 1.0 / m[1][1];
- m[1][0] *= s;
- m[1][1] *= s;
- m[1][2] *= s;
- m[1][3] *= s;
-
- s = m[2][1];
- m[2][0] -= m[1][0] * s;
- m[2][1] -= m[1][1] * s;
- m[2][2] -= m[1][2] * s;
- m[2][3] -= m[1][3] * s;
-
- s = 1.0 / m[2][2];
- m[2][0] *= s;
- m[2][1] *= s;
- m[2][2] *= s;
- m[2][3] *= s;
-
- f->textureMatrix[i][2] = m[2][3];
- f->textureMatrix[i][1] = m[1][3] - f->textureMatrix[i][2] * m[1][2];
- f->textureMatrix[i][0] = m[0][3] - f->textureMatrix[i][2] * m[0][2] - f->textureMatrix[i][1] * m[0][1];
-
- f->textureMatrix[i][3] = 0;
-/*
- s = fabs( DotProduct( a->xyz, f->textureMatrix[i] ) - a->st[i] );
- if ( s > 0.01 ) {
- Error( "Bad textureMatrix" );
- }
- s = fabs( DotProduct( b->xyz, f->textureMatrix[i] ) - b->st[i] );
- if ( s > 0.01 ) {
- Error( "Bad textureMatrix" );
- }
- s = fabs( DotProduct( c->xyz, f->textureMatrix[i] ) - c->st[i] );
- if ( s > 0.01 ) {
- Error( "Bad textureMatrix" );
- }
-*/
- }
-}
-
-/*
-=====================
-CM_GenerateFacetFor3Points
-=====================
-*/
-qboolean CM_GenerateFacetFor3Points( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) {
- // if we can't generate a valid plane for the points, ignore the facet
- if ( !PlaneFromPoints( f->surface, a->xyz, b->xyz, c->xyz ) ) {
- f->numBoundaries = 0;
- return qfalse;
- }
-
- // make boundaries
- f->numBoundaries = 3;
-
- CM_GenerateBoundaryForPoints( f->boundaries[0], f->surface, a->xyz, b->xyz );
- CM_GenerateBoundaryForPoints( f->boundaries[1], f->surface, b->xyz, c->xyz );
- CM_GenerateBoundaryForPoints( f->boundaries[2], f->surface, c->xyz, a->xyz );
-
- VectorCopy( a->xyz, f->points[0] );
- VectorCopy( b->xyz, f->points[1] );
- VectorCopy( c->xyz, f->points[2] );
-
- TextureMatrixFromPoints( f, a, b, c );
-
- return qtrue;
-}
-
-/*
-=====================
-CM_GenerateFacetFor4Points
-
-Attempts to use four points as a planar quad
-=====================
-*/
-#define PLANAR_EPSILON 0.1
-qboolean CM_GenerateFacetFor4Points( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c, drawVert_t *d ) {
- float dist;
- int i;
- vec4_t plane;
-
- // if we can't generate a valid plane for the points, ignore the facet
- if ( !PlaneFromPoints( f->surface, a->xyz, b->xyz, c->xyz ) ) {
- f->numBoundaries = 0;
- return qfalse;
- }
-
- // if the fourth point is also on the plane, we can make a quad facet
- dist = DotProduct( d->xyz, f->surface ) - f->surface[3];
- if ( fabs( dist ) > PLANAR_EPSILON ) {
- f->numBoundaries = 0;
- return qfalse;
- }
-
- // make boundaries
- f->numBoundaries = 4;
-
- CM_GenerateBoundaryForPoints( f->boundaries[0], f->surface, a->xyz, b->xyz );
- CM_GenerateBoundaryForPoints( f->boundaries[1], f->surface, b->xyz, c->xyz );
- CM_GenerateBoundaryForPoints( f->boundaries[2], f->surface, c->xyz, d->xyz );
- CM_GenerateBoundaryForPoints( f->boundaries[3], f->surface, d->xyz, a->xyz );
-
- VectorCopy( a->xyz, f->points[0] );
- VectorCopy( b->xyz, f->points[1] );
- VectorCopy( c->xyz, f->points[2] );
- VectorCopy( d->xyz, f->points[3] );
-
- for (i = 1; i < 4; i++)
- {
- if ( !PlaneFromPoints( plane, f->points[i], f->points[(i+1) % 4], f->points[(i+2) % 4]) ) {
- f->numBoundaries = 0;
- return qfalse;
- }
-
- if (DotProduct(f->surface, plane) < 0.9) {
- f->numBoundaries = 0;
- return qfalse;
- }
- }
-
- TextureMatrixFromPoints( f, a, b, c );
-
- return qtrue;
-}
-
-
-
-
-/*
-===============
-SphereFromBounds
-===============
-*/
-void SphereFromBounds( vec3_t mins, vec3_t maxs, vec3_t origin, float *radius ) {
- vec3_t temp;
-
- VectorAdd( mins, maxs, origin );
- VectorScale( origin, 0.5, origin );
- VectorSubtract( maxs, origin, temp );
- *radius = VectorLength( temp );
-}
-
-
-/*
-====================
-FacetsForTriangleSurface
-====================
-*/
-void FacetsForTriangleSurface( dsurface_t *dsurf, shaderInfo_t *si, surfaceTest_t *test ) {
- int i;
- drawVert_t *v1, *v2, *v3, *v4;
- int count;
- int i1, i2, i3, i4, i5, i6;
-
- test->patch = qfalse;
- test->numFacets = dsurf->numIndexes / 3;
- test->facets = malloc( sizeof( test->facets[0] ) * test->numFacets );
- test->shader = si;
-
- count = 0;
- for ( i = 0 ; i < test->numFacets ; i++ ) {
- i1 = drawIndexes[ dsurf->firstIndex + i*3 ];
- i2 = drawIndexes[ dsurf->firstIndex + i*3 + 1 ];
- i3 = drawIndexes[ dsurf->firstIndex + i*3 + 2 ];
-
- v1 = &drawVerts[ dsurf->firstVert + i1 ];
- v2 = &drawVerts[ dsurf->firstVert + i2 ];
- v3 = &drawVerts[ dsurf->firstVert + i3 ];
-
- // try and make a quad out of two triangles
- if ( i != test->numFacets - 1 ) {
- i4 = drawIndexes[ dsurf->firstIndex + i*3 + 3 ];
- i5 = drawIndexes[ dsurf->firstIndex + i*3 + 4 ];
- i6 = drawIndexes[ dsurf->firstIndex + i*3 + 5 ];
- if ( i4 == i3 && i5 == i2 ) {
- v4 = &drawVerts[ dsurf->firstVert + i6 ];
- if ( CM_GenerateFacetFor4Points( &test->facets[count], v1, v2, v4, v3 ) ) {
- count++;
- i++; // skip next tri
- continue;
- }
- }
- }
-
- if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v2, v3 ))
- count++;
- }
-
- // we may have turned some pairs into quads
- test->numFacets = count;
-}
-
-/*
-====================
-FacetsForPatch
-====================
-*/
-void FacetsForPatch( dsurface_t *dsurf, shaderInfo_t *si, surfaceTest_t *test ) {
- int i, j;
- drawVert_t *v1, *v2, *v3, *v4;
- int count;
- mesh_t srcMesh, *subdivided, *mesh;
-
- srcMesh.width = dsurf->patchWidth;
- srcMesh.height = dsurf->patchHeight;
- srcMesh.verts = &drawVerts[ dsurf->firstVert ];
-
- //subdivided = SubdivideMesh( mesh, CURVE_FACET_ERROR, 9999 );
- mesh = SubdivideMesh( srcMesh, 8, 999 );
- PutMeshOnCurve( *mesh );
- MakeMeshNormals( *mesh );
-
- subdivided = RemoveLinearMeshColumnsRows( mesh );
- FreeMesh(mesh);
-
- test->patch = qtrue;
- test->numFacets = ( subdivided->width - 1 ) * ( subdivided->height - 1 ) * 2;
- test->facets = malloc( sizeof( test->facets[0] ) * test->numFacets );
- test->shader = si;
-
- count = 0;
- for ( i = 0 ; i < subdivided->width - 1 ; i++ ) {
- for ( j = 0 ; j < subdivided->height - 1 ; j++ ) {
-
- v1 = subdivided->verts + j * subdivided->width + i;
- v2 = v1 + 1;
- v3 = v1 + subdivided->width + 1;
- v4 = v1 + subdivided->width;
-
- if ( CM_GenerateFacetFor4Points( &test->facets[count], v1, v4, v3, v2 ) ) {
- count++;
- } else {
- if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v4, v3 ))
- count++;
- if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v3, v2 ))
- count++;
- }
- }
- }
- test->numFacets = count;
- FreeMesh(subdivided);
-}
-
-
-/*
-=====================
-InitSurfacesForTesting
-
-Builds structures to speed the ray tracing against surfaces
-=====================
-*/
-void InitSurfacesForTesting( void ) {
-
- int i, j;
- dsurface_t *dsurf;
- surfaceTest_t *test;
- drawVert_t *dvert;
- shaderInfo_t *si;
-
- for ( i = 0 ; i < numDrawSurfaces ; i++ ) {
- dsurf = &drawSurfaces[ i ];
- if ( !dsurf->numIndexes && !dsurf->patchWidth ) {
- continue;
- }
-
- // don't make surfaces for transparent objects
- // because we want light to pass through them
- si = ShaderInfoForShader( dshaders[ dsurf->shaderNum].shader );
- if ( (si->contents & CONTENTS_TRANSLUCENT) && !(si->surfaceFlags & SURF_ALPHASHADOW) ) {
- continue;
- }
-
- test = malloc( sizeof( *test ) );
- surfaceTest[i] = test;
- ClearBounds( test->mins, test->maxs );
-
- dvert = &drawVerts[ dsurf->firstVert ];
- for ( j = 0 ; j < dsurf->numVerts ; j++, dvert++ ) {
- AddPointToBounds( dvert->xyz, test->mins, test->maxs );
- }
-
- SphereFromBounds( test->mins, test->maxs, test->origin, &test->radius );
-
- if ( dsurf->surfaceType == MST_TRIANGLE_SOUP || dsurf->surfaceType == MST_PLANAR ) {
- FacetsForTriangleSurface( dsurf, si, test );
- } else if ( dsurf->surfaceType == MST_PATCH ) {
- FacetsForPatch( dsurf, si, test );
- }
- }
-}
-
-
-/*
-=====================
-GenerateBoundaryForPoints
-=====================
-*/
-void GenerateBoundaryForPoints( float boundary[4], float plane[4], vec3_t a, vec3_t b ) {
- vec3_t d1;
-
- // amke a perpendicular vector to the edge and the surface
- VectorSubtract( b, a, d1 );
- CrossProduct( plane, d1, boundary );
- VectorNormalize( boundary, boundary );
- boundary[3] = DotProduct( a, boundary );
-}
-
-
-/*
-=================
-SetFacetFilter
-
-Given a point on a facet, determine the color filter
-for light passing through
-=================
-*/
-void SetFacetFilter( traceWork_t *tr, shaderInfo_t *shader, cFacet_t *facet, vec3_t point ) {
- float s, t;
- int is, it;
- byte *image;
- int b;
-
- // most surfaces are completely opaque
- if ( !(shader->surfaceFlags & SURF_ALPHASHADOW) ) {
- VectorClear( tr->trace->filter );
- return;
- }
-
- s = DotProduct( point, facet->textureMatrix[0] ) + facet->textureMatrix[0][3];
- t = DotProduct( point, facet->textureMatrix[1] ) + facet->textureMatrix[1][3];
-
- if ( !shader->pixels ) {
- // assume completely solid
- VectorClear( point );
- return;
- }
-
- s = s - floor( s );
- t = t - floor( t );
-
- is = s * shader->width;
- it = t * shader->height;
-
- image = shader->pixels + 4 * ( it * shader->width + is );
-
- // alpha filter
- b = image[3];
-
- // alpha test makes this a binary option
- b = b < 128 ? 0 : 255;
-
- tr->trace->filter[0] = tr->trace->filter[0] * (255-b) / 255;
- tr->trace->filter[1] = tr->trace->filter[1] * (255-b) / 255;
- tr->trace->filter[2] = tr->trace->filter[2] * (255-b) / 255;
-}
-
-
-/*
-====================
-TraceAgainstFacet
-
-Shader is needed for translucent surfaces
-====================
-*/
-void TraceAgainstFacet( traceWork_t *tr, shaderInfo_t *shader, cFacet_t *facet ) {
- int j;
- float d1, d2, d, f;
- vec3_t point;
- float dist;
-
- // ignore degenerate facets
- if ( facet->numBoundaries < 3 ) {
- return;
- }
-
- dist = facet->surface[3];
-
- // compare the trace endpoints against the facet plane
- d1 = DotProduct( tr->start, facet->surface ) - dist;
- if ( d1 > -1 && d1 < 1 ) {
- return; // don't self intersect
- }
- d2 = DotProduct( tr->end, facet->surface ) - dist;
- if ( d2 > -1 && d2 < 1 ) {
- return; // don't self intersect
- }
-
- // calculate the intersection fraction
- f = ( d1 - ON_EPSILON ) / ( d1 - d2 );
- if ( f <= 0 ) {
- return;
- }
- if ( f >= tr->trace->hitFraction ) {
- return; // we have hit something earlier
- }
-
- // calculate the intersection point
- for ( j = 0 ; j < 3 ; j++ ) {
- point[j] = tr->start[j] + f * ( tr->end[j] - tr->start[j] );
- }
-
- // check the point against the facet boundaries
- for ( j = 0 ; j < facet->numBoundaries ; j++ ) {
- // adjust the plane distance apropriately for mins/maxs
- dist = facet->boundaries[j][3];
-
- d = DotProduct( point, facet->boundaries[j] );
- if ( d > dist + ON_EPSILON ) {
- break; // outside the bounds
- }
- }
-
- if ( j != facet->numBoundaries ) {
- return; // we are outside the bounds of the facet
- }
-
- // we hit this facet
-
- // if this is a transparent surface, calculate filter value
- if ( shader->surfaceFlags & SURF_ALPHASHADOW ) {
- SetFacetFilter( tr, shader, facet, point );
- } else {
- // completely opaque
- VectorClear( tr->trace->filter );
- tr->trace->hitFraction = f;
- }
-
-// VectorCopy( facet->surface, tr->trace->plane.normal );
-// tr->trace->plane.dist = facet->surface[3];
-}
-
-
-/*
-===============================================================
-
- LINE TRACING
-
-===============================================================
-*/
-
-
-#define TRACE_ON_EPSILON 0.1
-
-typedef struct tnode_s
-{
- int type;
- vec3_t normal;
- float dist;
- int children[2];
- int planeNum;
-} tnode_t;
-
-#define MAX_TNODES (MAX_MAP_NODES*4)
-tnode_t *tnodes, *tnode_p;
-
-/*
-==============
-MakeTnode
-
-Converts the disk node structure into the efficient tracing structure
-==============
-*/
-void MakeTnode (int nodenum)
-{
- tnode_t *t;
- dplane_t *plane;
- int i;
- dnode_t *node;
- int leafNum;
-
- t = tnode_p++;
-
- node = dnodes + nodenum;
- plane = dplanes + node->planeNum;
-
- t->planeNum = node->planeNum;
- t->type = PlaneTypeForNormal( plane->normal );
- VectorCopy (plane->normal, t->normal);
- t->dist = plane->dist;
-
- for (i=0 ; i<2 ; i++)
- {
- if (node->children[i] < 0) {
- leafNum = -node->children[i] - 1;
- if ( dleafs[leafNum].cluster == -1 ) {
- // solid
- t->children[i] = leafNum | ( 1 << 31 ) | ( 1 << 30 );
- } else {
- t->children[i] = leafNum | ( 1 << 31 );
- }
- } else {
- t->children[i] = tnode_p - tnodes;
- MakeTnode (node->children[i]);
- }
- }
-
-}
-
-/*
-=============
-InitTrace
-
-Loads the node structure out of a .bsp file to be used for light occlusion
-=============
-*/
-void InitTrace( void ) {
- // 32 byte align the structs
- tnodes = malloc( (MAX_TNODES+1) * sizeof(tnode_t));
- tnodes = (tnode_t *)(((int)tnodes + 31)&~31);
- tnode_p = tnodes;
-
- MakeTnode (0);
-
- InitSurfacesForTesting();
-}
-
-
-/*
-===================
-PointInSolid
-===================
-*/
-qboolean PointInSolid_r( vec3_t start, int node ) {
- tnode_t *tnode;
- float front;
-
- while ( !(node & (1<<31) ) ) {
- tnode = &tnodes[node];
- switch (tnode->type) {
- case PLANE_X:
- front = start[0] - tnode->dist;
- break;
- case PLANE_Y:
- front = start[1] - tnode->dist;
- break;
- case PLANE_Z:
- front = start[2] - tnode->dist;
- break;
- default:
- front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
- break;
- }
-
- if ( front == 0 ) {
- // exactly on node, must check both sides
- return (qboolean) ( PointInSolid_r( start, tnode->children[0] )
- | PointInSolid_r( start, tnode->children[1] ) );
- }
-
- if ( front > 0 ) {
- node = tnode->children[0];
- } else {
- node = tnode->children[1];
- }
- }
-
- if ( node & ( 1 << 30 ) ) {
- return qtrue;
- }
- return qfalse;
-}
-
-/*
-=============
-PointInSolid
-
-=============
-*/
-qboolean PointInSolid( vec3_t start ) {
- return PointInSolid_r( start, 0 );
-}
-
-
-/*
-=============
-TraceLine_r
-
-Returns qtrue if something is hit and tracing can stop
-=============
-*/
-int TraceLine_r( int node, const vec3_t start, const vec3_t stop, traceWork_t *tw ) {
- tnode_t *tnode;
- float front, back;
- vec3_t mid;
- float frac;
- int side;
- int r;
-
- if (node & (1<<31)) {
- if (node & ( 1 << 30 ) ) {
- VectorCopy (start, tw->trace->hit);
- tw->trace->passSolid = qtrue;
- return qtrue;
- } else {
- // save the node off for more exact testing
- if ( tw->numOpenLeafs == MAX_MAP_LEAFS ) {
- return qfalse;
- }
- tw->openLeafNumbers[ tw->numOpenLeafs ] = node & ~(3 << 30);
- tw->numOpenLeafs++;
- return qfalse;
- }
- }
-
- tnode = &tnodes[node];
- switch (tnode->type) {
- case PLANE_X:
- front = start[0] - tnode->dist;
- back = stop[0] - tnode->dist;
- break;
- case PLANE_Y:
- front = start[1] - tnode->dist;
- back = stop[1] - tnode->dist;
- break;
- case PLANE_Z:
- front = start[2] - tnode->dist;
- back = stop[2] - tnode->dist;
- break;
- default:
- front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
- back = (stop[0]*tnode->normal[0] + stop[1]*tnode->normal[1] + stop[2]*tnode->normal[2]) - tnode->dist;
- break;
- }
-
- if (front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON) {
- return TraceLine_r (tnode->children[0], start, stop, tw);
- }
-
- if (front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON) {
- return TraceLine_r (tnode->children[1], start, stop, tw);
- }
-
- side = front < 0;
-
- frac = front / (front-back);
-
- mid[0] = start[0] + (stop[0] - start[0])*frac;
- mid[1] = start[1] + (stop[1] - start[1])*frac;
- mid[2] = start[2] + (stop[2] - start[2])*frac;
-
- r = TraceLine_r (tnode->children[side], start, mid, tw);
-
- if (r) {
- return r;
- }
-
-// trace->planeNum = tnode->planeNum;
- return TraceLine_r (tnode->children[!side], mid, stop, tw);
-}
-
-//==========================================================================================
-
-
-/*
-================
-SphereCull
-================
-*/
-qboolean SphereCull( vec3_t start, vec3_t stop, vec3_t origin, float radius ) {
- vec3_t v;
- float d;
- vec3_t dir;
- float len;
- vec3_t on;
-
- VectorSubtract( stop, start, dir );
- len = VectorNormalize( dir, dir );
-
- VectorSubtract( origin, start, v );
- d = DotProduct( v, dir );
- if ( d > len + radius ) {
- return qtrue; // too far ahead
- }
- if ( d < -radius ) {
- return qtrue; // too far behind
- }
- VectorMA( start, d, dir, on );
-
- VectorSubtract( on, origin, v );
-
- len = VectorLength( v );
-
- if ( len > radius ) {
- return qtrue; // too far to the side
- }
-
- return qfalse; // must be traced against
-}
-
-/*
-================
-TraceAgainstSurface
-================
-*/
-void TraceAgainstSurface( traceWork_t *tw, surfaceTest_t *surf ) {
- int i;
-
- // if surfaces are trans
- if ( SphereCull( tw->start, tw->end, surf->origin, surf->radius ) ) {
- if ( numthreads == 1 ) {
- c_cullTrace++;
- }
- return;
- }
-
- if ( numthreads == 1 ) {
- c_testTrace++;
- c_testFacets += surf->numFacets;
- }
-
- /*
- // MrE: backface culling
- if (!surf->patch && surf->numFacets) {
- // if the surface does not cast an alpha shadow
- if ( !(surf->shader->surfaceFlags & SURF_ALPHASHADOW) ) {
- vec3_t vec;
- VectorSubtract(tw->end, tw->start, vec);
- if (DotProduct(vec, surf->facets->surface) > 0)
- return;
- }
- }
- */
-
- // test against each facet
- for ( i = 0 ; i < surf->numFacets ; i++ ) {
- TraceAgainstFacet( tw, surf->shader, surf->facets + i );
- }
-}
-
-/*
-=============
-TraceLine
-
-Follow the trace just through the solid leafs first, and only
-if it passes that, trace against the objects inside the empty leafs
-Returns qtrue if the trace hit any
-
-traceWork_t is only a parameter to crutch up poor large local allocations on
-winNT and macOS. It should be allocated in the worker function, but never
-looked at.
-
-leave testAll false if all you care about is if it hit anything at all.
-if you need to know the exact first point of impact (for a sun trace), set
-testAll to true
-=============
-*/
-extern qboolean patchshadows;
-
-void TraceLine( const vec3_t start, const vec3_t stop, trace_t *trace, qboolean testAll, traceWork_t *tw ) {
- int r;
- int i, j;
- dleaf_t *leaf;
- float oldHitFrac;
- surfaceTest_t *test;
- int surfaceNum;
- byte surfaceTested[MAX_MAP_DRAW_SURFS/8];
- ;
-
- if ( numthreads == 1 ) {
- c_totalTrace++;
- }
-
- // assume all light gets through, unless the ray crosses
- // a translucent surface
- trace->filter[0] = 1.0;
- trace->filter[1] = 1.0;
- trace->filter[2] = 1.0;
-
- VectorCopy( start, tw->start );
- VectorCopy( stop, tw->end );
- tw->trace = trace;
-
- tw->numOpenLeafs = 0;
-
- trace->passSolid = qfalse;
- trace->hitFraction = 1.0;
-
- r = TraceLine_r( 0, start, stop, tw );
-
- // if we hit a solid leaf, stop without testing the leaf
- // surfaces. Note that the plane and endpoint might not
- // be the first solid intersection along the ray.
- if ( r && !testAll ) {
- return;
- }
-
- if ( noSurfaces ) {
- return;
- }
-
- memset( surfaceTested, 0, (numDrawSurfaces+7)/8 );
- oldHitFrac = trace->hitFraction;
-
- for ( i = 0 ; i < tw->numOpenLeafs ; i++ ) {
- leaf = &dleafs[ tw->openLeafNumbers[ i ] ];
- for ( j = 0 ; j < leaf->numLeafSurfaces ; j++ ) {
- surfaceNum = dleafsurfaces[ leaf->firstLeafSurface + j ];
-
- // make sure we don't test the same ray against a surface more than once
- if ( surfaceTested[ surfaceNum>>3 ] & ( 1 << ( surfaceNum & 7) ) ) {
- continue;
- }
- surfaceTested[ surfaceNum>>3 ] |= ( 1 << ( surfaceNum & 7 ) );
-
- test = surfaceTest[ surfaceNum ];
- if ( !test ) {
- continue;
- }
- //
- if ( !tw->patchshadows && test->patch ) {
- continue;
- }
- TraceAgainstSurface( tw, test );
- }
-
- // if the trace is now solid, we can't possibly hit anything closer
- if ( trace->hitFraction < oldHitFrac ) {
- trace->passSolid = qtrue;
- break;
- }
- }
-
- for ( i = 0 ; i < 3 ; i++ ) {
- trace->hit[i] = start[i] + ( stop[i] - start[i] ) * trace->hitFraction;
- }
-}
-
+#include "light.h"
+
+
+
+#define CURVE_FACET_ERROR 8
+
+int c_totalTrace;
+int c_cullTrace, c_testTrace;
+int c_testFacets;
+
+surfaceTest_t *surfaceTest[MAX_MAP_DRAW_SURFS];
+
+/*
+=====================
+CM_GenerateBoundaryForPoints
+=====================
+*/
+void CM_GenerateBoundaryForPoints( float boundary[4], float plane[4], vec3_t a, vec3_t b ) {
+ vec3_t d1;
+
+ // amke a perpendicular vector to the edge and the surface
+ VectorSubtract( b, a, d1 );
+ CrossProduct( plane, d1, boundary );
+ VectorNormalize( boundary, boundary );
+ boundary[3] = DotProduct( a, boundary );
+}
+
+/*
+=====================
+TextureMatrixFromPoints
+=====================
+*/
+void TextureMatrixFromPoints( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) {
+ int i, j;
+ float t;
+ float m[3][4];
+ float s;
+
+ // This is an incredibly stupid way of solving a three variable equation
+ for ( i = 0 ; i < 2 ; i++ ) {
+
+ m[0][0] = a->xyz[0];
+ m[0][1] = a->xyz[1];
+ m[0][2] = a->xyz[2];
+ m[0][3] = a->st[i];
+
+ m[1][0] = b->xyz[0];
+ m[1][1] = b->xyz[1];
+ m[1][2] = b->xyz[2];
+ m[1][3] = b->st[i];
+
+ m[2][0] = c->xyz[0];
+ m[2][1] = c->xyz[1];
+ m[2][2] = c->xyz[2];
+ m[2][3] = c->st[i];
+
+ if ( fabs(m[1][0]) > fabs(m[0][0]) && fabs(m[1][0]) > fabs(m[2][0]) ) {
+ for ( j = 0 ; j < 4 ; j ++ ) {
+ t = m[0][j];
+ m[0][j] = m[1][j];
+ m[1][j] = t;
+ }
+ } else if ( fabs(m[2][0]) > fabs(m[0][0]) && fabs(m[2][0]) > fabs(m[1][0]) ) {
+ for ( j = 0 ; j < 4 ; j ++ ) {
+ t = m[0][j];
+ m[0][j] = m[2][j];
+ m[2][j] = t;
+ }
+ }
+
+ s = 1.0 / m[0][0];
+ m[0][0] *= s;
+ m[0][1] *= s;
+ m[0][2] *= s;
+ m[0][3] *= s;
+
+ s = m[1][0];
+ m[1][0] -= m[0][0] * s;
+ m[1][1] -= m[0][1] * s;
+ m[1][2] -= m[0][2] * s;
+ m[1][3] -= m[0][3] * s;
+
+ s = m[2][0];
+ m[2][0] -= m[0][0] * s;
+ m[2][1] -= m[0][1] * s;
+ m[2][2] -= m[0][2] * s;
+ m[2][3] -= m[0][3] * s;
+
+ if ( fabs(m[2][1]) > fabs(m[1][1]) ) {
+ for ( j = 0 ; j < 4 ; j ++ ) {
+ t = m[1][j];
+ m[1][j] = m[2][j];
+ m[2][j] = t;
+ }
+ }
+
+ s = 1.0 / m[1][1];
+ m[1][0] *= s;
+ m[1][1] *= s;
+ m[1][2] *= s;
+ m[1][3] *= s;
+
+ s = m[2][1];
+ m[2][0] -= m[1][0] * s;
+ m[2][1] -= m[1][1] * s;
+ m[2][2] -= m[1][2] * s;
+ m[2][3] -= m[1][3] * s;
+
+ s = 1.0 / m[2][2];
+ m[2][0] *= s;
+ m[2][1] *= s;
+ m[2][2] *= s;
+ m[2][3] *= s;
+
+ f->textureMatrix[i][2] = m[2][3];
+ f->textureMatrix[i][1] = m[1][3] - f->textureMatrix[i][2] * m[1][2];
+ f->textureMatrix[i][0] = m[0][3] - f->textureMatrix[i][2] * m[0][2] - f->textureMatrix[i][1] * m[0][1];
+
+ f->textureMatrix[i][3] = 0;
+/*
+ s = fabs( DotProduct( a->xyz, f->textureMatrix[i] ) - a->st[i] );
+ if ( s > 0.01 ) {
+ Error( "Bad textureMatrix" );
+ }
+ s = fabs( DotProduct( b->xyz, f->textureMatrix[i] ) - b->st[i] );
+ if ( s > 0.01 ) {
+ Error( "Bad textureMatrix" );
+ }
+ s = fabs( DotProduct( c->xyz, f->textureMatrix[i] ) - c->st[i] );
+ if ( s > 0.01 ) {
+ Error( "Bad textureMatrix" );
+ }
+*/
+ }
+}
+
+/*
+=====================
+CM_GenerateFacetFor3Points
+=====================
+*/
+qboolean CM_GenerateFacetFor3Points( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) {
+ // if we can't generate a valid plane for the points, ignore the facet
+ if ( !PlaneFromPoints( f->surface, a->xyz, b->xyz, c->xyz ) ) {
+ f->numBoundaries = 0;
+ return qfalse;
+ }
+
+ // make boundaries
+ f->numBoundaries = 3;
+
+ CM_GenerateBoundaryForPoints( f->boundaries[0], f->surface, a->xyz, b->xyz );
+ CM_GenerateBoundaryForPoints( f->boundaries[1], f->surface, b->xyz, c->xyz );
+ CM_GenerateBoundaryForPoints( f->boundaries[2], f->surface, c->xyz, a->xyz );
+
+ VectorCopy( a->xyz, f->points[0] );
+ VectorCopy( b->xyz, f->points[1] );
+ VectorCopy( c->xyz, f->points[2] );
+
+ TextureMatrixFromPoints( f, a, b, c );
+
+ return qtrue;
+}
+
+/*
+=====================
+CM_GenerateFacetFor4Points
+
+Attempts to use four points as a planar quad
+=====================
+*/
+#define PLANAR_EPSILON 0.1
+qboolean CM_GenerateFacetFor4Points( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c, drawVert_t *d ) {
+ float dist;
+ int i;
+ vec4_t plane;
+
+ // if we can't generate a valid plane for the points, ignore the facet
+ if ( !PlaneFromPoints( f->surface, a->xyz, b->xyz, c->xyz ) ) {
+ f->numBoundaries = 0;
+ return qfalse;
+ }
+
+ // if the fourth point is also on the plane, we can make a quad facet
+ dist = DotProduct( d->xyz, f->surface ) - f->surface[3];
+ if ( fabs( dist ) > PLANAR_EPSILON ) {
+ f->numBoundaries = 0;
+ return qfalse;
+ }
+
+ // make boundaries
+ f->numBoundaries = 4;
+
+ CM_GenerateBoundaryForPoints( f->boundaries[0], f->surface, a->xyz, b->xyz );
+ CM_GenerateBoundaryForPoints( f->boundaries[1], f->surface, b->xyz, c->xyz );
+ CM_GenerateBoundaryForPoints( f->boundaries[2], f->surface, c->xyz, d->xyz );
+ CM_GenerateBoundaryForPoints( f->boundaries[3], f->surface, d->xyz, a->xyz );
+
+ VectorCopy( a->xyz, f->points[0] );
+ VectorCopy( b->xyz, f->points[1] );
+ VectorCopy( c->xyz, f->points[2] );
+ VectorCopy( d->xyz, f->points[3] );
+
+ for (i = 1; i < 4; i++)
+ {
+ if ( !PlaneFromPoints( plane, f->points[i], f->points[(i+1) % 4], f->points[(i+2) % 4]) ) {
+ f->numBoundaries = 0;
+ return qfalse;
+ }
+
+ if (DotProduct(f->surface, plane) < 0.9) {
+ f->numBoundaries = 0;
+ return qfalse;
+ }
+ }
+
+ TextureMatrixFromPoints( f, a, b, c );
+
+ return qtrue;
+}
+
+
+
+
+/*
+===============
+SphereFromBounds
+===============
+*/
+void SphereFromBounds( vec3_t mins, vec3_t maxs, vec3_t origin, float *radius ) {
+ vec3_t temp;
+
+ VectorAdd( mins, maxs, origin );
+ VectorScale( origin, 0.5, origin );
+ VectorSubtract( maxs, origin, temp );
+ *radius = VectorLength( temp );
+}
+
+
+/*
+====================
+FacetsForTriangleSurface
+====================
+*/
+void FacetsForTriangleSurface( dsurface_t *dsurf, shaderInfo_t *si, surfaceTest_t *test ) {
+ int i;
+ drawVert_t *v1, *v2, *v3, *v4;
+ int count;
+ int i1, i2, i3, i4, i5, i6;
+
+ test->patch = qfalse;
+ test->numFacets = dsurf->numIndexes / 3;
+ test->facets = malloc( sizeof( test->facets[0] ) * test->numFacets );
+ test->shader = si;
+
+ count = 0;
+ for ( i = 0 ; i < test->numFacets ; i++ ) {
+ i1 = drawIndexes[ dsurf->firstIndex + i*3 ];
+ i2 = drawIndexes[ dsurf->firstIndex + i*3 + 1 ];
+ i3 = drawIndexes[ dsurf->firstIndex + i*3 + 2 ];
+
+ v1 = &drawVerts[ dsurf->firstVert + i1 ];
+ v2 = &drawVerts[ dsurf->firstVert + i2 ];
+ v3 = &drawVerts[ dsurf->firstVert + i3 ];
+
+ // try and make a quad out of two triangles
+ if ( i != test->numFacets - 1 ) {
+ i4 = drawIndexes[ dsurf->firstIndex + i*3 + 3 ];
+ i5 = drawIndexes[ dsurf->firstIndex + i*3 + 4 ];
+ i6 = drawIndexes[ dsurf->firstIndex + i*3 + 5 ];
+ if ( i4 == i3 && i5 == i2 ) {
+ v4 = &drawVerts[ dsurf->firstVert + i6 ];
+ if ( CM_GenerateFacetFor4Points( &test->facets[count], v1, v2, v4, v3 ) ) {
+ count++;
+ i++; // skip next tri
+ continue;
+ }
+ }
+ }
+
+ if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v2, v3 ))
+ count++;
+ }
+
+ // we may have turned some pairs into quads
+ test->numFacets = count;
+}
+
+/*
+====================
+FacetsForPatch
+====================
+*/
+void FacetsForPatch( dsurface_t *dsurf, shaderInfo_t *si, surfaceTest_t *test ) {
+ int i, j;
+ drawVert_t *v1, *v2, *v3, *v4;
+ int count;
+ mesh_t srcMesh, *subdivided, *mesh;
+
+ srcMesh.width = dsurf->patchWidth;
+ srcMesh.height = dsurf->patchHeight;
+ srcMesh.verts = &drawVerts[ dsurf->firstVert ];
+
+ //subdivided = SubdivideMesh( mesh, CURVE_FACET_ERROR, 9999 );
+ mesh = SubdivideMesh( srcMesh, 8, 999 );
+ PutMeshOnCurve( *mesh );
+ MakeMeshNormals( *mesh );
+
+ subdivided = RemoveLinearMeshColumnsRows( mesh );
+ FreeMesh(mesh);
+
+ test->patch = qtrue;
+ test->numFacets = ( subdivided->width - 1 ) * ( subdivided->height - 1 ) * 2;
+ test->facets = malloc( sizeof( test->facets[0] ) * test->numFacets );
+ test->shader = si;
+
+ count = 0;
+ for ( i = 0 ; i < subdivided->width - 1 ; i++ ) {
+ for ( j = 0 ; j < subdivided->height - 1 ; j++ ) {
+
+ v1 = subdivided->verts + j * subdivided->width + i;
+ v2 = v1 + 1;
+ v3 = v1 + subdivided->width + 1;
+ v4 = v1 + subdivided->width;
+
+ if ( CM_GenerateFacetFor4Points( &test->facets[count], v1, v4, v3, v2 ) ) {
+ count++;
+ } else {
+ if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v4, v3 ))
+ count++;
+ if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v3, v2 ))
+ count++;
+ }
+ }
+ }
+ test->numFacets = count;
+ FreeMesh(subdivided);
+}
+
+
+/*
+=====================
+InitSurfacesForTesting
+
+Builds structures to speed the ray tracing against surfaces
+=====================
+*/
+void InitSurfacesForTesting( void ) {
+
+ int i, j;
+ dsurface_t *dsurf;
+ surfaceTest_t *test;
+ drawVert_t *dvert;
+ shaderInfo_t *si;
+
+ for ( i = 0 ; i < numDrawSurfaces ; i++ ) {
+ dsurf = &drawSurfaces[ i ];
+ if ( !dsurf->numIndexes && !dsurf->patchWidth ) {
+ continue;
+ }
+
+ // don't make surfaces for transparent objects
+ // because we want light to pass through them
+ si = ShaderInfoForShader( dshaders[ dsurf->shaderNum].shader );
+ if ( (si->contents & CONTENTS_TRANSLUCENT) && !(si->surfaceFlags & SURF_ALPHASHADOW) ) {
+ continue;
+ }
+
+ test = malloc( sizeof( *test ) );
+ surfaceTest[i] = test;
+ ClearBounds( test->mins, test->maxs );
+
+ dvert = &drawVerts[ dsurf->firstVert ];
+ for ( j = 0 ; j < dsurf->numVerts ; j++, dvert++ ) {
+ AddPointToBounds( dvert->xyz, test->mins, test->maxs );
+ }
+
+ SphereFromBounds( test->mins, test->maxs, test->origin, &test->radius );
+
+ if ( dsurf->surfaceType == MST_TRIANGLE_SOUP || dsurf->surfaceType == MST_PLANAR ) {
+ FacetsForTriangleSurface( dsurf, si, test );
+ } else if ( dsurf->surfaceType == MST_PATCH ) {
+ FacetsForPatch( dsurf, si, test );
+ }
+ }
+}
+
+
+/*
+=====================
+GenerateBoundaryForPoints
+=====================
+*/
+void GenerateBoundaryForPoints( float boundary[4], float plane[4], vec3_t a, vec3_t b ) {
+ vec3_t d1;
+
+ // amke a perpendicular vector to the edge and the surface
+ VectorSubtract( b, a, d1 );
+ CrossProduct( plane, d1, boundary );
+ VectorNormalize( boundary, boundary );
+ boundary[3] = DotProduct( a, boundary );
+}
+
+
+/*
+=================
+SetFacetFilter
+
+Given a point on a facet, determine the color filter
+for light passing through
+=================
+*/
+void SetFacetFilter( traceWork_t *tr, shaderInfo_t *shader, cFacet_t *facet, vec3_t point ) {
+ float s, t;
+ int is, it;
+ byte *image;
+ int b;
+
+ // most surfaces are completely opaque
+ if ( !(shader->surfaceFlags & SURF_ALPHASHADOW) ) {
+ VectorClear( tr->trace->filter );
+ return;
+ }
+
+ s = DotProduct( point, facet->textureMatrix[0] ) + facet->textureMatrix[0][3];
+ t = DotProduct( point, facet->textureMatrix[1] ) + facet->textureMatrix[1][3];
+
+ if ( !shader->pixels ) {
+ // assume completely solid
+ VectorClear( point );
+ return;
+ }
+
+ s = s - floor( s );
+ t = t - floor( t );
+
+ is = s * shader->width;
+ it = t * shader->height;
+
+ image = shader->pixels + 4 * ( it * shader->width + is );
+
+ // alpha filter
+ b = image[3];
+
+ // alpha test makes this a binary option
+ b = b < 128 ? 0 : 255;
+
+ tr->trace->filter[0] = tr->trace->filter[0] * (255-b) / 255;
+ tr->trace->filter[1] = tr->trace->filter[1] * (255-b) / 255;
+ tr->trace->filter[2] = tr->trace->filter[2] * (255-b) / 255;
+}
+
+
+/*
+====================
+TraceAgainstFacet
+
+Shader is needed for translucent surfaces
+====================
+*/
+void TraceAgainstFacet( traceWork_t *tr, shaderInfo_t *shader, cFacet_t *facet ) {
+ int j;
+ float d1, d2, d, f;
+ vec3_t point;
+ float dist;
+
+ // ignore degenerate facets
+ if ( facet->numBoundaries < 3 ) {
+ return;
+ }
+
+ dist = facet->surface[3];
+
+ // compare the trace endpoints against the facet plane
+ d1 = DotProduct( tr->start, facet->surface ) - dist;
+ if ( d1 > -1 && d1 < 1 ) {
+ return; // don't self intersect
+ }
+ d2 = DotProduct( tr->end, facet->surface ) - dist;
+ if ( d2 > -1 && d2 < 1 ) {
+ return; // don't self intersect
+ }
+
+ // calculate the intersection fraction
+ f = ( d1 - ON_EPSILON ) / ( d1 - d2 );
+ if ( f <= 0 ) {
+ return;
+ }
+ if ( f >= tr->trace->hitFraction ) {
+ return; // we have hit something earlier
+ }
+
+ // calculate the intersection point
+ for ( j = 0 ; j < 3 ; j++ ) {
+ point[j] = tr->start[j] + f * ( tr->end[j] - tr->start[j] );
+ }
+
+ // check the point against the facet boundaries
+ for ( j = 0 ; j < facet->numBoundaries ; j++ ) {
+ // adjust the plane distance apropriately for mins/maxs
+ dist = facet->boundaries[j][3];
+
+ d = DotProduct( point, facet->boundaries[j] );
+ if ( d > dist + ON_EPSILON ) {
+ break; // outside the bounds
+ }
+ }
+
+ if ( j != facet->numBoundaries ) {
+ return; // we are outside the bounds of the facet
+ }
+
+ // we hit this facet
+
+ // if this is a transparent surface, calculate filter value
+ if ( shader->surfaceFlags & SURF_ALPHASHADOW ) {
+ SetFacetFilter( tr, shader, facet, point );
+ } else {
+ // completely opaque
+ VectorClear( tr->trace->filter );
+ tr->trace->hitFraction = f;
+ }
+
+// VectorCopy( facet->surface, tr->trace->plane.normal );
+// tr->trace->plane.dist = facet->surface[3];
+}
+
+
+/*
+===============================================================
+
+ LINE TRACING
+
+===============================================================
+*/
+
+
+#define TRACE_ON_EPSILON 0.1
+
+typedef struct tnode_s
+{
+ int type;
+ vec3_t normal;
+ float dist;
+ int children[2];
+ int planeNum;
+} tnode_t;
+
+#define MAX_TNODES (MAX_MAP_NODES*4)
+tnode_t *tnodes, *tnode_p;
+
+/*
+==============
+MakeTnode
+
+Converts the disk node structure into the efficient tracing structure
+==============
+*/
+void MakeTnode (int nodenum)
+{
+ tnode_t *t;
+ dplane_t *plane;
+ int i;
+ dnode_t *node;
+ int leafNum;
+
+ t = tnode_p++;
+
+ node = dnodes + nodenum;
+ plane = dplanes + node->planeNum;
+
+ t->planeNum = node->planeNum;
+ t->type = PlaneTypeForNormal( plane->normal );
+ VectorCopy (plane->normal, t->normal);
+ t->dist = plane->dist;
+
+ for (i=0 ; i<2 ; i++)
+ {
+ if (node->children[i] < 0) {
+ leafNum = -node->children[i] - 1;
+ if ( dleafs[leafNum].cluster == -1 ) {
+ // solid
+ t->children[i] = leafNum | ( 1 << 31 ) | ( 1 << 30 );
+ } else {
+ t->children[i] = leafNum | ( 1 << 31 );
+ }
+ } else {
+ t->children[i] = tnode_p - tnodes;
+ MakeTnode (node->children[i]);
+ }
+ }
+
+}
+
+/*
+=============
+InitTrace
+
+Loads the node structure out of a .bsp file to be used for light occlusion
+=============
+*/
+void InitTrace( void ) {
+ // 32 byte align the structs
+ tnodes = malloc( (MAX_TNODES+1) * sizeof(tnode_t));
+ tnodes = (tnode_t *)(((int)tnodes + 31)&~31);
+ tnode_p = tnodes;
+
+ MakeTnode (0);
+
+ InitSurfacesForTesting();
+}
+
+
+/*
+===================
+PointInSolid
+===================
+*/
+qboolean PointInSolid_r( vec3_t start, int node ) {
+ tnode_t *tnode;
+ float front;
+
+ while ( !(node & (1<<31) ) ) {
+ tnode = &tnodes[node];
+ switch (tnode->type) {
+ case PLANE_X:
+ front = start[0] - tnode->dist;
+ break;
+ case PLANE_Y:
+ front = start[1] - tnode->dist;
+ break;
+ case PLANE_Z:
+ front = start[2] - tnode->dist;
+ break;
+ default:
+ front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
+ break;
+ }
+
+ if ( front == 0 ) {
+ // exactly on node, must check both sides
+ return (qboolean) ( PointInSolid_r( start, tnode->children[0] )
+ | PointInSolid_r( start, tnode->children[1] ) );
+ }
+
+ if ( front > 0 ) {
+ node = tnode->children[0];
+ } else {
+ node = tnode->children[1];
+ }
+ }
+
+ if ( node & ( 1 << 30 ) ) {
+ return qtrue;
+ }
+ return qfalse;
+}
+
+/*
+=============
+PointInSolid
+
+=============
+*/
+qboolean PointInSolid( vec3_t start ) {
+ return PointInSolid_r( start, 0 );
+}
+
+
+/*
+=============
+TraceLine_r
+
+Returns qtrue if something is hit and tracing can stop
+=============
+*/
+int TraceLine_r( int node, const vec3_t start, const vec3_t stop, traceWork_t *tw ) {
+ tnode_t *tnode;
+ float front, back;
+ vec3_t mid;
+ float frac;
+ int side;
+ int r;
+
+ if (node & (1<<31)) {
+ if (node & ( 1 << 30 ) ) {
+ VectorCopy (start, tw->trace->hit);
+ tw->trace->passSolid = qtrue;
+ return qtrue;
+ } else {
+ // save the node off for more exact testing
+ if ( tw->numOpenLeafs == MAX_MAP_LEAFS ) {
+ return qfalse;
+ }
+ tw->openLeafNumbers[ tw->numOpenLeafs ] = node & ~(3 << 30);
+ tw->numOpenLeafs++;
+ return qfalse;
+ }
+ }
+
+ tnode = &tnodes[node];
+ switch (tnode->type) {
+ case PLANE_X:
+ front = start[0] - tnode->dist;
+ back = stop[0] - tnode->dist;
+ break;
+ case PLANE_Y:
+ front = start[1] - tnode->dist;
+ back = stop[1] - tnode->dist;
+ break;
+ case PLANE_Z:
+ front = start[2] - tnode->dist;
+ back = stop[2] - tnode->dist;
+ break;
+ default:
+ front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
+ back = (stop[0]*tnode->normal[0] + stop[1]*tnode->normal[1] + stop[2]*tnode->normal[2]) - tnode->dist;
+ break;
+ }
+
+ if (front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON) {
+ return TraceLine_r (tnode->children[0], start, stop, tw);
+ }
+
+ if (front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON) {
+ return TraceLine_r (tnode->children[1], start, stop, tw);
+ }
+
+ side = front < 0;
+
+ frac = front / (front-back);
+
+ mid[0] = start[0] + (stop[0] - start[0])*frac;
+ mid[1] = start[1] + (stop[1] - start[1])*frac;
+ mid[2] = start[2] + (stop[2] - start[2])*frac;
+
+ r = TraceLine_r (tnode->children[side], start, mid, tw);
+
+ if (r) {
+ return r;
+ }
+
+// trace->planeNum = tnode->planeNum;
+ return TraceLine_r (tnode->children[!side], mid, stop, tw);
+}
+
+//==========================================================================================
+
+
+/*
+================
+SphereCull
+================
+*/
+qboolean SphereCull( vec3_t start, vec3_t stop, vec3_t origin, float radius ) {
+ vec3_t v;
+ float d;
+ vec3_t dir;
+ float len;
+ vec3_t on;
+
+ VectorSubtract( stop, start, dir );
+ len = VectorNormalize( dir, dir );
+
+ VectorSubtract( origin, start, v );
+ d = DotProduct( v, dir );
+ if ( d > len + radius ) {
+ return qtrue; // too far ahead
+ }
+ if ( d < -radius ) {
+ return qtrue; // too far behind
+ }
+ VectorMA( start, d, dir, on );
+
+ VectorSubtract( on, origin, v );
+
+ len = VectorLength( v );
+
+ if ( len > radius ) {
+ return qtrue; // too far to the side
+ }
+
+ return qfalse; // must be traced against
+}
+
+/*
+================
+TraceAgainstSurface
+================
+*/
+void TraceAgainstSurface( traceWork_t *tw, surfaceTest_t *surf ) {
+ int i;
+
+ // if surfaces are trans
+ if ( SphereCull( tw->start, tw->end, surf->origin, surf->radius ) ) {
+ if ( numthreads == 1 ) {
+ c_cullTrace++;
+ }
+ return;
+ }
+
+ if ( numthreads == 1 ) {
+ c_testTrace++;
+ c_testFacets += surf->numFacets;
+ }
+
+ /*
+ // MrE: backface culling
+ if (!surf->patch && surf->numFacets) {
+ // if the surface does not cast an alpha shadow
+ if ( !(surf->shader->surfaceFlags & SURF_ALPHASHADOW) ) {
+ vec3_t vec;
+ VectorSubtract(tw->end, tw->start, vec);
+ if (DotProduct(vec, surf->facets->surface) > 0)
+ return;
+ }
+ }
+ */
+
+ // test against each facet
+ for ( i = 0 ; i < surf->numFacets ; i++ ) {
+ TraceAgainstFacet( tw, surf->shader, surf->facets + i );
+ }
+}
+
+/*
+=============
+TraceLine
+
+Follow the trace just through the solid leafs first, and only
+if it passes that, trace against the objects inside the empty leafs
+Returns qtrue if the trace hit any
+
+traceWork_t is only a parameter to crutch up poor large local allocations on
+winNT and macOS. It should be allocated in the worker function, but never
+looked at.
+
+leave testAll false if all you care about is if it hit anything at all.
+if you need to know the exact first point of impact (for a sun trace), set
+testAll to true
+=============
+*/
+extern qboolean patchshadows;
+
+void TraceLine( const vec3_t start, const vec3_t stop, trace_t *trace, qboolean testAll, traceWork_t *tw ) {
+ int r;
+ int i, j;
+ dleaf_t *leaf;
+ float oldHitFrac;
+ surfaceTest_t *test;
+ int surfaceNum;
+ byte surfaceTested[MAX_MAP_DRAW_SURFS/8];
+ ;
+
+ if ( numthreads == 1 ) {
+ c_totalTrace++;
+ }
+
+ // assume all light gets through, unless the ray crosses
+ // a translucent surface
+ trace->filter[0] = 1.0;
+ trace->filter[1] = 1.0;
+ trace->filter[2] = 1.0;
+
+ VectorCopy( start, tw->start );
+ VectorCopy( stop, tw->end );
+ tw->trace = trace;
+
+ tw->numOpenLeafs = 0;
+
+ trace->passSolid = qfalse;
+ trace->hitFraction = 1.0;
+
+ r = TraceLine_r( 0, start, stop, tw );
+
+ // if we hit a solid leaf, stop without testing the leaf
+ // surfaces. Note that the plane and endpoint might not
+ // be the first solid intersection along the ray.
+ if ( r && !testAll ) {
+ return;
+ }
+
+ if ( noSurfaces ) {
+ return;
+ }
+
+ memset( surfaceTested, 0, (numDrawSurfaces+7)/8 );
+ oldHitFrac = trace->hitFraction;
+
+ for ( i = 0 ; i < tw->numOpenLeafs ; i++ ) {
+ leaf = &dleafs[ tw->openLeafNumbers[ i ] ];
+ for ( j = 0 ; j < leaf->numLeafSurfaces ; j++ ) {
+ surfaceNum = dleafsurfaces[ leaf->firstLeafSurface + j ];
+
+ // make sure we don't test the same ray against a surface more than once
+ if ( surfaceTested[ surfaceNum>>3 ] & ( 1 << ( surfaceNum & 7) ) ) {
+ continue;
+ }
+ surfaceTested[ surfaceNum>>3 ] |= ( 1 << ( surfaceNum & 7 ) );
+
+ test = surfaceTest[ surfaceNum ];
+ if ( !test ) {
+ continue;
+ }
+ //
+ if ( !tw->patchshadows && test->patch ) {
+ continue;
+ }
+ TraceAgainstSurface( tw, test );
+ }
+
+ // if the trace is now solid, we can't possibly hit anything closer
+ if ( trace->hitFraction < oldHitFrac ) {
+ trace->passSolid = qtrue;
+ break;
+ }
+ }
+
+ for ( i = 0 ; i < 3 ; i++ ) {
+ trace->hit[i] = start[i] + ( stop[i] - start[i] ) * trace->hitFraction;
+ }
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-04 01:28:19 +0000