//Toonz components includes

#include "tcurveutil.h"

#include "tinterval.h"

#include "tellipticbrushP.h"

#include "tstrokeoutline.h"

using namespace tellipticbrush;

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

//    EXPLANATION

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

/*! \file tellipticbrush.cpp

This code deals with the "outlinization" process of a TStroke instance.

The process of extracing the outline of a thick stroke can be resumed in 2 main steps:

  1. Discretize the stroke centerline in the most appropriate centerline points,

     extracting infos about position and left/right derivatives at each.

  2. Build the outline points associated to each individual centerline point;

     eventually including additional junction points and caps.

The first major step has some sub-routines worth noting:

  1.1 Isolate regions of the stroke where the thickness speed is greater

      than the gemoetrical speed of the centerline. These points are 'self-covered'

      by their immediate neighbourhood, and thus cannot be seen - or build outline directions.

  1.2 Some procedural style need to sample the centerline at a given length step.

  1.3 The centerline should be sampled so that the resulting polygonal outline

      approximation is tightly close to the theoretical outline, up to an error bound.

      The recursive approach is the simplest to deal with this issue.

The second step implements different outline styles to extrude the centerline points.

*/

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

//    Geometric Helper Functions

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

//! Returns the distance between two points

double tellipticbrush::dist(const TPointD &P1, const TPointD &P2)

{

	return norm(P2 - P1);

}

//------------------------------------------------------------

//! Returns the distance between two points

double tellipticbrush::dist(const TThickPoint &P1, const TThickPoint &P2)

{

	return norm(P2 - P1);

}

//------------------------------------------------------------

//!Returns the angle between (unnormalized) vectors v1 and v2

double tellipticbrush::angle(const TPointD &v1, const TPointD &v2)

{

	TPointD d1(v1 * (1.0 / norm(v1))), d2(v2 * (1.0 / norm(v2)));

	return atan2(cross(v1, v2), v1 * v2);

}

//------------------------------------------------------------

/*!

  Returns the intersection between two lines in the form of \b coordinates

  from a pair of the lines' starting points. Passed directions must have norm 1.

  If the system's determinant modulus is under the specified tolerance parameter, 

  TConsts::napd is returned.

*/

TPointD tellipticbrush::intersectionCoords(

	const TPointD &P0, const TPointD &d0, const TPointD &P1, const TPointD &d1,

	double detTol)

{

	//Solve P0 + x * d0 == P1 + y * d1

	double det = d0.y * d1.x - d0.x * d1.y;

	if (fabs(det) < detTol)

		return TConsts::napd;

	TPointD P1_P0(P1 - P0);

	return TPointD(

		(d1.x * P1_P0.y - d1.y * P1_P0.x) / det,

		(d0.x * P1_P0.y - d0.y * P1_P0.x) / det);

}

//------------------------------------------------------------

/*!

  Returns the left or right envelope direction of centerline point p against thick direction d.

*/

void tellipticbrush::buildEnvelopeDirection(

	const TThickPoint &p, const TThickPoint &d, bool left, TPointD &res)

{

	double dNorm2 = sq(d.x) + sq(d.y);

	double a = -d.thick / dNorm2;

	double b = sqrt(dNorm2 - sq(d.thick)) / dNorm2;

	TPointD n(left ? TPointD(-d.y, d.x) : TPointD(d.y, -d.x));

	res = a * TPointD(d.x, d.y) + b * n;

}

//------------------------------------------------------------

void tellipticbrush::buildEnvelopeDirections(

	const TThickPoint &p, const TThickPoint &d, TPointD &resL, TPointD &resR)

{

	double dNorm2 = sq(d.x) + sq(d.y);

	double a = -d.thick / dNorm2;

	double b = sqrt(dNorm2 - sq(d.thick)) / dNorm2;

	TPointD n(-d.y, d.x);

	resL = a * TPointD(d.x, d.y) + b * n;

	resR = a * TPointD(d.x, d.y) - b * n;

}

//------------------------------------------------------------

/*!

  Extrudes centerline point p against thick direction d, returning its left or right

  envelope displacement vector.

*/

void tellipticbrush::buildEnvelopeVector(

	const TThickPoint &p, const TThickPoint &d, bool left, TPointD &res)

{

	buildEnvelopeDirection(p, d, left, res);

	res.x = p.thick * res.x;

	res.y = p.thick * res.y;

}

//------------------------------------------------------------

