SkOpContour.h revision 624637cc8ec22c000409704d0b403ac1b81ad4b0 
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 addConic(SkPoint pts[3], SkScalar weight, SkChunkAlloc* allocator) {
38        appendSegment(allocator).addConic(pts, weight, this);
39    }
40
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
47    void addLine(SkPoint pts[2], SkChunkAlloc* allocator) {
48        appendSegment(allocator).addLine(pts, this);
49    }
50
51    void addQuad(SkPoint pts[3], SkChunkAlloc* allocator) {
52        appendSegment(allocator).addQuad(pts, this);
53    }
54
55    void align() {
56        SkASSERT(fCount > 0);
57        SkOpSegment* segment = &fHead;
58        do {
59            segment->align();
60        } while ((segment = segment->next()));
61    }
62
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
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
86    const SkPathOpsBounds& bounds() const {
87        return fBounds;
88    }
89
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
98    void complete() {
99        setBounds();
100    }
101
102    int count() const {
103        return fCount;
104    }
105
106    int debugID() const {
107        return SkDEBUGRELEASE(fID, -1);
108    }
109
110    int debugIndent() const {
111        return SkDEBUGRELEASE(fDebugIndent, 0);
112    }
113
114#if DEBUG_ACTIVE_SPANS
115    void debugShowActiveSpans() {
116        SkOpSegment* segment = &fHead;
117        do {
118            segment->debugShowActiveSpans();
119        } while ((segment = segment->next()));
120    }
121#endif
122
123    const SkOpAngle* debugAngle(int id) const {
124        return SkDEBUGRELEASE(this->globalState()->debugAngle(id), NULL);
125    }
126
127    SkOpContour* debugContour(int id) {
128        return SkDEBUGRELEASE(this->globalState()->debugContour(id), NULL);
129    }
130
131    const SkOpPtT* debugPtT(int id) const {
132        return SkDEBUGRELEASE(this->globalState()->debugPtT(id), NULL);
133    }
134
135    const SkOpSegment* debugSegment(int id) const {
136        return SkDEBUGRELEASE(this->globalState()->debugSegment(id), NULL);
137    }
138
139    const SkOpSpanBase* debugSpan(int id) const {
140        return SkDEBUGRELEASE(this->globalState()->debugSpan(id), NULL);
141    }
142
143    SkOpGlobalState* globalState() const {
144        return fState;
145    }
146
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
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
183    const SkPoint& end() const {
184        return fTail->pts()[SkPathOpsVerbToPoints(fTail->verb())];
185    }
186
187    SkOpSpan* findSortableTop(SkOpContour* );
188
189    SkOpSegment* first() {
190        SkASSERT(fCount > 0);
191        return &fHead;
192    }
193
194    const SkOpSegment* first() const {
195        SkASSERT(fCount > 0);
196        return &fHead;
197    }
198
199    void indentDump() const {
200        SkDEBUGCODE(fDebugIndent += 2);
201    }
202
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
210    bool isXor() const {
211        return fXor;
212    }
213
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
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
235    void moveNearby() {
236        SkASSERT(fCount > 0);
237        SkOpSegment* segment = &fHead;
238        do {
239            segment->moveNearby();
240        } while ((segment = segment->next()));
241    }
242
243    SkOpContour* next() {
244        return fNext;
245    }
246
247    const SkOpContour* next() const {
248        return fNext;
249    }
250
251    bool operand() const {
252        return fOperand;
253    }
254
255    bool oppXor() const {
256        return fOppXor;
257    }
258
259    void outdentDump() const {
260        SkDEBUGCODE(fDebugIndent -= 2);
261    }
262
263    void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkChunkAlloc* );
264
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
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
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
301    void setGlobalState(SkOpGlobalState* state) {
302        fState = state;
303    }
304
305    void setNext(SkOpContour* contour) {
306//        SkASSERT(!fNext == !!contour);
307        fNext = contour;
308    }
309
310    void setOperand(bool isOp) {
311        fOperand = isOp;
312    }
313
314    void setOppXor(bool isOppXor) {
315        fOppXor = isOppXor;
316    }
317
318    void setXor(bool isXor) {
319        fXor = isXor;
320    }
321
322    SkPath::Verb simplifyCubic(SkPoint pts[4]);
323
324    void sortAngles() {
325        SkASSERT(fCount > 0);
326        SkOpSegment* segment = &fHead;
327        do {
328            segment->sortAngles();
329        } while ((segment = segment->next()));
330    }
331
332    const SkPoint& start() const {
333        return fHead.pts()[0];
334    }
335
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
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
353private:
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
370class SkOpContourHead : public SkOpContour {
371};
372
373#endif
374