#include <assert.h>
#include "map.h"
#include "bspbrush.h"
#include "common/shared.h"
#include "common/scriplib.h"
#include "common/polylib.h"
#include "common/bspfile.h"
#include "../../common/tracing.h"

Include dependency graph for bsp.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	node_t
struct	tree_t

Functions
byte	GetLevelFlagsFromBrush (const mapbrush_t *brush)
	Extract the level flags (1-8) from the content flags of the given brush.
void	LoadMapFile (const char *filename)
void	WriteMapFile (const char *filename)
uint16_t	FindOrCreateFloatPlane (vec3_t normal, vec_t dist)
int	MapBrushesBounds (const int startbrush, const int endbrush, const int level, const AABB &clipBox, AABB &bBox)
	sets mins and maxs to the smallest sizes that can contain all brushes from startbrush to endbrush that are in a given level.
bspbrush_t *	MakeBspBrushList (int startbrush, int endbrush, int level, const AABB &clip)
bspbrush_t *	ChopBrushes (bspbrush_t *head)
	Carves any intersecting solid brushes into the minimum number of non-intersecting brushes.
uint32_t	VisibleContents (uint32_t contents)
	Returns the single content bit of the strongest visible content present.
void	MarkVisibleSides (tree_t *tree, int start, int end)
void	FreePortal (portal_t *p)
void	MakeTreePortals (tree_t *tree)
void	RemovePortalFromNode (portal_t portal, node_t l)
	Removes references to the given portal from the given node.
void	SetModelNumbers (void)
	Set the model numbers for SOLID_BSP or SOLID_TRIGGER entities like func_door or func_breakable.
void	BeginBSPFile (void)
	Starts a new bsp file.
int	WriteBSP (node_t *headnode)
	copies working data for a bsp tree into the structures used to create the bsp file.
void	EndBSPFile (const char *filename)
	Finishes a new bsp and writes to disk.
void	BeginModel (int entityNum)
	Sets up a new brush model.
void	EndModel (void)
	Finish a model's processing.
void	EmitBrushes (void)
	Writes the brush list to the bsp.
void	EmitPlanes (void)
	Emits planes to the bsp file.
void	MakeFaces (node_t *headnode)
void	FixTjuncs (node_t *headnode)
int	GetEdge (int v1, int v2, const face_t *f)
void	FreeFace (face_t *f)
node_t *	AllocNode (void)
tree_t *	AllocTree (void)
	Allocates a tree and initializes it.
tree_t *	BuildTree (bspbrush_t *brushlist, const vec3_t mins, const vec3_t maxs)
	The incoming list will be freed before exiting.
void	FreeTree (tree_t *tree)
void	PruneNodes (node_t *node)
void	MakeTracingNodes (int levels)
	Use the bsp node structure to reconstruct efficient tracing structures that are used for fast visibility and pathfinding checks.
void	CloseTracingNodes (void)
void	DoRouting (void)
	Calculates the routing of a map.
void	ProcessModels (const char *filename)

Function Documentation

◆ AllocNode()

node_t * AllocNode ( void )

See also: AllocBrush; AllocTree

Definition at line 34 of file tree.cpp.

References Mem_AllocType.

Referenced by BuildTree(), and BuildTree_r().

◆ AllocTree()

tree_t * AllocTree ( void )

Allocates a tree and initializes it.

Definition at line 92 of file tree.cpp.

References tree_t::aabb, Mem_AllocType, and AABB::setNegativeVolume().

Referenced by BuildTree().

◆ BeginBSPFile()

void BeginBSPFile ( void )

Starts a new bsp file.

See also: EndBSPFile

Definition at line 303 of file writebsp.cpp.

References CONTENTS_SOLID, curTile, and mapTiles.

Referenced by ProcessModels().

◆ BeginModel()

void BeginModel ( int entityNum )

Sets up a new brush model.

See also: EndModel

Definition at line 353 of file writebsp.cpp.