void tellipticbrush::buildEnvelopeVectors(

	const TThickPoint &p, const TThickPoint &d, TPointD &resL, TPointD &resR)

{

	buildEnvelopeDirections(p, d, resL, resR);

	resL.x = p.thick * resL.x;

	resL.y = p.thick * resL.y;

	resR.x = p.thick * resR.x;

	resR.y = p.thick * resR.y;

}

//------------------------------------------------------------

/*!

  Builds the angle that supports a *quality* discretization of the circle

  with maximal error < m_pixSize.

*/

void tellipticbrush::buildAngularSubdivision(

	double radius, double angle, double err, int &nAngles)

{

	/*

    See "Graphic Gems", page 600.

    NOTE: maxAngle is not multiplied by 2.0 as the naive pythagorical

    argument would pretend. The 2.0 holds if we want to find the angle

    at which the distance of the circle from its approximation is always < error.

    But we want MORE. We want that to happen against the distance from EVERY

    TANGENT LINE of the arc - not the arc itself.

    This is coherent with the assumption that pixels orientation is not known.

    It's easy to see that maxAngle just has to be not multiplied by 2.

  */

	double maxAngle = acos(1.0 - err / radius); //* 2.0;

	nAngles = tceil(fabs(angle) / maxAngle);

}

//------------------------------------------------------------

TRectD tellipticbrush::computeBBox(const TStroke &stroke)

{

	TRectD bbox;

	int i, n = stroke.getChunkCount();

	for (i = 0; i < n; i++)

		bbox += stroke.getChunk(i)->getBBox();

	return bbox;

}

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

//    CenterlinePoint implementation

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

void tellipticbrush::CenterlinePoint::buildPos(const TStroke &stroke)

{

	if (m_posBuilt)

		return;

	m_p = stroke.getChunk(m_chunkIdx)->getThickPoint(m_t);

	m_posBuilt = true;

}

//------------------------------------------------------------

void tellipticbrush::CenterlinePoint::buildDirs(const TStroke &stroke)

{

	if (m_dirsBuilt)

		return;

	int chunkPrev, chunkNext;

	double tPrev, tNext;

	bool coveredPrev, coveredNext;

	//Discriminate the boundary cases

	bool quadBoundary;

	if (m_t == 0.0) {

		quadBoundary = true;

		chunkPrev = m_chunkIdx - 1, chunkNext = m_chunkIdx;

		tPrev = 1.0, tNext = 0.0;

	} else if (m_t == 1.0) {

		quadBoundary = true;

		chunkPrev = m_chunkIdx, chunkNext = m_chunkIdx + 1;

		tPrev = 1.0, tNext = 0.0;

	} else {

		quadBoundary = false;

		chunkPrev = chunkNext = m_chunkIdx;

		tPrev = tNext = m_t;

	}

	//Build the backward direction

	if (chunkPrev >= 0) {

		const TThickQuadratic *ttqPrev = stroke.getChunk(chunkPrev);

		const TThickPoint &P0 = ttqPrev->getThickP0();

		const TThickPoint &P1 = ttqPrev->getThickP1();

		const TThickPoint &P2 = ttqPrev->getThickP2();

		if (quadBoundary && (P1 == P2))

			m_prevD = P2 - P0; //Toonz 'Linear' CPs. Eliminating a perilous singularity this way.

		else {

			m_prevD.x = 2.0 * ((P1.x - P0.x) + tPrev * (P0.x - 2.0 * P1.x + P2.x));

			m_prevD.y = 2.0 * ((P1.y - P0.y) + tPrev * (P0.y - 2.0 * P1.y + P2.y));

			m_prevD.thick = 2.0 * ((P1.thick - P0.thick) + tPrev * (P0.thick - 2.0 * P1.thick + P2.thick));

		}

		//Points whose thickness derivative does exceeds the point speed

		//cannot project envelope directions for that direction. This needs to be known.

		coveredPrev = (sq(m_prevD.x) + sq(m_prevD.y) < sq(m_prevD.thick) + tolPar);

		//Accept only uncovered derivatives

		m_hasPrevD = !coveredPrev;

	} else {

		m_hasPrevD = false;

		coveredPrev = true; //ie prev coverage must not affect next coverage

		m_prevD = TConsts::natp;

	}

	//Build the forward direction

	if (chunkPrev == chunkNext) {

		//If the quadratic is the same, no need to derive it twice

		m_hasNextD = m_hasPrevD;

		m_nextD = m_prevD;

		coveredNext = coveredPrev;

	} else if (chunkNext < stroke.getChunkCount()) {

		const TThickQuadratic *ttqNext = stroke.getChunk(chunkNext);

		const TThickPoint &P0 = ttqNext->getThickP0();

		const TThickPoint &P1 = ttqNext->getThickP1();

		const TThickPoint &P2 = ttqNext->getThickP2();

		if (quadBoundary && (P0 == P1))

			m_nextD = P2 - P0;

		else {

			m_nextD.x = 2.0 * ((P1.x - P0.x) + tNext * (P0.x - 2.0 * P1.x + P2.x));

			m_nextD.y = 2.0 * ((P1.y - P0.y) + tNext * (P0.y - 2.0 * P1.y + P2.y));

			m_nextD.thick = 2.0 * ((P1.thick - P0.thick) + tNext * (P0.thick - 2.0 * P1.thick + P2.thick));

		}

		coveredNext = (sq(m_nextD.x) + sq(m_nextD.y) < sq(m_nextD.thick) + tolPar);

		m_hasNextD = !coveredNext;

	} else {

		m_hasNextD = false;

		coveredNext = true; //ie prev coverage must not affect next coverage

		m_nextD = TConsts::natp;

	}

	m_covered = (coveredPrev && coveredNext);

	m_dirsBuilt = true;

}

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

