/*
   Copyright (C) 1997-2001 Id Software, Inc.

   This program 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.

   This program 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 this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

 */
// cmodel.c -- model loading

#include "qcommon.h"
#include "cm_local.h"

static qboolean	cm_initialized = qfalse;

static mempool_t *cmap_mempool;

static cvar_t *cm_noAreas;
cvar_t *cm_noCurves;

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

   		    PATCH LOADING

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

static void CM_Clear( cmodel_state_t *cms )
{
	int i, j;

	if( cms->map_shaderrefs )
	{
		Mem_Free( cms->map_shaderrefs[0].name );
		Mem_Free( cms->map_shaderrefs );
		cms->map_shaderrefs = NULL;
	}

	if( cms->map_faces )
	{
		for( i = 0; i < cms->numfaces; i++ )
		{
			for( j = 0; j < cms->map_faces[i].numfacets; j++ )
			{
				if( cms->map_faces[i].facets[j].numsides )
					Mem_Free( cms->map_faces[i].facets[j].brushsides );
			}
			Mem_Free( cms->map_faces[i].facets );
		}
		Mem_Free( cms->map_faces );
		cms->map_faces = NULL;
		cms->numfaces = 0;
	}

	if( cms->map_cmodels != &cms->map_cmodel_empty )
	{
		for( i = 0; i < cms->numcmodels; i++ )
		{
			Mem_Free( cms->map_cmodels[i].markfaces );
			Mem_Free( cms->map_cmodels[i].markbrushes );
		}
		Mem_Free( cms->map_cmodels );
		cms->map_cmodels = &cms->map_cmodel_empty;
		cms->numcmodels = 0;
	}

	if( cms->map_nodes )
	{
		Mem_Free( cms->map_nodes );
		cms->map_nodes = NULL;
	}

	if( cms->map_markfaces )
	{
		Mem_Free( cms->map_markfaces );
		cms->map_markfaces = NULL;
	}

	if( cms->map_leafs != &cms->map_leaf_empty )
	{
		Mem_Free( cms->map_leafs );
		cms->map_leafs = &cms->map_leaf_empty;
	}

	if( cms->map_areas != &cms->map_area_empty )
	{
		Mem_Free( cms->map_areas );
		cms->map_areas = &cms->map_area_empty;
	}

	if( cms->map_planes )
	{
		Mem_Free( cms->map_planes );
		cms->map_planes = NULL;
	}

	if( cms->map_markbrushes )
	{
		Mem_Free( cms->map_markbrushes );
		cms->map_markbrushes = NULL;
	}

	if( cms->map_brushsides )
	{
		Mem_Free( cms->map_brushsides );
		cms->map_brushsides = NULL;
	}

	if( cms->map_brushes )
	{
		Mem_Free( cms->map_brushes );
		cms->map_brushes = NULL;
	}

	if( cms->map_pvs )
	{
		Mem_Free( cms->map_pvs );
		cms->map_pvs = NULL;
	}

	if( cms->map_entitystring != &cms->map_entitystring_empty )
	{
		Mem_Free( cms->map_entitystring );
		cms->map_entitystring = &cms->map_entitystring_empty;
	}

	if( cms->map_phs )
	{
		Mem_Free( cms->map_phs );
		cms->map_phs = NULL;
	}

	cms->map_name[0] = 0;

	ClearBounds( cms->world_mins, cms->world_maxs );
}

/*
   =================
   CM_CreateFacetFromPoints
   =================
 */
static int CM_CreateFacetFromPoints( cmodel_state_t *cms, cbrush_t *facet, vec3_t *verts, int numverts, cshaderref_t *shaderref )
{
	int i, j, k;
	int axis, dir;
	cbrushside_t *s;
	cplane_t *planes;
	vec3_t normal, mins, maxs;
	float d, dist;
	cplane_t mainplane;
	vec3_t vec, vec2;
	int numbrushplanes;
	cplane_t brushplanes[32];

	// set default values for brush
	facet->numsides = 0;
	facet->brushsides = NULL;
	facet->contents = shaderref->contents;

	// calculate plane for this triangle
	PlaneFromPoints( verts, &mainplane );
	if( ComparePlanes( mainplane.normal, mainplane.dist, vec3_origin, 0 ) )
		return 0;

	// test a quad case
	if( numverts > 3 )
	{
		d = DotProduct( verts[3], mainplane.normal ) - mainplane.dist;
		if( d < -0.1 || d > 0.1 )
			return 0;

		if( 0 )
		{
			vec3_t v[3];
			cplane_t plane;

			// try different combinations of planes
			for( i = 1; i < 4; i++ )
			{
				VectorCopy( verts[i], v[0] );
				VectorCopy( verts[( i+1 )%4], v[1] );
				VectorCopy( verts[( i+2 )%4], v[2] );
				PlaneFromPoints( v, &plane );

				if( fabs( DotProduct( mainplane.normal, plane.normal ) ) < 0.9 )
					return 0;
			}
		}
	}

	numbrushplanes = 0;

	// add front plane
	SnapPlane( mainplane.normal, &mainplane.dist );
	VectorCopy( mainplane.normal, brushplanes[numbrushplanes].normal );
	brushplanes[numbrushplanes].dist = mainplane.dist; numbrushplanes++;

	// calculate mins & maxs
	ClearBounds( mins, maxs );
	for( i = 0; i < numverts; i++ )
		AddPointToBounds( verts[i], mins, maxs );

	// add the axial planes
	for( axis = 0; axis < 3; axis++ )
	{
		for( dir = -1; dir <= 1; dir += 2 )
		{
			for( i = 0; i < numbrushplanes; i++ )
			{
				if( brushplanes[i].normal[axis] == dir )
					break;
			}

			if( i == numbrushplanes )
			{
				VectorClear( normal );
				normal[axis] = dir;
				if( dir == 1 )
					dist = maxs[axis];
				else
					dist = -mins[axis];

				VectorCopy( normal, brushplanes[numbrushplanes].normal );
				brushplanes[numbrushplanes].dist = dist; numbrushplanes++;
			}
		}
	}

	// add the edge bevels
	for( i = 0; i < numverts; i++ )
	{
		j = ( i + 1 ) % numverts;
		k = ( i + 2 ) % numverts;

		VectorSubtract( verts[i], verts[j], vec );
		if( VectorNormalize( vec ) < 0.5 )
			continue;

		SnapVector( vec );
		for( j = 0; j < 3; j++ )
		{
			if( vec[j] == 1 || vec[j] == -1 )
				break; // axial
		}
		if( j != 3 )
			continue; // only test non-axial edges

		// try the six possible slanted axials from this edge
		for( axis = 0; axis < 3; axis++ )
		{
			for( dir = -1; dir <= 1; dir += 2 )
			{
				// construct a plane
				VectorClear( vec2 );
				vec2[axis] = dir;
				CrossProduct( vec, vec2, normal );
				if( VectorNormalize( normal ) < 0.5 )
					continue;
				dist = DotProduct( verts[i], normal );

				for( j = 0; j < numbrushplanes; j++ )
				{
					// if this plane has already been used, skip it
					if( ComparePlanes( brushplanes[j].normal, brushplanes[j].dist, normal, dist ) )
						break;
				}
				if( j != numbrushplanes )
					continue;

				// if all other points are behind this plane, it is a proper edge bevel
				for( j = 0; j < numverts; j++ )
				{
					if( j != i )
					{
						d = DotProduct( verts[j], normal ) - dist;
						if( d > 0.1 )
							break; // point in front: this plane isn't part of the outer hull
					}
				}
				if( j != numverts )
					continue;

				// add this plane
				VectorCopy( normal, brushplanes[numbrushplanes].normal );
				brushplanes[numbrushplanes].dist = dist; numbrushplanes++;
			}
		}
	}

	if( !numbrushplanes )
		return 0;

	// add brushsides
	s = facet->brushsides = Mem_Alloc( cms->mempool, numbrushplanes * ( sizeof( cbrushside_t ) + sizeof( cplane_t ) ) );
	planes = ( cplane_t * )( ( qbyte * )s + numbrushplanes * sizeof( cbrushside_t ) );
	for( i = 0; i < numbrushplanes; i++, s++ )
	{
		planes[i] = brushplanes[i];
		SnapPlane( planes[i].normal, &planes[i].dist );
		CategorizePlane( &planes[i] );

		s->plane = &planes[i];
		s->surfFlags = shaderref->flags;
	}

	return ( facet->numsides = numbrushplanes );
}

