diff options
author | Baligh Uddin <baligh@google.com> | 2013-11-01 16:01:55 -0700 |
---|---|---|
committer | Baligh Uddin <baligh@google.com> | 2013-11-01 16:01:55 -0700 |
commit | ec502fb532582da0f3141560bc451df3902ce463 (patch) | |
tree | bfd8e692b73dee4749734ca317b4707988dfae3a /pathops/SkReduceOrder.cpp | |
parent | 5588ded0ae11d6fa36e1771747b82b7831db906b (diff) | |
parent | 53a521c76400a3e6d64dc96396390b746ec1e48e (diff) | |
download | src-ec502fb532582da0f3141560bc451df3902ce463.tar.gz |
Merge remote-tracking branch 'origin/kitkat-dev'chromium_org-pre-replicationidea133
Diffstat (limited to 'pathops/SkReduceOrder.cpp')
-rw-r--r-- | pathops/SkReduceOrder.cpp | 452 |
1 files changed, 452 insertions, 0 deletions
diff --git a/pathops/SkReduceOrder.cpp b/pathops/SkReduceOrder.cpp new file mode 100644 index 00000000..3dfdc9da --- /dev/null +++ b/pathops/SkReduceOrder.cpp @@ -0,0 +1,452 @@ +/* + * Copyright 2012 Google Inc. + * + * 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[0] = line[0]; + int different = line[0] != line[1]; + fLine[1] = line[different]; + return 1 + different; +} + +static double interp_quad_coords(double a, double b, double c, double t) { + double ab = SkDInterp(a, b, t); + double bc = SkDInterp(b, c, t); + return SkDInterp(ab, bc, t); +} + +static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) { + reduction[0] = reduction[1] = quad[0]; + return 1; +} + +static int reductionLineCount(const SkDQuad& reduction) { + return 1 + !reduction[0].approximatelyEqual(reduction[1]); +} + +static int vertical_line(const SkDQuad& quad, SkReduceOrder::Style reduceStyle, + SkDQuad& reduction) { + double tValue; + reduction[0] = quad[0]; + reduction[1] = quad[2]; + if (reduceStyle == SkReduceOrder::kFill_Style) { + return reductionLineCount(reduction); + } + int smaller = reduction[1].fY > reduction[0].fY; + int larger = smaller ^ 1; + if (SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValue)) { + double yExtrema = interp_quad_coords(quad[0].fY, quad[1].fY, quad[2].fY, tValue); + if (reduction[smaller].fY > yExtrema) { + reduction[smaller].fY = yExtrema; + } else if (reduction[larger].fY < yExtrema) { + reduction[larger].fY = yExtrema; + } + } + return reductionLineCount(reduction); +} + +static int horizontal_line(const SkDQuad& quad, SkReduceOrder::Style reduceStyle, + SkDQuad& reduction) { + double tValue; + reduction[0] = quad[0]; + reduction[1] = quad[2]; + if (reduceStyle == SkReduceOrder::kFill_Style) { + return reductionLineCount(reduction); + } + int smaller = reduction[1].fX > reduction[0].fX; + int larger = smaller ^ 1; + if (SkDQuad::FindExtrema(quad[0].fX, quad[1].fX, quad[2].fX, &tValue)) { + double xExtrema = interp_quad_coords(quad[0].fX, quad[1].fX, quad[2].fX, tValue); + if (reduction[smaller].fX > xExtrema) { + reduction[smaller].fX = xExtrema; + } else if (reduction[larger].fX < xExtrema) { + reduction[larger].fX = xExtrema; + } + } + return reductionLineCount(reduction); +} + +static int check_linear(const SkDQuad& quad, SkReduceOrder::Style reduceStyle, + int minX, int maxX, int minY, int maxY, SkDQuad& reduction) { + int startIndex = 0; + int endIndex = 2; + while (quad[startIndex].approximatelyEqual(quad[endIndex])) { + --endIndex; + if (endIndex == 0) { + SkDebugf("%s shouldn't get here if all four points are about equal", __FUNCTION__); + SkASSERT(0); + } + } + if (!quad.isLinear(startIndex, endIndex)) { + return 0; + } + // four are colinear: return line formed by outside + reduction[0] = quad[0]; + reduction[1] = quad[2]; + if (reduceStyle == SkReduceOrder::kFill_Style) { + return reductionLineCount(reduction); + } + int sameSide; + bool useX = quad[maxX].fX - quad[minX].fX >= quad[maxY].fY - quad[minY].fY; + if (useX) { + sameSide = SkDSign(quad[0].fX - quad[1].fX) + SkDSign(quad[2].fX - quad[1].fX); + } else { + sameSide = SkDSign(quad[0].fY - quad[1].fY) + SkDSign(quad[2].fY - quad[1].fY); + } + if ((sameSide & 3) != 2) { + return reductionLineCount(reduction); + } + double tValue; + int root; + if (useX) { + root = SkDQuad::FindExtrema(quad[0].fX, quad[1].fX, quad[2].fX, &tValue); + } else { + root = SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValue); + } + if (root) { + SkDPoint extrema; + extrema.fX = interp_quad_coords(quad[0].fX, quad[1].fX, quad[2].fX, tValue); + extrema.fY = interp_quad_coords(quad[0].fY, quad[1].fY, quad[2].fY, tValue); + // sameSide > 0 means mid is smaller than either [0] or [2], so replace smaller + int replace; + if (useX) { + if ((extrema.fX < quad[0].fX) ^ (extrema.fX < quad[2].fX)) { + return reductionLineCount(reduction); + } + replace = ((extrema.fX < quad[0].fX) | (extrema.fX < quad[2].fX)) + ^ (quad[0].fX < quad[2].fX); + } else { + if ((extrema.fY < quad[0].fY) ^ (extrema.fY < quad[2].fY)) { + return reductionLineCount(reduction); + } + replace = ((extrema.fY < quad[0].fY) | (extrema.fY < quad[2].fY)) + ^ (quad[0].fY < quad[2].fY); + } + reduction[replace] = extrema; + } + 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 SkReduceOrder::reduce(const SkDQuad& quad, Style reduceStyle) { + int index, minX, maxX, minY, maxY; + int minXSet, minYSet; + minX = maxX = minY = maxY = 0; + minXSet = minYSet = 0; + for (index = 1; index < 3; ++index) { + if (quad[minX].fX > quad[index].fX) { + minX = index; + } + if (quad[minY].fY > quad[index].fY) { + minY = index; + } + if (quad[maxX].fX < quad[index].fX) { + maxX = index; + } + if (quad[maxY].fY < quad[index].fY) { + maxY = index; + } + } + for (index = 0; index < 3; ++index) { + if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) { + minXSet |= 1 << index; + } + if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) { + minYSet |= 1 << index; + } + } + if (minXSet == 0x7) { // test for vertical line + if (minYSet == 0x7) { // return 1 if all four are coincident + return coincident_line(quad, fQuad); + } + return vertical_line(quad, reduceStyle, fQuad); + } + if (minYSet == 0xF) { // test for horizontal line + return horizontal_line(quad, reduceStyle, fQuad); + } + int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, fQuad); + if (result) { + return result; + } + fQuad = quad; + return 3; +} + +//////////////////////////////////////////////////////////////////////////////////// + +static double interp_cubic_coords(const double* src, double t) { + double ab = SkDInterp(src[0], src[2], t); + double bc = SkDInterp(src[2], src[4], t); + double cd = SkDInterp(src[4], src[6], t); + double abc = SkDInterp(ab, bc, t); + double bcd = SkDInterp(bc, cd, t); + return SkDInterp(abc, bcd, t); +} + +static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) { + reduction[0] = reduction[1] = cubic[0]; + return 1; +} + +static int reductionLineCount(const SkDCubic& reduction) { + return 1 + !reduction[0].approximatelyEqual(reduction[1]); +} + +static int vertical_line(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle, + SkDCubic& reduction) { + double tValues[2]; + reduction[0] = cubic[0]; + reduction[1] = cubic[3]; + if (reduceStyle == SkReduceOrder::kFill_Style) { + return reductionLineCount(reduction); + } + int smaller = reduction[1].fY > reduction[0].fY; + int larger = smaller ^ 1; + int roots = SkDCubic::FindExtrema(cubic[0].fY, cubic[1].fY, cubic[2].fY, cubic[3].fY, tValues); + for (int index = 0; index < roots; ++index) { + double yExtrema = interp_cubic_coords(&cubic[0].fY, tValues[index]); + if (reduction[smaller].fY > yExtrema) { + reduction[smaller].fY = yExtrema; + continue; + } + if (reduction[larger].fY < yExtrema) { + reduction[larger].fY = yExtrema; + } + } + return reductionLineCount(reduction); +} + +static int horizontal_line(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle, + SkDCubic& reduction) { + double tValues[2]; + reduction[0] = cubic[0]; + reduction[1] = cubic[3]; + if (reduceStyle == SkReduceOrder::kFill_Style) { + return reductionLineCount(reduction); + } + int smaller = reduction[1].fX > reduction[0].fX; + int larger = smaller ^ 1; + int roots = SkDCubic::FindExtrema(cubic[0].fX, cubic[1].fX, cubic[2].fX, cubic[3].fX, tValues); + for (int index = 0; index < roots; ++index) { + double xExtrema = interp_cubic_coords(&cubic[0].fX, tValues[index]); + if (reduction[smaller].fX > xExtrema) { + reduction[smaller].fX = xExtrema; + continue; + } + if (reduction[larger].fX < xExtrema) { + reduction[larger].fX = xExtrema; + } + } + 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[1].fX - cubic[0].fX; + double dx23 = cubic[2].fX - cubic[3].fX; + double midX = cubic[0].fX + dx10 * 3 / 2; + double sideAx = midX - cubic[3].fX; + double sideBx = dx23 * 3 / 2; + if (approximately_zero(sideAx) ? !approximately_equal(sideAx, sideBx) + : !AlmostEqualUlps(sideAx, sideBx)) { + return 0; + } + double dy10 = cubic[1].fY - cubic[0].fY; + double dy23 = cubic[2].fY - cubic[3].fY; + double midY = cubic[0].fY + dy10 * 3 / 2; + double sideAy = midY - cubic[3].fY; + double sideBy = dy23 * 3 / 2; + if (approximately_zero(sideAy) ? !approximately_equal(sideAy, sideBy) + : !AlmostEqualUlps(sideAy, sideBy)) { + return 0; + } + reduction[0] = cubic[0]; + reduction[1].fX = midX; + reduction[1].fY = midY; + reduction[2] = cubic[3]; + return 3; +} + +static int check_linear(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle, + int minX, int maxX, int minY, int maxY, SkDCubic& reduction) { + int startIndex = 0; + int endIndex = 3; + while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) { + --endIndex; + if (endIndex == 0) { + SkDebugf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__); + SkASSERT(0); + } + } + if (!cubic.isLinear(startIndex, endIndex)) { + return 0; + } + // four are colinear: return line formed by outside + reduction[0] = cubic[0]; + reduction[1] = cubic[3]; + if (reduceStyle == SkReduceOrder::kFill_Style) { + return reductionLineCount(reduction); + } + int sameSide1; + int sameSide2; + bool useX = cubic[maxX].fX - cubic[minX].fX >= cubic[maxY].fY - cubic[minY].fY; + if (useX) { + sameSide1 = SkDSign(cubic[0].fX - cubic[1].fX) + SkDSign(cubic[3].fX - cubic[1].fX); + sameSide2 = SkDSign(cubic[0].fX - cubic[2].fX) + SkDSign(cubic[3].fX - cubic[2].fX); + } else { + sameSide1 = SkDSign(cubic[0].fY - cubic[1].fY) + SkDSign(cubic[3].fY - cubic[1].fY); + sameSide2 = SkDSign(cubic[0].fY - cubic[2].fY) + SkDSign(cubic[3].fY - cubic[2].fY); + } + if (sameSide1 == sameSide2 && (sameSide1 & 3) != 2) { + return reductionLineCount(reduction); + } + double tValues[2]; + int roots; + if (useX) { + roots = SkDCubic::FindExtrema(cubic[0].fX, cubic[1].fX, cubic[2].fX, cubic[3].fX, tValues); + } else { + roots = SkDCubic::FindExtrema(cubic[0].fY, cubic[1].fY, cubic[2].fY, cubic[3].fY, tValues); + } + for (int index = 0; index < roots; ++index) { + SkDPoint extrema; + extrema.fX = interp_cubic_coords(&cubic[0].fX, tValues[index]); + extrema.fY = interp_cubic_coords(&cubic[0].fY, tValues[index]); + // sameSide > 0 means mid is smaller than either [0] or [3], so replace smaller + int replace; + if (useX) { + if ((extrema.fX < cubic[0].fX) ^ (extrema.fX < cubic[3].fX)) { + continue; + } + replace = ((extrema.fX < cubic[0].fX) | (extrema.fX < cubic[3].fX)) + ^ (cubic[0].fX < cubic[3].fX); + } else { + if ((extrema.fY < cubic[0].fY) ^ (extrema.fY < cubic[3].fY)) { + continue; + } + replace = ((extrema.fY < cubic[0].fY) | (extrema.fY < cubic[3].fY)) + ^ (cubic[0].fY < cubic[3].fY); + } + reduction[replace] = extrema; + } + return reductionLineCount(reduction); +} + +/* food for thought: +http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html + +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, + Style reduceStyle) { + 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, reduceStyle, fCubic); + } + if (minYSet == 0xF) { // test for horizontal line + return horizontal_line(cubic, reduceStyle, fCubic); + } + int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, fCubic); + if (result) { + return result; + } + if (allowQuadratics == SkReduceOrder::kAllow_Quadratics + && (result = check_quadratic(cubic, fCubic))) { + return result; + } + fCubic = cubic; + return 4; +} + +SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) { + SkDQuad quad; + quad.set(a); + SkReduceOrder reducer; + int order = reducer.reduce(quad, kFill_Style); + 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::Cubic(const SkPoint a[4], SkPoint* reducePts) { + SkDCubic cubic; + cubic.set(a); + SkReduceOrder reducer; + int order = reducer.reduce(cubic, kAllow_Quadratics, kFill_Style); + if (order == 2 || order == 3) { // cubic became line or quad + for (int index = 0; index < order; ++index) { + *reducePts++ = reducer.fQuad[index].asSkPoint(); + } + } + return SkPathOpsPointsToVerb(order - 1); +} |