//===========================================================================
// Returns a single brush made up by the intersection of the
// two provided brushes, or NULL if they are disjoint.
//
// The originals are undisturbed.
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bspbrush_t *IntersectBrush( bspbrush_t *a, bspbrush_t *b ) {
	int i;
	bspbrush_t  *front, *back;
	bspbrush_t  *in;

	in = a;
	for ( i = 0 ; i < b->numsides && in ; i++ )
	{
		SplitBrush( in, b->sides[i].planenum, &front, &back );
//		SplitBrush2(in, b->sides[i].planenum, &front, &back);
		if ( in != a ) {
			FreeBrush( in );
		}
		if ( front ) {
			FreeBrush( front );
		}
		in = back;
	} //end for

	if ( in == a ) {
		return NULL;
	}

	in->next = NULL;
	return in;
} //end of the function IntersectBrush

//===========================================================================
// Returns a list of brushes that remain after B is subtracted from A.
// May by empty if A is contained inside B.
// The originals are undisturbed.
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b)
{	// a - b = out (list)
	int		i;
	bspbrush_t	*front, *back;
	bspbrush_t	*out, *in;

	in = a;
	out = NULL;
	for (i = 0; i < b->numsides && in; i++)
	{
		SplitBrush2(in, b->sides[i].planenum, &front, &back);
		if (in != a) FreeBrush(in);
		if (front)
		{	// add to list
			front->next = out;
			out = front;
		} //end if
		in = back;
	} //end for
	if (in)
	{
		FreeBrush (in);
	} //end if
	else
	{	// didn't really intersect
		FreeBrushList (out);
		return a;
	} //end else
	return out;
} //end of the function SubtractBrush

/*
================
FreeDMapFile
================
*/
void FreeDMapFile( void )
{
    int		i, j;

    FreeBrush( buildBrush );
    buildBrush = NULL;

    // free the entities and brushes
    for( i = 0; i < dmapGlobals.num_entities; i++ )
    {
        uEntity_t	*ent;
        primitive_t	*prim, *nextPrim;

        ent = &dmapGlobals.uEntities[i];

        FreeTree( ent->tree );

        // free primitives
        for( prim = ent->primitives; prim; prim = nextPrim )
        {
            nextPrim = prim->next;

            if( prim->brush )
            {
                FreeBrush( prim->brush );
            }

            if( prim->tris )
            {
                FreeTriList( prim->tris );
            }
            Mem_Free( prim );
        }

        // free area surfaces
        if( ent->areas )
        {
            for( j = 0; j < ent->numAreas; j++ )
            {
                uArea_t	*area;

                area = &ent->areas[j];
                FreeOptimizeGroupList( area->groups );

            }
            Mem_Free( ent->areas );
        }
    }
    Mem_Free( dmapGlobals.uEntities );

    dmapGlobals.num_entities = 0;

    // free the map lights
    for( i = 0; i < dmapGlobals.mapLights.Num(); i++ )
    {
        R_FreeLightDefDerivedData( &dmapGlobals.mapLights[i]->def );
    }
    dmapGlobals.mapLights.DeleteContents( true );
}

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bspbrush_t *MergeBrushes(bspbrush_t *brushlist)
{
	int nummerges, merged;
	bspbrush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
	bspbrush_t *lastb2;

	if (!brushlist) return NULL;

	qprintf("%5d brushes merged", nummerges = 0);
	do
	{
		for (tail = brushlist; tail; tail = tail->next)
		{
			if (!tail->next) break;
		} //end for
		merged = 0;
		newbrushlist = NULL;
		for (b1 = brushlist; b1; b1 = brushlist)
		{
			lastb2 = b1;
			for (b2 = b1->next; b2; b2 = b2->next)
			{
				//if the brushes don't have the same contents
				if (b1->original->contents != b2->original->contents ||
					b1->original->expansionbbox != b2->original->expansionbbox) newbrush = NULL;
				else newbrush = TryMergeBrushes(b1, b2);
				if (newbrush)
				{
					tail->next = newbrush;
					lastb2->next = b2->next;
					brushlist = brushlist->next;
					FreeBrush(b1);
					FreeBrush(b2);
					for (tail = brushlist; tail; tail = tail->next)
					{
						if (!tail->next) break;
					} //end for
					merged++;
					qprintf("\r%5d", nummerges++);
					break;
				} //end if
				lastb2 = b2;
			} //end for
			//if b1 can't be merged with any of the other brushes
			if (!b2)
			{
				brushlist = brushlist->next;
				//keep b1
				b1->next = newbrushlist;
				newbrushlist = b1;
			} //end else
		} //end for
		brushlist = newbrushlist;
	} while(merged);
	qprintf("\n");
	return newbrushlist;
} //end of the function MergeBrushes

