qbsp.h

/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/


#if defined(WIN32) || defined(_WIN32)
#include <io.h>
#endif
#include <stdlib.h>
#include "l_cmd.h"
#include "l_math.h"
#include "l_poly.h"
#include "l_threads.h"
#include "botlib/l_script.h"
#include "l_bsp_ent.h"
#include "q2files.h"
#include "l_mem.h"
#include "l_utils.h"
#include "l_log.h"
#include "l_qfiles.h"

#define BSPC_VERSION		"2.1h"

#ifdef SMOKINGUNS
#define SMOKINGUNS_MESSAGE	"Customized for Smokin'Guns v0.2"
#endif

// vsnprintf is ISO/IEC 9899:1999
// abstracting this to make it portable
#ifdef _WIN32
  #define Q_vsnprintf _vsnprintf
  #define Q_snprintf _snprintf
#else
  #define Q_vsnprintf vsnprintf
  #define Q_snprintf snprintf
#endif

#define Com_sprintf (void)Q_snprintf

#define Com_Memset memset
#define Com_Memcpy memcpy

#define ME
#define DEBUG
#define NODELIST
#define SIN

#define MAX_BRUSH_SIDES		128		//maximum number of sides per brush
#define CLIP_EPSILON		0.1
#define MAX_MAP_BOUNDS		65535
#define BOGUS_RANGE			(MAX_MAP_BOUNDS+128)	//somewhere outside the map
#define TEXINFO_NODE		-1		//side is allready on a node
#define PLANENUM_LEAF		-1		//used for leaf nodes
#define MAXEDGES			20		//maximum number of face edges
#define MAX_NODE_BRUSHES	8		//maximum brushes in a node
//side flags
#define SFL_TESTED			1
#define SFL_VISIBLE			2
#define SFL_BEVEL			4
#define SFL_TEXTURED		8
#define SFL_CURVE			16

//map plane
typedef struct plane_s
{
	vec3_t normal;
	vec_t dist;
	int type;
	int signbits;
	struct plane_s	*hash_chain;
} plane_t;
//brush texture
typedef struct
{
	vec_t	shift[2];
	vec_t	rotate;
	vec_t	scale[2];
	char	name[32];
	int		flags;
	int		value;
} brush_texture_t;
//brush side
typedef struct side_s
{
	int				planenum;	// map plane this side is in
	int				texinfo;		// texture reference
	winding_t		*winding;	// winding of this side
	struct side_s	*original;	// bspbrush_t sides will reference the mapbrush_t sides
   int				lightinfo;	// for SIN only
	int				contents;	// from miptex
	int				surf;			// from miptex
	unsigned short flags;		// side flags
} side_t;		//sizeof(side_t) = 36
//map brush
typedef struct mapbrush_s
{
	int		entitynum;
	int		brushnum;

	int		contents;
#ifdef ME
	int		expansionbbox;			//bbox used for expansion of the brush
	int		leafnum;
	int		modelnum;
#endif

	vec3_t	mins, maxs;

	int		numsides;
	side_t	*original_sides;
} mapbrush_t;
//bsp face
typedef struct face_s
{
	struct face_s		*next;		// on node

	// the chain of faces off of a node can be merged or split,
	// but each face_t along the way will remain in the chain
	// until the entire tree is freed
	struct face_s		*merged;	// if set, this face isn't valid anymore
	struct face_s		*split[2];	// if set, this face isn't valid anymore

	struct portal_s	*portal;
	int					texinfo;
#ifdef SIN
   int					lightinfo;
#endif
	int					planenum;
	int					contents;	// faces in different contents can't merge
	int					outputnumber;
	winding_t			*w;
	int					numpoints;
	qboolean				badstartvert;	// tjunctions cannot be fixed without a midpoint vertex
	int					vertexnums[MAXEDGES];
} face_t;
//bsp brush
typedef struct bspbrush_s
{
	struct		bspbrush_s	*next;
	vec3_t		mins, maxs;
	int			side, testside;		// side of node during construction
	mapbrush_t	*original;
	int			numsides;
	side_t		sides[6];			// variably sized
} bspbrush_t;	//sizeof(bspbrush_t) = 44 + numsides * sizeof(side_t)
//bsp node
typedef struct node_s
{
	//both leafs and nodes
	int				planenum;	// -1 = leaf node
	struct node_s	*parent;
	vec3_t			mins, maxs;	// valid after portalization
	bspbrush_t		*volume;		// one for each leaf/node

	// nodes only
	qboolean			detail_seperator;	// a detail brush caused the split
	side_t			*side;		// the side that created the node
	struct node_s	*children[2];
	face_t			*faces;

	// leafs only
	bspbrush_t		*brushlist;	// fragments of all brushes in this leaf
	int				contents;	// OR of all brush contents
	int				occupied;	// 1 or greater can reach entity
	entity_t			*occupant;	// for leak file testing
	int				cluster;		// for portalfile writing
	int				area;			// for areaportals
	struct portal_s *portals;	// also on nodes during construction
#ifdef NODELIST
	struct node_s *next;			//next node in the nodelist
#endif
#ifdef ME
	int expansionbboxes;			//OR of all bboxes used for expansion of the brushes
	int modelnum;
#endif
} node_t;		//sizeof(node_t) = 80 bytes
//bsp portal
typedef struct portal_s
{
	plane_t plane;
	node_t *onnode;					// NULL = outside box
	node_t *nodes[2];				// [0] = front side of plane
	struct portal_s *next[2];
	winding_t *winding;

	qboolean	sidefound;			// false if ->side hasn't been checked
	side_t *side;					// NULL = non-visible
	face_t *face[2];				// output face in bsp file
#ifdef ME
	struct tmp_face_s *tmpface;		//pointer to the tmpface created for this portal
	int planenum;					//number of the map plane used by the portal
#endif
} portal_t;
//bsp tree
typedef struct
{
	node_t		*headnode;
	node_t		outside_node;
	vec3_t		mins, maxs;
} tree_t;

