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