/*****************************************************************************
The Dark Mod GPL Source Code

This file is part of the The Dark Mod Source Code, originally based
on the Doom 3 GPL Source Code as published in 2011.

The Dark Mod 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. For details, see LICENSE.TXT.

Project: The Dark Mod (http://www.thedarkmod.com/)

******************************************************************************/

#include "precompiled.h"
#pragma hdrstop



#include "dmap.h"


#define	 TEXTURE_OFFSET_EQUAL_EPSILON	0.005
#define	 TEXTURE_VECTOR_EQUAL_EPSILON	0.001

idCVar dmap_fasterPutPrimitives(
	"dmap_fasterPutPrimitives", "1", CVAR_BOOL | CVAR_SYSTEM,
	"If set to 1, then use faster data structures for groups search in PutPrimitivesInAreas. "
	"This is performance improvement in TDM 2.10."
);
struct groupsPerPlane_s {
	idHashIndex hash;
	idList<struct optimizeGroup_s *> lists;
};

/*
===============
AddTriListToArea

The triList is appended to the apropriate optimzeGroup_t,
creating a new one if needed.
The entire list is assumed to come from the same planar primitive
===============
*/
static void AddTriListToArea( uEntity_t *e, mapTri_t *triList, int planeNum, int areaNum, textureVectors_t *texVec ) {
	uArea_t		*area;
	optimizeGroup_t	*group;
	int			i, j;

	if ( !triList ) {
		return;
	}
	area = &e->areas[areaNum];

	optimizeGroup_t* *groupsList = &area->groups;
	if (dmap_fasterPutPrimitives.GetBool()) {
		groupsPerPlane_s &gpp = *area->groupsPerPlane;
		//stgatilov: try to find list for this planeNum in hash table
		groupsList = nullptr;
		for (int i = gpp.hash.First(planeNum); i >= 0; i = gpp.hash.Next(i)) {
			if (gpp.lists[i]->planeNum == planeNum) {
				groupsList = &gpp.lists[i];
				break;
			}
		}
		if (!groupsList) {
			//not found: create a new list
			gpp.lists.AddGrow(nullptr);
			gpp.hash.Add(planeNum, gpp.lists.Num() - 1);
			groupsList = &gpp.lists[gpp.lists.Num() - 1];
		}
	}

	for ( group = *groupsList ; group ; group = group->nextGroup ) {
		if ( group->material == triList->material
			&& group->planeNum == planeNum
			&& group->mergeGroup == triList->mergeGroup ) {
			// check the texture vectors
			for ( i = 0 ; i < 2 ; i++ ) {
				for ( j = 0 ; j < 3 ; j++ ) {
					if ( idMath::Fabs( texVec->v[i][j] - group->texVec.v[i][j] ) > TEXTURE_VECTOR_EQUAL_EPSILON ) {
						break;
					}
				}
				if ( j != 3 ) {
					break;
				}
				if ( idMath::Fabs( texVec->v[i][3] - group->texVec.v[i][3] ) > TEXTURE_OFFSET_EQUAL_EPSILON ) {
					break;
				}
			}
			if ( i == 2 ) {
				break;	// exact match
			} else {
				// different texture offsets
				i = 1;	// just for debugger breakpoint
			}
		}
	}

	if ( !group ) {
		group = (optimizeGroup_t *)Mem_Alloc( sizeof( *group ) );
		memset( group, 0, sizeof( *group ) );
		group->planeNum = planeNum;
		group->mergeGroup = triList->mergeGroup;
		group->material = triList->material;
		group->nextGroup = *groupsList;
		group->texVec = *texVec;
		*groupsList = group;
	}

	group->triList = MergeTriLists( group->triList, triList );
}

