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