/*
   =================
   CM_CreatePatch
   =================
 */
static void CM_CreatePatch( cmodel_state_t *cms, cface_t *patch, cshaderref_t *shaderref, vec3_t *verts, int *patch_cp )
{
	int step[2], size[2], flat[2], i, u, v;
	cbrush_t *facets;
	vec3_t *points;
	vec3_t tverts[4];

	// find the degree of subdivision in the u and v directions
	Patch_GetFlatness( CM_SUBDIV_LEVEL, (vec_t *)verts[0], 3, patch_cp, flat );

	step[0] = 1 << flat[0];
	step[1] = 1 << flat[1];
	size[0] = ( patch_cp[0] >> 1 ) * step[0] + 1;
	size[1] = ( patch_cp[1] >> 1 ) * step[1] + 1;
	if( size[0] <= 0 || size[1] <= 0 )
		return;

	points = Mem_Alloc( cms->mempool, size[0] * size[1] * sizeof( vec3_t ) );
	facets = Mem_Alloc( cms->mempool, ( size[0]-1 ) * ( size[1]-1 ) * 2 * sizeof( cbrush_t ) );

	// fill in
	Patch_Evaluate( verts[0], patch_cp, step, points[0], 3 );

	patch->numfacets = 0;
	patch->facets = NULL;
	ClearBounds( patch->mins, patch->maxs );

	// create a set of facets
	for( v = 0; v < size[1]-1; v++ )
	{
		for( u = 0; u < size[0]-1; u++ )
		{
			i = v * size[0] + u;
			VectorCopy( points[i], tverts[0] );
			VectorCopy( points[i + size[0]], tverts[1] );
			VectorCopy( points[i + size[0] + 1], tverts[2] );
			VectorCopy( points[i + 1], tverts[3] );

			for( i = 0; i < 4; i++ )
				AddPointToBounds( tverts[i], patch->mins, patch->maxs );

			// try to create one facet from a quad
			if( CM_CreateFacetFromPoints( cms, &facets[patch->numfacets], tverts, 4, shaderref ) )
			{
				patch->numfacets++;
				continue;
			}

			VectorCopy( tverts[3], tverts[2] );

			// create two facets from triangles
			if( CM_CreateFacetFromPoints( cms, &facets[patch->numfacets], tverts, 3, shaderref ) )
				patch->numfacets++;

			VectorCopy( tverts[2], tverts[0] );
			VectorCopy( points[v *size[0] + u + size[0] + 1], tverts[2] );

			if( CM_CreateFacetFromPoints( cms, &facets[patch->numfacets], tverts, 3, shaderref ) )
				patch->numfacets++;
		}
	}

	if( !patch->numfacets )
	{
		ClearBounds( patch->mins, patch->maxs );
		Mem_Free( points );
		Mem_Free( facets );
		return;
	}

	patch->contents = shaderref->contents;
	patch->facets = Mem_Alloc( cms->mempool, patch->numfacets * sizeof( cbrush_t ) );
	memcpy( patch->facets, facets, patch->numfacets * sizeof( cbrush_t ) );

	Mem_Free( points );
	Mem_Free( facets );

	for( i = 0; i < 3; i++ )
	{
		// spread the mins / maxs by a pixel
		patch->mins[i] -= 1;
		patch->maxs[i] += 1;
	}
}


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

   		    MAP LOADING

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

/*
   =================
   CMod_LoadSurfaces
   =================
 */
static void CMod_LoadSurfaces( cmodel_state_t *cms, lump_t *l )
{
	int i;
	int count;
	char *buffer;
	size_t len, bufLen, bufSize;
	dshaderref_t *in;
	cshaderref_t *out;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadSurfaces: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "CMod_LoadSurfaces: map with no shaders" );

	out = cms->map_shaderrefs = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numshaderrefs = count;

	buffer = NULL;
	bufLen = bufSize = 0;
	for( i = 0; i < count; i++, in++, out++, bufLen += len + 1 )
	{
		len = strlen( in->name );
		if( bufLen + len >= bufSize )
		{
			bufSize = bufLen + len + 128;
			if( buffer )
				buffer = Mem_Realloc( buffer, bufSize );
			else
				buffer = Mem_Alloc( cms->mempool, bufSize );
		}

		// Vic: ZOMG, this is so nasty, perfectly valid in C though
		out->name = ( char * )( ( void * )bufLen );
		strcpy( buffer + bufLen, in->name );
		out->flags = LittleLong( in->flags );
		out->contents = LittleLong( in->contents );
	}

	for( i = 0; i < count; i++ )
	{
		cms->map_shaderrefs[i].name = buffer + ( size_t )( ( void * )cms->map_shaderrefs[i].name );
	}
}

