1 /*
2 * Copyright 2014 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 "SkOpCoincidence.h"
8 #include "SkOpContour.h"
9 #include "SkOpSegment.h"
10 #include "SkPathWriter.h"
11
alias() const12 bool SkOpPtT::alias() const {
13 return this->span()->ptT() != this;
14 }
15
contour() const16 SkOpContour* SkOpPtT::contour() const {
17 return segment()->contour();
18 }
19
globalState() const20 SkOpGlobalState* SkOpPtT::globalState() const {
21 return contour()->globalState();
22 }
23
init(SkOpSpanBase * span,double t,const SkPoint & pt,bool duplicate)24 void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) {
25 fT = t;
26 fPt = pt;
27 fSpan = span;
28 fNext = this;
29 fDuplicatePt = duplicate;
30 fDeleted = false;
31 SkDEBUGCODE(fID = span->globalState()->nextPtTID());
32 }
33
onEnd() const34 bool SkOpPtT::onEnd() const {
35 const SkOpSpanBase* span = this->span();
36 if (span->ptT() != this) {
37 return false;
38 }
39 const SkOpSegment* segment = this->segment();
40 return span == segment->head() || span == segment->tail();
41 }
42
prev()43 SkOpPtT* SkOpPtT::prev() {
44 SkOpPtT* result = this;
45 SkOpPtT* next = this;
46 while ((next = next->fNext) != this) {
47 result = next;
48 }
49 SkASSERT(result->fNext == this);
50 return result;
51 }
52
remove()53 SkOpPtT* SkOpPtT::remove() {
54 SkOpPtT* prev = this;
55 do {
56 SkOpPtT* next = prev->fNext;
57 if (next == this) {
58 prev->removeNext(this);
59 SkASSERT(prev->fNext != prev);
60 fDeleted = true;
61 return prev;
62 }
63 prev = next;
64 } while (prev != this);
65 SkASSERT(0);
66 return NULL;
67 }
68
removeNext(SkOpPtT * kept)69 void SkOpPtT::removeNext(SkOpPtT* kept) {
70 SkASSERT(this->fNext);
71 SkOpPtT* next = this->fNext;
72 SkASSERT(this != next->fNext);
73 this->fNext = next->fNext;
74 SkOpSpanBase* span = next->span();
75 next->setDeleted();
76 if (span->ptT() == next) {
77 span->upCast()->detach(kept);
78 }
79 }
80
segment() const81 const SkOpSegment* SkOpPtT::segment() const {
82 return span()->segment();
83 }
84
segment()85 SkOpSegment* SkOpPtT::segment() {
86 return span()->segment();
87 }
88
align()89 void SkOpSpanBase::align() {
90 if (this->fAligned) {
91 return;
92 }
93 SkASSERT(!zero_or_one(this->fPtT.fT));
94 SkASSERT(this->fPtT.next());
95 // if a linked pt/t pair has a t of zero or one, use it as the base for alignment
96 SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
97 while ((ptT = ptT->next()) != stopPtT) {
98 if (zero_or_one(ptT->fT)) {
99 SkOpSegment* segment = ptT->segment();
100 SkASSERT(this->segment() != segment);
101 SkASSERT(segment->head()->ptT() == ptT || segment->tail()->ptT() == ptT);
102 if (ptT->fT) {
103 segment->tail()->alignEnd(1, segment->lastPt());
104 } else {
105 segment->head()->alignEnd(0, segment->pts()[0]);
106 }
107 return;
108 }
109 }
110 alignInner();
111 this->fAligned = true;
112 }
113
114
115 // FIXME: delete spans that collapse
116 // delete segments that collapse
117 // delete contours that collapse
alignEnd(double t,const SkPoint & pt)118 void SkOpSpanBase::alignEnd(double t, const SkPoint& pt) {
119 SkASSERT(zero_or_one(t));
120 SkOpSegment* segment = this->segment();
121 SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt);
122 alignInner();
123 *segment->writablePt(!!t) = pt;
124 SkOpPtT* ptT = &this->fPtT;
125 SkASSERT(t == ptT->fT);
126 SkASSERT(pt == ptT->fPt);
127 SkOpPtT* test = ptT, * stopPtT = ptT;
128 while ((test = test->next()) != stopPtT) {
129 SkOpSegment* other = test->segment();
130 if (other == this->segment()) {
131 continue;
132 }
133 if (!zero_or_one(test->fT)) {
134 continue;
135 }
136 *other->writablePt(!!test->fT) = pt;
137 }
138 this->fAligned = true;
139 }
140
alignInner()141 void SkOpSpanBase::alignInner() {
142 // force the spans to share points and t values
143 SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
144 const SkPoint& pt = ptT->fPt;
145 do {
146 ptT->fPt = pt;
147 const SkOpSpanBase* span = ptT->span();
148 SkOpPtT* test = ptT;
149 do {
150 SkOpPtT* prev = test;
151 if ((test = test->next()) == stopPtT) {
152 break;
153 }
154 if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) {
155 // omit aliases that alignment makes redundant
156 if ((!ptT->alias() || test->alias()) && (ptT->onEnd() || !test->onEnd())) {
157 SkASSERT(test->alias());
158 prev->removeNext(ptT);
159 test = prev;
160 } else {
161 SkASSERT(ptT->alias());
162 stopPtT = ptT = ptT->remove();
163 break;
164 }
165 }
166 } while (true);
167 } while ((ptT = ptT->next()) != stopPtT);
168 }
169
contains(const SkOpSpanBase * span) const170 bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
171 const SkOpPtT* start = &fPtT;
172 const SkOpPtT* check = &span->fPtT;
173 SkASSERT(start != check);
174 const SkOpPtT* walk = start;
175 while ((walk = walk->next()) != start) {
176 if (walk == check) {
177 return true;
178 }
179 }
180 return false;
181 }
182
contains(const SkOpSegment * segment)183 SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) {
184 SkOpPtT* start = &fPtT;
185 SkOpPtT* walk = start;
186 while ((walk = walk->next()) != start) {
187 if (walk->segment() == segment) {
188 return walk;
189 }
190 }
191 return NULL;
192 }
193
containsCoinEnd(const SkOpSegment * segment) const194 bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
195 SkASSERT(this->segment() != segment);
196 const SkOpSpanBase* next = this;
197 while ((next = next->fCoinEnd) != this) {
198 if (next->segment() == segment) {
199 return true;
200 }
201 }
202 return false;
203 }
204
contour() const205 SkOpContour* SkOpSpanBase::contour() const {
206 return segment()->contour();
207 }
208
globalState() const209 SkOpGlobalState* SkOpSpanBase::globalState() const {
210 return contour()->globalState();
211 }
212
initBase(SkOpSegment * segment,SkOpSpan * prev,double t,const SkPoint & pt)213 void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
214 fSegment = segment;
215 fPtT.init(this, t, pt, false);
216 fCoinEnd = this;
217 fFromAngle = NULL;
218 fPrev = prev;
219 fSpanAdds = 0;
220 fAligned = true;
221 fChased = false;
222 SkDEBUGCODE(fCount = 1);
223 SkDEBUGCODE(fID = globalState()->nextSpanID());
224 }
225
226 // this pair of spans share a common t value or point; merge them and eliminate duplicates
227 // this does not compute the best t or pt value; this merely moves all data into a single list
merge(SkOpSpan * span)228 void SkOpSpanBase::merge(SkOpSpan* span) {
229 SkOpPtT* spanPtT = span->ptT();
230 SkASSERT(this->t() != spanPtT->fT);
231 SkASSERT(!zero_or_one(spanPtT->fT));
232 span->detach(this->ptT());
233 SkOpPtT* remainder = spanPtT->next();
234 ptT()->insert(spanPtT);
235 while (remainder != spanPtT) {
236 SkOpPtT* next = remainder->next();
237 SkOpPtT* compare = spanPtT->next();
238 while (compare != spanPtT) {
239 SkOpPtT* nextC = compare->next();
240 if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
241 goto tryNextRemainder;
242 }
243 compare = nextC;
244 }
245 spanPtT->insert(remainder);
246 tryNextRemainder:
247 remainder = next;
248 }
249 fSpanAdds += span->fSpanAdds;
250 }
251
computeWindSum()252 int SkOpSpan::computeWindSum() {
253 SkOpGlobalState* globals = this->globalState();
254 SkOpContour* contourHead = globals->contourHead();
255 int windTry = 0;
256 while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
257 ;
258 }
259 return this->windSum();
260 }
261
containsCoincidence(const SkOpSegment * segment) const262 bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
263 SkASSERT(this->segment() != segment);
264 const SkOpSpan* next = fCoincident;
265 do {
266 if (next->segment() == segment) {
267 return true;
268 }
269 } while ((next = next->fCoincident) != this);
270 return false;
271 }
272
detach(SkOpPtT * kept)273 void SkOpSpan::detach(SkOpPtT* kept) {
274 SkASSERT(!final());
275 SkOpSpan* prev = this->prev();
276 SkASSERT(prev);
277 SkOpSpanBase* next = this->next();
278 SkASSERT(next);
279 prev->setNext(next);
280 next->setPrev(prev);
281 this->segment()->detach(this);
282 this->globalState()->coincidence()->fixUp(this->ptT(), kept);
283 this->ptT()->setDeleted();
284 }
285
init(SkOpSegment * segment,SkOpSpan * prev,double t,const SkPoint & pt)286 void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
287 SkASSERT(t != 1);
288 initBase(segment, prev, t, pt);
289 fCoincident = this;
290 fToAngle = NULL;
291 fWindSum = fOppSum = SK_MinS32;
292 fWindValue = 1;
293 fOppValue = 0;
294 fTopTTry = 0;
295 fChased = fDone = false;
296 segment->bumpCount();
297 }
298
setOppSum(int oppSum)299 void SkOpSpan::setOppSum(int oppSum) {
300 SkASSERT(!final());
301 if (fOppSum != SK_MinS32 && fOppSum != oppSum) {
302 this->globalState()->setWindingFailed();
303 return;
304 }
305 SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(oppSum) <= DEBUG_LIMIT_WIND_SUM);
306 fOppSum = oppSum;
307 }
308
setWindSum(int windSum)309 void SkOpSpan::setWindSum(int windSum) {
310 SkASSERT(!final());
311 if (fWindSum != SK_MinS32 && fWindSum != windSum) {
312 this->globalState()->setWindingFailed();
313 return;
314 }
315 SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(windSum) <= DEBUG_LIMIT_WIND_SUM);
316 fWindSum = windSum;
317 }
318