SkOpContour.cpp revision d892bd8ba676d34d4ce4a73ac7aad88e102fad70 
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 "SkTSort.h"
11
12void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
13        const SkIntersections& ts, bool swap) {
14    SkCoincidence& coincidence = fCoincidences.push_back();
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 startSwapped, oStartSwapped, cancelers;
68        if ((cancelers = startSwapped = startT > endT)) {
69            SkTSwap(startT, endT);
70        }
71        SkASSERT(!approximately_negative(endT - startT));
72        double oStartT = coincidence.fTs[1][0];
73        double oEndT = coincidence.fTs[1][1];
74        if ((oStartSwapped = oStartT > oEndT)) {
75            SkTSwap(oStartT, oEndT);
76            cancelers ^= true;
77        }
78        SkASSERT(!approximately_negative(oEndT - oStartT));
79        if (cancelers) {
80            // make sure startT and endT have t entries
81            if (startT > 0 || oEndT < 1
82                    || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
83                thisOne.addTPair(startT, &other, oEndT, true, coincidence.fPts[startSwapped]);
84            }
85            if (oStartT > 0 || endT < 1
86                    || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
87                other.addTPair(oStartT, &thisOne, endT, true, coincidence.fPts[oStartSwapped]);
88            }
89        } else {
90            if (startT > 0 || oStartT > 0
91                    || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
92                thisOne.addTPair(startT, &other, oStartT, true, coincidence.fPts[startSwapped]);
93            }
94            if (endT < 1 || oEndT < 1
95                    || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
96                other.addTPair(oEndT, &thisOne, endT, true, coincidence.fPts[!oStartSwapped]);
97            }
98        }
99    #if DEBUG_CONCIDENT
100        thisOne.debugShowTs();
101        other.debugShowTs();
102    #endif
103    }
104}
105
106void SkOpContour::calcCoincidentWinding() {
107    int count = fCoincidences.count();
108    for (int index = 0; index < count; ++index) {
109        SkCoincidence& coincidence = fCoincidences[index];
110        SkASSERT(coincidence.fContours[0] == this);
111        int thisIndex = coincidence.fSegments[0];
112        SkOpSegment& thisOne = fSegments[thisIndex];
113        if (thisOne.done()) {
114            continue;
115        }
116        SkOpContour* otherContour = coincidence.fContours[1];
117        int otherIndex = coincidence.fSegments[1];
118        SkOpSegment& other = otherContour->fSegments[otherIndex];
119        if (other.done()) {
120            continue;
121        }
122        double startT = coincidence.fTs[0][0];
123        double endT = coincidence.fTs[0][1];
124        bool cancelers;
125        if ((cancelers = startT > endT)) {
126            SkTSwap<double>(startT, endT);
127        }
128        SkASSERT(!approximately_negative(endT - startT));
129        double oStartT = coincidence.fTs[1][0];
130        double oEndT = coincidence.fTs[1][1];
131        if (oStartT > oEndT) {
132            SkTSwap<double>(oStartT, oEndT);
133            cancelers ^= true;
134        }
135        SkASSERT(!approximately_negative(oEndT - oStartT));
136        if (cancelers) {
137            // make sure startT and endT have t entries
138            if (!thisOne.done() && !other.done()) {
139                thisOne.addTCancel(startT, endT, &other, oStartT, oEndT);
140            }
141        } else {
142            if (!thisOne.done() && !other.done()) {
143                thisOne.addTCoincident(startT, endT, &other, oStartT, oEndT);
144            }
145        }
146    #if DEBUG_CONCIDENT
147        thisOne.debugShowTs();
148        other.debugShowTs();
149    #endif
150    }
151}
152
153void SkOpContour::sortSegments() {
154    int segmentCount = fSegments.count();
155    fSortedSegments.push_back_n(segmentCount);
156    for (int test = 0; test < segmentCount; ++test) {
157        fSortedSegments[test] = &fSegments[test];
158    }
159    SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
160    fFirstSorted = 0;
161}
162
163void SkOpContour::toPath(SkPathWriter* path) const {
164    int segmentCount = fSegments.count();
165    const SkPoint& pt = fSegments.front().pts()[0];
166    path->deferredMove(pt);
167    for (int test = 0; test < segmentCount; ++test) {
168        fSegments[test].addCurveTo(0, 1, path, true);
169    }
170    path->close();
171}
172
173void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
174        SkOpSegment** topStart) {
175    int segmentCount = fSortedSegments.count();
176    SkASSERT(segmentCount > 0);
177    int sortedIndex = fFirstSorted;
178    fDone = true;  // may be cleared below
179    for ( ; sortedIndex < segmentCount; ++sortedIndex) {
180        SkOpSegment* testSegment = fSortedSegments[sortedIndex];
181        if (testSegment->done()) {
182            if (sortedIndex == fFirstSorted) {
183                ++fFirstSorted;
184            }
185            continue;
186        }
187        fDone = false;
188        SkPoint testXY = testSegment->activeLeftTop(true, NULL);
189        if (*topStart) {
190            if (testXY.fY < topLeft.fY) {
191                continue;
192            }
193            if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
194                continue;
195            }
196            if (bestXY->fY < testXY.fY) {
197                continue;
198            }
199            if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
200                continue;
201            }
202        }
203        *topStart = testSegment;
204        *bestXY = testXY;
205    }
206}
207
208SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
209    int segmentCount = fSegments.count();
210    for (int test = 0; test < segmentCount; ++test) {
211        SkOpSegment* testSegment = &fSegments[test];
212        if (testSegment->done()) {
213            continue;
214        }
215        testSegment->undoneSpan(start, end);
216        return testSegment;
217    }
218    return NULL;
219}
220
221#if DEBUG_SHOW_WINDING
222int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
223    int count = fSegments.count();
224    int sum = 0;
225    for (int index = 0; index < count; ++index) {
226        sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
227    }
228//      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
229    return sum;
230}
231
232static void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
233//     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
234//    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
235    int ofInterest = 1 << 5 | 1 << 8;
236    int total = 0;
237    int index;
238    for (index = 0; index < contourList.count(); ++index) {
239        total += contourList[index]->segments().count();
240    }
241    int sum = 0;
242    for (index = 0; index < contourList.count(); ++index) {
243        sum += contourList[index]->debugShowWindingValues(total, ofInterest);
244    }
245//       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
246}
247#endif
248
249void SkOpContour::setBounds() {
250    int count = fSegments.count();
251    if (count == 0) {
252        SkDebugf("%s empty contour\n", __FUNCTION__);
253        SkASSERT(0);
254        // FIXME: delete empty contour?
255        return;
256    }
257    fBounds = fSegments.front().bounds();
258    for (int index = 1; index < count; ++index) {
259        fBounds.add(fSegments[index].bounds());
260    }
261}
262