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