///////////////////////////////////////////////////////////////////////////////
/// @file deLine.cpp
///
/// @brief Line creation
///
/// @author Assassin 
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Feb 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "deLine_priv.hpp"
#include "deBrush.hpp"
#include "deMath.hpp"

#define LINE_TESTS (0)

IdeLine * IdeLine_CreateStraightLine()
{
	return new StraightLine;
}
IdeLine * IdeLine_CreateBezierLine()
{
	return new BezierLine;
}
IdeLine * IdeLine_CreateArcLine()
{
	return new ArcLine;
}
IdeLine * IdeLine_CreateGroupLine()
{
	return new GroupLine;
} 
deBoolean IdeLine_GroupLineAdd(IdeLine * Group, IdeLine * ToAdd)
{
	return ((GroupLine*)Group)->AddLine(ToAdd);
}
long IdeLine_GroupLineRemoveLast(IdeLine * Group)
{
	return ((GroupLine*)Group)->RemoveLine();
}


deLine::deLine()
{
	m_CVNum = 0;
	m_Length = 1;
	m_Changed = deFALSE;
}

deLine::~deLine()
{
}

long deLine::Release()
{
	delete this;
	return 0;
}

void deLine::GetPointOnLine(deDouble Fraction, deVec3d & point)
{
	InterpolateLine(Fraction, point);
}

void deLine::GetTangentAtPoint(deDouble Fraction, deVec3d & point)
{
	InterpolateTangent(Fraction, point);
}

long deLine::GetLength()
{
	return m_Length;
}

long deLine::GetNumCVs()
{
	return m_CVNum;
}

void deLine::GetCVList(deVec3d buffer[])
{
	for (int i = 0; i < m_CVNum; i++)
		buffer[i] = m_CVList[i];
}

deVec3d deLine::GetCV(long num)
{
	return m_CVList[num];
}

void deLine::SetCV(long num, deVec3d & CV)
{
	m_CVList[num] = CV;
	m_Changed = deTRUE;
}

void deLine::SetCVList(long num, deVec3d CVList[])
{
	m_CVList.Resize(0);
	m_CVList.Resize(num);
	m_CVNum = num;
	for (int i = 0; i < m_CVNum; i++)
		m_CVList[i] = CVList[i];
	m_Changed = deTRUE;
}

void deLine::AddCV(deVec3d & point)
{
	m_CVList.Resize(m_CVNum + 1);
	m_CVList[m_CVNum] = point;
	m_CVNum++;
	m_Changed = deTRUE;
}

IdeLine * deLine::Copy()
{
	deLine * p = (deLine*)CopyLine();
	p->m_CVList = m_CVList;
	p->m_CVNum = m_CVNum;
	p->m_Changed = deTRUE;
	return p;
}

//=======================================================
GroupLine::GroupLine()
{
	m_Length = 0;
}

GroupLine::~GroupLine()
{
	int i;
	for (i = 0; i < m_Length; i++)
		m_Lines[i]->Release();
}

deBoolean GroupLine::AddLine(IdeLine * line)
{
	if (m_Length > 0)
	{
		deVec3d p1,p2;
		line->GetPointOnLine(0,p1);
		m_Lines[m_Length-1]->GetPointOnLine(1, p2);
		if (!Vec3d_Compare(p1,p2))
		{
			return deFALSE;
		}
	}
	m_Lines.Resize(m_Length+1);
	m_Lines[m_Length] = line->Copy();
	m_Length++;
	return deTRUE;
}

long GroupLine::RemoveLine()
{
	if (m_Length > 0)
		m_Length--;
	else
		return 0;
	IdeLine * p = m_Lines[m_Length];
	if (p)
		p->Release();
	m_Lines.Resize(m_Length);

	return m_Length;
}

IdeLine * GroupLine::CopyLine()
{
	GroupLine * l = new GroupLine;
	for (int i = 0; i < m_Length; i++)
		l->AddLine(m_Lines[i]);
	return l;
}

void GroupLine::InterpolateLine(deDouble Fraction, deVec3d & point)
{
	int index = (int)(Fraction);
	if (index == m_Length)
		index--;
	Fraction -= index;
	m_Lines[index]->GetPointOnLine(Fraction, point);
}

void GroupLine::InterpolateTangent(deDouble Fraction, deVec3d & point)
{
	int index = (int)(Fraction);
	if (deDouble(index) == Fraction)
	{
		if (index == 0)
		{
			m_Lines[index]->GetTangentAtPoint(Fraction, point);
		}
		else if (index == m_Length)
		{
			index--;
			Fraction -= index;
			m_Lines[index]->GetTangentAtPoint(Fraction, point);
		}
		else
		{
			deVec3d temp;
			Fraction = 0;
			m_Lines[index]->GetTangentAtPoint(Fraction, temp);
			Fraction = 1;
			index -= 1;
			m_Lines[index]->GetTangentAtPoint(Fraction, point);
			point = (point + temp) * 0.5;
		}
	}
	else
	{
		Fraction -= index;
		m_Lines[index]->GetTangentAtPoint(Fraction, point);
	}
}