//    Specialized Linearizator for common stroke drawing

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

namespace

{

class LengthLinearizator : public tellipticbrush::StrokeLinearizator

{

	double m_lengthStep;

	int m_countIdx;

public:

	LengthLinearizator(const TStroke *stroke, double lengthStep)

		: StrokeLinearizator(stroke), m_lengthStep(lengthStep), m_countIdx(0) {}

	void linearize(std::vector<centerlinepoint> &cPoints, int chunk);</centerlinepoint>

};

//--------------------------------------------------------------------------------------------

void LengthLinearizator::linearize(std::vector<centerlinepoint> &cPoints, int chunk)</centerlinepoint>

{

	if (m_lengthStep == 0.0)

		return;

	//Retrieve the stroke length at stroke start

	double startW = this->m_stroke->getW(chunk, 0.0);

	double startLength = this->m_stroke->getLength(startW);

	//Retrieve the quadratic's end length

	const TThickQuadratic *ttq = this->m_stroke->getChunk(chunk);

	double endLength = startLength + ttq->getLength();

	//Build the step-length inside the chunk

	int n = tceil(startLength / m_lengthStep);

	double length;

	double t, w;

	int chk;

	for (length = n * m_lengthStep; length < endLength; length += m_lengthStep) {

		//Retrieve the new params at length. Need to use the sloppy TStroke interface,

		//unfortunately...

		w = this->m_stroke->getParameterAtLength(length);

		//WARNING: TStroke's interface is COMPLETELY WRONG about what gets returned

		//by the following function. This is just *CRAZY* - however, let's take it all right...

		bool ok = !this->m_stroke->getChunkAndT(w, chk, t);

		//In case something goes wrong, skip

		if (!ok || chk != chunk)

			continue;

		//Store the param, that NEEDS TO BE INCREMENTALLY COUNTED - as length linearization

		//is typically used for special procedural vector styles that need this info.

		CenterlinePoint cPoint(chk, t);

		cPoint.m_countIdx = m_countIdx += 2; //++m_countIdx;

		cPoints.push_back(cPoint);

	}

}

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

class RecursiveLinearizator : public tellipticbrush::StrokeLinearizator

{

	double m_pixSize;

public:

	RecursiveLinearizator(const TStroke *stroke, double pixSize)

		: StrokeLinearizator(stroke), m_pixSize(pixSize) {}

	void linearize(std::vector<centerlinepoint> &cPoints, int chunk);</centerlinepoint>