/*
===================
TexVecForTri
===================
*/
static void TexVecForTri( textureVectors_t *texVec, mapTri_t *tri ) {
	float	area, inva;
	idVec3	temp;
	idVec5	d0, d1;
	idDrawVert	*a, *b, *c;

	a = &tri->v[0];
	b = &tri->v[1];
	c = &tri->v[2];

	d0[0] = b->xyz[0] - a->xyz[0];
	d0[1] = b->xyz[1] - a->xyz[1];
	d0[2] = b->xyz[2] - a->xyz[2];
	d0[3] = b->st[0] - a->st[0];
	d0[4] = b->st[1] - a->st[1];

	d1[0] = c->xyz[0] - a->xyz[0];
	d1[1] = c->xyz[1] - a->xyz[1];
	d1[2] = c->xyz[2] - a->xyz[2];
	d1[3] = c->st[0] - a->st[0];
	d1[4] = c->st[1] - a->st[1];

	area = d0[3] * d1[4] - d0[4] * d1[3];
	inva = 1.0 / area;

    temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]) * inva;
    temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]) * inva;
    temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]) * inva;
	temp.Normalize();
	texVec->v[0].ToVec3() = temp;
	texVec->v[0][3] = tri->v[0].xyz * texVec->v[0].ToVec3() - tri->v[0].st[0];

    temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]) * inva;
    temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]) * inva;
    temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]) * inva;
	temp.Normalize();
	texVec->v[1].ToVec3() = temp;
	texVec->v[1][3] = tri->v[0].xyz * texVec->v[0].ToVec3() - tri->v[0].st[1];
}


/*
=================
TriListForSide
=================
*/
//#define	SNAP_FLOAT_TO_INT	8
#define	SNAP_FLOAT_TO_INT	256
#define	SNAP_INT_TO_FLOAT	(1.0/SNAP_FLOAT_TO_INT)

mapTri_t *TriListForSide( const side_t *s, const idWinding *w ) {
	int				i, j;
	idDrawVert		*dv;
	mapTri_t		*tri, *triList;
	const idVec3		*vec;
	const idMaterial	*si;

	si = s->material;

	// skip any generated faces
	if ( !si ) {
		return NULL;
	}

	// don't create faces for non-visible sides
	if ( !si->SurfaceCastsShadow() && !si->IsDrawn() ) {
		return NULL;
	}

	if ( 1 ) {
		// triangle fan using only the outer verts
		// this gives the minimum triangle count,
		// but may have some very distended triangles
		triList = NULL;
		for ( i = 2 ; i < w->GetNumPoints() ; i++ ) {
			tri = AllocTri();
			tri->material = si;	
			tri->next = triList;
			triList = tri;

			for ( j = 0 ; j < 3 ; j++ ) {
				if ( j == 0 ) {
					vec = &((*w)[0]).ToVec3();
				} else if ( j == 1 ) {
					vec = &((*w)[i-1]).ToVec3();
				} else {
					vec = &((*w)[i]).ToVec3();
				}

				dv = tri->v + j;
#if 0
				// round the xyz to a given precision
				for ( k = 0 ; k < 3 ; k++ ) {
					dv->xyz[k] = SNAP_INT_TO_FLOAT * floor( vec[k] * SNAP_FLOAT_TO_INT + 0.5 );
				}
#else
				VectorCopy( *vec, dv->xyz );
#endif
				
				// calculate texture s/t from brush primitive texture matrix
				dv->st[0] = DotProduct( dv->xyz, s->texVec.v[0] ) + s->texVec.v[0][3];
				dv->st[1] = DotProduct( dv->xyz, s->texVec.v[1] ) + s->texVec.v[1][3];

				// copy normal
				dv->normal = dmapGlobals.mapPlanes[s->planenum].Normal();
				if ( dv->normal.Length() < 0.9 || dv->normal.Length() > 1.1 ) {
					common->Error( "Bad normal in TriListForSide" );
				}
			}
		}
	} else {
		// triangle fan from central point, more verts and tris, but less distended
		// I use this when debugging some tjunction problems
		triList = NULL;
		for ( i = 0 ; i < w->GetNumPoints() ; i++ ) {
			idVec3	midPoint;

			tri = AllocTri();
			tri->material = si;	
			tri->next = triList;
			triList = tri;

			for ( j = 0 ; j < 3 ; j++ ) {
				if ( j == 0 ) {
					vec = &midPoint;
					midPoint = w->GetCenter();
				} else if ( j == 1 ) {
					vec = &((*w)[i]).ToVec3();
				} else {
					vec = &((*w)[(i+1)%w->GetNumPoints()]).ToVec3();
				}

				dv = tri->v + j;

				VectorCopy( *vec, dv->xyz );
				
				// calculate texture s/t from brush primitive texture matrix
				dv->st[0] = DotProduct( dv->xyz, s->texVec.v[0] ) + s->texVec.v[0][3];
				dv->st[1] = DotProduct( dv->xyz, s->texVec.v[1] ) + s->texVec.v[1][3];

				// copy normal
				dv->normal = dmapGlobals.mapPlanes[s->planenum].Normal();
				if ( dv->normal.Length() < 0.9f || dv->normal.Length() > 1.1f ) {
					common->Error( "Bad normal in TriListForSide" );
				}
			}
		}
	}

	// set merge groups if needed, to prevent multiple sides from being
	// merged into a single surface in the case of gui shaders, mirrors, and autosprites
	if ( s->material->IsDiscrete() ) {
		for ( tri = triList ; tri ; tri = tri->next ) {
			tri->mergeGroup = (void *)s;
		}
	}

	return triList;
}

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

