tracing.c File Reference

model tracing and bounding More...

#include "tracing.h"
#include "common.h"
#include "mem.h"

Include dependency graph for tracing.c:

Data Structures
struct	leaf_check_s
Typedefs
typedef struct leaf_check_s	leaf_check_t
Functions
static void	TR_MakeTracingNode (TR_TILE_TYPE tile, tnode_t *tnode, int32_t nodenum)
	Converts the disk node structure into the efficient tracing structure for LineTraces.
void	TR_BuildTracingNode_r (TR_TILE_TYPE tile, tnode_t *tnode, int32_t nodenum, int level)
int	TR_TestLine_r (TR_TILE_TYPE *tile, int32_t nodenum, const vec3_t start, const vec3_t stop)
static qboolean	TR_TileTestLine (TR_TILE_TYPE *tile, const vec3_t start, const vec3_t stop, const int levelmask)
	Tests to see if a line intersects any brushes in a tile.
qboolean	TR_TestLine (mapTiles_t *mapTiles, const vec3_t start, const vec3_t stop, const int levelmask)
	Checks traces against the world.
static int	TR_TestLineDist_r (TR_TILE_TYPE *tile, int32_t nodenum, const vec3_t start, const vec3_t stop, vec3_t tr_end)
static qboolean	TR_TileTestLineDM (TR_TILE_TYPE *tile, const vec3_t start, const vec3_t stop, vec3_t end, const int levelmask)
	Checks traces against the world, gives hit position back.
qboolean	TR_TestLineDM (mapTiles_t *mapTiles, const vec3_t start, const vec3_t stop, vec3_t end, const int levelmask)
	Checks traces against the world, gives hit position back.
int	TR_BoxOnPlaneSide (const vec3_t mins, const vec3_t maxs, const TR_PLANE_TYPE *plane)
	Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH.
static void	TR_BoxLeafnums_r (boxtrace_t traceData, int32_t nodenum, leaf_check_t lc)
	Fills in a list of all the leafs touched call with topnode set to the headnode, returns with topnode set to the first node that splits the box.
static int	TR_BoxLeafnums_headnode (boxtrace_t traceData, int32_t list, int listsize, int32_t headnode, int32_t *topnode)
static void	TR_ClipBoxToBrush (boxtrace_t traceData, cBspBrush_t brush, TR_LEAF_TYPE *leaf)
	This function checks to see if any sides of a brush intersect the line from p1 to p2 or are located within the perpendicular bounding box from mins to maxs originating from the line. It also check to see if the line originates from inside the brush, terminates inside the brush, or is completely contained within the brush.
static void	TR_TestBoxInBrush (boxtrace_t traceData, cBspBrush_t brush)
static void	TR_TraceToLeaf (boxtrace_t *traceData, int32_t leafnum)
	This function checks if the specified leaf matches any mask specified in traceData.contents. and does not contain any mask specified in traceData.rejects If so, each brush in the leaf is examined to see if it is intersected by the line drawn in TR_RecursiveHullCheck or is within the bounding box set in trace_mins and trace_maxs with the origin on the line.
static void	TR_TestInLeaf (boxtrace_t *traceData, int32_t leafnum)
static void	TR_RecursiveHullCheck (boxtrace_t *traceData, int32_t nodenum, float p1f, float p2f, const vec3_t p1, const vec3_t p2)
	This recursive function traces through the bsp tree looking to see if a brush can be found that intersects the line from p1 to p2, including a bounding box (plane) offset that is perpendicular to the line. If the node of the tree is a leaf, the leaf is checked. If not, it is determined which side(s) of the tree need to be traversed, and this function is called again. The bounding box mentioned earlier is set in TR_BoxTrace, and propagated using trace_extents. Trace_extents is specifically how far from the line a bsp node needs to be in order to be included or excluded in the search.
trace_t	TR_BoxTrace (TR_TILE_TYPE *tile, const vec3_t start, const vec3_t end, const vec3_t mins, const vec3_t maxs, const int headnode, const int brushmask, const int brushreject, const float fraction)
	This function traces a line from start to end. It returns a trace_t indicating what portion of the line can be traveled from start to end before hitting a brush that meets the criteria in brushmask. The point that this line intersects that brush is also returned. There is a special case when start and end are the same vector. In this case, the bounding box formed by mins and maxs offset from start is examined for any brushes that meet the criteria. The first brush found inside the bounding box is returned. There is another special case when mins and maxs are both origin vectors (0, 0, 0). In this case, the.