//=============================================================================
// bspc.c
//=============================================================================

extern	qboolean noprune;
extern	qboolean nodetail;
extern	qboolean fulldetail;
extern	qboolean nomerge;
extern	qboolean nosubdiv;
extern	qboolean nowater;
extern	qboolean noweld;
extern	qboolean noshare;
extern	qboolean notjunc;
extern	qboolean onlyents;
#ifdef ME
extern	qboolean nocsg;
extern	qboolean create_aas;
extern	qboolean freetree;
extern	qboolean lessbrushes;
extern	qboolean nobrushmerge;
extern	qboolean cancelconversion;
extern	qboolean noliquids;
extern	qboolean capsule_collision;
#endif //ME

extern	float subdivide_size;
extern	vec_t microvolume;

extern	char outbase[32];
extern	char source[1024];

//=============================================================================
// map.c
//=============================================================================

#ifdef SMOKINGUNS
#define MAX_MAPFILE_PLANES			512000
#define MAX_MAPFILE_BRUSHES			(65535*2)
#else
#define MAX_MAPFILE_PLANES			256000
#define MAX_MAPFILE_BRUSHES			65535
#endif
#define MAX_MAPFILE_BRUSHSIDES		(MAX_MAPFILE_BRUSHES*8)
#define MAX_MAPFILE_TEXINFO			8192

extern	int			entity_num;

extern	plane_t		mapplanes[MAX_MAPFILE_PLANES];
extern	int			nummapplanes;
extern	int			mapplaneusers[MAX_MAPFILE_PLANES];

extern	int			nummapbrushes;
extern	mapbrush_t	mapbrushes[MAX_MAPFILE_BRUSHES];

extern	vec3_t		map_mins, map_maxs;

extern	int			nummapbrushsides;
extern	side_t		brushsides[MAX_MAPFILE_BRUSHSIDES];
extern	brush_texture_t	side_brushtextures[MAX_MAPFILE_BRUSHSIDES];

