model tracing and bounding More...

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

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. More...

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 end)

static bool	TR_TileTestLine (TR_TILE_TYPE *tile, const vec3_t start, const vec3_t end, const int levelmask)
	Tests to see if a line intersects any brushes in a tile. More...

bool	TR_TestLine (mapTiles_t *mapTiles, const vec3_t start, const vec3_t end, const int levelmask)
	Checks traces against the world. More...

static int	TR_TestLineDist_r (TR_TILE_TYPE *tile, int32_t nodenum, const vec3_t start, const vec3_t end, vec3_t tr_end)

static bool	TR_TileTestLineDM (TR_TILE_TYPE *tile, const vec3_t start, const vec3_t end, vec3_t hit, const int levelmask)
	Checks traces against the world, gives hit position back. More...

bool	TR_TestLineDM (mapTiles_t *mapTiles, const vec3_t start, const vec3_t end, vec3_t hit, const int levelmask)
	Checks traces against the world, gives hit position back. More...

int	TR_BoxOnPlaneSide (const vec3_t mins, const vec3_t maxs, const TR_PLANE_TYPE *plane)
	Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH. More...

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. More...

static int	TR_BoxLeafnums_headnode (boxtrace_t traceData, int32_t list, int listsize, int32_t headnode)
	Fill a list of leafnodes that the trace touches. More...

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. More...

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. More...

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. More...

trace_t	TR_BoxTrace (boxtrace_t &traceData, const Line &traceLine, const AABB &traceBox, const int headnode, 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. More...

trace_t	TR_TileBoxTrace (TR_TILE_TYPE *myTile, const Line &traceLine, const AABB &aabb, 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. More...

Variables
static int	checkcount

Detailed Description

model tracing and bounding

Note: collision detection code

Definition in file tracing.cpp.

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
	)

static

Fill a list of leafnodes that the trace touches.

Parameters

[in]	traceData	both parameters and results of the trace
[out]	list	The list to fill
[in]	listsize	Maximum size of that list
[in]	headnode	if < 0 we are in a leaf node

Definition at line 633 of file tracing.cpp.

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 589 of file tracing.cpp.

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 542 of file tracing.cpp.

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

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

trace_t TR_BoxTrace	(	boxtrace_t &	traceData,
		const Line &	traceLine,
		const AABB &	traceBox,
		const int	headnode,
		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]	traceData	All parameters of the trace; also stores some intermediate results
[in]	traceLine	The trace start and end vector
[in]	traceBox	The box we shove through the world
[in]	headnode	if < 0 we are in a leaf node
[in]	fraction	The furthest distance needed to trace before we stop.

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

Definition at line 1003 of file tracing.cpp.

References boxtrace_s::absmaxs, boxtrace_s::absmins, trace_s::allsolid, checkcount, Com_Error(), 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, boxtrace_s::offset, Line::start, boxtrace_s::start, boxtrace_s::tile, TR_BoxLeafnums_headnode(), TR_RecursiveHullCheck(), TR_TestInLeaf(), boxtrace_s::trace, VectorAdd, VectorClear, VectorCopy, VectorEmpty, VectorEqual, 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 nullptr.

Definition at line 122 of file tracing.cpp.

References tnode_s::children, Com_Error(), Com_Printf(), tnode_s::dist, ERR_DROP, i, level, 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 656 of file tracing.cpp.

References trace_s::allsolid, cBspBrush_s::brushContentFlags, 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, trace_s::plane, trace_s::planenum, 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 83 of file tracing.cpp.

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 891 of file tracing.cpp.

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 759 of file tracing.cpp.

References trace_s::allsolid, cBspBrush_s::brushContentFlags, trace_s::contentFlags, DotProduct, cBspBrush_s::firstbrushside, trace_s::fraction, i, boxtrace_s::maxs, boxtrace_s::mins, cBspBrush_s::numsides, 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 845 of file tracing.cpp.

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

Referenced by TR_BoxTrace().

bool TR_TestLine	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	end,
		const int	levelmask
	)

Checks traces against the world.

Parameters

[in]	mapTiles	List of tiles the current (RMA-)map is composed of
[in]	start	The position to start the trace.
[in]	end	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: false if not blocked

Definition at line 310 of file tracing.cpp.

References mapTiles_s::mapTiles, mapTiles_s::numTiles, 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	end
	)

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]	end	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 209 of file tracing.cpp.

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	end,
		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]	end	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 336 of file tracing.cpp.

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().

bool TR_TestLineDM	(	mapTiles_t *	mapTiles,
		const vec3_t	start,
		const vec3_t	end,
		vec3_t	hit,
		const int	levelmask
	)

Checks traces against the world, gives hit position back.

Parameters

[in]	mapTiles	List of tiles the current (RMA-)map is composed of
[in]	start	The position to start the trace.
[in]	end	The position where the trace ends.
[out]	hit	The position where the trace hits a object or the 'end' 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: false if no connection between start and end - 1 otherwise

Definition at line 458 of file tracing.cpp.

References EQUAL_EPSILON, mapTiles_s::mapTiles, mapTiles_s::numTiles, TR_TileTestLineDM(), VectorCompareEps(), VectorCopy, and VectorNearer().

Referenced by CM_EntTestLineDM().

trace_t TR_TileBoxTrace	(	TR_TILE_TYPE *	myTile,
		const Line &	traceLine,
		const AABB &	aabb,
		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]	traceLine	The trace start and end vectors
[in]	aabb	The box we are moving through the world
[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_*)

Definition at line 1067 of file tracing.cpp.

References chead_s::cnode, trace_s::fraction, i, boxtrace_s::init(), chead_s::level, LEVEL_LASTVISIBLE, boxtrace_s::setLineAndBox(), tr, and TR_BoxTrace().

Referenced by CM_CompleteBoxTrace().

static bool TR_TileTestLine	(	TR_TILE_TYPE *	tile,
		const vec3_t	start,
		const vec3_t	end,
		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]	end	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 279 of file tracing.cpp.

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

Referenced by TR_TestLine().

static bool TR_TileTestLineDM	(	TR_TILE_TYPE *	tile,
		const vec3_t	start,
		const vec3_t	end,
		vec3_t	hit,
		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]	end	The position where the trace ends.
[out]	hit	The position where the trace hits a object or the 'end' 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: false if no connection between start and end - 1 otherwise

Definition at line 414 of file tracing.cpp.

References EQUAL_EPSILON, i, LEVEL_ACTORCLIP, LEVEL_WEAPONCLIP, 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

[in]	traceData	both parameters and results of the trace
[in]	leafnum	the leaf index that we are looking in for a hit against

See also: CM_ClipBoxToBrush; CM_TestBoxInBrush; CM_RecursiveHullCheck

Definition at line 811 of file tracing.cpp.

References cBspBrush_s::brushContentFlags, cBspBrush_s::checkcount, checkcount, boxtrace_s::contents, trace_s::fraction, LEAFNODE, MASK_ALL, boxtrace_s::rejects, boxtrace_s::tile, TR_ClipBoxToBrush(), and boxtrace_s::trace.

Referenced by TR_RecursiveHullCheck().

Variable Documentation

int checkcount

static

Note: For multi-check avoidance.

Todo:: not thread safe

Definition at line 72 of file tracing.cpp.

Referenced by TR_BoxTrace(), TR_TestInLeaf(), and TR_TraceToLeaf().

Data Structures

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

Function Documentation

Variable Documentation