trace_t	TR_TileBoxTrace (TR_TILE_TYPE *myTile, const vec3_t start, const vec3_t end, const vec3_t mins, const vec3_t maxs, const int levelmask, const int brushmask, const int brushreject)
	Traces all submodels in the specified tile. Provides for a short circuit if the trace tries to move past fraction to save time.
Variables
static int	checkcount

Detailed Description

model tracing and bounding

Note:: collision detection code

Definition in file tracing.c.

Typedef Documentation

typedef struct leaf_check_s leaf_check_t

Function Documentation

static int TR_BoxLeafnums_headnode	(	boxtrace_t *	traceData,
		int32_t *	list,
		int	listsize,
		int32_t	headnode,
		int32_t *	topnode
	)			`[static]`

Parameters:

`[in]`	traceData	both parameters and results of the trace
`[in]`	headnode	if < 0 we are in a leaf node

Definition at line 560 of file tracing.c.

References leaf_check_s::leaf_count, leaf_check_s::leaf_list, leaf_check_s::leaf_maxcount, leaf_check_s::leaf_topnode, LEAFNODE, and TR_BoxLeafnums_r().

Referenced by TR_BoxTrace().

static void TR_BoxLeafnums_r	(	boxtrace_t *	traceData,
		int32_t	nodenum,
		leaf_check_t *	lc
	)			`[static]`

Fills in a list of all the leafs touched call with topnode set to the headnode, returns with topnode set to the first node that splits the box.

Definition at line 517 of file tracing.c.

References boxtrace_s::absmaxs, boxtrace_s::absmins, leaf_check_s::leaf_count, leaf_check_s::leaf_list, leaf_check_s::leaf_maxcount, leaf_check_s::leaf_topnode, LEAFNODE, PSIDE_BACK, PSIDE_FRONT, boxtrace_s::tile, and TR_BoxOnPlaneSide().

Referenced by TR_BoxLeafnums_headnode().

int TR_BoxOnPlaneSide	(	const vec3_t	mins,
		const vec3_t	maxs,
		const TR_PLANE_TYPE *	plane
	)

Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH.

Definition at line 467 of file tracing.c.

References AXIAL, DotProduct, i, PLANESIDE_EPSILON, PSIDE_BACK, and PSIDE_FRONT.

Referenced by R_CullBox(), TestBrushToPlanenum(), and TR_BoxLeafnums_r().

trace_t TR_BoxTrace	(	TR_TILE_TYPE *	tile,
		const vec3_t	start,
		const vec3_t	end,
		const vec3_t	mins,
		const vec3_t	maxs,
		const int	headnode,
		const int	brushmask,
		const int	brushreject,
		const float	fraction
	)

This function traces a line from start to end. It returns a trace_t indicating what portion of the line can be traveled from start to end before hitting a brush that meets the criteria in brushmask. The point that this line intersects that brush is also returned. There is a special case when start and end are the same vector. In this case, the bounding box formed by mins and maxs offset from start is examined for any brushes that meet the criteria. The first brush found inside the bounding box is returned. There is another special case when mins and maxs are both origin vectors (0, 0, 0). In this case, the.

Parameters:

`[in]`	start	trace start vector
`[in]`	end	trace end vector
`[in]`	mins	box mins
`[in]`	maxs	box maxs
`[in]`	tile	Tile to check (normally 0 - except in assembled maps)
`[in]`	headnode	if < 0 we are in a leaf node
`[in]`	brushmask	brushes the trace should stop at (see MASK_*)
`[in]`	brushreject	brushes the trace should ignore (see MASK_*)
`[in]`	fraction	The furthest distance needed to trace before we stop.

See also:: TR_RecursiveHullCheck; TR_BoxLeafnums_headnode

Todo:: Would Interpolating aend to traceData.fraction and passing traceData.fraction instead of 1.0 make this faster?

Definition at line 958 of file tracing.c.

References boxtrace_s::absmaxs, boxtrace_s::absmins, trace_s::allsolid, checkcount, Com_Error(), boxtrace_s::contents, boxtrace_s::end, trace_s::endpos, ERR_DROP, boxtrace_s::extents, f, trace_s::fraction, i, boxtrace_s::ispoint, MAX_LEAFS, boxtrace_s::maxs, boxtrace_s::mins, qfalse, qtrue, boxtrace_s::rejects, boxtrace_s::start, trace_s::surface, boxtrace_s::tile, TR_BoxLeafnums_headnode(), TR_RecursiveHullCheck(), TR_TestInLeaf(), boxtrace_s::trace, vec3_origin, VectorAdd, VectorCenterFromMinsMaxs(), VectorClear, VectorCompare, VectorCopy, VectorInterpolation, and VectorSubtract.

