light_trace.c

来自「quake3工具源码。包括生成bsp文件」· C语言 代码 · 共 924 行 · 第 1/2 页

#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;