References AABB::add(), curTile, dBspModel_t::dbmBox, entities, entityNum, entity_t::firstbrush, dBspModel_t::firstface, firstmodeledge, mapbrushes, MAX_MAP_MODELS, mapbrush_t::mbBox, entity_t::numbrushes, mapbrush_t::numsides, AABB::set(), AABB::setNegativeVolume(), and Sys_Error().

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ BuildTree()

tree_t * BuildTree	(	bspbrush_t *	brushlist,
		const vec3_t	mins,
		const vec3_t	maxs )

The incoming list will be freed before exiting.

Definition at line 182 of file tree.cpp.

References tree_t::aabb, AABB::add(), AllocNode(), AllocTree(), BrushFromBounds(), BrushlistCalcStats(), BuildTree_r(), c_nodes, c_nonvis, tree_t::headnode, AABB::setNegativeVolume(), VERB_EXTRA, Verb_Printf(), and node_t::volume.

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ ChopBrushes()

bspbrush_t * ChopBrushes ( bspbrush_t * head )

Carves any intersecting solid brushes into the minimum number of non-intersecting brushes.

Definition at line 376 of file csg.cpp.

References AddBrushListToTail(), BrushesDisjoint(), BrushGE(), CountBrushList(), CullList(), FreeBrushList(), bspbrush_t::next, SubtractBrush(), VERB_EXTRA, and Verb_Printf().

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ CloseTracingNodes()

void CloseTracingNodes ( void )

See also: MakeTnodes

Definition at line 65 of file trace.cpp.

References curTile, and Mem_Free.

Referenced by LightWorld(), and MakeTracingNodes().

◆ DoRouting()

void DoRouting ( void )

Calculates the routing of a map.

See also: CheckUnit; CheckConnections; ProcessWorldModel

This is needed for tracing to work!!!

Note: LEVEL_TRACING is not an actual level

Definition at line 115 of file routing.cpp.

References ACTOR_MAX_SIZE, baseFilename, CELL_HEIGHT, CheckConnectionsThread(), CheckUnitThread(), CompressRouting(), config, CORE_DIRECTIONS, curTile, data, debugTrace, EmitBrushes(), EmitPlanes(), i, LEVEL_ACTORCLIP, LittleLong, MakeTracingNodes(), mapTiles, MAX_MAP_ROUTING, AABB::maxs, AABB::mins, Nmap, PATHFINDING_HEIGHT, PATHFINDING_WIDTH, PopInfo(), PushInfo(), RT_GetMapSize(), RT_IS_BIDIRECTIONAL, RT_WriteCSVFiles(), RunSingleThreadOn(), UNIT_HEIGHT, VecToPos, VectorCopy, VectorSet, VERB_NORMAL, wpMaxs, and wpMins.

Referenced by ProcessWorldModel().

◆ EmitBrushes()

void EmitBrushes ( void )

Writes the brush list to the bsp.

Definition at line 236 of file writebsp.cpp.

References cBspBrush_t::brushContentFlags, dBspBrush_t::brushContentFlags, cBspBrush_t::checkcount, mapbrush_t::contentFlags, curTile, FindOrCreateFloatPlane(), cBspBrush_t::firstbrushside, dBspBrush_t::firstbrushside, i, mapbrushes, MAX_MAP_BRUSHSIDES, AABB::maxs, mapbrush_t::mbBox, AABB::mins, nummapbrushes, cBspBrush_t::numsides, dBspBrush_t::numsides, mapbrush_t::numsides, OBJZERO, mapbrush_t::original_sides, dBspBrushSide_t::planenum, Sys_Error(), dBspBrushSide_t::texinfo, vec3_origin, and VectorCopy.

Referenced by DoRouting(), and EndBSPFile().

◆ EmitPlanes()

void EmitPlanes ( void )

Emits planes to the bsp file.

Note: There is no oportunity to discard planes, because all of the original brushes will be saved in the map.

Definition at line 41 of file writebsp.cpp.

References curTile, dBspPlane_t::dist, plane_t::dist, i, mapplanes, dBspPlane_t::normal, plane_t::normal, nummapplanes, dBspPlane_t::type, plane_t::type, and VectorCopy.

Referenced by DoRouting(), and EndBSPFile().

◆ EndBSPFile()

