bsp.c

著名物理引擎Hawk的源代码

/* bsp.c, HAWK game engine
*
* Copyright 1997-1998 by Phil Frisbie, Jr.
* for Hawk Software
*
*/

#include "hawk.h"
#include "internal.h"
#define NODE_FRONT	0
#define NODE_BACK	1

int	bspPointInLeafnum(vec3_t point)
{
	int			nodenum;
	vec_t		dist;
	dnode_t		*node;
	dplane_t	*plane;
	
	nodenum = 0;
	while (nodenum >= 0)
	{
		node = &BSP.dnodes[nodenum];
		plane = &BSP.dplanes[node->planenum];
		dist = DotProduct(point, plane->normal) - plane->dist;
		if (dist > 0)
			nodenum = node->children[0];
		else
			nodenum = node->children[1];
	}
	
	return -nodenum - 1;
}

dleaf_t *bspPointInLeaf(vec3_t point)
{
	int		num;
	
	num = bspPointInLeafnum (point);
	return &BSP.dleafs[num];
}


BOOL bspClipRay(vec3_t start, vec3_t end, int contentmask)
{
	dleaf_t		*sleaf, *eleaf;
	int			clipped = FALSE;
	int			nsteps, totalsteps;
	vec3_t		move, step, e;
	float		dist;
	
	sleaf = bspPointInLeaf(start);
	eleaf = bspPointInLeaf(end);
	
	if(sleaf == eleaf)
		return FALSE;
	
	VectorSubtract(end, start, move);
	dist = (float)VectorLength(move);
	
	if(dist > 1.0)
		nsteps = totalsteps = (int)dist + 1;
	else
		nsteps = totalsteps = 1;
	
	VectorScale(move, (float)2/nsteps, step);
	VectorCopy(start, e);
	
	do
	{
		VectorAdd(e, step, e);
		eleaf = bspPointInLeaf(e);
		if(eleaf->contents&contentmask)
			break;
		nsteps--;
	}while(nsteps);
	
	
	if(nsteps)
	{
		/* FIXME: need something better */
		VectorSubtract(e, step, e);
		VectorCopy(e, end);
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

TRACE *bspTraceRay(vec3_t start, vec3_t end, OBJECT *passent, int contentmask)
{
	TRACE		*tr = passent->trace;
	dleaf_t		*sleaf, *eleaf, *lleaf;
	int			clipped = FALSE;
	int			nsteps, totalsteps;
	vec3_t		move, step, e;
	float		dist;

	/* set up the TRACE */
	memset(tr, 0, sizeof(TRACE));
	VectorCopy(end, tr->endpos);
	tr->fraction = 1.0f;

	sleaf = bspPointInLeaf(start);
	eleaf = bspPointInLeaf(end);
	if(sleaf->cluster == -1)
	{
		tr->startsolid = TRUE;
		if(eleaf->cluster == -1)
		{
			tr->allsolid = TRUE;
		}
	}
	
	if(sleaf == eleaf)
		return tr;
	
	VectorSubtract(end, start, move);
	dist = (float)VectorLength(move);
	
	if(dist > 1.0f)
		nsteps = totalsteps = (int)dist + 1;
	else
		nsteps = totalsteps = 1;

	VectorScale(move, (float)2/nsteps, step);
	lleaf = sleaf;
	VectorCopy(start, e);
	
	do
	{
		VectorAdd(e, step, e);
		eleaf = bspPointInLeaf(e);
		if(eleaf->contents & contentmask)
			break;
		lleaf = eleaf;
		nsteps--;
	}while(nsteps);
	
	
	if(nsteps)
	{
		int first = lleaf->firstleafface;
		int last = first + lleaf->numleaffaces;
		int i;
		vec3_t	otherend;

		VectorCopy(e, otherend);
		VectorSubtract(e, step, e);
		VectorCopy(e, tr->endpos);
		tr->contents = eleaf->contents;/* update the contents */

		/* find the surface */
		for (i=first;i<last;++i)
		{
			int			s = BSP.dleaffaces[i];
			SURFACE		*surf = &Level.surf[s];
			float		d1, d2;

			d1 = DotProduct(e, surf->normal) - surf->dist;
			d2 = DotProduct(otherend, surf->normal) - surf->dist;
			if((d1 > 0 && d2 <= 0)||(d1 <= 0 && d2 > 0))/* found the surface */
			{
				tr->surface = (GSURFACE *)surf;/* point to the surface info */
			}
		}
	}
	if(!tr->surface)
	{
		int first = eleaf->firstleafface;
		int last = first + eleaf->numleaffaces;
		int i;
		vec3_t	otherend;

		VectorAdd(e, step, otherend);
		tr->contents = eleaf->contents;/* update the contents */
		/* find the surface */
				
		for (i=first;i<last;++i)
		{
			int			s = BSP.dleaffaces[i];
			SURFACE		*surf = &Level.surf[s];
			float		d1, d2;

			d1 = DotProduct(e, surf->normal) - surf->dist;
			d2 = DotProduct(otherend, surf->normal) - surf->dist;
			if((d1 > 0 && d2 <= 0)||(d1 <= 0 && d2 > 0))/* found the surface */
			{
				tr->surface = (GSURFACE *)surf;/* point to the surface info */
			}
		}
	}
	if(!tr->surface)
	{
		tr->fraction = 1.0f;
	}
	else
	{
		vec3_t	m;
		float d;
		vec3_t	temp;
		SURFACE		*surf = (SURFACE *)tr->surface;

		float d1 = DotProduct(tr->endpos, surf->normal) - surf->dist;

		switch(surf->type)
		{
			case PLANE_X:
				tr->endpos[X] = surf->dist;
				break;
			case PLANE_Y:
				tr->endpos[Y] = surf->dist;
				break;
			case PLANE_Z:
				tr->endpos[Z] = surf->dist;
				break;
			default:
				/*FIXME*/
				VectorScale(surf->normal, d1, temp);
				if(d1 > 0.0f)
				{
					VectorAdd(tr->endpos, temp, tr->endpos);
				}
				else
				{
					VectorSubtract(tr->endpos, temp, tr->endpos);
				}
				break;
		}
		VectorSubtract(start, tr->endpos, m);
		d = (float)VectorLength(m);
		tr->fraction = d / dist;
	}

	return tr;
}

int bspPointcontents(vec3_t point)
{
	dleaf_t *leaf;
	
	leaf = bspPointInLeaf(point);
	
	return leaf->contents;
}

BOOL bspInPVS(vec3_t p1, vec3_t p2)
{
	int		leafnumber;
	
	leafnumber = bspPointInLeafnum(p1);
	
	if(pvs[leafnumber])
	{
		unsigned char	*vis = pvs[leafnumber];
		dleaf_t			*leaf2 = bspPointInLeaf(p2);
		int cluster = leaf2->cluster;
		
		if (cluster==-1)
			return FALSE;		/* it is a solid cluster */
		if (!(vis[cluster>>3] & (1<<(cluster&7))))
			return FALSE;		/* not in pvs */
	}
	return TRUE;
}

BOOL bspInPHS(vec3_t p1, vec3_t p2)
{
	int		leafnumber;
	
	leafnumber = bspPointInLeafnum(p1);
	
	if(phs[leafnumber])
	{
		unsigned char	*vis = phs[leafnumber];
		dleaf_t			*leaf2 = bspPointInLeaf(p2);
		int cluster = leaf2->cluster;
		
		if (cluster==-1)
			return FALSE;		/* it is a solid cluster */
		if (!(vis[cluster>>3] & (1<<(cluster&7))))
			return FALSE;		/* not in phs */
	}
	return TRUE;
}

/* Uses the TraceRay routine to sweep a bounding box.
*  Can be heavily optimized depending on the design of the levels.
*  This sample is designed more for accurracy and not speed.
*/
#pragma optimize( "", off )

TRACE *bspTraceBBox(vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, OBJECT *passent, int contentmask)
{
	TRACE	*tr = passent->trace;
	TRACE	temptr;
	vec3_t	p[8];
	vec3_t	move, temp;
	int		i;

if(1)
{
	memset(tr, 0, sizeof(TRACE));
	VectorCopy(end, tr->endpos);
	tr->fraction = 1.0f;

	return tr;
}
	/* set up the TRACE */
	memset(&temptr, 0, sizeof(TRACE));
	VectorCopy(end, temptr.endpos);
	temptr.fraction = 1.0f;

	VectorSubtract(end, start, move);

	/* create the eight points of the BBOX */
	p[0][X] = mins[X]; p[0][Y] = maxs[Y]; p[0][Z] = mins[Z];/* left front bottom */
	p[1][X] = maxs[X]; p[1][Y] = maxs[Y]; p[1][Z] = mins[Z];/* right front bottom */
	p[2][X] = mins[X]; p[2][Y] = maxs[Y]; p[2][Z] = maxs[Z];/* left front top */
	p[3][X] = maxs[X]; p[3][Y] = maxs[Y]; p[3][Z] = maxs[Z];/* right front top */
	p[4][X] = mins[X]; p[4][Y] = mins[Y]; p[4][Z] = mins[Z];/* left back bottom */
	p[5][X] = maxs[X]; p[5][Y] = mins[Y]; p[5][Z] = mins[Z];/* right back bottom */
	p[6][X] = mins[X]; p[6][Y] = mins[Y]; p[6][Z] = maxs[Z];/* left back top */
	p[7][X] = maxs[X]; p[7][Y] = mins[Y]; p[7][Z] = maxs[Z];/* right back top */

	for(i=0;i<8;i++)
		VectorAdd(p[i], start, p[i]);

	/* now trace from each point */
	for(i=0;i<8;i++)
	{
		VectorAdd(p[i], move, temp);
		tr = bspTraceRay(p[i], temp, passent, contentmask);
		if(!temptr.startsolid)
			temptr.startsolid = tr->startsolid;
		if(!temptr.allsolid)
			temptr.allsolid = tr->allsolid;
		if(tr->fraction < temptr.fraction)
		{
			temptr.fraction = tr->fraction;
			temptr.contents = tr->contents;
			temptr.surface = tr->surface;
		}
	}

	/* check to see if we hit anything yet */
	if(temptr.fraction < 1.0f)
	{
		/* we are done */
		memcpy(tr, &temptr, sizeof(TRACE));
		VectorScale(move, tr->fraction, move);
		VectorAdd(start, move, tr->endpos);
		return tr;
	}

	/* Now we check a few more rays just for good measure ;) */

	/* Check the vertical rays at the end position */

	/* done */
	memcpy(tr, &temptr, sizeof(TRACE));
	return tr;
}
#pragma optimize( "", on )
TRACE *bspTraceSphere(vec3_t start, vec3_t radius, vec3_t end, OBJECT *passent, int contentmask)
{
	TRACE	*tr = passent->trace;

	/* set up the TRACE */
	memset(tr, 0, sizeof(TRACE));
	VectorCopy(end, tr->endpos);
	tr->fraction = 1.0f;

	return tr;
}