SkPathOpsSimplify.cpp 7.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226
  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. static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* writer) {
  13. bool unsortable = false;
  14. do {
  15. SkOpSpan* span = FindSortableTop(contourList);
  16. if (!span) {
  17. break;
  18. }
  19. SkOpSegment* current = span->segment();
  20. SkOpSpanBase* start = span->next();
  21. SkOpSpanBase* end = span;
  22. SkTDArray<SkOpSpanBase*> chase;
  23. do {
  24. if (current->activeWinding(start, end)) {
  25. do {
  26. if (!unsortable && current->done()) {
  27. break;
  28. }
  29. SkASSERT(unsortable || !current->done());
  30. SkOpSpanBase* nextStart = start;
  31. SkOpSpanBase* nextEnd = end;
  32. SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
  33. &unsortable);
  34. if (!next) {
  35. break;
  36. }
  37. #if DEBUG_FLOW
  38. SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
  39. current->debugID(), start->pt().fX, start->pt().fY,
  40. end->pt().fX, end->pt().fY);
  41. #endif
  42. if (!current->addCurveTo(start, end, writer)) {
  43. return false;
  44. }
  45. current = next;
  46. start = nextStart;
  47. end = nextEnd;
  48. } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
  49. if (current->activeWinding(start, end) && !writer->isClosed()) {
  50. SkOpSpan* spanStart = start->starter(end);
  51. if (!spanStart->done()) {
  52. if (!current->addCurveTo(start, end, writer)) {
  53. return false;
  54. }
  55. current->markDone(spanStart);
  56. }
  57. }
  58. writer->finishContour();
  59. } else {
  60. SkOpSpanBase* last;
  61. if (!current->markAndChaseDone(start, end, &last)) {
  62. return false;
  63. }
  64. if (last && !last->chased()) {
  65. last->setChased(true);
  66. SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
  67. *chase.append() = last;
  68. #if DEBUG_WINDING
  69. SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
  70. if (!last->final()) {
  71. SkDebugf(" windSum=%d", last->upCast()->windSum());
  72. }
  73. SkDebugf("\n");
  74. #endif
  75. }
  76. }
  77. current = FindChase(&chase, &start, &end);
  78. SkPathOpsDebug::ShowActiveSpans(contourList);
  79. if (!current) {
  80. break;
  81. }
  82. } while (true);
  83. } while (true);
  84. return true;
  85. }
  86. // returns true if all edges were processed
  87. static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* writer) {
  88. bool unsortable = false;
  89. int safetyNet = 1000000;
  90. do {
  91. SkOpSpan* span = FindUndone(contourList);
  92. if (!span) {
  93. break;
  94. }
  95. SkOpSegment* current = span->segment();
  96. SkOpSpanBase* start = span->next();
  97. SkOpSpanBase* end = span;
  98. do {
  99. if (--safetyNet < 0) {
  100. return false;
  101. }
  102. if (!unsortable && current->done()) {
  103. break;
  104. }
  105. SkASSERT(unsortable || !current->done());
  106. SkOpSpanBase* nextStart = start;
  107. SkOpSpanBase* nextEnd = end;
  108. SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd,
  109. &unsortable);
  110. if (!next) {
  111. break;
  112. }
  113. #if DEBUG_FLOW
  114. SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
  115. current->debugID(), start->pt().fX, start->pt().fY,
  116. end->pt().fX, end->pt().fY);
  117. #endif
  118. if (!current->addCurveTo(start, end, writer)) {
  119. return false;
  120. }
  121. current = next;
  122. start = nextStart;
  123. end = nextEnd;
  124. } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
  125. if (!writer->isClosed()) {
  126. SkOpSpan* spanStart = start->starter(end);
  127. if (!spanStart->done()) {
  128. return false;
  129. }
  130. }
  131. writer->finishContour();
  132. SkPathOpsDebug::ShowActiveSpans(contourList);
  133. } while (true);
  134. return true;
  135. }
  136. // FIXME : add this as a member of SkPath
  137. bool SimplifyDebug(const SkPath& path, SkPath* result
  138. SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
  139. // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
  140. SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
  141. : SkPath::kEvenOdd_FillType;
  142. if (path.isConvex()) {
  143. if (result != &path) {
  144. *result = path;
  145. }
  146. result->setFillType(fillType);
  147. return true;
  148. }
  149. // turn path into list of segments
  150. SkSTArenaAlloc<4096> allocator; // FIXME: constant-ize, tune
  151. SkOpContour contour;
  152. SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
  153. SkOpGlobalState globalState(contourList, &allocator
  154. SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
  155. SkOpCoincidence coincidence(&globalState);
  156. #if DEBUG_DUMP_VERIFY
  157. #ifndef SK_DEBUG
  158. const char* testName = "release";
  159. #endif
  160. if (SkPathOpsDebug::gDumpOp) {
  161. SkPathOpsDebug::DumpSimplify(path, testName);
  162. }
  163. #endif
  164. #if DEBUG_SORT
  165. SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
  166. #endif
  167. SkOpEdgeBuilder builder(path, contourList, &globalState);
  168. if (!builder.finish()) {
  169. return false;
  170. }
  171. #if DEBUG_DUMP_SEGMENTS
  172. contour.dumpSegments();
  173. #endif
  174. if (!SortContourList(&contourList, false, false)) {
  175. result->reset();
  176. result->setFillType(fillType);
  177. return true;
  178. }
  179. // find all intersections between segments
  180. SkOpContour* current = contourList;
  181. do {
  182. SkOpContour* next = current;
  183. while (AddIntersectTs(current, next, &coincidence)
  184. && (next = next->next()));
  185. } while ((current = current->next()));
  186. #if DEBUG_VALIDATE
  187. globalState.setPhase(SkOpPhase::kWalking);
  188. #endif
  189. bool success = HandleCoincidence(contourList, &coincidence);
  190. #if DEBUG_COIN
  191. globalState.debugAddToGlobalCoinDicts();
  192. #endif
  193. if (!success) {
  194. return false;
  195. }
  196. #if DEBUG_DUMP_ALIGNMENT
  197. contour.dumpSegments("aligned");
  198. #endif
  199. // construct closed contours
  200. result->reset();
  201. result->setFillType(fillType);
  202. SkPathWriter wrapper(*result);
  203. if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList, &wrapper)
  204. : !bridgeXor(contourList, &wrapper)) {
  205. return false;
  206. }
  207. wrapper.assemble(); // if some edges could not be resolved, assemble remaining
  208. return true;
  209. }
  210. bool Simplify(const SkPath& path, SkPath* result) {
  211. #if DEBUG_DUMP_VERIFY
  212. if (SkPathOpsDebug::gVerifyOp) {
  213. if (!SimplifyDebug(path, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
  214. SkPathOpsDebug::ReportSimplifyFail(path);
  215. return false;
  216. }
  217. SkPathOpsDebug::VerifySimplify(path, *result);
  218. return true;
  219. }
  220. #endif
  221. return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
  222. }