michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkReduceOrder.h"
michael@0: 
michael@0: int SkReduceOrder::reduce(const SkDLine& line) {
michael@0:     fLine[0] = line[0];
michael@0:     int different = line[0] != line[1];
michael@0:     fLine[1] = line[different];
michael@0:     return 1 + different;
michael@0: }
michael@0: 
michael@0: static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) {
michael@0:     reduction[0] = reduction[1] = quad[0];
michael@0:     return 1;
michael@0: }
michael@0: 
michael@0: static int reductionLineCount(const SkDQuad& reduction) {
michael@0:     return 1 + !reduction[0].approximatelyEqual(reduction[1]);
michael@0: }
michael@0: 
michael@0: static int vertical_line(const SkDQuad& quad, SkDQuad& reduction) {
michael@0:     reduction[0] = quad[0];
michael@0:     reduction[1] = quad[2];
michael@0:     return reductionLineCount(reduction);
michael@0: }
michael@0: 
michael@0: static int horizontal_line(const SkDQuad& quad, SkDQuad& reduction) {
michael@0:     reduction[0] = quad[0];
michael@0:     reduction[1] = quad[2];
michael@0:     return reductionLineCount(reduction);
michael@0: }
michael@0: 
michael@0: static int check_linear(const SkDQuad& quad,
michael@0:         int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
michael@0:     int startIndex = 0;
michael@0:     int endIndex = 2;
michael@0:     while (quad[startIndex].approximatelyEqual(quad[endIndex])) {
michael@0:         --endIndex;
michael@0:         if (endIndex == 0) {
michael@0:             SkDebugf("%s shouldn't get here if all four points are about equal", __FUNCTION__);
michael@0:             SkASSERT(0);
michael@0:         }
michael@0:     }
michael@0:     if (!quad.isLinear(startIndex, endIndex)) {
michael@0:         return 0;
michael@0:     }
michael@0:     // four are colinear: return line formed by outside
michael@0:     reduction[0] = quad[0];
michael@0:     reduction[1] = quad[2];
michael@0:     return reductionLineCount(reduction);
michael@0: }
michael@0: 
michael@0: // reduce to a quadratic or smaller
michael@0: // look for identical points
michael@0: // look for all four points in a line
michael@0:     // note that three points in a line doesn't simplify a cubic
michael@0: // look for approximation with single quadratic
michael@0:     // save approximation with multiple quadratics for later
michael@0: int SkReduceOrder::reduce(const SkDQuad& quad) {
michael@0:     int index, minX, maxX, minY, maxY;
michael@0:     int minXSet, minYSet;
michael@0:     minX = maxX = minY = maxY = 0;
michael@0:     minXSet = minYSet = 0;
michael@0:     for (index = 1; index < 3; ++index) {
michael@0:         if (quad[minX].fX > quad[index].fX) {
michael@0:             minX = index;
michael@0:         }
michael@0:         if (quad[minY].fY > quad[index].fY) {
michael@0:             minY = index;
michael@0:         }
michael@0:         if (quad[maxX].fX < quad[index].fX) {
michael@0:             maxX = index;
michael@0:         }
michael@0:         if (quad[maxY].fY < quad[index].fY) {
michael@0:             maxY = index;
michael@0:         }
michael@0:     }
michael@0:     for (index = 0; index < 3; ++index) {
michael@0:         if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) {
michael@0:             minXSet |= 1 << index;
michael@0:         }
michael@0:         if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) {
michael@0:             minYSet |= 1 << index;
michael@0:         }
michael@0:     }
michael@0:     if (minXSet == 0x7) {  // test for vertical line
michael@0:         if (minYSet == 0x7) {  // return 1 if all four are coincident
michael@0:             return coincident_line(quad, fQuad);
michael@0:         }
michael@0:         return vertical_line(quad, fQuad);
michael@0:     }
michael@0:     if (minYSet == 0xF) {  // test for horizontal line
michael@0:         return horizontal_line(quad, fQuad);
michael@0:     }
michael@0:     int result = check_linear(quad, minX, maxX, minY, maxY, fQuad);
michael@0:     if (result) {
michael@0:         return result;
michael@0:     }
michael@0:     fQuad = quad;
michael@0:     return 3;
michael@0: }
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) {
michael@0:     reduction[0] = reduction[1] = cubic[0];
michael@0:     return 1;
michael@0: }
michael@0: 
michael@0: static int reductionLineCount(const SkDCubic& reduction) {
michael@0:     return 1 + !reduction[0].approximatelyEqual(reduction[1]);
michael@0: }
michael@0: 
michael@0: static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) {
michael@0:     reduction[0] = cubic[0];
michael@0:     reduction[1] = cubic[3];
michael@0:     return reductionLineCount(reduction);
michael@0: }
michael@0: 
michael@0: static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) {
michael@0:     reduction[0] = cubic[0];
michael@0:     reduction[1] = cubic[3];
michael@0:     return reductionLineCount(reduction);
michael@0: }
michael@0: 
michael@0: // check to see if it is a quadratic or a line
michael@0: static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
michael@0:     double dx10 = cubic[1].fX - cubic[0].fX;
michael@0:     double dx23 = cubic[2].fX - cubic[3].fX;
michael@0:     double midX = cubic[0].fX + dx10 * 3 / 2;
michael@0:     double sideAx = midX - cubic[3].fX;
michael@0:     double sideBx = dx23 * 3 / 2;
michael@0:     if (approximately_zero(sideAx) ? !approximately_equal(sideAx, sideBx)
michael@0:             : !AlmostEqualUlps(sideAx, sideBx)) {
michael@0:         return 0;
michael@0:     }
michael@0:     double dy10 = cubic[1].fY - cubic[0].fY;
michael@0:     double dy23 = cubic[2].fY - cubic[3].fY;
michael@0:     double midY = cubic[0].fY + dy10 * 3 / 2;
michael@0:     double sideAy = midY - cubic[3].fY;
michael@0:     double sideBy = dy23 * 3 / 2;
michael@0:     if (approximately_zero(sideAy) ? !approximately_equal(sideAy, sideBy)
michael@0:             : !AlmostEqualUlps(sideAy, sideBy)) {
michael@0:         return 0;
michael@0:     }
michael@0:     reduction[0] = cubic[0];
michael@0:     reduction[1].fX = midX;
michael@0:     reduction[1].fY = midY;
michael@0:     reduction[2] = cubic[3];
michael@0:     return 3;
michael@0: }
michael@0: 
michael@0: static int check_linear(const SkDCubic& cubic,
michael@0:         int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
michael@0:     int startIndex = 0;
michael@0:     int endIndex = 3;
michael@0:     while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) {
michael@0:         --endIndex;
michael@0:         if (endIndex == 0) {
michael@0:             SkDebugf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__);
michael@0:             SkASSERT(0);
michael@0:         }
michael@0:     }
michael@0:     if (!cubic.isLinear(startIndex, endIndex)) {
michael@0:         return 0;
michael@0:     }
michael@0:     // four are colinear: return line formed by outside
michael@0:     reduction[0] = cubic[0];
michael@0:     reduction[1] = cubic[3];
michael@0:     return reductionLineCount(reduction);
michael@0: }
michael@0: 
michael@0: /* food for thought:
michael@0: http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html
michael@0: 
michael@0: Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the
michael@0: corresponding quadratic Bezier are (given in convex combinations of
michael@0: points):
michael@0: 
michael@0: q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4
michael@0: q2 = -c1 + (3/2)c2 + (3/2)c3 - c4
michael@0: q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4
michael@0: 
michael@0: Of course, this curve does not interpolate the end-points, but it would
michael@0: be interesting to see the behaviour of such a curve in an applet.
michael@0: 
michael@0: --
michael@0: Kalle Rutanen
michael@0: http://kaba.hilvi.org
michael@0: 
michael@0: */
michael@0: 
michael@0: // reduce to a quadratic or smaller
michael@0: // look for identical points
michael@0: // look for all four points in a line
michael@0:     // note that three points in a line doesn't simplify a cubic
michael@0: // look for approximation with single quadratic
michael@0:     // save approximation with multiple quadratics for later
michael@0: int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) {
michael@0:     int index, minX, maxX, minY, maxY;
michael@0:     int minXSet, minYSet;
michael@0:     minX = maxX = minY = maxY = 0;
michael@0:     minXSet = minYSet = 0;
michael@0:     for (index = 1; index < 4; ++index) {
michael@0:         if (cubic[minX].fX > cubic[index].fX) {
michael@0:             minX = index;
michael@0:         }
michael@0:         if (cubic[minY].fY > cubic[index].fY) {
michael@0:             minY = index;
michael@0:         }
michael@0:         if (cubic[maxX].fX < cubic[index].fX) {
michael@0:             maxX = index;
michael@0:         }
michael@0:         if (cubic[maxY].fY < cubic[index].fY) {
michael@0:             maxY = index;
michael@0:         }
michael@0:     }
michael@0:     for (index = 0; index < 4; ++index) {
michael@0:         double cx = cubic[index].fX;
michael@0:         double cy = cubic[index].fY;
michael@0:         double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
michael@0:                 SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY))));
michael@0:         if (denom == 0) {
michael@0:             minXSet |= 1 << index;
michael@0:             minYSet |= 1 << index;
michael@0:             continue;
michael@0:         }
michael@0:         double inv = 1 / denom;
michael@0:         if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) {
michael@0:             minXSet |= 1 << index;
michael@0:         }
michael@0:         if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) {
michael@0:             minYSet |= 1 << index;
michael@0:         }
michael@0:     }
michael@0:     if (minXSet == 0xF) {  // test for vertical line
michael@0:         if (minYSet == 0xF) {  // return 1 if all four are coincident
michael@0:             return coincident_line(cubic, fCubic);
michael@0:         }
michael@0:         return vertical_line(cubic, fCubic);
michael@0:     }
michael@0:     if (minYSet == 0xF) {  // test for horizontal line
michael@0:         return horizontal_line(cubic, fCubic);
michael@0:     }
michael@0:     int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic);
michael@0:     if (result) {
michael@0:         return result;
michael@0:     }
michael@0:     if (allowQuadratics == SkReduceOrder::kAllow_Quadratics
michael@0:             && (result = check_quadratic(cubic, fCubic))) {
michael@0:         return result;
michael@0:     }
michael@0:     fCubic = cubic;
michael@0:     return 4;
michael@0: }
michael@0: 
michael@0: SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
michael@0:     SkDQuad quad;
michael@0:     quad.set(a);
michael@0:     SkReduceOrder reducer;
michael@0:     int order = reducer.reduce(quad);
michael@0:     if (order == 2) {  // quad became line
michael@0:         for (int index = 0; index < order; ++index) {
michael@0:             *reducePts++ = reducer.fLine[index].asSkPoint();
michael@0:         }
michael@0:     }
michael@0:     return SkPathOpsPointsToVerb(order - 1);
michael@0: }
michael@0: 
michael@0: SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
michael@0:     SkDCubic cubic;
michael@0:     cubic.set(a);
michael@0:     SkReduceOrder reducer;
michael@0:     int order = reducer.reduce(cubic, kAllow_Quadratics);
michael@0:     if (order == 2 || order == 3) {  // cubic became line or quad
michael@0:         for (int index = 0; index < order; ++index) {
michael@0:             *reducePts++ = reducer.fQuad[index].asSkPoint();
michael@0:         }
michael@0:     }
michael@0:     return SkPathOpsPointsToVerb(order - 1);
michael@0: }