	void subdivide(std::vector<centerlinepoint> &cPoints,</centerlinepoint>

				   CenterlinePoint &cp0, CenterlinePoint &cp1);

};

//--------------------------------------------------------------------------------------------

void RecursiveLinearizator::linearize(std::vector<centerlinepoint> &cPoints, int chunk)</centerlinepoint>

{

	/*

    Recursively linearizes the centerline, in the following way:

    Take one point, together with the next. Add a point in the middle interval, until

    the next thick point is included (up to pixSize) in the 'forward-cast' envelope of

    current one. If the midpoint was added, repeat on the 2 sub-intervals.

  */

	const TStroke &stroke = *this->m_stroke;

	const TThickQuadratic &ttq = *stroke.getChunk(chunk);

	//Sort the interval (SHOULD BE DONE OUTSIDE?)

	std::sort(cPoints.begin(), cPoints.end());

	std::vector<centerlinepoint> addedPoints;</centerlinepoint>

	unsigned int i, size_1 = cPoints.size() - 1;

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

		cPoints[i].buildPos(stroke);

		cPoints[i].buildDirs(stroke);

		cPoints[i + 1].buildPos(stroke);

		cPoints[i + 1].buildDirs(stroke);

		subdivide(addedPoints, cPoints[i], cPoints[i + 1]);

	}

	cPoints[size_1].buildPos(stroke);

	cPoints[size_1].buildDirs(stroke);

	CenterlinePoint cpEnd(chunk, 1.0);

	{

		const TThickPoint &P1(ttq.getThickP1());

		cpEnd.m_p = ttq.getThickP2();

		cpEnd.m_prevD = TThickPoint(

			2.0 * (cpEnd.m_p.x - P1.x),

			2.0 * (cpEnd.m_p.y - P1.y),

			2.0 * (cpEnd.m_p.thick - P1.thick));

		cpEnd.m_hasPrevD = true; //The effective false case should already be dealt by sqrt...

	}

	subdivide(addedPoints, cPoints[size_1], cpEnd);

	cPoints.insert(cPoints.end(), addedPoints.begin(), addedPoints.end());

}

//--------------------------------------------------------------------------------------------

void RecursiveLinearizator::subdivide(std::vector<centerlinepoint> &cPoints,</centerlinepoint>

									  CenterlinePoint &cp0, CenterlinePoint &cp1)

{

	if (!(cp0.m_hasNextD && cp1.m_hasPrevD))

		return;

	//Build the distance of next from the outline of cp's 'envelope extension'

	TPointD envDirL0, envDirR0, envDirL1, envDirR1;

	buildEnvelopeDirections(cp0.m_p, cp0.m_nextD, envDirL0, envDirR0);

	buildEnvelopeDirections(cp1.m_p, cp1.m_prevD, envDirL1, envDirR1);

	TPointD diff(convert(cp1.m_p) - convert(cp0.m_p));

	double d = tmax(

		fabs(envDirL0 * (diff + cp1.m_p.thick * envDirL1 - cp0.m_p.thick * envDirL0)),

		fabs(envDirR0 * (diff + cp1.m_p.thick * envDirR1 - cp0.m_p.thick * envDirR0)));

	if (d > m_pixSize &&

		cp1.m_t - cp0.m_t > 1e-4) {

		double midT = 0.5 * (cp0.m_t + cp1.m_t);

		CenterlinePoint midPoint(cp0.m_chunkIdx, midT);

		midPoint.buildPos(*this->m_stroke);

		midPoint.buildDirs(*this->m_stroke);

		subdivide(cPoints, cp0, midPoint);

		subdivide(cPoints, midPoint, cp1);

		cPoints.push_back(midPoint);

	}

}

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

class CoverageLinearizator : public tellipticbrush::StrokeLinearizator

{

public:

	CoverageLinearizator(const TStroke *stroke)

		: StrokeLinearizator(stroke) {}

	void linearize(std::vector<centerlinepoint> &cPoints, int chunk);</centerlinepoint>

};

//--------------------------------------------------------------------------------------------

void CoverageLinearizator::linearize(std::vector<centerlinepoint> &cPoints, int chunk)</centerlinepoint>

