ref: bea7b7bf8ccbc2bc41906517079e76fcfb31cb5a
dir: /code/bspc/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 <malloc.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"
#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
//=============================================================================
#define MAX_MAPFILE_PLANES 256000
#define MAX_MAPFILE_BRUSHES 65535
#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);