945 lines
23 KiB
C
945 lines
23 KiB
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;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|