/*
============
PruneNodes_r
============
*/
void PruneNodes_r (node_t *node)
{
	bspbrush_t		*b, *next;
//	portal_t	*p, *nextp;
//	int			s;

	if (node->planenum == PLANENUM_LEAF)
		return;
	PruneNodes_r (node->children[0]);
	PruneNodes_r (node->children[1]);

	if ( (node->children[0]->contents & CONTENTS_SOLID)
	&& (node->children[1]->contents & CONTENTS_SOLID) )
	{
		if (node->faces)
			Error ("node->faces seperating CONTENTS_SOLID");
		if (node->children[0]->faces || node->children[1]->faces)
			Error ("!node->faces with children");

		// FIXME: free stuff

		node->pruned = true;
		node->planenum = PLANENUM_LEAF;
		node->contents = CONTENTS_SOLID;
		node->detail_seperator = false;

		if (node->brushlist)
			Error ("PruneNodes: node->brushlist");

		// combine brush lists
		node->brushlist = node->children[1]->brushlist;

		for (b=node->children[0]->brushlist ; b ; b=next)
		{
			next = b->next;
			b->next = node->brushlist;
			node->brushlist = b;
		}

		node->children[0]->brushlist = NULL;
		node->children[1]->brushlist = NULL;

		if(node->children[0]->volume != NULL)
		{
			FreeBrush(node->children[0]->volume);
			node->children[0]->volume = NULL;
		}

		if(node->children[1]->volume != NULL)
		{
			FreeBrush(node->children[1]->volume);
			node->children[1]->volume = NULL;
		}

		c_pruned++;
	}
}

//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void Tree_Free_r( node_t *node ) {
//	face_t *f, *nextf;
	bspbrush_t *brush, *nextbrush;

	//free children
	if ( node->planenum != PLANENUM_LEAF ) {
		Tree_Free_r( node->children[0] );
		Tree_Free_r( node->children[1] );
	} //end if
	  //free bspbrushes
//	FreeBrushList (node->brushlist);
	for ( brush = node->brushlist; brush; brush = nextbrush )
	{
		nextbrush = brush->next;
#ifdef ME
		freedtreemem += MemorySize( brush );
#endif //ME
		FreeBrush( brush );
	} //end for
	node->brushlist = NULL;

	/*
	NOTE: only used when creating Q2 bsp
	// free faces
	for (f = node->faces; f; f = nextf)
	{
		nextf = f->next;
#ifdef ME
		if (f->w) freedtreemem += MemorySize(f->w);
		freedtreemem += sizeof(face_t);
#endif //ME
		FreeFace(f);
	} //end for
	*/

	// free the node
	if ( node->volume ) {
#ifdef ME
		freedtreemem += MemorySize( node->volume );
#endif //ME
		FreeBrush( node->volume );
	} //end if

	if ( numthreads == 1 ) {
		c_nodes--;
	}
#ifdef ME
	freedtreemem += MemorySize( node );
#endif //ME
	FreeMemory( node );
} //end of the function Tree_Free_r

