/*****************************************************************************
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 "AASBuild_local.h"

#define LEDGE_EPSILON		0.1f

//===============================================================
//
//	idLedge
//
//===============================================================

/*
============
idLedge::idLedge
============
*/
idLedge::idLedge( void ) {
}

/*
============
idLedge::idLedge
============
*/
idLedge::idLedge( const idVec3 &v1, const idVec3 &v2, const idVec3 &gravityDir, idBrushBSPNode *n ) {
	start = v1;
	end = v2;
	node = n;
	numPlanes = 4;
	planes[0].SetNormal( (v1 - v2).Cross( gravityDir ) );
	planes[0].Normalize();
	planes[0].FitThroughPoint( v1 );
	planes[1].SetNormal( (v1 - v2).Cross( planes[0].Normal() ) );
	planes[1].Normalize();
	planes[1].FitThroughPoint( v1 );
	planes[2].SetNormal( v1 - v2 );
	planes[2].Normalize();
	planes[2].FitThroughPoint( v1 );
	planes[3].SetNormal( v2 - v1 );
	planes[3].Normalize();
	planes[3].FitThroughPoint( v2 );
	numExpandedPlanes = numSplitPlanes = 0; // DG: make sure those are initialized
}

/*
============
idLedge::AddPoint
============
*/
void idLedge::AddPoint( const idVec3 &v ) {
	if ( planes[2].Distance( v ) > 0.0f ) {
		start = v;
		planes[2].FitThroughPoint( start );
	}
	if ( planes[3].Distance( v ) > 0.0f ) {
		end = v;
		planes[3].FitThroughPoint( end );
	}
}

/*
============
idLedge::CreateBevels

  NOTE: this assumes the gravity is vertical
============
*/
void idLedge::CreateBevels( const idVec3 &gravityDir ) {
	int i, j;
	idBounds bounds;
	idVec3 size, normal;

	bounds.Clear();
	bounds.AddPoint( start );
	bounds.AddPoint( end );
	size = bounds[1] - bounds[0];

	// plane through ledge
	planes[0].SetNormal( (start - end).Cross( gravityDir ) );
	planes[0].Normalize();
	planes[0].FitThroughPoint( start );
	// axial bevels at start and end point
	i = size[1] > size[0];
	normal = vec3_origin;
	normal[i] = 1.0f;
	j = end[i] > start[i];
	planes[1+j].SetNormal( normal );
	planes[1+!j].SetNormal( -normal );
	planes[1].FitThroughPoint( start );
	planes[2].FitThroughPoint( end );
	numExpandedPlanes = 3;
	// if additional bevels are required
	if ( idMath::Fabs( size[!i] ) > 0.01f ) {
		normal = vec3_origin;
		normal[!i] = 1.0f;
		j = end[!i] > start[!i];
		planes[3+j].SetNormal( normal );
		planes[3+!j].SetNormal( -normal );
		planes[3].FitThroughPoint( start );
		planes[4].FitThroughPoint( end );
		numExpandedPlanes = 5;
	}
	// opposite of first
	planes[numExpandedPlanes+0] = -planes[0];
	// number of planes used for splitting
	numSplitPlanes = numExpandedPlanes + 1;
	// top plane
	planes[numSplitPlanes+0].SetNormal( (start - end).Cross( planes[0].Normal() ) );
	planes[numSplitPlanes+0].Normalize();
	planes[numSplitPlanes+0].FitThroughPoint( start );
	// bottom plane
	planes[numSplitPlanes+1] = -planes[numSplitPlanes+0];
	// total number of planes
	numPlanes = numSplitPlanes + 2;
}

/*
============
idLedge::Expand
============
*/
void idLedge::Expand( const idBounds &bounds, float maxStepHeight ) {
	int i, j;
	idVec3 v;

	for ( i = 0; i < numExpandedPlanes; i++ ) {

		for ( j = 0; j < 3; j++ ) {
			if ( planes[i].Normal()[j] > 0.0f ) {
				v[j] = bounds[0][j];
			}
			else {
				v[j] = bounds[1][j];
			}
		}

		planes[i].SetDist( planes[i].Dist() + v * -planes[i].Normal() );
	}

	planes[numSplitPlanes+0].SetDist( planes[numSplitPlanes+0].Dist() + maxStepHeight );
	planes[numSplitPlanes+1].SetDist( planes[numSplitPlanes+1].Dist() + 1.0f );
}

