SkOpSpan.cpp revision 96fcdcc219d2a0d3579719b84b28bede76efba64
154359294a7c9dc54802d512a5d891a35c1663392caryclark/* 254359294a7c9dc54802d512a5d891a35c1663392caryclark * Copyright 2014 Google Inc. 354359294a7c9dc54802d512a5d891a35c1663392caryclark * 454359294a7c9dc54802d512a5d891a35c1663392caryclark * Use of this source code is governed by a BSD-style license that can be 554359294a7c9dc54802d512a5d891a35c1663392caryclark * found in the LICENSE file. 654359294a7c9dc54802d512a5d891a35c1663392caryclark */ 754359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpCoincidence.h" 854359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpContour.h" 954359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpSegment.h" 1054359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkPathWriter.h" 1154359294a7c9dc54802d512a5d891a35c1663392caryclark 1254359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpPtT::alias() const { 1354359294a7c9dc54802d512a5d891a35c1663392caryclark return this->span()->ptT() != this; 1454359294a7c9dc54802d512a5d891a35c1663392caryclark} 1554359294a7c9dc54802d512a5d891a35c1663392caryclark 16d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclarkbool SkOpPtT::collapsed(const SkOpPtT* check) const { 17d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark if (fPt != check->fPt) { 18d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark return false; 19d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark } 20d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark SkASSERT(this != check); 21d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark const SkOpSegment* segment = this->segment(); 22d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark SkASSERT(segment == check->segment()); 23d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark return segment->collapsed(); 24d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark} 25d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark 2627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclarkbool SkOpPtT::contains(const SkOpPtT* check) const { 2727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkASSERT(this != check); 2827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* ptT = this; 2927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* stopPtT = ptT; 3027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while ((ptT = ptT->next()) != stopPtT) { 3127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (ptT == check) { 3227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return true; 3327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 3427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 3527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return false; 3627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 3727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 3827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclarkSkOpPtT* SkOpPtT::contains(const SkOpSegment* check) { 3927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkASSERT(this->segment() != check); 4027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkOpPtT* ptT = this; 4127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* stopPtT = ptT; 4227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while ((ptT = ptT->next()) != stopPtT) { 4327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (ptT->segment() == check) { 4427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return ptT; 4527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 4627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 4796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 4827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 4927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 5054359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpContour* SkOpPtT::contour() const { 5154359294a7c9dc54802d512a5d891a35c1663392caryclark return segment()->contour(); 5254359294a7c9dc54802d512a5d891a35c1663392caryclark} 5354359294a7c9dc54802d512a5d891a35c1663392caryclark 5427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclarkSkOpPtT* SkOpPtT::doppelganger() { 5527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkASSERT(fDeleted); 5627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkOpPtT* ptT = fNext; 5727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while (ptT->fDeleted) { 5827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark ptT = ptT->fNext; 5927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 6027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* stopPtT = ptT; 6127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 6227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (ptT->fSpan == fSpan) { 6327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return ptT; 6427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 6527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark ptT = ptT->fNext; 6627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } while (stopPtT != ptT); 6727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkASSERT(0); 6896fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 6927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 7027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 7127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclarkSkOpPtT* SkOpPtT::find(SkOpSegment* segment) { 7227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkOpPtT* ptT = this; 7327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark const SkOpPtT* stopPtT = ptT; 7427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 7527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (ptT->segment() == segment) { 7627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return ptT; 7727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 7827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark ptT = ptT->fNext; 7927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } while (stopPtT != ptT); 8027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkASSERT(0); 8196fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 8227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 8327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 8454359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpGlobalState* SkOpPtT::globalState() const { 8554359294a7c9dc54802d512a5d891a35c1663392caryclark return contour()->globalState(); 8654359294a7c9dc54802d512a5d891a35c1663392caryclark} 8754359294a7c9dc54802d512a5d891a35c1663392caryclark 8854359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) { 8954359294a7c9dc54802d512a5d891a35c1663392caryclark fT = t; 9054359294a7c9dc54802d512a5d891a35c1663392caryclark fPt = pt; 9154359294a7c9dc54802d512a5d891a35c1663392caryclark fSpan = span; 9254359294a7c9dc54802d512a5d891a35c1663392caryclark fNext = this; 9354359294a7c9dc54802d512a5d891a35c1663392caryclark fDuplicatePt = duplicate; 9454359294a7c9dc54802d512a5d891a35c1663392caryclark fDeleted = false; 951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fID = span->globalState()->nextPtTID()); 9654359294a7c9dc54802d512a5d891a35c1663392caryclark} 9754359294a7c9dc54802d512a5d891a35c1663392caryclark 9854359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpPtT::onEnd() const { 9954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* span = this->span(); 10054359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->ptT() != this) { 10154359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 10254359294a7c9dc54802d512a5d891a35c1663392caryclark } 10354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSegment* segment = this->segment(); 10454359294a7c9dc54802d512a5d891a35c1663392caryclark return span == segment->head() || span == segment->tail(); 10554359294a7c9dc54802d512a5d891a35c1663392caryclark} 10654359294a7c9dc54802d512a5d891a35c1663392caryclark 10754359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpPtT* SkOpPtT::prev() { 10854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* result = this; 10954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* next = this; 11054359294a7c9dc54802d512a5d891a35c1663392caryclark while ((next = next->fNext) != this) { 11154359294a7c9dc54802d512a5d891a35c1663392caryclark result = next; 11254359294a7c9dc54802d512a5d891a35c1663392caryclark } 11354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(result->fNext == this); 11454359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 11554359294a7c9dc54802d512a5d891a35c1663392caryclark} 11654359294a7c9dc54802d512a5d891a35c1663392caryclark 11754359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpPtT* SkOpPtT::remove() { 11854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* prev = this; 11954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 12054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* next = prev->fNext; 12154359294a7c9dc54802d512a5d891a35c1663392caryclark if (next == this) { 12254359294a7c9dc54802d512a5d891a35c1663392caryclark prev->removeNext(this); 12354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(prev->fNext != prev); 12454359294a7c9dc54802d512a5d891a35c1663392caryclark fDeleted = true; 12554359294a7c9dc54802d512a5d891a35c1663392caryclark return prev; 12654359294a7c9dc54802d512a5d891a35c1663392caryclark } 12754359294a7c9dc54802d512a5d891a35c1663392caryclark prev = next; 12854359294a7c9dc54802d512a5d891a35c1663392caryclark } while (prev != this); 12954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0); 13096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 13154359294a7c9dc54802d512a5d891a35c1663392caryclark} 13254359294a7c9dc54802d512a5d891a35c1663392caryclark 13354359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpPtT::removeNext(SkOpPtT* kept) { 13454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->fNext); 13554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* next = this->fNext; 13654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this != next->fNext); 13754359294a7c9dc54802d512a5d891a35c1663392caryclark this->fNext = next->fNext; 13854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* span = next->span(); 13954359294a7c9dc54802d512a5d891a35c1663392caryclark next->setDeleted(); 14054359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->ptT() == next) { 14154359294a7c9dc54802d512a5d891a35c1663392caryclark span->upCast()->detach(kept); 14254359294a7c9dc54802d512a5d891a35c1663392caryclark } 14354359294a7c9dc54802d512a5d891a35c1663392caryclark} 14454359294a7c9dc54802d512a5d891a35c1663392caryclark 14554359294a7c9dc54802d512a5d891a35c1663392caryclarkconst SkOpSegment* SkOpPtT::segment() const { 14654359294a7c9dc54802d512a5d891a35c1663392caryclark return span()->segment(); 14754359294a7c9dc54802d512a5d891a35c1663392caryclark} 14854359294a7c9dc54802d512a5d891a35c1663392caryclark 14954359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpPtT::segment() { 15054359294a7c9dc54802d512a5d891a35c1663392caryclark return span()->segment(); 15154359294a7c9dc54802d512a5d891a35c1663392caryclark} 15254359294a7c9dc54802d512a5d891a35c1663392caryclark 15354359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpanBase::align() { 15454359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->fAligned) { 15554359294a7c9dc54802d512a5d891a35c1663392caryclark return; 15654359294a7c9dc54802d512a5d891a35c1663392caryclark } 15754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!zero_or_one(this->fPtT.fT)); 15854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->fPtT.next()); 15954359294a7c9dc54802d512a5d891a35c1663392caryclark // if a linked pt/t pair has a t of zero or one, use it as the base for alignment 16054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT; 16154359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != stopPtT) { 16254359294a7c9dc54802d512a5d891a35c1663392caryclark if (zero_or_one(ptT->fT)) { 16354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = ptT->segment(); 16454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->segment() != segment); 16554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(segment->head()->ptT() == ptT || segment->tail()->ptT() == ptT); 16654359294a7c9dc54802d512a5d891a35c1663392caryclark if (ptT->fT) { 16754359294a7c9dc54802d512a5d891a35c1663392caryclark segment->tail()->alignEnd(1, segment->lastPt()); 16854359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 16954359294a7c9dc54802d512a5d891a35c1663392caryclark segment->head()->alignEnd(0, segment->pts()[0]); 17054359294a7c9dc54802d512a5d891a35c1663392caryclark } 17154359294a7c9dc54802d512a5d891a35c1663392caryclark return; 17254359294a7c9dc54802d512a5d891a35c1663392caryclark } 17354359294a7c9dc54802d512a5d891a35c1663392caryclark } 17454359294a7c9dc54802d512a5d891a35c1663392caryclark alignInner(); 17554359294a7c9dc54802d512a5d891a35c1663392caryclark this->fAligned = true; 17654359294a7c9dc54802d512a5d891a35c1663392caryclark} 17754359294a7c9dc54802d512a5d891a35c1663392caryclark 17854359294a7c9dc54802d512a5d891a35c1663392caryclark 17954359294a7c9dc54802d512a5d891a35c1663392caryclark// FIXME: delete spans that collapse 18054359294a7c9dc54802d512a5d891a35c1663392caryclark// delete segments that collapse 18154359294a7c9dc54802d512a5d891a35c1663392caryclark// delete contours that collapse 18254359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpanBase::alignEnd(double t, const SkPoint& pt) { 18354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(zero_or_one(t)); 18454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = this->segment(); 18554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt); 18654359294a7c9dc54802d512a5d891a35c1663392caryclark alignInner(); 18754359294a7c9dc54802d512a5d891a35c1663392caryclark *segment->writablePt(!!t) = pt; 18854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = &this->fPtT; 18954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(t == ptT->fT); 19054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(pt == ptT->fPt); 19154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* test = ptT, * stopPtT = ptT; 19254359294a7c9dc54802d512a5d891a35c1663392caryclark while ((test = test->next()) != stopPtT) { 19354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = test->segment(); 19454359294a7c9dc54802d512a5d891a35c1663392caryclark if (other == this->segment()) { 19554359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 19654359294a7c9dc54802d512a5d891a35c1663392caryclark } 19754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!zero_or_one(test->fT)) { 19854359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 19954359294a7c9dc54802d512a5d891a35c1663392caryclark } 20054359294a7c9dc54802d512a5d891a35c1663392caryclark *other->writablePt(!!test->fT) = pt; 20154359294a7c9dc54802d512a5d891a35c1663392caryclark } 20254359294a7c9dc54802d512a5d891a35c1663392caryclark this->fAligned = true; 20354359294a7c9dc54802d512a5d891a35c1663392caryclark} 20454359294a7c9dc54802d512a5d891a35c1663392caryclark 20554359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpanBase::alignInner() { 20654359294a7c9dc54802d512a5d891a35c1663392caryclark // force the spans to share points and t values 20754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT; 20854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkPoint& pt = ptT->fPt; 20954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 21054359294a7c9dc54802d512a5d891a35c1663392caryclark ptT->fPt = pt; 21154359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* span = ptT->span(); 21254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* test = ptT; 21354359294a7c9dc54802d512a5d891a35c1663392caryclark do { 21454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* prev = test; 21554359294a7c9dc54802d512a5d891a35c1663392caryclark if ((test = test->next()) == stopPtT) { 21654359294a7c9dc54802d512a5d891a35c1663392caryclark break; 21754359294a7c9dc54802d512a5d891a35c1663392caryclark } 21854359294a7c9dc54802d512a5d891a35c1663392caryclark if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) { 21954359294a7c9dc54802d512a5d891a35c1663392caryclark // omit aliases that alignment makes redundant 22054359294a7c9dc54802d512a5d891a35c1663392caryclark if ((!ptT->alias() || test->alias()) && (ptT->onEnd() || !test->onEnd())) { 22154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(test->alias()); 22254359294a7c9dc54802d512a5d891a35c1663392caryclark prev->removeNext(ptT); 22354359294a7c9dc54802d512a5d891a35c1663392caryclark test = prev; 22454359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 22554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(ptT->alias()); 22654359294a7c9dc54802d512a5d891a35c1663392caryclark stopPtT = ptT = ptT->remove(); 22754359294a7c9dc54802d512a5d891a35c1663392caryclark break; 22854359294a7c9dc54802d512a5d891a35c1663392caryclark } 22954359294a7c9dc54802d512a5d891a35c1663392caryclark } 23054359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 23154359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((ptT = ptT->next()) != stopPtT); 23254359294a7c9dc54802d512a5d891a35c1663392caryclark} 23354359294a7c9dc54802d512a5d891a35c1663392caryclark 23454359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSpanBase::contains(const SkOpSpanBase* span) const { 23554359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* start = &fPtT; 23654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* check = &span->fPtT; 23754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != check); 23854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* walk = start; 23954359294a7c9dc54802d512a5d891a35c1663392caryclark while ((walk = walk->next()) != start) { 24054359294a7c9dc54802d512a5d891a35c1663392caryclark if (walk == check) { 24154359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 24254359294a7c9dc54802d512a5d891a35c1663392caryclark } 24354359294a7c9dc54802d512a5d891a35c1663392caryclark } 24454359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 24554359294a7c9dc54802d512a5d891a35c1663392caryclark} 24654359294a7c9dc54802d512a5d891a35c1663392caryclark 24754359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) { 24854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* start = &fPtT; 24954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* walk = start; 25054359294a7c9dc54802d512a5d891a35c1663392caryclark while ((walk = walk->next()) != start) { 25154359294a7c9dc54802d512a5d891a35c1663392caryclark if (walk->segment() == segment) { 25254359294a7c9dc54802d512a5d891a35c1663392caryclark return walk; 25354359294a7c9dc54802d512a5d891a35c1663392caryclark } 25454359294a7c9dc54802d512a5d891a35c1663392caryclark } 25596fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 25654359294a7c9dc54802d512a5d891a35c1663392caryclark} 25754359294a7c9dc54802d512a5d891a35c1663392caryclark 25854359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const { 25954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->segment() != segment); 26054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* next = this; 26154359294a7c9dc54802d512a5d891a35c1663392caryclark while ((next = next->fCoinEnd) != this) { 26254359294a7c9dc54802d512a5d891a35c1663392caryclark if (next->segment() == segment) { 26354359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 26454359294a7c9dc54802d512a5d891a35c1663392caryclark } 26554359294a7c9dc54802d512a5d891a35c1663392caryclark } 26654359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 26754359294a7c9dc54802d512a5d891a35c1663392caryclark} 26854359294a7c9dc54802d512a5d891a35c1663392caryclark 26954359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpContour* SkOpSpanBase::contour() const { 27054359294a7c9dc54802d512a5d891a35c1663392caryclark return segment()->contour(); 27154359294a7c9dc54802d512a5d891a35c1663392caryclark} 27254359294a7c9dc54802d512a5d891a35c1663392caryclark 27354359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpGlobalState* SkOpSpanBase::globalState() const { 27454359294a7c9dc54802d512a5d891a35c1663392caryclark return contour()->globalState(); 27554359294a7c9dc54802d512a5d891a35c1663392caryclark} 27654359294a7c9dc54802d512a5d891a35c1663392caryclark 27754359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) { 27854359294a7c9dc54802d512a5d891a35c1663392caryclark fSegment = segment; 27954359294a7c9dc54802d512a5d891a35c1663392caryclark fPtT.init(this, t, pt, false); 28054359294a7c9dc54802d512a5d891a35c1663392caryclark fCoinEnd = this; 28196fcdcc219d2a0d3579719b84b28bede76efba64halcanary fFromAngle = nullptr; 28254359294a7c9dc54802d512a5d891a35c1663392caryclark fPrev = prev; 28308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark fSpanAdds = 0; 28454359294a7c9dc54802d512a5d891a35c1663392caryclark fAligned = true; 28554359294a7c9dc54802d512a5d891a35c1663392caryclark fChased = false; 2861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fCount = 1); 2871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fID = globalState()->nextSpanID()); 28854359294a7c9dc54802d512a5d891a35c1663392caryclark} 28954359294a7c9dc54802d512a5d891a35c1663392caryclark 29054359294a7c9dc54802d512a5d891a35c1663392caryclark// this pair of spans share a common t value or point; merge them and eliminate duplicates 29154359294a7c9dc54802d512a5d891a35c1663392caryclark// this does not compute the best t or pt value; this merely moves all data into a single list 29254359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpanBase::merge(SkOpSpan* span) { 29354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* spanPtT = span->ptT(); 29454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->t() != spanPtT->fT); 29554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!zero_or_one(spanPtT->fT)); 29654359294a7c9dc54802d512a5d891a35c1663392caryclark span->detach(this->ptT()); 29754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* remainder = spanPtT->next(); 29854359294a7c9dc54802d512a5d891a35c1663392caryclark ptT()->insert(spanPtT); 29954359294a7c9dc54802d512a5d891a35c1663392caryclark while (remainder != spanPtT) { 30054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* next = remainder->next(); 30154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* compare = spanPtT->next(); 30254359294a7c9dc54802d512a5d891a35c1663392caryclark while (compare != spanPtT) { 30354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* nextC = compare->next(); 30454359294a7c9dc54802d512a5d891a35c1663392caryclark if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) { 30554359294a7c9dc54802d512a5d891a35c1663392caryclark goto tryNextRemainder; 30654359294a7c9dc54802d512a5d891a35c1663392caryclark } 30754359294a7c9dc54802d512a5d891a35c1663392caryclark compare = nextC; 30854359294a7c9dc54802d512a5d891a35c1663392caryclark } 30954359294a7c9dc54802d512a5d891a35c1663392caryclark spanPtT->insert(remainder); 31054359294a7c9dc54802d512a5d891a35c1663392caryclarktryNextRemainder: 31154359294a7c9dc54802d512a5d891a35c1663392caryclark remainder = next; 31254359294a7c9dc54802d512a5d891a35c1663392caryclark } 31308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark fSpanAdds += span->fSpanAdds; 31454359294a7c9dc54802d512a5d891a35c1663392caryclark} 31554359294a7c9dc54802d512a5d891a35c1663392caryclark 316bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclarkint SkOpSpan::computeWindSum() { 317bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpGlobalState* globals = this->globalState(); 318bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpContour* contourHead = globals->contourHead(); 319bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark int windTry = 0; 320bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) { 321bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark ; 322bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 323bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark return this->windSum(); 324bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark} 325bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark 32654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const { 32754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this->segment() != segment); 32854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* next = fCoincident; 32954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 33054359294a7c9dc54802d512a5d891a35c1663392caryclark if (next->segment() == segment) { 33154359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 33254359294a7c9dc54802d512a5d891a35c1663392caryclark } 33354359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((next = next->fCoincident) != this); 33454359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 33554359294a7c9dc54802d512a5d891a35c1663392caryclark} 33654359294a7c9dc54802d512a5d891a35c1663392caryclark 33754359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpan::detach(SkOpPtT* kept) { 33854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 33954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prev = this->prev(); 34054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(prev); 34154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = this->next(); 34254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(next); 34354359294a7c9dc54802d512a5d891a35c1663392caryclark prev->setNext(next); 34454359294a7c9dc54802d512a5d891a35c1663392caryclark next->setPrev(prev); 34554359294a7c9dc54802d512a5d891a35c1663392caryclark this->segment()->detach(this); 346218f21ac09c70b98a10cb8e1999b85a22fa0b151caryclark SkOpCoincidence* coincidence = this->globalState()->coincidence(); 347218f21ac09c70b98a10cb8e1999b85a22fa0b151caryclark if (coincidence) { 348218f21ac09c70b98a10cb8e1999b85a22fa0b151caryclark coincidence->fixUp(this->ptT(), kept); 349218f21ac09c70b98a10cb8e1999b85a22fa0b151caryclark } 35054359294a7c9dc54802d512a5d891a35c1663392caryclark this->ptT()->setDeleted(); 35154359294a7c9dc54802d512a5d891a35c1663392caryclark} 35254359294a7c9dc54802d512a5d891a35c1663392caryclark 35354359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) { 35454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(t != 1); 35554359294a7c9dc54802d512a5d891a35c1663392caryclark initBase(segment, prev, t, pt); 35654359294a7c9dc54802d512a5d891a35c1663392caryclark fCoincident = this; 35796fcdcc219d2a0d3579719b84b28bede76efba64halcanary fToAngle = nullptr; 35854359294a7c9dc54802d512a5d891a35c1663392caryclark fWindSum = fOppSum = SK_MinS32; 35954359294a7c9dc54802d512a5d891a35c1663392caryclark fWindValue = 1; 36054359294a7c9dc54802d512a5d891a35c1663392caryclark fOppValue = 0; 361624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fTopTTry = 0; 36254359294a7c9dc54802d512a5d891a35c1663392caryclark fChased = fDone = false; 36354359294a7c9dc54802d512a5d891a35c1663392caryclark segment->bumpCount(); 36454359294a7c9dc54802d512a5d891a35c1663392caryclark} 36554359294a7c9dc54802d512a5d891a35c1663392caryclark 36654359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSpan::setOppSum(int oppSum) { 36754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!final()); 36854359294a7c9dc54802d512a5d891a35c1663392caryclark if (fOppSum != SK_MinS32 && fOppSum != oppSum) { 36954359294a7c9dc54802d512a5d891a35c1663392caryclark this->globalState()->setWindingFailed(); 37054359294a7c9dc54802d512a5d891a35c1663392caryclark return; 37154359294a7c9dc54802d512a5d891a35c1663392caryclark } 37260e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(oppSum) <= DEBUG_LIMIT_WIND_SUM); 37354359294a7c9dc54802d512a5d891a35c1663392caryclark fOppSum = oppSum; 37454359294a7c9dc54802d512a5d891a35c1663392caryclark} 375624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 376624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkvoid SkOpSpan::setWindSum(int windSum) { 377624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkASSERT(!final()); 378624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (fWindSum != SK_MinS32 && fWindSum != windSum) { 379624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark this->globalState()->setWindingFailed(); 380624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return; 381624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 38260e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM); 383624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fWindSum = windSum; 384624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 385