//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
qboolean CheckPlaneAgainstVolume (int pnum, node_t *node)
{
	bspbrush_t	*front, *back;
	qboolean	good;

	SplitBrush (node->volume, pnum, &front, &back);

	good = (front && back);

	if (front) FreeBrush (front);
	if (back) FreeBrush (back);

	return good;
} //end of the function CheckPlaneAgaintsVolume

/*
====================
FilterBrushIntoTree_r

====================
*/
int FilterBrushIntoTree_r( uBrush_t *b, node_t *node )
{
	uBrush_t		*front, *back;
	int				c;
	
	if( !b )
	{
		return 0;
	}
	
	// add it to the leaf list
	if( node->planenum == PLANENUM_LEAF )
	{
		b->next = node->brushlist;
		node->brushlist = b;
		
		// classify the leaf by the structural brush
		if( b->opaque )
		{
			node->opaque = true;
		}
		return 1;
	}
	
	// split it by the node plane
	SplitBrush( b, node->planenum, &front, &back );
	FreeBrush( b );
	
	c = 0;
	c += FilterBrushIntoTree_r( front, node->children[0] );
	c += FilterBrushIntoTree_r( back, node->children[1] );
	
	return c;
}

static bool CheckPlaneAgainstVolume (uint16_t pnum, const bspbrush_t* volume)
{
		bspbrush_t* front, *back;
		bool good;

		SplitBrush(volume, pnum, &front, &back);

		good = (front && back);

		if (front)
				FreeBrush(front);
		if (back)
				FreeBrush(back);

		return good;
}

/*
   =============
   FreeTree_r
   =============
 */
void FreeTree_r( node_t *node ){
	face_t      *f, *nextf;

	// free children
	if ( node->planenum != PLANENUM_LEAF ) {
		FreeTree_r( node->children[0] );
		FreeTree_r( node->children[1] );
	}

	// free bspbrushes
	FreeBrushList( node->brushlist );

	// free faces
	for ( f = node->faces ; f ; f = nextf )
	{
		nextf = f->next;
		FreeFace( f );
	}

	// free the node
	if ( node->volume ) {
		FreeBrush( node->volume );
	}

	if ( numthreads == 1 ) {
		c_nodes--;
	}
	free( node );
}

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void Q1_CreateMapBrushes(entity_t *mapent, int modelnum)
{
    bspbrush_t *brushlist, *brush, *nextbrush;
    int i;

    //create brushes from the model BSP tree
    brushlist = Q1_CreateBrushesFromBSP(modelnum);
    //texture the brushes and split them when necesary
    brushlist = Q1_TextureBrushes(brushlist, modelnum);
    //fix the contents textures of all brushes
    Q1_FixContentsTextures(brushlist);
    //
    if (!nobrushmerge)
    {
        brushlist = Q1_MergeBrushes(brushlist, modelnum);
        //brushlist = Q1_MergeBrushes(brushlist, modelnum);
    } //end if
    //
    if (!modelnum) qprintf("converting brushes to map brushes\n");
    if (!modelnum) qprintf("%5d brushes", i = 0);
    for (brush = brushlist; brush; brush = nextbrush)
    {
        nextbrush = brush->next;
        Q1_BSPBrushToMapBrush(brush, mapent);
        brush->next = NULL;
        FreeBrush(brush);
        if (!modelnum) qprintf("\r%5d", ++i);
    } //end for
    if (!modelnum) qprintf("\n");
} //end of the function Q1_CreateMapBrushes

static void FreeTree_r (node_t *node)
{
	face_t *f, *nextf;

	/* free children */
	if (node->planenum != PLANENUM_LEAF) {
		FreeTree_r(node->children[0]);
		FreeTree_r(node->children[1]);
	}

	/* free bspbrushes */
	FreeBrushList(node->brushlist);

	/* free faces */
	for (f = node->faces; f; f = nextf) {
		nextf = f->next;
		FreeFace(f);
	}

	/* free the node */
	if (node->volume)
		FreeBrush(node->volume);

	if (threadstate.numthreads == 1)
		c_nodes--;
	Mem_Free(node);
}

