SkOpContour.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454
  1. /*
  2. * Copyright 2013 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. #ifndef SkOpContour_DEFINED
  8. #define SkOpContour_DEFINED
  9. #include "include/private/SkTDArray.h"
  10. #include "src/core/SkTSort.h"
  11. #include "src/pathops/SkOpSegment.h"
  12. enum class SkOpRayDir;
  13. struct SkOpRayHit;
  14. class SkPathWriter;
  15. class SkOpContour {
  16. public:
  17. SkOpContour() {
  18. reset();
  19. }
  20. bool operator<(const SkOpContour& rh) const {
  21. return fBounds.fTop == rh.fBounds.fTop
  22. ? fBounds.fLeft < rh.fBounds.fLeft
  23. : fBounds.fTop < rh.fBounds.fTop;
  24. }
  25. void addConic(SkPoint pts[3], SkScalar weight) {
  26. appendSegment().addConic(pts, weight, this);
  27. }
  28. void addCubic(SkPoint pts[4]) {
  29. appendSegment().addCubic(pts, this);
  30. }
  31. SkOpSegment* addLine(SkPoint pts[2]) {
  32. SkASSERT(pts[0] != pts[1]);
  33. return appendSegment().addLine(pts, this);
  34. }
  35. void addQuad(SkPoint pts[3]) {
  36. appendSegment().addQuad(pts, this);
  37. }
  38. SkOpSegment& appendSegment() {
  39. SkOpSegment* result = fCount++ ? this->globalState()->allocator()->make<SkOpSegment>()
  40. : &fHead;
  41. result->setPrev(fTail);
  42. if (fTail) {
  43. fTail->setNext(result);
  44. }
  45. fTail = result;
  46. return *result;
  47. }
  48. const SkPathOpsBounds& bounds() const {
  49. return fBounds;
  50. }
  51. void calcAngles() {
  52. SkASSERT(fCount > 0);
  53. SkOpSegment* segment = &fHead;
  54. do {
  55. segment->calcAngles();
  56. } while ((segment = segment->next()));
  57. }
  58. void complete() {
  59. setBounds();
  60. }
  61. int count() const {
  62. return fCount;
  63. }
  64. int debugID() const {
  65. return SkDEBUGRELEASE(fID, -1);
  66. }
  67. int debugIndent() const {
  68. return SkDEBUGRELEASE(fDebugIndent, 0);
  69. }
  70. const SkOpAngle* debugAngle(int id) const {
  71. return SkDEBUGRELEASE(this->globalState()->debugAngle(id), nullptr);
  72. }
  73. const SkOpCoincidence* debugCoincidence() const {
  74. return this->globalState()->coincidence();
  75. }
  76. #if DEBUG_COIN
  77. void debugCheckHealth(SkPathOpsDebug::GlitchLog* ) const;
  78. #endif
  79. SkOpContour* debugContour(int id) const {
  80. return SkDEBUGRELEASE(this->globalState()->debugContour(id), nullptr);
  81. }
  82. #if DEBUG_COIN
  83. void debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const;
  84. void debugMoveMultiples(SkPathOpsDebug::GlitchLog* ) const;
  85. void debugMoveNearby(SkPathOpsDebug::GlitchLog* log) const;
  86. #endif
  87. const SkOpPtT* debugPtT(int id) const {
  88. return SkDEBUGRELEASE(this->globalState()->debugPtT(id), nullptr);
  89. }
  90. const SkOpSegment* debugSegment(int id) const {
  91. return SkDEBUGRELEASE(this->globalState()->debugSegment(id), nullptr);
  92. }
  93. #if DEBUG_ACTIVE_SPANS
  94. void debugShowActiveSpans(SkString* str) {
  95. SkOpSegment* segment = &fHead;
  96. do {
  97. segment->debugShowActiveSpans(str);
  98. } while ((segment = segment->next()));
  99. }
  100. #endif
  101. const SkOpSpanBase* debugSpan(int id) const {
  102. return SkDEBUGRELEASE(this->globalState()->debugSpan(id), nullptr);
  103. }
  104. SkOpGlobalState* globalState() const {
  105. return fState;
  106. }
  107. void debugValidate() const {
  108. #if DEBUG_VALIDATE
  109. const SkOpSegment* segment = &fHead;
  110. const SkOpSegment* prior = nullptr;
  111. do {
  112. segment->debugValidate();
  113. SkASSERT(segment->prev() == prior);
  114. prior = segment;
  115. } while ((segment = segment->next()));
  116. SkASSERT(prior == fTail);
  117. #endif
  118. }
  119. bool done() const {
  120. return fDone;
  121. }
  122. void dump() const;
  123. void dumpAll() const;
  124. void dumpAngles() const;
  125. void dumpContours() const;
  126. void dumpContoursAll() const;
  127. void dumpContoursAngles() const;
  128. void dumpContoursPts() const;
  129. void dumpContoursPt(int segmentID) const;
  130. void dumpContoursSegment(int segmentID) const;
  131. void dumpContoursSpan(int segmentID) const;
  132. void dumpContoursSpans() const;
  133. void dumpPt(int ) const;
  134. void dumpPts(const char* prefix = "seg") const;
  135. void dumpPtsX(const char* prefix) const;
  136. void dumpSegment(int ) const;
  137. void dumpSegments(const char* prefix = "seg", SkPathOp op = (SkPathOp) -1) const;
  138. void dumpSpan(int ) const;
  139. void dumpSpans() const;
  140. const SkPoint& end() const {
  141. return fTail->pts()[SkPathOpsVerbToPoints(fTail->verb())];
  142. }
  143. SkOpSpan* findSortableTop(SkOpContour* );
  144. SkOpSegment* first() {
  145. SkASSERT(fCount > 0);
  146. return &fHead;
  147. }
  148. const SkOpSegment* first() const {
  149. SkASSERT(fCount > 0);
  150. return &fHead;
  151. }
  152. void indentDump() const {
  153. SkDEBUGCODE(fDebugIndent += 2);
  154. }
  155. void init(SkOpGlobalState* globalState, bool operand, bool isXor) {
  156. fState = globalState;
  157. fOperand = operand;
  158. fXor = isXor;
  159. SkDEBUGCODE(fID = globalState->nextContourID());
  160. }
  161. int isCcw() const {
  162. return fCcw;
  163. }
  164. bool isXor() const {
  165. return fXor;
  166. }
  167. void joinSegments() {
  168. SkOpSegment* segment = &fHead;
  169. SkOpSegment* next;
  170. do {
  171. next = segment->next();
  172. segment->joinEnds(next ? next : &fHead);
  173. } while ((segment = next));
  174. }
  175. void markAllDone() {
  176. SkOpSegment* segment = &fHead;
  177. do {
  178. segment->markAllDone();
  179. } while ((segment = segment->next()));
  180. }
  181. // Please keep this aligned with debugMissingCoincidence()
  182. bool missingCoincidence() {
  183. SkASSERT(fCount > 0);
  184. SkOpSegment* segment = &fHead;
  185. bool result = false;
  186. do {
  187. if (segment->missingCoincidence()) {
  188. result = true;
  189. }
  190. segment = segment->next();
  191. } while (segment);
  192. return result;
  193. }
  194. bool moveMultiples() {
  195. SkASSERT(fCount > 0);
  196. SkOpSegment* segment = &fHead;
  197. do {
  198. if (!segment->moveMultiples()) {
  199. return false;
  200. }
  201. } while ((segment = segment->next()));
  202. return true;
  203. }
  204. bool moveNearby() {
  205. SkASSERT(fCount > 0);
  206. SkOpSegment* segment = &fHead;
  207. do {
  208. if (!segment->moveNearby()) {
  209. return false;
  210. }
  211. } while ((segment = segment->next()));
  212. return true;
  213. }
  214. SkOpContour* next() {
  215. return fNext;
  216. }
  217. const SkOpContour* next() const {
  218. return fNext;
  219. }
  220. bool operand() const {
  221. return fOperand;
  222. }
  223. bool oppXor() const {
  224. return fOppXor;
  225. }
  226. void outdentDump() const {
  227. SkDEBUGCODE(fDebugIndent -= 2);
  228. }
  229. void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkArenaAlloc*);
  230. void reset() {
  231. fTail = nullptr;
  232. fNext = nullptr;
  233. fCount = 0;
  234. fDone = false;
  235. SkDEBUGCODE(fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin));
  236. SkDEBUGCODE(fFirstSorted = -1);
  237. SkDEBUGCODE(fDebugIndent = 0);
  238. }
  239. void resetReverse() {
  240. SkOpContour* next = this;
  241. do {
  242. if (!next->count()) {
  243. continue;
  244. }
  245. next->fCcw = -1;
  246. next->fReverse = false;
  247. } while ((next = next->next()));
  248. }
  249. bool reversed() const {
  250. return fReverse;
  251. }
  252. void setBounds() {
  253. SkASSERT(fCount > 0);
  254. const SkOpSegment* segment = &fHead;
  255. fBounds = segment->bounds();
  256. while ((segment = segment->next())) {
  257. fBounds.add(segment->bounds());
  258. }
  259. }
  260. void setCcw(int ccw) {
  261. fCcw = ccw;
  262. }
  263. void setGlobalState(SkOpGlobalState* state) {
  264. fState = state;
  265. }
  266. void setNext(SkOpContour* contour) {
  267. // SkASSERT(!fNext == !!contour);
  268. fNext = contour;
  269. }
  270. void setOperand(bool isOp) {
  271. fOperand = isOp;
  272. }
  273. void setOppXor(bool isOppXor) {
  274. fOppXor = isOppXor;
  275. }
  276. void setReverse() {
  277. fReverse = true;
  278. }
  279. void setXor(bool isXor) {
  280. fXor = isXor;
  281. }
  282. bool sortAngles() {
  283. SkASSERT(fCount > 0);
  284. SkOpSegment* segment = &fHead;
  285. do {
  286. FAIL_IF(!segment->sortAngles());
  287. } while ((segment = segment->next()));
  288. return true;
  289. }
  290. const SkPoint& start() const {
  291. return fHead.pts()[0];
  292. }
  293. void toPartialBackward(SkPathWriter* path) const {
  294. const SkOpSegment* segment = fTail;
  295. do {
  296. SkAssertResult(segment->addCurveTo(segment->tail(), segment->head(), path));
  297. } while ((segment = segment->prev()));
  298. }
  299. void toPartialForward(SkPathWriter* path) const {
  300. const SkOpSegment* segment = &fHead;
  301. do {
  302. SkAssertResult(segment->addCurveTo(segment->head(), segment->tail(), path));
  303. } while ((segment = segment->next()));
  304. }
  305. void toReversePath(SkPathWriter* path) const;
  306. void toPath(SkPathWriter* path) const;
  307. SkOpSpan* undoneSpan();
  308. protected:
  309. SkOpGlobalState* fState;
  310. SkOpSegment fHead;
  311. SkOpSegment* fTail;
  312. SkOpContour* fNext;
  313. SkPathOpsBounds fBounds;
  314. int fCcw;
  315. int fCount;
  316. int fFirstSorted;
  317. bool fDone; // set by find top segment
  318. bool fOperand; // true for the second argument to a binary operator
  319. bool fReverse; // true if contour should be reverse written to path (used only by fix winding)
  320. bool fXor; // set if original path had even-odd fill
  321. bool fOppXor; // set if opposite path had even-odd fill
  322. SkDEBUGCODE(int fID);
  323. SkDEBUGCODE(mutable int fDebugIndent);
  324. };
  325. class SkOpContourHead : public SkOpContour {
  326. public:
  327. SkOpContour* appendContour() {
  328. SkOpContour* contour = this->globalState()->allocator()->make<SkOpContour>();
  329. contour->setNext(nullptr);
  330. SkOpContour* prev = this;
  331. SkOpContour* next;
  332. while ((next = prev->next())) {
  333. prev = next;
  334. }
  335. prev->setNext(contour);
  336. return contour;
  337. }
  338. void joinAllSegments() {
  339. SkOpContour* next = this;
  340. do {
  341. if (!next->count()) {
  342. continue;
  343. }
  344. next->joinSegments();
  345. } while ((next = next->next()));
  346. }
  347. void remove(SkOpContour* contour) {
  348. if (contour == this) {
  349. SkASSERT(this->count() == 0);
  350. return;
  351. }
  352. SkASSERT(contour->next() == nullptr);
  353. SkOpContour* prev = this;
  354. SkOpContour* next;
  355. while ((next = prev->next()) != contour) {
  356. SkASSERT(next);
  357. prev = next;
  358. }
  359. SkASSERT(prev);
  360. prev->setNext(nullptr);
  361. }
  362. };
  363. class SkOpContourBuilder {
  364. public:
  365. SkOpContourBuilder(SkOpContour* contour)
  366. : fContour(contour)
  367. , fLastIsLine(false) {
  368. }
  369. void addConic(SkPoint pts[3], SkScalar weight);
  370. void addCubic(SkPoint pts[4]);
  371. void addCurve(SkPath::Verb verb, const SkPoint pts[4], SkScalar weight = 1);
  372. void addLine(const SkPoint pts[2]);
  373. void addQuad(SkPoint pts[3]);
  374. void flush();
  375. SkOpContour* contour() { return fContour; }
  376. void setContour(SkOpContour* contour) { flush(); fContour = contour; }
  377. protected:
  378. SkOpContour* fContour;
  379. SkPoint fLastLine[2];
  380. bool fLastIsLine;
  381. };
  382. #endif