void EndBSPFile ( const char * filename )

Finishes a new bsp and writes to disk.

See also: BeginBSPFile

Definition at line 336 of file writebsp.cpp.

References EmitBrushes(), EmitPlanes(), UnparseEntities(), VERB_LESS, Verb_Printf(), and WriteBSPFile().

Referenced by ProcessModels().

◆ EndModel()

void EndModel ( void )

Finish a model's processing.

See also: BeginModel

Definition at line 387 of file writebsp.cpp.

References curTile, dBspModel_t::firstface, and dBspModel_t::numfaces.

Referenced by ProcessSubModel().

◆ FindOrCreateFloatPlane()

uint16_t FindOrCreateFloatPlane	(	vec3_t	normal,
		vec_t	dist )

Definition at line 194 of file map.cpp.

References CreateNewFloatPlane(), GetPlaneHashValueForDistance(), hash, plane_t::hash_chain, i, index, mapplanes, PLANE_HASHES, PlaneEqual(), planehash, and SnapPlane().

Referenced by AddBrushBevels(), AdjustBrushesForOrigin(), BrushFromBounds(), EmitBrushes(), MakeBspBrushList(), and PlaneFromPoints().

◆ FixTjuncs()

void FixTjuncs ( node_t * headnode )

See also: ProcessSubModel; ConstructLevelNodes_r

Definition at line 370 of file faces.cpp.

References c_badstartverts, c_degenerate, c_facecollapse, c_faceoverflows, c_tjunctions, c_totalverts, c_uniqueverts, config, EmitVertexes_r(), FixEdges_r(), hashverts, OBJZERO, VERB_EXTRA, and Verb_Printf().

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ FreeFace()

void FreeFace ( face_t * f )

Definition at line 133 of file faces.cpp.

References c_faces, f, FreeWinding(), and Mem_Free.

Referenced by FreeTree_r().

◆ FreePortal()

void FreePortal ( portal_t * p )

See also: AllocPortal

Definition at line 52 of file portals.cpp.

References c_active_portals, FreeWinding(), Mem_Free, threadstate, and portal_t::winding.

Referenced by FreeTreePortals_r().

◆ FreeTree()

void FreeTree ( tree_t * tree )

Definition at line 102 of file tree.cpp.

References FreeTree_r(), FreeTreePortals_r(), tree_t::headnode, and Mem_Free.

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ GetEdge()

int GetEdge	(	int	v1,
		int	v2,
		const face_t *	f )

See also: EmitFace.

Note: Don't allow four way edges

Definition at line 399 of file faces.cpp.

References config, curTile, edgefaces, f, firstmodeledge, i, MAX_MAP_EDGES, Sys_Error(), and dBspEdge_t::v.

Referenced by EmitFace().

◆ GetLevelFlagsFromBrush()

byte GetLevelFlagsFromBrush ( const mapbrush_t * brush )

Extract the level flags (1-8) from the content flags of the given brush.

Parameters

brush The brush to extract the level flags from

Returns: The level flags (content flags) of the given brush

Definition at line 277 of file map.cpp.

References mapbrush_t::contentFlags.

◆ LoadMapFile()

void LoadMapFile ( const char * filename )

See also: WriteMapFile; ParseMapEntity

Definition at line 1197 of file map.cpp.

References AABB_STRING, AABB::add(), AABB::asIntString(), brushsides, c_boxbevels, c_edgebevels, Com_Printf(), config, curTile, entities, footstepsCnt, GetUMPName(), i, LoadScriptFile(), mapbrushes, mapplanes, mapTiles, materialsCnt, MAX_TOKEN_CHARS, MAX_WORLD_WIDTH, num_entities, nummapbrushes, nummapbrushsides, nummapplanes, OBJZERO, ParseMapEntity(), ParseUMP(), AABB::setNegativeVolume(), side_brushtextures, ValueForKey(), VERB_EXTRA, and Verb_Printf().

Referenced by main().

◆ MakeBspBrushList()

bspbrush_t * MakeBspBrushList	(	int	startbrush,
		int	endbrush,
		int	level,
		const AABB &	clip )

