SkOpContour.h revision 0bcb8ca8a8fc04a4a9c69013ccc46645d2f2ae77 
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 "SkTArray.h"
12
13#if defined(SK_DEBUG) || !FORCE_RELEASE
14#include "SkThread.h"
15#endif
16
17class SkIntersections;
18class SkOpContour;
19class SkPathWriter;
20
21struct SkCoincidence {
22    SkOpContour* fOther;
23    int fSegments[2];
24    double fTs[2][2];
25    SkPoint fPts[2];
26};
27
28class SkOpContour {
29public:
30    SkOpContour() {
31        reset();
32#if defined(SK_DEBUG) || !FORCE_RELEASE
33        fID = sk_atomic_inc(&SkPathOpsDebug::gContourID);
34#endif
35    }
36
37    bool operator<(const SkOpContour& rh) const {
38        return fBounds.fTop == rh.fBounds.fTop
39                ? fBounds.fLeft < rh.fBounds.fLeft
40                : fBounds.fTop < rh.fBounds.fTop;
41    }
42
43    bool addCoincident(int index, SkOpContour* other, int otherIndex,
44                       const SkIntersections& ts, bool swap);
45    void addCoincidentPoints();
46
47    void addCross(const SkOpContour* crosser) {
48#ifdef DEBUG_CROSS
49        for (int index = 0; index < fCrosses.count(); ++index) {
50            SkASSERT(fCrosses[index] != crosser);
51        }
52#endif
53        fCrosses.push_back(crosser);
54    }
55
56    void addCubic(const SkPoint pts[4]) {
57        fSegments.push_back().addCubic(pts, fOperand, fXor);
58        fContainsCurves = fContainsCubics = true;
59    }
60
61    int addLine(const SkPoint pts[2]) {
62        fSegments.push_back().addLine(pts, fOperand, fXor);
63        return fSegments.count();
64    }
65
66    void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
67        fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
68    }
69
70    bool addPartialCoincident(int index, SkOpContour* other, int otherIndex,
71                       const SkIntersections& ts, int ptIndex, bool swap);
72
73    int addQuad(const SkPoint pts[3]) {
74        fSegments.push_back().addQuad(pts, fOperand, fXor);
75        fContainsCurves = true;
76        return fSegments.count();
77    }
78
79    int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
80        setContainsIntercepts();
81        return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
82    }
83
84    int addSelfT(int segIndex, const SkPoint& pt, double newT) {
85        setContainsIntercepts();
86        return fSegments[segIndex].addSelfT(pt, newT);
87    }
88
89    const SkPathOpsBounds& bounds() const {
90        return fBounds;
91    }
92
93    bool calcAngles();
94    void calcCoincidentWinding();
95    void calcPartialCoincidentWinding();
96
97    void checkDuplicates() {
98        int segmentCount = fSegments.count();
99        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
100            SkOpSegment& segment = fSegments[sIndex];
101            if (segment.count() > 2) {
102                segment.checkDuplicates();
103            }
104        }
105    }
106
107    void checkEnds() {
108        if (!fContainsCurves) {
109            return;
110        }
111        int segmentCount = fSegments.count();
112        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
113            SkOpSegment* segment = &fSegments[sIndex];
114            if (segment->verb() == SkPath::kLine_Verb) {
115                continue;
116            }
117            if (segment->done()) {
118                continue;   // likely coincident, nothing to do
119            }
120            segment->checkEnds();
121        }
122    }
123
124    void checkMultiples() {
125        int segmentCount = fSegments.count();
126        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
127            SkOpSegment& segment = fSegments[sIndex];
128            if (segment.count() > 2) {
129                segment.checkMultiples();
130            }
131        }
132    }
133
134    void checkSmall() {
135        int segmentCount = fSegments.count();
136        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
137            SkOpSegment& segment = fSegments[sIndex];
138            if (segment.hasSmall()) {
139                segment.checkSmall();
140            }
141        }
142    }
143
144    // if same point has different T values, choose a common T
145    void checkTiny() {
146        int segmentCount = fSegments.count();
147        if (segmentCount <= 2) {
148            return;
149        }
150        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
151            SkOpSegment& segment = fSegments[sIndex];
152            if (segment.hasTiny()) {
153                segment.checkTiny();
154            }
155        }
156    }
157
158    void complete() {
159        setBounds();
160        fContainsIntercepts = false;
161    }
162
163    bool containsCubics() const {
164        return fContainsCubics;
165    }
166
167    bool crosses(const SkOpContour* crosser) const {
168        for (int index = 0; index < fCrosses.count(); ++index) {
169            if (fCrosses[index] == crosser) {
170                return true;
171            }
172        }
173        return false;
174    }
175
176    bool done() const {
177        return fDone;
178    }
179
180    const SkPoint& end() const {
181        const SkOpSegment& segment = fSegments.back();
182        return segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
183    }
184
185    void fixOtherTIndex() {
186        int segmentCount = fSegments.count();
187        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
188            fSegments[sIndex].fixOtherTIndex();
189        }
190    }
191
192    void joinCoincidence() {
193        joinCoincidence(fCoincidences, false);
194        joinCoincidence(fPartialCoincidences, true);
195    }
196
197    SkOpSegment* nonVerticalSegment(int* start, int* end);
198
199    bool operand() const {
200        return fOperand;
201    }
202
203    void reset() {
204        fSegments.reset();
205        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
206        fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = false;
207    }
208
209    SkTArray<SkOpSegment>& segments() {
210        return fSegments;
211    }
212
213    void setContainsIntercepts() {
214        fContainsIntercepts = true;
215    }
216
217    void setOperand(bool isOp) {
218        fOperand = isOp;
219    }
220
221    void setOppXor(bool isOppXor) {
222        fOppXor = isOppXor;
223        int segmentCount = fSegments.count();
224        for (int test = 0; test < segmentCount; ++test) {
225            fSegments[test].setOppXor(isOppXor);
226        }
227    }
228
229    void setXor(bool isXor) {
230        fXor = isXor;
231    }
232
233    void sortAngles();
234    void sortSegments();
235
236    const SkPoint& start() const {
237        return fSegments.front().pts()[0];
238    }
239
240    void toPath(SkPathWriter* path) const;
241
242    void toPartialBackward(SkPathWriter* path) const {
243        int segmentCount = fSegments.count();
244        for (int test = segmentCount - 1; test >= 0; --test) {
245            fSegments[test].addCurveTo(1, 0, path, true);
246        }
247    }
248
249    void toPartialForward(SkPathWriter* path) const {
250        int segmentCount = fSegments.count();
251        for (int test = 0; test < segmentCount; ++test) {
252            fSegments[test].addCurveTo(0, 1, path, true);
253        }
254    }
255
256    void topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, SkOpSegment** topStart);
257    SkOpSegment* undoneSegment(int* start, int* end);
258
259    int updateSegment(int index, const SkPoint* pts) {
260        SkOpSegment& segment = fSegments[index];
261        segment.updatePts(pts);
262        return SkPathOpsVerbToPoints(segment.verb()) + 1;
263    }
264
265#if DEBUG_TEST
266    SkTArray<SkOpSegment>& debugSegments() {
267        return fSegments;
268    }
269#endif
270
271#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
272    void debugShowActiveSpans() {
273        for (int index = 0; index < fSegments.count(); ++index) {
274            fSegments[index].debugShowActiveSpans();
275        }
276    }
277#endif
278
279#if DEBUG_SHOW_WINDING
280    int debugShowWindingValues(int totalSegments, int ofInterest);
281    static void debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList);
282#endif
283
284    // available to test routines only
285    void dump() const;
286    void dumpAngles() const;
287    void dumpPts() const;
288    void dumpSpans() const;
289
290private:
291    void calcCommonCoincidentWinding(const SkCoincidence& );
292    void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
293    void setBounds();
294
295    SkTArray<SkOpSegment> fSegments;
296    SkTArray<SkOpSegment*, true> fSortedSegments;
297    int fFirstSorted;
298    SkTArray<SkCoincidence, true> fCoincidences;
299    SkTArray<SkCoincidence, true> fPartialCoincidences;
300    SkTArray<const SkOpContour*, true> fCrosses;
301    SkPathOpsBounds fBounds;
302    bool fContainsIntercepts;  // FIXME: is this used by anybody?
303    bool fContainsCubics;
304    bool fContainsCurves;
305    bool fDone;
306    bool fOperand;  // true for the second argument to a binary operator
307    bool fXor;
308    bool fOppXor;
309#if defined(SK_DEBUG) || !FORCE_RELEASE
310    int debugID() const { return fID; }
311    int fID;
312#else
313    int debugID() const { return -1; }
314#endif
315};
316
317#endif
318