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