{

	//Retrieve the at max 2 parameters for which:

	//    sq(d.x) + sq(d.y) == sq(d.thick) + tolPar(*)     (ie, "self-coverage" critical points)

	//It can be rewritten in the canonical form:    at^2 + bt + c == 0

	const TThickQuadratic &ttq(*this->m_stroke->getChunk(chunk));

	TThickPoint P0(ttq.getThickP0()), P1(ttq.getThickP1()), P2(ttq.getThickP2());

	if ((P0 == P1) || (P1 == P2))

		return; //Linear speed out/in case. Straighted up in the buildDirs()

	//Remember that d = 2 [P1 - P0 + t (P0 + P2 - 2 P1)]

	T3DPointD u(P1.x - P0.x, P1.y - P0.y, P1.thick - P0.thick);

	T3DPointD v(P0.x + P2.x - 2.0 * P1.x, P0.y + P2.y - 2.0 * P1.y, P0.thick + P2.thick - 2.0 * P1.thick);

	double a = sq(v.x) + sq(v.y) - sq(v.z);

	if (fabs(a) < 1e-4)

		return; //Little (acceleration) quadratics case

	//(*) Build tolerance - 2.0 since tolPar is already used to discriminate 'good' dirs. Ours must be.

	const double twiceTolPar = 2.0 * tolPar;

	double b = 2.0 * (u.x * v.x + u.y * v.y - u.z * v.z);

	double c = sq(u.x) + sq(u.y) - sq(u.z) - twiceTolPar;

	double delta = sq(b) - 4.0 * a * c;

	if (delta < 0)

		return;

	double sqrtDelta = sqrt(delta);

	double t0 = (-b - sqrtDelta) / (2.0 * a);

	double t1 = (-b + sqrtDelta) / (2.0 * a);

	if (t0 > 0 && t0 < 1) {

		CenterlinePoint cp(chunk, t0);

		cp.buildPos(*this->m_stroke);

		cp.buildDirs(*this->m_stroke);

		cp.m_hasNextD = false;

		cPoints.push_back(cp);

	}

	if (t1 > 0 && t1 < 1) {

		CenterlinePoint cp(chunk, t1);

		cp.buildPos(*this->m_stroke);

		cp.buildDirs(*this->m_stroke);

		cp.m_hasPrevD = false;

		cPoints.push_back(cp);

	}

}

} //namespace

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

//    Outline Builder implementation

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

tellipticbrush::OutlineBuilder::OutlineBuilder(const OutlinizationData &data, const TStroke &stroke)

	: m_pixSize(data.m_pixSize), m_oOptions(stroke.outlineOptions()), m_lastChunk(stroke.getChunkCount() - 1)

{

	typedef TStroke::OutlineOptions OutlineOptions;

	switch (m_oOptions.m_capStyle) {

	case OutlineOptions::PROJECTING_CAP: {

		m_addBeginCap = &OutlineBuilder::addProjectingBeginCap<std::vector<toutlinepoint>>;</std::vector<toutlinepoint>

		m_addEndCap = &OutlineBuilder::addProjectingEndCap<std::vector<toutlinepoint>>;</std::vector<toutlinepoint>

		m_addBeginCap_ext = &OutlineBuilder::addProjectingBeginCap<trectd>;</trectd>

		m_addEndCap_ext = &OutlineBuilder::addProjectingEndCap<trectd>;</trectd>

		break;

	}

	case OutlineOptions::BUTT_CAP: {

		m_addBeginCap = &OutlineBuilder::addButtBeginCap;

		m_addEndCap = &OutlineBuilder::addButtEndCap;

		m_addBeginCap_ext = 0;

		m_addEndCap_ext = 0;

		break;

	}

	case OutlineOptions::ROUND_CAP:

	default:

		m_addBeginCap = &OutlineBuilder::addRoundBeginCap;

		m_addEndCap = &OutlineBuilder::addRoundEndCap;

		m_addBeginCap_ext = 0;

		m_addEndCap_ext = 0;

	};

	switch (m_oOptions.m_joinStyle) {

	case OutlineOptions::MITER_JOIN: {

		m_addSideCaps = &OutlineBuilder::addMiterSideCaps<std::vector<toutlinepoint>>;</std::vector<toutlinepoint>

		m_addSideCaps_ext = &OutlineBuilder::addMiterSideCaps<trectd>;</trectd>

		break;

	}

	case OutlineOptions::BEVEL_JOIN: {

		m_addSideCaps = &OutlineBuilder::addBevelSideCaps;

		m_addSideCaps_ext = 0;

		break;

	}

	case OutlineOptions::ROUND_JOIN:

	default:

		m_addSideCaps = &OutlineBuilder::addRoundSideCaps;

		m_addSideCaps_ext = 0;

	};

}

//------------------------------------------------------------

/*!

  Translates a CenterlinePoint instance into OutlinePoints, and

  adds them to the supplied vector container.

*/

void tellipticbrush::OutlineBuilder::buildOutlinePoints(

	std::vector<toutlinepoint> &oPoints, const CenterlinePoint &cPoint)</toutlinepoint>