/*
====================
ClipSideByTree_r

Adds non-opaque leaf fragments to the convex hull
====================
*/
static void ClipSideByTree_r( idWinding *w, side_t *side, node_t *node ) {
	idWinding		*front, *back;

	if ( !w ) {
		return;
	}

	if ( node->planenum != PLANENUM_LEAF ) {
		if ( side->planenum == node->planenum ) {
			ClipSideByTree_r( w, side, node->children[0] );
			return;
		}
		if ( side->planenum == ( node->planenum ^ 1) ) {
			ClipSideByTree_r( w, side, node->children[1] );
			return;
		}

		w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
		delete w;

		ClipSideByTree_r( front, side, node->children[0] );
		ClipSideByTree_r( back, side, node->children[1] );

		return;
	}

	// if opaque leaf, don't add
	if ( !node->opaque ) {
		if ( !side->visibleHull ) {
			side->visibleHull = w->Copy();
		}
		else {
			side->visibleHull->AddToConvexHull( w, dmapGlobals.mapPlanes[ side->planenum ].Normal() );
		}
	}

	delete w;
	return;
}


/*
=====================
ClipSidesByTree

Creates side->visibleHull for all visible sides

The visible hull for a side will consist of the convex hull of
all points in non-opaque clusters, which allows overlaps
to be trimmed off automatically.
=====================
*/
void ClipSidesByTree( uEntity_t *e ) {
	uBrush_t		*b;
	int				i;
	idWinding		*w;
	side_t			*side;
	primitive_t		*prim;

	TRACE_CPU_SCOPE_TEXT("ClipSidesByTree", e->nameEntity)
	PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "----- ClipSidesByTree -----\n");

	for ( prim = e->primitives ; prim ; prim = prim->next ) {
		b = prim->brush;
		if ( !b ) {
			// FIXME: other primitives!
			continue;
		}
		for ( i = 0 ; i < b->numsides ; i++ ) {
			side = &b->sides[i];
			if ( !side->winding) {
				continue;
			}
			w = side->winding->Copy();
			side->visibleHull = NULL;
			ClipSideByTree_r( w, side, e->tree->headnode );
			// for debugging, we can choose to use the entire original side
			// but we skip this if the side was completely clipped away
			if ( side->visibleHull && dmapGlobals.noClipSides ) {
				delete side->visibleHull;
				side->visibleHull = side->winding->Copy();
			}
		}
	}
}



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

/*
====================
ClipTriIntoTree_r

This is used for adding curve triangles
The winding will be freed before it returns
====================
*/
void ClipTriIntoTree_r( idWinding *w, mapTri_t *originalTri, uEntity_t *e, node_t *node ) {
	idWinding		*front, *back;

	if ( !w ) {
		return;
	}

	if ( node->planenum != PLANENUM_LEAF ) {
		w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
		delete w;

		ClipTriIntoTree_r( front, originalTri, e, node->children[0] );
		ClipTriIntoTree_r( back, originalTri, e, node->children[1] );

		return;
	}

	// if opaque leaf, don't add
	if ( !node->opaque && node->area >= 0 ) {
		mapTri_t	*list;
		int			planeNum;
		idPlane		plane;
		textureVectors_t	texVec;

		list = WindingToTriList( w, originalTri );

		PlaneForTri( originalTri, plane );
		planeNum = FindFloatPlane( plane );

		TexVecForTri( &texVec, originalTri );

		AddTriListToArea( e, list, planeNum, node->area, &texVec );
	}

	delete w;
	return;
}



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

