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