compilers/dmap/dmap.h

/*
===========================================================================

Doom 3 GPL Source Code
Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.

This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code").

Doom 3 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 3 of the License, or
(at your option) any later version.

Doom 3 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 Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.

In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.

If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.

===========================================================================
*/

#include "idlib/containers/PlaneSet.h"
#include "idlib/MapFile.h"
#include "cm/CollisionModel.h"
#include "renderer/tr_local.h"

typedef struct primitive_s {
	struct primitive_s *next;

	// only one of these will be non-NULL
	struct bspbrush_s *	brush;
	struct mapTri_s *	tris;
} primitive_t;


typedef struct {
	struct optimizeGroup_s	*groups;
	// we might want to add other fields later
} uArea_t;

typedef struct {
	idMapEntity *		mapEntity;		// points into mapFile_t data

	idVec3				origin;
	primitive_t *		primitives;
	struct tree_s *		tree;

	int					numAreas;
	uArea_t *			areas;
} uEntity_t;


// chains of mapTri_t are the general unit of processing
typedef struct mapTri_s {
	struct mapTri_s *	next;

	const idMaterial *	material;
	void *				mergeGroup;		// we want to avoid merging triangles
											// from different fixed groups, like guiSurfs and mirrors
	int					planeNum;			// not set universally, just in some areas

	idDrawVert			v[3];
	const struct hashVert_s *hashVert[3];
	struct optVertex_s *optVert[3];
} mapTri_t;


typedef struct {
	int					width, height;
	idDrawVert *		verts;
} mesh_t;


#define	MAX_PATCH_SIZE	32

#define	PLANENUM_LEAF		-1

typedef struct parseMesh_s {
	struct parseMesh_s *next;
	mesh_t				mesh;
	const idMaterial *	material;
} parseMesh_t;

typedef struct bspface_s {
	struct bspface_s *	next;
	int					planenum;
	bool				portal;			// all portals will be selected before
										// any non-portals
	bool				checked;		// used by SelectSplitPlaneNum()
	idWinding *			w;
} bspface_t;

typedef struct {
	idVec4		v[2];		// the offset value will always be in the 0.0 to 1.0 range
} textureVectors_t;

typedef struct side_s {
	int					planenum;

	const idMaterial *	material;
	textureVectors_t	texVec;

	idWinding *			winding;		// only clipped to the other sides of the brush
	idWinding *			visibleHull;	// also clipped to the solid parts of the world
} side_t;


typedef struct bspbrush_s {
	struct bspbrush_s *	next;
	struct bspbrush_s *	original;	// chopped up brushes will reference the originals

	int					entitynum;			// editor numbering for messages
	int					brushnum;			// editor numbering for messages

	const idMaterial *	contentShader;	// one face's shader will determine the volume attributes

	int					contents;
	bool				opaque;
	int					outputNumber;		// set when the brush is written to the file list

	idBounds			bounds;
	int					numsides;
	side_t				sides[6];			// variably sized
} uBrush_t;


typedef struct drawSurfRef_s {
	struct drawSurfRef_s *	nextRef;
	int						outputNumber;
} drawSurfRef_t;


typedef struct node_s {
	// both leafs and nodes
	int					planenum;	// -1 = leaf node
	struct node_s *		parent;
	idBounds			bounds;		// valid after portalization

	// nodes only
	side_t *			side;		// the side that created the node
	struct node_s *		children[2];
	int					nodeNumber;	// set after pruning

	// leafs only
	bool				opaque;		// view can never be inside

	uBrush_t *			brushlist;	// fragments of all brushes in this leaf
									// needed for FindSideForPortal

	int					area;		// determined by flood filling up to areaportals
	int					occupied;	// 1 or greater can reach entity
	uEntity_t *			occupant;	// for leak file testing

	struct uPortal_s *	portals;	// also on nodes during construction
} node_t;


typedef struct uPortal_s {
	idPlane		plane;
	node_t		*onnode;		// NULL = outside box
	node_t		*nodes[2];		// [0] = front side of plane
	struct uPortal_s	*next[2];
	idWinding	*winding;
} uPortal_t;

// a tree_t is created by FaceBSP()
typedef struct tree_s {
	node_t		*headnode;
	node_t		outside_node;
	idBounds	bounds;
} tree_t;

#define	MAX_QPATH			256			// max length of a game pathname

typedef struct {
	idRenderLightLocal	def;
	char		name[MAX_QPATH];		// for naming the shadow volume surface and interactions
	srfTriangles_t	*shadowTris;
} mapLight_t;

#define	MAX_GROUP_LIGHTS	16