#ifdef ME

typedef struct
{
	float	vecs[2][4];		// [s/t][xyz offset]
	int		flags;			// miptex flags + overrides
	int		value;
	char	texture[64];	// texture name (textures/*.wal)
	int		nexttexinfo;	// for animations, -1 = end of chain
} map_texinfo_t;

extern	map_texinfo_t		map_texinfo[MAX_MAPFILE_TEXINFO];
extern	int					map_numtexinfo;
#define NODESTACKSIZE		1024

#define MAPTYPE_QUAKE1		1
#define MAPTYPE_QUAKE2		2
#define MAPTYPE_QUAKE3		3
#define MAPTYPE_HALFLIFE	4
#define MAPTYPE_SIN			5

extern	int nodestack[NODESTACKSIZE];
extern	int *nodestackptr;
extern	int nodestacksize;
extern	int brushmodelnumbers[MAX_MAPFILE_BRUSHES];
extern	int dbrushleafnums[MAX_MAPFILE_BRUSHES];
extern	int dplanes2mapplanes[MAX_MAPFILE_PLANES];

extern	int loadedmaptype;
#endif //ME

extern	int c_boxbevels;
extern	int c_edgebevels;
extern	int c_areaportals;
extern	int c_clipbrushes;
extern	int c_squattbrushes;

//finds a float plane for the given normal and distance
int FindFloatPlane(vec3_t normal, vec_t dist);
//returns the plane type for the given normal
int PlaneTypeForNormal(vec3_t normal);
//returns the plane defined by the three given points
int PlaneFromPoints(int *p0, int *p1, int *p2);
//add bevels to the map brush
void AddBrushBevels(mapbrush_t *b);
//makes brush side windings for the brush
qboolean MakeBrushWindings(mapbrush_t *ob);
//marks brush bevels of the brush as bevel
void MarkBrushBevels(mapbrush_t *brush);
//returns true if the map brush already exists
int BrushExists(mapbrush_t *brush);
//loads a map from a bsp file
int LoadMapFromBSP(struct quakefile_s *qf);
//resets map loading
void ResetMapLoading(void);
//print some map info
void PrintMapInfo(void);
//writes a map file (type depending on loaded map type)
void WriteMapFile(char *filename);

//=============================================================================
// map_q2.c
//=============================================================================

void Q2_ResetMapLoading(void);
//loads a Quake2 map file
void Q2_LoadMapFile(char *filename);
//loads a map from a Quake2 bsp file
void Q2_LoadMapFromBSP(char *filename, int offset, int length);

//=============================================================================
// map_q1.c
//=============================================================================

void Q1_ResetMapLoading(void);
//loads a Quake2 map file
void Q1_LoadMapFile(char *filename);
//loads a map from a Quake1 bsp file
void Q1_LoadMapFromBSP(char *filename, int offset, int length);

//=============================================================================
// map_q3.c
//=============================================================================
void Q3_ResetMapLoading(void);
//loads a map from a Quake3 bsp file
void Q3_LoadMapFromBSP(struct quakefile_s *qf);

//=============================================================================
// map_sin.c
//=============================================================================

void Sin_ResetMapLoading(void);
//loads a Sin map file
void Sin_LoadMapFile(char *filename);
//loads a map from a Sin bsp file
void Sin_LoadMapFromBSP(char *filename, int offset, int length);

//=============================================================================
// map_hl.c
//=============================================================================

void HL_ResetMapLoading(void);
//loads a Half-Life map file
void HL_LoadMapFile(char *filename);
//loads a map from a Half-Life bsp file
void HL_LoadMapFromBSP(char *filename, int offset, int length);

//=============================================================================
// textures.c
//=============================================================================

typedef struct
{
	char	name[64];
	int		flags;
	int		value;
	int		contents;
	char	animname[64];
} textureref_t;

#define	MAX_MAP_TEXTURES	1024