/*
====================
CheckWindingInAreas_r

Returns the area number that the winding is in, or
-2 if it crosses multiple areas.

====================
*/
static int CheckWindingInAreas_r( const idWinding *w, node_t *node ) {
	idWinding		*front, *back;

	if ( !w ) {
		return -1;
	}

	if ( node->planenum != PLANENUM_LEAF ) {
		int		a1, a2;
#if 0
		if ( side->planenum == node->planenum ) {
			return CheckWindingInAreas_r( w, node->children[0] );
		}
		if ( side->planenum == ( node->planenum ^ 1) ) {
			return CheckWindingInAreas_r( w, node->children[1] );
		}
#endif
		w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );

		a1 = CheckWindingInAreas_r( front, node->children[0] );
		delete front;
		a2 = CheckWindingInAreas_r( back, node->children[1] );
		delete back;

		if ( a1 == -2 || a2 == -2 ) {
			return -2;	// different
		}
		if ( a1 == -1 ) {
			return a2;	// one solid
		}
		if ( a2 == -1 ) {
			return a1;	// one solid
		}

		if ( a1 != a2 ) {
			return -2;	// cross areas
		}
		return a1;
	}

	return node->area;
}



/*
====================
PutWindingIntoAreas_r

Clips a winding down into the bsp tree, then converts
the fragments to triangles and adds them to the area lists
====================
*/
static void PutWindingIntoAreas_r( uEntity_t *e, const idWinding *w, side_t *side, node_t *node ) {
	idWinding		*front, *back;
	int				area;

	if ( !w ) {
		return;
	}

	if ( node->planenum != PLANENUM_LEAF ) {
		if ( side->planenum == node->planenum ) {
			PutWindingIntoAreas_r( e, w, side, node->children[0] );
			return;
		}
		if ( side->planenum == ( node->planenum ^ 1) ) {
			PutWindingIntoAreas_r( e, w, side, node->children[1] );
			return;
		}

		// see if we need to split it
		// adding the "noFragment" flag to big surfaces like sky boxes
		// will avoid potentially dicing them up into tons of triangles
		// that take forever to optimize back together
		if ( !dmapGlobals.fullCarve || side->material->NoFragment() ) {
			area = CheckWindingInAreas_r( w, node );
			if ( area >= 0 ) {
				mapTri_t	*tri;

				// put in single area
				tri = TriListForSide( side, w );
				AddTriListToArea( e, tri, side->planenum, area, &side->texVec );
				return;
			}
		}

		w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );

		PutWindingIntoAreas_r( e, front, side, node->children[0] );
		if ( front ) {
			delete front;
		}

		PutWindingIntoAreas_r( e, back, side, node->children[1] );
		if ( back ) {
			delete back;
		}

		return;
	}

	// if opaque leaf, don't add
	if ( node->area >= 0 && !node->opaque ) {
		mapTri_t	*tri;

		tri = TriListForSide( side, w );
		AddTriListToArea( e, tri, side->planenum, node->area, &side->texVec );
	}
}

/*
==================
AddMapTriToAreas

Used for curves and inlined models
==================
*/
void AddMapTriToAreas( mapTri_t *tri, uEntity_t *e ) {
	int				area;
	idWinding		*w;

	// skip degenerate triangles from pinched curves
	if ( MapTriArea( tri ) <= 0 ) {
		return;
	}

	if ( dmapGlobals.fullCarve ) {
		// always fragment into areas
		w = WindingForTri( tri );
		ClipTriIntoTree_r( w, tri, e, e->tree->headnode );
		return;
	}

	w = WindingForTri( tri );
	area = CheckWindingInAreas_r( w, e->tree->headnode );
	delete w;
	if ( area == -1 ) {
		return;
	}
	if ( area >= 0 ) {
		mapTri_t	*newTri;
		idPlane		plane;
		int			planeNum;
		textureVectors_t	texVec;

		// put in single area
		newTri = CopyMapTri( tri );
		newTri->next = NULL;

		PlaneForTri( tri, plane );
		planeNum = FindFloatPlane( plane );

		TexVecForTri( &texVec, newTri );

		AddTriListToArea( e, newTri, planeNum, area, &texVec );
	} else {
		// fragment into areas
		w = WindingForTri( tri );
		ClipTriIntoTree_r( w, tri, e, e->tree->headnode );
	}
}