Definition at line 292 of file csg.cpp.

References AllocBrush(), bspbrush_t::brBox, ClipBrushToBox(), AABB::contains(), mapbrush_t::contentFlags, CopyWinding(), FindOrCreateFloatPlane(), mapbrush_t::finished, i, IsInLevel(), level, mapbrushes, maxplanenums, AABB::maxs, mapbrush_t::mbBox, minplanenums, AABB::mins, bspbrush_t::next, bspbrush_t::numsides, mapbrush_t::numsides, bspbrush_t::original, mapbrush_t::original_sides, AABB::set(), bspbrush_t::sides, SURF_HINT, side_t::surfaceFlags, VERB_DUMP, Verb_Printf(), side_t::visible, and side_t::winding.

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ MakeFaces()

void MakeFaces ( node_t * headnode )

Definition at line 764 of file faces.cpp.

References c_merge, c_nodefaces, c_subdivide, MakeFaces_r(), VERB_EXTRA, and Verb_Printf().

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ MakeTracingNodes()

void MakeTracingNodes ( int levels )

Use the bsp node structure to reconstruct efficient tracing structures that are used for fast visibility and pathfinding checks.

Note: curTile->tnodes is expected to have enough memory malloc'ed for the function to work.

See also: BuildTracingNode_r

Definition at line 38 of file trace.cpp.

References CloseTracingNodes(), curTile, dBspModel_t::headnode, i, LEVEL_ACTORCLIP, LEVEL_LIGHTCLIP, LEVEL_MAX, Mem_AllocTypeN, dBspModel_t::numfaces, and TR_BuildTracingNode_r().

Referenced by DoRouting(), and LightWorld().

◆ MakeTreePortals()

void MakeTreePortals ( tree_t * tree )

Definition at line 391 of file portals.cpp.

References tree_t::headnode, MakeHeadnodePortals(), and MakeTreePortals_r().

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ MapBrushesBounds()

int MapBrushesBounds	(	const int	startbrush,
		const int	endbrush,
		const int	level,
		const AABB &	clipBox,
		AABB &	bBox )

sets mins and maxs to the smallest sizes that can contain all brushes from startbrush to endbrush that are in a given level.

Parameters

[in]	startbrush	the index of the first brush to check.
[in]	endbrush	the index after the last brush to check.
[in]	level	the level that we are searching for brushes in. -1 for skipping the levelflag check.
[in]	clipBox	the absolute lowest and highest boundaries to allow for brushes.
[out]	bBox	the max boundaries for all accepted brushes within the clipped bounds.

See also: ProcessSubModel; IsInLevel

Definition at line 264 of file csg.cpp.

References AABB::add(), AABB::contains(), mapbrush_t::contentFlags, mapbrush_t::finished, i, IsInLevel(), level, mapbrushes, mapbrush_t::mbBox, and AABB::setNegativeVolume().

Referenced by ConstructLevelNodes_r().

◆ MarkVisibleSides()

void MarkVisibleSides	(	tree_t *	tree,
		int	start,
		int	end )

Definition at line 482 of file portals.cpp.

References tree_t::headnode, i, mapbrushes, MarkVisibleSides_r(), mapbrush_t::numsides, mapbrush_t::original_sides, VERB_EXTRA, and Verb_Printf().

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ ProcessModels()

void ProcessModels ( const char * filename )

See also: ProcessWorldModel; ProcessSubModel

Definition at line 106 of file bsp.cpp.

References BeginBSPFile(), config, curTile, EndBSPFile(), entities, num_entities, ProcessSubModel(), ProcessWorldModel(), VERB_EXTRA, and Verb_Printf().

Referenced by main().

◆ PruneNodes()

void PruneNodes ( node_t * node )

See also: PruneNodes_r

Definition at line 261 of file tree.cpp.

References c_pruned, PruneNodes_r(), VERB_EXTRA, and Verb_Printf().

Referenced by ConstructLevelNodes_r().

◆ RemovePortalFromNode()

void RemovePortalFromNode	(	portal_t *	portal,
		node_t *	l )

Removes references to the given portal from the given node.

Parameters

