light_trace.c

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

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