Referenced by CM_HintedTransformedBoxTrace(), and TR_TileBoxTrace().

void TR_BuildTracingNode_r	(	TR_TILE_TYPE *	tile,
		tnode_t **	tnode,
		int32_t	nodenum,
		int	level
	)

See also:: CMod_LoadNodes; R_ModLoadNodes

We are checking for a leaf in the tracing node. For ufo2map, planenum == PLANENUMLEAF. For the game, plane will be NULL.

Definition at line 90 of file tracing.c.

References tnode_s::children, Com_Error(), Com_Printf(), tnode_s::dist, ERR_DROP, i, MAX_MAP_NODES, tnode_s::normal, PLANE_NONE, PLANENUM_LEAF, Sys_Error(), TR_BuildTracingNode_r(), TR_MakeTracingNode(), tnode_s::type, VectorCopy, and VectorSet.

Referenced by CM_MakeTracingNodes(), MakeTracingNodes(), and TR_BuildTracingNode_r().

static void TR_ClipBoxToBrush	(	boxtrace_t *	traceData,
		cBspBrush_t *	brush,
		TR_LEAF_TYPE *	leaf
	)			`[static]`

This function checks to see if any sides of a brush intersect the line from p1 to p2 or are located within the perpendicular bounding box from mins to maxs originating from the line. It also check to see if the line originates from inside the brush, terminates inside the brush, or is completely contained within the brush.

Parameters:

`[in,out]`	traceData	both parameters and results of the trace
`[in]`	brush	the brush that is being examined
`[in]`	leaf	the leafnode the brush that is being examined belongs to

Todo:: special case for axial

Definition at line 586 of file tracing.c.

References trace_s::allsolid, cBspBrush_s::contentFlags, trace_s::contentFlags, DIST_EPSILON, DotProduct, boxtrace_s::end, f, cBspBrush_s::firstbrushside, trace_s::fraction, i, boxtrace_s::ispoint, trace_s::leafnum, boxtrace_s::maxs, boxtrace_s::mins, cBspBrush_s::numsides, ofs, trace_s::plane, trace_s::planenum, qfalse, qtrue, boxtrace_s::start, trace_s::startsolid, trace_s::surface, boxtrace_s::tile, and boxtrace_s::trace.

Referenced by TR_TraceToLeaf().

static void TR_MakeTracingNode	(	TR_TILE_TYPE *	tile,
		tnode_t **	tnode,
		int32_t	nodenum
	)			`[static]`

Converts the disk node structure into the efficient tracing structure for LineTraces.

Definition at line 46 of file tracing.c.

References tnode_s::children, Com_Printf(), CONTENTS_PASSABLE, CONTENTS_SOLID, tnode_s::dist, i, MASK_CLIP, tnode_s::normal, tnode_s::type, and VectorCopy.

Referenced by TR_BuildTracingNode_r().

static void TR_RecursiveHullCheck	(	boxtrace_t *	traceData,
		int32_t	nodenum,
		float	p1f,
		float	p2f,
		const vec3_t	p1,
		const vec3_t	p2
	)			`[static]`

This recursive function traces through the bsp tree looking to see if a brush can be found that intersects the line from p1 to p2, including a bounding box (plane) offset that is perpendicular to the line. If the node of the tree is a leaf, the leaf is checked. If not, it is determined which side(s) of the tree need to be traversed, and this function is called again. The bounding box mentioned earlier is set in TR_BoxTrace, and propagated using trace_extents. Trace_extents is specifically how far from the line a bsp node needs to be in order to be included or excluded in the search.

Parameters:

`[in]`	traceData	both parameters and results of the trace
`[in]`	nodenum	the node index that we are looking in for a hit
`[in]`	p1f	based on the original line, the fraction traveled to reach the start vector
`[in]`	p2f	based on the original line, the fraction traveled to reach the end vector
`[in]`	p1	start vector
`[in]`	p2	end vector

See also:: CM_BoxTrace; CM_TraceToLeaf

Note:: t1 and t2 refer to the distance the endpoints of the line are from the bsp dividing plane for this node. Additionally, frac and frac2 are the fractions of the CURRENT PIECE of the line that was being tested, and will add to (approximately) 1. When midf is calculated, frac and frac2 are converted to reflect the fraction of the WHOLE line being traced. However, the interpolated vector is based on the CURRENT endpoints so uses frac and frac2 to find the actual splitting point.

Definition at line 836 of file tracing.c.