//=======================================================
StraightLine::StraightLine()
{
#if LINE_TESTS
	deVec3d list[] = {{0,-4,0},{0,0,0}};
	SetCVList(2, list);

	deVec3d point;
	GetPointOnLine(0.75, point);
#endif
}

StraightLine::~StraightLine()
{
}

IdeLine * StraightLine::CopyLine()
{
	return new StraightLine;
}

void StraightLine::InterpolateLine(deDouble Fraction, deVec3d & point)
{
	point = (m_CVList[1] * Fraction) + (m_CVList[0] * (1-Fraction));
}

void StraightLine::InterpolateTangent(deDouble , deVec3d & point)
{
	point = m_CVList[1] - m_CVList[0];
	Vec3d_Normalize(point);
}


//=======================================================
BezierLine::BezierLine()
{
#if LINE_TESTS
	deVec3d hull[] = {{0,0,0},{0,2,0},{2,2,0},{2,4,0}};
	SetCVList(4, hull);

	deVec3d point;
	GetPointOnLine(0.75, point);
#endif
}

BezierLine::~BezierLine()
{
}

IdeLine * BezierLine::CopyLine()
{
	BezierLine * ret = new BezierLine;
	ret->SetCVList(m_CVList.Length(), m_CVList.GetCArray());
	return ret;
}

/*
From my pre-cal class
binomial thm
(x + y)^n = x^n + n*x^(n-1)*y + ((n*(n-1))/(2!))*x^(n-2)*y^2...y^n
specific term:
1) Find key # (k)	[term number - 1]
2) Find n			[exponent of binom.]
	(n k)			[(step down n k times)/(k!)]
					(8 3) = (8*7*6)/(3*2*1)
3) Use (n k)(1st term)^(n-k)(2nd term)^k
in this case the equation is (t + (1-t))^n
*/

static deDouble dePower(deDouble base, const int exp)
{
	if (exp == 0)
		return 1.0;
	if (base == 1.0 || base == 0.0 || exp == 1)
		return base;
	deDouble result = 1.0;
	for (int i = 0; i < exp; i++)
		result *= base;
	return result;
}

// like F0(t), F1(t), F2(t), etc... from the bezier article on gamedev.net
deDouble BezierLine::F(long k, deDouble t)
{
#pragma todo (make sure that the 'optimization' here didnt bust things)
	int n, nk, top, bottom, tmp;
	deDouble result;
	n = m_CVNum - 1;	// the degree of equation
	if (m_CVNum == 3)
	{
		if (k == 0)
		{
			return t*t;
		}
		else
		{
			if (k == 1)
			{
				return 2*t*(1-t);
			}
			else // k == 2
			{
				t = 1-t;
				return t*t;
			}
		}
	}
	if (m_CVNum == 4)
	{
		if (k < 2)
		{
			if (k == 0)
			{
				return t*t*t;
			}
			else
			{
				return 3*t*t*(1-t);
			}
		}
		else
		{
			if (k == 2)
			{
				result = (1-t);
				return 3*t*result*result;
			}
			else
			{
				result = 1-t;
				return result*result*result;
			}
		}
	}
	result = 0;
	if (k == 0)
		return (deDouble)dePower(t, n);
	if (k == n)
		return (deDouble)dePower((1-t), n);

	// step down n a number of k times
	top = 1;
	for (tmp = n; tmp > n-k; tmp--)
		top *= tmp;
	// k! (factorial)
	bottom = 1;
	for (tmp = k; tmp > 0; tmp--)
		bottom *= tmp;
	nk = top / bottom;
	
	result = (deDouble)(nk * dePower((t), n-k) * dePower((1-t), k));
	return result;
}

void BezierLine::InterpolateLine(deDouble Fraction, deVec3d & point)
{
	point = deZeroVec;
	if (Fraction < 0 || Fraction > 1)
		return;
	for (int term = 0; term < m_CVNum; term++)
	{
		point = point + m_CVList[term] * F(term,1-Fraction);
	}
}

