SkOpBuilder.cpp 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195
  1. /*
  2. * Copyright 2014 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/SkMatrix.h"
  8. #include "include/pathops/SkPathOps.h"
  9. #include "src/core/SkArenaAlloc.h"
  10. #include "src/core/SkPathPriv.h"
  11. #include "src/pathops/SkOpEdgeBuilder.h"
  12. #include "src/pathops/SkPathOpsCommon.h"
  13. static bool one_contour(const SkPath& path) {
  14. SkSTArenaAlloc<256> allocator;
  15. int verbCount = path.countVerbs();
  16. uint8_t* verbs = (uint8_t*) allocator.makeArrayDefault<uint8_t>(verbCount);
  17. (void) path.getVerbs(verbs, verbCount);
  18. for (int index = 1; index < verbCount; ++index) {
  19. if (verbs[index] == SkPath::kMove_Verb) {
  20. return false;
  21. }
  22. }
  23. return true;
  24. }
  25. void SkOpBuilder::ReversePath(SkPath* path) {
  26. SkPath temp;
  27. SkPoint lastPt;
  28. SkAssertResult(path->getLastPt(&lastPt));
  29. temp.moveTo(lastPt);
  30. temp.reversePathTo(*path);
  31. temp.close();
  32. *path = temp;
  33. }
  34. bool SkOpBuilder::FixWinding(SkPath* path) {
  35. SkPath::FillType fillType = path->getFillType();
  36. if (fillType == SkPath::kInverseEvenOdd_FillType) {
  37. fillType = SkPath::kInverseWinding_FillType;
  38. } else if (fillType == SkPath::kEvenOdd_FillType) {
  39. fillType = SkPath::kWinding_FillType;
  40. }
  41. SkPathPriv::FirstDirection dir;
  42. if (one_contour(*path) && SkPathPriv::CheapComputeFirstDirection(*path, &dir)) {
  43. if (dir != SkPathPriv::kCCW_FirstDirection) {
  44. ReversePath(path);
  45. }
  46. path->setFillType(fillType);
  47. return true;
  48. }
  49. SkSTArenaAlloc<4096> allocator;
  50. SkOpContourHead contourHead;
  51. SkOpGlobalState globalState(&contourHead, &allocator SkDEBUGPARAMS(false)
  52. SkDEBUGPARAMS(nullptr));
  53. SkOpEdgeBuilder builder(*path, &contourHead, &globalState);
  54. if (builder.unparseable() || !builder.finish()) {
  55. return false;
  56. }
  57. if (!contourHead.count()) {
  58. return true;
  59. }
  60. if (!contourHead.next()) {
  61. return false;
  62. }
  63. contourHead.joinAllSegments();
  64. contourHead.resetReverse();
  65. bool writePath = false;
  66. SkOpSpan* topSpan;
  67. globalState.setPhase(SkOpPhase::kFixWinding);
  68. while ((topSpan = FindSortableTop(&contourHead))) {
  69. SkOpSegment* topSegment = topSpan->segment();
  70. SkOpContour* topContour = topSegment->contour();
  71. SkASSERT(topContour->isCcw() >= 0);
  72. #if DEBUG_WINDING
  73. SkDebugf("%s id=%d nested=%d ccw=%d\n", __FUNCTION__,
  74. topSegment->debugID(), globalState.nested(), topContour->isCcw());
  75. #endif
  76. if ((globalState.nested() & 1) != SkToBool(topContour->isCcw())) {
  77. topContour->setReverse();
  78. writePath = true;
  79. }
  80. topContour->markAllDone();
  81. globalState.clearNested();
  82. }
  83. if (!writePath) {
  84. path->setFillType(fillType);
  85. return true;
  86. }
  87. SkPath empty;
  88. SkPathWriter woundPath(empty);
  89. SkOpContour* test = &contourHead;
  90. do {
  91. if (!test->count()) {
  92. continue;
  93. }
  94. if (test->reversed()) {
  95. test->toReversePath(&woundPath);
  96. } else {
  97. test->toPath(&woundPath);
  98. }
  99. } while ((test = test->next()));
  100. *path = *woundPath.nativePath();
  101. path->setFillType(fillType);
  102. return true;
  103. }
  104. void SkOpBuilder::add(const SkPath& path, SkPathOp op) {
  105. if (0 == fOps.count() && op != kUnion_SkPathOp) {
  106. fPathRefs.push_back() = SkPath();
  107. *fOps.append() = kUnion_SkPathOp;
  108. }
  109. fPathRefs.push_back() = path;
  110. *fOps.append() = op;
  111. }
  112. void SkOpBuilder::reset() {
  113. fPathRefs.reset();
  114. fOps.reset();
  115. }
  116. /* OPTIMIZATION: Union doesn't need to be all-or-nothing. A run of three or more convex
  117. paths with union ops could be locally resolved and still improve over doing the
  118. ops one at a time. */
  119. bool SkOpBuilder::resolve(SkPath* result) {
  120. SkPath original = *result;
  121. int count = fOps.count();
  122. bool allUnion = true;
  123. SkPathPriv::FirstDirection firstDir = SkPathPriv::kUnknown_FirstDirection;
  124. for (int index = 0; index < count; ++index) {
  125. SkPath* test = &fPathRefs[index];
  126. if (kUnion_SkPathOp != fOps[index] || test->isInverseFillType()) {
  127. allUnion = false;
  128. break;
  129. }
  130. // If all paths are convex, track direction, reversing as needed.
  131. if (test->isConvex()) {
  132. SkPathPriv::FirstDirection dir;
  133. if (!SkPathPriv::CheapComputeFirstDirection(*test, &dir)) {
  134. allUnion = false;
  135. break;
  136. }
  137. if (firstDir == SkPathPriv::kUnknown_FirstDirection) {
  138. firstDir = dir;
  139. } else if (firstDir != dir) {
  140. ReversePath(test);
  141. }
  142. continue;
  143. }
  144. // If the path is not convex but its bounds do not intersect the others, simplify is enough.
  145. const SkRect& testBounds = test->getBounds();
  146. for (int inner = 0; inner < index; ++inner) {
  147. // OPTIMIZE: check to see if the contour bounds do not intersect other contour bounds?
  148. if (SkRect::Intersects(fPathRefs[inner].getBounds(), testBounds)) {
  149. allUnion = false;
  150. break;
  151. }
  152. }
  153. }
  154. if (!allUnion) {
  155. *result = fPathRefs[0];
  156. for (int index = 1; index < count; ++index) {
  157. if (!Op(*result, fPathRefs[index], fOps[index], result)) {
  158. reset();
  159. *result = original;
  160. return false;
  161. }
  162. }
  163. reset();
  164. return true;
  165. }
  166. SkPath sum;
  167. for (int index = 0; index < count; ++index) {
  168. if (!Simplify(fPathRefs[index], &fPathRefs[index])) {
  169. reset();
  170. *result = original;
  171. return false;
  172. }
  173. if (!fPathRefs[index].isEmpty()) {
  174. // convert the even odd result back to winding form before accumulating it
  175. if (!FixWinding(&fPathRefs[index])) {
  176. *result = original;
  177. return false;
  178. }
  179. sum.addPath(fPathRefs[index]);
  180. }
  181. }
  182. reset();
  183. bool success = Simplify(sum, result);
  184. if (!success) {
  185. *result = original;
  186. }
  187. return success;
  188. }