SkOpSegment.h 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455
  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 SkOpSegment_DEFINE
  8. #define SkOpSegment_DEFINE
  9. #include "src/core/SkArenaAlloc.h"
  10. #include "src/pathops/SkOpAngle.h"
  11. #include "src/pathops/SkOpSpan.h"
  12. #include "src/pathops/SkPathOpsBounds.h"
  13. #include "src/pathops/SkPathOpsCubic.h"
  14. #include "src/pathops/SkPathOpsCurve.h"
  15. struct SkDCurve;
  16. class SkOpCoincidence;
  17. class SkOpContour;
  18. enum class SkOpRayDir;
  19. struct SkOpRayHit;
  20. class SkPathWriter;
  21. class SkOpSegment {
  22. public:
  23. bool operator<(const SkOpSegment& rh) const {
  24. return fBounds.fTop < rh.fBounds.fTop;
  25. }
  26. SkOpAngle* activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr,
  27. bool* done);
  28. SkOpAngle* activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
  29. SkOpSpanBase** endPtr, bool* done);
  30. SkOpAngle* activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
  31. SkOpSpanBase** endPtr, bool* done);
  32. bool activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
  33. SkPathOp op);
  34. bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, SkPathOp op,
  35. int* sumMiWinding, int* sumSuWinding);
  36. bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end);
  37. bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding);
  38. SkOpSegment* addConic(SkPoint pts[3], SkScalar weight, SkOpContour* parent) {
  39. init(pts, weight, parent, SkPath::kConic_Verb);
  40. SkDCurve curve;
  41. curve.fConic.set(pts, weight);
  42. curve.setConicBounds(pts, weight, 0, 1, &fBounds);
  43. return this;
  44. }
  45. SkOpSegment* addCubic(SkPoint pts[4], SkOpContour* parent) {
  46. init(pts, 1, parent, SkPath::kCubic_Verb);
  47. SkDCurve curve;
  48. curve.fCubic.set(pts);
  49. curve.setCubicBounds(pts, 1, 0, 1, &fBounds);
  50. return this;
  51. }
  52. bool addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path) const;
  53. SkOpAngle* addEndSpan() {
  54. SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
  55. angle->set(&fTail, fTail.prev());
  56. fTail.setFromAngle(angle);
  57. return angle;
  58. }
  59. bool addExpanded(double newT, const SkOpSpanBase* test, bool* startOver);
  60. SkOpSegment* addLine(SkPoint pts[2], SkOpContour* parent) {
  61. SkASSERT(pts[0] != pts[1]);
  62. init(pts, 1, parent, SkPath::kLine_Verb);
  63. fBounds.set(pts, 2);
  64. return this;
  65. }
  66. SkOpPtT* addMissing(double t, SkOpSegment* opp, bool* allExist);
  67. SkOpAngle* addStartSpan() {
  68. SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
  69. angle->set(&fHead, fHead.next());
  70. fHead.setToAngle(angle);
  71. return angle;
  72. }
  73. SkOpSegment* addQuad(SkPoint pts[3], SkOpContour* parent) {
  74. init(pts, 1, parent, SkPath::kQuad_Verb);
  75. SkDCurve curve;
  76. curve.fQuad.set(pts);
  77. curve.setQuadBounds(pts, 1, 0, 1, &fBounds);
  78. return this;
  79. }
  80. SkOpPtT* addT(double t);
  81. SkOpPtT* addT(double t, const SkPoint& pt);
  82. const SkPathOpsBounds& bounds() const {
  83. return fBounds;
  84. }
  85. void bumpCount() {
  86. ++fCount;
  87. }
  88. void calcAngles();
  89. SkOpSpanBase::Collapsed collapsed(double startT, double endT) const;
  90. static bool ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
  91. SkOpAngle::IncludeType );
  92. static bool ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
  93. SkOpAngle::IncludeType );
  94. int computeSum(SkOpSpanBase* start, SkOpSpanBase* end, SkOpAngle::IncludeType includeType);
  95. void clearAll();
  96. void clearOne(SkOpSpan* span);
  97. static void ClearVisited(SkOpSpanBase* span);
  98. bool contains(double t) const;
  99. SkOpContour* contour() const {
  100. return fContour;
  101. }
  102. int count() const {
  103. return fCount;
  104. }
  105. void debugAddAngle(double startT, double endT);
  106. #if DEBUG_COIN
  107. const SkOpPtT* debugAddT(double t, SkPathOpsDebug::GlitchLog* ) const;
  108. #endif
  109. const SkOpAngle* debugAngle(int id) const;
  110. #if DEBUG_ANGLE
  111. void debugCheckAngleCoin() const;
  112. #endif
  113. #if DEBUG_COIN
  114. void debugCheckHealth(SkPathOpsDebug::GlitchLog* ) const;
  115. void debugClearAll(SkPathOpsDebug::GlitchLog* glitches) const;
  116. void debugClearOne(const SkOpSpan* span, SkPathOpsDebug::GlitchLog* glitches) const;
  117. #endif
  118. const SkOpCoincidence* debugCoincidence() const;
  119. SkOpContour* debugContour(int id) const;
  120. int debugID() const {
  121. return SkDEBUGRELEASE(fID, -1);
  122. }
  123. SkOpAngle* debugLastAngle();
  124. #if DEBUG_COIN
  125. void debugMissingCoincidence(SkPathOpsDebug::GlitchLog* glitches) const;
  126. void debugMoveMultiples(SkPathOpsDebug::GlitchLog* glitches) const;
  127. void debugMoveNearby(SkPathOpsDebug::GlitchLog* glitches) const;
  128. #endif
  129. const SkOpPtT* debugPtT(int id) const;
  130. void debugReset();
  131. const SkOpSegment* debugSegment(int id) const;
  132. #if DEBUG_ACTIVE_SPANS
  133. void debugShowActiveSpans(SkString* str) const;
  134. #endif
  135. #if DEBUG_MARK_DONE
  136. void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding);
  137. void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, int oppWinding);
  138. #endif
  139. const SkOpSpanBase* debugSpan(int id) const;
  140. void debugValidate() const;
  141. #if DEBUG_COINCIDENCE_ORDER
  142. void debugResetCoinT() const;
  143. void debugSetCoinT(int, SkScalar ) const;
  144. #endif
  145. #if DEBUG_COIN
  146. static void DebugClearVisited(const SkOpSpanBase* span);
  147. bool debugVisited() const {
  148. if (!fDebugVisited) {
  149. fDebugVisited = true;
  150. return false;
  151. }
  152. return true;
  153. }
  154. #endif
  155. #if DEBUG_ANGLE
  156. double distSq(double t, const SkOpAngle* opp) const;
  157. #endif
  158. bool done() const {
  159. SkOPASSERT(fDoneCount <= fCount);
  160. return fDoneCount == fCount;
  161. }
  162. bool done(const SkOpAngle* angle) const {
  163. return angle->start()->starter(angle->end())->done();
  164. }
  165. SkDPoint dPtAtT(double mid) const {
  166. return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
  167. }
  168. SkDVector dSlopeAtT(double mid) const {
  169. return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid);
  170. }
  171. void dump() const;
  172. void dumpAll() const;
  173. void dumpAngles() const;
  174. void dumpCoin() const;
  175. void dumpPts(const char* prefix = "seg") const;
  176. void dumpPtsInner(const char* prefix = "seg") const;
  177. const SkOpPtT* existing(double t, const SkOpSegment* opp) const;
  178. SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
  179. SkOpSpanBase** nextEnd, bool* unsortable, bool* simple,
  180. SkPathOp op, int xorMiMask, int xorSuMask);
  181. SkOpSegment* findNextWinding(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
  182. SkOpSpanBase** nextEnd, bool* unsortable);
  183. SkOpSegment* findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable);
  184. SkOpSpan* findSortableTop(SkOpContour* );
  185. SkOpGlobalState* globalState() const;
  186. const SkOpSpan* head() const {
  187. return &fHead;
  188. }
  189. SkOpSpan* head() {
  190. return &fHead;
  191. }
  192. void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);
  193. SkOpSpan* insert(SkOpSpan* prev) {
  194. SkOpGlobalState* globalState = this->globalState();
  195. globalState->setAllocatedOpSpan();
  196. SkOpSpan* result = globalState->allocator()->make<SkOpSpan>();
  197. SkOpSpanBase* next = prev->next();
  198. result->setPrev(prev);
  199. prev->setNext(result);
  200. SkDEBUGCODE(result->ptT()->fT = 0);
  201. result->setNext(next);
  202. if (next) {
  203. next->setPrev(result);
  204. }
  205. return result;
  206. }
  207. bool isClose(double t, const SkOpSegment* opp) const;
  208. bool isHorizontal() const {
  209. return fBounds.fTop == fBounds.fBottom;
  210. }
  211. SkOpSegment* isSimple(SkOpSpanBase** end, int* step) const {
  212. return nextChase(end, step, nullptr, nullptr);
  213. }
  214. bool isVertical() const {
  215. return fBounds.fLeft == fBounds.fRight;
  216. }
  217. bool isVertical(SkOpSpanBase* start, SkOpSpanBase* end) const {
  218. return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t());
  219. }
  220. bool isXor() const;
  221. void joinEnds(SkOpSegment* start) {
  222. fTail.ptT()->addOpp(start->fHead.ptT(), start->fHead.ptT());
  223. }
  224. const SkPoint& lastPt() const {
  225. return fPts[SkPathOpsVerbToPoints(fVerb)];
  226. }
  227. void markAllDone();
  228. bool markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end, SkOpSpanBase** found);
  229. bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
  230. SkOpSpanBase** lastPtr);
  231. bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
  232. int oppWinding, SkOpSpanBase** lastPtr);
  233. bool markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle, SkOpSpanBase** result);
  234. bool markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
  235. const SkOpAngle* angle, SkOpSpanBase** result);
  236. void markDone(SkOpSpan* );
  237. bool markWinding(SkOpSpan* , int winding);
  238. bool markWinding(SkOpSpan* , int winding, int oppWinding);
  239. bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const;
  240. bool missingCoincidence();
  241. bool moveMultiples();
  242. bool moveNearby();
  243. SkOpSegment* next() const {
  244. return fNext;
  245. }
  246. SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const;
  247. bool operand() const;
  248. static int OppSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
  249. int result = start->t() < end->t() ? -start->upCast()->oppValue()
  250. : end->upCast()->oppValue();
  251. return result;
  252. }
  253. bool oppXor() const;
  254. const SkOpSegment* prev() const {
  255. return fPrev;
  256. }
  257. SkPoint ptAtT(double mid) const {
  258. return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
  259. }
  260. const SkPoint* pts() const {
  261. return fPts;
  262. }
  263. bool ptsDisjoint(const SkOpPtT& span, const SkOpPtT& test) const {
  264. SkASSERT(this == span.segment());
  265. SkASSERT(this == test.segment());
  266. return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt);
  267. }
  268. bool ptsDisjoint(const SkOpPtT& span, double t, const SkPoint& pt) const {
  269. SkASSERT(this == span.segment());
  270. return ptsDisjoint(span.fT, span.fPt, t, pt);
  271. }
  272. bool ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const;
  273. void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkArenaAlloc*);
  274. void release(const SkOpSpan* );
  275. #if DEBUG_COIN
  276. void resetDebugVisited() const {
  277. fDebugVisited = false;
  278. }
  279. #endif
  280. void resetVisited() {
  281. fVisited = false;
  282. }
  283. void setContour(SkOpContour* contour) {
  284. fContour = contour;
  285. }
  286. void setNext(SkOpSegment* next) {
  287. fNext = next;
  288. }
  289. void setPrev(SkOpSegment* prev) {
  290. fPrev = prev;
  291. }
  292. void setUpWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* maxWinding, int* sumWinding) {
  293. int deltaSum = SpanSign(start, end);
  294. *maxWinding = *sumWinding;
  295. if (*sumWinding == SK_MinS32) {
  296. return;
  297. }
  298. *sumWinding -= deltaSum;
  299. }
  300. void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
  301. int* maxWinding, int* sumWinding);
  302. void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, int* sumSuWinding,
  303. int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
  304. bool sortAngles();
  305. bool spansNearby(const SkOpSpanBase* ref, const SkOpSpanBase* check, bool* found) const;
  306. static int SpanSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
  307. int result = start->t() < end->t() ? -start->upCast()->windValue()
  308. : end->upCast()->windValue();
  309. return result;
  310. }
  311. SkOpAngle* spanToAngle(SkOpSpanBase* start, SkOpSpanBase* end) {
  312. SkASSERT(start != end);
  313. return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle();
  314. }
  315. bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const;
  316. const SkOpSpanBase* tail() const {
  317. return &fTail;
  318. }
  319. SkOpSpanBase* tail() {
  320. return &fTail;
  321. }
  322. bool testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, const SkOpSpanBase* prior,
  323. const SkOpSpanBase* spanBase, const SkOpSegment* opp) const;
  324. SkOpSpan* undoneSpan();
  325. int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const;
  326. int updateOppWinding(const SkOpAngle* angle) const;
  327. int updateOppWindingReverse(const SkOpAngle* angle) const;
  328. int updateWinding(SkOpSpanBase* start, SkOpSpanBase* end);
  329. int updateWinding(SkOpAngle* angle);
  330. int updateWindingReverse(const SkOpAngle* angle);
  331. static bool UseInnerWinding(int outerWinding, int innerWinding);
  332. SkPath::Verb verb() const {
  333. return fVerb;
  334. }
  335. // look for two different spans that point to the same opposite segment
  336. bool visited() {
  337. if (!fVisited) {
  338. fVisited = true;
  339. return false;
  340. }
  341. return true;
  342. }
  343. SkScalar weight() const {
  344. return fWeight;
  345. }
  346. SkOpSpan* windingSpanAtT(double tHit);
  347. int windSum(const SkOpAngle* angle) const;
  348. private:
  349. SkOpSpan fHead; // the head span always has its t set to zero
  350. SkOpSpanBase fTail; // the tail span always has its t set to one
  351. SkOpContour* fContour;
  352. SkOpSegment* fNext; // forward-only linked list used by contour to walk the segments
  353. const SkOpSegment* fPrev;
  354. SkPoint* fPts; // pointer into array of points owned by edge builder that may be tweaked
  355. SkPathOpsBounds fBounds; // tight bounds
  356. SkScalar fWeight;
  357. int fCount; // number of spans (one for a non-intersecting segment)
  358. int fDoneCount; // number of processed spans (zero initially)
  359. SkPath::Verb fVerb;
  360. bool fVisited; // used by missing coincidence check
  361. #if DEBUG_COIN
  362. mutable bool fDebugVisited; // used by debug missing coincidence check
  363. #endif
  364. #if DEBUG_COINCIDENCE_ORDER
  365. mutable int fDebugBaseIndex;
  366. mutable SkScalar fDebugBaseMin; // if > 0, the 1st t value in this seg vis-a-vis the ref seg
  367. mutable SkScalar fDebugBaseMax;
  368. mutable int fDebugLastIndex;
  369. mutable SkScalar fDebugLastMin; // if > 0, the last t -- next t val - base has same sign
  370. mutable SkScalar fDebugLastMax;
  371. #endif
  372. SkDEBUGCODE(int fID);
  373. };
  374. #endif