deDouble BezierLine::D(long k, deDouble t)
{
	/*
	if (m_CVNum == 3)
	{
		if (k == 0)
			return -2*(1-t);
		if (k == 1)
			return 2*(-t + (1-t));
		if (k == 2)
			return 2*t;
	}
	*/
	/*
	if (m_CVNum == 4)
	{
		if (k == 0)
			return -3*(1-t)*(1-t);
		if (k == 1)
			return -6*t*(1-t) + 3*(1-t)*(1-t);
		if (k == 2)
			return 6*t*(1-t) + -3*t*t;
		if (k == 3)
			return 3*t*t;
	}
	*/
	{
		int n, nk, top, bottom, tmp;
		deDouble result = 0;
		n = m_CVNum - 1;	// the degree of equation
		if (k == 0)
			return (deDouble)dePower((1-t), n-1) * -n;
		if (k == n)
			return (deDouble)dePower((t), n-1) * n;

		// step down n a number of k times
		top = 1;
		for (tmp = n; tmp > n-k; tmp--)
			top *= tmp;
		// k! (factorial)
		bottom = 1;
		for (tmp = k; tmp > 0; tmp--)
			bottom *= tmp;
		nk = top / bottom;
		
		result = (deDouble)(nk * -(n-k) * dePower((1-t), n-k-1) * dePower((t), k));
		result +=(deDouble)(nk * (k) * dePower((1-t), n-k) * dePower((t), k-1));
		return result;
	}
}

void BezierLine::InterpolateTangent(deDouble Fraction, deVec3d & point)
{
	if (m_CVNum < 2)
	{
		point = deZeroVec;
		return;
	}
	if (m_CVNum == 2 || Fraction == 0)
	{
		point = m_CVList[1] - m_CVList[0];
		Vec3d_Normalize(point);
		return;
	}
	if (Fraction == 1)
	{
		point = m_CVList[m_CVNum-1] - m_CVList[m_CVNum-2];
		Vec3d_Normalize(point);
		return;
	}
	point = deZeroVec;
	for (int term = 0; term < m_CVNum; term++)
	{
		point = point + (m_CVList[term]) * D(term,Fraction);
	}
	Vec3d_Normalize(point);
}


//=======================================================
ArcLine::ArcLine()
{
	m_Changed = deTRUE;
#if LINE_TESTS
	deVec3d hull[] = {{0,0,0},{0,0,0.5},{0,25,0}};
	SetCVList(3, hull);

	deVec3d point;
	GetPointOnLine(0.5, point);
#endif
}

ArcLine::~ArcLine()
{
}

IdeLine * ArcLine::CopyLine()
{
	ArcLine * p = new ArcLine;
	p->m_Degree = m_Degree;
	p->m_Radius = m_Radius;
	p->m_transform = m_transform;
	return p;
}

void ArcLine::InterpolateLine(deDouble Fraction, deVec3d & point)
{
	if (m_CVNum < 3)
	{
		point = deZeroVec;
		return;
	}
	if (m_Changed)
	{
		deVec3d L,U,I;
		I = m_CVList[1] - m_CVList[0];
		U = m_CVList[2] - m_CVList[0];
		m_Radius = Vec3d_Normalize(I);
		m_Degree = Vec3d_Normalize(U);
		m_Degree = min(m_Degree, m_Radius);
		m_Degree = 2 * DE_PI * (m_Degree / m_Radius);
		L = Vec3d_Cross(U, I);
		if (Vec3d_Compare(L,deZeroVec))
			return;
		U = Vec3d_Cross(I, L);
		m_transform.SetRightUpIn(L,U,I);
		m_transform.SetTranslation(m_CVList[0]);
		m_Changed = deFALSE;
	}
	{
		deVec3d in;
		in.x = SIN(-(m_Degree * Fraction));
		in.z = COS(-(m_Degree * Fraction));
		in.y = 0;
		in *= m_Radius;
		m_transform.Transform(in, in);
		point = in;
		Vec3d_Squeeze(point);
	}
}

void ArcLine::InterpolateTangent(deDouble Fraction, deVec3d & point)
{
	if (m_CVNum < 3)
	{
		point = deZeroVec;
		return;
	}
	if (m_Changed)
	{
		deVec3d L,U,I;
		I = m_CVList[1] - m_CVList[0];
		U = m_CVList[2] - m_CVList[0];
		m_Radius = Vec3d_Normalize(I);
		m_Degree = Vec3d_Normalize(U);
		m_Degree = min(m_Degree, m_Radius);
		m_Degree = 2 * DE_PI * (m_Degree / m_Radius);
		L = Vec3d_Cross(U, I);
		if (Vec3d_Compare(L,deZeroVec))
			return;
		U = Vec3d_Cross(I, L);
		m_transform.SetRightUpIn(L,U,I);
		m_transform.SetTranslation(m_CVList[0]);
		m_Changed = deFALSE;
	}
	{
		deTransform rot;
		deVec3d right;
		rot.SetYRot((m_Degree * Fraction));
		rot.GetRight(right);
		m_transform.Transform(right, right);
		right -= m_transform.Translation;
		point = right;
		Vec3d_Squeeze(point);
	}
	Vec3d_Normalize(point);
}
