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