typedef struct optimizeGroup_s {
	struct optimizeGroup_s	*nextGroup;

	idBounds			bounds;			// set in CarveGroupsByLight

	// all of these must match to add a triangle to the triList
	bool				smoothed;				// curves will never merge with brushes
	int					planeNum;
	int					areaNum;
	const idMaterial *	material;
	int					numGroupLights;
	mapLight_t *		groupLights[MAX_GROUP_LIGHTS];	// lights effecting this list
	void *				mergeGroup;		// if this differs (guiSurfs, mirrors, etc), the
										// groups will not be combined into model surfaces
										// after optimization
	textureVectors_t	texVec;

	bool				surfaceEmited;

	mapTri_t *			triList;
	mapTri_t *			regeneratedTris;	// after each island optimization
	idVec3				axis[2];			// orthogonal to the plane, so optimization can be 2D
} optimizeGroup_t;

// all primitives from the map are added to optimzeGroups, creating new ones as needed
// each optimizeGroup is then split into the map areas, creating groups in each area
// each optimizeGroup is then divided by each light, creating more groups
// the final list of groups is then tjunction fixed against all groups, then optimized internally
// multiple optimizeGroups will be merged together into .proc surfaces, but no further optimization
// is done on them


//=============================================================================

// dmap.cpp

typedef enum {
	SO_NONE,			// 0
	SO_MERGE_SURFACES,	// 1
	SO_CULL_OCCLUDED,	// 2
	SO_CLIP_OCCLUDERS,	// 3
	SO_CLIP_SILS,		// 4
	SO_SIL_OPTIMIZE		// 5
} shadowOptLevel_t;

typedef struct {
	// mapFileBase will contain the qpath without any extension: "maps/test_box"
	char		mapFileBase[1024];

	idMapFile	*dmapFile;

	idPlaneSet	mapPlanes;

	int			num_entities;
	uEntity_t	*uEntities;

	int			entityNum;

	idList<mapLight_t*>	mapLights;

	bool	verbose;

	bool	glview;
	bool	noOptimize;
	bool	verboseentities;
	bool	noCurves;
	bool	fullCarve;
	bool	noModelBrushes;
	bool	noTJunc;
	bool	nomerge;
	bool	noFlood;
	bool	noClipSides;		// don't cut sides by solid leafs, use the entire thing
	bool	noLightCarve;		// extra triangle subdivision by light frustums
	shadowOptLevel_t	shadowOptLevel;
	bool	noShadow;			// don't create optimized shadow volumes

	idBounds	drawBounds;
	bool	drawflag;

	int		totalShadowTriangles;
	int		totalShadowVerts;
} dmapGlobals_t;

extern dmapGlobals_t dmapGlobals;

int FindFloatPlane( const idPlane &plane, bool *fixedDegeneracies = NULL );


//=============================================================================

// brush.cpp

#ifndef CLIP_EPSILON
#define	CLIP_EPSILON	0.1f
#endif

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

int	CountBrushList (uBrush_t *brushes);
uBrush_t *AllocBrush (int numsides);
void FreeBrush (uBrush_t *brushes);
void FreeBrushList (uBrush_t *brushes);
uBrush_t *CopyBrush (uBrush_t *brush);
void DrawBrushList (uBrush_t *brush);
void PrintBrush (uBrush_t *brush);
bool BoundBrush (uBrush_t *brush);
bool CreateBrushWindings (uBrush_t *brush);
uBrush_t	*BrushFromBounds( const idBounds &bounds );
float BrushVolume (uBrush_t *brush);
void WriteBspBrushMap( const char *name, uBrush_t *list );

void FilterBrushesIntoTree( uEntity_t *e );

void SplitBrush( uBrush_t *brush, int planenum, uBrush_t **front, uBrush_t **back);
node_t *AllocNode( void );


//=============================================================================

// map.cpp

bool		LoadDMapFile( const char *filename );
void		FreeOptimizeGroupList( optimizeGroup_t *groups );
void		FreeDMapFile( void );

//=============================================================================

// draw.cpp -- draw debug views either directly, or through glserv.exe

void Draw_ClearWindow( void );
void DrawWinding( const idWinding *w );
void DrawAuxWinding( const idWinding *w );

void DrawLine( idVec3 v1, idVec3 v2, int color );

void GLS_BeginScene( void );
void GLS_Winding( const idWinding *w, int code );
void GLS_Triangle( const mapTri_t *tri, int code );
void GLS_EndScene( void );


//=============================================================================

// portals.cpp

#define	MAX_INTER_AREA_PORTALS	1024

typedef struct {
	int		area0, area1;
	side_t	*side;
} interAreaPortal_t;

extern	interAreaPortal_t interAreaPortals[MAX_INTER_AREA_PORTALS];
extern	int					numInterAreaPortals;