/*
   =================
   CMod_LoadVertexes
   =================
 */
static void CMod_LoadVertexes( cmodel_state_t *cms, lump_t *l )
{
	int i;
	int count;
	dvertex_t *in;
	vec3_t *out;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMOD_LoadVertexes: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no vertexes" );

	out = cms->map_verts = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numvertexes = count;

	for( i = 0; i < count; i++, in++ )
	{
		out[i][0] = LittleFloat( in->point[0] );
		out[i][1] = LittleFloat( in->point[1] );
		out[i][2] = LittleFloat( in->point[2] );
	}
}

/*
   =================
   CMod_LoadVertexes_RBSP
   =================
 */
static void CMod_LoadVertexes_RBSP( cmodel_state_t *cms, lump_t *l )
{
	int i;
	int count;
	rdvertex_t *in;
	vec3_t *out;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadVertexes_RBSP: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no vertexes" );

	out = cms->map_verts = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numvertexes = count;

	for( i = 0; i < count; i++, in++ )
	{
		out[i][0] = LittleFloat( in->point[0] );
		out[i][1] = LittleFloat( in->point[1] );
		out[i][2] = LittleFloat( in->point[2] );
	}
}

/*
   =================
   CMod_LoadFace
   =================
 */
static inline void CMod_LoadFace( cmodel_state_t *cms, cface_t *out, int shadernum, int firstvert, int numverts, int *patch_cp )
{
	cshaderref_t *shaderref;

	shadernum = LittleLong( shadernum );
	if( shadernum < 0 || shadernum >= cms->numshaderrefs )
		return;

	shaderref = &cms->map_shaderrefs[shadernum];
	if( !shaderref->contents || ( shaderref->flags & SURF_NONSOLID ) )
		return;

	patch_cp[0] = LittleLong( patch_cp[0] );
	patch_cp[1] = LittleLong( patch_cp[1] );
	if( patch_cp[0] <= 0 || patch_cp[1] <= 0 )
		return;

	firstvert = LittleLong( firstvert );
	if( numverts <= 0 || firstvert < 0 || firstvert >= cms->numvertexes )
		return;

	CM_CreatePatch( cms, out, shaderref, cms->map_verts + firstvert, patch_cp );
}

/*
   =================
   CMod_LoadFaces
   =================
 */
static void CMod_LoadFaces( cmodel_state_t *cms, lump_t *l )
{
	int i, count;
	dface_t	*in;
	cface_t	*out;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadFaces: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no faces" );

	out = cms->map_faces = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numfaces = count;

	for( i = 0; i < count; i++, in++, out++ )
	{
		out->contents = 0;
		out->numfacets = 0;
		out->facets = NULL;
		if( LittleLong( in->facetype ) != FACETYPE_PATCH )
			continue;
		CMod_LoadFace( cms, out, in->shadernum, in->firstvert, in->numverts, in->patch_cp );
	}
}

/*
   =================
   CMod_LoadFaces_RBSP
   =================
 */
static void CMod_LoadFaces_RBSP( cmodel_state_t *cms, lump_t *l )
{
	int i, count;
	rdface_t *in;
	cface_t	*out;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadFaces_RBSP: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no faces" );

	out = cms->map_faces = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numfaces = count;

	for( i = 0; i < count; i++, in++, out++ )
	{
		out->contents = 0;
		out->numfacets = 0;
		out->facets = NULL;
		if( LittleLong( in->facetype ) != FACETYPE_PATCH )
			continue;
		CMod_LoadFace( cms, out, in->shadernum, in->firstvert, in->numverts, in->patch_cp );
	}
}

/*
   =================
   CMod_LoadSubmodels
   =================
 */
static void CMod_LoadSubmodels( cmodel_state_t *cms, lump_t *l )
{
	int i, j;
	int count;
	dmodel_t *in;
	cmodel_t *out;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadSubmodels: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no models" );

	out = cms->map_cmodels = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numcmodels = count;

	for( i = 0; i < count; i++, in++, out++ )
	{
		out->nummarkfaces = LittleLong( in->numfaces );
		out->markfaces = Mem_Alloc( cms->mempool, out->nummarkfaces * sizeof( cface_t * ) );
		out->nummarkbrushes = LittleLong( in->numbrushes );
		out->markbrushes = Mem_Alloc( cms->mempool, out->nummarkbrushes * sizeof( cbrush_t * ) );

		for( j = 0; j < out->nummarkfaces; j++ )
			out->markfaces[j] = cms->map_faces + LittleLong( in->firstface ) + j;
		for( j = 0; j < out->nummarkbrushes; j++ )
			out->markbrushes[j] = cms->map_brushes + LittleLong( in->firstbrush ) + j;

		for( j = 0; j < 3; j++ )
		{
			// spread the mins / maxs by a pixel
			out->mins[j] = LittleFloat( in->mins[j] ) - 1;
			out->maxs[j] = LittleFloat( in->maxs[j] ) + 1;
		}
	}
}

/*
   =================
   CMod_LoadNodes
   =================
 */
static void CMod_LoadNodes( cmodel_state_t *cms, lump_t *l )
{
	int i;
	int count;
	dnode_t	*in;
	cnode_t	*out;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadNodes: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map has no nodes" );

	out = cms->map_nodes = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numnodes = count;

	for( i = 0; i < 3; i++ )
	{
		cms->world_mins[i] = LittleFloat( in->mins[i] );
		cms->world_maxs[i] = LittleFloat( in->maxs[i] );
	}

	for( i = 0; i < count; i++, out++, in++ )
	{
		out->plane = cms->map_planes + LittleLong( in->planenum );
		out->children[0] = LittleLong( in->children[0] );
		out->children[1] = LittleLong( in->children[1] );
	}
}

/*
   =================
   CMod_LoadMarkFaces
   =================
 */
