caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 25 | static int vertical_line(const SkDQuad& quad, SkDQuad& reduction) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 26 | reduction[0] = quad[0]; |
| 27 | reduction[1] = quad[2]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 28 | return reductionLineCount(reduction); |
| 29 | } |
| 30 | |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 31 | static int horizontal_line(const SkDQuad& quad, SkDQuad& reduction) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 32 | reduction[0] = quad[0]; |
| 33 | reduction[1] = quad[2]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 34 | return reductionLineCount(reduction); |
| 35 | } |
| 36 | |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 37 | static int check_linear(const SkDQuad& quad, |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 63 | int SkReduceOrder::reduce(const SkDQuad& quad) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | } |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 94 | return vertical_line(quad, fQuad); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 95 | } |
| 96 | if (minYSet == 0xF) { // test for horizontal line |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 97 | return horizontal_line(quad, fQuad); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 98 | } |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 99 | int result = check_linear(quad, minX, maxX, minY, maxY, fQuad); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 100 | if (result) { |
| 101 | return result; |
| 102 | } |
| 103 | fQuad = quad; |
| 104 | return 3; |
| 105 | } |
| 106 | |
| 107 | //////////////////////////////////////////////////////////////////////////////////// |
| 108 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 118 | static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 119 | reduction[0] = cubic[0]; |
| 120 | reduction[1] = cubic[3]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 121 | return reductionLineCount(reduction); |
| 122 | } |
| 123 | |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 124 | static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 125 | reduction[0] = cubic[0]; |
| 126 | reduction[1] = cubic[3]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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; |
caryclark@google.com | 7ec5e39 | 2013-04-17 16:19:02 +0000 | [diff] [blame] | 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)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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; |
caryclark@google.com | 7ec5e39 | 2013-04-17 16:19:02 +0000 | [diff] [blame] | 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)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 157 | static int check_linear(const SkDCubic& cubic, |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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) { |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame^] | 164 | endIndex = 3; |
| 165 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 203 | int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | } |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 244 | return vertical_line(cubic, fCubic); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 245 | } |
| 246 | if (minYSet == 0xF) { // test for horizontal line |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 247 | return horizontal_line(cubic, fCubic); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 248 | } |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 249 | int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 261 | SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 262 | SkDQuad quad; |
| 263 | quad.set(a); |
| 264 | SkReduceOrder reducer; |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 265 | int order = reducer.reduce(quad); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 266 | if (order == 2) { // quad became line |
| 267 | for (int index = 0; index < order; ++index) { |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 268 | *reducePts++ = reducer.fLine[index].asSkPoint(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 269 | } |
| 270 | } |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 271 | return SkPathOpsPointsToVerb(order - 1); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 272 | } |
| 273 | |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 274 | SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 275 | SkDCubic cubic; |
| 276 | cubic.set(a); |
| 277 | SkReduceOrder reducer; |
caryclark@google.com | 927b702 | 2013-11-25 14:18:21 +0000 | [diff] [blame] | 278 | int order = reducer.reduce(cubic, kAllow_Quadratics); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 279 | if (order == 2 || order == 3) { // cubic became line or quad |
| 280 | for (int index = 0; index < order; ++index) { |
caryclark@google.com | 07e97fc | 2013-07-08 17:17:02 +0000 | [diff] [blame] | 281 | *reducePts++ = reducer.fQuad[index].asSkPoint(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 282 | } |
| 283 | } |
reed@google.com | 277c3f8 | 2013-05-31 15:17:50 +0000 | [diff] [blame] | 284 | return SkPathOpsPointsToVerb(order - 1); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 285 | } |