SkOpSpan.h 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578
  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. #ifndef SkOpSpan_DEFINED
  8. #define SkOpSpan_DEFINED
  9. #include "include/core/SkPoint.h"
  10. #include "src/pathops/SkPathOpsDebug.h"
  11. #include "src/pathops/SkPathOpsTypes.h"
  12. class SkArenaAlloc;
  13. class SkOpAngle;
  14. class SkOpContour;
  15. class SkOpGlobalState;
  16. class SkOpSegment;
  17. class SkOpSpanBase;
  18. class SkOpSpan;
  19. struct SkPathOpsBounds;
  20. // subset of op span used by terminal span (when t is equal to one)
  21. class SkOpPtT {
  22. public:
  23. enum {
  24. kIsAlias = 1,
  25. kIsDuplicate = 1
  26. };
  27. const SkOpPtT* active() const;
  28. // please keep in sync with debugAddOpp()
  29. void addOpp(SkOpPtT* opp, SkOpPtT* oppPrev) {
  30. SkOpPtT* oldNext = this->fNext;
  31. SkASSERT(this != opp);
  32. this->fNext = opp;
  33. SkASSERT(oppPrev != oldNext);
  34. oppPrev->fNext = oldNext;
  35. }
  36. bool alias() const;
  37. bool coincident() const { return fCoincident; }
  38. bool contains(const SkOpPtT* ) const;
  39. bool contains(const SkOpSegment*, const SkPoint& ) const;
  40. bool contains(const SkOpSegment*, double t) const;
  41. const SkOpPtT* contains(const SkOpSegment* ) const;
  42. SkOpContour* contour() const;
  43. int debugID() const {
  44. return SkDEBUGRELEASE(fID, -1);
  45. }
  46. void debugAddOpp(const SkOpPtT* opp, const SkOpPtT* oppPrev) const;
  47. const SkOpAngle* debugAngle(int id) const;
  48. const SkOpCoincidence* debugCoincidence() const;
  49. bool debugContains(const SkOpPtT* ) const;
  50. const SkOpPtT* debugContains(const SkOpSegment* check) const;
  51. SkOpContour* debugContour(int id) const;
  52. const SkOpPtT* debugEnder(const SkOpPtT* end) const;
  53. int debugLoopLimit(bool report) const;
  54. bool debugMatchID(int id) const;
  55. const SkOpPtT* debugOppPrev(const SkOpPtT* opp) const;
  56. const SkOpPtT* debugPtT(int id) const;
  57. void debugResetCoinT() const;
  58. const SkOpSegment* debugSegment(int id) const;
  59. void debugSetCoinT(int ) const;
  60. const SkOpSpanBase* debugSpan(int id) const;
  61. void debugValidate() const;
  62. bool deleted() const {
  63. return fDeleted;
  64. }
  65. bool duplicate() const {
  66. return fDuplicatePt;
  67. }
  68. void dump() const; // available to testing only
  69. void dumpAll() const;
  70. void dumpBase() const;
  71. const SkOpPtT* find(const SkOpSegment* ) const;
  72. SkOpGlobalState* globalState() const;
  73. void init(SkOpSpanBase* , double t, const SkPoint& , bool dup);
  74. void insert(SkOpPtT* span) {
  75. SkASSERT(span != this);
  76. span->fNext = fNext;
  77. fNext = span;
  78. }
  79. const SkOpPtT* next() const {
  80. return fNext;
  81. }
  82. SkOpPtT* next() {
  83. return fNext;
  84. }
  85. bool onEnd() const;
  86. // returns nullptr if this is already in the opp ptT loop
  87. SkOpPtT* oppPrev(const SkOpPtT* opp) const {
  88. // find the fOpp ptr to opp
  89. SkOpPtT* oppPrev = opp->fNext;
  90. if (oppPrev == this) {
  91. return nullptr;
  92. }
  93. while (oppPrev->fNext != opp) {
  94. oppPrev = oppPrev->fNext;
  95. if (oppPrev == this) {
  96. return nullptr;
  97. }
  98. }
  99. return oppPrev;
  100. }
  101. static bool Overlaps(const SkOpPtT* s1, const SkOpPtT* e1, const SkOpPtT* s2,
  102. const SkOpPtT* e2, const SkOpPtT** sOut, const SkOpPtT** eOut) {
  103. const SkOpPtT* start1 = s1->fT < e1->fT ? s1 : e1;
  104. const SkOpPtT* start2 = s2->fT < e2->fT ? s2 : e2;
  105. *sOut = between(s1->fT, start2->fT, e1->fT) ? start2
  106. : between(s2->fT, start1->fT, e2->fT) ? start1 : nullptr;
  107. const SkOpPtT* end1 = s1->fT < e1->fT ? e1 : s1;
  108. const SkOpPtT* end2 = s2->fT < e2->fT ? e2 : s2;
  109. *eOut = between(s1->fT, end2->fT, e1->fT) ? end2
  110. : between(s2->fT, end1->fT, e2->fT) ? end1 : nullptr;
  111. if (*sOut == *eOut) {
  112. SkOPOBJASSERT(s1, start1->fT >= end2->fT || start2->fT >= end1->fT);
  113. return false;
  114. }
  115. SkASSERT(!*sOut || *sOut != *eOut);
  116. return *sOut && *eOut;
  117. }
  118. bool ptAlreadySeen(const SkOpPtT* head) const;
  119. SkOpPtT* prev();
  120. const SkOpSegment* segment() const;
  121. SkOpSegment* segment();
  122. void setCoincident() const {
  123. SkOPASSERT(!fDeleted);
  124. fCoincident = true;
  125. }
  126. void setDeleted();
  127. void setSpan(const SkOpSpanBase* span) {
  128. fSpan = const_cast<SkOpSpanBase*>(span);
  129. }
  130. const SkOpSpanBase* span() const {
  131. return fSpan;
  132. }
  133. SkOpSpanBase* span() {
  134. return fSpan;
  135. }
  136. const SkOpPtT* starter(const SkOpPtT* end) const {
  137. return fT < end->fT ? this : end;
  138. }
  139. double fT;
  140. SkPoint fPt; // cache of point value at this t
  141. protected:
  142. SkOpSpanBase* fSpan; // contains winding data
  143. SkOpPtT* fNext; // intersection on opposite curve or alias on this curve
  144. bool fDeleted; // set if removed from span list
  145. bool fDuplicatePt; // set if identical pt is somewhere in the next loop
  146. // below mutable since referrer is otherwise always const
  147. mutable bool fCoincident; // set if at some point a coincident span pointed here
  148. SkDEBUGCODE(int fID);
  149. };
  150. class SkOpSpanBase {
  151. public:
  152. enum class Collapsed {
  153. kNo,
  154. kYes,
  155. kError,
  156. };
  157. bool addOpp(SkOpSpanBase* opp);
  158. void bumpSpanAdds() {
  159. ++fSpanAdds;
  160. }
  161. bool chased() const {
  162. return fChased;
  163. }
  164. void checkForCollapsedCoincidence();
  165. const SkOpSpanBase* coinEnd() const {
  166. return fCoinEnd;
  167. }
  168. Collapsed collapsed(double s, double e) const;
  169. bool contains(const SkOpSpanBase* ) const;
  170. const SkOpPtT* contains(const SkOpSegment* ) const;
  171. bool containsCoinEnd(const SkOpSpanBase* coin) const {
  172. SkASSERT(this != coin);
  173. const SkOpSpanBase* next = this;
  174. while ((next = next->fCoinEnd) != this) {
  175. if (next == coin) {
  176. return true;
  177. }
  178. }
  179. return false;
  180. }
  181. bool containsCoinEnd(const SkOpSegment* ) const;
  182. SkOpContour* contour() const;
  183. int debugBumpCount() {
  184. return SkDEBUGRELEASE(++fCount, -1);
  185. }
  186. int debugID() const {
  187. return SkDEBUGRELEASE(fID, -1);
  188. }
  189. #if DEBUG_COIN
  190. void debugAddOpp(SkPathOpsDebug::GlitchLog* , const SkOpSpanBase* opp) const;
  191. #endif
  192. bool debugAlignedEnd(double t, const SkPoint& pt) const;
  193. bool debugAlignedInner() const;
  194. const SkOpAngle* debugAngle(int id) const;
  195. #if DEBUG_COIN
  196. void debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog* ) const;
  197. #endif
  198. const SkOpCoincidence* debugCoincidence() const;
  199. bool debugCoinEndLoopCheck() const;
  200. SkOpContour* debugContour(int id) const;
  201. #ifdef SK_DEBUG
  202. bool debugDeleted() const { return fDebugDeleted; }
  203. #endif
  204. #if DEBUG_COIN
  205. void debugInsertCoinEnd(SkPathOpsDebug::GlitchLog* ,
  206. const SkOpSpanBase* ) const;
  207. void debugMergeMatches(SkPathOpsDebug::GlitchLog* log,
  208. const SkOpSpanBase* opp) const;
  209. #endif
  210. const SkOpPtT* debugPtT(int id) const;
  211. void debugResetCoinT() const;
  212. const SkOpSegment* debugSegment(int id) const;
  213. void debugSetCoinT(int ) const;
  214. #ifdef SK_DEBUG
  215. void debugSetDeleted() { fDebugDeleted = true; }
  216. #endif
  217. const SkOpSpanBase* debugSpan(int id) const;
  218. const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const;
  219. SkOpGlobalState* globalState() const;
  220. void debugValidate() const;
  221. bool deleted() const {
  222. return fPtT.deleted();
  223. }
  224. void dump() const; // available to testing only
  225. void dumpCoin() const;
  226. void dumpAll() const;
  227. void dumpBase() const;
  228. void dumpHead() const;
  229. bool final() const {
  230. return fPtT.fT == 1;
  231. }
  232. SkOpAngle* fromAngle() const {
  233. return fFromAngle;
  234. }
  235. void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
  236. // Please keep this in sync with debugInsertCoinEnd()
  237. void insertCoinEnd(SkOpSpanBase* coin) {
  238. if (containsCoinEnd(coin)) {
  239. SkASSERT(coin->containsCoinEnd(this));
  240. return;
  241. }
  242. debugValidate();
  243. SkASSERT(this != coin);
  244. SkOpSpanBase* coinNext = coin->fCoinEnd;
  245. coin->fCoinEnd = this->fCoinEnd;
  246. this->fCoinEnd = coinNext;
  247. debugValidate();
  248. }
  249. void merge(SkOpSpan* span);
  250. bool mergeMatches(SkOpSpanBase* opp);
  251. const SkOpSpan* prev() const {
  252. return fPrev;
  253. }
  254. SkOpSpan* prev() {
  255. return fPrev;
  256. }
  257. const SkPoint& pt() const {
  258. return fPtT.fPt;
  259. }
  260. const SkOpPtT* ptT() const {
  261. return &fPtT;
  262. }
  263. SkOpPtT* ptT() {
  264. return &fPtT;
  265. }
  266. SkOpSegment* segment() const {
  267. return fSegment;
  268. }
  269. void setAligned() {
  270. fAligned = true;
  271. }
  272. void setChased(bool chased) {
  273. fChased = chased;
  274. }
  275. void setFromAngle(SkOpAngle* angle) {
  276. fFromAngle = angle;
  277. }
  278. void setPrev(SkOpSpan* prev) {
  279. fPrev = prev;
  280. }
  281. bool simple() const {
  282. fPtT.debugValidate();
  283. return fPtT.next()->next() == &fPtT;
  284. }
  285. int spanAddsCount() const {
  286. return fSpanAdds;
  287. }
  288. const SkOpSpan* starter(const SkOpSpanBase* end) const {
  289. const SkOpSpanBase* result = t() < end->t() ? this : end;
  290. return result->upCast();
  291. }
  292. SkOpSpan* starter(SkOpSpanBase* end) {
  293. SkASSERT(this->segment() == end->segment());
  294. SkOpSpanBase* result = t() < end->t() ? this : end;
  295. return result->upCast();
  296. }
  297. SkOpSpan* starter(SkOpSpanBase** endPtr) {
  298. SkOpSpanBase* end = *endPtr;
  299. SkASSERT(this->segment() == end->segment());
  300. SkOpSpanBase* result;
  301. if (t() < end->t()) {
  302. result = this;
  303. } else {
  304. result = end;
  305. *endPtr = this;
  306. }
  307. return result->upCast();
  308. }
  309. int step(const SkOpSpanBase* end) const {
  310. return t() < end->t() ? 1 : -1;
  311. }
  312. double t() const {
  313. return fPtT.fT;
  314. }
  315. void unaligned() {
  316. fAligned = false;
  317. }
  318. SkOpSpan* upCast() {
  319. SkASSERT(!final());
  320. return (SkOpSpan*) this;
  321. }
  322. const SkOpSpan* upCast() const {
  323. SkOPASSERT(!final());
  324. return (const SkOpSpan*) this;
  325. }
  326. SkOpSpan* upCastable() {
  327. return final() ? nullptr : upCast();
  328. }
  329. const SkOpSpan* upCastable() const {
  330. return final() ? nullptr : upCast();
  331. }
  332. private:
  333. void alignInner();
  334. protected: // no direct access to internals to avoid treating a span base as a span
  335. SkOpPtT fPtT; // list of points and t values associated with the start of this span
  336. SkOpSegment* fSegment; // segment that contains this span
  337. SkOpSpanBase* fCoinEnd; // linked list of coincident spans that end here (may point to itself)
  338. SkOpAngle* fFromAngle; // points to next angle from span start to end
  339. SkOpSpan* fPrev; // previous intersection point
  340. int fSpanAdds; // number of times intersections have been added to span
  341. bool fAligned;
  342. bool fChased; // set after span has been added to chase array
  343. SkDEBUGCODE(int fCount); // number of pt/t pairs added
  344. SkDEBUGCODE(int fID);
  345. SkDEBUGCODE(bool fDebugDeleted); // set when span was merged with another span
  346. };
  347. class SkOpSpan : public SkOpSpanBase {
  348. public:
  349. bool alreadyAdded() const {
  350. if (fAlreadyAdded) {
  351. return true;
  352. }
  353. return false;
  354. }
  355. bool clearCoincident() {
  356. SkASSERT(!final());
  357. if (fCoincident == this) {
  358. return false;
  359. }
  360. fCoincident = this;
  361. return true;
  362. }
  363. int computeWindSum();
  364. bool containsCoincidence(const SkOpSegment* ) const;
  365. bool containsCoincidence(const SkOpSpan* coin) const {
  366. SkASSERT(this != coin);
  367. const SkOpSpan* next = this;
  368. while ((next = next->fCoincident) != this) {
  369. if (next == coin) {
  370. return true;
  371. }
  372. }
  373. return false;
  374. }
  375. bool debugCoinLoopCheck() const;
  376. #if DEBUG_COIN
  377. void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* , const SkOpSpan* ) const;
  378. void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* ,
  379. const SkOpSegment* , bool flipped, bool ordered) const;
  380. #endif
  381. void dumpCoin() const;
  382. bool dumpSpan() const;
  383. bool done() const {
  384. SkASSERT(!final());
  385. return fDone;
  386. }
  387. void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
  388. bool insertCoincidence(const SkOpSegment* , bool flipped, bool ordered);
  389. // Please keep this in sync with debugInsertCoincidence()
  390. void insertCoincidence(SkOpSpan* coin) {
  391. if (containsCoincidence(coin)) {
  392. SkASSERT(coin->containsCoincidence(this));
  393. return;
  394. }
  395. debugValidate();
  396. SkASSERT(this != coin);
  397. SkOpSpan* coinNext = coin->fCoincident;
  398. coin->fCoincident = this->fCoincident;
  399. this->fCoincident = coinNext;
  400. debugValidate();
  401. }
  402. bool isCanceled() const {
  403. SkASSERT(!final());
  404. return fWindValue == 0 && fOppValue == 0;
  405. }
  406. bool isCoincident() const {
  407. SkASSERT(!final());
  408. return fCoincident != this;
  409. }
  410. void markAdded() {
  411. fAlreadyAdded = true;
  412. }
  413. SkOpSpanBase* next() const {
  414. SkASSERT(!final());
  415. return fNext;
  416. }
  417. int oppSum() const {
  418. SkASSERT(!final());
  419. return fOppSum;
  420. }
  421. int oppValue() const {
  422. SkASSERT(!final());
  423. return fOppValue;
  424. }
  425. void release(const SkOpPtT* );
  426. SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment);
  427. void setDone(bool done) {
  428. SkASSERT(!final());
  429. fDone = done;
  430. }
  431. void setNext(SkOpSpanBase* nextT) {
  432. SkASSERT(!final());
  433. fNext = nextT;
  434. }
  435. void setOppSum(int oppSum);
  436. void setOppValue(int oppValue) {
  437. SkASSERT(!final());
  438. SkASSERT(fOppSum == SK_MinS32);
  439. SkOPASSERT(!oppValue || !fDone);
  440. fOppValue = oppValue;
  441. }
  442. void setToAngle(SkOpAngle* angle) {
  443. SkASSERT(!final());
  444. fToAngle = angle;
  445. }
  446. void setWindSum(int windSum);
  447. void setWindValue(int windValue) {
  448. SkASSERT(!final());
  449. SkASSERT(windValue >= 0);
  450. SkASSERT(fWindSum == SK_MinS32);
  451. SkOPASSERT(!windValue || !fDone);
  452. fWindValue = windValue;
  453. }
  454. bool sortableTop(SkOpContour* );
  455. SkOpAngle* toAngle() const {
  456. SkASSERT(!final());
  457. return fToAngle;
  458. }
  459. int windSum() const {
  460. SkASSERT(!final());
  461. return fWindSum;
  462. }
  463. int windValue() const {
  464. SkOPASSERT(!final());
  465. return fWindValue;
  466. }
  467. private: // no direct access to internals to avoid treating a span base as a span
  468. SkOpSpan* fCoincident; // linked list of spans coincident with this one (may point to itself)
  469. SkOpAngle* fToAngle; // points to next angle from span start to end
  470. SkOpSpanBase* fNext; // next intersection point
  471. int fWindSum; // accumulated from contours surrounding this one.
  472. int fOppSum; // for binary operators: the opposite winding sum
  473. int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
  474. int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
  475. int fTopTTry; // specifies direction and t value to try next
  476. bool fDone; // if set, this span to next higher T has been processed
  477. bool fAlreadyAdded;
  478. };
  479. #endif