/*
=====================
PutPrimitivesInAreas

=====================
*/
void PutPrimitivesInAreas( uEntity_t *e ) {
	uBrush_t		*b;
	int				i;
	side_t			*side;
	primitive_t		*prim;
	mapTri_t		*tri;

	TRACE_CPU_SCOPE_TEXT("PutPrimitivesInAreas", e->nameEntity)
	PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "----- PutPrimitivesInAreas -----\n");

	// allocate space for surface chains for each area
	e->areas = (uArea_t *)Mem_Alloc( e->numAreas * sizeof( e->areas[0] ) );
	memset( e->areas, 0, e->numAreas * sizeof( e->areas[0] ) );

	if (dmap_fasterPutPrimitives.GetBool()) {
		//stgatilov: prepare auxilliary search structures for optimize groups
		int avgPrimCount = e->mapEntity->GetNumPrimitives() / e->numAreas;
		int capacity = idMath::Imax(16, idMath::CeilPowerOfTwo(avgPrimCount));
		for (int i = 0; i < e->numAreas; i++) {
			e->areas[i].groupsPerPlane = new groupsPerPlane_s();
			groupsPerPlane_s &gpp = *e->areas[i].groupsPerPlane;
			gpp.hash.ClearFree(capacity, capacity);
			gpp.lists.Clear();
			gpp.lists.Reserve(capacity);
		}
	}

	// for each primitive, clip it to the non-solid leafs
	// and divide it into different areas
	for ( prim = e->primitives ; prim ; prim = prim->next ) {
		b = prim->brush;

		if ( !b ) {
			TRACE_CPU_SCOPE_TEXT("PutPrimitiveInArea", "patch")
			// add curve triangles
			for ( tri = prim->tris ; tri ; tri = tri->next ) {
				AddMapTriToAreas( tri, e );
			}
			continue;
		}
		TRACE_CPU_SCOPE_FORMAT("PutPrimitiveInArea", "Ent%d Br%d", prim->brush->entitynum, prim->brush->brushnum)

		// clip in brush sides
		for ( i = 0 ; i < b->numsides ; i++ ) {
			side = &b->sides[i];
			if ( !side->visibleHull ) {
				continue;
			}
			PutWindingIntoAreas_r( e, side->visibleHull, side, e->tree->headnode );
		}
	}


	// optionally inline some of the func_static models
	if ( dmapGlobals.entityNum == 0 ) {
		bool inlineAll = dmapGlobals.uEntities[0].mapEntity->epairs.GetBool( "inlineAllStatics" );

		for ( int eNum = 1 ; eNum < dmapGlobals.num_entities ; eNum++ ) {
			uEntity_t *entity = &dmapGlobals.uEntities[eNum];
			const char *className = entity->mapEntity->epairs.GetString( "classname" );
			if ( idStr::Icmp( className, "func_static" ) ) {
				continue;
			}
			if ( !entity->mapEntity->epairs.GetBool( "inline" ) && !inlineAll ) {
				continue;
			}
			const char *modelName = entity->mapEntity->epairs.GetString( "model" );
			if ( !modelName ) {
				continue;
			}
			idRenderModel	*model = renderModelManager->FindModel( modelName );

			common->Printf( "inlining %s.\n", entity->mapEntity->epairs.GetString( "name" ) );

			idMat3	axis;
			gameEdit->ParseSpawnArgsToAxis( &entity->mapEntity->epairs, axis );
			idVec3	origin = entity->mapEntity->epairs.GetVector( "origin" );

			for ( i = 0 ; i < model->NumSurfaces() ; i++ ) {
				const modelSurface_t *surface = model->Surface( i );
				const srfTriangles_t *tri = surface->geometry;

				mapTri_t	mapTri;
				memset( &mapTri, 0, sizeof( mapTri ) );
				mapTri.material = surface->material;
				// don't let discretes (autosprites, etc) merge together
				if ( mapTri.material->IsDiscrete() ) {
					mapTri.mergeGroup = (void *)surface;
				}
				for ( int j = 0 ; j < tri->numIndexes ; j += 3 ) {
					for ( int k = 0 ; k < 3 ; k++ ) {
						idVec3 v = tri->verts[tri->indexes[j+k]].xyz;

						mapTri.v[k].xyz = v * axis + origin;

						mapTri.v[k].normal = tri->verts[tri->indexes[j+k]].normal * axis;
						mapTri.v[k].st = tri->verts[tri->indexes[j+k]].st;
					}
					AddMapTriToAreas( &mapTri, e );
				}
			}
		}
	}

	if (dmap_fasterPutPrimitives.GetBool()) {
		//stgatilov: merge lists of optimize groups back and shutdown auxilliary data structures
		for (int i = 0; i < e->numAreas; i++) {
			uArea_t *area = &e->areas[i];
			groupsPerPlane_s &gpp = *area->groupsPerPlane;
			//merge per-plane lists into one long list
			optimizeGroup_t* &mergedList = area->groups;
			assert(mergedList == nullptr);
			for (int j = 0; j < gpp.lists.Num(); j++) {
				optimizeGroup_t *group = gpp.lists[j];
				assert(group);
				optimizeGroup_t *end = group;
				while (end->nextGroup)
					end = end->nextGroup;
				end->nextGroup = mergedList;
				mergedList = group;
			}
			//delete auxilliary data structures
			delete area->groupsPerPlane;
			area->groupsPerPlane = nullptr;
		}
	}
}

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

