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