/*
============
idLedge::ChopWinding
============
*/
idWinding *idLedge::ChopWinding( const idWinding *winding ) const {
	int i;
	idWinding *w;

	w = winding->Copy();
	for ( i = 0; i < numPlanes && w; i++ ) {
		w = w->Clip( -planes[i], ON_EPSILON, true );
	}
	return w;
}

/*
============
idLedge::PointBetweenBounds
============
*/
bool idLedge::PointBetweenBounds( const idVec3 &v ) const {
	return ( planes[2].Distance( v ) < LEDGE_EPSILON ) && ( planes[3].Distance( v ) < LEDGE_EPSILON );
}


//===============================================================
//
//	idAASBuild
//
//===============================================================

/*
============
idAASBuild::LedgeSubdivFlood_r
============
*/
void idAASBuild::LedgeSubdivFlood_r( idBrushBSPNode *node, const idLedge *ledge ) {
	int s1, i;
	idBrushBSPPortal *p1;
	idWinding *w;
	idList<idBrushBSPNode *> nodeList;

	if ( node->GetFlags() & NODE_VISITED ) {
		return;
	}

	// if this is not already a ledge area
	if ( !( node->GetFlags() & AREA_LEDGE ) ) {
		for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
			s1 = (p1->GetNode(1) == node);

			if ( !(p1->GetFlags() & FACE_FLOOR) ) {
				continue;
			}

			// split the area if some part of the floor portal is inside the expanded ledge
			w = ledge->ChopWinding( p1->GetWinding() );
			if ( !w ) {
				continue;
			}
			delete w;

			for ( i = 0; i < ledge->numSplitPlanes; i++ ) {
				if ( node->PlaneSide( ledge->planes[i], 0.1f ) != SIDE_CROSS ) {
					continue;
				}
				if ( !node->Split( ledge->planes[i], -1 ) ) {
					continue;
				}
				numLedgeSubdivisions++;
				DisplayRealTimeString( "\r%6d", numLedgeSubdivisions );
				node->GetChild(0)->SetFlag( NODE_VISITED );
				LedgeSubdivFlood_r( node->GetChild(1), ledge );
				return;
			}

			node->SetFlag( AREA_LEDGE );
			break;
		}
	}

	node->SetFlag( NODE_VISITED );

	// get all nodes we might need to flood into
	for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
		s1 = (p1->GetNode(1) == node);

		if ( p1->GetNode( !s1 )->GetContents() & AREACONTENTS_SOLID ) {
			continue;
		}

		// flood through this portal if the portal is partly inside the expanded ledge
		w = ledge->ChopWinding( p1->GetWinding() );
		if ( !w ) {
			continue;
		}
		delete w;
		// add to list, cannot flood directly cause portals might be split on the way
		nodeList.Append( p1->GetNode( !s1 ) );
	}

	// flood into other nodes
	for ( i = 0; i < nodeList.Num(); i++ ) {
		LedgeSubdivLeafNodes_r( nodeList[i], ledge );
	}
}

/*
============
idAASBuild::LedgeSubdivLeafNodes_r

  The node the ledge was originally part of might be split by other ledges.
  Here we recurse down the tree from the original node to find all the new leaf nodes the ledge might be part of.
============
*/
void idAASBuild::LedgeSubdivLeafNodes_r( idBrushBSPNode *node, const idLedge *ledge ) {
	if ( !node ) {
		return;
	}
	if ( !node->GetChild(0) && !node->GetChild(1) ) {
		LedgeSubdivFlood_r( node, ledge );
		return;
	}
	LedgeSubdivLeafNodes_r( node->GetChild(0), ledge );
	LedgeSubdivLeafNodes_r( node->GetChild(1), ledge );
}

