| /* |
| * 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); |
| } |
