caryclark@google.com | 818b0cc | 2013-04-08 11:50:46 +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 "PathOpsTestCommon.h" |
caryclark@google.com | 8d0a524 | 2013-07-16 16:11:16 +0000 | [diff] [blame] | 8 | #include "SkPathOpsBounds.h" |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 9 | #include "SkPathOpsConic.h" |
caryclark@google.com | 818b0cc | 2013-04-08 11:50:46 +0000 | [diff] [blame] | 10 | #include "SkPathOpsCubic.h" |
caryclark@google.com | 8d0a524 | 2013-07-16 16:11:16 +0000 | [diff] [blame] | 11 | #include "SkPathOpsLine.h" |
| 12 | #include "SkPathOpsQuad.h" |
Cary Clark | 0949bee | 2018-03-19 09:42:00 -0400 | [diff] [blame] | 13 | #include "SkPathOpsTSect.h" |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 14 | #include "SkReduceOrder.h" |
| 15 | #include "SkTSort.h" |
| 16 | |
| 17 | static double calc_t_div(const SkDCubic& cubic, double precision, double start) { |
| 18 | const double adjust = sqrt(3.) / 36; |
| 19 | SkDCubic sub; |
| 20 | const SkDCubic* cPtr; |
| 21 | if (start == 0) { |
| 22 | cPtr = &cubic; |
| 23 | } else { |
| 24 | // OPTIMIZE: special-case half-split ? |
| 25 | sub = cubic.subDivide(start, 1); |
| 26 | cPtr = ⊂ |
| 27 | } |
| 28 | const SkDCubic& c = *cPtr; |
| 29 | double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX; |
| 30 | double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY; |
| 31 | double dist = sqrt(dx * dx + dy * dy); |
| 32 | double tDiv3 = precision / (adjust * dist); |
| 33 | double t = SkDCubeRoot(tDiv3); |
| 34 | if (start > 0) { |
| 35 | t = start + (1 - start) * t; |
| 36 | } |
| 37 | return t; |
| 38 | } |
| 39 | |
| 40 | static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) { |
| 41 | double tDiv = calc_t_div(cubic, precision, 0); |
| 42 | if (tDiv >= 1) { |
| 43 | return true; |
| 44 | } |
| 45 | if (tDiv >= 0.5) { |
| 46 | ts->push_back(0.5); |
| 47 | return true; |
| 48 | } |
| 49 | return false; |
| 50 | } |
| 51 | |
| 52 | static void addTs(const SkDCubic& cubic, double precision, double start, double end, |
| 53 | SkTArray<double, true>* ts) { |
| 54 | double tDiv = calc_t_div(cubic, precision, 0); |
| 55 | double parts = ceil(1.0 / tDiv); |
| 56 | for (double index = 0; index < parts; ++index) { |
| 57 | double newT = start + (index / parts) * (end - start); |
| 58 | if (newT > 0 && newT < 1) { |
| 59 | ts->push_back(newT); |
| 60 | } |
| 61 | } |
| 62 | } |
| 63 | |
| 64 | static void toQuadraticTs(const SkDCubic* cubic, double precision, SkTArray<double, true>* ts) { |
| 65 | SkReduceOrder reducer; |
| 66 | int order = reducer.reduce(*cubic, SkReduceOrder::kAllow_Quadratics); |
| 67 | if (order < 3) { |
| 68 | return; |
| 69 | } |
| 70 | double inflectT[5]; |
| 71 | int inflections = cubic->findInflections(inflectT); |
| 72 | SkASSERT(inflections <= 2); |
| 73 | if (!cubic->endsAreExtremaInXOrY()) { |
| 74 | inflections += cubic->findMaxCurvature(&inflectT[inflections]); |
| 75 | SkASSERT(inflections <= 5); |
| 76 | } |
| 77 | SkTQSort<double>(inflectT, &inflectT[inflections - 1]); |
| 78 | // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its |
| 79 | // own subroutine? |
| 80 | while (inflections && approximately_less_than_zero(inflectT[0])) { |
| 81 | memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections); |
| 82 | } |
| 83 | int start = 0; |
| 84 | int next = 1; |
| 85 | while (next < inflections) { |
| 86 | if (!approximately_equal(inflectT[start], inflectT[next])) { |
| 87 | ++start; |
| 88 | ++next; |
| 89 | continue; |
| 90 | } |
| 91 | memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start)); |
| 92 | } |
| 93 | |
| 94 | while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) { |
| 95 | --inflections; |
| 96 | } |
| 97 | SkDCubicPair pair; |
| 98 | if (inflections == 1) { |
| 99 | pair = cubic->chopAt(inflectT[0]); |
| 100 | int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics); |
| 101 | if (orderP1 < 2) { |
| 102 | --inflections; |
| 103 | } else { |
| 104 | int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics); |
| 105 | if (orderP2 < 2) { |
| 106 | --inflections; |
| 107 | } |
| 108 | } |
| 109 | } |
| 110 | if (inflections == 0 && add_simple_ts(*cubic, precision, ts)) { |
| 111 | return; |
| 112 | } |
| 113 | if (inflections == 1) { |
| 114 | pair = cubic->chopAt(inflectT[0]); |
| 115 | addTs(pair.first(), precision, 0, inflectT[0], ts); |
| 116 | addTs(pair.second(), precision, inflectT[0], 1, ts); |
| 117 | return; |
| 118 | } |
| 119 | if (inflections > 1) { |
| 120 | SkDCubic part = cubic->subDivide(0, inflectT[0]); |
| 121 | addTs(part, precision, 0, inflectT[0], ts); |
| 122 | int last = inflections - 1; |
| 123 | for (int idx = 0; idx < last; ++idx) { |
| 124 | part = cubic->subDivide(inflectT[idx], inflectT[idx + 1]); |
| 125 | addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts); |
| 126 | } |
| 127 | part = cubic->subDivide(inflectT[last], 1); |
| 128 | addTs(part, precision, inflectT[last], 1, ts); |
| 129 | return; |
| 130 | } |
| 131 | addTs(*cubic, precision, 0, 1, ts); |
| 132 | } |
caryclark@google.com | 818b0cc | 2013-04-08 11:50:46 +0000 | [diff] [blame] | 133 | |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 134 | void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, true>& quads) { |
| 135 | SkTArray<double, true> ts; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 136 | toQuadraticTs(&cubic, precision, &ts); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 137 | if (ts.count() <= 0) { |
caryclark@google.com | 818b0cc | 2013-04-08 11:50:46 +0000 | [diff] [blame] | 138 | SkDQuad quad = cubic.toQuad(); |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 139 | quads.push_back(quad); |
caryclark@google.com | 818b0cc | 2013-04-08 11:50:46 +0000 | [diff] [blame] | 140 | return; |
| 141 | } |
| 142 | double tStart = 0; |
| 143 | for (int i1 = 0; i1 <= ts.count(); ++i1) { |
| 144 | const double tEnd = i1 < ts.count() ? ts[i1] : 1; |
caryclark | aec2510 | 2015-04-29 08:28:30 -0700 | [diff] [blame] | 145 | SkDRect bounds; |
| 146 | bounds.setBounds(cubic); |
caryclark@google.com | 818b0cc | 2013-04-08 11:50:46 +0000 | [diff] [blame] | 147 | SkDCubic part = cubic.subDivide(tStart, tEnd); |
| 148 | SkDQuad quad = part.toQuad(); |
caryclark | aec2510 | 2015-04-29 08:28:30 -0700 | [diff] [blame] | 149 | if (quad[1].fX < bounds.fLeft) { |
| 150 | quad[1].fX = bounds.fLeft; |
| 151 | } else if (quad[1].fX > bounds.fRight) { |
| 152 | quad[1].fX = bounds.fRight; |
| 153 | } |
| 154 | if (quad[1].fY < bounds.fTop) { |
| 155 | quad[1].fY = bounds.fTop; |
| 156 | } else if (quad[1].fY > bounds.fBottom) { |
| 157 | quad[1].fY = bounds.fBottom; |
| 158 | } |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 159 | quads.push_back(quad); |
caryclark@google.com | 818b0cc | 2013-04-08 11:50:46 +0000 | [diff] [blame] | 160 | tStart = tEnd; |
| 161 | } |
| 162 | } |
caryclark@google.com | 8d0a524 | 2013-07-16 16:11:16 +0000 | [diff] [blame] | 163 | |
caryclark | e4097e3 | 2014-06-18 07:24:19 -0700 | [diff] [blame] | 164 | void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) { |
| 165 | quadPath->reset(); |
| 166 | SkDCubic cubic; |
| 167 | SkTArray<SkDQuad, true> quads; |
| 168 | SkPath::RawIter iter(cubicPath); |
| 169 | uint8_t verb; |
| 170 | SkPoint pts[4]; |
| 171 | while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { |
| 172 | switch (verb) { |
| 173 | case SkPath::kMove_Verb: |
| 174 | quadPath->moveTo(pts[0].fX, pts[0].fY); |
| 175 | continue; |
| 176 | case SkPath::kLine_Verb: |
| 177 | quadPath->lineTo(pts[1].fX, pts[1].fY); |
| 178 | break; |
| 179 | case SkPath::kQuad_Verb: |
| 180 | quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); |
| 181 | break; |
| 182 | case SkPath::kCubic_Verb: |
| 183 | quads.reset(); |
| 184 | cubic.set(pts); |
| 185 | CubicToQuads(cubic, cubic.calcPrecision(), quads); |
| 186 | for (int index = 0; index < quads.count(); ++index) { |
| 187 | SkPoint qPts[2] = { |
| 188 | quads[index][1].asSkPoint(), |
| 189 | quads[index][2].asSkPoint() |
| 190 | }; |
| 191 | quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY); |
| 192 | } |
| 193 | break; |
| 194 | case SkPath::kClose_Verb: |
| 195 | quadPath->close(); |
| 196 | break; |
| 197 | default: |
| 198 | SkDEBUGFAIL("bad verb"); |
| 199 | return; |
| 200 | } |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) { |
| 205 | simplePath->reset(); |
| 206 | SkDCubic cubic; |
| 207 | SkPath::RawIter iter(cubicPath); |
| 208 | uint8_t verb; |
| 209 | SkPoint pts[4]; |
| 210 | while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { |
| 211 | switch (verb) { |
| 212 | case SkPath::kMove_Verb: |
| 213 | simplePath->moveTo(pts[0].fX, pts[0].fY); |
| 214 | continue; |
| 215 | case SkPath::kLine_Verb: |
| 216 | simplePath->lineTo(pts[1].fX, pts[1].fY); |
| 217 | break; |
| 218 | case SkPath::kQuad_Verb: |
| 219 | simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); |
| 220 | break; |
| 221 | case SkPath::kCubic_Verb: { |
| 222 | cubic.set(pts); |
| 223 | double tInflects[2]; |
| 224 | int inflections = cubic.findInflections(tInflects); |
| 225 | if (inflections > 1 && tInflects[0] > tInflects[1]) { |
| 226 | SkTSwap(tInflects[0], tInflects[1]); |
| 227 | } |
| 228 | double lo = 0; |
| 229 | for (int index = 0; index <= inflections; ++index) { |
| 230 | double hi = index < inflections ? tInflects[index] : 1; |
| 231 | SkDCubic part = cubic.subDivide(lo, hi); |
| 232 | SkPoint cPts[3]; |
| 233 | cPts[0] = part[1].asSkPoint(); |
| 234 | cPts[1] = part[2].asSkPoint(); |
| 235 | cPts[2] = part[3].asSkPoint(); |
| 236 | simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY, |
| 237 | cPts[2].fX, cPts[2].fY); |
| 238 | lo = hi; |
| 239 | } |
| 240 | break; |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 241 | } |
caryclark | e4097e3 | 2014-06-18 07:24:19 -0700 | [diff] [blame] | 242 | case SkPath::kClose_Verb: |
| 243 | simplePath->close(); |
| 244 | break; |
| 245 | default: |
| 246 | SkDEBUGFAIL("bad verb"); |
| 247 | return; |
| 248 | } |
| 249 | } |
| 250 | } |
| 251 | |
caryclark@google.com | 8d0a524 | 2013-07-16 16:11:16 +0000 | [diff] [blame] | 252 | bool ValidBounds(const SkPathOpsBounds& bounds) { |
| 253 | if (SkScalarIsNaN(bounds.fLeft)) { |
| 254 | return false; |
| 255 | } |
| 256 | if (SkScalarIsNaN(bounds.fTop)) { |
| 257 | return false; |
| 258 | } |
| 259 | if (SkScalarIsNaN(bounds.fRight)) { |
| 260 | return false; |
| 261 | } |
| 262 | return !SkScalarIsNaN(bounds.fBottom); |
| 263 | } |
| 264 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 265 | bool ValidConic(const SkDConic& conic) { |
| 266 | for (int index = 0; index < SkDConic::kPointCount; ++index) { |
| 267 | if (!ValidPoint(conic[index])) { |
| 268 | return false; |
| 269 | } |
| 270 | } |
| 271 | if (SkDoubleIsNaN(conic.fWeight)) { |
| 272 | return false; |
| 273 | } |
| 274 | return true; |
| 275 | } |
| 276 | |
caryclark@google.com | 8d0a524 | 2013-07-16 16:11:16 +0000 | [diff] [blame] | 277 | bool ValidCubic(const SkDCubic& cubic) { |
| 278 | for (int index = 0; index < 4; ++index) { |
| 279 | if (!ValidPoint(cubic[index])) { |
| 280 | return false; |
| 281 | } |
| 282 | } |
| 283 | return true; |
| 284 | } |
| 285 | |
| 286 | bool ValidLine(const SkDLine& line) { |
| 287 | for (int index = 0; index < 2; ++index) { |
| 288 | if (!ValidPoint(line[index])) { |
| 289 | return false; |
| 290 | } |
| 291 | } |
| 292 | return true; |
| 293 | } |
| 294 | |
| 295 | bool ValidPoint(const SkDPoint& pt) { |
| 296 | if (SkDoubleIsNaN(pt.fX)) { |
| 297 | return false; |
| 298 | } |
skia.committer@gmail.com | eebe6f4 | 2013-07-17 07:01:13 +0000 | [diff] [blame] | 299 | return !SkDoubleIsNaN(pt.fY); |
caryclark@google.com | 8d0a524 | 2013-07-16 16:11:16 +0000 | [diff] [blame] | 300 | } |
| 301 | |
| 302 | bool ValidPoints(const SkPoint* pts, int count) { |
| 303 | for (int index = 0; index < count; ++index) { |
| 304 | if (SkScalarIsNaN(pts[index].fX)) { |
| 305 | return false; |
| 306 | } |
| 307 | if (SkScalarIsNaN(pts[index].fY)) { |
| 308 | return false; |
| 309 | } |
| 310 | } |
| 311 | return true; |
| 312 | } |
| 313 | |
| 314 | bool ValidQuad(const SkDQuad& quad) { |
| 315 | for (int index = 0; index < 3; ++index) { |
| 316 | if (!ValidPoint(quad[index])) { |
| 317 | return false; |
| 318 | } |
| 319 | } |
| 320 | return true; |
| 321 | } |
| 322 | |
caryclark@google.com | 8d0a524 | 2013-07-16 16:11:16 +0000 | [diff] [blame] | 323 | bool ValidVector(const SkDVector& v) { |
| 324 | if (SkDoubleIsNaN(v.fX)) { |
| 325 | return false; |
| 326 | } |
skia.committer@gmail.com | eebe6f4 | 2013-07-17 07:01:13 +0000 | [diff] [blame] | 327 | return !SkDoubleIsNaN(v.fY); |
caryclark@google.com | 8d0a524 | 2013-07-16 16:11:16 +0000 | [diff] [blame] | 328 | } |