Quake-III-Arena/q3map/light_trace.c

/*
===========================================================================
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;
	}
}