SubdivideBezier

SubdivideBezier.cpp

void Painter::SubdivideBezier(std::list<Vector2>& points,
		const std::list<Vector2>::iterator& start)
{
	auto curPt = start;

	Vector2 p1 = *curPt;
	auto p2Iter = ++curPt;
	Vector2 p2 = *curPt;
	auto p3Iter = ++curPt;
	Vector2 p3 = *curPt;
	auto p4Iter = ++curPt;
	Vector2 p4 = *curPt;

	//Calculate the new control points. l1, l2 are for the left subcurve, r1, r2 are for the right subcurve
	Vector2 l1 = (p1 + p2) / 2.;
	Vector2 h = (p2 + p3) / 2.;
	Vector2 r2 = (p3 + p4) / 2.;
	Vector2 l2 = (l1 + h) / 2.;
	Vector2 r1 = (h + r2) / 2.;
	Vector2 center = (l2 + r1) / 2;

	//Old control points are not needed
	points.erase(p2Iter);
	points.erase(p3Iter);

	//Add the new ones
	points.insert(p4Iter, {l1, l2, center, r1, r2});
	auto curveTwoIter = start;
	++curveTwoIter;
	++curveTwoIter;
	++curveTwoIter;
	//Compute the deviance from a straight line for the first subcurve.
	Vector2 g1 = (center - p1);
	Vector2 c11 = (l1 - p1);
	Vector2 c21 = (l2 - p1);
	double error11 = -c11.x * g1.y + c11.y * g1.x;
	double error21 = -c21.x * g1.y + c21.y * g1.x;
	double maxErrorSub1 = std::max(std::abs(error11), std::abs(error21));

	if(maxErrorSub1 > m_bezierMaxFlatnessError)
	{
		SubdivideBezier(points, start);
	}

	//Compute the deviance from a straight line for the second subcurve.
	Vector2 g2 = (center - p1);
	Vector2 c12 = (l1 - p1);
	Vector2 c22 = (l2 - p1);
	double error12 = -c12.x * g2.y + c12.y * g2.x;
	double error22 = -c22.x * g2.y + c22.y * g2.x;
	double maxErrorSub2 = std::max(std::abs(error12), std::abs(error22));

	if(maxErrorSub2 > m_bezierMaxFlatnessError)
	{
		SubdivideBezier(points, curveTwoIter);
	}
}