/*
=================
ClipTriByLight

Carves a triangle by the frustom planes of a light, producing
a (possibly empty) list of triangles on the inside and outside.

The original triangle is not modified.

If no clipping is required, the result will be a copy of the original.

If clipping was required, the outside fragments will be planar clips, which
will benefit from re-optimization.
=================
*/
static void ClipTriByLight( const mapLight_t *light, const mapTri_t *tri, 
						   mapTri_t **in, mapTri_t **out ) {
	idWinding	*inside, *oldInside;
	idWinding	*outside[6];
	bool	hasOutside;
	int			i;

	*in = NULL;
	*out = NULL;

	// clip this winding to the light
	inside = WindingForTri( tri );
	hasOutside = false;
	for ( i = 0 ; i < 6 ; i++ ) {
		oldInside = inside;
		if ( oldInside ) {
			oldInside->Split( light->def.frustum[i], 0, &outside[i], &inside );
			delete oldInside;
		}
		else {
			outside[i] = NULL;
		}
		if ( outside[i] ) {
			hasOutside = true;
		}
	}

	if ( !inside ) {
		// the entire winding is outside this light

		// free the clipped fragments
		for ( i = 0 ; i < 6 ; i++ ) {
			if ( outside[i] ) {
				delete outside[i];
			}
		}

		*out = CopyMapTri( tri );
		(*out)->next = NULL;

		return;
	}

	if ( !hasOutside ) {
		// the entire winding is inside this light

		// free the inside copy
		delete inside;

		*in = CopyMapTri( tri );
		(*in)->next = NULL;

		return;
	}

	// the winding is split
	*in = WindingToTriList( inside, tri );
	delete inside;

	// combine all the outside fragments
	for ( i = 0 ; i < 6 ; i++ ) {
		if ( outside[i] ) {
			mapTri_t	*list;

			list = WindingToTriList( outside[i], tri );
			delete outside[i];
			*out = MergeTriLists( *out, list );
		}
	}
}

/*
=================
BoundOptimizeGroup
=================
*/
static void BoundOptimizeGroup( optimizeGroup_t *group ) {
	group->bounds.Clear();
	for ( mapTri_t *tri = group->triList ; tri ; tri = tri->next ) {
		group->bounds.AddPoint( tri->v[0].xyz );
		group->bounds.AddPoint( tri->v[1].xyz );
		group->bounds.AddPoint( tri->v[2].xyz );
	}
}

