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