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