1 /* 2 * Copyright 2018 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 "SkOpEdgeBuilder.h" 8 #include "SkPathOpsCommon.h" 9 #include "SkRect.h" 10 #include <algorithm> 11 #include <vector> 12 13 using std::vector; 14 15 struct Contour { 16 enum class Direction { // SkPath::Direction doesn't have 'none' state 17 kCCW = -1, 18 kNone, 19 kCW, 20 }; 21 22 Contour(const SkRect& bounds, int lastStart, int verbStart) 23 : fBounds(bounds) 24 , fVerbStart(lastStart) 25 , fVerbEnd(verbStart) { 26 } 27 28 vector<Contour*> fChildren; 29 const SkRect fBounds; 30 SkPoint fMinXY{SK_ScalarMax, SK_ScalarMax}; 31 const int fVerbStart; 32 const int fVerbEnd; 33 Direction fDirection{Direction::kNone}; 34 bool fContained{false}; 35 bool fReverse{false}; 36 }; 37 38 static const int kPtCount[] = { 1, 1, 2, 2, 3, 0 }; 39 static const int kPtIndex[] = { 0, 1, 1, 1, 1, 0 }; 40 41 static Contour::Direction to_direction(SkScalar dy) { 42 return dy > 0 ? Contour::Direction::kCCW : dy < 0 ? Contour::Direction::kCW : 43 Contour::Direction::kNone; 44 } 45 46 static int contains_edge(SkPoint pts[4], SkPath::Verb verb, SkScalar weight, const SkPoint& edge) { 47 SkRect bounds; 48 bounds.set(pts, kPtCount[verb] + 1); 49 if (bounds.fTop > edge.fY) { 50 return 0; 51 } 52 if (bounds.fBottom <= edge.fY) { // check to see if y is at line end to avoid double counting 53 return 0; 54 } 55 if (bounds.fLeft >= edge.fX) { 56 return 0; 57 } 58 int winding = 0; 59 double tVals[3]; 60 Contour::Direction directions[3]; 61 // must intersect horz ray with curve in case it intersects more than once 62 int count = (*CurveIntercept[verb * 2])(pts, weight, edge.fY, tVals); 63 SkASSERT(between(0, count, 3)); 64 // remove results to the right of edge 65 for (int index = 0; index < count; ) { 66 SkScalar intersectX = (*CurvePointAtT[verb])(pts, weight, tVals[index]).fX; 67 if (intersectX < edge.fX) { 68 ++index; 69 continue; 70 } 71 if (intersectX > edge.fX) { 72 tVals[index] = tVals[--count]; 73 continue; 74 } 75 // if intersect x equals edge x, we need to determine if pts is to the left or right of edge 76 if (pts[0].fX < edge.fX && pts[kPtCount[verb]].fX < edge.fX) { 77 ++index; 78 continue; 79 } 80 // TODO : other cases need discriminating. need op angle code to figure it out 81 // example: edge ends 45 degree diagonal going up. If pts is to the left of edge, keep. 82 // if pts is to the right of edge, discard. With code as is, can't distiguish the two cases. 83 tVals[index] = tVals[--count]; 84 } 85 // use first derivative to determine if intersection is contributing +1 or -1 to winding 86 for (int index = 0; index < count; ++index) { 87 directions[index] = to_direction((*CurveSlopeAtT[verb])(pts, weight, tVals[index]).fY); 88 } 89 for (int index = 0; index < count; ++index) { 90 // skip intersections that end at edge and go up 91 if (zero_or_one(tVals[index]) && Contour::Direction::kCCW != directions[index]) { 92 continue; 93 } 94 winding += (int) directions[index]; 95 } 96 return winding; // note winding indicates containership, not contour direction 97 } 98 99 static SkScalar conic_weight(const SkPath::Iter& iter, SkPath::Verb verb) { 100 return SkPath::kConic_Verb == verb ? iter.conicWeight() : 1; 101 } 102 103 static SkPoint left_edge(SkPoint pts[4], SkPath::Verb verb, SkScalar weight, 104 Contour::Direction* direction) { 105 SkASSERT(SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb); 106 SkPoint result; 107 double dy; 108 double t SK_INIT_TO_AVOID_WARNING; 109 int roots = 0; 110 if (SkPath::kLine_Verb == verb) { 111 result = pts[0].fX < pts[1].fX ? pts[0] : pts[1]; 112 dy = pts[1].fY - pts[0].fY; 113 } else if (SkPath::kQuad_Verb == verb) { 114 SkDQuad quad; 115 quad.set(pts); 116 if (!quad.monotonicInX()) { 117 roots = SkDQuad::FindExtrema(&quad[0].fX, &t); 118 } 119 if (roots) { 120 result = quad.ptAtT(t).asSkPoint(); 121 } else { 122 result = pts[0].fX < pts[2].fX ? pts[0] : pts[2]; 123 t = pts[0].fX < pts[2].fX ? 0 : 1; 124 } 125 dy = quad.dxdyAtT(t).fY; 126 } else if (SkPath::kConic_Verb == verb) { 127 SkDConic conic; 128 conic.set(pts, weight); 129 if (!conic.monotonicInX()) { 130 roots = SkDConic::FindExtrema(&conic[0].fX, weight, &t); 131 } 132 if (roots) { 133 result = conic.ptAtT(t).asSkPoint(); 134 } else { 135 result = pts[0].fX < pts[2].fX ? pts[0] : pts[2]; 136 t = pts[0].fX < pts[2].fX ? 0 : 1; 137 } 138 dy = conic.dxdyAtT(t).fY; 139 } else { 140 SkASSERT(SkPath::kCubic_Verb == verb); 141 SkDCubic cubic; 142 cubic.set(pts); 143 if (!cubic.monotonicInX()) { 144 double tValues[2]; 145 roots = SkDCubic::FindExtrema(&cubic[0].fX, tValues); 146 SkASSERT(roots <= 2); 147 for (int index = 0; index < roots; ++index) { 148 SkPoint temp = cubic.ptAtT(tValues[index]).asSkPoint(); 149 if (0 == index || result.fX > temp.fX) { 150 result = temp; 151 t = tValues[index]; 152 } 153 } 154 } 155 if (roots) { 156 result = cubic.ptAtT(t).asSkPoint(); 157 } else { 158 result = pts[0].fX < pts[3].fX ? pts[0] : pts[3]; 159 t = pts[0].fX < pts[3].fX ? 0 : 1; 160 } 161 dy = cubic.dxdyAtT(t).fY; 162 } 163 *direction = to_direction(dy); 164 return result; 165 } 166 167 class OpAsWinding { 168 public: 169 enum class Edge { 170 kInitial, 171 kCompare, 172 }; 173 174 OpAsWinding(const SkPath& path) 175 : fPath(path) { 176 } 177 178 void contourBounds(vector<Contour>* containers) { 179 SkRect bounds; 180 bounds.setEmpty(); 181 SkPath::RawIter iter(fPath); 182 SkPoint pts[4]; 183 SkPath::Verb verb; 184 int lastStart = 0; 185 int verbStart = 0; 186 do { 187 verb = iter.next(pts); 188 if (SkPath::kMove_Verb == verb) { 189 if (!bounds.isEmpty()) { 190 containers->emplace_back(bounds, lastStart, verbStart); 191 lastStart = verbStart; 192 } 193 bounds.setBounds(&pts[kPtIndex[verb]], kPtCount[verb]); 194 } 195 if (SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb) { 196 SkRect verbBounds; 197 verbBounds.setBounds(&pts[kPtIndex[verb]], kPtCount[verb]); 198 bounds.joinPossiblyEmptyRect(verbBounds); 199 } 200 ++verbStart; 201 } while (SkPath::kDone_Verb != verb); 202 if (!bounds.isEmpty()) { 203 containers->emplace_back(bounds, lastStart, verbStart); 204 } 205 } 206 207 int nextEdge(Contour& contour, Edge edge) { 208 SkPath::Iter iter(fPath, true); 209 SkPoint pts[4]; 210 SkPath::Verb verb; 211 int verbCount = -1; 212 int winding = 0; 213 do { 214 verb = iter.next(pts); 215 if (++verbCount < contour.fVerbStart) { 216 continue; 217 } 218 if (verbCount >= contour.fVerbEnd) { 219 continue; 220 } 221 if (SkPath::kLine_Verb > verb || verb > SkPath::kCubic_Verb) { 222 continue; 223 } 224 bool horizontal = true; 225 for (int index = 1; index <= kPtCount[verb]; ++index) { 226 if (pts[0].fY != pts[index].fY) { 227 horizontal = false; 228 break; 229 } 230 } 231 if (horizontal) { 232 continue; 233 } 234 if (edge == Edge::kCompare) { 235 winding += contains_edge(pts, verb, conic_weight(iter, verb), contour.fMinXY); 236 continue; 237 } 238 SkASSERT(edge == Edge::kInitial); 239 Contour::Direction direction; 240 SkPoint minXY = left_edge(pts, verb, conic_weight(iter, verb), &direction); 241 if (minXY.fX > contour.fMinXY.fX) { 242 continue; 243 } 244 if (minXY.fX == contour.fMinXY.fX) { 245 if (minXY.fY != contour.fMinXY.fY) { 246 continue; 247 } 248 if (direction == contour.fDirection) { 249 continue; 250 } 251 // incomplete: must sort edges to find the one most to left 252 // File a bug if this code path is triggered and AsWinding was 253 // expected to succeed. 254 SkDEBUGF("incomplete\n"); 255 // TODO: add edges as opangle and sort 256 } 257 contour.fMinXY = minXY; 258 contour.fDirection = direction; 259 } while (SkPath::kDone_Verb != verb); 260 return winding; 261 } 262 263 bool containerContains(Contour& contour, Contour& test) { 264 // find outside point on lesser contour 265 // arbitrarily, choose non-horizontal edge where point <= bounds left 266 // note that if leftmost point is control point, may need tight bounds 267 // to find edge with minimum-x 268 if (SK_ScalarMax == test.fMinXY.fX) { 269 this->nextEdge(test, Edge::kInitial); 270 } 271 // find all edges on greater equal or to the left of one on lesser 272 contour.fMinXY = test.fMinXY; 273 int winding = this->nextEdge(contour, Edge::kCompare); 274 // if edge is up, mark contour cw, otherwise, ccw 275 // sum of greater edges direction should be cw, 0, ccw 276 test.fContained = winding != 0; 277 return -1 <= winding && winding <= 1; 278 } 279 280 void inParent(Contour& contour, Contour& parent) { 281 // move contour into sibling list contained by parent 282 for (auto test : parent.fChildren) { 283 if (test->fBounds.contains(contour.fBounds)) { 284 inParent(contour, *test); 285 return; 286 } 287 } 288 // move parent's children into contour's children if contained by contour 289 for (auto iter = parent.fChildren.begin(); iter != parent.fChildren.end(); ) { 290 if (contour.fBounds.contains((*iter)->fBounds)) { 291 contour.fChildren.push_back(*iter); 292 iter = parent.fChildren.erase(iter); 293 continue; 294 } 295 ++iter; 296 } 297 parent.fChildren.push_back(&contour); 298 } 299 300 bool checkContainerChildren(Contour* parent, Contour* child) { 301 for (auto grandChild : child->fChildren) { 302 if (!checkContainerChildren(child, grandChild)) { 303 return false; 304 } 305 } 306 if (parent) { 307 if (!containerContains(*parent, *child)) { 308 return false; 309 } 310 } 311 return true; 312 } 313 314 bool markReverse(Contour* parent, Contour* child) { 315 bool reversed = false; 316 for (auto grandChild : child->fChildren) { 317 reversed |= markReverse(grandChild->fContained ? child : parent, grandChild); 318 } 319 if (parent && parent->fDirection == child->fDirection) { 320 child->fReverse = true; 321 child->fDirection = (Contour::Direction) -(int) child->fDirection; 322 return true; 323 } 324 return reversed; 325 } 326 327 void reverseMarkedContours(vector<Contour>& contours, SkPath* result) { 328 SkPath::RawIter iter(fPath); 329 int verbCount = 0; 330 for (auto contour : contours) { 331 SkPath reverse; 332 SkPath* temp = contour.fReverse ? &reverse : result; 333 do { 334 SkPoint pts[4]; 335 switch (iter.next(pts)) { 336 case SkPath::kMove_Verb: 337 temp->moveTo(pts[0]); 338 break; 339 case SkPath::kLine_Verb: 340 temp->lineTo(pts[1]); 341 break; 342 case SkPath::kQuad_Verb: 343 temp->quadTo(pts[1], pts[2]); 344 break; 345 case SkPath::kConic_Verb: 346 temp->conicTo(pts[1], pts[2], iter.conicWeight()); 347 break; 348 case SkPath::kCubic_Verb: 349 temp->cubicTo(pts[1], pts[2], pts[3]); 350 break; 351 case SkPath::kClose_Verb: 352 temp->close(); 353 break; 354 case SkPath::kDone_Verb: 355 break; 356 default: 357 SkASSERT(0); 358 } 359 } while (++verbCount < contour.fVerbEnd); 360 if (contour.fReverse) { 361 result->reverseAddPath(reverse); 362 } 363 } 364 } 365 366 private: 367 const SkPath& fPath; 368 }; 369 370 static bool set_result_path(SkPath* result, const SkPath& path, SkPath::FillType fillType) { 371 *result = path; 372 result->setFillType(fillType); 373 return true; 374 } 375 376 bool SK_API AsWinding(const SkPath& path, SkPath* result) { 377 if (!path.isFinite()) { 378 return false; 379 } 380 SkPath::FillType fillType = path.getFillType(); 381 if (fillType == SkPath::kWinding_FillType 382 || fillType == SkPath::kInverseWinding_FillType ) { 383 return set_result_path(result, path, fillType); 384 } 385 fillType = path.isInverseFillType() ? SkPath::kInverseWinding_FillType : 386 SkPath::kWinding_FillType; 387 if (path.isEmpty() || path.isConvex()) { 388 return set_result_path(result, path, fillType); 389 } 390 // count contours 391 vector<Contour> contours; // one per contour 392 OpAsWinding winder(path); 393 winder.contourBounds(&contours); 394 if (contours.size() <= 1) { 395 return set_result_path(result, path, fillType); 396 } 397 // create contour bounding box tree 398 Contour sorted(SkRect(), 0, 0); 399 for (auto& contour : contours) { 400 winder.inParent(contour, sorted); 401 } 402 // if sorted has no grandchildren, no child has to fix its children's winding 403 if (std::all_of(sorted.fChildren.begin(), sorted.fChildren.end(), 404 [](const Contour* contour) -> bool { return !contour->fChildren.size(); } )) { 405 return set_result_path(result, path, fillType); 406 } 407 // starting with outermost and moving inward, see if one path contains another 408 for (auto contour : sorted.fChildren) { 409 winder.nextEdge(*contour, OpAsWinding::Edge::kInitial); 410 if (!winder.checkContainerChildren(nullptr, contour)) { 411 return false; 412 } 413 } 414 // starting with outermost and moving inward, mark paths to reverse 415 bool reversed = false; 416 for (auto contour : sorted.fChildren) { 417 reversed |= winder.markReverse(nullptr, contour); 418 } 419 if (!reversed) { 420 return set_result_path(result, path, fillType); 421 } 422 SkPath temp; 423 temp.setFillType(fillType); 424 winder.reverseMarkedContours(contours, &temp); 425 result->swap(temp); 426 return true; 427 } 428