gfx/skia/skia/src/pathops/SkReduceOrder.cpp
 author Lee Salzman Tue, 09 Feb 2016 13:38:06 -0500 changeset 283658 159e0a5a653f2789e0c9b94f41501a4a44f7cb34 parent 276967 a3503094c48d771e020f34f35b8945cd525d40e8 child 319205 1ed742f88f492a503afcef0779522dadda7985ac permissions -rw-r--r--
Bug 1246756 - part 3 - update Skia to m49 branch. r=jrmuizel

/*
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "SkReduceOrder.h"

int SkReduceOrder::reduce(const SkDLine& line) {
fLine = line;
int different = line != line;
fLine = line[different];
return 1 + different;
}

reduction = reduction = quad;
return 1;
}

static int reductionLineCount(const SkDQuad& reduction) {
return 1 + !reduction.approximatelyEqual(reduction);
}

return reductionLineCount(reduction);
}

return reductionLineCount(reduction);
}

int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
if (!quad.isLinear(0, 2)) {
return 0;
}
// four are colinear: return line formed by outside
return reductionLineCount(reduction);
}

// reduce to a quadratic or smaller
// look for identical points
// look for all four points in a line
// note that three points in a line doesn't simplify a cubic
// look for approximation with single quadratic
// save approximation with multiple quadratics for later
int index, minX, maxX, minY, maxY;
int minXSet, minYSet;
minX = maxX = minY = maxY = 0;
minXSet = minYSet = 0;
for (index = 1; index < 3; ++index) {
minX = index;
}
minY = index;
}
maxX = index;
}
maxY = index;
}
}
for (index = 0; index < 3; ++index) {
minXSet |= 1 << index;
}
minYSet |= 1 << index;
}
}
if (minXSet == 0x7) {  // test for vertical line
if (minYSet == 0x7) {  // return 1 if all three are coincident
}
}
if (minYSet == 0x7) {  // test for horizontal line
}
int result = check_linear(quad, minX, maxX, minY, maxY, fQuad);
if (result) {
return result;
}
return 3;
}

////////////////////////////////////////////////////////////////////////////////////

static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) {
reduction = reduction = cubic;
return 1;
}

static int reductionLineCount(const SkDCubic& reduction) {
return 1 + !reduction.approximatelyEqual(reduction);
}

static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) {
reduction = cubic;
reduction = cubic;
return reductionLineCount(reduction);
}

static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) {
reduction = cubic;
reduction = cubic;
return reductionLineCount(reduction);
}

// check to see if it is a quadratic or a line
static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
double dx10 = cubic.fX - cubic.fX;
double dx23 = cubic.fX - cubic.fX;
double midX = cubic.fX + dx10 * 3 / 2;
double sideAx = midX - cubic.fX;
double sideBx = dx23 * 3 / 2;
if (approximately_zero(sideAx) ? !approximately_equal(sideAx, sideBx)
: !AlmostEqualUlps_Pin(sideAx, sideBx)) {
return 0;
}
double dy10 = cubic.fY - cubic.fY;
double dy23 = cubic.fY - cubic.fY;
double midY = cubic.fY + dy10 * 3 / 2;
double sideAy = midY - cubic.fY;
double sideBy = dy23 * 3 / 2;
if (approximately_zero(sideAy) ? !approximately_equal(sideAy, sideBy)
: !AlmostEqualUlps_Pin(sideAy, sideBy)) {
return 0;
}
reduction = cubic;
reduction.fX = midX;
reduction.fY = midY;
reduction = cubic;
return 3;
}

static int check_linear(const SkDCubic& cubic,
int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
if (!cubic.isLinear(0, 3)) {
return 0;
}
// four are colinear: return line formed by outside
reduction = cubic;
reduction = cubic;
return reductionLineCount(reduction);
}

/* food for thought:

Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the
corresponding quadratic Bezier are (given in convex combinations of
points):

q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4
q2 = -c1 + (3/2)c2 + (3/2)c3 - c4
q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4

Of course, this curve does not interpolate the end-points, but it would
be interesting to see the behaviour of such a curve in an applet.

--
Kalle Rutanen
http://kaba.hilvi.org

*/

// reduce to a quadratic or smaller
// look for identical points
// look for all four points in a line
// note that three points in a line doesn't simplify a cubic
// look for approximation with single quadratic
// save approximation with multiple quadratics for later
int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) {
int index, minX, maxX, minY, maxY;
int minXSet, minYSet;
minX = maxX = minY = maxY = 0;
minXSet = minYSet = 0;
for (index = 1; index < 4; ++index) {
if (cubic[minX].fX > cubic[index].fX) {
minX = index;
}
if (cubic[minY].fY > cubic[index].fY) {
minY = index;
}
if (cubic[maxX].fX < cubic[index].fX) {
maxX = index;
}
if (cubic[maxY].fY < cubic[index].fY) {
maxY = index;
}
}
for (index = 0; index < 4; ++index) {
double cx = cubic[index].fX;
double cy = cubic[index].fY;
double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY))));
if (denom == 0) {
minXSet |= 1 << index;
minYSet |= 1 << index;
continue;
}
double inv = 1 / denom;
if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) {
minXSet |= 1 << index;
}
if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) {
minYSet |= 1 << index;
}
}
if (minXSet == 0xF) {  // test for vertical line
if (minYSet == 0xF) {  // return 1 if all four are coincident
return coincident_line(cubic, fCubic);
}
return vertical_line(cubic, fCubic);
}
if (minYSet == 0xF) {  // test for horizontal line
return horizontal_line(cubic, fCubic);
}
int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic);
if (result) {
return result;
}
&& (result = check_quadratic(cubic, fCubic))) {
return result;
}
fCubic = cubic;
return 4;
}

SkPath::Verb SkReduceOrder::Quad(const SkPoint a, SkPoint* reducePts) {
SkReduceOrder reducer;
int order = reducer.reduce(quad);
if (order == 2) {  // quad became line
for (int index = 0; index < order; ++index) {
*reducePts++ = reducer.fLine[index].asSkPoint();
}
}
return SkPathOpsPointsToVerb(order - 1);
}

SkPath::Verb SkReduceOrder::Conic(const SkPoint a, SkScalar weight, SkPoint* reducePts) {
SkPath::Verb verb = SkReduceOrder::Quad(a, reducePts);
if (verb > SkPath::kLine_Verb && weight == 1) {
}
return verb == SkPath::kQuad_Verb ? SkPath::kConic_Verb : verb;
}

SkPath::Verb SkReduceOrder::Cubic(const SkPoint a, SkPoint* reducePts) {
if (SkDPoint::ApproximatelyEqual(a, a) && SkDPoint::ApproximatelyEqual(a, a)
&& SkDPoint::ApproximatelyEqual(a, a)) {
reducePts = a;
return SkPath::kMove_Verb;
}
SkDCubic cubic;
cubic.set(a);
SkReduceOrder reducer;
int order = reducer.reduce(cubic, kAllow_Quadratics);
if (order == 2 || order == 3) {  // cubic became line or quad
for (int index = 0; index < order; ++index) {