References AXIAL, DIST_EPSILON, DotProduct, boxtrace_s::extents, trace_s::fraction, boxtrace_s::ispoint, LEAFNODE, MAX_MAP_NODES, MAX_MAP_PLANES, boxtrace_s::tile, TR_TraceToLeaf(), boxtrace_s::trace, type, and VectorInterpolation.

Referenced by TR_BoxTrace().

static void TR_TestBoxInBrush	(	boxtrace_t *	traceData,
		cBspBrush_t *	brush
	)			`[static]`

See also:: CM_TraceToLeaf

Todo:: special case for axial

Definition at line 695 of file tracing.c.

References trace_s::allsolid, cBspBrush_s::contentFlags, trace_s::contentFlags, DotProduct, cBspBrush_s::firstbrushside, trace_s::fraction, i, boxtrace_s::maxs, boxtrace_s::mins, cBspBrush_s::numsides, ofs, qtrue, boxtrace_s::start, trace_s::startsolid, boxtrace_s::tile, and boxtrace_s::trace.

Referenced by TR_TestInLeaf().

static void TR_TestInLeaf	(	boxtrace_t *	traceData,
		int32_t	leafnum
	)			`[static]`

See also:: CM_TestBoxInBrush

Definition at line 788 of file tracing.c.

References checkcount, cBspBrush_s::checkcount, cBspBrush_s::contentFlags, boxtrace_s::contents, trace_s::fraction, LEAFNODE, boxtrace_s::rejects, boxtrace_s::tile, TR_TestBoxInBrush(), and boxtrace_s::trace.

Referenced by TR_BoxTrace().

qboolean TR_TestLine	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	stop,
		const int	levelmask
	)

Checks traces against the world.

Parameters:

`[in]`	start	The position to start the trace.
`[in]`	stop	The position where the trace ends.
`[in]`	levelmask	Indicates which special levels, if any, to include in the trace.

Note:: Special levels are LEVEL_ACTORCLIP and LEVEL_WEAPONCLIP.

See also:: TR_TestLine_r

Returns:: qfalse if not blocked

Definition at line 283 of file tracing.c.

References mapTiles_t::mapTiles, mapTiles_t::numTiles, qfalse, qtrue, and TR_TileTestLine().

Referenced by CL_TestLine(), CM_EntTestLine(), and SV_TestLine().

int TR_TestLine_r	(	TR_TILE_TYPE *	tile,
		int32_t	nodenum,
		const vec3_t	start,
		const vec3_t	stop
	)

Parameters:

`[in]`	tile	The map tile containing the structures to be traced.
`[in]`	nodenum	Node index
`[in]`	start	The position to start the trace.
`[in]`	stop	The position where the trace ends.

Returns:: zero if the line is not blocked, else a positive value

See also:: TR_TestLineDist_r; CM_TestLine

Definition at line 181 of file tracing.c.

References tnode_s::children, tnode_s::dist, DotProduct, tnode_s::normal, ON_EPSILON, PLANE_NONE, PLANE_X, PLANE_Y, PLANE_Z, TR_TestLine_r(), tnode_s::type, and VectorInterpolation.

Referenced by TR_TestLine_r(), TR_TestLineSingleTile(), and TR_TileTestLine().

static int TR_TestLineDist_r	(	TR_TILE_TYPE *	tile,
		int32_t	nodenum,
		const vec3_t	start,
		const vec3_t	stop,
		vec3_t	tr_end
	)			`[static]`

Parameters:

`[in]`	tile	The map tile containing the structures to be traced.
`[in]`	nodenum	Node index
`[in]`	start	The position to start the trace.
`[in]`	stop	The position where the trace ends.
`[in,out]`	tr_end	used to hold the point on a line that an obstacle is encountered.

See also:: TR_TestLine_r; TR_TestLineDM

Definition at line 311 of file tracing.c.

References tnode_s::children, tnode_s::dist, tnode_s::normal, ON_EPSILON, PLANE_NONE, PLANE_X, PLANE_Y, PLANE_Z, tnode_s::type, VectorCopy, VectorInterpolation, and VectorNearer().

Referenced by TR_TileTestLineDM().

qboolean TR_TestLineDM	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	stop,
		vec3_t	end,
		const int	levelmask
	)

Checks traces against the world, gives hit position back.

Parameters:

`[in]`	start	The position to start the trace.
`[in]`	stop	The position where the trace ends.
`[out]`	end	The position where the trace hits a object or the stop position if nothing is in the line.
`[in]`	levelmask	Indicates which special levels, if any, to include in the trace.

See also:: TR_TestLineDM; CL_ActorMouseTrace

Returns:: qfalse if no connection between start and stop - 1 otherwise

Definition at line 435 of file tracing.c.

