SkOpContour.cpp revision 07393cab57ce74a4aae89a31fae9aaa9780fc19d 
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#include "SkIntersections.h"
8#include "SkOpContour.h"
9#include "SkPathWriter.h"
10#include "TSearch.h"
11
12void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
13        const SkIntersections& ts, bool swap) {
14    SkCoincidence& coincidence = *fCoincidences.append();
15    coincidence.fContours[0] = this;  // FIXME: no need to store
16    coincidence.fContours[1] = other;
17    coincidence.fSegments[0] = index;
18    coincidence.fSegments[1] = otherIndex;
19    coincidence.fTs[swap][0] = ts[0][0];
20    coincidence.fTs[swap][1] = ts[0][1];
21    coincidence.fTs[!swap][0] = ts[1][0];
22    coincidence.fTs[!swap][1] = ts[1][1];
23    coincidence.fPts[0] = ts.pt(0).asSkPoint();
24    coincidence.fPts[1] = ts.pt(1).asSkPoint();
25}
26
27SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
28    int segmentCount = fSortedSegments.count();
29    SkASSERT(segmentCount > 0);
30    for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
31        SkOpSegment* testSegment = fSortedSegments[sortedIndex];
32        if (testSegment->done()) {
33            continue;
34        }
35        *start = *end = 0;
36        while (testSegment->nextCandidate(start, end)) {
37            if (!testSegment->isVertical(*start, *end)) {
38                return testSegment;
39            }
40        }
41    }
42    return NULL;
43}
44
45// first pass, add missing T values
46// second pass, determine winding values of overlaps
47void SkOpContour::addCoincidentPoints() {
48    int count = fCoincidences.count();
49    for (int index = 0; index < count; ++index) {
50        SkCoincidence& coincidence = fCoincidences[index];
51        SkASSERT(coincidence.fContours[0] == this);
52        int thisIndex = coincidence.fSegments[0];
53        SkOpSegment& thisOne = fSegments[thisIndex];
54        SkOpContour* otherContour = coincidence.fContours[1];
55        int otherIndex = coincidence.fSegments[1];
56        SkOpSegment& other = otherContour->fSegments[otherIndex];
57        if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
58            // OPTIMIZATION: remove from array
59            continue;
60        }
61    #if DEBUG_CONCIDENT
62        thisOne.debugShowTs();
63        other.debugShowTs();
64    #endif
65        double startT = coincidence.fTs[0][0];
66        double endT = coincidence.fTs[0][1];
67        bool cancelers;
68        if ((cancelers = startT > endT)) {
69            SkTSwap(startT, endT);
70            SkTSwap(coincidence.fPts[0], coincidence.fPts[1]);
71        }
72        SkASSERT(!approximately_negative(endT - startT));
73        double oStartT = coincidence.fTs[1][0];
74        double oEndT = coincidence.fTs[1][1];
75        if (oStartT > oEndT) {
76            SkTSwap<double>(oStartT, oEndT);
77            cancelers ^= true;
78        }
79        SkASSERT(!approximately_negative(oEndT - oStartT));
80        bool opp = fOperand ^ otherContour->fOperand;
81        if (cancelers && !opp) {
82            // make sure startT and endT have t entries
83            if (startT > 0 || oEndT < 1
84                    || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
85                thisOne.addTPair(startT, &other, oEndT, true, coincidence.fPts[0]);
86            }
87            if (oStartT > 0 || endT < 1
88                    || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
89                other.addTPair(oStartT, &thisOne, endT, true, coincidence.fPts[1]);
90            }
91        } else {
92            if (startT > 0 || oStartT > 0
93                    || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
94                thisOne.addTPair(startT, &other, oStartT, true, coincidence.fPts[0]);
95            }
96            if (endT < 1 || oEndT < 1
97                    || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
98                other.addTPair(oEndT, &thisOne, endT, true, coincidence.fPts[1]);
99            }
100        }
101    #if DEBUG_CONCIDENT
102        thisOne.debugShowTs();
103        other.debugShowTs();
104    #endif
105    }
106}
107
108void SkOpContour::calcCoincidentWinding() {
109    int count = fCoincidences.count();
110    for (int index = 0; index < count; ++index) {
111        SkCoincidence& coincidence = fCoincidences[index];
112        SkASSERT(coincidence.fContours[0] == this);
113        int thisIndex = coincidence.fSegments[0];
114        SkOpSegment& thisOne = fSegments[thisIndex];
115        if (thisOne.done()) {
116            continue;
117        }
118        SkOpContour* otherContour = coincidence.fContours[1];
119        int otherIndex = coincidence.fSegments[1];
120        SkOpSegment& other = otherContour->fSegments[otherIndex];
121        if (other.done()) {
122            continue;
123        }
124        double startT = coincidence.fTs[0][0];
125        double endT = coincidence.fTs[0][1];
126        bool cancelers;
127        if ((cancelers = startT > endT)) {
128            SkTSwap<double>(startT, endT);
129        }
130        SkASSERT(!approximately_negative(endT - startT));
131        double oStartT = coincidence.fTs[1][0];
132        double oEndT = coincidence.fTs[1][1];
133        if (oStartT > oEndT) {
134            SkTSwap<double>(oStartT, oEndT);
135            cancelers ^= true;
136        }
137        SkASSERT(!approximately_negative(oEndT - oStartT));
138        bool opp = fOperand ^ otherContour->fOperand;
139        if (cancelers && !opp) {
140            // make sure startT and endT have t entries
141            if (!thisOne.done() && !other.done()) {
142                thisOne.addTCancel(startT, endT, &other, oStartT, oEndT);
143            }
144        } else {
145            if (!thisOne.done() && !other.done()) {
146                thisOne.addTCoincident(startT, endT, &other, oStartT, oEndT);
147            }
148        }
149    #if DEBUG_CONCIDENT
150        thisOne.debugShowTs();
151        other.debugShowTs();
152    #endif
153    }
154}
155
156void SkOpContour::sortSegments() {
157    int segmentCount = fSegments.count();
158    fSortedSegments.setReserve(segmentCount);
159    for (int test = 0; test < segmentCount; ++test) {
160        *fSortedSegments.append() = &fSegments[test];
161    }
162    QSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
163    fFirstSorted = 0;
164}
165
166void SkOpContour::toPath(SkPathWriter* path) const {
167    int segmentCount = fSegments.count();
168    const SkPoint& pt = fSegments.front().pts()[0];
169    path->deferredMove(pt);
170    for (int test = 0; test < segmentCount; ++test) {
171        fSegments[test].addCurveTo(0, 1, path, true);
172    }
173    path->close();
174}
175
176void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
177        SkOpSegment** topStart) {
178    int segmentCount = fSortedSegments.count();
179    SkASSERT(segmentCount > 0);
180    int sortedIndex = fFirstSorted;
181    fDone = true;  // may be cleared below
182    for ( ; sortedIndex < segmentCount; ++sortedIndex) {
183        SkOpSegment* testSegment = fSortedSegments[sortedIndex];
184        if (testSegment->done()) {
185            if (sortedIndex == fFirstSorted) {
186                ++fFirstSorted;
187            }
188            continue;
189        }
190        fDone = false;
191        SkPoint testXY = testSegment->activeLeftTop(true, NULL);
192        if (*topStart) {
193            if (testXY.fY < topLeft.fY) {
194                continue;
195            }
196            if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
197                continue;
198            }
199            if (bestXY->fY < testXY.fY) {
200                continue;
201            }
202            if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
203                continue;
204            }
205        }
206        *topStart = testSegment;
207        *bestXY = testXY;
208    }
209}
210
211SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
212    int segmentCount = fSegments.count();
213    for (int test = 0; test < segmentCount; ++test) {
214        SkOpSegment* testSegment = &fSegments[test];
215        if (testSegment->done()) {
216            continue;
217        }
218        testSegment->undoneSpan(start, end);
219        return testSegment;
220    }
221    return NULL;
222}
223
224#if DEBUG_SHOW_WINDING
225int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
226    int count = fSegments.count();
227    int sum = 0;
228    for (int index = 0; index < count; ++index) {
229        sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
230    }
231//      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
232    return sum;
233}
234
235static void SkOpContour::debugShowWindingValues(const SkTDArray<SkOpContour*>& contourList) {
236//     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
237//    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
238    int ofInterest = 1 << 5 | 1 << 8;
239    int total = 0;
240    int index;
241    for (index = 0; index < contourList.count(); ++index) {
242        total += contourList[index]->segments().count();
243    }
244    int sum = 0;
245    for (index = 0; index < contourList.count(); ++index) {
246        sum += contourList[index]->debugShowWindingValues(total, ofInterest);
247    }
248//       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
249}
250#endif
251
252void SkOpContour::setBounds() {
253    int count = fSegments.count();
254    if (count == 0) {
255        SkDebugf("%s empty contour\n", __FUNCTION__);
256        SkASSERT(0);
257        // FIXME: delete empty contour?
258        return;
259    }
260    fBounds = fSegments.front().bounds();
261    for (int index = 1; index < count; ++index) {
262        fBounds.add(fSegments[index].bounds());
263    }
264}
265
266