SkPathOpsOp.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382
  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 "src/pathops/SkAddIntersections.h"
  8. #include "src/pathops/SkOpCoincidence.h"
  9. #include "src/pathops/SkOpEdgeBuilder.h"
  10. #include "src/pathops/SkPathOpsCommon.h"
  11. #include "src/pathops/SkPathWriter.h"
  12. #include <utility>
  13. static bool findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
  14. SkOpSpanBase** endPtr, SkOpSegment** result) {
  15. while (chase.count()) {
  16. SkOpSpanBase* span;
  17. chase.pop(&span);
  18. // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
  19. *startPtr = span->ptT()->prev()->span();
  20. SkOpSegment* segment = (*startPtr)->segment();
  21. bool done = true;
  22. *endPtr = nullptr;
  23. if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
  24. *startPtr = last->start();
  25. *endPtr = last->end();
  26. #if TRY_ROTATE
  27. *chase.insert(0) = span;
  28. #else
  29. *chase.append() = span;
  30. #endif
  31. *result = last->segment();
  32. return true;
  33. }
  34. if (done) {
  35. continue;
  36. }
  37. int winding;
  38. bool sortable;
  39. const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
  40. if (!angle) {
  41. *result = nullptr;
  42. return true;
  43. }
  44. if (winding == SK_MinS32) {
  45. continue;
  46. }
  47. int sumMiWinding, sumSuWinding;
  48. if (sortable) {
  49. segment = angle->segment();
  50. sumMiWinding = segment->updateWindingReverse(angle);
  51. if (sumMiWinding == SK_MinS32) {
  52. SkASSERT(segment->globalState()->debugSkipAssert());
  53. *result = nullptr;
  54. return true;
  55. }
  56. sumSuWinding = segment->updateOppWindingReverse(angle);
  57. if (sumSuWinding == SK_MinS32) {
  58. SkASSERT(segment->globalState()->debugSkipAssert());
  59. *result = nullptr;
  60. return true;
  61. }
  62. if (segment->operand()) {
  63. using std::swap;
  64. swap(sumMiWinding, sumSuWinding);
  65. }
  66. }
  67. SkOpSegment* first = nullptr;
  68. const SkOpAngle* firstAngle = angle;
  69. while ((angle = angle->next()) != firstAngle) {
  70. segment = angle->segment();
  71. SkOpSpanBase* start = angle->start();
  72. SkOpSpanBase* end = angle->end();
  73. int maxWinding = 0, sumWinding = 0, oppMaxWinding = 0, oppSumWinding = 0;
  74. if (sortable) {
  75. segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
  76. &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
  77. }
  78. if (!segment->done(angle)) {
  79. if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
  80. first = segment;
  81. *startPtr = start;
  82. *endPtr = end;
  83. }
  84. // OPTIMIZATION: should this also add to the chase?
  85. if (sortable) {
  86. if (!segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
  87. oppSumWinding, angle, nullptr)) {
  88. return false;
  89. }
  90. }
  91. }
  92. }
  93. if (first) {
  94. #if TRY_ROTATE
  95. *chase.insert(0) = span;
  96. #else
  97. *chase.append() = span;
  98. #endif
  99. *result = first;
  100. return true;
  101. }
  102. }
  103. *result = nullptr;
  104. return true;
  105. }
  106. static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
  107. const int xorMask, const int xorOpMask, SkPathWriter* writer) {
  108. bool unsortable = false;
  109. bool lastSimple = false;
  110. bool simple = false;
  111. do {
  112. SkOpSpan* span = FindSortableTop(contourList);
  113. if (!span) {
  114. break;
  115. }
  116. SkOpSegment* current = span->segment();
  117. SkOpSpanBase* start = span->next();
  118. SkOpSpanBase* end = span;
  119. SkTDArray<SkOpSpanBase*> chase;
  120. do {
  121. if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
  122. do {
  123. if (!unsortable && current->done()) {
  124. break;
  125. }
  126. SkASSERT(unsortable || !current->done());
  127. SkOpSpanBase* nextStart = start;
  128. SkOpSpanBase* nextEnd = end;
  129. lastSimple = simple;
  130. SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
  131. &unsortable, &simple, op, xorMask, xorOpMask);
  132. if (!next) {
  133. if (!unsortable && writer->hasMove()
  134. && current->verb() != SkPath::kLine_Verb
  135. && !writer->isClosed()) {
  136. if (!current->addCurveTo(start, end, writer)) {
  137. return false;
  138. }
  139. if (!writer->isClosed()) {
  140. SkPathOpsDebug::ShowActiveSpans(contourList);
  141. }
  142. } else if (lastSimple) {
  143. if (!current->addCurveTo(start, end, writer)) {
  144. return false;
  145. }
  146. }
  147. break;
  148. }
  149. #if DEBUG_FLOW
  150. SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
  151. current->debugID(), start->pt().fX, start->pt().fY,
  152. end->pt().fX, end->pt().fY);
  153. #endif
  154. if (!current->addCurveTo(start, end, writer)) {
  155. return false;
  156. }
  157. current = next;
  158. start = nextStart;
  159. end = nextEnd;
  160. } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
  161. if (current->activeWinding(start, end) && !writer->isClosed()) {
  162. SkOpSpan* spanStart = start->starter(end);
  163. if (!spanStart->done()) {
  164. if (!current->addCurveTo(start, end, writer)) {
  165. return false;
  166. }
  167. current->markDone(spanStart);
  168. }
  169. }
  170. writer->finishContour();
  171. } else {
  172. SkOpSpanBase* last;
  173. if (!current->markAndChaseDone(start, end, &last)) {
  174. return false;
  175. }
  176. if (last && !last->chased()) {
  177. last->setChased(true);
  178. SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
  179. *chase.append() = last;
  180. #if DEBUG_WINDING
  181. SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
  182. if (!last->final()) {
  183. SkDebugf(" windSum=%d", last->upCast()->windSum());
  184. }
  185. SkDebugf("\n");
  186. #endif
  187. }
  188. }
  189. if (!findChaseOp(chase, &start, &end, &current)) {
  190. return false;
  191. }
  192. SkPathOpsDebug::ShowActiveSpans(contourList);
  193. if (!current) {
  194. break;
  195. }
  196. } while (true);
  197. } while (true);
  198. return true;
  199. }
  200. // diagram of why this simplifcation is possible is here:
  201. // https://skia.org/dev/present/pathops link at bottom of the page
  202. // https://drive.google.com/file/d/0BwoLUwz9PYkHLWpsaXd0UDdaN00/view?usp=sharing
  203. static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
  204. // inside minuend outside minuend
  205. // inside subtrahend outside subtrahend inside subtrahend outside subtrahend
  206. {{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
  207. {{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
  208. {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }},
  209. {{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }},
  210. {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }},
  211. };
  212. static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
  213. {{ false, false }, { true, false }}, // diff
  214. {{ false, false }, { false, true }}, // sect
  215. {{ false, true }, { true, true }}, // union
  216. {{ false, true }, { true, false }}, // xor
  217. {{ false, true }, { false, false }}, // rev diff
  218. };
  219. #if DEBUG_T_SECT_LOOP_COUNT
  220. #include "include/private/SkMutex.h"
  221. SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr));
  222. void ReportPathOpsDebugging() {
  223. debugWorstState.debugLoopReport();
  224. }
  225. extern void (*gVerboseFinalize)();
  226. #endif
  227. bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
  228. SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
  229. #if DEBUG_DUMP_VERIFY
  230. #ifndef SK_DEBUG
  231. const char* testName = "release";
  232. #endif
  233. if (SkPathOpsDebug::gDumpOp) {
  234. SkPathOpsDebug::DumpOp(one, two, op, testName);
  235. }
  236. #endif
  237. op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
  238. bool inverseFill = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()];
  239. SkPath::FillType fillType = inverseFill ? SkPath::kInverseEvenOdd_FillType :
  240. SkPath::kEvenOdd_FillType;
  241. SkRect rect1, rect2;
  242. if (kIntersect_SkPathOp == op && one.isRect(&rect1) && two.isRect(&rect2)) {
  243. result->reset();
  244. result->setFillType(fillType);
  245. if (rect1.intersect(rect2)) {
  246. result->addRect(rect1);
  247. }
  248. return true;
  249. }
  250. if (one.isEmpty() || two.isEmpty()) {
  251. SkPath work;
  252. switch (op) {
  253. case kIntersect_SkPathOp:
  254. break;
  255. case kUnion_SkPathOp:
  256. case kXOR_SkPathOp:
  257. work = one.isEmpty() ? two : one;
  258. break;
  259. case kDifference_SkPathOp:
  260. if (!one.isEmpty()) {
  261. work = one;
  262. }
  263. break;
  264. case kReverseDifference_SkPathOp:
  265. if (!two.isEmpty()) {
  266. work = two;
  267. }
  268. break;
  269. default:
  270. SkASSERT(0); // unhandled case
  271. }
  272. if (inverseFill != work.isInverseFillType()) {
  273. work.toggleInverseFillType();
  274. }
  275. return Simplify(work, result);
  276. }
  277. SkSTArenaAlloc<4096> allocator; // FIXME: add a constant expression here, tune
  278. SkOpContour contour;
  279. SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
  280. SkOpGlobalState globalState(contourList, &allocator
  281. SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
  282. SkOpCoincidence coincidence(&globalState);
  283. const SkPath* minuend = &one;
  284. const SkPath* subtrahend = &two;
  285. if (op == kReverseDifference_SkPathOp) {
  286. using std::swap;
  287. swap(minuend, subtrahend);
  288. op = kDifference_SkPathOp;
  289. }
  290. #if DEBUG_SORT
  291. SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
  292. #endif
  293. // turn path into list of segments
  294. SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
  295. if (builder.unparseable()) {
  296. return false;
  297. }
  298. const int xorMask = builder.xorMask();
  299. builder.addOperand(*subtrahend);
  300. if (!builder.finish()) {
  301. return false;
  302. }
  303. #if DEBUG_DUMP_SEGMENTS
  304. contourList->dumpSegments("seg", op);
  305. #endif
  306. const int xorOpMask = builder.xorMask();
  307. if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
  308. xorOpMask == kEvenOdd_PathOpsMask)) {
  309. result->reset();
  310. result->setFillType(fillType);
  311. return true;
  312. }
  313. // find all intersections between segments
  314. SkOpContour* current = contourList;
  315. do {
  316. SkOpContour* next = current;
  317. while (AddIntersectTs(current, next, &coincidence)
  318. && (next = next->next()))
  319. ;
  320. } while ((current = current->next()));
  321. #if DEBUG_VALIDATE
  322. globalState.setPhase(SkOpPhase::kWalking);
  323. #endif
  324. bool success = HandleCoincidence(contourList, &coincidence);
  325. #if DEBUG_COIN
  326. globalState.debugAddToGlobalCoinDicts();
  327. #endif
  328. if (!success) {
  329. return false;
  330. }
  331. #if DEBUG_ALIGNMENT
  332. contourList->dumpSegments("aligned");
  333. #endif
  334. // construct closed contours
  335. SkPath original = *result;
  336. result->reset();
  337. result->setFillType(fillType);
  338. SkPathWriter wrapper(*result);
  339. if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
  340. *result = original;
  341. return false;
  342. }
  343. wrapper.assemble(); // if some edges could not be resolved, assemble remaining
  344. #if DEBUG_T_SECT_LOOP_COUNT
  345. static SkMutex& debugWorstLoop = *(new SkMutex);
  346. {
  347. SkAutoMutexExclusive autoM(debugWorstLoop);
  348. if (!gVerboseFinalize) {
  349. gVerboseFinalize = &ReportPathOpsDebugging;
  350. }
  351. debugWorstState.debugDoYourWorst(&globalState);
  352. }
  353. #endif
  354. return true;
  355. }
  356. bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
  357. #if DEBUG_DUMP_VERIFY
  358. if (SkPathOpsDebug::gVerifyOp) {
  359. if (!OpDebug(one, two, op, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
  360. SkPathOpsDebug::ReportOpFail(one, two, op);
  361. return false;
  362. }
  363. SkPathOpsDebug::VerifyOp(one, two, op, *result);
  364. return true;
  365. }
  366. #endif
  367. return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
  368. }