1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkReduceOrder.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,285 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#include "SkReduceOrder.h"
1.11 +
1.12 +int SkReduceOrder::reduce(const SkDLine& line) {
1.13 + fLine[0] = line[0];
1.14 + int different = line[0] != line[1];
1.15 + fLine[1] = line[different];
1.16 + return 1 + different;
1.17 +}
1.18 +
1.19 +static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) {
1.20 + reduction[0] = reduction[1] = quad[0];
1.21 + return 1;
1.22 +}
1.23 +
1.24 +static int reductionLineCount(const SkDQuad& reduction) {
1.25 + return 1 + !reduction[0].approximatelyEqual(reduction[1]);
1.26 +}
1.27 +
1.28 +static int vertical_line(const SkDQuad& quad, SkDQuad& reduction) {
1.29 + reduction[0] = quad[0];
1.30 + reduction[1] = quad[2];
1.31 + return reductionLineCount(reduction);
1.32 +}
1.33 +
1.34 +static int horizontal_line(const SkDQuad& quad, SkDQuad& reduction) {
1.35 + reduction[0] = quad[0];
1.36 + reduction[1] = quad[2];
1.37 + return reductionLineCount(reduction);
1.38 +}
1.39 +
1.40 +static int check_linear(const SkDQuad& quad,
1.41 + int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
1.42 + int startIndex = 0;
1.43 + int endIndex = 2;
1.44 + while (quad[startIndex].approximatelyEqual(quad[endIndex])) {
1.45 + --endIndex;
1.46 + if (endIndex == 0) {
1.47 + SkDebugf("%s shouldn't get here if all four points are about equal", __FUNCTION__);
1.48 + SkASSERT(0);
1.49 + }
1.50 + }
1.51 + if (!quad.isLinear(startIndex, endIndex)) {
1.52 + return 0;
1.53 + }
1.54 + // four are colinear: return line formed by outside
1.55 + reduction[0] = quad[0];
1.56 + reduction[1] = quad[2];
1.57 + return reductionLineCount(reduction);
1.58 +}
1.59 +
1.60 +// reduce to a quadratic or smaller
1.61 +// look for identical points
1.62 +// look for all four points in a line
1.63 + // note that three points in a line doesn't simplify a cubic
1.64 +// look for approximation with single quadratic
1.65 + // save approximation with multiple quadratics for later
1.66 +int SkReduceOrder::reduce(const SkDQuad& quad) {
1.67 + int index, minX, maxX, minY, maxY;
1.68 + int minXSet, minYSet;
1.69 + minX = maxX = minY = maxY = 0;
1.70 + minXSet = minYSet = 0;
1.71 + for (index = 1; index < 3; ++index) {
1.72 + if (quad[minX].fX > quad[index].fX) {
1.73 + minX = index;
1.74 + }
1.75 + if (quad[minY].fY > quad[index].fY) {
1.76 + minY = index;
1.77 + }
1.78 + if (quad[maxX].fX < quad[index].fX) {
1.79 + maxX = index;
1.80 + }
1.81 + if (quad[maxY].fY < quad[index].fY) {
1.82 + maxY = index;
1.83 + }
1.84 + }
1.85 + for (index = 0; index < 3; ++index) {
1.86 + if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) {
1.87 + minXSet |= 1 << index;
1.88 + }
1.89 + if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) {
1.90 + minYSet |= 1 << index;
1.91 + }
1.92 + }
1.93 + if (minXSet == 0x7) { // test for vertical line
1.94 + if (minYSet == 0x7) { // return 1 if all four are coincident
1.95 + return coincident_line(quad, fQuad);
1.96 + }
1.97 + return vertical_line(quad, fQuad);
1.98 + }
1.99 + if (minYSet == 0xF) { // test for horizontal line
1.100 + return horizontal_line(quad, fQuad);
1.101 + }
1.102 + int result = check_linear(quad, minX, maxX, minY, maxY, fQuad);
1.103 + if (result) {
1.104 + return result;
1.105 + }
1.106 + fQuad = quad;
1.107 + return 3;
1.108 +}
1.109 +
1.110 +////////////////////////////////////////////////////////////////////////////////////
1.111 +
1.112 +static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) {
1.113 + reduction[0] = reduction[1] = cubic[0];
1.114 + return 1;
1.115 +}
1.116 +
1.117 +static int reductionLineCount(const SkDCubic& reduction) {
1.118 + return 1 + !reduction[0].approximatelyEqual(reduction[1]);
1.119 +}
1.120 +
1.121 +static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) {
1.122 + reduction[0] = cubic[0];
1.123 + reduction[1] = cubic[3];
1.124 + return reductionLineCount(reduction);
1.125 +}
1.126 +
1.127 +static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) {
1.128 + reduction[0] = cubic[0];
1.129 + reduction[1] = cubic[3];
1.130 + return reductionLineCount(reduction);
1.131 +}
1.132 +
1.133 +// check to see if it is a quadratic or a line
1.134 +static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
1.135 + double dx10 = cubic[1].fX - cubic[0].fX;
1.136 + double dx23 = cubic[2].fX - cubic[3].fX;
1.137 + double midX = cubic[0].fX + dx10 * 3 / 2;
1.138 + double sideAx = midX - cubic[3].fX;
1.139 + double sideBx = dx23 * 3 / 2;
1.140 + if (approximately_zero(sideAx) ? !approximately_equal(sideAx, sideBx)
1.141 + : !AlmostEqualUlps(sideAx, sideBx)) {
1.142 + return 0;
1.143 + }
1.144 + double dy10 = cubic[1].fY - cubic[0].fY;
1.145 + double dy23 = cubic[2].fY - cubic[3].fY;
1.146 + double midY = cubic[0].fY + dy10 * 3 / 2;
1.147 + double sideAy = midY - cubic[3].fY;
1.148 + double sideBy = dy23 * 3 / 2;
1.149 + if (approximately_zero(sideAy) ? !approximately_equal(sideAy, sideBy)
1.150 + : !AlmostEqualUlps(sideAy, sideBy)) {
1.151 + return 0;
1.152 + }
1.153 + reduction[0] = cubic[0];
1.154 + reduction[1].fX = midX;
1.155 + reduction[1].fY = midY;
1.156 + reduction[2] = cubic[3];
1.157 + return 3;
1.158 +}
1.159 +
1.160 +static int check_linear(const SkDCubic& cubic,
1.161 + int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
1.162 + int startIndex = 0;
1.163 + int endIndex = 3;
1.164 + while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) {
1.165 + --endIndex;
1.166 + if (endIndex == 0) {
1.167 + SkDebugf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__);
1.168 + SkASSERT(0);
1.169 + }
1.170 + }
1.171 + if (!cubic.isLinear(startIndex, endIndex)) {
1.172 + return 0;
1.173 + }
1.174 + // four are colinear: return line formed by outside
1.175 + reduction[0] = cubic[0];
1.176 + reduction[1] = cubic[3];
1.177 + return reductionLineCount(reduction);
1.178 +}
1.179 +
1.180 +/* food for thought:
1.181 +http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html
1.182 +
1.183 +Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the
1.184 +corresponding quadratic Bezier are (given in convex combinations of
1.185 +points):
1.186 +
1.187 +q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4
1.188 +q2 = -c1 + (3/2)c2 + (3/2)c3 - c4
1.189 +q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4
1.190 +
1.191 +Of course, this curve does not interpolate the end-points, but it would
1.192 +be interesting to see the behaviour of such a curve in an applet.
1.193 +
1.194 +--
1.195 +Kalle Rutanen
1.196 +http://kaba.hilvi.org
1.197 +
1.198 +*/
1.199 +
1.200 +// reduce to a quadratic or smaller
1.201 +// look for identical points
1.202 +// look for all four points in a line
1.203 + // note that three points in a line doesn't simplify a cubic
1.204 +// look for approximation with single quadratic
1.205 + // save approximation with multiple quadratics for later
1.206 +int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) {
1.207 + int index, minX, maxX, minY, maxY;
1.208 + int minXSet, minYSet;
1.209 + minX = maxX = minY = maxY = 0;
1.210 + minXSet = minYSet = 0;
1.211 + for (index = 1; index < 4; ++index) {
1.212 + if (cubic[minX].fX > cubic[index].fX) {
1.213 + minX = index;
1.214 + }
1.215 + if (cubic[minY].fY > cubic[index].fY) {
1.216 + minY = index;
1.217 + }
1.218 + if (cubic[maxX].fX < cubic[index].fX) {
1.219 + maxX = index;
1.220 + }
1.221 + if (cubic[maxY].fY < cubic[index].fY) {
1.222 + maxY = index;
1.223 + }
1.224 + }
1.225 + for (index = 0; index < 4; ++index) {
1.226 + double cx = cubic[index].fX;
1.227 + double cy = cubic[index].fY;
1.228 + double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
1.229 + SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY))));
1.230 + if (denom == 0) {
1.231 + minXSet |= 1 << index;
1.232 + minYSet |= 1 << index;
1.233 + continue;
1.234 + }
1.235 + double inv = 1 / denom;
1.236 + if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) {
1.237 + minXSet |= 1 << index;
1.238 + }
1.239 + if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) {
1.240 + minYSet |= 1 << index;
1.241 + }
1.242 + }
1.243 + if (minXSet == 0xF) { // test for vertical line
1.244 + if (minYSet == 0xF) { // return 1 if all four are coincident
1.245 + return coincident_line(cubic, fCubic);
1.246 + }
1.247 + return vertical_line(cubic, fCubic);
1.248 + }
1.249 + if (minYSet == 0xF) { // test for horizontal line
1.250 + return horizontal_line(cubic, fCubic);
1.251 + }
1.252 + int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic);
1.253 + if (result) {
1.254 + return result;
1.255 + }
1.256 + if (allowQuadratics == SkReduceOrder::kAllow_Quadratics
1.257 + && (result = check_quadratic(cubic, fCubic))) {
1.258 + return result;
1.259 + }
1.260 + fCubic = cubic;
1.261 + return 4;
1.262 +}
1.263 +
1.264 +SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
1.265 + SkDQuad quad;
1.266 + quad.set(a);
1.267 + SkReduceOrder reducer;
1.268 + int order = reducer.reduce(quad);
1.269 + if (order == 2) { // quad became line
1.270 + for (int index = 0; index < order; ++index) {
1.271 + *reducePts++ = reducer.fLine[index].asSkPoint();
1.272 + }
1.273 + }
1.274 + return SkPathOpsPointsToVerb(order - 1);
1.275 +}
1.276 +
1.277 +SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
1.278 + SkDCubic cubic;
1.279 + cubic.set(a);
1.280 + SkReduceOrder reducer;
1.281 + int order = reducer.reduce(cubic, kAllow_Quadratics);
1.282 + if (order == 2 || order == 3) { // cubic became line or quad
1.283 + for (int index = 0; index < order; ++index) {
1.284 + *reducePts++ = reducer.fQuad[index].asSkPoint();
1.285 + }
1.286 + }
1.287 + return SkPathOpsPointsToVerb(order - 1);
1.288 +}
