OLD | NEW |
(Empty) | |
| 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 double interp_quad_coords(double a, double b, double c, double t) { |
| 17 double ab = SkDInterp(a, b, t); |
| 18 double bc = SkDInterp(b, c, t); |
| 19 return SkDInterp(ab, bc, t); |
| 20 } |
| 21 |
| 22 static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) { |
| 23 reduction[0] = reduction[1] = quad[0]; |
| 24 return 1; |
| 25 } |
| 26 |
| 27 static int reductionLineCount(const SkDQuad& reduction) { |
| 28 return 1 + !reduction[0].approximatelyEqual(reduction[1]); |
| 29 } |
| 30 |
| 31 static int vertical_line(const SkDQuad& quad, SkReduceOrder::Style reduceStyle, |
| 32 SkDQuad& reduction) { |
| 33 double tValue; |
| 34 reduction[0] = quad[0]; |
| 35 reduction[1] = quad[2]; |
| 36 if (reduceStyle == SkReduceOrder::kFill_Style) { |
| 37 return reductionLineCount(reduction); |
| 38 } |
| 39 int smaller = reduction[1].fY > reduction[0].fY; |
| 40 int larger = smaller ^ 1; |
| 41 if (SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValue)) { |
| 42 double yExtrema = interp_quad_coords(quad[0].fY, quad[1].fY, quad[2].fY,
tValue); |
| 43 if (reduction[smaller].fY > yExtrema) { |
| 44 reduction[smaller].fY = yExtrema; |
| 45 } else if (reduction[larger].fY < yExtrema) { |
| 46 reduction[larger].fY = yExtrema; |
| 47 } |
| 48 } |
| 49 return reductionLineCount(reduction); |
| 50 } |
| 51 |
| 52 static int horizontal_line(const SkDQuad& quad, SkReduceOrder::Style reduceStyle
, |
| 53 SkDQuad& reduction) { |
| 54 double tValue; |
| 55 reduction[0] = quad[0]; |
| 56 reduction[1] = quad[2]; |
| 57 if (reduceStyle == SkReduceOrder::kFill_Style) { |
| 58 return reductionLineCount(reduction); |
| 59 } |
| 60 int smaller = reduction[1].fX > reduction[0].fX; |
| 61 int larger = smaller ^ 1; |
| 62 if (SkDQuad::FindExtrema(quad[0].fX, quad[1].fX, quad[2].fX, &tValue)) { |
| 63 double xExtrema = interp_quad_coords(quad[0].fX, quad[1].fX, quad[2].fX,
tValue); |
| 64 if (reduction[smaller].fX > xExtrema) { |
| 65 reduction[smaller].fX = xExtrema; |
| 66 } else if (reduction[larger].fX < xExtrema) { |
| 67 reduction[larger].fX = xExtrema; |
| 68 } |
| 69 } |
| 70 return reductionLineCount(reduction); |
| 71 } |
| 72 |
| 73 static int check_linear(const SkDQuad& quad, SkReduceOrder::Style reduceStyle, |
| 74 int minX, int maxX, int minY, int maxY, SkDQuad& reduction) { |
| 75 int startIndex = 0; |
| 76 int endIndex = 2; |
| 77 while (quad[startIndex].approximatelyEqual(quad[endIndex])) { |
| 78 --endIndex; |
| 79 if (endIndex == 0) { |
| 80 SkDebugf("%s shouldn't get here if all four points are about equal",
__FUNCTION__); |
| 81 SkASSERT(0); |
| 82 } |
| 83 } |
| 84 if (!quad.isLinear(startIndex, endIndex)) { |
| 85 return 0; |
| 86 } |
| 87 // four are colinear: return line formed by outside |
| 88 reduction[0] = quad[0]; |
| 89 reduction[1] = quad[2]; |
| 90 if (reduceStyle == SkReduceOrder::kFill_Style) { |
| 91 return reductionLineCount(reduction); |
| 92 } |
| 93 int sameSide; |
| 94 bool useX = quad[maxX].fX - quad[minX].fX >= quad[maxY].fY - quad[minY].fY; |
| 95 if (useX) { |
| 96 sameSide = SkDSign(quad[0].fX - quad[1].fX) + SkDSign(quad[2].fX - quad[
1].fX); |
| 97 } else { |
| 98 sameSide = SkDSign(quad[0].fY - quad[1].fY) + SkDSign(quad[2].fY - quad[
1].fY); |
| 99 } |
| 100 if ((sameSide & 3) != 2) { |
| 101 return reductionLineCount(reduction); |
| 102 } |
| 103 double tValue; |
| 104 int root; |
| 105 if (useX) { |
| 106 root = SkDQuad::FindExtrema(quad[0].fX, quad[1].fX, quad[2].fX, &tValue)
; |
| 107 } else { |
| 108 root = SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValue)
; |
| 109 } |
| 110 if (root) { |
| 111 SkDPoint extrema; |
| 112 extrema.fX = interp_quad_coords(quad[0].fX, quad[1].fX, quad[2].fX, tVal
ue); |
| 113 extrema.fY = interp_quad_coords(quad[0].fY, quad[1].fY, quad[2].fY, tVal
ue); |
| 114 // sameSide > 0 means mid is smaller than either [0] or [2], so replace
smaller |
| 115 int replace; |
| 116 if (useX) { |
| 117 if (extrema.fX < quad[0].fX ^ extrema.fX < quad[2].fX) { |
| 118 return reductionLineCount(reduction); |
| 119 } |
| 120 replace = (extrema.fX < quad[0].fX | extrema.fX < quad[2].fX) |
| 121 ^ (quad[0].fX < quad[2].fX); |
| 122 } else { |
| 123 if (extrema.fY < quad[0].fY ^ extrema.fY < quad[2].fY) { |
| 124 return reductionLineCount(reduction); |
| 125 } |
| 126 replace = (extrema.fY < quad[0].fY | extrema.fY < quad[2].fY) |
| 127 ^ (quad[0].fY < quad[2].fY); |
| 128 } |
| 129 reduction[replace] = extrema; |
| 130 } |
| 131 return reductionLineCount(reduction); |
| 132 } |
| 133 |
| 134 // reduce to a quadratic or smaller |
| 135 // look for identical points |
| 136 // look for all four points in a line |
| 137 // note that three points in a line doesn't simplify a cubic |
| 138 // look for approximation with single quadratic |
| 139 // save approximation with multiple quadratics for later |
| 140 int SkReduceOrder::reduce(const SkDQuad& quad, Style reduceStyle) { |
| 141 int index, minX, maxX, minY, maxY; |
| 142 int minXSet, minYSet; |
| 143 minX = maxX = minY = maxY = 0; |
| 144 minXSet = minYSet = 0; |
| 145 for (index = 1; index < 3; ++index) { |
| 146 if (quad[minX].fX > quad[index].fX) { |
| 147 minX = index; |
| 148 } |
| 149 if (quad[minY].fY > quad[index].fY) { |
| 150 minY = index; |
| 151 } |
| 152 if (quad[maxX].fX < quad[index].fX) { |
| 153 maxX = index; |
| 154 } |
| 155 if (quad[maxY].fY < quad[index].fY) { |
| 156 maxY = index; |
| 157 } |
| 158 } |
| 159 for (index = 0; index < 3; ++index) { |
| 160 if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) { |
| 161 minXSet |= 1 << index; |
| 162 } |
| 163 if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) { |
| 164 minYSet |= 1 << index; |
| 165 } |
| 166 } |
| 167 if (minXSet == 0x7) { // test for vertical line |
| 168 if (minYSet == 0x7) { // return 1 if all four are coincident |
| 169 return coincident_line(quad, fQuad); |
| 170 } |
| 171 return vertical_line(quad, reduceStyle, fQuad); |
| 172 } |
| 173 if (minYSet == 0xF) { // test for horizontal line |
| 174 return horizontal_line(quad, reduceStyle, fQuad); |
| 175 } |
| 176 int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, fQuad); |
| 177 if (result) { |
| 178 return result; |
| 179 } |
| 180 fQuad = quad; |
| 181 return 3; |
| 182 } |
| 183 |
| 184 ////////////////////////////////////////////////////////////////////////////////
//// |
| 185 |
| 186 static double interp_cubic_coords(const double* src, double t) { |
| 187 double ab = SkDInterp(src[0], src[2], t); |
| 188 double bc = SkDInterp(src[2], src[4], t); |
| 189 double cd = SkDInterp(src[4], src[6], t); |
| 190 double abc = SkDInterp(ab, bc, t); |
| 191 double bcd = SkDInterp(bc, cd, t); |
| 192 return SkDInterp(abc, bcd, t); |
| 193 } |
| 194 |
| 195 static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) { |
| 196 reduction[0] = reduction[1] = cubic[0]; |
| 197 return 1; |
| 198 } |
| 199 |
| 200 static int reductionLineCount(const SkDCubic& reduction) { |
| 201 return 1 + !reduction[0].approximatelyEqual(reduction[1]); |
| 202 } |
| 203 |
| 204 static int vertical_line(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle
, |
| 205 SkDCubic& reduction) { |
| 206 double tValues[2]; |
| 207 reduction[0] = cubic[0]; |
| 208 reduction[1] = cubic[3]; |
| 209 if (reduceStyle == SkReduceOrder::kFill_Style) { |
| 210 return reductionLineCount(reduction); |
| 211 } |
| 212 int smaller = reduction[1].fY > reduction[0].fY; |
| 213 int larger = smaller ^ 1; |
| 214 int roots = SkDCubic::FindExtrema(cubic[0].fY, cubic[1].fY, cubic[2].fY, cub
ic[3].fY, tValues); |
| 215 for (int index = 0; index < roots; ++index) { |
| 216 double yExtrema = interp_cubic_coords(&cubic[0].fY, tValues[index]); |
| 217 if (reduction[smaller].fY > yExtrema) { |
| 218 reduction[smaller].fY = yExtrema; |
| 219 continue; |
| 220 } |
| 221 if (reduction[larger].fY < yExtrema) { |
| 222 reduction[larger].fY = yExtrema; |
| 223 } |
| 224 } |
| 225 return reductionLineCount(reduction); |
| 226 } |
| 227 |
| 228 static int horizontal_line(const SkDCubic& cubic, SkReduceOrder::Style reduceSty
le, |
| 229 SkDCubic& reduction) { |
| 230 double tValues[2]; |
| 231 reduction[0] = cubic[0]; |
| 232 reduction[1] = cubic[3]; |
| 233 if (reduceStyle == SkReduceOrder::kFill_Style) { |
| 234 return reductionLineCount(reduction); |
| 235 } |
| 236 int smaller = reduction[1].fX > reduction[0].fX; |
| 237 int larger = smaller ^ 1; |
| 238 int roots = SkDCubic::FindExtrema(cubic[0].fX, cubic[1].fX, cubic[2].fX, cub
ic[3].fX, tValues); |
| 239 for (int index = 0; index < roots; ++index) { |
| 240 double xExtrema = interp_cubic_coords(&cubic[0].fX, tValues[index]); |
| 241 if (reduction[smaller].fX > xExtrema) { |
| 242 reduction[smaller].fX = xExtrema; |
| 243 continue; |
| 244 } |
| 245 if (reduction[larger].fX < xExtrema) { |
| 246 reduction[larger].fX = xExtrema; |
| 247 } |
| 248 } |
| 249 return reductionLineCount(reduction); |
| 250 } |
| 251 |
| 252 // check to see if it is a quadratic or a line |
| 253 static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) { |
| 254 double dx10 = cubic[1].fX - cubic[0].fX; |
| 255 double dx23 = cubic[2].fX - cubic[3].fX; |
| 256 double midX = cubic[0].fX + dx10 * 3 / 2; |
| 257 if (!AlmostEqualUlps(midX - cubic[3].fX, dx23 * 3 / 2)) { |
| 258 return 0; |
| 259 } |
| 260 double dy10 = cubic[1].fY - cubic[0].fY; |
| 261 double dy23 = cubic[2].fY - cubic[3].fY; |
| 262 double midY = cubic[0].fY + dy10 * 3 / 2; |
| 263 if (!AlmostEqualUlps(midY - cubic[3].fY, dy23 * 3 / 2)) { |
| 264 return 0; |
| 265 } |
| 266 reduction[0] = cubic[0]; |
| 267 reduction[1].fX = midX; |
| 268 reduction[1].fY = midY; |
| 269 reduction[2] = cubic[3]; |
| 270 return 3; |
| 271 } |
| 272 |
| 273 static int check_linear(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle, |
| 274 int minX, int maxX, int minY, int maxY, SkDCubic& reduction) { |
| 275 int startIndex = 0; |
| 276 int endIndex = 3; |
| 277 while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) { |
| 278 --endIndex; |
| 279 if (endIndex == 0) { |
| 280 SkDebugf("%s shouldn't get here if all four points are about equal\n
", __FUNCTION__); |
| 281 SkASSERT(0); |
| 282 } |
| 283 } |
| 284 if (!cubic.isLinear(startIndex, endIndex)) { |
| 285 return 0; |
| 286 } |
| 287 // four are colinear: return line formed by outside |
| 288 reduction[0] = cubic[0]; |
| 289 reduction[1] = cubic[3]; |
| 290 if (reduceStyle == SkReduceOrder::kFill_Style) { |
| 291 return reductionLineCount(reduction); |
| 292 } |
| 293 int sameSide1; |
| 294 int sameSide2; |
| 295 bool useX = cubic[maxX].fX - cubic[minX].fX >= cubic[maxY].fY - cubic[minY].
fY; |
| 296 if (useX) { |
| 297 sameSide1 = SkDSign(cubic[0].fX - cubic[1].fX) + SkDSign(cubic[3].fX - c
ubic[1].fX); |
| 298 sameSide2 = SkDSign(cubic[0].fX - cubic[2].fX) + SkDSign(cubic[3].fX - c
ubic[2].fX); |
| 299 } else { |
| 300 sameSide1 = SkDSign(cubic[0].fY - cubic[1].fY) + SkDSign(cubic[3].fY - c
ubic[1].fY); |
| 301 sameSide2 = SkDSign(cubic[0].fY - cubic[2].fY) + SkDSign(cubic[3].fY - c
ubic[2].fY); |
| 302 } |
| 303 if (sameSide1 == sameSide2 && (sameSide1 & 3) != 2) { |
| 304 return reductionLineCount(reduction); |
| 305 } |
| 306 double tValues[2]; |
| 307 int roots; |
| 308 if (useX) { |
| 309 roots = SkDCubic::FindExtrema(cubic[0].fX, cubic[1].fX, cubic[2].fX, cub
ic[3].fX, tValues); |
| 310 } else { |
| 311 roots = SkDCubic::FindExtrema(cubic[0].fY, cubic[1].fY, cubic[2].fY, cub
ic[3].fY, tValues); |
| 312 } |
| 313 for (int index = 0; index < roots; ++index) { |
| 314 SkDPoint extrema; |
| 315 extrema.fX = interp_cubic_coords(&cubic[0].fX, tValues[index]); |
| 316 extrema.fY = interp_cubic_coords(&cubic[0].fY, tValues[index]); |
| 317 // sameSide > 0 means mid is smaller than either [0] or [3], so replace
smaller |
| 318 int replace; |
| 319 if (useX) { |
| 320 if (extrema.fX < cubic[0].fX ^ extrema.fX < cubic[3].fX) { |
| 321 continue; |
| 322 } |
| 323 replace = (extrema.fX < cubic[0].fX | extrema.fX < cubic[3].fX) |
| 324 ^ (cubic[0].fX < cubic[3].fX); |
| 325 } else { |
| 326 if (extrema.fY < cubic[0].fY ^ extrema.fY < cubic[3].fY) { |
| 327 continue; |
| 328 } |
| 329 replace = (extrema.fY < cubic[0].fY | extrema.fY < cubic[3].fY) |
| 330 ^ (cubic[0].fY < cubic[3].fY); |
| 331 } |
| 332 reduction[replace] = extrema; |
| 333 } |
| 334 return reductionLineCount(reduction); |
| 335 } |
| 336 |
| 337 /* food for thought: |
| 338 http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piece
wise-degree-reduction-algos-2-a.html |
| 339 |
| 340 Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the |
| 341 corresponding quadratic Bezier are (given in convex combinations of |
| 342 points): |
| 343 |
| 344 q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4 |
| 345 q2 = -c1 + (3/2)c2 + (3/2)c3 - c4 |
| 346 q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4 |
| 347 |
| 348 Of course, this curve does not interpolate the end-points, but it would |
| 349 be interesting to see the behaviour of such a curve in an applet. |
| 350 |
| 351 -- |
| 352 Kalle Rutanen |
| 353 http://kaba.hilvi.org |
| 354 |
| 355 */ |
| 356 |
| 357 // reduce to a quadratic or smaller |
| 358 // look for identical points |
| 359 // look for all four points in a line |
| 360 // note that three points in a line doesn't simplify a cubic |
| 361 // look for approximation with single quadratic |
| 362 // save approximation with multiple quadratics for later |
| 363 int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics, |
| 364 Style reduceStyle) { |
| 365 int index, minX, maxX, minY, maxY; |
| 366 int minXSet, minYSet; |
| 367 minX = maxX = minY = maxY = 0; |
| 368 minXSet = minYSet = 0; |
| 369 for (index = 1; index < 4; ++index) { |
| 370 if (cubic[minX].fX > cubic[index].fX) { |
| 371 minX = index; |
| 372 } |
| 373 if (cubic[minY].fY > cubic[index].fY) { |
| 374 minY = index; |
| 375 } |
| 376 if (cubic[maxX].fX < cubic[index].fX) { |
| 377 maxX = index; |
| 378 } |
| 379 if (cubic[maxY].fY < cubic[index].fY) { |
| 380 maxY = index; |
| 381 } |
| 382 } |
| 383 for (index = 0; index < 4; ++index) { |
| 384 double cx = cubic[index].fX; |
| 385 double cy = cubic[index].fY; |
| 386 double denom = SkTMax(fabs(cx), SkTMax(fabs(cy), |
| 387 SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY)))); |
| 388 if (denom == 0) { |
| 389 minXSet |= 1 << index; |
| 390 minYSet |= 1 << index; |
| 391 continue; |
| 392 } |
| 393 double inv = 1 / denom; |
| 394 if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) { |
| 395 minXSet |= 1 << index; |
| 396 } |
| 397 if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) { |
| 398 minYSet |= 1 << index; |
| 399 } |
| 400 } |
| 401 if (minXSet == 0xF) { // test for vertical line |
| 402 if (minYSet == 0xF) { // return 1 if all four are coincident |
| 403 return coincident_line(cubic, fCubic); |
| 404 } |
| 405 return vertical_line(cubic, reduceStyle, fCubic); |
| 406 } |
| 407 if (minYSet == 0xF) { // test for horizontal line |
| 408 return horizontal_line(cubic, reduceStyle, fCubic); |
| 409 } |
| 410 int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, fCubic
); |
| 411 if (result) { |
| 412 return result; |
| 413 } |
| 414 if (allowQuadratics == SkReduceOrder::kAllow_Quadratics |
| 415 && (result = check_quadratic(cubic, fCubic))) { |
| 416 return result; |
| 417 } |
| 418 fCubic = cubic; |
| 419 return 4; |
| 420 } |
| 421 |
| 422 SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkTDArray<SkPoint>* reduceP
ts) { |
| 423 SkDQuad quad; |
| 424 quad.set(a); |
| 425 SkReduceOrder reducer; |
| 426 int order = reducer.reduce(quad, kFill_Style); |
| 427 if (order == 2) { // quad became line |
| 428 for (int index = 0; index < order; ++index) { |
| 429 SkPoint* pt = reducePts->append(); |
| 430 pt->fX = SkDoubleToScalar(reducer.fLine[index].fX); |
| 431 pt->fY = SkDoubleToScalar(reducer.fLine[index].fY); |
| 432 } |
| 433 } |
| 434 return (SkPath::Verb) (order - 1); |
| 435 } |
| 436 |
| 437 SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkTDArray<SkPoint>* reduce
Pts) { |
| 438 SkDCubic cubic; |
| 439 cubic.set(a); |
| 440 SkReduceOrder reducer; |
| 441 int order = reducer.reduce(cubic, kAllow_Quadratics, kFill_Style); |
| 442 if (order == 2 || order == 3) { // cubic became line or quad |
| 443 for (int index = 0; index < order; ++index) { |
| 444 SkPoint* pt = reducePts->append(); |
| 445 pt->fX = SkDoubleToScalar(reducer.fQuad[index].fX); |
| 446 pt->fY = SkDoubleToScalar(reducer.fQuad[index].fY); |
| 447 } |
| 448 } |
| 449 return (SkPath::Verb) (order - 1); |
| 450 } |
OLD | NEW |