/*
============
idAASBuild::LedgeSubdiv
============
*/
void idAASBuild::LedgeSubdiv( idBrushBSPNode *root ) {
	int i, j;
	idBrush *brush;
	idList<idBrushSide *> sideList;

	// create ledge bevels and expand ledges
	for ( i = 0; i < ledgeList.Num(); i++ ) {

		ledgeList[i].CreateBevels( aasSettings->gravityDir );
		ledgeList[i].Expand( aasSettings->boundingBoxes[0], aasSettings->maxStepHeight );

		// if we should write out a ledge map
		if ( ledgeMap ) {
			sideList.SetNum( 0 );
			for ( j = 0; j < ledgeList[i].numPlanes; j++ ) {
				sideList.Append( new idBrushSide( ledgeList[i].planes[j], -1 ) );
			}

			brush = new idBrush();
			brush->FromSides( sideList );

			ledgeMap->WriteBrush( brush );

			delete brush;
		}

		// flood tree from the ledge node and subdivide areas with the ledge
		LedgeSubdivLeafNodes_r( ledgeList[i].node, &ledgeList[i] );

		// remove the node visited flags
		ledgeList[i].node->RemoveFlagRecurseFlood( NODE_VISITED );
	}
}

/*
============
idAASBuild::IsLedgeSide_r
============
*/
bool idAASBuild::IsLedgeSide_r( idBrushBSPNode *node, idFixedWinding *w, const idPlane &plane, const idVec3 &normal, const idVec3 &origin, const float radius ) {
	int res, i;
	idFixedWinding back;
	float dist;

	if ( !node ) {
		return false;
	}

	while ( node->GetChild(0) && node->GetChild(1) ) {
		dist = node->GetPlane().Distance( origin );
		if ( dist > radius ) {
			res = SIDE_FRONT;
		}
		else if ( dist < -radius ) {
			res = SIDE_BACK;
		}
		else {
			res = w->Split( &back, node->GetPlane(), LEDGE_EPSILON );
		}
		if ( res == SIDE_FRONT ) {
			node = node->GetChild(0);
		}
		else if ( res == SIDE_BACK ) {
			node = node->GetChild(1);
		}
		else if ( res == SIDE_ON ) {
			// continue with the side the winding faces
			if ( node->GetPlane().Normal() * normal > 0.0f ) {
				node = node->GetChild(0);
			}
			else {
				node = node->GetChild(1);
			}
		}
		else {
			if ( IsLedgeSide_r( node->GetChild(1), &back, plane, normal, origin, radius ) ) {
				return true;
			}
			node = node->GetChild(0);
		}
	}

	if ( node->GetContents() & AREACONTENTS_SOLID ) {
		return false;
	}

	for ( i = 0; i < w->GetNumPoints(); i++ ) {
		if ( plane.Distance( (*w)[i].ToVec3() ) > 0.0f ) {
			return true;
		}
	}

	return false;
}

/*
============
idAASBuild::AddLedge
============
*/
void idAASBuild::AddLedge( const idVec3 &v1, const idVec3 &v2, idBrushBSPNode *node ) {
	int i, j, merged;

	// first try to merge the ledge with existing ledges
	merged = -1;
	for ( i = 0; i < ledgeList.Num(); i++ ) {

		for ( j = 0; j < 2; j++ ) {
			if ( idMath::Fabs( ledgeList[i].planes[j].Distance( v1 ) ) > LEDGE_EPSILON ) {
				break;
			}
			if ( idMath::Fabs( ledgeList[i].planes[j].Distance( v2 ) ) > LEDGE_EPSILON ) {
				break;
			}
		}
		if ( j < 2 ) {
			continue;
		}

		if ( !ledgeList[i].PointBetweenBounds( v1 ) &&
			!ledgeList[i].PointBetweenBounds( v2 ) ) {
			continue;
		}

		if ( merged == -1 ) {
			ledgeList[i].AddPoint( v1 );
			ledgeList[i].AddPoint( v2 );
			merged = i;
		}
		else {
			ledgeList[merged].AddPoint( ledgeList[i].start );
			ledgeList[merged].AddPoint( ledgeList[i].end );
			ledgeList.RemoveIndex(i);
			break;
		}
	}

	// if the ledge could not be merged
	if ( merged == -1 ) {
		ledgeList.Append( idLedge( v1, v2, aasSettings->gravityDir, node ) );
	}
}

/*
============
idAASBuild::FindLeafNodeLedges
============
*/
void idAASBuild::FindLeafNodeLedges( idBrushBSPNode *root, idBrushBSPNode *node ) {
	int s1, i;
	idBrushBSPPortal *p1;
	idWinding *w;
	idVec3 v1, v2, normal, origin;
	idFixedWinding winding;
	idBounds bounds;
	idPlane plane;
	float radius;

	for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
		s1 = (p1->GetNode(1) == node);

		if ( !(p1->GetFlags() & FACE_FLOOR) ) {
			continue;
		}

		if ( s1 ) {
			plane = p1->GetPlane();
			w = p1->GetWinding()->Reverse();
		}
		else {
			plane = -p1->GetPlane();
			w = p1->GetWinding();
		}

		for ( i = 0; i < w->GetNumPoints(); i++ ) {

			v1 = (*w)[i].ToVec3();
			v2 = (*w)[(i+1)%w->GetNumPoints()].ToVec3();
			normal = (v2 - v1).Cross( aasSettings->gravityDir );
			if ( normal.Normalize() < 0.5f ) {
				continue;
			}

			winding.Clear();
			winding += v1 + normal * LEDGE_EPSILON * 0.5f;
			winding += v2 + normal * LEDGE_EPSILON * 0.5f;
			winding += winding[1].ToVec3() + ( aasSettings->maxStepHeight + 1.0f ) * aasSettings->gravityDir;
			winding += winding[0].ToVec3() + ( aasSettings->maxStepHeight + 1.0f ) * aasSettings->gravityDir;

			winding.GetBounds( bounds );
			origin = (bounds[1] - bounds[0]) * 0.5f;
			radius = origin.Length() + LEDGE_EPSILON;
			origin = bounds[0] + origin;

			plane.FitThroughPoint( v1 + aasSettings->maxStepHeight * aasSettings->gravityDir );

			if ( !IsLedgeSide_r( root, &winding, plane, normal, origin, radius ) ) {
				continue;
			}

			AddLedge( v1, v2, node );
		}

		if ( w != p1->GetWinding() ) {
			delete w;
		}
	}
}

/*
============
idAASBuild::FindLedges_r
============
*/
void idAASBuild::FindLedges_r( idBrushBSPNode *root, idBrushBSPNode *node ) {
	if ( !node ) {
		return;
	}

	if ( node->GetContents() & AREACONTENTS_SOLID ) {
		return;
	}

	if ( !node->GetChild(0) && !node->GetChild(1) ) {
		if ( node->GetFlags() & NODE_VISITED ) {
			return;
		}
		FindLeafNodeLedges( root, node );
		node->SetFlag( NODE_VISITED );
		return;
	}

	FindLedges_r( root, node->GetChild(0) );
	FindLedges_r( root, node->GetChild(1) );
}

/*
============
idAASBuild::WriteLedgeMap
============
*/
void idAASBuild::WriteLedgeMap( const idStr &fileName, const idStr &ext ) {
	ledgeMap = new idBrushMap( fileName, ext );
	ledgeMap->SetTexture( "textures/base_trim/bluetex4q_ed" );
}

/*
============
idAASBuild::LedgeSubdivision

  NOTE: this assumes the bounding box is higher than the maximum step height
		only ledges with vertical sides are considered
============
*/
void idAASBuild::LedgeSubdivision( idBrushBSP &bsp ) {
	numLedgeSubdivisions = 0;
	ledgeList.Clear();

	TRACE_CPU_SCOPE("LedgeSubdivision")
	common->Printf( "[Ledge Subdivision]\n" );

	bsp.GetRootNode()->RemoveFlagRecurse( NODE_VISITED );
	FindLedges_r( bsp.GetRootNode(), bsp.GetRootNode() );
	bsp.GetRootNode()->RemoveFlagRecurse( NODE_VISITED );

	common->Printf( "\r%6d ledges\n", ledgeList.Num() );

	LedgeSubdiv( bsp.GetRootNode() );

	common->Printf( "\r%6d subdivisions\n", numLedgeSubdivisions );
}