static void CMod_LoadMarkFaces( cmodel_state_t *cms, lump_t *l )
{
	int i, j;
	int count;
	cface_t	**out;
	int *in;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadMarkFaces: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no leaffaces" );

	out = cms->map_markfaces = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->nummarkfaces = count;

	for( i = 0; i < count; i++ )
	{
		j = LittleLong( in[i] );
		if( j < 0 || j >= cms->numfaces )
			Com_Error( ERR_DROP, "CMod_LoadMarkFaces: bad surface number" );
		out[i] = cms->map_faces + j;
	}
}

/*
   =================
   CMod_LoadLeafs
   =================
 */
static void CMod_LoadLeafs( cmodel_state_t *cms, lump_t *l )
{
	int i, j, k;
	int count;
	cleaf_t	*out;
	dleaf_t	*in;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadLeafs: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no leafs" );

	out = cms->map_leafs = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numleafs = count;

	for( i = 0; i < count; i++, in++, out++ )
	{
		out->contents = 0;
		out->cluster = LittleLong( in->cluster );
		out->area = LittleLong( in->area ) + 1;
		out->markbrushes = cms->map_markbrushes + LittleLong( in->firstleafbrush );
		out->nummarkbrushes = LittleLong( in->numleafbrushes );
		out->markfaces = cms->map_markfaces + LittleLong( in->firstleafface );
		out->nummarkfaces = LittleLong( in->numleaffaces );

		// OR brushes' contents
		for( j = 0; j < out->nummarkbrushes; j++ )
			out->contents |= out->markbrushes[j]->contents;

		// exclude markfaces that have no facets
		// so we don't perform this check at runtime
		for( j = 0; j < out->nummarkfaces; )
		{
			k = j;
			if( !out->markfaces[j]->facets )
			{
				for(; ( ++j < out->nummarkfaces ) && !out->markfaces[j]->facets; ) ;
				if( j < out->nummarkfaces )
					memmove( &out->markfaces[k], &out->markfaces[j], ( out->nummarkfaces - j ) * sizeof( *out->markfaces ) );
				out->nummarkfaces -= j - k;

			}
			j = k + 1;
		}

		// OR patches' contents
		for( j = 0; j < out->nummarkfaces; j++ )
			out->contents |= out->markfaces[j]->contents;

		if( out->area >= cms->numareas )
			cms->numareas = out->area + 1;
	}

	cms->map_areas = Mem_Alloc( cms->mempool, cms->numareas * sizeof( *cms->map_areas ) );
}

/*
   =================
   CMod_LoadPlanes
   =================
 */
static void CMod_LoadPlanes( cmodel_state_t *cms, lump_t *l )
{
	int i, j;
	int count;
	cplane_t *out;
	dplane_t *in;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadPlanes: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no planes" );

	out = cms->map_planes = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numplanes = count;

	for( i = 0; i < count; i++, in++, out++ )
	{
		out->signbits = 0;
		out->type = PLANE_NONAXIAL;

		for( j = 0; j < 3; j++ )
		{
			out->normal[j] = LittleFloat( in->normal[j] );
			if( out->normal[j] < 0 )
				out->signbits |= ( 1 << j );
			if( out->normal[j] == 1.0f )
				out->type = j;
		}

		out->dist = LittleFloat( in->dist );
	}
}

/*
   =================
   CMod_LoadMarkBrushes
   =================
 */
static void CMod_LoadMarkBrushes( cmodel_state_t *cms, lump_t *l )
{
	int i;
	int count;
	cbrush_t **out;
	int *in;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadMarkBrushes: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no leafbrushes" );

	out = cms->map_markbrushes = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->nummarkbrushes = count;

	for( i = 0; i < count; i++, in++ )
		out[i] = cms->map_brushes + LittleLong( *in );
}

/*
   =================
   CMod_LoadBrushSides
   =================
 */
static void CMod_LoadBrushSides( cmodel_state_t *cms, lump_t *l )
{
	int i, j;
	int count;
	cbrushside_t *out;
	dbrushside_t *in;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadBrushSides: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no brushsides" );

	out = cms->map_brushsides = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numbrushsides = count;

	for( i = 0; i < count; i++, in++, out++ )
	{
		out->plane = cms->map_planes + LittleLong( in->planenum );
		j = LittleLong( in->shadernum );
		if( j >= cms->numshaderrefs )
			Com_Error( ERR_DROP, "Bad brushside texinfo" );
		out->surfFlags = cms->map_shaderrefs[j].flags;
	}
}

/*
   =================
   CMod_LoadBrushSides_RBSP
   =================
 */
static void CMod_LoadBrushSides_RBSP( cmodel_state_t *cms, lump_t *l )
{
	int i, j;
	int count;
	cbrushside_t *out;
	rdbrushside_t *in;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadBrushSides_RBSP: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no brushsides" );

	out = cms->map_brushsides = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numbrushsides = count;

	for( i = 0; i < count; i++, in++, out++ )
	{
		out->plane = cms->map_planes + LittleLong( in->planenum );
		j = LittleLong( in->shadernum );
		if( j >= cms->numshaderrefs )
			Com_Error( ERR_DROP, "Bad brushside texinfo" );
		out->surfFlags = cms->map_shaderrefs[j].flags;
	}
}

/*
   =================
   CMod_LoadBrushes
   =================
 */
static void CMod_LoadBrushes( cmodel_state_t *cms, lump_t *l )
{
	int i;
	int count;
	dbrush_t *in;
	cbrush_t *out;
	int shaderref;

	in = ( void * )( cms->cmod_base + l->fileofs );
	if( l->filelen % sizeof( *in ) )
		Com_Error( ERR_DROP, "CMod_LoadBrushes: funny lump size" );
	count = l->filelen / sizeof( *in );
	if( count < 1 )
		Com_Error( ERR_DROP, "Map with no brushes" );

	out = cms->map_brushes = Mem_Alloc( cms->mempool, count * sizeof( *out ) );
	cms->numbrushes = count;

	for( i = 0; i < count; i++, out++, in++ )
	{
		shaderref = LittleLong( in->shadernum );
		out->contents = cms->map_shaderrefs[shaderref].contents;
		out->numsides = LittleLong( in->numsides );
		out->brushsides = cms->map_brushsides + LittleLong( in->firstside );
	}
}

/*
   =================
   CMod_LoadVisibility
   =================
 */
