From 952c5c128f9efaea89d41d882c4ea3ade7df4591 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 04:48:05 +0000 Subject: Itsa me, quake3io! git-svn-id: svn://svn.icculus.org/quake3/trunk@2 edf5b092-35ff-0310-97b2-ce42778d08ea --- q3map/light_trace.c | 944 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 944 insertions(+) create mode 100755 q3map/light_trace.c (limited to 'q3map/light_trace.c') diff --git a/q3map/light_trace.c b/q3map/light_trace.c new file mode 100755 index 0000000..f8a51e7 --- /dev/null +++ b/q3map/light_trace.c @@ -0,0 +1,944 @@ +/* +=========================================================================== +Copyright (C) 1999-2005 Id Software, Inc. + +This file is part of Quake III Arena source code. + +Quake III Arena source code 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. + +Quake III Arena source code 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 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; + } +} + -- cgit v1.2.3