107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 754359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpCoincidence.h" 8dac1d17027dcaa5596885a9f333979418b35001ccaryclark#include "SkOpContour.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkOpSegment.h" 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathWriter.h" 11df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark#include "SkPointPriv.h" 1254359294a7c9dc54802d512a5d891a35c1663392caryclark 1354359294a7c9dc54802d512a5d891a35c1663392caryclark/* 1454359294a7c9dc54802d512a5d891a35c1663392caryclarkAfter computing raw intersections, post process all segments to: 1554359294a7c9dc54802d512a5d891a35c1663392caryclark- find small collections of points that can be collapsed to a single point 1654359294a7c9dc54802d512a5d891a35c1663392caryclark- find missing intersections to resolve differences caused by different algorithms 1754359294a7c9dc54802d512a5d891a35c1663392caryclark 1854359294a7c9dc54802d512a5d891a35c1663392caryclarkConsider segments containing tiny or small intervals. Consider coincident segments 1954359294a7c9dc54802d512a5d891a35c1663392caryclarkbecause coincidence finds intersections through distance measurement that non-coincident 2054359294a7c9dc54802d512a5d891a35c1663392caryclarkintersection tests cannot. 2154359294a7c9dc54802d512a5d891a35c1663392caryclark */ 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define F (false) // discard the edge 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define T (true) // keep the edge 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic const bool gUnaryActiveEdge[2][2] = { 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// from=0 from=1 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// to=0,1 to=0,1 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {F, T}, {T, F}, 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com}; 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3254359294a7c9dc54802d512a5d891a35c1663392caryclarkstatic const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = { 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// miFrom=0 miFrom=1 344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// miTo=0 miTo=1 miTo=0 miTo=1 354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com}; 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#undef F 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#undef T 4507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4654359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, 47bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase** endPtr, bool* done) { 48bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) { 494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return result; 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 51bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) { 5254359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5496fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 5607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5754359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr, 58bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase** endPtr, bool* done) { 5954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* upSpan = start->upCastable(); 6054359294a7c9dc54802d512a5d891a35c1663392caryclark if (upSpan) { 6154359294a7c9dc54802d512a5d891a35c1663392caryclark if (upSpan->windValue() || upSpan->oppValue()) { 6254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = upSpan->next(); 6354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!*endPtr) { 6454359294a7c9dc54802d512a5d891a35c1663392caryclark *startPtr = start; 6554359294a7c9dc54802d512a5d891a35c1663392caryclark *endPtr = next; 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!upSpan->done()) { 6854359294a7c9dc54802d512a5d891a35c1663392caryclark if (upSpan->windSum() != SK_MinS32) { 6954359294a7c9dc54802d512a5d891a35c1663392caryclark return spanToAngle(start, next); 704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *done = false; 724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 7454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(upSpan->done()); 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* downSpan = start->prev(); 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // edge leading into junction 7954359294a7c9dc54802d512a5d891a35c1663392caryclark if (downSpan) { 8054359294a7c9dc54802d512a5d891a35c1663392caryclark if (downSpan->windValue() || downSpan->oppValue()) { 8154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!*endPtr) { 8254359294a7c9dc54802d512a5d891a35c1663392caryclark *startPtr = start; 8354359294a7c9dc54802d512a5d891a35c1663392caryclark *endPtr = downSpan; 8454359294a7c9dc54802d512a5d891a35c1663392caryclark } 8554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!downSpan->done()) { 8654359294a7c9dc54802d512a5d891a35c1663392caryclark if (downSpan->windSum() != SK_MinS32) { 8754359294a7c9dc54802d512a5d891a35c1663392caryclark return spanToAngle(start, downSpan); 884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *done = false; 9007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 9254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(downSpan->done()); 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9596fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 9854359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr, 99bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase** endPtr, bool* done) { 10054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* oPtT = start->ptT()->next(); 10154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = oPtT->segment(); 10254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oSpan = oPtT->span(); 103bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark return other->activeAngleInner(oSpan, startPtr, endPtr, done); 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 10507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 10654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, 10754359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOp op) { 10854359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = this->updateWinding(end, start); 10954359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding = this->updateOppWinding(end, start); 11065f553182ab7069378ef863d30094d0327f178d0caryclark#if DEBUG_LIMIT_WIND_SUM 11165f553182ab7069378ef863d30094d0327f178d0caryclark SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM); 11265f553182ab7069378ef863d30094d0327f178d0caryclark SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM); 11365f553182ab7069378ef863d30094d0327f178d0caryclark#endif 11454359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand()) { 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap<int>(sumMiWinding, sumSuWinding); 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11754359294a7c9dc54802d512a5d891a35c1663392caryclark return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding); 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 12054359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, 12154359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOp op, int* sumMiWinding, int* sumSuWinding) { 1224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 12354359294a7c9dc54802d512a5d891a35c1663392caryclark this->setUpWindings(start, end, sumMiWinding, sumSuWinding, 1244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool miFrom; 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool miTo; 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool suFrom; 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool suTo; 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 1304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org miFrom = (oppMaxWinding & xorMiMask) != 0; 1314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org miTo = (oppSumWinding & xorMiMask) != 0; 1324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org suFrom = (maxWinding & xorSuMask) != 0; 1334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org suTo = (sumWinding & xorSuMask) != 0; 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 1354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org miFrom = (maxWinding & xorMiMask) != 0; 1364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org miTo = (sumWinding & xorMiMask) != 0; 1374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org suFrom = (oppMaxWinding & xorSuMask) != 0; 1384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org suTo = (oppSumWinding & xorSuMask) != 0; 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_ACTIVE_OP 142dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", 14354359294a7c9dc54802d512a5d891a35c1663392caryclark __FUNCTION__, debugID(), start->t(), end->t(), 144570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 14954359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 15054359294a7c9dc54802d512a5d891a35c1663392caryclark int sumWinding = updateWinding(end, start); 15154359294a7c9dc54802d512a5d891a35c1663392caryclark return activeWinding(start, end, &sumWinding); 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 15454359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) { 1554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int maxWinding; 15654359294a7c9dc54802d512a5d891a35c1663392caryclark setUpWinding(start, end, &maxWinding, sumWinding); 1574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool from = maxWinding != 0; 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool to = *sumWinding != 0; 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool result = gUnaryActiveEdge[from][to]; 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 163ef784fb7f58c9c021172045a8e0b396c81fdc425caryclarkbool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, 164ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark SkPathWriter* path) const { 165025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(start->starter(end)->alreadyAdded()); 166eed356d281adbf93ecbd89cb23913a7861cd8578caryclark SkDCurveSweep curvePart; 167eed356d281adbf93ecbd89cb23913a7861cd8578caryclark start->segment()->subDivide(start, end, &curvePart.fCurve); 168eed356d281adbf93ecbd89cb23913a7861cd8578caryclark curvePart.setCurveHullSweep(fVerb); 169eed356d281adbf93ecbd89cb23913a7861cd8578caryclark SkPath::Verb verb = curvePart.isCurve() ? fVerb : SkPath::kLine_Verb; 170eed356d281adbf93ecbd89cb23913a7861cd8578caryclark path->deferredMove(start->ptT()); 171eed356d281adbf93ecbd89cb23913a7861cd8578caryclark switch (verb) { 172eed356d281adbf93ecbd89cb23913a7861cd8578caryclark case SkPath::kLine_Verb: 173a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!path->deferredLine(end->ptT())); 174eed356d281adbf93ecbd89cb23913a7861cd8578caryclark break; 175eed356d281adbf93ecbd89cb23913a7861cd8578caryclark case SkPath::kQuad_Verb: 176a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark path->quadTo(curvePart.fCurve.fQuad[1].asSkPoint(), end->ptT()); 177eed356d281adbf93ecbd89cb23913a7861cd8578caryclark break; 178eed356d281adbf93ecbd89cb23913a7861cd8578caryclark case SkPath::kConic_Verb: 179a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark path->conicTo(curvePart.fCurve.fConic[1].asSkPoint(), end->ptT(), 180eed356d281adbf93ecbd89cb23913a7861cd8578caryclark curvePart.fCurve.fConic.fWeight); 181eed356d281adbf93ecbd89cb23913a7861cd8578caryclark break; 182eed356d281adbf93ecbd89cb23913a7861cd8578caryclark case SkPath::kCubic_Verb: 183a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark path->cubicTo(curvePart.fCurve.fCubic[1].asSkPoint(), 184a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark curvePart.fCurve.fCubic[2].asSkPoint(), end->ptT()); 185eed356d281adbf93ecbd89cb23913a7861cd8578caryclark break; 186eed356d281adbf93ecbd89cb23913a7861cd8578caryclark default: 187eed356d281adbf93ecbd89cb23913a7861cd8578caryclark SkASSERT(0); 18807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 189ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark return true; 19007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 19107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 19255888e44171ffd48b591d19256884a969fe4da17caryclarkconst SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const { 19355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* test = &fHead; 19455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* testPtT; 19555888e44171ffd48b591d19256884a969fe4da17caryclark SkPoint pt = this->ptAtT(t); 1964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 19755888e44171ffd48b591d19256884a969fe4da17caryclark testPtT = test->ptT(); 19855888e44171ffd48b591d19256884a969fe4da17caryclark if (testPtT->fT == t) { 19954359294a7c9dc54802d512a5d891a35c1663392caryclark break; 20054359294a7c9dc54802d512a5d891a35c1663392caryclark } 201ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark if (!this->match(testPtT, this, t, pt)) { 20255888e44171ffd48b591d19256884a969fe4da17caryclark if (t < testPtT->fT) { 20355888e44171ffd48b591d19256884a969fe4da17caryclark return nullptr; 20455888e44171ffd48b591d19256884a969fe4da17caryclark } 20555888e44171ffd48b591d19256884a969fe4da17caryclark continue; 20655888e44171ffd48b591d19256884a969fe4da17caryclark } 20755888e44171ffd48b591d19256884a969fe4da17caryclark if (!opp) { 20855888e44171ffd48b591d19256884a969fe4da17caryclark return testPtT; 20955888e44171ffd48b591d19256884a969fe4da17caryclark } 21055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* loop = testPtT->next(); 21155888e44171ffd48b591d19256884a969fe4da17caryclark while (loop != testPtT) { 21255888e44171ffd48b591d19256884a969fe4da17caryclark if (loop->segment() == this && loop->fT == t && loop->fPt == pt) { 21355888e44171ffd48b591d19256884a969fe4da17caryclark goto foundMatch; 21455888e44171ffd48b591d19256884a969fe4da17caryclark } 21555888e44171ffd48b591d19256884a969fe4da17caryclark loop = loop->next(); 21655888e44171ffd48b591d19256884a969fe4da17caryclark } 21755888e44171ffd48b591d19256884a969fe4da17caryclark return nullptr; 21854359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = test->upCast()->next())); 21955888e44171ffd48b591d19256884a969fe4da17caryclarkfoundMatch: 22055888e44171ffd48b591d19256884a969fe4da17caryclark return opp && !test->contains(opp) ? nullptr : testPtT; 22155888e44171ffd48b591d19256884a969fe4da17caryclark} 22255888e44171ffd48b591d19256884a969fe4da17caryclark 22355888e44171ffd48b591d19256884a969fe4da17caryclark// break the span so that the coincident part does not change the angle of the remainder 22455888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) { 22555888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(newT)) { 22655888e44171ffd48b591d19256884a969fe4da17caryclark return true; 22707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 22829b2563afb1677515739f1d24fb27733626eca92caryclark this->globalState()->resetAllocatedOpSpan(); 229a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!between(0, newT, 1)); 23029b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* newPtT = this->addT(newT); 23129b2563afb1677515739f1d24fb27733626eca92caryclark *startOver |= this->globalState()->allocatedOpSpan(); 23255888e44171ffd48b591d19256884a969fe4da17caryclark if (!newPtT) { 23355888e44171ffd48b591d19256884a969fe4da17caryclark return false; 23455888e44171ffd48b591d19256884a969fe4da17caryclark } 23555888e44171ffd48b591d19256884a969fe4da17caryclark newPtT->fPt = this->ptAtT(newT); 23629b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT); 23729b2563afb1677515739f1d24fb27733626eca92caryclark if (oppPrev) { 2388016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // const cast away to change linked list; pt/t values stays unchanged 23929b2563afb1677515739f1d24fb27733626eca92caryclark SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test); 24030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark writableTest->mergeMatches(newPtT->span()); 24129b2563afb1677515739f1d24fb27733626eca92caryclark writableTest->ptT()->addOpp(newPtT, oppPrev); 24255888e44171ffd48b591d19256884a969fe4da17caryclark writableTest->checkForCollapsedCoincidence(); 24355888e44171ffd48b591d19256884a969fe4da17caryclark } 24455888e44171ffd48b591d19256884a969fe4da17caryclark return true; 24507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 24607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 24755888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugAddT() 24873e597d0eddeaaa466101d5bb7da537c0066166aCary ClarkSkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) { 24954359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 25029b2563afb1677515739f1d24fb27733626eca92caryclark SkOpSpanBase* spanBase = &fHead; 2514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 25229b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* result = spanBase->ptT(); 25327c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) { 25429b2563afb1677515739f1d24fb27733626eca92caryclark spanBase->bumpSpanAdds(); 255ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark return result; 25654359294a7c9dc54802d512a5d891a35c1663392caryclark } 25754359294a7c9dc54802d512a5d891a35c1663392caryclark if (t < result->fT) { 25854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prev = result->span()->prev(); 25929b2563afb1677515739f1d24fb27733626eca92caryclark FAIL_WITH_NULL_IF(!prev); 26029b2563afb1677515739f1d24fb27733626eca92caryclark // marks in global state that new op span has been allocated 26129b2563afb1677515739f1d24fb27733626eca92caryclark SkOpSpan* span = this->insert(prev); 26254359294a7c9dc54802d512a5d891a35c1663392caryclark span->init(this, prev, t, pt); 26354359294a7c9dc54802d512a5d891a35c1663392caryclark this->debugValidate(); 26454359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_ADD_T 26554359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, 26654359294a7c9dc54802d512a5d891a35c1663392caryclark span->segment()->debugID(), span->debugID()); 26754359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 26808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark span->bumpSpanAdds(); 26954359294a7c9dc54802d512a5d891a35c1663392caryclark return span->ptT(); 27054359294a7c9dc54802d512a5d891a35c1663392caryclark } 27129b2563afb1677515739f1d24fb27733626eca92caryclark FAIL_WITH_NULL_IF(spanBase == &fTail); 27229b2563afb1677515739f1d24fb27733626eca92caryclark } while ((spanBase = spanBase->upCast()->next())); 27354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0); 27429b2563afb1677515739f1d24fb27733626eca92caryclark return nullptr; // we never get here, but need this to satisfy compiler 2754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 27773e597d0eddeaaa466101d5bb7da537c0066166aCary ClarkSkOpPtT* SkOpSegment::addT(double t) { 27873e597d0eddeaaa466101d5bb7da537c0066166aCary Clark return addT(t, this->ptAtT(t)); 27973e597d0eddeaaa466101d5bb7da537c0066166aCary Clark} 28073e597d0eddeaaa466101d5bb7da537c0066166aCary Clark 28155888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::calcAngles() { 28254359294a7c9dc54802d512a5d891a35c1663392caryclark bool activePrior = !fHead.isCanceled(); 28354359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior && !fHead.simple()) { 28455888e44171ffd48b591d19256884a969fe4da17caryclark addStartSpan(); 2850dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 28654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prior = &fHead; 28754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* spanBase = fHead.next(); 28854359294a7c9dc54802d512a5d891a35c1663392caryclark while (spanBase != &fTail) { 28954359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior) { 290ecc364c42691f24b41a672de1636b3a5f181160aHerb Derby SkOpAngle* priorAngle = this->globalState()->allocator()->make<SkOpAngle>(); 29154359294a7c9dc54802d512a5d891a35c1663392caryclark priorAngle->set(spanBase, prior); 29254359294a7c9dc54802d512a5d891a35c1663392caryclark spanBase->setFromAngle(priorAngle); 293ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 29454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* span = spanBase->upCast(); 29554359294a7c9dc54802d512a5d891a35c1663392caryclark bool active = !span->isCanceled(); 29654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = span->next(); 29754359294a7c9dc54802d512a5d891a35c1663392caryclark if (active) { 298ecc364c42691f24b41a672de1636b3a5f181160aHerb Derby SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>(); 29954359294a7c9dc54802d512a5d891a35c1663392caryclark angle->set(span, next); 30054359294a7c9dc54802d512a5d891a35c1663392caryclark span->setToAngle(angle); 30154359294a7c9dc54802d512a5d891a35c1663392caryclark } 30254359294a7c9dc54802d512a5d891a35c1663392caryclark activePrior = active; 30354359294a7c9dc54802d512a5d891a35c1663392caryclark prior = span; 30454359294a7c9dc54802d512a5d891a35c1663392caryclark spanBase = next; 3054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 30654359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior && !fTail.simple()) { 30755888e44171ffd48b591d19256884a969fe4da17caryclark addEndSpan(); 3084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 30965f553182ab7069378ef863d30094d0327f178d0caryclark} 31065f553182ab7069378ef863d30094d0327f178d0caryclark 31155888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugClearAll() 31255888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::clearAll() { 31355888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpan* span = &fHead; 31455888e44171ffd48b591d19256884a969fe4da17caryclark do { 31555888e44171ffd48b591d19256884a969fe4da17caryclark this->clearOne(span); 31655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((span = span->next()->upCastable())); 31755888e44171ffd48b591d19256884a969fe4da17caryclark this->globalState()->coincidence()->release(this); 31855888e44171ffd48b591d19256884a969fe4da17caryclark} 31955888e44171ffd48b591d19256884a969fe4da17caryclark 32055888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugClearOne() 32155888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::clearOne(SkOpSpan* span) { 32255888e44171ffd48b591d19256884a969fe4da17caryclark span->setWindValue(0); 32355888e44171ffd48b591d19256884a969fe4da17caryclark span->setOppValue(0); 32455888e44171ffd48b591d19256884a969fe4da17caryclark this->markDone(span); 32555888e44171ffd48b591d19256884a969fe4da17caryclark} 32655888e44171ffd48b591d19256884a969fe4da17caryclark 32730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkbool SkOpSegment::collapsed(double s, double e) const { 32830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpSpanBase* span = &fHead; 32930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark do { 33030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (span->collapsed(s, e)) { 33130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return true; 33230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 33330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } while (span->upCastable() && (span = span->upCast()->next())); 33430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return false; 33530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 33630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 33754359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 33854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 339624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* baseSegment = baseAngle->segment(); 34054359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); 34154359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding; 34254359294a7c9dc54802d512a5d891a35c1663392caryclark bool binary = includeType >= SkOpAngle::kBinarySingle; 34354359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 34454359294a7c9dc54802d512a5d891a35c1663392caryclark sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); 34554359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseSegment->operand()) { 34654359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap<int>(sumMiWinding, sumSuWinding); 3470dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 34854359294a7c9dc54802d512a5d891a35c1663392caryclark } 34954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* nextSegment = nextAngle->segment(); 35054359294a7c9dc54802d512a5d891a35c1663392caryclark int maxWinding, sumWinding; 35154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 35254359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 35354359294a7c9dc54802d512a5d891a35c1663392caryclark int oppMaxWinding, oppSumWinding; 35454359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 35554359294a7c9dc54802d512a5d891a35c1663392caryclark &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 35654359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 35754359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle); 3584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 35954359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 36054359294a7c9dc54802d512a5d891a35c1663392caryclark &maxWinding, &sumWinding); 36154359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 3624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 36354359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle->setLastMarked(last); 3644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 366624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkvoid SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, 36754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 368624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* baseSegment = baseAngle->segment(); 36954359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = baseSegment->updateWinding(baseAngle); 37054359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding; 37154359294a7c9dc54802d512a5d891a35c1663392caryclark bool binary = includeType >= SkOpAngle::kBinarySingle; 3720dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed if (binary) { 37354359294a7c9dc54802d512a5d891a35c1663392caryclark sumSuWinding = baseSegment->updateOppWinding(baseAngle); 37454359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseSegment->operand()) { 37554359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap<int>(sumMiWinding, sumSuWinding); 3760dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 3770dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 37854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* nextSegment = nextAngle->segment(); 37954359294a7c9dc54802d512a5d891a35c1663392caryclark int maxWinding, sumWinding; 38054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 38154359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 38254359294a7c9dc54802d512a5d891a35c1663392caryclark int oppMaxWinding, oppSumWinding; 38354359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 38454359294a7c9dc54802d512a5d891a35c1663392caryclark &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 38554359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 38654359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle); 3874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 38854359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 38954359294a7c9dc54802d512a5d891a35c1663392caryclark &maxWinding, &sumWinding); 39054359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 3910dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 39254359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle->setLastMarked(last); 3934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 395dac1d17027dcaa5596885a9f333979418b35001ccaryclark// at this point, the span is already ordered, or unorderable 39654359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, 39754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 3984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(includeType != SkOpAngle::kUnaryXor); 39954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* firstAngle = this->spanToAngle(end, start); 40096fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == firstAngle || nullptr == firstAngle->next()) { 4014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return SK_NaN32; 402570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 403570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // if all angles have a computed winding, 404570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // or if no adjacent angles are orderable, 405570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // or if adjacent orderable angles have no computed winding, 406570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // there's nothing to do 407dac1d17027dcaa5596885a9f333979418b35001ccaryclark // if two orderable angles are adjacent, and both are next to orderable angles, 408dac1d17027dcaa5596885a9f333979418b35001ccaryclark // and one has winding computed, transfer to the other 40996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpAngle* baseAngle = nullptr; 410570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool tryReverse = false; 411570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // look for counterclockwise transfers 412dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* angle = firstAngle->previous(); 413dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* next = angle->next(); 414dac1d17027dcaa5596885a9f333979418b35001ccaryclark firstAngle = next; 41507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 416dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* prior = angle; 417dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle = next; 418dac1d17027dcaa5596885a9f333979418b35001ccaryclark next = angle->next(); 419dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(prior->next() == angle); 420dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(angle->next() == next); 421dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 42296fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 4234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 42554359294a7c9dc54802d512a5d891a35c1663392caryclark int testWinding = angle->starter()->windSum(); 426dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (SK_MinS32 != testWinding) { 427dac1d17027dcaa5596885a9f333979418b35001ccaryclark baseAngle = angle; 4284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tryReverse = true; 4294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (baseAngle) { 4324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ComputeOneSum(baseAngle, angle, includeType); 43396fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 4344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 435dac1d17027dcaa5596885a9f333979418b35001ccaryclark } while (next != firstAngle); 43654359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) { 4374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org firstAngle = baseAngle; 4384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tryReverse = true; 4394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tryReverse) { 44196fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 442dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* prior = firstAngle; 443570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com do { 444dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle = prior; 445dac1d17027dcaa5596885a9f333979418b35001ccaryclark prior = angle->previous(); 446dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(prior->next() == angle); 447dac1d17027dcaa5596885a9f333979418b35001ccaryclark next = angle->next(); 448dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 44996fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 450dac1d17027dcaa5596885a9f333979418b35001ccaryclark continue; 451dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 45254359294a7c9dc54802d512a5d891a35c1663392caryclark int testWinding = angle->starter()->windSum(); 4534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SK_MinS32 != testWinding) { 4544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org baseAngle = angle; 455570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com continue; 45607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 457570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (baseAngle) { 4584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ComputeOneSumReverse(baseAngle, angle, includeType); 45996fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 460570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 461dac1d17027dcaa5596885a9f333979418b35001ccaryclark } while (prior != firstAngle); 462570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 46354359294a7c9dc54802d512a5d891a35c1663392caryclark return start->starter(end)->windSum(); 46407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 46507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 46655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpSegment::contains(double newT) const { 46755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* spanBase = &fHead; 46855888e44171ffd48b591d19256884a969fe4da17caryclark do { 46955888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase->ptT()->contains(this, newT)) { 47055888e44171ffd48b591d19256884a969fe4da17caryclark return true; 47155888e44171ffd48b591d19256884a969fe4da17caryclark } 47255888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase == &fTail) { 47355888e44171ffd48b591d19256884a969fe4da17caryclark break; 47455888e44171ffd48b591d19256884a969fe4da17caryclark } 47555888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = spanBase->upCast()->next(); 47655888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 47755888e44171ffd48b591d19256884a969fe4da17caryclark return false; 47855888e44171ffd48b591d19256884a969fe4da17caryclark} 47955888e44171ffd48b591d19256884a969fe4da17caryclark 48018300a3aa7cb6eb55d21bb0450dffa58b6fc062cmtkleinvoid SkOpSegment::release(const SkOpSpan* span) { 48154359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 48208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark --fDoneCount; 483ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 48408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark --fCount; 4851597628fa38d24f23ad505bfb40e70e7c8617457caryclark SkOPASSERT(fCount >= fDoneCount); 4860dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed} 4870dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed 488e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark#if DEBUG_ANGLE 489e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark// called only by debugCheckNearCoincidence 49026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclarkdouble SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const { 49154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint testPt = this->dPtAtT(t); 49254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine testPerp = {{ testPt, testPt }}; 49354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector slope = this->dSlopeAtT(t); 49454359294a7c9dc54802d512a5d891a35c1663392caryclark testPerp[1].fX += slope.fY; 49554359294a7c9dc54802d512a5d891a35c1663392caryclark testPerp[1].fY -= slope.fX; 49654359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 49726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark const SkOpSegment* oppSegment = oppAngle->segment(); 4981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); 49954359294a7c9dc54802d512a5d891a35c1663392caryclark double closestDistSq = SK_ScalarInfinity; 50054359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < i.used(); ++index) { 50154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { 50254359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 5030dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 50454359294a7c9dc54802d512a5d891a35c1663392caryclark double testDistSq = testPt.distanceSquared(i.pt(index)); 50554359294a7c9dc54802d512a5d891a35c1663392caryclark if (closestDistSq > testDistSq) { 50654359294a7c9dc54802d512a5d891a35c1663392caryclark closestDistSq = testDistSq; 5070dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 50854359294a7c9dc54802d512a5d891a35c1663392caryclark } 50954359294a7c9dc54802d512a5d891a35c1663392caryclark return closestDistSq; 5104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 511e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark#endif 5124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 51307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 51407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com The M and S variable name parts stand for the operators. 51507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Mi stands for Minuend (see wiki subtraction, analogous to difference) 51607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Su stands for Subtrahend 51707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com The Opp variable name part designates that the value is for the Opposite operator. 51807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Opposite values result from combining coincident spans. 51907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 52054359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 52154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) { 52254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 52354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 52454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 52554359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 52654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 52754359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 52807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // mark the smaller of startIndex, endIndex done, and all adjacent 52907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // spans with the same T value (but not 'other' spans) 53007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 53107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 53207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 53354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 53454359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 53596fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 536cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 53754359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 53854359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 53907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 54007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 54154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 54254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 54354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 54454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 54554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 5464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // more than one viable candidate -- measure angles to find best 54754359294a7c9dc54802d512a5d891a35c1663392caryclark int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp); 548570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool sortable = calcWinding != SK_NaN32; 5494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!sortable) { 5507eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com *unsortable = true; 55154359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 55296fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 5537eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 55454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 5554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle->unorderable()) { 55607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *unsortable = true; 55754359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 55896fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 55907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 5614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 5624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 56307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 56454359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = updateWinding(end, start); 5658cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (sumMiWinding == SK_MinS32) { 5668cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org *unsortable = true; 56754359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 56896fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 5698cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 57054359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding = updateOppWinding(end, start); 57107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 57207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap<int>(sumMiWinding, sumSuWinding); 57307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 57596fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 57607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 57707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // iterate through the angle, and compute everyone's winding 57807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 57907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 58007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 58107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 58207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), 5834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nextAngle->end(), op, &sumMiWinding, &sumSuWinding); 58407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (activeAngle) { 58507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 58607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 58707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 588570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com foundDone = nextSegment->done(nextAngle); 58907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 59007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 59107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (nextSegment->done()) { 59207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 59307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 594570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!activeAngle) { 59554359294a7c9dc54802d512a5d891a35c1663392caryclark (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 596570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 59754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = nextAngle->lastMarked(); 59807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (last) { 5994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 60007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *chase->append() = last; 60107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 60254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 60354359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 60454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 60554359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum=%d", last->upCast()->windSum()); 60654359294a7c9dc54802d512a5d891a35c1663392caryclark } 60754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 60807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 60907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while ((nextAngle = nextAngle->next()) != angle); 61154359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 61207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 61396fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 61407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 61507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 61607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 61707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 61807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 61907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 62007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 62107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 62207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 62307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 62407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 62554359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase, 62654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { 62754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 62854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 62954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 63054359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 63154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 63254359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 63307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // mark the smaller of startIndex, endIndex done, and all adjacent 63407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // spans with the same T value (but not 'other' spans) 63507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 63607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 63707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 63854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 63954359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 64096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 641570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 64254359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 64354359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 64407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 64507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 64654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 64754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 64854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 64954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 65054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 6514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // more than one viable candidate -- measure angles to find best 65254359294a7c9dc54802d512a5d891a35c1663392caryclark int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding); 653570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool sortable = calcWinding != SK_NaN32; 65407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!sortable) { 65507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *unsortable = true; 65654359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 65796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 65854359294a7c9dc54802d512a5d891a35c1663392caryclark } 65954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 66054359294a7c9dc54802d512a5d891a35c1663392caryclark if (angle->unorderable()) { 66154359294a7c9dc54802d512a5d891a35c1663392caryclark *unsortable = true; 66254359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 66396fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 66407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 6664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 6674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 66807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 66954359294a7c9dc54802d512a5d891a35c1663392caryclark int sumWinding = updateWinding(end, start); 6704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 67196fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 67207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 67354359294a7c9dc54802d512a5d891a35c1663392caryclark // iterate through the angle, and compute everyone's winding 67407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 67507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 67607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 67707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 67807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), 6794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org &sumWinding); 68007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (activeAngle) { 68107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 68207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 68307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 68407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundDone = nextSegment->done(nextAngle); 68507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 68607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 68707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (nextSegment->done()) { 68807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 68907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 690570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!activeAngle) { 69154359294a7c9dc54802d512a5d891a35c1663392caryclark (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 692570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 69354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = nextAngle->lastMarked(); 69407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (last) { 6954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 69607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *chase->append() = last; 69707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 69854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 69954359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 70054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 70154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum=%d", last->upCast()->windSum()); 70254359294a7c9dc54802d512a5d891a35c1663392caryclark } 70354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 70407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 70507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while ((nextAngle = nextAngle->next()) != angle); 70754359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 70807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 70996fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 71007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 71107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 71207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 71307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 71407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 71507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 71607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 71707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 71807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 71907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 72007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 72154359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, 72254359294a7c9dc54802d512a5d891a35c1663392caryclark bool* unsortable) { 72354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 72454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 72554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 72654359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 72754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 72854359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 72954359294a7c9dc54802d512a5d891a35c1663392caryclark // mark the smaller of startIndex, endIndex done, and all adjacent 73054359294a7c9dc54802d512a5d891a35c1663392caryclark // spans with the same T value (but not 'other' spans) 73107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 73207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 73307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 73454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 73554359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 73696fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 73707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 73854359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 73954359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 74007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 74107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 74254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \ 74354359294a7c9dc54802d512a5d891a35c1663392caryclark : (*nextStart)->prev()); 74454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 74554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 74654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 74754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 74854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 74927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!angle || angle->unorderable()) { 75054359294a7c9dc54802d512a5d891a35c1663392caryclark *unsortable = true; 75154359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 75296fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 75354359294a7c9dc54802d512a5d891a35c1663392caryclark } 7544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 7554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 7564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 757570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 7584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 75996fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 76007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 76154359294a7c9dc54802d512a5d891a35c1663392caryclark // iterate through the angle, and compute everyone's winding 76207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 76307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 76407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 76507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 76607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 76707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 76807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 7694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!(foundDone = nextSegment->done(nextAngle))) { 7704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 7714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 77207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nextAngle = nextAngle->next(); 7744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (nextAngle != angle); 77554359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 77607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 77796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 77807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 77907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 78007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 78107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 78207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 78307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 78407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 78507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 78607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 78707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 78807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 78954359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpGlobalState* SkOpSegment::globalState() const { 79055888e44171ffd48b591d19256884a969fe4da17caryclark return contour()->globalState(); 79165f553182ab7069378ef863d30094d0327f178d0caryclark} 79265f553182ab7069378ef863d30094d0327f178d0caryclark 7931049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { 79454359294a7c9dc54802d512a5d891a35c1663392caryclark fContour = contour; 79596fcdcc219d2a0d3579719b84b28bede76efba64halcanary fNext = nullptr; 79607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fPts = pts; 7971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fWeight = weight; 79807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fVerb = verb; 79954359294a7c9dc54802d512a5d891a35c1663392caryclark fCount = 0; 80054359294a7c9dc54802d512a5d891a35c1663392caryclark fDoneCount = 0; 80154359294a7c9dc54802d512a5d891a35c1663392caryclark fVisited = false; 80254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* zeroSpan = &fHead; 80396fcdcc219d2a0d3579719b84b28bede76efba64halcanary zeroSpan->init(this, nullptr, 0, fPts[0]); 80454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oneSpan = &fTail; 80554359294a7c9dc54802d512a5d891a35c1663392caryclark zeroSpan->setNext(oneSpan); 80654359294a7c9dc54802d512a5d891a35c1663392caryclark oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); 8071049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fID = globalState()->nextSegmentID()); 80854359294a7c9dc54802d512a5d891a35c1663392caryclark} 80954359294a7c9dc54802d512a5d891a35c1663392caryclark 81054359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { 81154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint cPt = this->dPtAtT(t); 8121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); 81354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 81454359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 8151049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i); 81654359294a7c9dc54802d512a5d891a35c1663392caryclark int used = i.used(); 81754359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < used; ++index) { 81854359294a7c9dc54802d512a5d891a35c1663392caryclark if (cPt.roughlyEqual(i.pt(index))) { 8190dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed return true; 8200dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 82154359294a7c9dc54802d512a5d891a35c1663392caryclark } 822a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return false; 823a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com} 824a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 82554359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::isXor() const { 82654359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->isXor(); 82707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 82807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 8295b5ddd73b4baf22752924bf20d097e96236c36f8caryclarkvoid SkOpSegment::markAllDone() { 8305b5ddd73b4baf22752924bf20d097e96236c36f8caryclark SkOpSpan* span = this->head(); 8315b5ddd73b4baf22752924bf20d097e96236c36f8caryclark do { 8325b5ddd73b4baf22752924bf20d097e96236c36f8caryclark this->markDone(span); 8335b5ddd73b4baf22752924bf20d097e96236c36f8caryclark } while ((span = span->next()->upCastable())); 8345b5ddd73b4baf22752924bf20d097e96236c36f8caryclark} 8355b5ddd73b4baf22752924bf20d097e96236c36f8caryclark 83654359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) { 83754359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 83854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* minSpan = start->starter(end); 83954359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(minSpan); 84096fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 84107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* other = this; 842918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark SkOpSpan* priorDone = nullptr; 843918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark SkOpSpan* lastDone = nullptr; 84454359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &minSpan, &last))) { 84507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (other->done()) { 846dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 847dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 84807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 849918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark if (lastDone == minSpan || priorDone == minSpan) { 850918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark return nullptr; 851918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark } 85254359294a7c9dc54802d512a5d891a35c1663392caryclark other->markDone(minSpan); 853918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark priorDone = lastDone; 854918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark lastDone = minSpan; 85507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 85607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 85707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 85807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 85954359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 86054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** lastPtr) { 86154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* spanStart = start->starter(end); 86254359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 86354359294a7c9dc54802d512a5d891a35c1663392caryclark bool success = markWinding(spanStart, winding); 86496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 8654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpSegment* other = this; 86654359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 86754359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart->windSum() != SK_MinS32) { 868b36a3cd137e2b6c328854015018594bb9967e493caryclark// SkASSERT(spanStart->windSum() == winding); // FIXME: is this assert too aggressive? 869dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 870dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 8714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 87254359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, winding); 8736f726addf3178b01949bb389ef83cf14a1d7b6b2caryclark } 87465f553182ab7069378ef863d30094d0327f178d0caryclark if (lastPtr) { 87565f553182ab7069378ef863d30094d0327f178d0caryclark *lastPtr = last; 87665f553182ab7069378ef863d30094d0327f178d0caryclark } 87765f553182ab7069378ef863d30094d0327f178d0caryclark return success; 8784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 8794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 88054359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, 88154359294a7c9dc54802d512a5d891a35c1663392caryclark int winding, int oppWinding, SkOpSpanBase** lastPtr) { 88254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* spanStart = start->starter(end); 88354359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 88454359294a7c9dc54802d512a5d891a35c1663392caryclark bool success = markWinding(spanStart, winding, oppWinding); 88596fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 88607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* other = this; 88754359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 88854359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart->windSum() != SK_MinS32) { 88954359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand() == other->operand()) { 890624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { 89154359294a7c9dc54802d512a5d891a35c1663392caryclark this->globalState()->setWindingFailed(); 89254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 893dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 89454359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 89554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->windSum() == oppWinding); 89654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->oppSum() == winding); 897dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 898dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 899dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 900dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 90154359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand() == other->operand()) { 90254359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, winding, oppWinding); 903dac1d17027dcaa5596885a9f333979418b35001ccaryclark } else { 90454359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, oppWinding, winding); 90507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 90607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 90765f553182ab7069378ef863d30094d0327f178d0caryclark if (lastPtr) { 90865f553182ab7069378ef863d30094d0327f178d0caryclark *lastPtr = last; 90965f553182ab7069378ef863d30094d0327f178d0caryclark } 91065f553182ab7069378ef863d30094d0327f178d0caryclark return success; 91107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 91207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 91354359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) { 91407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(angle->segment() == this); 91507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (UseInnerWinding(maxWinding, sumWinding)) { 91607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com maxWinding = sumWinding; 91707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 91854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 91954359294a7c9dc54802d512a5d891a35c1663392caryclark (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last); 920570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_WINDING 921570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (last) { 92254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s last seg=%d span=%d", __FUNCTION__, 92354359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 92454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 92554359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum="); 92654359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 92754359294a7c9dc54802d512a5d891a35c1663392caryclark } 92854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 929570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 930570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 93107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 93207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 93307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 93454359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, 93554359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSumWinding, const SkOpAngle* angle) { 93607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(angle->segment() == this); 93707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (UseInnerWinding(maxWinding, sumWinding)) { 93807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com maxWinding = sumWinding; 93907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 94007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { 94107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com oppMaxWinding = oppSumWinding; 94207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 94396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 94465f553182ab7069378ef863d30094d0327f178d0caryclark // caller doesn't require that this marks anything 94554359294a7c9dc54802d512a5d891a35c1663392caryclark (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last); 946570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_WINDING 947570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (last) { 94854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s last segment=%d span=%d", __FUNCTION__, 94954359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 95054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 95154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum="); 95254359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 95354359294a7c9dc54802d512a5d891a35c1663392caryclark } 95454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" \n"); 955570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 956570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 95707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 95807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 95907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 96054359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::markDone(SkOpSpan* span) { 96154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 96254359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 9630dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed return; 9640dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 96554359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_MARK_DONE 96654359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum()); 96754359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 96854359294a7c9dc54802d512a5d891a35c1663392caryclark span->setDone(true); 96954359294a7c9dc54802d512a5d891a35c1663392caryclark ++fDoneCount; 97054359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 9710dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed} 9720dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed 97354359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markWinding(SkOpSpan* span, int winding) { 97454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 97554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(winding); 97654359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 97765f553182ab7069378ef863d30094d0327f178d0caryclark return false; 97807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 97907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_MARK_DONE 98054359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, winding); 9810dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed#endif 98254359294a7c9dc54802d512a5d891a35c1663392caryclark span->setWindSum(winding); 98354359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 98465f553182ab7069378ef863d30094d0327f178d0caryclark return true; 98507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 98607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 98754359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { 98854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 98954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(winding || oppWinding); 99054359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 99165f553182ab7069378ef863d30094d0327f178d0caryclark return false; 99207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 99307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_MARK_DONE 99454359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, winding, oppWinding); 9958cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org#endif 99654359294a7c9dc54802d512a5d891a35c1663392caryclark span->setWindSum(winding); 99754359294a7c9dc54802d512a5d891a35c1663392caryclark span->setOppSum(oppWinding); 9984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org debugValidate(); 99965f553182ab7069378ef863d30094d0327f178d0caryclark return true; 100007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 100107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 100254359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, 1003ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark const SkPoint& testPt) const { 100455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(this == base->segment()); 100555888e44171ffd48b591d19256884a969fe4da17caryclark if (this == testParent) { 100655888e44171ffd48b591d19256884a969fe4da17caryclark if (precisely_equal(base->fT, testT)) { 100755888e44171ffd48b591d19256884a969fe4da17caryclark return true; 100855888e44171ffd48b591d19256884a969fe4da17caryclark } 100907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 101054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { 101154359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 1012e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 101355888e44171ffd48b591d19256884a969fe4da17caryclark return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); 101454359294a7c9dc54802d512a5d891a35c1663392caryclark} 101554359294a7c9dc54802d512a5d891a35c1663392caryclark 101654359294a7c9dc54802d512a5d891a35c1663392caryclarkstatic SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { 101754359294a7c9dc54802d512a5d891a35c1663392caryclark if (last) { 101854359294a7c9dc54802d512a5d891a35c1663392caryclark *last = endSpan; 101907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 102096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 102107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 102207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 102354359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, 102454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** last) const { 102554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* origStart = *startPtr; 1026dac1d17027dcaa5596885a9f333979418b35001ccaryclark int step = *stepPtr; 102754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev(); 102854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endSpan); 102954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle(); 103054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* foundSpan; 103154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* otherEnd; 1032dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpSegment* other; 103396fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (angle == nullptr) { 103454359294a7c9dc54802d512a5d891a35c1663392caryclark if (endSpan->t() != 0 && endSpan->t() != 1) { 103596fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 1036dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 103754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* otherPtT = endSpan->ptT()->next(); 103854359294a7c9dc54802d512a5d891a35c1663392caryclark other = otherPtT->segment(); 103954359294a7c9dc54802d512a5d891a35c1663392caryclark foundSpan = otherPtT->span(); 1040343382e3acc8369f7bd4328e7c807255b5776fe5caryclark otherEnd = step > 0 1041343382e3acc8369f7bd4328e7c807255b5776fe5caryclark ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr 1042343382e3acc8369f7bd4328e7c807255b5776fe5caryclark : foundSpan->prev(); 1043dac1d17027dcaa5596885a9f333979418b35001ccaryclark } else { 1044dac1d17027dcaa5596885a9f333979418b35001ccaryclark int loopCount = angle->loopCount(); 1045dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (loopCount > 2) { 104654359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 1047dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 1048dac1d17027dcaa5596885a9f333979418b35001ccaryclark const SkOpAngle* next = angle->next(); 104996fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == next) { 105096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 105165b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark } 1052dac1d17027dcaa5596885a9f333979418b35001ccaryclark#if DEBUG_WINDING 1053624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() 105454359294a7c9dc54802d512a5d891a35c1663392caryclark && !next->segment()->contour()->isXor()) { 1055dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDebugf("%s mismatched signs\n", __FUNCTION__); 10560dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 105754359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 1058dac1d17027dcaa5596885a9f333979418b35001ccaryclark other = next->segment(); 105954359294a7c9dc54802d512a5d891a35c1663392caryclark foundSpan = endSpan = next->start(); 1060dac1d17027dcaa5596885a9f333979418b35001ccaryclark otherEnd = next->end(); 1061570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 1062343382e3acc8369f7bd4328e7c807255b5776fe5caryclark if (!otherEnd) { 1063343382e3acc8369f7bd4328e7c807255b5776fe5caryclark return nullptr; 1064343382e3acc8369f7bd4328e7c807255b5776fe5caryclark } 106554359294a7c9dc54802d512a5d891a35c1663392caryclark int foundStep = foundSpan->step(otherEnd); 1066dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (*stepPtr != foundStep) { 106754359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 106807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 106954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(*startPtr); 107065b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark// SkASSERT(otherEnd >= 0); 107154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast(); 107254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* foundMin = foundSpan->starter(otherEnd); 107354359294a7c9dc54802d512a5d891a35c1663392caryclark if (foundMin->windValue() != origMin->windValue() 107454359294a7c9dc54802d512a5d891a35c1663392caryclark || foundMin->oppValue() != origMin->oppValue()) { 107554359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 1076dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 107754359294a7c9dc54802d512a5d891a35c1663392caryclark *startPtr = foundSpan; 1078dac1d17027dcaa5596885a9f333979418b35001ccaryclark *stepPtr = foundStep; 1079dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (minPtr) { 1080dac1d17027dcaa5596885a9f333979418b35001ccaryclark *minPtr = foundMin; 1081a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 108207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 108307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 108407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 108555888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with DebugClearVisited() 108655888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::ClearVisited(SkOpSpanBase* span) { 108754359294a7c9dc54802d512a5d891a35c1663392caryclark // reset visited flag back to false 108854359294a7c9dc54802d512a5d891a35c1663392caryclark do { 108954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 109054359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != stopPtT) { 109154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* opp = ptT->segment(); 109254359294a7c9dc54802d512a5d891a35c1663392caryclark opp->resetVisited(); 109307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1094bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } while (!span->final() && (span = span->upCast()->next())); 109507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 109607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 109755888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugMissingCoincidence() 109854359294a7c9dc54802d512a5d891a35c1663392caryclark// look for pairs of undetected coincident curves 109954359294a7c9dc54802d512a5d891a35c1663392caryclark// assumes that segments going in have visited flag clear 110055888e44171ffd48b591d19256884a969fe4da17caryclark// Even though pairs of curves correct detect coincident runs, a run may be missed 110155888e44171ffd48b591d19256884a969fe4da17caryclark// if the coincidence is a product of multiple intersections. For instance, given 110255888e44171ffd48b591d19256884a969fe4da17caryclark// curves A, B, and C: 110355888e44171ffd48b591d19256884a969fe4da17caryclark// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near 110455888e44171ffd48b591d19256884a969fe4da17caryclark// the end of C that the intersection is replaced with the end of C. 110555888e44171ffd48b591d19256884a969fe4da17caryclark// Even though A-B correctly do not detect an intersection at point 2, 110655888e44171ffd48b591d19256884a969fe4da17caryclark// the resulting run from point 1 to point 2 is coincident on A and B. 110755888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpSegment::missingCoincidence() { 1108bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (this->done()) { 110927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return false; 1110bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 111196fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpan* prior = nullptr; 1112bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase* spanBase = &fHead; 111355888e44171ffd48b591d19256884a969fe4da17caryclark bool result = false; 111454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1115bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; 1116c6d855f7f3d548c52f450299dc6975820cda3387caryclark SkOPASSERT(ptT->span() == spanBase); 111754359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != spanStopPtT) { 1118182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (ptT->deleted()) { 1119182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1120182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 112154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* opp = ptT->span()->segment(); 1122bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (opp->done()) { 112354359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 112454359294a7c9dc54802d512a5d891a35c1663392caryclark } 1125bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence 1126bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (!opp->visited()) { 112754359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 112854359294a7c9dc54802d512a5d891a35c1663392caryclark } 1129bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (spanBase == &fHead) { 113054359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 1131bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 113255888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->segment() == this) { 113355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 113455888e44171ffd48b591d19256884a969fe4da17caryclark } 1135bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* span = spanBase->upCastable(); 1136bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // FIXME?: this assumes that if the opposite segment is coincident then no more 1137bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // coincidence needs to be detected. This may not be true. 113855888e44171ffd48b591d19256884a969fe4da17caryclark if (span && span->containsCoincidence(opp)) { 113926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark continue; 114026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 1141bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (spanBase->containsCoinEnd(opp)) { 1142bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 114355888e44171ffd48b591d19256884a969fe4da17caryclark } 114496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpPtT* priorPtT = nullptr, * priorStopPtT; 114554359294a7c9dc54802d512a5d891a35c1663392caryclark // find prior span containing opp segment 114696fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSegment* priorOpp = nullptr; 1147bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* priorTest = spanBase->prev(); 1148bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark while (!priorOpp && priorTest) { 1149bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark priorStopPtT = priorPtT = priorTest->ptT(); 115054359294a7c9dc54802d512a5d891a35c1663392caryclark while ((priorPtT = priorPtT->next()) != priorStopPtT) { 1151182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (priorPtT->deleted()) { 1152182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1153182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 115454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = priorPtT->span()->segment(); 115554359294a7c9dc54802d512a5d891a35c1663392caryclark if (segment == opp) { 1156bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark prior = priorTest; 115754359294a7c9dc54802d512a5d891a35c1663392caryclark priorOpp = opp; 115854359294a7c9dc54802d512a5d891a35c1663392caryclark break; 115954359294a7c9dc54802d512a5d891a35c1663392caryclark } 116054359294a7c9dc54802d512a5d891a35c1663392caryclark } 1161bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark priorTest = priorTest->prev(); 116254359294a7c9dc54802d512a5d891a35c1663392caryclark } 116354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!priorOpp) { 116454359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 116554359294a7c9dc54802d512a5d891a35c1663392caryclark } 116626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (priorPtT == ptT) { 116726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark continue; 116826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 116954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* oppStart = prior->ptT(); 1170bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpPtT* oppEnd = spanBase->ptT(); 117154359294a7c9dc54802d512a5d891a35c1663392caryclark bool swapped = priorPtT->fT > ptT->fT; 117254359294a7c9dc54802d512a5d891a35c1663392caryclark if (swapped) { 117354359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(priorPtT, ptT); 117454359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppStart, oppEnd); 117554359294a7c9dc54802d512a5d891a35c1663392caryclark } 117655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpCoincidence* coincidences = this->globalState()->coincidence(); 117755888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootPriorPtT = priorPtT->span()->ptT(); 117855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootPtT = ptT->span()->ptT(); 117955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootOppStart = oppStart->span()->ptT(); 118055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootOppEnd = oppEnd->span()->ptT(); 118155888e44171ffd48b591d19256884a969fe4da17caryclark if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 118254359294a7c9dc54802d512a5d891a35c1663392caryclark goto swapBack; 118354359294a7c9dc54802d512a5d891a35c1663392caryclark } 118455888e44171ffd48b591d19256884a969fe4da17caryclark if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) { 118554359294a7c9dc54802d512a5d891a35c1663392caryclark // mark coincidence 118655888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 118755888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__, 118855888e44171ffd48b591d19256884a969fe4da17caryclark rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(), 118955888e44171ffd48b591d19256884a969fe4da17caryclark rootOppEnd->debugID()); 119055888e44171ffd48b591d19256884a969fe4da17caryclark#endif 119155888e44171ffd48b591d19256884a969fe4da17caryclark if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 119255888e44171ffd48b591d19256884a969fe4da17caryclark coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd); 1193bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 119455888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 119555888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)); 119655888e44171ffd48b591d19256884a969fe4da17caryclark#endif 119755888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 119854359294a7c9dc54802d512a5d891a35c1663392caryclark } 119954359294a7c9dc54802d512a5d891a35c1663392caryclark swapBack: 120054359294a7c9dc54802d512a5d891a35c1663392caryclark if (swapped) { 120154359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(priorPtT, ptT); 120254359294a7c9dc54802d512a5d891a35c1663392caryclark } 12030dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 120496fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); 120555888e44171ffd48b591d19256884a969fe4da17caryclark ClearVisited(&fHead); 120655888e44171ffd48b591d19256884a969fe4da17caryclark return result; 120754359294a7c9dc54802d512a5d891a35c1663392caryclark} 120854359294a7c9dc54802d512a5d891a35c1663392caryclark 120955888e44171ffd48b591d19256884a969fe4da17caryclark// please keep this in sync with debugMoveMultiples() 121008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark// if a span has more than one intersection, merge the other segments' span as needed 1211d78c088b6136590371fddd4cab67bfb4bf692fd3caryclarkbool SkOpSegment::moveMultiples() { 121208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark debugValidate(); 121308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* test = &fHead; 121408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 121508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark int addCount = test->spanAddsCount(); 12167eb01e00b1a1f7c649e1e78eb3f4644033ce94eeCary Clark// FAIL_IF(addCount < 1); 12177eb01e00b1a1f7c649e1e78eb3f4644033ce94eeCary Clark if (addCount <= 1) { 121808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 121908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 122008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* startPtT = test->ptT(); 122108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* testPtT = startPtT; 122208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { // iterate through all spans associated with start 122308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppSpan = testPtT->span(); 122408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSpan->spanAddsCount() == addCount) { 122508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 122608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 122708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSpan->deleted()) { 122808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 122908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 123008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSegment* oppSegment = oppSpan->segment(); 123108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSegment == this) { 123208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 123308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 123408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // find range of spans to consider merging 123508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppPrev = oppSpan; 123608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppFirst = oppSpan; 123708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppPrev = oppPrev->prev())) { 123808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (!roughly_equal(oppPrev->t(), oppSpan->t())) { 123908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark break; 124008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPrev->spanAddsCount() == addCount) { 124208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 124308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPrev->deleted()) { 124508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 124608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppFirst = oppPrev; 124808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppNext = oppSpan; 125008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppLast = oppSpan; 125196fcdcc219d2a0d3579719b84b28bede76efba64halcanary while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { 125208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (!roughly_equal(oppNext->t(), oppSpan->t())) { 125308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark break; 125408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppNext->spanAddsCount() == addCount) { 125608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 125708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppNext->deleted()) { 125908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 126008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppLast = oppNext; 126208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppFirst == oppLast) { 126408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 126508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppTest = oppFirst; 126708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 126808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppTest == oppSpan) { 126908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 127008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 127108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // check to see if the candidate meets specific criteria: 127208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // it contains spans of segments in test's loop but not including 'this' 127308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* oppStartPtT = oppTest->ptT(); 127408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* oppPtT = oppStartPtT; 127508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppPtT = oppPtT->next()) != oppStartPtT) { 127608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSegment* oppPtTSegment = oppPtT->segment(); 127708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPtTSegment == this) { 127808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto tryNextSpan; 127908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 128008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* matchPtT = startPtT; 128108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 128208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (matchPtT->segment() == oppPtTSegment) { 128308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto foundMatch; 128408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 128508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((matchPtT = matchPtT->next()) != startPtT); 128608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto tryNextSpan; 128708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark foundMatch: // merge oppTest and oppSpan 128808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSegment->debugValidate(); 128930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppTest->mergeMatches(oppSpan); 129030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppTest->addOpp(oppSpan); 129108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSegment->debugValidate(); 129208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto checkNextSpan; 129308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 129455888e44171ffd48b591d19256884a969fe4da17caryclark tryNextSpan: 129508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ; 129608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); 129708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((testPtT = testPtT->next()) != startPtT); 129855888e44171ffd48b591d19256884a969fe4da17caryclarkcheckNextSpan: 129908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ; 130096fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while ((test = test->final() ? nullptr : test->upCast()->next())); 130108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark debugValidate(); 1302d78c088b6136590371fddd4cab67bfb4bf692fd3caryclark return true; 130308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark} 130408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark 130555888e44171ffd48b591d19256884a969fe4da17caryclark// adjacent spans may have points close by 130628da2837040cd116dd2d854dd3268723ca219f11Cary Clarkbool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan, 130728da2837040cd116dd2d854dd3268723ca219f11Cary Clark bool* found) const { 130855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* refHead = refSpan->ptT(); 130955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* checkHead = checkSpan->ptT(); 131055888e44171ffd48b591d19256884a969fe4da17caryclark// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart 131130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) { 131255888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 131355888e44171ffd48b591d19256884a969fe4da17caryclark // verify that no combination of points are close 131455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* dBugRef = refHead; 131555888e44171ffd48b591d19256884a969fe4da17caryclark do { 131655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* dBugCheck = checkHead; 131755888e44171ffd48b591d19256884a969fe4da17caryclark do { 131830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt)); 131955888e44171ffd48b591d19256884a969fe4da17caryclark dBugCheck = dBugCheck->next(); 132055888e44171ffd48b591d19256884a969fe4da17caryclark } while (dBugCheck != checkHead); 132155888e44171ffd48b591d19256884a969fe4da17caryclark dBugRef = dBugRef->next(); 132255888e44171ffd48b591d19256884a969fe4da17caryclark } while (dBugRef != refHead); 132355888e44171ffd48b591d19256884a969fe4da17caryclark#endif 132428da2837040cd116dd2d854dd3268723ca219f11Cary Clark *found = false; 132528da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 132655888e44171ffd48b591d19256884a969fe4da17caryclark } 132755888e44171ffd48b591d19256884a969fe4da17caryclark // check only unique points 132855888e44171ffd48b591d19256884a969fe4da17caryclark SkScalar distSqBest = SK_ScalarMax; 132955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* refBest = nullptr; 133055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* checkBest = nullptr; 133155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ref = refHead; 133255888e44171ffd48b591d19256884a969fe4da17caryclark do { 133355888e44171ffd48b591d19256884a969fe4da17caryclark if (ref->deleted()) { 133455888e44171ffd48b591d19256884a969fe4da17caryclark continue; 133555888e44171ffd48b591d19256884a969fe4da17caryclark } 133655888e44171ffd48b591d19256884a969fe4da17caryclark while (ref->ptAlreadySeen(refHead)) { 133755888e44171ffd48b591d19256884a969fe4da17caryclark ref = ref->next(); 133855888e44171ffd48b591d19256884a969fe4da17caryclark if (ref == refHead) { 133955888e44171ffd48b591d19256884a969fe4da17caryclark goto doneCheckingDistance; 134055888e44171ffd48b591d19256884a969fe4da17caryclark } 134155888e44171ffd48b591d19256884a969fe4da17caryclark } 134255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* check = checkHead; 134355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* refSeg = ref->segment(); 134428da2837040cd116dd2d854dd3268723ca219f11Cary Clark int escapeHatch = 100000; // defend against infinite loops 134555888e44171ffd48b591d19256884a969fe4da17caryclark do { 134655888e44171ffd48b591d19256884a969fe4da17caryclark if (check->deleted()) { 134755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 134855888e44171ffd48b591d19256884a969fe4da17caryclark } 134955888e44171ffd48b591d19256884a969fe4da17caryclark while (check->ptAlreadySeen(checkHead)) { 135055888e44171ffd48b591d19256884a969fe4da17caryclark check = check->next(); 135155888e44171ffd48b591d19256884a969fe4da17caryclark if (check == checkHead) { 135255888e44171ffd48b591d19256884a969fe4da17caryclark goto nextRef; 135355888e44171ffd48b591d19256884a969fe4da17caryclark } 135455888e44171ffd48b591d19256884a969fe4da17caryclark } 1355df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark SkScalar distSq = SkPointPriv::DistanceToSqd(ref->fPt, check->fPt); 135655888e44171ffd48b591d19256884a969fe4da17caryclark if (distSqBest > distSq && (refSeg != check->segment() 135755888e44171ffd48b591d19256884a969fe4da17caryclark || !refSeg->ptsDisjoint(*ref, *check))) { 135855888e44171ffd48b591d19256884a969fe4da17caryclark distSqBest = distSq; 135955888e44171ffd48b591d19256884a969fe4da17caryclark refBest = ref; 136055888e44171ffd48b591d19256884a969fe4da17caryclark checkBest = check; 136155888e44171ffd48b591d19256884a969fe4da17caryclark } 136228da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (--escapeHatch <= 0) { 136328da2837040cd116dd2d854dd3268723ca219f11Cary Clark return false; 136428da2837040cd116dd2d854dd3268723ca219f11Cary Clark } 136555888e44171ffd48b591d19256884a969fe4da17caryclark } while ((check = check->next()) != checkHead); 136628da2837040cd116dd2d854dd3268723ca219f11Cary Clark nextRef: 136755888e44171ffd48b591d19256884a969fe4da17caryclark ; 136855888e44171ffd48b591d19256884a969fe4da17caryclark } while ((ref = ref->next()) != refHead); 136955888e44171ffd48b591d19256884a969fe4da17caryclarkdoneCheckingDistance: 137028da2837040cd116dd2d854dd3268723ca219f11Cary Clark *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT, 1371ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark checkBest->fPt); 137228da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 137355888e44171ffd48b591d19256884a969fe4da17caryclark} 137455888e44171ffd48b591d19256884a969fe4da17caryclark 137555888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this function in sync with debugMoveNearby() 137654359294a7c9dc54802d512a5d891a35c1663392caryclark// Move nearby t values and pts so they all hang off the same span. Alignment happens later. 137728da2837040cd116dd2d854dd3268723ca219f11Cary Clarkbool SkOpSegment::moveNearby() { 137854359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 137955888e44171ffd48b591d19256884a969fe4da17caryclark // release undeleted spans pointing to this seg that are linked to the primary span 138055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* spanBase = &fHead; 138143938b8533dbee75816726b54737e410097428ceCary Clark int escapeHatch = 9999; // the largest count for a regular test is 50; for a fuzzer, 500 138254359294a7c9dc54802d512a5d891a35c1663392caryclark do { 138355888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* ptT = spanBase->ptT(); 138455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* headPtT = ptT; 138555888e44171ffd48b591d19256884a969fe4da17caryclark while ((ptT = ptT->next()) != headPtT) { 138643938b8533dbee75816726b54737e410097428ceCary Clark if (!--escapeHatch) { 138743938b8533dbee75816726b54737e410097428ceCary Clark return false; 138843938b8533dbee75816726b54737e410097428ceCary Clark } 138955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* test = ptT->span(); 139055888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->segment() == this && !ptT->deleted() && test != spanBase 139155888e44171ffd48b591d19256884a969fe4da17caryclark && test->ptT() == ptT) { 139255888e44171ffd48b591d19256884a969fe4da17caryclark if (test->final()) { 139355888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase == &fHead) { 139455888e44171ffd48b591d19256884a969fe4da17caryclark this->clearAll(); 139528da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 139655888e44171ffd48b591d19256884a969fe4da17caryclark } 139755888e44171ffd48b591d19256884a969fe4da17caryclark spanBase->upCast()->release(ptT); 139855888e44171ffd48b591d19256884a969fe4da17caryclark } else if (test->prev()) { 139955888e44171ffd48b591d19256884a969fe4da17caryclark test->upCast()->release(headPtT); 140055888e44171ffd48b591d19256884a969fe4da17caryclark } 140155888e44171ffd48b591d19256884a969fe4da17caryclark break; 1402570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 140307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 140455888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = spanBase->upCast()->next(); 140555888e44171ffd48b591d19256884a969fe4da17caryclark } while (!spanBase->final()); 140655888e44171ffd48b591d19256884a969fe4da17caryclark // This loop looks for adjacent spans which are near by 140755888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = &fHead; 140855888e44171ffd48b591d19256884a969fe4da17caryclark do { // iterate through all spans associated with start 140955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* test = spanBase->upCast()->next(); 141028da2837040cd116dd2d854dd3268723ca219f11Cary Clark bool found; 141128da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (!this->spansNearby(spanBase, test, &found)) { 141228da2837040cd116dd2d854dd3268723ca219f11Cary Clark return false; 141328da2837040cd116dd2d854dd3268723ca219f11Cary Clark } 141428da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (found) { 141555888e44171ffd48b591d19256884a969fe4da17caryclark if (test->final()) { 141655888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase->prev()) { 141755888e44171ffd48b591d19256884a969fe4da17caryclark test->merge(spanBase->upCast()); 141855888e44171ffd48b591d19256884a969fe4da17caryclark } else { 141955888e44171ffd48b591d19256884a969fe4da17caryclark this->clearAll(); 142028da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 142155888e44171ffd48b591d19256884a969fe4da17caryclark } 142255888e44171ffd48b591d19256884a969fe4da17caryclark } else { 142355888e44171ffd48b591d19256884a969fe4da17caryclark spanBase->merge(test->upCast()); 142455888e44171ffd48b591d19256884a969fe4da17caryclark } 142555888e44171ffd48b591d19256884a969fe4da17caryclark } 142655888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = test; 142755888e44171ffd48b591d19256884a969fe4da17caryclark } while (!spanBase->final()); 142854359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 142928da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 1430dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1431dac1d17027dcaa5596885a9f333979418b35001ccaryclark 143254359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::operand() const { 143354359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->operand(); 14345e27e0eb1d1d4c7674e221d3ba3314500ea0b97acaryclark} 14355e27e0eb1d1d4c7674e221d3ba3314500ea0b97acaryclark 143654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::oppXor() const { 143754359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->oppXor(); 1438ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark} 1439ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark 144054359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { 144154359294a7c9dc54802d512a5d891a35c1663392caryclark if (fVerb == SkPath::kLine_Verb) { 144254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 14430dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 144454359294a7c9dc54802d512a5d891a35c1663392caryclark // quads (and cubics) can loop back to nearly a line so that an opposite curve 144554359294a7c9dc54802d512a5d891a35c1663392caryclark // hits in two places with very different t values. 144654359294a7c9dc54802d512a5d891a35c1663392caryclark // OPTIMIZATION: curves could be preflighted so that, for example, something like 144754359294a7c9dc54802d512a5d891a35c1663392caryclark // 'controls contained by ends' could avoid this check for common curves 144854359294a7c9dc54802d512a5d891a35c1663392caryclark // 'ends are extremes in x or y' is cheaper to compute and real-world common 144954359294a7c9dc54802d512a5d891a35c1663392caryclark // on the other hand, the below check is relatively inexpensive 145054359294a7c9dc54802d512a5d891a35c1663392caryclark double midT = (t1 + t2) / 2; 145154359294a7c9dc54802d512a5d891a35c1663392caryclark SkPoint midPt = this->ptAtT(midT); 1452df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark double seDistSq = SkTMax(SkPointPriv::DistanceToSqd(pt1, pt2) * 2, FLT_EPSILON * 2); 1453df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark return SkPointPriv::DistanceToSqd(midPt, pt1) > seDistSq || 1454df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark SkPointPriv::DistanceToSqd(midPt, pt2) > seDistSq; 145554359294a7c9dc54802d512a5d891a35c1663392caryclark} 145654359294a7c9dc54802d512a5d891a35c1663392caryclark 145754359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 145854359294a7c9dc54802d512a5d891a35c1663392caryclark int* maxWinding, int* sumWinding) { 145954359294a7c9dc54802d512a5d891a35c1663392caryclark int deltaSum = SpanSign(start, end); 146054359294a7c9dc54802d512a5d891a35c1663392caryclark *maxWinding = *sumMiWinding; 146154359294a7c9dc54802d512a5d891a35c1663392caryclark *sumWinding = *sumMiWinding -= deltaSum; 146260e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 1463dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1464dac1d17027dcaa5596885a9f333979418b35001ccaryclark 146554359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 146654359294a7c9dc54802d512a5d891a35c1663392caryclark int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, 146754359294a7c9dc54802d512a5d891a35c1663392caryclark int* oppSumWinding) { 146854359294a7c9dc54802d512a5d891a35c1663392caryclark int deltaSum = SpanSign(start, end); 146954359294a7c9dc54802d512a5d891a35c1663392caryclark int oppDeltaSum = OppSign(start, end); 147007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 147107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *maxWinding = *sumSuWinding; 147207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *sumWinding = *sumSuWinding -= deltaSum; 147307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppMaxWinding = *sumMiWinding; 147407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppSumWinding = *sumMiWinding -= oppDeltaSum; 147507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 147607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *maxWinding = *sumMiWinding; 147707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *sumWinding = *sumMiWinding -= deltaSum; 147807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppMaxWinding = *sumSuWinding; 147907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppSumWinding = *sumSuWinding -= oppDeltaSum; 148007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 148160e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 148260e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM); 148307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 148407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1485b36a3cd137e2b6c328854015018594bb9967e493caryclarkbool SkOpSegment::sortAngles() { 148654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* span = &this->fHead; 14874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 148854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* fromAngle = span->fromAngle(); 148996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle(); 1490dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (!fromAngle && !toAngle) { 14914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 14924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1493cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#if DEBUG_ANGLE 14944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool wroteAfterHeader = false; 1495cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#endif 149654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* baseAngle = fromAngle; 149754359294a7c9dc54802d512a5d891a35c1663392caryclark if (fromAngle && toAngle) { 14984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 149954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(), 150054359294a7c9dc54802d512a5d891a35c1663392caryclark span->debugID()); 150154359294a7c9dc54802d512a5d891a35c1663392caryclark wroteAfterHeader = true; 15024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 1503b36a3cd137e2b6c328854015018594bb9967e493caryclark FAIL_IF(!fromAngle->insert(toAngle)); 150454359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (!fromAngle) { 150554359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle = toAngle; 150607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 150754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 15084431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 150954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oSpan = ptT->span(); 151054359294a7c9dc54802d512a5d891a35c1663392caryclark if (oSpan == span) { 151154359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 151254359294a7c9dc54802d512a5d891a35c1663392caryclark } 151354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* oAngle = oSpan->fromAngle(); 1514dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (oAngle) { 1515570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_ANGLE 15164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!wroteAfterHeader) { 151754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 151854359294a7c9dc54802d512a5d891a35c1663392caryclark span->t(), span->debugID()); 15194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org wroteAfterHeader = true; 15204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1521570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 152254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oAngle->loopContains(baseAngle)) { 15238cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org baseAngle->insert(oAngle); 15248cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 15254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 152654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oSpan->final()) { 152754359294a7c9dc54802d512a5d891a35c1663392caryclark oAngle = oSpan->upCast()->toAngle(); 152854359294a7c9dc54802d512a5d891a35c1663392caryclark if (oAngle) { 15294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 153054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!wroteAfterHeader) { 153154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 153254359294a7c9dc54802d512a5d891a35c1663392caryclark span->t(), span->debugID()); 153354359294a7c9dc54802d512a5d891a35c1663392caryclark wroteAfterHeader = true; 153454359294a7c9dc54802d512a5d891a35c1663392caryclark } 15354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 153654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oAngle->loopContains(baseAngle)) { 153754359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle->insert(oAngle); 153854359294a7c9dc54802d512a5d891a35c1663392caryclark } 15398cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 15404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 154154359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((ptT = ptT->next()) != stopPtT); 154254359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseAngle->loopCount() == 1) { 154396fcdcc219d2a0d3579719b84b28bede76efba64halcanary span->setFromAngle(nullptr); 154454359294a7c9dc54802d512a5d891a35c1663392caryclark if (toAngle) { 154596fcdcc219d2a0d3579719b84b28bede76efba64halcanary span->upCast()->setToAngle(nullptr); 15464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 154796fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 15484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 15494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 15504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!baseAngle || baseAngle->loopCount() > 1); 15514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 155254359294a7c9dc54802d512a5d891a35c1663392caryclark } while (!span->final() && (span = span->upCast()->next())); 1553b36a3cd137e2b6c328854015018594bb9967e493caryclark return true; 1554570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1555570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 155654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 15571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDCurve* edge) const { 1558cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(start != end); 155954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& startPtT = *start->ptT(); 156054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& endPtT = *end->ptT(); 15611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(edge->fVerb = fVerb); 15621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[0].set(startPtT.fPt); 1563cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int points = SkPathOpsVerbToPoints(fVerb); 15641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[points].set(endPtT.fPt); 1565cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kLine_Verb) { 1566cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1567cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 156854359294a7c9dc54802d512a5d891a35c1663392caryclark double startT = startPtT.fT; 156954359294a7c9dc54802d512a5d891a35c1663392caryclark double endT = endPtT.fT; 1570cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1571cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // don't compute midpoints if we already have them 1572cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fLine[1].set(fPts[1]); 15741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return false; 15751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (fVerb == SkPath::kConic_Verb) { 15771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic[1].set(fPts[1]); 15781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic.fWeight = fWeight; 1579cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1580cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1581cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 158254359294a7c9dc54802d512a5d891a35c1663392caryclark if (startT == 0) { 15831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[1].set(fPts[1]); 15841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[2].set(fPts[2]); 1585cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1586cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 15871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[1].set(fPts[2]); 15881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[2].set(fPts[1]); 1589cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1590cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1591cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT); 15931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (fVerb == SkPath::kConic_Verb) { 15941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2], 15951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark startT, endT, &edge->fConic.fWeight); 1596cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } else { 1597cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 15981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]); 1599cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1600cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return true; 160107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 160207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 160327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclarkbool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, 160455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const { 160527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // average t, find mid pt 160627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark double midT = (prior->t() + spanBase->t()) / 2; 160727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkPoint midPt = this->ptAtT(midT); 160827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark bool coincident = true; 160927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // if the mid pt is not near either end pt, project perpendicular through opp seg 161027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) 161127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { 161255888e44171ffd48b591d19256884a969fe4da17caryclark if (priorPtT->span() == ptT->span()) { 161355888e44171ffd48b591d19256884a969fe4da17caryclark return false; 161455888e44171ffd48b591d19256884a969fe4da17caryclark } 161527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark coincident = false; 161627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkIntersections i; 161755888e44171ffd48b591d19256884a969fe4da17caryclark SkDCurve curvePart; 161855888e44171ffd48b591d19256884a969fe4da17caryclark this->subDivide(prior, spanBase, &curvePart); 161955888e44171ffd48b591d19256884a969fe4da17caryclark SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f); 162055888e44171ffd48b591d19256884a969fe4da17caryclark SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f); 162155888e44171ffd48b591d19256884a969fe4da17caryclark SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}}; 162255888e44171ffd48b591d19256884a969fe4da17caryclark SkDCurve oppPart; 162355888e44171ffd48b591d19256884a969fe4da17caryclark opp->subDivide(priorPtT->span(), ptT->span(), &oppPart); 162455888e44171ffd48b591d19256884a969fe4da17caryclark (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i); 162527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // measure distance and see if it's small enough to denote coincidence 162627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark for (int index = 0; index < i.used(); ++index) { 162755888e44171ffd48b591d19256884a969fe4da17caryclark if (!between(0, i[0][index], 1)) { 162855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 162955888e44171ffd48b591d19256884a969fe4da17caryclark } 163027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkDPoint oppPt = i.pt(index); 163130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (oppPt.approximatelyDEqual(midPt)) { 163255888e44171ffd48b591d19256884a969fe4da17caryclark // the coincidence can occur at almost any angle 163355888e44171ffd48b591d19256884a969fe4da17caryclark coincident = true; 163427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return coincident; 163827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 163927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 1640ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary ClarkSkOpSpan* SkOpSegment::undoneSpan() { 1641ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark SkOpSpan* span = &fHead; 1642ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark SkOpSpanBase* next; 164354359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1644ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark next = span->next(); 164554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->done()) { 1646ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark return span; 164707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1648ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark } while (!next->final() && (span = next->upCast())); 1649ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark return nullptr; 165007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 165107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 165254359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { 165354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* lesser = start->starter(end); 165454359294a7c9dc54802d512a5d891a35c1663392caryclark int oppWinding = lesser->oppSum(); 165554359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSpanWinding = SkOpSegment::OppSign(start, end); 165607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) 165707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && oppWinding != SK_MaxS32) { 165807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com oppWinding -= oppSpanWinding; 165907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 166007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return oppWinding; 166107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 166207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 166307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { 166454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* startSpan = angle->start(); 166554359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* endSpan = angle->end(); 166654359294a7c9dc54802d512a5d891a35c1663392caryclark return updateOppWinding(endSpan, startSpan); 166707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 166807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 166907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { 167054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* startSpan = angle->start(); 167154359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* endSpan = angle->end(); 167254359294a7c9dc54802d512a5d891a35c1663392caryclark return updateOppWinding(startSpan, endSpan); 167307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 167407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1675624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 1676624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* lesser = start->starter(end); 167754359294a7c9dc54802d512a5d891a35c1663392caryclark int winding = lesser->windSum(); 16788cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (winding == SK_MinS32) { 1679bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark winding = lesser->computeWindSum(); 1680624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 1681624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (winding == SK_MinS32) { 16828cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return winding; 16838cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 168454359294a7c9dc54802d512a5d891a35c1663392caryclark int spanWinding = SkOpSegment::SpanSign(start, end); 1685570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (winding && UseInnerWinding(winding - spanWinding, winding) 1686570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com && winding != SK_MaxS32) { 168707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com winding -= spanWinding; 168807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 168907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return winding; 169007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 169107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1692624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWinding(SkOpAngle* angle) { 1693624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* startSpan = angle->start(); 1694624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* endSpan = angle->end(); 169554359294a7c9dc54802d512a5d891a35c1663392caryclark return updateWinding(endSpan, startSpan); 1696570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1697570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1698624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { 1699624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* startSpan = angle->start(); 1700624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* endSpan = angle->end(); 170154359294a7c9dc54802d512a5d891a35c1663392caryclark return updateWinding(startSpan, endSpan); 1702570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1703570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1704570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// OPTIMIZATION: does the following also work, and is it any faster? 1705570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// return outerWinding * innerWinding > 0 1706570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) 1707570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { 1708570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(outerWinding != SK_MaxS32); 1709570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(innerWinding != SK_MaxS32); 171060e0fee6d4acff638ccc9670c4055aced529a7a0bungeman int absOut = SkTAbs(outerWinding); 171160e0fee6d4acff638ccc9670c4055aced529a7a0bungeman int absIn = SkTAbs(innerWinding); 1712570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 1713570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return result; 1714570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1715570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 171607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::windSum(const SkOpAngle* angle) const { 171754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* minSpan = angle->start()->starter(angle->end()); 171854359294a7c9dc54802d512a5d891a35c1663392caryclark return minSpan->windSum(); 171907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 1720