light_trace.c

Go to the documentation of this file.

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

---