[in,out]	portal	The portal to remove from the node
[in,out]	l	The node to remove the portal from

See also: AddPortalToNodes

Definition at line 102 of file portals.cpp.

References portal_t::next, portal_t::nodes, node_t::portals, and Sys_Error().

Referenced by FreeTreePortals_r(), and SplitNodePortals().

◆ SetModelNumbers()

void SetModelNumbers ( void )

Set the model numbers for SOLID_BSP or SOLID_TRIGGER entities like func_door or func_breakable.

Definition at line 217 of file writebsp.cpp.

References Com_sprintf(), entities, i, num_entities, and SetKeyValue().

Referenced by main().

◆ VisibleContents()

uint32_t VisibleContents ( uint32_t contents )

Returns the single content bit of the strongest visible content present.

Definition at line 64 of file portals.cpp.

References i, and LAST_VISIBLE_CONTENTS.

Referenced by FaceFromPortal(), and FindPortalSide().

◆ WriteBSP()

int WriteBSP ( node_t * headnode )

copies working data for a bsp tree into the structures used to create the bsp file.

Parameters

[in] headnode the top-most node in this bsp tree

Returns: the index to the head node created.

Definition at line 195 of file writebsp.cpp.

References c_facenodes, c_nofaces, curTile, EmitDrawNode_r(), oldfaces, VERB_EXTRA, and Verb_Printf().

Referenced by ConstructLevelNodes_r(), and ProcessSubModel().

◆ WriteMapFile()

void WriteMapFile ( const char * filename )

See also: LoadMapFile; FixErrors

Definition at line 1055 of file map.cpp.

References Check_ExtraBrushesForWorldspawn(), entities, entity_t::epairs, f, FILE_WRITE, entity_t::firstbrush, FS_OpenFile(), FS_Printf(), i, mapbrushes, Mem_Free, num_entities, entity_t::numbrushes, entity_t::skip, mapbrush_t::skipWriteBack, Sys_Error(), VERB_NORMAL, Verb_Printf(), WriteMapBrush(), and WriteMapEntities().

Referenced by main().

Variable Documentation

◆ brush_end

int brush_end

Definition at line 77 of file bsp.h.

Referenced by ConstructLevelNodes_r(), and ProcessWorldModel().

◆ brush_start

int brush_start

extern

Definition at line 29 of file levels.cpp.

Referenced by ConstructLevelNodes_r(), and ProcessWorldModel().

◆ brushsides

side_t brushsides[MAX_MAP_SIDES]

extern

Definition at line 37 of file map.cpp.

Referenced by AddBrushBevels(), AdjustBrushesForOrigin(), Check_SetNodraw(), Check_SurfProp(), Check_SurfProps(), CheckFlagsBasedOnTextures(), CheckMixedFaceContents(), CheckTexturesBasedOnFlags(), LoadMapFile(), ParseBrush(), and WriteMapBrush().

◆ curTile

dMapTile_t* curTile

extern

Note: used as a shortcut so the tile being processed does not need to be repeatedly passed between functions.

Definition at line 32 of file bsp.cpp.

Referenced by BeginBSPFile(), BeginModel(), BuildFaceExtents(), BuildFacelights(), BuildNodeChildren(), BuildPatch(), BuildPatches(), BuildVertexNormals(), CalcLightinfoExtents(), CalcLightinfoVectors(), CalcTextureReflectivity(), CalcTextureSize(), CloseTracingNodes(), DoRouting(), EmissiveLight(), EmitBrushes(), EmitDrawNode_r(), EmitFace(), EmitFaceVertexes(), EmitLeaf(), EmitPlanes(), EndModel(), ExportLightmap(), FaceFromPortal(), FacesWithVert(), FinalLightFace(), FixFaceEdges(), GetEdge(), GetVertexnum(), HasLight(), LightWorld(), LoadBSPFile(), LoadMapFile(), MakeTracingNodes(), ParseEntities(), PopInfo(), PrintBSPFileSizes(), ProcessLevel(), ProcessModels(), ProcessSubModel(), ProcessWorldModel(), PushInfo(), SampleNormal(), SubdivideFace(), SwapBSPFile(), TestEdge(), TexinfoForBrushTexture(), TR_TestLineSingleTile(), UnparseEntities(), WindingFromFace(), WriteBSP(), and WriteBSPFile().