static void CMod_LoadVisibility( cmodel_state_t *cms, lump_t *l )
{
	cms->map_visdatasize = l->filelen;
	if( !cms->map_visdatasize )
	{
		cms->map_pvs = NULL;
		return;
	}

	cms->map_pvs = Mem_Alloc( cms->mempool, cms->map_visdatasize );
	memcpy( cms->map_pvs, cms->cmod_base + l->fileofs, cms->map_visdatasize );

	cms->map_pvs->numclusters = LittleLong( cms->map_pvs->numclusters );
	cms->map_pvs->rowsize = LittleLong( cms->map_pvs->rowsize );
}


/*
   =================
   CMod_LoadEntityString
   =================
 */
static void CMod_LoadEntityString( cmodel_state_t *cms, lump_t *l )
{
	cms->numentitychars = l->filelen;
	if( !l->filelen )
		return;

	cms->map_entitystring = Mem_Alloc( cms->mempool, cms->numentitychars );
	memcpy( cms->map_entitystring, cms->cmod_base + l->fileofs, l->filelen );
}

/*
   ==================
   CM_LoadMap

   Loads in the map and all submodels

   // for spawning a server with no map at all, call like this:
   // CM_LoadMap( "", qfalse, &checksum );	// no real map
   ==================
 */
cmodel_t *CM_LoadMap( cmodel_state_t *cms, char *name, qboolean clientload, unsigned *checksum )
{
	unsigned *buf;
	int i;
	dheader_t header;
	int length, version;

	assert( cms );
	assert( name && strlen( name ) < MAX_CONFIGSTRING_CHARS );
	assert( checksum );

	cms->map_clientload = clientload;

	if( !strcmp( cms->map_name, name ) && ( clientload || !Cvar_Value( "flushmap" ) ) )
	{
		*checksum = cms->checksum;
		if( !clientload )
		{
			memset( cms->map_areaportals, 0, sizeof( cms->map_areaportals ) );
			CM_FloodAreaConnections( cms );
		}
		return cms->map_cmodels; // still have the right version
	}

	CM_Clear( cms );

	if( !name || !name[0] )
	{
		cms->numleafs = 1;
		cms->numcmodels = 2;
		*checksum = 0;
		return cms->map_cmodels;    // cinematic servers won't have anything at all
	}

	//
	// load the file
	//
	length = FS_LoadFile( name, ( void ** )&buf, NULL, 0 );
	if( !buf )
		Com_Error( ERR_DROP, "Couldn't load %s", name );

	cms->checksum = Com_BlockChecksum( buf, length );
	*checksum = cms->checksum;

	header = *(dheader_t *)buf;
	version = LittleLong( header.version );
	for( i = 0, cms->cmap_bspFormat = bspFormats; i < numBspFormats; i++, cms->cmap_bspFormat++ )
	{
		if( !strncmp( (char *)buf, cms->cmap_bspFormat->header, 4 ) && ( version == cms->cmap_bspFormat->version ) )
			break;
	}
	if( i == numBspFormats )
		Com_Error( ERR_DROP, "CM_LoadMap: %s: unknown bsp format, version %i", name, version );

	for( i = 0; i < sizeof( dheader_t ) / 4; i++ )
		( (int *)&header )[i] = LittleLong( ( (int *)&header )[i] );
	cms->cmod_base = ( qbyte * )buf;

	// load into heap
	CMod_LoadSurfaces( cms, &header.lumps[LUMP_SHADERREFS] );
	CMod_LoadPlanes( cms, &header.lumps[LUMP_PLANES] );
	if( cms->cmap_bspFormat->flags & BSP_RAVEN )
		CMod_LoadBrushSides_RBSP( cms, &header.lumps[LUMP_BRUSHSIDES] );
	else
		CMod_LoadBrushSides( cms, &header.lumps[LUMP_BRUSHSIDES] );
	CMod_LoadBrushes( cms, &header.lumps[LUMP_BRUSHES] );
	CMod_LoadMarkBrushes( cms, &header.lumps[LUMP_LEAFBRUSHES] );
	if( cms->cmap_bspFormat->flags & BSP_RAVEN )
	{
		CMod_LoadVertexes_RBSP( cms, &header.lumps[LUMP_VERTEXES] );
		CMod_LoadFaces_RBSP( cms, &header.lumps[LUMP_FACES] );
	}
	else
	{
		CMod_LoadVertexes( cms, &header.lumps[LUMP_VERTEXES] );
		CMod_LoadFaces( cms, &header.lumps[LUMP_FACES] );
	}
	CMod_LoadMarkFaces( cms, &header.lumps[LUMP_LEAFFACES] );
	CMod_LoadLeafs( cms, &header.lumps[LUMP_LEAFS] );
	CMod_LoadNodes( cms, &header.lumps[LUMP_NODES] );
	CMod_LoadSubmodels( cms, &header.lumps[LUMP_MODELS] );
	CMod_LoadVisibility( cms, &header.lumps[LUMP_VISIBILITY] );
	CMod_LoadEntityString( cms, &header.lumps[LUMP_ENTITIES] );

	FS_FreeFile( buf );

	CM_InitBoxHull( cms );

	memset( cms->map_areaportals, 0, sizeof( cms->map_areaportals ) );
	CM_FloodAreaConnections( cms );

	CM_CalcPHS( cms );

	if( cms->numvertexes )
		Mem_Free( cms->map_verts );

	memset( cms->nullrow, 255, MAX_CM_LEAFS / 8 );

	Q_strncpyz( cms->map_name, name, sizeof( cms->map_name ) );

	return cms->map_cmodels;
}

/*
   ==================
   CM_LoadMapMessage
   ==================
 */
