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