References EQUAL_EPSILON, mapTiles_t::mapTiles, mapTiles_t::numTiles, qfalse, qtrue, TR_TileTestLineDM(), VectorCompareEps(), VectorCopy, and VectorNearer().

Referenced by CM_EntTestLineDM().

trace_t TR_TileBoxTrace	(	TR_TILE_TYPE *	myTile,
		const vec3_t	start,
		const vec3_t	end,
		const vec3_t	mins,
		const vec3_t	maxs,
		const int	levelmask,
		const int	brushmask,
		const int	brushreject
	)

Traces all submodels in the specified tile. Provides for a short circuit if the trace tries to move past fraction to save time.

Parameters:

`[in]`	myTile	The tile being traced
`[in]`	start	trace start vector
`[in]`	end	trace end vector
`[in]`	mins	box mins
`[in]`	maxs	box maxs
`[in]`	levelmask	Selects which submodels get scanned.
`[in]`	brushmask	brushes the trace should stop at (see MASK_*)
`[in]`	brushreject	brushes the trace should ignore (see MASK_*)
`[in]`	fraction	The furthest distance needed to trace before we stop. We assume that a brush was already hit at fraction.

Definition at line 1063 of file tracing.c.

References chead_s::cnode, trace_s::fraction, i, chead_s::level, LEVEL_LASTVISIBLE, and TR_BoxTrace().

Referenced by CM_CompleteBoxTrace().

static qboolean TR_TileTestLine	(	TR_TILE_TYPE *	tile,
		const vec3_t	start,
		const vec3_t	stop,
		const int	levelmask
	)			`[static]`

Tests to see if a line intersects any brushes in a tile.

Parameters:

`[in]`	tile	The map tile containing the structures to be traced.
`[in]`	start	The position to start the trace.
`[in]`	stop	The position where the trace ends.
`[in]`	levelmask

Returns:: true if the line is blocked

Note:: This function uses levels and levelmasks. The levels are as following: 0-255: brushes are assigned to a level based on their assigned viewing levels. A brush with no levels assigned will be stuck in 0, a brush viewable from all 8 levels will be in 255, and so on. Each brush will only appear in one level. 256: weaponclip-level 257: actorclip-level

The levelmask is used to determine which levels AND which, if either, clip to trace through. The mask bits are as follows: 0x0FF: Level bits. If any bits are set then a brush's level ANDed with the levelmask, then that level is traced. It could possibly be used to speed up traces. 0x100: Actorclip bit. If this bit is set, the actorclip level will be traced. 0x200: Weaponclip bit. If this bit is set, the weaponclip level will be traced.

Definition at line 252 of file tracing.c.

References i, LEVEL_ACTORCLIP, LEVEL_LIGHTCLIP, LEVEL_WEAPONCLIP, qfalse, qtrue, TL_FLAG_ACTORCLIP, TL_FLAG_REGULAR_LEVELS, TL_FLAG_WEAPONCLIP, and TR_TestLine_r().

Referenced by TR_TestLine().

static qboolean TR_TileTestLineDM	(	TR_TILE_TYPE *	tile,
		const vec3_t	start,
		const vec3_t	stop,
		vec3_t	end,
		const int	levelmask
	)			`[static]`

Checks traces against the world, gives hit position back.

Parameters:

`[in]`	tile	The map tile containing the structures to be traced.
`[in]`	start	The position to start the trace.
`[in]`	stop	The position where the trace ends.
`[out]`	end	The position where the trace hits a object or the stop position if nothing is in the line.
`[in]`	levelmask	The bitmask of the levels (1<<[0-7]) to trace for

See also:: TR_TestLineDM; CL_ActorMouseTrace

Returns:: qfalse if no connection between start and stop - 1 otherwise

Definition at line 391 of file tracing.c.

References EQUAL_EPSILON, i, LEVEL_ACTORCLIP, LEVEL_WEAPONCLIP, qfalse, qtrue, TL_FLAG_ACTORCLIP, TL_FLAG_REGULAR_LEVELS, TL_FLAG_WEAPONCLIP, TR_TestLineDist_r(), VectorCompareEps(), VectorCopy, and VectorNearer().

Referenced by TR_TestLineDM().

static void TR_TraceToLeaf	(	boxtrace_t *	traceData,
		int32_t	leafnum
	)			`[static]`

This function checks if the specified leaf matches any mask specified in traceData.contents. and does not contain any mask specified in traceData.rejects If so, each brush in the leaf is examined to see if it is intersected by the line drawn in TR_RecursiveHullCheck or is within the bounding box set in trace_mins and trace_maxs with the origin on the line.

Parameters: