//
// Copyright (C) 2004 Tanguy Fautré.
// For conditions of distribution and use,
// see copyright notice in tri_stripper.h
//
//////////////////////////////////////////////////////////////////////
// SVN: $Id: tri_stripper.cpp 86 2005-06-08 17:47:27Z gpsnoopy $
//////////////////////////////////////////////////////////////////////

#include "tri_stripper.h"

#include "detail/connectivity_graph.h"
#include "detail/policy.h"

#include <cassert>




namespace triangle_stripper {

	using namespace detail;




tri_stripper::tri_stripper(const indices & TriIndices)
	: m_Triangles(TriIndices.size() / 3), // Silently ignore extra indices if (Indices.size() % 3 != 0)
	  m_StripID(0),
	  m_FirstRun(true)
{
	SetCacheSize();
	SetMinStripSize();
	SetBackwardSearch();
	SetPushCacheHits();

	make_connectivity_graph(m_Triangles, TriIndices);

	//	Initialize	Progress bar function.
	mUPB	=	NULL;
}



void tri_stripper::Strip(primitive_vector * out_pPrimitivesVector)
{
	assert(out_pPrimitivesVector);

	if (! m_FirstRun) {
		unmark_nodes(m_Triangles);
		ResetStripIDs();
		m_Cache.reset();
		m_TriHeap.clear();
		m_Candidates.clear();
		m_StripID = 0;

		m_FirstRun = false;
	}

	out_pPrimitivesVector->clear();

	InitTriHeap();

	Stripify();
	AddLeftTriangles();
	
	std::swap(m_PrimitivesVector, (* out_pPrimitivesVector));
}



void tri_stripper::InitTriHeap()
{
	m_TriHeap.reserve(m_Triangles.size());

	// Set up the triangles priority queue
	// The lower the number of available neighbour triangles, the higher the priority.
	for (size_t i = 0; i < m_Triangles.size(); ++i)
		m_TriHeap.push(m_Triangles[i].out_size());

	// We're not going to add new elements anymore
	m_TriHeap.lock();

	// Remove useless triangles
	// Note: we had to put all of them into the heap before to ensure coherency of the heap_array object
	while ((! m_TriHeap.empty()) && (m_TriHeap.top() == 0))
		m_TriHeap.pop();
}



void tri_stripper::ResetStripIDs()
{
	for (triangle_graph::node_iterator it = m_Triangles.begin(); it != m_Triangles.end(); ++it)
		(**it).ResetStripID();
}


void tri_stripper::Stripify()
{
	float		percent;
	size_t	triangle_count;
	size_t	current_triangles;
	
	//	Gets the triangle count.
	triangle_count	=	m_TriHeap.size();
	
	while (! m_TriHeap.empty())
	{
		//	If progres bar is activated.
		if (mUPB)
		{
			current_triangles	=	m_TriHeap.size();
		
			percent	=	(mUPBInc	*	(triangle_count - current_triangles)) / triangle_count;

			triangle_count	=	current_triangles;

			//	Update progress bar.
			mUPB(percent);
		}
		
		// There is no triangle in the candidates list, 
		// refill it with the loneliest triangle
		const size_t HeapTop = m_TriHeap.position(0);
		m_Candidates.push_back(HeapTop);

		while (! m_Candidates.empty())
		{
			// Note: FindBestStrip empties the candidate list, 
			// while BuildStrip refills it
			const strip TriStrip = FindBestStrip();

			if (TriStrip.Size() >= m_MinStripSize)
			{
				BuildStrip(TriStrip);
			}
		}

		if (! m_TriHeap.removed(HeapTop))
		{
			m_TriHeap.erase(HeapTop);
		}

		// Eliminate all the triangles that have now become useless
		while ((! m_TriHeap.empty()) && (m_TriHeap.top() == 0))
		{
			m_TriHeap.pop();
		}
	}
}

//	Sets the progress bar function and the increment to update.
void	tri_stripper::SetProgressFunc(Geometry::TIPOFUNC upb,float	increment)
{
	mUPB		=	upb;
	mUPBInc	=	increment;
}

inline strip tri_stripper::FindBestStrip()
{
	// Allow to restore the cache (modified by ExtendTriToStrip) and implicitly reset the cache hit count
	const cache_simulator CacheBackup = m_Cache;

	policy Policy(m_MinStripSize, Cache());

	while (! m_Candidates.empty()) {

		const size_t Candidate = m_Candidates.back();
		m_Candidates.pop_back();

		// Discard useless triangles from the candidate list
		if ((m_Triangles[Candidate].marked()) || (m_TriHeap[Candidate] == 0))
			continue;		

		// Try to extend the triangle in the 3 possible forward directions
		for (size_t i = 0; i < 3; ++i) {

			const strip Strip = ExtendToStrip(Candidate, triangle_order(i));
			Policy.Challenge(Strip, m_TriHeap[Strip.Start()], m_Cache.hitcount());
			
			m_Cache = CacheBackup;
		}

		// Try to extend the triangle in the 6 possible backward directions
		if (m_BackwardSearch) {

			for (size_t i = 0; i < 3; ++i) {

				const strip Strip = BackExtendToStrip(Candidate, triangle_order(i), false);
				Policy.Challenge(Strip, m_TriHeap[Strip.Start()], m_Cache.hitcount());
			
				m_Cache = CacheBackup;
			}

			for (size_t i = 0; i < 3; ++i) {

				const strip Strip = BackExtendToStrip(Candidate, triangle_order(i), true);
				Policy.Challenge(Strip, m_TriHeap[Strip.Start()], m_Cache.hitcount());
			
				m_Cache = CacheBackup;
			}
		}

	}

	return Policy.BestStrip();
}



strip tri_stripper::ExtendToStrip(const size_t Start, triangle_order Order)
{
	const triangle_order StartOrder = Order;
	
	// Begin a new strip
	m_Triangles[Start]->SetStripID(++m_StripID);
	AddTriangle(* m_Triangles[Start], Order, false);

	size_t Size = 1;
	bool ClockWise = false;

	// Loop while we can further extend the strip
	for (tri_iterator Node = (m_Triangles.begin() + Start); 
		(Node != m_Triangles.end()) && (!Cache() || ((Size + 2) < CacheSize()));
		++Size) {

		const const_link_iterator Link = LinkToNeighbour(Node, ClockWise, Order, false);

		// Is it the end of the strip?
		if (Link == Node->out_end()) {

			Node = m_Triangles.end();
			--Size;

		} else {

			Node = Link->terminal();
			(* Node)->SetStripID(m_StripID);
			ClockWise = ! ClockWise;

		}
	}

	return strip(Start, StartOrder, Size);
}



strip tri_stripper::BackExtendToStrip(size_t Start, triangle_order Order, bool ClockWise)
{
	// Begin a new strip
	m_Triangles[Start]->SetStripID(++m_StripID);
	BackAddIndex(LastEdge(* m_Triangles[Start], Order).B());
	size_t Size = 1;

	tri_iterator Node;

	// Loop while we can further extend the strip
	for (Node = (m_Triangles.begin() + Start); 
		!Cache() || ((Size + 2) < CacheSize());
		++Size) {

		const const_link_iterator Link = BackLinkToNeighbour(Node, ClockWise, Order);

		// Is it the end of the strip?
		if (Link == Node->out_end())
			break;

		else {
			Node = Link->terminal();
			(* Node)->SetStripID(m_StripID);
			ClockWise = ! ClockWise;
		}
	}

	// We have to start from a counterclockwise triangle.
	// Simply return an empty strip in the case where the first triangle is clockwise.
	// Even though we could discard the first triangle and start from the next counterclockwise triangle,
	// this often leads to more lonely triangles afterward.
	if (ClockWise)
		return strip();

	if (Cache()) {
		m_Cache.merge(m_BackCache, Size);
		m_BackCache.reset();
	}

	return strip(Node - m_Triangles.begin(), Order, Size);
}



void tri_stripper::BuildStrip(const strip Strip)
{
	const size_t Start = Strip.Start();

	bool ClockWise = false;
	triangle_order Order = Strip.Order();

	// Create a new strip
	m_PrimitivesVector.push_back(primitive_group());
	m_PrimitivesVector.back().Type = TRIANGLE_STRIP;
	AddTriangle(* m_Triangles[Start], Order, true);
	MarkTriAsTaken(Start);

	// Loop while we can further extend the strip
	tri_iterator Node = (m_Triangles.begin() + Start);

	for (size_t Size = 1; Size < Strip.Size(); ++Size) {

		const const_link_iterator Link = LinkToNeighbour(Node, ClockWise, Order, true);

		assert(Link != Node->out_end());

		// Go to the next triangle
		Node = Link->terminal();
		MarkTriAsTaken(Node - m_Triangles.begin());
		ClockWise = ! ClockWise;
	}
}



inline tri_stripper::const_link_iterator tri_stripper::LinkToNeighbour(const const_tri_iterator Node, const bool ClockWise, triangle_order & Order, const bool NotSimulation)
{
	const triangle_edge Edge = LastEdge(** Node, Order);

	for (const_link_iterator Link = Node->out_begin(); Link != Node->out_end(); ++Link) {

		// Get the reference to the possible next triangle
		const triangle & Tri = ** Link->terminal();

		// Check whether it's already been used
		if (NotSimulation || (Tri.StripID() != m_StripID)) {

			if (! Link->terminal()->marked()) {

				// Does the current candidate triangle match the required position for the strip?

				if ((Edge.B() == Tri.A()) && (Edge.A() == Tri.B())) {
					Order = (ClockWise) ? ABC : BCA;
					AddIndex(Tri.C(), NotSimulation);
					return Link;
				}

				else if ((Edge.B() == Tri.B()) && (Edge.A() == Tri.C())) {
					Order = (ClockWise) ? BCA : CAB;
					AddIndex(Tri.A(), NotSimulation);
					return Link;
				}

				else if ((Edge.B() == Tri.C()) && (Edge.A() == Tri.A())) {
					Order = (ClockWise) ? CAB : ABC;
					AddIndex(Tri.B(), NotSimulation);
					return Link;
				}
			}
		}

	}

	return Node->out_end();
}



inline tri_stripper::const_link_iterator tri_stripper::BackLinkToNeighbour(const_tri_iterator Node, bool ClockWise, triangle_order & Order)
{
	const triangle_edge Edge = FirstEdge(** Node, Order);

	for (const_link_iterator Link = Node->out_begin(); Link != Node->out_end(); ++Link) {

		// Get the reference to the possible previous triangle
		const triangle & Tri = ** Link->terminal();

		// Check whether it's already been used
		if ((Tri.StripID() != m_StripID) && ! Link->terminal()->marked()) {

			// Does the current candidate triangle match the required position for the strip?

			if ((Edge.B() == Tri.A()) && (Edge.A() == Tri.B())) {
				Order = (ClockWise) ? CAB : BCA;
				BackAddIndex(Tri.C());
				return Link;
			}

			else if ((Edge.B() == Tri.B()) && (Edge.A() == Tri.C())) {
				Order = (ClockWise) ? ABC : CAB;
				BackAddIndex(Tri.A());
				return Link;
			}

			else if ((Edge.B() == Tri.C()) && (Edge.A() == Tri.A())) {
				Order = (ClockWise) ? BCA : ABC;
				BackAddIndex(Tri.B());
				return Link;
			}
		}

	}

	return Node->out_end();
}



void tri_stripper::MarkTriAsTaken(const size_t i)
{
	typedef triangle_graph::node_iterator tri_node_iter;
	typedef triangle_graph::out_arc_iterator tri_link_iter;

	// Mark the triangle node
	m_Triangles[i].mark();

	// Remove triangle from priority queue if it isn't yet
	if (! m_TriHeap.removed(i))
		m_TriHeap.erase(i);

	// Adjust the degree of available neighbour triangles
	for (tri_link_iter Link = m_Triangles[i].out_begin(); Link != m_Triangles[i].out_end(); ++Link) {

		const size_t j = Link->terminal() - m_Triangles.begin();

		if ((! m_Triangles[j].marked()) && (! m_TriHeap.removed(j))) {
			size_t NewDegree = m_TriHeap.peek(j);
			NewDegree = NewDegree - 1;
			m_TriHeap.update(j, NewDegree);

			// Update the candidate list if cache is enabled
			if (Cache() && (NewDegree > 0))
				m_Candidates.push_back(j);
		}
	}
}



inline triangle_edge tri_stripper::FirstEdge(const triangle & Triangle, const triangle_order Order)
{
	switch (Order)
	{
	case ABC:
		return triangle_edge(Triangle.A(), Triangle.B());

	case BCA:
		return triangle_edge(Triangle.B(), Triangle.C());

	case CAB:
		return triangle_edge(Triangle.C(), Triangle.A());

	default:
		assert(false);
		return triangle_edge(0, 0);
	}
}



inline triangle_edge tri_stripper::LastEdge(const triangle & Triangle, const triangle_order Order)
{
	switch (Order)
	{
	case ABC:
		return triangle_edge(Triangle.B(), Triangle.C());

	case BCA:
		return triangle_edge(Triangle.C(), Triangle.A());

	case CAB:
		return triangle_edge(Triangle.A(), Triangle.B());

	default:
		assert(false);
		return triangle_edge(0, 0);
	}
}



inline void tri_stripper::AddIndex(const index i, const bool NotSimulation)
{
	if (Cache())
		m_Cache.push(i, ! NotSimulation);

	if (NotSimulation)
		m_PrimitivesVector.back().Indices.push_back(i);
}



inline void tri_stripper::BackAddIndex(const index i)
{
	if (Cache())
		m_BackCache.push(i, true);
}



inline void tri_stripper::AddTriangle(const triangle & Tri, const triangle_order Order, const bool NotSimulation)
{
	switch (Order)
	{
	case ABC:
		AddIndex(Tri.A(), NotSimulation);
		AddIndex(Tri.B(), NotSimulation);
		AddIndex(Tri.C(), NotSimulation);
		break;

	case BCA:
		AddIndex(Tri.B(), NotSimulation);
		AddIndex(Tri.C(), NotSimulation);
		AddIndex(Tri.A(), NotSimulation);
		break;

	case CAB:
		AddIndex(Tri.C(), NotSimulation);
		AddIndex(Tri.A(), NotSimulation);
		AddIndex(Tri.B(), NotSimulation);
		break;
	}
}



inline void tri_stripper::BackAddTriangle(const triangle & Tri, const triangle_order Order)
{
	switch (Order)
	{
	case ABC:
		BackAddIndex(Tri.C());
		BackAddIndex(Tri.B());
		BackAddIndex(Tri.A());
		break;

	case BCA:
		BackAddIndex(Tri.A());
		BackAddIndex(Tri.C());
		BackAddIndex(Tri.B());
		break;

	case CAB:
		BackAddIndex(Tri.B());
		BackAddIndex(Tri.A());
		BackAddIndex(Tri.C());
		break;
	}
}



void tri_stripper::AddLeftTriangles()
{
	// Create the last indices array and fill it with all the triangles that couldn't be stripped
	primitive_group Primitives;
	Primitives.Type = TRIANGLES;
	m_PrimitivesVector.push_back(Primitives);
	indices & Indices = m_PrimitivesVector.back().Indices;

	for (size_t i = 0; i < m_Triangles.size(); ++i)
		if (! m_Triangles[i].marked()) {
			Indices.push_back(m_Triangles[i]->A());
			Indices.push_back(m_Triangles[i]->B());
			Indices.push_back(m_Triangles[i]->C());
		}

	// Undo if useless
	if (Indices.size() == 0)
		m_PrimitivesVector.pop_back();
}



inline bool tri_stripper::Cache() const
{
	return (m_Cache.size() != 0);
}



inline size_t tri_stripper::CacheSize() const
{
	return m_Cache.size();
}




} // namespace triangle_stripper