◆ mapbrushes

◆ mapplanes

plane_t mapplanes[MAX_MAP_PLANES]

extern

an index of the planes containing the faces of the brushes

Definition at line 43 of file map.cpp.

Referenced by AddBrushBevels(), AdjustBrushesForOrigin(), BaseWindingForNode(), BrushVolume(), Check_IsPointInsideBrush(), Check_MapBrushVolume(), Check_SidePointsDown(), Check_WindingIntersects(), CreateBrushWindings(), CreateNewFloatPlane(), DoesPlaneSplitBrush(), EmitPlanes(), FaceFromPortal(), FacingAndCoincidentTo(), FindOrCreateFloatPlane(), FindPortalSide(), LoadMapFile(), MakeBrushWindings(), MakeNodePortal(), MergeNodeFaces(), ParallelAndCoincidentTo(), ParseBrush(), SelectSplitSide(), SplitBrush(), SplitNodePortals(), TestBrushToPlanenum(), and WriteMapBrush().

◆ mapTiles

mapTiles_t mapTiles

extern

Definition at line 33 of file bsp.cpp.

◆ nummapbrushes

int nummapbrushes

extern

◆ nummapbrushsides

int nummapbrushsides

extern

Definition at line 38 of file map.cpp.

Referenced by AddBrushBevels(), Check_Stats(), LoadMapFile(), and ParseBrush().

◆ nummapplanes

int nummapplanes

extern

Definition at line 44 of file map.cpp.

Referenced by Check_Stats(), CreateNewFloatPlane(), EmitPlanes(), and LoadMapFile().

◆ side_brushtextures

brush_texture_t side_brushtextures[MAX_MAP_SIDES]

extern

Definition at line 40 of file map.cpp.

Referenced by AddBrushBevels(), AdjustBrushesForOrigin(), Check_SetNodraw(), Check_SurfProp(), Check_SurfProps(), CheckFlagsBasedOnTextures(), CheckMixedFaceContents(), CheckTexturesBasedOnFlags(), LoadMapFile(), ParseBrush(), and WriteMapBrush().

Variables
dMapTile_t *	curTile
mapTiles_t	mapTiles
plane_t	mapplanes [MAX_MAP_PLANES]
int	nummapplanes
int	nummapbrushes
mapbrush_t	mapbrushes [MAX_MAP_BRUSHES]
int	nummapbrushsides
side_t	brushsides [MAX_MAP_SIDES]
brush_texture_t	side_brushtextures [MAX_MAP_SIDES]
int	brush_start
int	brush_end

Data Structures

Functions

Variables

Function Documentation

◆ AllocNode()

◆ AllocTree()

◆ BeginBSPFile()

◆ BeginModel()

◆ BuildTree()

◆ ChopBrushes()

◆ CloseTracingNodes()

◆ DoRouting()

◆ EmitBrushes()

◆ EmitPlanes()

◆ EndBSPFile()

◆ EndModel()

◆ FindOrCreateFloatPlane()

◆ FixTjuncs()

◆ FreeFace()

◆ FreePortal()

◆ FreeTree()

◆ GetEdge()

◆ GetLevelFlagsFromBrush()

◆ LoadMapFile()

◆ MakeBspBrushList()

◆ MakeFaces()

◆ MakeTracingNodes()

◆ MakeTreePortals()

◆ MapBrushesBounds()

◆ MarkVisibleSides()

◆ ProcessModels()

◆ PruneNodes()

◆ RemovePortalFromNode()

◆ SetModelNumbers()

◆ VisibleContents()

◆ WriteBSP()

◆ WriteMapFile()

Variable Documentation

◆ brush_end

◆ brush_start

◆ brushsides

◆ curTile

◆ mapbrushes

◆ mapplanes

◆ mapTiles

◆ nummapbrushes

◆ nummapbrushsides

◆ nummapplanes

◆ side_brushtextures