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 12 bool SkOpPtT::alias() const { 13 return this->span()->ptT() != this; 14 } 15 16 SkOpContour* SkOpPtT::contour() const { 17 return segment()->contour(); 18 } 19 20 SkOpGlobalState* SkOpPtT::globalState() const { 21 return contour()->globalState(); 22 } 23 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 34 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 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 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 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 81 const SkOpSegment* SkOpPtT::segment() const { 82 return span()->segment(); 83 } 84 85 SkOpSegment* SkOpPtT::segment() { 86 return span()->segment(); 87 } 88 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 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 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 170 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 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 194 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 205 SkOpContour* SkOpSpanBase::contour() const { 206 return segment()->contour(); 207 } 208 209 SkOpGlobalState* SkOpSpanBase::globalState() const { 210 return contour()->globalState(); 211 } 212 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 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 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 262 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 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 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 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 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
