Home | History | Annotate | Download | only in pathops
      1 /*
      2  * Copyright 2012 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 #include "SkReduceOrder.h"
      8 
      9 int SkReduceOrder::reduce(const SkDLine& line) {
     10     fLine[0] = line[0];
     11     int different = line[0] != line[1];
     12     fLine[1] = line[different];
     13     return 1 + different;
     14 }
     15 
     16 static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) {
     17     reduction[0] = reduction[1] = quad[0];
     18     return 1;
     19 }
     20 
     21 static int reductionLineCount(const SkDQuad& reduction) {
     22     return 1 + !reduction[0].approximatelyEqual(reduction[1]);
     23 }
     24 
     25 static int vertical_line(const SkDQuad& quad, SkDQuad& reduction) {
     26     reduction[0] = quad[0];
     27     reduction[1] = quad[2];
     28     return reductionLineCount(reduction);
     29 }
     30 
     31 static int horizontal_line(const SkDQuad& quad, SkDQuad& reduction) {
     32     reduction[0] = quad[0];
     33     reduction[1] = quad[2];
     34     return reductionLineCount(reduction);
     35 }
     36 
     37 static int check_linear(const SkDQuad& quad,
     38         int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
     39     int startIndex = 0;
     40     int endIndex = 2;
     41     while (quad[startIndex].approximatelyEqual(quad[endIndex])) {
     42         --endIndex;
     43         if (endIndex == 0) {
     44             SkDebugf("%s shouldn't get here if all four points are about equal", __FUNCTION__);
     45             SkASSERT(0);
     46         }
     47     }
     48     if (!quad.isLinear(startIndex, endIndex)) {
     49         return 0;
     50     }
     51     // four are colinear: return line formed by outside
     52     reduction[0] = quad[0];
     53     reduction[1] = quad[2];
     54     return reductionLineCount(reduction);
     55 }
     56 
     57 // reduce to a quadratic or smaller
     58 // look for identical points
     59 // look for all four points in a line
     60     // note that three points in a line doesn't simplify a cubic
     61 // look for approximation with single quadratic
     62     // save approximation with multiple quadratics for later
     63 int SkReduceOrder::reduce(const SkDQuad& quad) {
     64     int index, minX, maxX, minY, maxY;
     65     int minXSet, minYSet;
     66     minX = maxX = minY = maxY = 0;
     67     minXSet = minYSet = 0;
     68     for (index = 1; index < 3; ++index) {
     69         if (quad[minX].fX > quad[index].fX) {
     70             minX = index;
     71         }
     72         if (quad[minY].fY > quad[index].fY) {
     73             minY = index;
     74         }
     75         if (quad[maxX].fX < quad[index].fX) {
     76             maxX = index;
     77         }
     78         if (quad[maxY].fY < quad[index].fY) {
     79             maxY = index;
     80         }
     81     }
     82     for (index = 0; index < 3; ++index) {
     83         if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) {
     84             minXSet |= 1 << index;
     85         }
     86         if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) {
     87             minYSet |= 1 << index;
     88         }
     89     }
     90     if (minXSet == 0x7) {  // test for vertical line
     91         if (minYSet == 0x7) {  // return 1 if all four are coincident
     92             return coincident_line(quad, fQuad);
     93         }
     94         return vertical_line(quad, fQuad);
     95     }
     96     if (minYSet == 0xF) {  // test for horizontal line
     97         return horizontal_line(quad, fQuad);
     98     }
     99     int result = check_linear(quad, minX, maxX, minY, maxY, fQuad);
    100     if (result) {
    101         return result;
    102     }
    103     fQuad = quad;
    104     return 3;
    105 }
    106 
    107 ////////////////////////////////////////////////////////////////////////////////////
    108 
    109 static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) {
    110     reduction[0] = reduction[1] = cubic[0];
    111     return 1;
    112 }
    113 
    114 static int reductionLineCount(const SkDCubic& reduction) {
    115     return 1 + !reduction[0].approximatelyEqual(reduction[1]);
    116 }
    117 
    118 static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) {
    119     reduction[0] = cubic[0];
    120     reduction[1] = cubic[3];
    121     return reductionLineCount(reduction);
    122 }
    123 
    124 static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) {
    125     reduction[0] = cubic[0];
    126     reduction[1] = cubic[3];
    127     return reductionLineCount(reduction);
    128 }
    129 
    130 // check to see if it is a quadratic or a line
    131 static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
    132     double dx10 = cubic[1].fX - cubic[0].fX;
    133     double dx23 = cubic[2].fX - cubic[3].fX;
    134     double midX = cubic[0].fX + dx10 * 3 / 2;
    135     double sideAx = midX - cubic[3].fX;
    136     double sideBx = dx23 * 3 / 2;
    137     if (approximately_zero(sideAx) ? !approximately_equal(sideAx, sideBx)
    138             : !AlmostEqualUlps(sideAx, sideBx)) {
    139         return 0;
    140     }
    141     double dy10 = cubic[1].fY - cubic[0].fY;
    142     double dy23 = cubic[2].fY - cubic[3].fY;
    143     double midY = cubic[0].fY + dy10 * 3 / 2;
    144     double sideAy = midY - cubic[3].fY;
    145     double sideBy = dy23 * 3 / 2;
    146     if (approximately_zero(sideAy) ? !approximately_equal(sideAy, sideBy)
    147             : !AlmostEqualUlps(sideAy, sideBy)) {
    148         return 0;
    149     }
    150     reduction[0] = cubic[0];
    151     reduction[1].fX = midX;
    152     reduction[1].fY = midY;
    153     reduction[2] = cubic[3];
    154     return 3;
    155 }
    156 
    157 static int check_linear(const SkDCubic& cubic,
    158         int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
    159     int startIndex = 0;
    160     int endIndex = 3;
    161     while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) {
    162         --endIndex;
    163         if (endIndex == 0) {
    164             SkDebugf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__);
    165             SkASSERT(0);
    166         }
    167     }
    168     if (!cubic.isLinear(startIndex, endIndex)) {
    169         return 0;
    170     }
    171     // four are colinear: return line formed by outside
    172     reduction[0] = cubic[0];
    173     reduction[1] = cubic[3];
    174     return reductionLineCount(reduction);
    175 }
    176 
    177 /* food for thought:
    178 http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html
    179 
    180 Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the
    181 corresponding quadratic Bezier are (given in convex combinations of
    182 points):
    183 
    184 q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4
    185 q2 = -c1 + (3/2)c2 + (3/2)c3 - c4
    186 q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4
    187 
    188 Of course, this curve does not interpolate the end-points, but it would
    189 be interesting to see the behaviour of such a curve in an applet.
    190 
    191 --
    192 Kalle Rutanen
    193 http://kaba.hilvi.org
    194 
    195 */
    196 
    197 // reduce to a quadratic or smaller
    198 // look for identical points
    199 // look for all four points in a line
    200     // note that three points in a line doesn't simplify a cubic
    201 // look for approximation with single quadratic
    202     // save approximation with multiple quadratics for later
    203 int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) {
    204     int index, minX, maxX, minY, maxY;
    205     int minXSet, minYSet;
    206     minX = maxX = minY = maxY = 0;
    207     minXSet = minYSet = 0;
    208     for (index = 1; index < 4; ++index) {
    209         if (cubic[minX].fX > cubic[index].fX) {
    210             minX = index;
    211         }
    212         if (cubic[minY].fY > cubic[index].fY) {
    213             minY = index;
    214         }
    215         if (cubic[maxX].fX < cubic[index].fX) {
    216             maxX = index;
    217         }
    218         if (cubic[maxY].fY < cubic[index].fY) {
    219             maxY = index;
    220         }
    221     }
    222     for (index = 0; index < 4; ++index) {
    223         double cx = cubic[index].fX;
    224         double cy = cubic[index].fY;
    225         double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
    226                 SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY))));
    227         if (denom == 0) {
    228             minXSet |= 1 << index;
    229             minYSet |= 1 << index;
    230             continue;
    231         }
    232         double inv = 1 / denom;
    233         if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) {
    234             minXSet |= 1 << index;
    235         }
    236         if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) {
    237             minYSet |= 1 << index;
    238         }
    239     }
    240     if (minXSet == 0xF) {  // test for vertical line
    241         if (minYSet == 0xF) {  // return 1 if all four are coincident
    242             return coincident_line(cubic, fCubic);
    243         }
    244         return vertical_line(cubic, fCubic);
    245     }
    246     if (minYSet == 0xF) {  // test for horizontal line
    247         return horizontal_line(cubic, fCubic);
    248     }
    249     int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic);
    250     if (result) {
    251         return result;
    252     }
    253     if (allowQuadratics == SkReduceOrder::kAllow_Quadratics
    254             && (result = check_quadratic(cubic, fCubic))) {
    255         return result;
    256     }
    257     fCubic = cubic;
    258     return 4;
    259 }
    260 
    261 SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
    262     SkDQuad quad;
    263     quad.set(a);
    264     SkReduceOrder reducer;
    265     int order = reducer.reduce(quad);
    266     if (order == 2) {  // quad became line
    267         for (int index = 0; index < order; ++index) {
    268             *reducePts++ = reducer.fLine[index].asSkPoint();
    269         }
    270     }
    271     return SkPathOpsPointsToVerb(order - 1);
    272 }
    273 
    274 SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
    275     SkDCubic cubic;
    276     cubic.set(a);
    277     SkReduceOrder reducer;
    278     int order = reducer.reduce(cubic, kAllow_Quadratics);
    279     if (order == 2 || order == 3) {  // cubic became line or quad
    280         for (int index = 0; index < order; ++index) {
    281             *reducePts++ = reducer.fQuad[index].asSkPoint();
    282         }
    283     }
    284     return SkPathOpsPointsToVerb(order - 1);
    285 }
    286