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