char *CM_LoadMapMessage( char *name, char *message, int size )
{
	int i, file, len;
	char ident[4], *data, *entitystring;
	int version;
	bspFormatDesc_t *format;
	lump_t l;
	qboolean isworld;
	char key[MAX_KEY], value[MAX_VALUE], *token;

	*message = '\0';

	len = FS_FOpenFile( name, &file, FS_READ );
	if( !file || len < 1 )
	{
		if( file )
			FS_FCloseFile( file );
		return message;
	}

	FS_Read( ident, sizeof( ident ), file );
	FS_Read( &version, sizeof( version ), file );

	version = LittleLong( version );
	for( i = 0, format = bspFormats; i < numBspFormats; i++, format++ )
	{
		if( !strncmp( ident, format->header, 4 ) && ( version == format->version ) )
			break;
	}

	if( i == numBspFormats )
	{
		Com_Printf( "CM_LoadMapMessage: %s: unknown bsp format, version %i", name, version );
		FS_FCloseFile( file );
		return message;
	}

	FS_Seek( file, sizeof( lump_t ) * LUMP_ENTITIES, FS_SEEK_CUR );

	FS_Read( &l.fileofs, sizeof( l.fileofs ), file );
	l.fileofs = LittleLong( l.fileofs );

	FS_Read( &l.filelen, sizeof( l.filelen ), file );
	l.filelen = LittleLong( l.filelen );

	if( !l.filelen )
	{
		FS_FCloseFile( file );
		return message;
	}

	FS_Seek( file, l.fileofs, FS_SEEK_SET );

	entitystring = Mem_TempMalloc( l.filelen );
	FS_Read( entitystring, l.filelen, file );

	FS_FCloseFile( file );

	for( data = entitystring; ( token = COM_Parse( &data ) ) && token[0] == '{'; )
	{
		isworld = qtrue;

		while( 1 )
		{
			token = COM_Parse( &data );
			if( !token[0] || token[0] == '}' )
				break; // end of entity

			Q_strncpyz( key, token, sizeof( key ) );
			while( key[strlen( key )-1] == ' ' )  // remove trailing spaces
				key[strlen( key )-1] = 0;

			token = COM_Parse( &data );
			if( !token[0] )
				break; // error

			Q_strncpyz( value, token, sizeof( value ) );

			// now that we have the key pair worked out...
			if( !strcmp( key, "classname" ) )
			{
				if( strcmp( value, "worldspawn" ) )
					isworld = qfalse;
			}
			else if( isworld && !strcmp( key, "message" ) )
			{
				Q_strncpyz( message, token, size );
				break;
			}
		}

		if( isworld )
			break;
	}

	Mem_Free( entitystring );

	return message;
}

/*
   ==================
   CM_ClientLoad

   FIXME!
   ==================
 */
qboolean CM_ClientLoad( cmodel_state_t *cms )
{
	return cms->map_clientload;
}

/*
   ==================
   CM_InlineModel
   ==================
 */
cmodel_t *CM_InlineModel( cmodel_state_t *cms, int num )
{
	if( num < 0 || num >= cms->numcmodels )
		Com_Error( ERR_DROP, "CM_InlineModel: bad number %i (%i)", num, cms->numcmodels );
	return &cms->map_cmodels[num];
}

/*
   =================
   CM_NumInlineModels
   =================
 */
int CM_NumInlineModels( cmodel_state_t *cms )
{
	return cms->numcmodels;
}

/*
   =================
   CM_InlineModelBounds
   =================
 */
void CM_InlineModelBounds( cmodel_state_t *cms, cmodel_t *cmodel, vec3_t mins, vec3_t maxs )
{
	if( cmodel == cms->map_cmodels )
	{
		VectorCopy( cms->world_mins, mins );
		VectorCopy( cms->world_maxs, maxs );
	}
	else
	{
		VectorCopy( cmodel->mins, mins );
		VectorCopy( cmodel->maxs, maxs );
	}
}

/*
   =================
   CM_ShaderrefName
   =================
 */
const char *CM_ShaderrefName( cmodel_state_t *cms, int ref )
{
	if( ref < 0 || ref >= cms->numshaderrefs )
		return NULL;
	return cms->map_shaderrefs[ref].name;
}

/*
   =================
   CM_EntityStringLen
   =================
 */
int CM_EntityStringLen( cmodel_state_t *cms )
{
	return cms->numentitychars;
}

/*
   =================
   CM_EntityString
   =================
 */
char *CM_EntityString( cmodel_state_t *cms )
{
	return cms->map_entitystring;
}

/*
   =================
   CM_LeafCluster
   =================
 */
int CM_LeafCluster( cmodel_state_t *cms, int leafnum )
{
	if( leafnum < 0 || leafnum >= cms->numleafs )
		Com_Error( ERR_DROP, "CM_LeafCluster: bad number" );
	return cms->map_leafs[leafnum].cluster;
}

/*
   =================
   CM_LeafArea
   =================
 */
int CM_LeafArea( cmodel_state_t *cms, int leafnum )
{
	if( leafnum < 0 || leafnum >= cms->numleafs )
		Com_Error( ERR_DROP, "CM_LeafArea: bad number" );
	return cms->map_leafs[leafnum].area;
}

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

   PVS / PHS

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

/*
   =================
   CM_CalcPHS
   =================
 */
void CM_CalcPHS( cmodel_state_t *cms )
{
	int i, j, k, l, index;
	int rowbytes, rowwords;
	int bitbyte;
	unsigned int *dest, *src;
	qbyte *scan;
	int count, vcount;

	if( !cms->map_pvs )
	{
		cms->map_phs = NULL;
		return;
	}

	Com_DPrintf( "Building PHS...\n" );

	cms->map_phs = Mem_Alloc( cms->mempool, cms->map_visdatasize );
	cms->map_phs->rowsize = cms->map_pvs->rowsize;
	cms->map_phs->numclusters = cms->map_pvs->numclusters;

	rowbytes = cms->map_pvs->rowsize;
	rowwords = rowbytes / sizeof( int );

	vcount = 0;
	for( i = 0; i < cms->map_pvs->numclusters; i++ )
	{
		scan = CM_ClusterPVS( cms, i );
		for( j = 0; j < cms->map_pvs->numclusters; j++ )
		{
			if( scan[j>>3] & ( 1<<( j&7 ) ) )
				vcount++;
		}
	}

	count = 0;
	scan = ( qbyte * )cms->map_pvs->data;
	dest = ( unsigned int * )( ( qbyte * )cms->map_phs->data );

	for( i = 0; i < cms->map_phs->numclusters; i++, dest += rowwords, scan += rowbytes )
	{
		memcpy( dest, scan, rowbytes );

		for( j = 0; j < rowbytes; j++ )
		{
			bitbyte = scan[j];
			if( !bitbyte )
				continue;
			for( k = 0; k < 8; k++ )
			{
				if( !( bitbyte & ( 1<<k ) ) )
					continue;

				// OR this pvs row into the phs
				index = ( j << 3 ) + k;
				if( index >= cms->map_phs->numclusters )
					Com_Error( ERR_DROP, "CM_CalcPHS: Bad bit in PVS" ); // pad bits should be 0

				src = ( unsigned int * )( ( qbyte * )cms->map_pvs->data ) + index * rowwords;
				for( l = 0; l < rowwords; l++ )
					dest[l] |= src[l];
			}
		}
		for( j = 0; j < cms->map_phs->numclusters; j++ )
			if( ( ( qbyte * )dest )[j>>3] & ( 1<<( j&7 ) ) )
				count++;
	}

	Com_DPrintf( "Average clusters visible / hearable / total: %i / %i / %i\n", vcount/cms->map_phs->numclusters,
	             count/cms->map_phs->numclusters, cms->map_phs->numclusters );
}