bool FloodEntities( tree_t *tree );
void FillOutside( uEntity_t *e );
void FloodAreas( uEntity_t *e );
void MakeTreePortals( tree_t *tree );
void FreePortal( uPortal_t *p );

//=============================================================================

// glfile.cpp -- write a debug file to be viewd with glview.exe

void OutputWinding( idWinding *w, idFile *glview );
void WriteGLView( tree_t *tree, char *source );

//=============================================================================

// leakfile.cpp

void LeakFile( tree_t *tree );

//=============================================================================

// facebsp.cpp

tree_t *AllocTree( void );

void FreeTree( tree_t *tree );

void FreeTree_r( node_t *node );
void FreeTreePortals_r( node_t *node );


bspface_t	*MakeStructuralBspFaceList( primitive_t *list );
bspface_t	*MakeVisibleBspFaceList( primitive_t *list );
tree_t		*FaceBSP( bspface_t *list );

//=============================================================================

// surface.cpp

mapTri_t *CullTrisInOpaqueLeafs( mapTri_t *triList, tree_t *tree );
void	ClipSidesByTree( uEntity_t *e );
void	SplitTrisToSurfaces( mapTri_t *triList, tree_t *tree );
void	PutPrimitivesInAreas( uEntity_t *e );
void	Prelight( uEntity_t *e );

//=============================================================================

// tritjunction.cpp

struct hashVert_s	*GetHashVert( idVec3 &v );
void	HashTriangles( optimizeGroup_t *groupList );
void	FreeTJunctionHash( void );
int		CountGroupListTris( const optimizeGroup_t *groupList );
void	FixEntityTjunctions( uEntity_t *e );
void	FixAreaGroupsTjunctions( optimizeGroup_t *groupList );
void	FixGlobalTjunctions( uEntity_t *e );

//=============================================================================

// optimize.cpp -- trianlge mesh reoptimization

// the shadow volume optimizer call internal optimizer routines, normal triangles
// will just be done by OptimizeEntity()


typedef struct optVertex_s {
	idDrawVert	v;
	idVec3	pv;					// projected against planar axis, third value is 0
	struct optEdge_s *edges;
	struct optVertex_s	*islandLink;
	bool	addedToIsland;
	bool	emited;			// when regenerating triangles
} optVertex_t;

typedef struct optEdge_s {
	optVertex_t	*v1, *v2;
	struct optEdge_s	*islandLink;
	bool	addedToIsland;
	bool	created;		// not one of the original edges
	bool	combined;		// combined from two or more colinear edges
	struct optTri_s	*frontTri, *backTri;
	struct optEdge_s *v1link, *v2link;
} optEdge_t;

typedef struct optTri_s {
	struct optTri_s	*next;
	idVec3		midpoint;
	optVertex_t	*v[3];
	bool	filled;
} optTri_t;

typedef struct {
	optimizeGroup_t	*group;
	optVertex_t	*verts;
	optEdge_t	*edges;
	optTri_t	*tris;
} optIsland_t;


void	OptimizeEntity( uEntity_t *e );
void	OptimizeGroupList( optimizeGroup_t *groupList );

//=============================================================================

// tritools.cpp

mapTri_t	*AllocTri( void );
void		FreeTri( mapTri_t *tri );
int			CountTriList( const mapTri_t *list );
mapTri_t	*MergeTriLists( mapTri_t *a, mapTri_t *b );
mapTri_t	*CopyTriList( const mapTri_t *a );
void		FreeTriList( mapTri_t *a );
mapTri_t	*CopyMapTri( const mapTri_t *tri );
float		MapTriArea( const mapTri_t *tri );
mapTri_t	*RemoveBadTris( const mapTri_t *tri );
void		BoundTriList( const mapTri_t *list, idBounds &b );
void		DrawTri( const mapTri_t *tri );
void		FlipTriList( mapTri_t *tris );
void		TriVertsFromOriginal( mapTri_t *tri, const mapTri_t *original );
void		PlaneForTri( const mapTri_t *tri, idPlane &plane );
idWinding	*WindingForTri( const mapTri_t *tri );
mapTri_t	*WindingToTriList( const idWinding *w, const mapTri_t *originalTri );
void		ClipTriList( const mapTri_t *list, const idPlane &plane, float epsilon, mapTri_t **front, mapTri_t **back );

//=============================================================================

// output.cpp

srfTriangles_t	*ShareMapTriVerts( const mapTri_t *tris );
void WriteOutputFile( void );

//=============================================================================

// shadowopt.cpp

srfTriangles_t *CreateLightShadow( optimizeGroup_t *shadowerGroups, const mapLight_t *light );
void		FreeBeamTree( struct beamTree_s *beamTree );

void		CarveTriByBeamTree( const struct beamTree_s *beamTree, const mapTri_t *tri, mapTri_t **lit, mapTri_t **unLit );