extern	textureref_t	textureref[MAX_MAP_TEXTURES];

int FindMiptex(char *name);
int TexinfoForBrushTexture(plane_t *plane, brush_texture_t *bt, vec3_t origin);
void TextureAxisFromPlane(plane_t *pln, vec3_t xv, vec3_t yv);

//=============================================================================
// csg
//=============================================================================

bspbrush_t *MakeBspBrushList(int startbrush, int endbrush, vec3_t clipmins, vec3_t clipmaxs);
bspbrush_t *ChopBrushes(bspbrush_t *head);
bspbrush_t *InitialBrushList(bspbrush_t *list);
bspbrush_t *OptimizedBrushList(bspbrush_t *list);
void WriteBrushMap(char *name, bspbrush_t *list);
void CheckBSPBrush(bspbrush_t *brush);
void BSPBrushWindings(bspbrush_t *brush);
bspbrush_t *TryMergeBrushes(bspbrush_t *brush1, bspbrush_t *brush2);
tree_t *ProcessWorldBrushes(int brush_start, int brush_end);

//=============================================================================
// brushbsp
//=============================================================================

#define	PSIDE_FRONT			1
#define	PSIDE_BACK			2
#define	PSIDE_BOTH			(PSIDE_FRONT|PSIDE_BACK)
#define	PSIDE_FACING		4

void WriteBrushList(char *name, bspbrush_t *brush, qboolean onlyvis);
bspbrush_t *CopyBrush(bspbrush_t *brush);
void SplitBrush(bspbrush_t *brush, int planenum, bspbrush_t **front, bspbrush_t **back);
node_t *AllocNode(void);
bspbrush_t *AllocBrush(int numsides);
int CountBrushList(bspbrush_t *brushes);
void FreeBrush(bspbrush_t *brushes);
vec_t BrushVolume(bspbrush_t *brush);
void BoundBrush(bspbrush_t *brush);
void FreeBrushList(bspbrush_t *brushes);
tree_t *BrushBSP(bspbrush_t *brushlist, vec3_t mins, vec3_t maxs);
bspbrush_t *BrushFromBounds(vec3_t mins, vec3_t maxs);
int BrushMostlyOnSide(bspbrush_t *brush, plane_t *plane);
qboolean WindingIsHuge(winding_t *w);
qboolean WindingIsTiny(winding_t *w);
void ResetBrushBSP(void);

//=============================================================================
// portals.c
//=============================================================================

int VisibleContents (int contents);
void MakeHeadnodePortals (tree_t *tree);
void MakeNodePortal (node_t *node);
void SplitNodePortals (node_t *node);
qboolean Portal_VisFlood (portal_t *p);
qboolean FloodEntities (tree_t *tree);
void FillOutside (node_t *headnode);
void FloodAreas (tree_t *tree);
void MarkVisibleSides (tree_t *tree, int start, int end);
void FreePortal (portal_t *p);
void EmitAreaPortals (node_t *headnode);
void MakeTreePortals (tree_t *tree);

//=============================================================================
// glfile.c
//=============================================================================

void OutputWinding(winding_t *w, FILE *glview);
void WriteGLView(tree_t *tree, char *source);

//=============================================================================
// gldraw.c
//=============================================================================

extern vec3_t draw_mins, draw_maxs;
extern qboolean drawflag;

void Draw_ClearWindow (void);
void DrawWinding (winding_t *w);
void GLS_BeginScene (void);
void GLS_Winding (winding_t *w, int code);
void GLS_EndScene (void);

//=============================================================================
// leakfile.c
//=============================================================================

void LeakFile (tree_t *tree);

//=============================================================================
// tree.c
//=============================================================================

tree_t *Tree_Alloc(void);
void Tree_Free(tree_t *tree);
void Tree_Free_r(node_t *node);
void Tree_Print_r(node_t *node, int depth);
void Tree_FreePortals_r(node_t *node);
void Tree_PruneNodes_r(node_t *node);
void Tree_PruneNodes(node_t *node);