/*
====================
BuildLightShadows

Build the beam tree and shadow volume surface for a light
====================
*/
static void BuildLightShadows( uEntity_t *e, mapLight_t *light ) {
	int			i;
	optimizeGroup_t	*group;
	mapTri_t	*tri;
	mapTri_t	*shadowers;
	optimizeGroup_t		*shadowerGroups;
	idVec3		lightOrigin;
	bool		hasPerforatedSurface = false;

	//
	// build a group list of all the triangles that will contribute to
	// the optimized shadow volume, leaving the original triangles alone
	//


	// shadowers will contain all the triangles that will contribute to the
	// shadow volume
	shadowerGroups = NULL;
	lightOrigin = light->def.globalLightOrigin;

	// if the light is no-shadows, don't add any surfaces
	// to the beam tree at all
	if ( !light->def.parms.noShadows && light->def.lightShader->LightCastsShadows() ) {
		for ( i = 0 ; i < e->numAreas ; i++ ) {
			for ( group = e->areas[i].groups ; group ; group = group->nextGroup ) {
				// if the surface doesn't cast shadows, skip it
				if ( !group->material->SurfaceCastsShadow() ) {
					continue;
				}

				// if the group doesn't face away from the light, it
				// won't contribute to the shadow volume
				if ( dmapGlobals.mapPlanes[ group->planeNum ].Distance( lightOrigin ) > 0 ) {
					continue;
				}

				// if the group bounds doesn't intersect the light bounds,
				// skip it
				if ( !group->bounds.IntersectsBounds( light->def.frustumTris->bounds ) ) {
					continue;
				}

				// build up a list of the triangle fragments inside the
				// light frustum
				shadowers = NULL;
				for ( tri = group->triList ; tri ; tri = tri->next ) {
					mapTri_t	*in, *out;

					// clip it to the light frustum
					ClipTriByLight( light, tri, &in, &out );
					FreeTriList( out );
					shadowers = MergeTriLists( shadowers, in );
				}

				// if we didn't get any out of this group, we don't
				// need to create a new group in the shadower list
				if ( !shadowers ) {
					continue;
				}

				// find a group in shadowerGroups to add these to
				// we will ignore everything but planenum, and we
				// can merge across areas
				optimizeGroup_t	*check;

				for ( check = shadowerGroups ; check ; check = check->nextGroup ) {
					if ( check->planeNum == group->planeNum ) {
						break;
					}
				}
				if ( !check ) {
					check = (optimizeGroup_t *)Mem_Alloc( sizeof( *check ) );
					*check = *group;
					check->triList = NULL;
					check->nextGroup = shadowerGroups;
					shadowerGroups = check;
				}

				// if any surface is a shadow-casting perforated or translucent surface, we
				// can't use the face removal optimizations because we can see through
				// some of the faces
				if ( group->material->Coverage() != MC_OPAQUE ) {
					hasPerforatedSurface = true;
				}

				check->triList = MergeTriLists( check->triList, shadowers );
			}
		}
	}

	// take the shadower group list and create a beam tree and shadow volume
	light->shadowTris = CreateLightShadow( shadowerGroups, light );

	if ( light->shadowTris && hasPerforatedSurface ) {
		// can't ever remove front faces, because we can see through some of them
		light->shadowTris->numShadowIndexesNoCaps = light->shadowTris->numShadowIndexesNoFrontCaps = 
			light->shadowTris->numIndexes;
	}

	// we don't need the original shadower triangles for anything else
	FreeOptimizeGroupList( shadowerGroups );
}


