SkPathOpsAsWinding.cpp 15 KB

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