{

	//If the centerline directions exist and match, just add their envelope

	//displacement directly

	if (cPoint.m_hasPrevD && cPoint.m_hasNextD &&

		cPoint.m_prevD == cPoint.m_nextD) {

		TPointD leftD, rightD;

		buildEnvelopeVector(cPoint.m_p, cPoint.m_prevD, true, leftD);

		buildEnvelopeVector(cPoint.m_p, cPoint.m_prevD, false, rightD);

		oPoints.push_back(TOutlinePoint(convert(cPoint.m_p) + rightD, cPoint.m_countIdx));

		oPoints.push_back(TOutlinePoint(convert(cPoint.m_p) + leftD, cPoint.m_countIdx));

	} else {

		//We have to add caps/joins together with the envelope displacements

		//Caps which are not at stroke ends are always imposed to be round.

		if (cPoint.m_hasPrevD) {

			if (cPoint.m_hasNextD)

				(this->*m_addSideCaps)(oPoints, cPoint);

			else if (cPoint.m_chunkIdx == m_lastChunk && cPoint.m_t == 1.0)

				(this->*m_addEndCap)(oPoints, cPoint);

			else

				addRoundEndCap(oPoints, cPoint);

		} else {

			if (cPoint.m_hasNextD)

				if (cPoint.m_chunkIdx == 0 && cPoint.m_t == 0.0)

					(this->*m_addBeginCap)(oPoints, cPoint);

				else

					addRoundBeginCap(oPoints, cPoint);

			else

				addCircle(oPoints, cPoint);

		}

	}

}

//------------------------------------------------------------

/*!

  Translates a CenterlinePoint instance into bounding box points,

  and adds them to the supplied (bbox) rect.

*/

void tellipticbrush::OutlineBuilder::buildOutlineExtensions(

	TRectD &bbox, const CenterlinePoint &cPoint)

{

	if (!(cPoint.m_hasPrevD && cPoint.m_hasNextD &&

		  cPoint.m_prevD == cPoint.m_nextD)) {

		//Only non-envelope points are interesting to the bbox builder procedure

		if (cPoint.m_hasPrevD) {

			if (cPoint.m_hasNextD &&

				m_addSideCaps_ext)

				(this->*m_addSideCaps_ext)(bbox, cPoint);

			else if (cPoint.m_chunkIdx == m_lastChunk && cPoint.m_t == 1.0 &&

					 m_addEndCap_ext)

				(this->*m_addEndCap_ext)(bbox, cPoint);

		} else {

			if (cPoint.m_hasNextD)

				if (cPoint.m_chunkIdx == 0 && cPoint.m_t == 0.0 &&

					m_addBeginCap_ext)

					(this->*m_addBeginCap_ext)(bbox, cPoint);

		}

	}

}

//------------------------------------------------------------

void tellipticbrush::OutlineBuilder::addCircularArcPoints(

	int idx, std::vector<toutlinepoint> &outPoints,</toutlinepoint>

	const TPointD ¢er, const TPointD &ray, double angle, int nAngles,

	int countIdx)

{

	TPointD rotRay(ray);

	//Push the initial point without rotation

	outPoints[idx] = TOutlinePoint(center + ray, countIdx);

	idx += 2;

	//Build the rotation

	double sin_a = sin(angle); //NOTE: The 'angle' input parameter CANNOT be substituted with just cos,

	double cos_a = cos(angle); //while sin = sqrt(1.0 - sq(cos)), BECAUSE this way sin is ALWAYS > 0

	int i;

	for (i = 1; i <= nAngles; ++i, idx += 2) {

		rotRay = TPointD(

			rotRay.x * cos_a - rotRay.y * sin_a,

			rotRay.x * sin_a + rotRay.y * cos_a);

		outPoints[idx] = center + rotRay;

	}

}

//------------------------------------------------------------

void tellipticbrush::OutlineBuilder::addCircle(

	std::vector<toutlinepoint> &oPoints, const CenterlinePoint &cPoint)</toutlinepoint>

{

	//Build the angle step for (0, pi)

	int nAngles;

	double stepAngle, totAngle = angle(TPointD(1.0, 0.0), TPointD(-1.0, 0.0));

	buildAngularSubdivision(cPoint.m_p.thick, totAngle, m_pixSize, nAngles);

	stepAngle = totAngle / (double)nAngles;

	//Resize the vector to store the required points

	int idx = oPoints.size();

	oPoints.resize(oPoints.size() + 2 * (nAngles + 1), TOutlinePoint(TPointD()));

	//Add the circle points from each semi-circle

	addCircularArcPoints(idx, oPoints,

						 convert(cPoint.m_p), TPointD(cPoint.m_p.thick, 0.0),

						 -stepAngle, nAngles, cPoint.m_countIdx);

	addCircularArcPoints(idx + 1, oPoints,

						 convert(cPoint.m_p), TPointD(cPoint.m_p.thick, 0.0),

						 stepAngle, nAngles, cPoint.m_countIdx);

}

