src/third_party/skia/src/pathops/SkReduceOrder.cpp

   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             endIndex = 3;
 165             break;
 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 }