/*
   =================
   CM_ClusterSize
   =================
 */
int CM_ClusterSize( cmodel_state_t *cms )
{
	return cms->map_pvs ? cms->map_pvs->rowsize : MAX_CM_LEAFS / 8;
}

/*
   =================
   CM_NumClusters
   =================
 */
int CM_NumClusters( cmodel_state_t *cms )
{
	return cms->map_pvs->numclusters;
}

/*
   =================
   CM_VisData
   =================
 */
dvis_t *CM_VisData( cmodel_state_t *cms )
{
	return cms->map_pvs;
}

/*
   =================
   CM_ClusterPVS
   =================
 */
qbyte *CM_ClusterPVS( cmodel_state_t *cms, int cluster )
{
	if( cluster == -1 || !cms->map_pvs )
		return cms->nullrow;
	return ( qbyte * )cms->map_pvs->data + cluster * cms->map_pvs->rowsize;
}

/*
   =================
   CM_ClusterPHS
   =================
 */
qbyte *CM_ClusterPHS( cmodel_state_t *cms, int cluster )
{
	if( cluster == -1 || !cms->map_phs )
		return cms->nullrow;
	return ( qbyte * )cms->map_phs->data + cluster * cms->map_phs->rowsize;
}

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

   AREAPORTALS

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

/*
   =================
   CM_AddAreaPortal
   =================
 */
static qboolean CM_AddAreaPortal( cmodel_state_t *cms, int portalnum, int area, int otherarea )
{
	carea_t *a;
	careaportal_t *ap;

	if( portalnum >= MAX_CM_AREAPORTALS )
		return qfalse;
	if( !area || area > cms->numareas || !otherarea || otherarea > cms->numareas )
		return qfalse;

	ap = &cms->map_areaportals[portalnum];
	ap->area = area;
	ap->otherarea = otherarea;

	a = &cms->map_areas[area];
	a->areaportals[a->numareaportals++] = portalnum;

	a = &cms->map_areas[otherarea];
	a->areaportals[a->numareaportals++] = portalnum;

	cms->numareaportals++;

	return qtrue;
}

/*
   =================
   CM_FloodArea_r
   =================
 */
static void CM_FloodArea_r( cmodel_state_t *cms, int areanum, int floodnum )
{
	int i;
	carea_t	*area;
	careaportal_t *p;

	area = &cms->map_areas[areanum];
	if( area->floodvalid == cms->floodvalid )
	{
		if( area->floodnum == floodnum )
			return;
		Com_Error( ERR_DROP, "FloodArea_r: reflooded" );
	}

	area->floodnum = floodnum;
	area->floodvalid = cms->floodvalid;
	for( i = 0; i < area->numareaportals; i++ )
	{
		p = &cms->map_areaportals[area->areaportals[i]];
		if( !p->open )
			continue;

		if( p->area == areanum )
			CM_FloodArea_r( cms, p->otherarea, floodnum );
		else if( p->otherarea == areanum )
			CM_FloodArea_r( cms, p->area, floodnum );
	}
}

/*
   ====================
   CM_FloodAreaConnections
   ====================
 */
void CM_FloodAreaConnections( cmodel_state_t *cms )
{
	int i;
	int floodnum;

	// all current floods are now invalid
	cms->floodvalid++;
	floodnum = 0;

	// area 0 is not used
	for( i = 1; i < cms->numareas; i++ )
	{
		if( cms->map_areas[i].floodvalid == cms->floodvalid )
			continue; // already flooded into
		floodnum++;
		CM_FloodArea_r( cms, i, floodnum );
	}
}

/*
   =================
   CM_SetAreaPortalState
   =================
 */
void CM_SetAreaPortalState( cmodel_state_t *cms, int portalnum, int area, int otherarea, qboolean open )
{
	if( portalnum >= MAX_CM_AREAPORTALS )
		Com_Error( ERR_DROP, "areaportal >= MAX_CM_AREAPORTALS" );

	if( !cms->map_areaportals[portalnum].area )
	{
		// add new areaportal if it doesn't exist
		if( !CM_AddAreaPortal( cms, portalnum, area, otherarea ) )
			return;
	}

	cms->map_areaportals[portalnum].open = open;
	CM_FloodAreaConnections( cms );
}

/*
   =================
   CM_AreasConnected
   =================
 */
qboolean CM_AreasConnected( cmodel_state_t *cms, int area1, int area2 )
{
	if( cm_noAreas->integer )
		return qtrue;

	if( area1 > cms->numareas || area2 > cms->numareas )
		Com_Error( ERR_DROP, "CM_AreasConnected: area > numareas" );

	if( cms->map_areas[area1].floodnum == cms->map_areas[area2].floodnum )
		return qtrue;

	return qfalse;
}

/*
   =================
   CM_WriteAreaBits

   Writes a length byte followed by a bit vector of all the areas
   that area in the same flood as the area parameter

   This is used by the client refreshes to cull visibility
   =================
 */
int CM_WriteAreaBits( cmodel_state_t *cms, qbyte *buffer, int area )
{
	int i;
	int bytes;

	bytes = ( cms->numareas + 7 ) >> 3;

	if( cm_noAreas->integer || area == -1 )
	{
		// for debugging, send everything
		memset( buffer, 255, bytes );
	}
	else
	{
		memset( buffer, 0, bytes );

		for( i = 1; i < cms->numareas; i++ )
		{
			if( !area || i == area || CM_AreasConnected( cms, i, area ) )
				buffer[i>>3] |= 1<<( i&7 );
		}
	}

	return bytes;
}

/*
   =================
   CM_MergeAreaBits
   =================
 */
void CM_MergeAreaBits( cmodel_state_t *cms, qbyte *buffer, int area )
{
	int i;

	for( i = 1; i < cms->numareas; i++ )
	{
		if( CM_AreasConnected( cms, i, area ) || i == area )
			buffer[i>>3] |= 1 << ( i&7 );
	}
}

/*
   ===================
   CM_WritePortalState

   Writes the portal state to a savegame file
   ===================
 */
