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 "SkPathOpsTSect.h" 14 #include "SkReduceOrder.h" 15 #include "SkTSort.h" 16 17 #include <utility> 18 19 static double calc_t_div(const SkDCubic& cubic, double precision, double start) { 20 const double adjust = sqrt(3.) / 36; 21 SkDCubic sub; 22 const SkDCubic* cPtr; 23 if (start == 0) { 24 cPtr = &cubic; 25 } else { 26 // OPTIMIZE: special-case half-split ? 27 sub = cubic.subDivide(start, 1); 28 cPtr = ⊂ 29 } 30 const SkDCubic& c = *cPtr; 31 double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX; 32 double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY; 33 double dist = sqrt(dx * dx + dy * dy); 34 double tDiv3 = precision / (adjust * dist); 35 double t = SkDCubeRoot(tDiv3); 36 if (start > 0) { 37 t = start + (1 - start) * t; 38 } 39 return t; 40 } 41 42 static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) { 43 double tDiv = calc_t_div(cubic, precision, 0); 44 if (tDiv >= 1) { 45 return true; 46 } 47 if (tDiv >= 0.5) { 48 ts->push_back(0.5); 49 return true; 50 } 51 return false; 52 } 53 54 static void addTs(const SkDCubic& cubic, double precision, double start, double end, 55 SkTArray<double, true>* ts) { 56 double tDiv = calc_t_div(cubic, precision, 0); 57 double parts = ceil(1.0 / tDiv); 58 for (double index = 0; index < parts; ++index) { 59 double newT = start + (index / parts) * (end - start); 60 if (newT > 0 && newT < 1) { 61 ts->push_back(newT); 62 } 63 } 64 } 65 66 static void toQuadraticTs(const SkDCubic* cubic, double precision, SkTArray<double, true>* ts) { 67 SkReduceOrder reducer; 68 int order = reducer.reduce(*cubic, SkReduceOrder::kAllow_Quadratics); 69 if (order < 3) { 70 return; 71 } 72 double inflectT[5]; 73 int inflections = cubic->findInflections(inflectT); 74 SkASSERT(inflections <= 2); 75 if (!cubic->endsAreExtremaInXOrY()) { 76 inflections += cubic->findMaxCurvature(&inflectT[inflections]); 77 SkASSERT(inflections <= 5); 78 } 79 SkTQSort<double>(inflectT, &inflectT[inflections - 1]); 80 // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its 81 // own subroutine? 82 while (inflections && approximately_less_than_zero(inflectT[0])) { 83 memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections); 84 } 85 int start = 0; 86 int next = 1; 87 while (next < inflections) { 88 if (!approximately_equal(inflectT[start], inflectT[next])) { 89 ++start; 90 ++next; 91 continue; 92 } 93 memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start)); 94 } 95 96 while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) { 97 --inflections; 98 } 99 SkDCubicPair pair; 100 if (inflections == 1) { 101 pair = cubic->chopAt(inflectT[0]); 102 int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics); 103 if (orderP1 < 2) { 104 --inflections; 105 } else { 106 int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics); 107 if (orderP2 < 2) { 108 --inflections; 109 } 110 } 111 } 112 if (inflections == 0 && add_simple_ts(*cubic, precision, ts)) { 113 return; 114 } 115 if (inflections == 1) { 116 pair = cubic->chopAt(inflectT[0]); 117 addTs(pair.first(), precision, 0, inflectT[0], ts); 118 addTs(pair.second(), precision, inflectT[0], 1, ts); 119 return; 120 } 121 if (inflections > 1) { 122 SkDCubic part = cubic->subDivide(0, inflectT[0]); 123 addTs(part, precision, 0, inflectT[0], ts); 124 int last = inflections - 1; 125 for (int idx = 0; idx < last; ++idx) { 126 part = cubic->subDivide(inflectT[idx], inflectT[idx + 1]); 127 addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts); 128 } 129 part = cubic->subDivide(inflectT[last], 1); 130 addTs(part, precision, inflectT[last], 1, ts); 131 return; 132 } 133 addTs(*cubic, precision, 0, 1, ts); 134 } 135 136 void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, true>& quads) { 137 SkTArray<double, true> ts; 138 toQuadraticTs(&cubic, precision, &ts); 139 if (ts.count() <= 0) { 140 SkDQuad quad = cubic.toQuad(); 141 quads.push_back(quad); 142 return; 143 } 144 double tStart = 0; 145 for (int i1 = 0; i1 <= ts.count(); ++i1) { 146 const double tEnd = i1 < ts.count() ? ts[i1] : 1; 147 SkDRect bounds; 148 bounds.setBounds(cubic); 149 SkDCubic part = cubic.subDivide(tStart, tEnd); 150 SkDQuad quad = part.toQuad(); 151 if (quad[1].fX < bounds.fLeft) { 152 quad[1].fX = bounds.fLeft; 153 } else if (quad[1].fX > bounds.fRight) { 154 quad[1].fX = bounds.fRight; 155 } 156 if (quad[1].fY < bounds.fTop) { 157 quad[1].fY = bounds.fTop; 158 } else if (quad[1].fY > bounds.fBottom) { 159 quad[1].fY = bounds.fBottom; 160 } 161 quads.push_back(quad); 162 tStart = tEnd; 163 } 164 } 165 166 void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) { 167 quadPath->reset(); 168 SkDCubic cubic; 169 SkTArray<SkDQuad, true> quads; 170 SkPath::RawIter iter(cubicPath); 171 uint8_t verb; 172 SkPoint pts[4]; 173 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 174 switch (verb) { 175 case SkPath::kMove_Verb: 176 quadPath->moveTo(pts[0].fX, pts[0].fY); 177 continue; 178 case SkPath::kLine_Verb: 179 quadPath->lineTo(pts[1].fX, pts[1].fY); 180 break; 181 case SkPath::kQuad_Verb: 182 quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); 183 break; 184 case SkPath::kCubic_Verb: 185 quads.reset(); 186 cubic.set(pts); 187 CubicToQuads(cubic, cubic.calcPrecision(), quads); 188 for (int index = 0; index < quads.count(); ++index) { 189 SkPoint qPts[2] = { 190 quads[index][1].asSkPoint(), 191 quads[index][2].asSkPoint() 192 }; 193 quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY); 194 } 195 break; 196 case SkPath::kClose_Verb: 197 quadPath->close(); 198 break; 199 default: 200 SkDEBUGFAIL("bad verb"); 201 return; 202 } 203 } 204 } 205 206 void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) { 207 simplePath->reset(); 208 SkDCubic cubic; 209 SkPath::RawIter iter(cubicPath); 210 uint8_t verb; 211 SkPoint pts[4]; 212 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 213 switch (verb) { 214 case SkPath::kMove_Verb: 215 simplePath->moveTo(pts[0].fX, pts[0].fY); 216 continue; 217 case SkPath::kLine_Verb: 218 simplePath->lineTo(pts[1].fX, pts[1].fY); 219 break; 220 case SkPath::kQuad_Verb: 221 simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); 222 break; 223 case SkPath::kCubic_Verb: { 224 cubic.set(pts); 225 double tInflects[2]; 226 int inflections = cubic.findInflections(tInflects); 227 if (inflections > 1 && tInflects[0] > tInflects[1]) { 228 using std::swap; 229 swap(tInflects[0], tInflects[1]); 230 } 231 double lo = 0; 232 for (int index = 0; index <= inflections; ++index) { 233 double hi = index < inflections ? tInflects[index] : 1; 234 SkDCubic part = cubic.subDivide(lo, hi); 235 SkPoint cPts[3]; 236 cPts[0] = part[1].asSkPoint(); 237 cPts[1] = part[2].asSkPoint(); 238 cPts[2] = part[3].asSkPoint(); 239 simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY, 240 cPts[2].fX, cPts[2].fY); 241 lo = hi; 242 } 243 break; 244 } 245 case SkPath::kClose_Verb: 246 simplePath->close(); 247 break; 248 default: 249 SkDEBUGFAIL("bad verb"); 250 return; 251 } 252 } 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