//------------------------------------------------------------

void tellipticbrush::OutlineBuilder::addRoundBeginCap(

	std::vector<toutlinepoint> &oPoints, const CenterlinePoint &cPoint)</toutlinepoint>

{

	TPointD rightD;

	buildEnvelopeVector(cPoint.m_p, cPoint.m_nextD, false, rightD);

	TPointD beginD(-convert(cPoint.m_nextD));

	beginD = (cPoint.m_p.thick / norm(beginD)) * beginD;

	int nAngles;

	double stepAngle, totAngle = angle(beginD, rightD);

	buildAngularSubdivision(cPoint.m_p.thick, totAngle, m_pixSize, nAngles);

	stepAngle = totAngle / (double)nAngles;

	int idx = oPoints.size();

	oPoints.resize(oPoints.size() + 2 * (nAngles + 1), TOutlinePoint(TPointD()));

	addCircularArcPoints(idx, oPoints,

						 convert(cPoint.m_p), beginD,

						 stepAngle, nAngles, cPoint.m_countIdx);

	addCircularArcPoints(idx + 1, oPoints,

						 convert(cPoint.m_p), beginD,

						 -stepAngle, nAngles, cPoint.m_countIdx); //we just need to take the opposite angle to deal with left side

}

//------------------------------------------------------------

void tellipticbrush::OutlineBuilder::addRoundEndCap(

	std::vector<toutlinepoint> &oPoints, const CenterlinePoint &cPoint)</toutlinepoint>

{

	//Build the backward envelope directions

	//Note that the situation is specular on the left and right side...

	TPointD leftD, rightD;

	buildEnvelopeVector(cPoint.m_p, cPoint.m_prevD, true, leftD);

	buildEnvelopeVector(cPoint.m_p, cPoint.m_prevD, false, rightD);

	int nAngles;

	double stepAngle, totAngle = angle(rightD, convert(cPoint.m_prevD));

	buildAngularSubdivision(cPoint.m_p.thick, totAngle, m_pixSize, nAngles);

	stepAngle = totAngle / (double)nAngles;

	int idx = oPoints.size();

	oPoints.resize(oPoints.size() + 2 * (nAngles + 1), TOutlinePoint(TPointD()));

	addCircularArcPoints(idx, oPoints,

						 convert(cPoint.m_p), rightD,

						 stepAngle, nAngles, cPoint.m_countIdx);

	addCircularArcPoints(idx + 1, oPoints,

						 convert(cPoint.m_p), leftD,

						 -stepAngle, nAngles, cPoint.m_countIdx); //we just need to take the opposite angle to deal with left side

}

//------------------------------------------------------------

void tellipticbrush::OutlineBuilder::addButtBeginCap(

	std::vector<toutlinepoint> &oPoints, const CenterlinePoint &cPoint)</toutlinepoint>

{

	//Just add the 2 basic envelope points

	TPointD leftDNext, rightDNext;

	buildEnvelopeVectors(cPoint.m_p, cPoint.m_nextD, leftDNext, rightDNext);

	//PLUS, add their midpoint, since it generates this part of stroke antialias...

	TPointD leftP(convert(cPoint.m_p) + leftDNext), rightP(convert(cPoint.m_p) + rightDNext);

	TPointD midP(0.5 * (leftP + rightP));

	oPoints.push_back(midP);

	oPoints.push_back(midP);

	oPoints.push_back(TOutlinePoint(rightP, cPoint.m_countIdx));

	oPoints.push_back(TOutlinePoint(leftP, cPoint.m_countIdx));

}

//------------------------------------------------------------

void tellipticbrush::OutlineBuilder::addButtEndCap(

	std::vector<toutlinepoint> &oPoints, const CenterlinePoint &cPoint)</toutlinepoint>

{

	TPointD leftDPrev, rightDPrev;

	buildEnvelopeVectors(cPoint.m_p, cPoint.m_prevD, leftDPrev, rightDPrev);

	TPointD leftP(convert(cPoint.m_p) + leftDPrev), rightP(convert(cPoint.m_p) + rightDPrev);

	TPointD midP(0.5 * (leftP + rightP));

	oPoints.push_back(TOutlinePoint(convert(cPoint.m_p) + rightDPrev, cPoint.m_countIdx));

	oPoints.push_back(TOutlinePoint(convert(cPoint.m_p) + leftDPrev, cPoint.m_countIdx));

	oPoints.push_back(midP);

	oPoints.push_back(midP);

}