/**
 * @sa AllocBrush
 * @sa CountBrushList
 */
void FreeBrushList (bspbrush_t* brushes)
{
	bspbrush_t* next;

	for (; brushes; brushes = next) {
		next = brushes->next;
		FreeBrush(brushes);
	}
}

/*
================
FreeBrushList
================
*/
void FreeBrushList( uBrush_t *brushes )
{
	uBrush_t	*next;
	
	for( /**/; brushes; brushes = next )
	{
		next = brushes->next;
		FreeBrush( brushes );
	}
}

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void FreeBrushList( bspbrush_t *brushes ) {
	bspbrush_t  *next;

	for ( ; brushes; brushes = next )
	{
		next = brushes->next;

		FreeBrush( brushes );
	} //end for
} //end of the function FreeBrushList

//===========================================================================
// Any planes shared with the box edge will be set to no texinfo
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bspbrush_t *ClipBrushToBox(bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs)
{
	int		i, j;
	bspbrush_t	*front,	*back;
	int		p;

	for (j=0 ; j<2 ; j++)
	{
		if (brush->maxs[j] > clipmaxs[j])
		{
			SplitBrush (brush, maxplanenums[j], &front, &back);
			if (front)
				FreeBrush (front);
			brush = back;
			if (!brush)
				return NULL;
		}
		if (brush->mins[j] < clipmins[j])
		{
			SplitBrush (brush, minplanenums[j], &front, &back);
			if (back)
				FreeBrush (back);
			brush = front;
			if (!brush)
				return NULL;
		}
	}

	// remove any colinear faces

	for (i=0 ; i<brush->numsides ; i++)
	{
		p = brush->sides[i].planenum & ~1;
		if (p == maxplanenums[0] || p == maxplanenums[1] 
			|| p == minplanenums[0] || p == minplanenums[1])
		{
			brush->sides[i].texinfo = TEXINFO_NODE;
			brush->sides[i].flags &= ~SFL_VISIBLE;
		}
	}
	return brush;
} //end of the function ClipBrushToBox

/*
=====================
FreeBrushsetBrushes
=====================
*/
void FreeBrushsetBrushes(void)
{
	brush_t *pBrush, *pNext;

	for (pBrush = brushset->brushes; pBrush; pBrush = pNext)
	{
		pNext = pBrush->next;
		FreeBrushFaces(pBrush->faces);
		FreeBrush(pBrush);
	}
}

void FreeBrushList( brush_t *brushes ){
	brush_t     *next;


	/* walk brush list */
	for ( ; brushes != NULL; brushes = next )
	{
		next = brushes->next;
		FreeBrush( brushes );
	}
}

/*
  ====================
  FreeBrushList

  ====================
*/
void FreeBrushList( cbspbrush_t *list )
{
	cbspbrush_t	*next;

	if ( !list )
		return;

	for ( ; list ;list = next )
	{
		next = list->next;
		FreeBrush( list );
	}
}

/*
====================
FilterBrushIntoTree_r
====================
*/
int FilterBrushIntoTree_r(bspBrush_t * b, node_t * node)
{
	bspBrush_t     *front, *back;
	int             c;

	if(!b)
	{
		return 0;
	}

	// add it to the leaf list
	if(node->planenum == PLANENUM_LEAF)
	{
		b->next = node->brushlist;
		node->brushlist = b;

		// classify the leaf by the structural brush
		if(!b->detail)
		{
			if(b->opaque)
			{
				node->opaque = qtrue;
				node->areaportal = qfalse;
			}
			else if(b->contents & CONTENTS_AREAPORTAL)
			{
				if(!node->opaque)
				{
					node->areaportal = qtrue;
				}
			}
		}

		return 1;
	}

	// split it by the node plane
	SplitBrush(b, node->planenum, &front, &back);
	FreeBrush(b);

	c = 0;
	c += FilterBrushIntoTree_r(front, node->children[0]);
	c += FilterBrushIntoTree_r(back, node->children[1]);

	return c;
}