/*
====================
CarveGroupsByLight

Divide each group into an inside group and an outside group, based
on which fragments are illuminated by the light's beam tree
====================
*/
static void CarveGroupsByLight( uEntity_t *e, mapLight_t *light ) {
	int			i;
	optimizeGroup_t	*group, *newGroup, *carvedGroups, *nextGroup;
	mapTri_t	*tri, *inside, *outside;
	uArea_t		*area;

	for ( i = 0 ; i < e->numAreas ; i++ ) {
		area = &e->areas[i];
		carvedGroups = NULL;

		// we will be either freeing or reassigning the groups as we go
		for ( group = area->groups ; group ; group = nextGroup ) {
			nextGroup = group->nextGroup;
			// if the surface doesn't get lit, don't carve it up
			if ( ( light->def.lightShader->IsFogLight() && !group->material->ReceivesFog() )
				|| ( !light->def.lightShader->IsFogLight() && !group->material->ReceivesLighting() ) 
				|| !group->bounds.IntersectsBounds( light->def.frustumTris->bounds ) ) {

				group->nextGroup = carvedGroups;
				carvedGroups = group;
				continue;
			}

			if ( group->numGroupLights == MAX_GROUP_LIGHTS ) {
				common->Error( "MAX_GROUP_LIGHTS around %f %f %f",
					 group->triList->v[0].xyz[0], group->triList->v[0].xyz[1], group->triList->v[0].xyz[2] );
			}

			// if the group doesn't face the light,
			// it won't get carved at all
			if ( !light->def.lightShader->LightEffectsBackSides() &&
				!group->material->ReceivesLightingOnBackSides() &&
				dmapGlobals.mapPlanes[ group->planeNum ].Distance( light->def.parms.origin ) <= 0  ) {

				group->nextGroup = carvedGroups;
				carvedGroups = group;
				continue;
			}

			// split into lists for hit-by-light, and not-hit-by-light
			inside = NULL;
			outside = NULL;

			for ( tri = group->triList ; tri ; tri = tri->next ) {
				mapTri_t	*in, *out;

				ClipTriByLight( light, tri, &in, &out );
				inside = MergeTriLists( inside, in );
				outside = MergeTriLists( outside, out );
			}

			if ( inside ) {
				newGroup = (optimizeGroup_t *)Mem_Alloc( sizeof( *newGroup ) );
				*newGroup = *group;
				newGroup->groupLights[newGroup->numGroupLights] = light;
				newGroup->numGroupLights++;
				newGroup->triList = inside;
				newGroup->nextGroup = carvedGroups;
				carvedGroups = newGroup;
			}

			if ( outside ) {
				newGroup = (optimizeGroup_t *)Mem_Alloc( sizeof( *newGroup ) );
				*newGroup = *group;
				newGroup->triList = outside;
				newGroup->nextGroup = carvedGroups;
				carvedGroups = newGroup;
			}

			// free the original
			group->nextGroup = NULL;
			FreeOptimizeGroupList( group );
		}

		// replace this area's group list with the new one
		area->groups = carvedGroups;
	}
}

/*
=====================
Prelight

Break optimize groups up into additional groups at light boundaries, so
optimization won't cross light bounds
=====================
*/
void Prelight( uEntity_t *e ) {
	int			i;
	int			start, end;
	mapLight_t	*light;

	// don't prelight anything but the world entity
	if ( dmapGlobals.entityNum != 0 ) {
		return;
	}
	TRACE_CPU_SCOPE("Prelight")
	
	if ( dmapGlobals.shadowOptLevel > 0 ) {
		TRACE_CPU_SCOPE("BuildLightShadows")
		PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "----- BuildLightShadows -----\n" );
		start = Sys_Milliseconds();

		// calc bounds for all the groups to speed things up
		for ( i = 0 ; i < e->numAreas ; i++ ) {
			uArea_t *area = &e->areas[i];

			for ( optimizeGroup_t *group = area->groups ; group ; group = group->nextGroup ) {
				BoundOptimizeGroup( group );
			}
		}

		for ( i = 0 ; i < dmapGlobals.mapLights.Num() ; i++ ) {
			light = dmapGlobals.mapLights[i];
			BuildLightShadows( e, light );
		}

		end = Sys_Milliseconds();
		PrintIfVerbosityAtLeast( VL_CONCISE, "%5.1f seconds for BuildLightShadows\n", ( end - start ) / 1000.0 );
	}


	if ( !dmapGlobals.noLightCarve ) {
		TRACE_CPU_SCOPE("CarveGroupsByLight")
		PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "----- CarveGroupsByLight -----\n" );
		start = Sys_Milliseconds();
		// now subdivide the optimize groups into additional groups for
		// each light that illuminates them
		for ( i = 0 ; i < dmapGlobals.mapLights.Num() ; i++ ) {
			light = dmapGlobals.mapLights[i];
			CarveGroupsByLight( e, light );
		}

		end = Sys_Milliseconds();
		PrintIfVerbosityAtLeast( VL_CONCISE, "%5.1f seconds for CarveGroupsByLight\n", ( end - start ) / 1000.0 );
	}

}