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