SkPathOpsCommon.cpp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333
  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 "include/private/SkMacros.h"
  8. #include "src/core/SkTSort.h"
  9. #include "src/pathops/SkAddIntersections.h"
  10. #include "src/pathops/SkOpCoincidence.h"
  11. #include "src/pathops/SkOpEdgeBuilder.h"
  12. #include "src/pathops/SkPathOpsCommon.h"
  13. #include "src/pathops/SkPathWriter.h"
  14. const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr,
  15. bool* sortablePtr) {
  16. // find first angle, initialize winding to computed fWindSum
  17. SkOpSegment* segment = start->segment();
  18. const SkOpAngle* angle = segment->spanToAngle(start, end);
  19. if (!angle) {
  20. *windingPtr = SK_MinS32;
  21. return nullptr;
  22. }
  23. bool computeWinding = false;
  24. const SkOpAngle* firstAngle = angle;
  25. bool loop = false;
  26. bool unorderable = false;
  27. int winding = SK_MinS32;
  28. do {
  29. angle = angle->next();
  30. if (!angle) {
  31. return nullptr;
  32. }
  33. unorderable |= angle->unorderable();
  34. if ((computeWinding = unorderable || (angle == firstAngle && loop))) {
  35. break; // if we get here, there's no winding, loop is unorderable
  36. }
  37. loop |= angle == firstAngle;
  38. segment = angle->segment();
  39. winding = segment->windSum(angle);
  40. } while (winding == SK_MinS32);
  41. // if the angle loop contains an unorderable span, the angle order may be useless
  42. // directly compute the winding in this case for each span
  43. if (computeWinding) {
  44. firstAngle = angle;
  45. winding = SK_MinS32;
  46. do {
  47. SkOpSpanBase* startSpan = angle->start();
  48. SkOpSpanBase* endSpan = angle->end();
  49. SkOpSpan* lesser = startSpan->starter(endSpan);
  50. int testWinding = lesser->windSum();
  51. if (testWinding == SK_MinS32) {
  52. testWinding = lesser->computeWindSum();
  53. }
  54. if (testWinding != SK_MinS32) {
  55. segment = angle->segment();
  56. winding = testWinding;
  57. }
  58. angle = angle->next();
  59. } while (angle != firstAngle);
  60. }
  61. *sortablePtr = !unorderable;
  62. *windingPtr = winding;
  63. return angle;
  64. }
  65. SkOpSpan* FindUndone(SkOpContourHead* contourHead) {
  66. SkOpContour* contour = contourHead;
  67. do {
  68. if (contour->done()) {
  69. continue;
  70. }
  71. SkOpSpan* result = contour->undoneSpan();
  72. if (result) {
  73. return result;
  74. }
  75. } while ((contour = contour->next()));
  76. return nullptr;
  77. }
  78. SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
  79. SkOpSpanBase** endPtr) {
  80. while (chase->count()) {
  81. SkOpSpanBase* span;
  82. chase->pop(&span);
  83. SkOpSegment* segment = span->segment();
  84. *startPtr = span->ptT()->next()->span();
  85. bool done = true;
  86. *endPtr = nullptr;
  87. if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
  88. *startPtr = last->start();
  89. *endPtr = last->end();
  90. #if TRY_ROTATE
  91. *chase->insert(0) = span;
  92. #else
  93. *chase->append() = span;
  94. #endif
  95. return last->segment();
  96. }
  97. if (done) {
  98. continue;
  99. }
  100. // find first angle, initialize winding to computed wind sum
  101. int winding;
  102. bool sortable;
  103. const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
  104. if (!angle) {
  105. return nullptr;
  106. }
  107. if (winding == SK_MinS32) {
  108. continue;
  109. }
  110. int sumWinding SK_INIT_TO_AVOID_WARNING;
  111. if (sortable) {
  112. segment = angle->segment();
  113. sumWinding = segment->updateWindingReverse(angle);
  114. }
  115. SkOpSegment* first = nullptr;
  116. const SkOpAngle* firstAngle = angle;
  117. while ((angle = angle->next()) != firstAngle) {
  118. segment = angle->segment();
  119. SkOpSpanBase* start = angle->start();
  120. SkOpSpanBase* end = angle->end();
  121. int maxWinding SK_INIT_TO_AVOID_WARNING;
  122. if (sortable) {
  123. segment->setUpWinding(start, end, &maxWinding, &sumWinding);
  124. }
  125. if (!segment->done(angle)) {
  126. if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
  127. first = segment;
  128. *startPtr = start;
  129. *endPtr = end;
  130. }
  131. // OPTIMIZATION: should this also add to the chase?
  132. if (sortable) {
  133. // TODO: add error handling
  134. SkAssertResult(segment->markAngle(maxWinding, sumWinding, angle, nullptr));
  135. }
  136. }
  137. }
  138. if (first) {
  139. #if TRY_ROTATE
  140. *chase->insert(0) = span;
  141. #else
  142. *chase->append() = span;
  143. #endif
  144. return first;
  145. }
  146. }
  147. return nullptr;
  148. }
  149. bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) {
  150. SkTDArray<SkOpContour* > list;
  151. SkOpContour* contour = *contourList;
  152. do {
  153. if (contour->count()) {
  154. contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
  155. *list.append() = contour;
  156. }
  157. } while ((contour = contour->next()));
  158. int count = list.count();
  159. if (!count) {
  160. return false;
  161. }
  162. if (count > 1) {
  163. SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
  164. }
  165. contour = list[0];
  166. SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
  167. contour->globalState()->setContourHead(contourHead);
  168. *contourList = contourHead;
  169. for (int index = 1; index < count; ++index) {
  170. SkOpContour* next = list[index];
  171. contour->setNext(next);
  172. contour = next;
  173. }
  174. contour->setNext(nullptr);
  175. return true;
  176. }
  177. static void calc_angles(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
  178. DEBUG_STATIC_SET_PHASE(contourList);
  179. SkOpContour* contour = contourList;
  180. do {
  181. contour->calcAngles();
  182. } while ((contour = contour->next()));
  183. }
  184. static bool missing_coincidence(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
  185. DEBUG_STATIC_SET_PHASE(contourList);
  186. SkOpContour* contour = contourList;
  187. bool result = false;
  188. do {
  189. result |= contour->missingCoincidence();
  190. } while ((contour = contour->next()));
  191. return result;
  192. }
  193. static bool move_multiples(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
  194. DEBUG_STATIC_SET_PHASE(contourList);
  195. SkOpContour* contour = contourList;
  196. do {
  197. if (!contour->moveMultiples()) {
  198. return false;
  199. }
  200. } while ((contour = contour->next()));
  201. return true;
  202. }
  203. static bool move_nearby(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
  204. DEBUG_STATIC_SET_PHASE(contourList);
  205. SkOpContour* contour = contourList;
  206. do {
  207. if (!contour->moveNearby()) {
  208. return false;
  209. }
  210. } while ((contour = contour->next()));
  211. return true;
  212. }
  213. static bool sort_angles(SkOpContourHead* contourList) {
  214. SkOpContour* contour = contourList;
  215. do {
  216. if (!contour->sortAngles()) {
  217. return false;
  218. }
  219. } while ((contour = contour->next()));
  220. return true;
  221. }
  222. bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) {
  223. SkOpGlobalState* globalState = contourList->globalState();
  224. // match up points within the coincident runs
  225. if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kIntersecting))) {
  226. return false;
  227. }
  228. // combine t values when multiple intersections occur on some segments but not others
  229. if (!move_multiples(contourList DEBUG_PHASE_PARAMS(kWalking))) {
  230. return false;
  231. }
  232. // move t values and points together to eliminate small/tiny gaps
  233. if (!move_nearby(contourList DEBUG_COIN_PARAMS())) {
  234. return false;
  235. }
  236. // add coincidence formed by pairing on curve points and endpoints
  237. coincidence->correctEnds(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
  238. if (!coincidence->addEndMovedSpans(DEBUG_COIN_ONLY_PARAMS())) {
  239. return false;
  240. }
  241. const int SAFETY_COUNT = 3;
  242. int safetyHatch = SAFETY_COUNT;
  243. // look for coincidence present in A-B and A-C but missing in B-C
  244. do {
  245. bool added;
  246. if (!coincidence->addMissing(&added DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
  247. return false;
  248. }
  249. if (!added) {
  250. break;
  251. }
  252. if (!--safetyHatch) {
  253. SkASSERT(globalState->debugSkipAssert());
  254. return false;
  255. }
  256. move_nearby(contourList DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch - 1));
  257. } while (true);
  258. // check to see if, loosely, coincident ranges may be expanded
  259. if (coincidence->expand(DEBUG_COIN_ONLY_PARAMS())) {
  260. bool added;
  261. if (!coincidence->addMissing(&added DEBUG_COIN_PARAMS())) {
  262. return false;
  263. }
  264. if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
  265. return false;
  266. }
  267. if (!move_multiples(contourList DEBUG_COIN_PARAMS())) {
  268. return false;
  269. }
  270. move_nearby(contourList DEBUG_COIN_PARAMS());
  271. }
  272. // the expanded ranges may not align -- add the missing spans
  273. if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
  274. return false;
  275. }
  276. // mark spans of coincident segments as coincident
  277. coincidence->mark(DEBUG_COIN_ONLY_PARAMS());
  278. // look for coincidence lines and curves undetected by intersection
  279. if (missing_coincidence(contourList DEBUG_COIN_PARAMS())) {
  280. (void) coincidence->expand(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
  281. if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
  282. return false;
  283. }
  284. if (!coincidence->mark(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
  285. return false;
  286. }
  287. } else {
  288. (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
  289. }
  290. (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
  291. SkOpCoincidence overlaps(globalState);
  292. safetyHatch = SAFETY_COUNT;
  293. do {
  294. SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
  295. // adjust the winding value to account for coincident edges
  296. if (!pairs->apply(DEBUG_ITER_ONLY_PARAMS(SAFETY_COUNT - safetyHatch))) {
  297. return false;
  298. }
  299. // For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
  300. // are different, construct a new pair to resolve their mutual span
  301. if (!pairs->findOverlaps(&overlaps DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
  302. return false;
  303. }
  304. if (!--safetyHatch) {
  305. SkASSERT(globalState->debugSkipAssert());
  306. return false;
  307. }
  308. } while (!overlaps.isEmpty());
  309. calc_angles(contourList DEBUG_COIN_PARAMS());
  310. if (!sort_angles(contourList)) {
  311. return false;
  312. }
  313. #if DEBUG_COINCIDENCE_VERBOSE
  314. coincidence->debugShowCoincidence();
  315. #endif
  316. #if DEBUG_COINCIDENCE
  317. coincidence->debugValidate();
  318. #endif
  319. SkPathOpsDebug::ShowActiveSpans(contourList);
  320. return true;
  321. }