317 lines
9.2 KiB
C
317 lines
9.2 KiB
C
/***
|
|
*
|
|
* Copyright (c) 1996-2002, Valve LLC. All rights reserved.
|
|
*
|
|
* This product contains software technology licensed from Id
|
|
* Software, Inc. ("Id Technology"). Id Technology (c) 1996 Id Software, Inc.
|
|
* All Rights Reserved.
|
|
*
|
|
****/
|
|
|
|
// bsp5.h
|
|
|
|
#include "cmdlib.h"
|
|
#include "mathlib.h"
|
|
#include "bspfile.h"
|
|
#include "threads.h"
|
|
#include "polylib.h"
|
|
#include "stringlib.h"
|
|
#include "filesystem.h"
|
|
|
|
#include <windows.h>
|
|
|
|
#ifndef DOUBLEVEC_T
|
|
#error you must add -dDOUBLEVEC_T to the project!
|
|
#endif
|
|
|
|
#define DEFAULT_SUBDIVIDE_SIZE ((MAX_SURFACE_EXTENT - 1) * TEXTURE_STEP)
|
|
#define DEFAULT_MAXNODE_SIZE -1
|
|
#define DEFAULT_MERGE_LEVEL 1
|
|
#define DEFAULT_NOFILL false
|
|
#define DEFAULT_NOTJUNC false
|
|
#define DEFAULT_NOCLIP false
|
|
#define DEFAULT_FORCEVIS true
|
|
#define BSPCHOP_EPSILON ( Q_min( g_prtepsilon * 4.0, ON_EPSILON ))
|
|
|
|
// the exact bounding box of the brushes is expanded some for the headnode
|
|
// volume. is this still needed?
|
|
#define SIDESPACE 24
|
|
|
|
// !!! if this is changed, it must be changed in csg.h too !!!
|
|
typedef struct
|
|
{
|
|
vec3_t normal;
|
|
vec3_t origin; // unused
|
|
vec_t dist;
|
|
int type;
|
|
int outplanenum; // mapped planenum (in CSG it was called a hash_chain)
|
|
} plane_t;
|
|
|
|
//============================================================================
|
|
typedef enum
|
|
{
|
|
face_normal = 0,
|
|
face_hint,
|
|
face_discardable, // contents must not differ between front and back
|
|
} facestyle_e;
|
|
|
|
typedef struct face_s
|
|
{
|
|
struct face_s *next;
|
|
|
|
int planenum;
|
|
int texturenum;
|
|
int contents; // contents in front of face
|
|
|
|
struct face_s *original; // face on node
|
|
int outputnumber; // only valid for original faces after
|
|
int referenced; // only valid for original faces
|
|
facestyle_e facestyle;
|
|
int bite;
|
|
|
|
int detaillevel; // defined by hlcsg
|
|
int *outputedges; // used in WriteDrawNodes
|
|
int numedges; // outcount
|
|
// write surfaces
|
|
winding_t *w;
|
|
} face_t;
|
|
|
|
|
|
typedef struct surface_s
|
|
{
|
|
struct surface_s *next;
|
|
int planenum;
|
|
vec3_t mins, maxs;
|
|
struct node_s *onnode; // true if surface has already been used
|
|
// as a splitting node
|
|
int detaillevel; // minimum detail level of its faces
|
|
face_t *faces; // links to all the faces on either side of the surf
|
|
} surface_t;
|
|
|
|
// detail brushes stuff
|
|
typedef struct side_s
|
|
{
|
|
struct side_s *next;
|
|
plane_t plane; // facing inside (reversed when loading brush file)
|
|
winding_t *w; // (also reversed)
|
|
} side_t;
|
|
|
|
typedef struct brush_s
|
|
{
|
|
struct brush_s *next;
|
|
side_t *sides;
|
|
} brush_t;
|
|
|
|
//
|
|
// there is a node_t structure for every node and leaf in the bsp tree
|
|
//
|
|
#define PLANENUM_LEAF -1
|
|
#define BOUNDS_EXPANSION 1.0
|
|
|
|
#define FNODE_DETAIL (1<<0) // is under a diskleaf
|
|
#define FNODE_LEAFPORTAL (1<<1) // not detail and children are detail; only visleafs have contents, portals, mins, maxs
|
|
#define FNODE_DETAILCONTENTS (1<<2) // inside a detail brush
|
|
#define FNODE_EMPTY (1<<3) // not solid or sky
|
|
|
|
typedef struct node_s
|
|
{
|
|
surface_t *surfaces;
|
|
brush_t *detailbrushes;
|
|
|
|
brush_t *boundsbrush;
|
|
vec3_t loosemins; // all leafs and nodes have this, while 'mins' and 'maxs'
|
|
vec3_t loosemaxs; // are only valid for nondetail leafs and nodes.
|
|
|
|
int flags;
|
|
vec3_t mins, maxs; // bounding volume of portals;
|
|
|
|
// information for decision nodes
|
|
int planenum; // -1 = leaf node
|
|
int firstface; // decision node only
|
|
int numfaces; // decision node only
|
|
struct node_s *children[2]; // only valid for decision nodes
|
|
face_t *faces; // decision nodes only, list for both sides
|
|
|
|
// information for leafs
|
|
int contents; // leaf nodes (0 for decision nodes)
|
|
face_t **markfaces; // leaf nodes only, point to node faces
|
|
struct portal_s *portals;
|
|
int visleafnum; // -1 = solid
|
|
int valid; // for flood filling
|
|
int occupied; // light number in leaf for outside filling
|
|
|
|
bool opaque() const { return contents == CONTENTS_SOLID || contents == CONTENTS_SKY; }
|
|
} node_t;
|
|
|
|
typedef struct portal_s
|
|
{
|
|
int planenum;
|
|
node_t *onnode; // NULL = outside box
|
|
node_t *nodes[2]; // [0] = front side of plane
|
|
struct portal_s *next[2];
|
|
winding_t *winding;
|
|
} portal_t;
|
|
|
|
typedef struct
|
|
{
|
|
vec3_t mins, maxs; // bounding box
|
|
face_t *validfaces[MAX_INTERNAL_MAP_PLANES]; // build surfaces is also used by GatherNodeFaces
|
|
brush_t *detailbrushes;
|
|
surface_t *surfaces;
|
|
node_t *headnode;
|
|
int numsurfaces; // surface_t[count]
|
|
int numfaces; // debug
|
|
} tree_t;
|
|
|
|
face_t *NewFaceFromFace (face_t *in);
|
|
void SplitFace( face_t *in, plane_t *split, face_t **front, face_t **back, bool keepsource = false );
|
|
void SplitFaceEpsilon( face_t *in, plane_t *split, face_t **front, face_t **back, vec_t epsilon, bool keepsource = false );
|
|
|
|
//=============================================================================
|
|
|
|
// solidbsp.c
|
|
|
|
void DivideFacet( face_t *in, plane_t *split, face_t **front, face_t **back );
|
|
void CalcSurfaceInfo( surface_t *surf );
|
|
void SubdivideFace( face_t *f, face_t **prevptr );
|
|
void SolidBSP( tree_t *tree, int modnum, int hullnum );
|
|
vec_t SplitPlaneMetric( const plane_t *p, const vec3_t mins, const vec3_t maxs );
|
|
void MakeNodePortal( node_t *node );
|
|
void SplitNodePortals( node_t *node );
|
|
void FreeLeafSurfs( node_t *leaf );
|
|
|
|
//=============================================================================
|
|
|
|
// merge.c
|
|
|
|
void MergePlaneFaces( surface_t *plane, int mergelevel );
|
|
face_t *FreeMergeListScraps (face_t *merged);
|
|
void MergeTreeFaces( tree_t *tree );
|
|
|
|
//=============================================================================
|
|
|
|
// surfaces.c
|
|
|
|
extern int firstmodeledge;
|
|
|
|
void SubdivideFaces (surface_t *surfhead);
|
|
int GetEdge (vec3_t p1, vec3_t p2, face_t *f);
|
|
void GatherTreeFaces( tree_t *tree );
|
|
void MakeFaceEdges( void );
|
|
void InitHash( void );
|
|
|
|
//=============================================================================
|
|
|
|
// portals.c
|
|
|
|
void AddPortalToNodes( portal_t *p, node_t *front, node_t *back );
|
|
void RemovePortalFromNode( portal_t *portal, node_t *l );
|
|
void MakeHeadnodePortals( node_t *node, const vec3_t mins, const vec3_t maxs );
|
|
void FreeTreePortals( tree_t *tree );
|
|
void WritePortalfile( tree_t *tree, bool leaked );
|
|
void FillInside( node_t *node );
|
|
|
|
//=============================================================================
|
|
|
|
// detail.c
|
|
|
|
brush_t *ReadBrushes( FILE *file );
|
|
|
|
//=============================================================================
|
|
|
|
// partition.c
|
|
|
|
surface_t *SelectPartition( surface_t *surfaces, node_t *node, bool midsplit, int splitdetaillevel, vec3_t validmins, vec3_t validmaxs );
|
|
|
|
// tree.c
|
|
|
|
tree_t *AllocTree( void );
|
|
void FreeTree( tree_t *t );
|
|
tree_t *MakeTreeFromHullFaces( FILE *polyfile, FILE *brushfile );
|
|
tree_t *TreeProcessModel( tree_t *tree, int modnum, int hullnum );
|
|
void MakeSurflistFromValidFaces( tree_t *tree );
|
|
bool CheckFaceForHint( const face_t *f );
|
|
bool CheckFaceForDiscardable( const face_t *f );
|
|
|
|
//=============================================================================
|
|
|
|
// tjunc.c
|
|
|
|
void tjunc( node_t *headnode, bool worldmodel );
|
|
|
|
//=============================================================================
|
|
|
|
// writebsp.c
|
|
|
|
void WriteNodePlanes (node_t *headnode);
|
|
void WriteClipNodes (node_t *headnode);
|
|
void WriteDrawNodes (node_t *headnode);
|
|
|
|
void EmitDrawNodes( tree_t *tree );
|
|
void EmitClipNodes( tree_t *tree, int modnum, int hullnum );
|
|
void EmitNodeFaces( node_t *headnode );
|
|
int EmitVertex( const vec3_t point );
|
|
void BeginBSPFile( void );
|
|
void FinishBSPFile( const char *source );
|
|
int FindFloatPlane( const vec3_t normal, vec_t dist );
|
|
|
|
//=============================================================================
|
|
|
|
// outside.c
|
|
|
|
bool FillOutside( tree_t *tree, int hullnum, bool leakfile );
|
|
|
|
//=============================================================================
|
|
|
|
extern bool g_nofill;
|
|
extern bool g_notjunc;
|
|
extern bool g_noclip;
|
|
extern bool g_forcevis;
|
|
|
|
extern int g_maxnode_size;
|
|
extern int g_merge_level;
|
|
extern vec_t g_prtepsilon;
|
|
|
|
extern int valid;
|
|
extern int c_splitnodes;
|
|
extern int c_unsplitted_faces;
|
|
|
|
extern char g_portfilename[1024];
|
|
extern char g_pointfilename[1024];
|
|
extern char g_linefilename[1024];
|
|
|
|
extern plane_t g_mapplanes[MAX_INTERNAL_MAP_PLANES];
|
|
extern int g_nummapplanes;
|
|
extern node_t g_outside_node;
|
|
|
|
void AddFaceToBounds( face_t *f, vec3_t mins, vec3_t maxs );
|
|
|
|
// misc functions
|
|
|
|
face_t *AllocFace( void );
|
|
void FreeFace( face_t *f );
|
|
void UnlinkFace( face_t **head, face_t *face );
|
|
int CountListFaces( face_t *list );
|
|
|
|
struct portal_s *AllocPortal( void );
|
|
void FreePortal( struct portal_s *p );
|
|
|
|
surface_t *AllocSurface( void );
|
|
void FreeSurface( surface_t *s );
|
|
|
|
side_t *AllocSide( void );
|
|
void FreeSide( side_t *s );
|
|
side_t *NewSideFromSide( const side_t *s );
|
|
brush_t *AllocBrush( void );
|
|
void FreeBrush( brush_t *b );
|
|
brush_t *NewBrushFromBrush( const brush_t *b );
|
|
void SplitBrush( brush_t *in, const plane_t *split, brush_t **front, brush_t **back );
|
|
brush_t *BrushFromBox( const vec3_t mins, const vec3_t maxs );
|
|
void CalcBrushBounds( const brush_t *b, vec3_t &mins, vec3_t &maxs );
|
|
|
|
node_t *AllocNode( void );
|
|
void FreeNode( node_t *n );
|
|
void FreeLeaf( node_t *n );
|
|
|
|
//=============================================================================
|