void CM_WritePortalState( cmodel_state_t *cms, int file )
{
	int i, j;

	FS_Write( &cms->numareaportals, sizeof( int ), file );

	for( i = 1; i < MAX_CM_AREAPORTALS; i++ )
	{
		if( cms->map_areaportals[i].area )
		{
			FS_Write( &i, sizeof( int ), file );
			FS_Write( &cms->map_areaportals[i], sizeof( cms->map_areaportals[0] ), file );
		}
	}

	FS_Write( &cms->numareas, sizeof( int ), file );

	for( i = 1; i < cms->numareas; i++ )
	{
		FS_Write( &cms->map_areas[i].numareaportals, sizeof( int ), file );

		for( j = 0; j < cms->map_areas[i].numareaportals; j++ )
			FS_Write( &cms->map_areas[i].areaportals[j], sizeof( int ), file );
	}
}

/*
   ===================
   CM_ReadPortalState

   Reads the portal state from a savegame file
   and recalculates the area connections
   ===================
 */
void CM_ReadPortalState( cmodel_state_t *cms, int file )
{
	int i, j;

	FS_Read( &cms->numareaportals, sizeof( int ), file );
	for( i = 1; i < cms->numareaportals; i++ )
	{
		FS_Read( &j, sizeof( int ), file );
		FS_Read( &cms->map_areaportals[j], sizeof( cms->map_areaportals[0] ), file );
	}

	FS_Read( &cms->numareas, sizeof( int ), file );

	for( i = 1; i < cms->numareas; i++ )
	{
		FS_Read( &cms->map_areas[i].numareaportals, sizeof( int ), file );

		for( j = 0; j < cms->map_areas[i].numareaportals; j++ )
			FS_Read( &cms->map_areas[i].areaportals[j], sizeof( int ), file );
	}

	CM_FloodAreaConnections( cms );
}

/*
   =============
   CM_HeadnodeVisible

   Returns true if any leaf under headnode has a cluster that
   is potentially visible
   =============
 */
qboolean CM_HeadnodeVisible( cmodel_state_t *cms, int nodenum, qbyte *visbits )
{
	int cluster;
	cnode_t	*node;

	while( nodenum >= 0 )
	{
		node = &cms->map_nodes[nodenum];
		if( CM_HeadnodeVisible( cms, node->children[0], visbits ) )
			return qtrue;
		nodenum = node->children[1];
	}

	cluster = cms->map_leafs[-1 - nodenum].cluster;
	if( cluster == -1 )
		return qfalse;
	if( visbits[cluster>>3] & ( 1<<( cluster&7 ) ) )
		return qtrue;
	return qfalse;
}


//============
//CM_MergePVS
//
//Merge PVS at origin into out
//===========
void CM_MergePVS( cmodel_state_t *cms, vec3_t org, qbyte *out )
{
	int leafs[128];
	int i, j, count;
	int longs;
	qbyte *src;
	vec3_t mins, maxs;

	for( i = 0; i < 3; i++ )
	{
		mins[i] = org[i] - 1;
		maxs[i] = org[i] + 1;
	}

	count = CM_BoxLeafnums( cms, mins, maxs, leafs, sizeof( leafs )/sizeof( int ), NULL );
	if( count < 1 )
		Com_Error( ERR_FATAL, "CM_MergePVS: count < 1" );
	longs = CM_ClusterSize( cms ) / sizeof( int );

	// convert leafs to clusters
	for( i = 0; i < count; i++ )
		leafs[i] = CM_LeafCluster( cms, leafs[i] );

	// or in all the other leaf bits
	for( i = 0; i < count; i++ )
	{
		for( j = 0; j < i; j++ )
			if( leafs[i] == leafs[j] )
				break;
		if( j != i )
			continue; // already have the cluster we want
		src = CM_ClusterPVS( cms, leafs[i] );
		for( j = 0; j < longs; j++ )
			( (int *)out )[j] |= ( (int *)src )[j];
	}
}

//============
//CM_MergePHS
//===========
void CM_MergePHS( cmodel_state_t *cms, int cluster, qbyte *out )
{
	int i, longs;
	qbyte *src;

	longs = CM_ClusterSize( cms ) / sizeof( int );

	// or in all the other leaf bits
	src = CM_ClusterPHS( cms, cluster );
	for( i = 0; i < longs; i++ )
		( (int *)out )[i] |= ( (int *)src )[i];
}

//============
//CM_MergeVisSets
//============
void CM_MergeVisSets( cmodel_state_t *cms, vec3_t org, qbyte *pvs, qbyte *phs, qbyte *areabits )
{
	int area;

	assert( pvs || phs || areabits );

	if( pvs )
		CM_MergePVS( cms, org, pvs );

	area = CM_PointLeafnum( cms, org );
	if( phs )
		CM_MergePHS( cms, CM_LeafCluster( cms, area ), phs );

	area = CM_LeafArea( cms, area );
	if( pvs )
		CM_MergeAreaBits( cms, areabits, area );
}

/*
   =============
   CM_New
   =============
 */
cmodel_state_t *CM_New( void *mempool )
{
	cmodel_state_t *cms;
	mempool_t *cms_mempool;

	cms_mempool = (mempool ? (mempool_t *)mempool : cmap_mempool);
	cms = Mem_Alloc( cms_mempool, sizeof( cmodel_state_t ) );

	cms->mempool = cms_mempool;
	cms->map_cmodels = &cms->map_cmodel_empty;
	cms->map_leafs = &cms->map_leaf_empty;
	cms->map_areas = &cms->map_area_empty;
	cms->map_entitystring = &cms->map_entitystring_empty;

	return cms;
}

/*
   =============
   CM_Free
   =============
 */
void CM_Free( cmodel_state_t *cms )
{
	CM_Clear( cms );

	Mem_Free( cms );
}

/*
   =============
   CM_Init
   =============
 */
void CM_Init( void )
{
	assert( !cm_initialized );

	cmap_mempool = Mem_AllocPool( NULL, "Collision Map" );

	cm_noAreas =	    Cvar_Get( "cm_noAreas", "0", CVAR_CHEAT );
	cm_noCurves =	    Cvar_Get( "cm_noCurves", "0", CVAR_CHEAT );

	cm_initialized = qtrue;
}

/*
   =============
   CM_Shutdown
   =============
 */
void CM_Shutdown( void )
{
	if( !cm_initialized )
		return;

	Mem_FreePool( &cmap_mempool );

	cm_initialized = qfalse;
}
