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