//------------------------------------------------------------

template <typename t=""></typename>

void tellipticbrush::OutlineBuilder::addProjectingBeginCap(

	T &oPoints, const CenterlinePoint &cPoint)

{

	double thick = cPoint.m_p.thick;

	//Find the base points

	TPointD leftDNext, rightDNext;

	buildEnvelopeDirections(cPoint.m_p, cPoint.m_nextD, leftDNext, rightDNext);

	TPointD leftP(convert(cPoint.m_p) + thick * leftDNext);

	TPointD rightP(convert(cPoint.m_p) + thick * rightDNext);

	//Add the intersections between the envelope directions' orthogonals and the

	//direction orthogonals

	TPointD dir(normalize(-cPoint.m_nextD));

	TPointD dirP(convert(cPoint.m_p) + thick * dir);

	TPointD cornerLCoords = intersectionCoords(

		dirP, TPointD(dir.y, -dir.x), leftP, TPointD(-leftDNext.y, leftDNext.x));

	TPointD cornerRCoords = intersectionCoords(

		dirP, TPointD(-dir.y, dir.x), rightP, TPointD(rightDNext.y, -rightDNext.x));

	if (cornerLCoords.x < 0 || cornerRCoords.y < 0)

		return;

	//As before, midPoints must be added due to antialias

	TPointD cornerL(dirP + cornerLCoords.x * TPointD(dir.y, -dir.x));

	TPointD cornerR(dirP + cornerRCoords.x * TPointD(-dir.y, dir.x));

	TPointD midP(0.5 * (cornerL + cornerR));

	addEnvelopePoint(oPoints, midP);

	addEnvelopePoint(oPoints, midP);

	addExtensionPoint(oPoints, cornerR);

	addExtensionPoint(oPoints, cornerL);

	//Initial points must be added later, in the begin case

	addEnvelopePoint(oPoints, rightP, cPoint.m_countIdx);

	addEnvelopePoint(oPoints, leftP, cPoint.m_countIdx);

}

//------------------------------------------------------------

template <typename t=""></typename>

void tellipticbrush::OutlineBuilder::addProjectingEndCap(

	T &oPoints, const CenterlinePoint &cPoint)

{

	double thick = cPoint.m_p.thick;

	//Add the base points

	TPointD leftDPrev, rightDPrev;

	buildEnvelopeDirections(cPoint.m_p, cPoint.m_prevD, leftDPrev, rightDPrev);

	TPointD leftP(convert(cPoint.m_p) + thick * leftDPrev);

	TPointD rightP(convert(cPoint.m_p) + thick * rightDPrev);

	addEnvelopePoint(oPoints, rightP, cPoint.m_countIdx);

	addEnvelopePoint(oPoints, leftP, cPoint.m_countIdx);

	//Add the intersections between the envelope directions' orthogonals and the

	//direction orthogonals

	TPointD dir(normalize(cPoint.m_prevD));

	TPointD dirP(convert(cPoint.m_p) + thick * dir);

	TPointD cornerLCoords = intersectionCoords(

		dirP, TPointD(-dir.y, dir.x), leftP, TPointD(leftDPrev.y, -leftDPrev.x));

	TPointD cornerRCoords = intersectionCoords(

		dirP, TPointD(dir.y, -dir.x), rightP, TPointD(-rightDPrev.y, rightDPrev.x));

	if (cornerLCoords.x < 0 || cornerRCoords.y < 0)

		return;

	TPointD cornerL(dirP + cornerLCoords.x * TPointD(-dir.y, dir.x));

	TPointD cornerR(dirP + cornerRCoords.x * TPointD(dir.y, -dir.x));

	TPointD midP(0.5 * (cornerL + cornerR));

	addExtensionPoint(oPoints, cornerR);

	addExtensionPoint(oPoints, cornerL);

	addEnvelopePoint(oPoints, midP);

	addEnvelopePoint(oPoints, midP);

}

//------------------------------------------------------------

void tellipticbrush::OutlineBuilder::addRoundSideCaps(

	std::vector<toutlinepoint> &oPoints, const CenterlinePoint &cPoint)</toutlinepoint>