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" 1154359294a7c9dc54802d512a5d891a35c1663392caryclark 1254359294a7c9dc54802d512a5d891a35c1663392caryclark/* 1354359294a7c9dc54802d512a5d891a35c1663392caryclarkAfter computing raw intersections, post process all segments to: 1454359294a7c9dc54802d512a5d891a35c1663392caryclark- find small collections of points that can be collapsed to a single point 1554359294a7c9dc54802d512a5d891a35c1663392caryclark- find missing intersections to resolve differences caused by different algorithms 1654359294a7c9dc54802d512a5d891a35c1663392caryclark 1754359294a7c9dc54802d512a5d891a35c1663392caryclarkConsider segments containing tiny or small intervals. Consider coincident segments 1854359294a7c9dc54802d512a5d891a35c1663392caryclarkbecause coincidence finds intersections through distance measurement that non-coincident 1954359294a7c9dc54802d512a5d891a35c1663392caryclarkintersection tests cannot. 2054359294a7c9dc54802d512a5d891a35c1663392caryclark */ 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define F (false) // discard the edge 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define T (true) // keep the edge 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic const bool gUnaryActiveEdge[2][2] = { 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// from=0 from=1 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// to=0,1 to=0,1 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {F, T}, {T, F}, 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com}; 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3154359294a7c9dc54802d512a5d891a35c1663392caryclarkstatic const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = { 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// miFrom=0 miFrom=1 334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// miTo=0 miTo=1 miTo=0 miTo=1 344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@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 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com}; 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#undef F 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#undef T 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4554359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, 46bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase** endPtr, bool* done) { 47bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) { 484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return result; 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 50bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) { 5154359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5396fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5654359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr, 57bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase** endPtr, bool* done) { 5854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* upSpan = start->upCastable(); 5954359294a7c9dc54802d512a5d891a35c1663392caryclark if (upSpan) { 6054359294a7c9dc54802d512a5d891a35c1663392caryclark if (upSpan->windValue() || upSpan->oppValue()) { 6154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = upSpan->next(); 6254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!*endPtr) { 6354359294a7c9dc54802d512a5d891a35c1663392caryclark *startPtr = start; 6454359294a7c9dc54802d512a5d891a35c1663392caryclark *endPtr = next; 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!upSpan->done()) { 6754359294a7c9dc54802d512a5d891a35c1663392caryclark if (upSpan->windSum() != SK_MinS32) { 6854359294a7c9dc54802d512a5d891a35c1663392caryclark return spanToAngle(start, next); 694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *done = false; 714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 7354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(upSpan->done()); 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* downSpan = start->prev(); 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // edge leading into junction 7854359294a7c9dc54802d512a5d891a35c1663392caryclark if (downSpan) { 7954359294a7c9dc54802d512a5d891a35c1663392caryclark if (downSpan->windValue() || downSpan->oppValue()) { 8054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!*endPtr) { 8154359294a7c9dc54802d512a5d891a35c1663392caryclark *startPtr = start; 8254359294a7c9dc54802d512a5d891a35c1663392caryclark *endPtr = downSpan; 8354359294a7c9dc54802d512a5d891a35c1663392caryclark } 8454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!downSpan->done()) { 8554359294a7c9dc54802d512a5d891a35c1663392caryclark if (downSpan->windSum() != SK_MinS32) { 8654359294a7c9dc54802d512a5d891a35c1663392caryclark return spanToAngle(start, downSpan); 874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *done = false; 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 9154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(downSpan->done()); 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9496fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 9754359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr, 98bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase** endPtr, bool* done) { 9954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* oPtT = start->ptT()->next(); 10054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = oPtT->segment(); 10154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oSpan = oPtT->span(); 102bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark return other->activeAngleInner(oSpan, startPtr, endPtr, done); 10307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 10554359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, 10654359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOp op) { 10754359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = this->updateWinding(end, start); 10854359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding = this->updateOppWinding(end, start); 10965f553182ab7069378ef863d30094d0327f178d0caryclark#if DEBUG_LIMIT_WIND_SUM 11065f553182ab7069378ef863d30094d0327f178d0caryclark SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM); 11165f553182ab7069378ef863d30094d0327f178d0caryclark SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM); 11265f553182ab7069378ef863d30094d0327f178d0caryclark#endif 11354359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand()) { 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap<int>(sumMiWinding, sumSuWinding); 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11654359294a7c9dc54802d512a5d891a35c1663392caryclark return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding); 11707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11954359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, 12054359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOp op, int* sumMiWinding, int* sumSuWinding) { 1214431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 12254359294a7c9dc54802d512a5d891a35c1663392caryclark this->setUpWindings(start, end, sumMiWinding, sumSuWinding, 1234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool miFrom; 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool miTo; 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool suFrom; 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool suTo; 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 1294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org miFrom = (oppMaxWinding & xorMiMask) != 0; 1304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org miTo = (oppSumWinding & xorMiMask) != 0; 1314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org suFrom = (maxWinding & xorSuMask) != 0; 1324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org suTo = (sumWinding & xorSuMask) != 0; 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 1344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org miFrom = (maxWinding & xorMiMask) != 0; 1354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org miTo = (sumWinding & xorMiMask) != 0; 1364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org suFrom = (oppMaxWinding & xorSuMask) != 0; 1374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org suTo = (oppSumWinding & xorSuMask) != 0; 13807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_ACTIVE_OP 141dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", 14254359294a7c9dc54802d512a5d891a35c1663392caryclark __FUNCTION__, debugID(), start->t(), end->t(), 143570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 14854359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 14954359294a7c9dc54802d512a5d891a35c1663392caryclark int sumWinding = updateWinding(end, start); 15054359294a7c9dc54802d512a5d891a35c1663392caryclark return activeWinding(start, end, &sumWinding); 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 15354359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) { 1544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org int maxWinding; 15554359294a7c9dc54802d512a5d891a35c1663392caryclark setUpWinding(start, end, &maxWinding, sumWinding); 1564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool from = maxWinding != 0; 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool to = *sumWinding != 0; 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool result = gUnaryActiveEdge[from][to]; 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 162ef784fb7f58c9c021172045a8e0b396c81fdc425caryclarkbool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, 163ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark SkPathWriter* path) const { 164025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(start->starter(end)->alreadyAdded()); 165eed356d281adbf93ecbd89cb23913a7861cd8578caryclark SkDCurveSweep curvePart; 166eed356d281adbf93ecbd89cb23913a7861cd8578caryclark start->segment()->subDivide(start, end, &curvePart.fCurve); 167eed356d281adbf93ecbd89cb23913a7861cd8578caryclark curvePart.setCurveHullSweep(fVerb); 168eed356d281adbf93ecbd89cb23913a7861cd8578caryclark SkPath::Verb verb = curvePart.isCurve() ? fVerb : SkPath::kLine_Verb; 169eed356d281adbf93ecbd89cb23913a7861cd8578caryclark path->deferredMove(start->ptT()); 170eed356d281adbf93ecbd89cb23913a7861cd8578caryclark switch (verb) { 171eed356d281adbf93ecbd89cb23913a7861cd8578caryclark case SkPath::kLine_Verb: 172a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!path->deferredLine(end->ptT())); 173eed356d281adbf93ecbd89cb23913a7861cd8578caryclark break; 174eed356d281adbf93ecbd89cb23913a7861cd8578caryclark case SkPath::kQuad_Verb: 175a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark path->quadTo(curvePart.fCurve.fQuad[1].asSkPoint(), end->ptT()); 176eed356d281adbf93ecbd89cb23913a7861cd8578caryclark break; 177eed356d281adbf93ecbd89cb23913a7861cd8578caryclark case SkPath::kConic_Verb: 178a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark path->conicTo(curvePart.fCurve.fConic[1].asSkPoint(), end->ptT(), 179eed356d281adbf93ecbd89cb23913a7861cd8578caryclark curvePart.fCurve.fConic.fWeight); 180eed356d281adbf93ecbd89cb23913a7861cd8578caryclark break; 181eed356d281adbf93ecbd89cb23913a7861cd8578caryclark case SkPath::kCubic_Verb: 182a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark path->cubicTo(curvePart.fCurve.fCubic[1].asSkPoint(), 183a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark curvePart.fCurve.fCubic[2].asSkPoint(), end->ptT()); 184eed356d281adbf93ecbd89cb23913a7861cd8578caryclark break; 185eed356d281adbf93ecbd89cb23913a7861cd8578caryclark default: 186eed356d281adbf93ecbd89cb23913a7861cd8578caryclark SkASSERT(0); 18707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 188ef784fb7f58c9c021172045a8e0b396c81fdc425caryclark return true; 18907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 19007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 19155888e44171ffd48b591d19256884a969fe4da17caryclarkconst SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const { 19255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* test = &fHead; 19355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* testPtT; 19455888e44171ffd48b591d19256884a969fe4da17caryclark SkPoint pt = this->ptAtT(t); 1954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 19655888e44171ffd48b591d19256884a969fe4da17caryclark testPtT = test->ptT(); 19755888e44171ffd48b591d19256884a969fe4da17caryclark if (testPtT->fT == t) { 19854359294a7c9dc54802d512a5d891a35c1663392caryclark break; 19954359294a7c9dc54802d512a5d891a35c1663392caryclark } 200ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark if (!this->match(testPtT, this, t, pt)) { 20155888e44171ffd48b591d19256884a969fe4da17caryclark if (t < testPtT->fT) { 20255888e44171ffd48b591d19256884a969fe4da17caryclark return nullptr; 20355888e44171ffd48b591d19256884a969fe4da17caryclark } 20455888e44171ffd48b591d19256884a969fe4da17caryclark continue; 20555888e44171ffd48b591d19256884a969fe4da17caryclark } 20655888e44171ffd48b591d19256884a969fe4da17caryclark if (!opp) { 20755888e44171ffd48b591d19256884a969fe4da17caryclark return testPtT; 20855888e44171ffd48b591d19256884a969fe4da17caryclark } 20955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* loop = testPtT->next(); 21055888e44171ffd48b591d19256884a969fe4da17caryclark while (loop != testPtT) { 21155888e44171ffd48b591d19256884a969fe4da17caryclark if (loop->segment() == this && loop->fT == t && loop->fPt == pt) { 21255888e44171ffd48b591d19256884a969fe4da17caryclark goto foundMatch; 21355888e44171ffd48b591d19256884a969fe4da17caryclark } 21455888e44171ffd48b591d19256884a969fe4da17caryclark loop = loop->next(); 21555888e44171ffd48b591d19256884a969fe4da17caryclark } 21655888e44171ffd48b591d19256884a969fe4da17caryclark return nullptr; 21754359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = test->upCast()->next())); 21855888e44171ffd48b591d19256884a969fe4da17caryclarkfoundMatch: 21955888e44171ffd48b591d19256884a969fe4da17caryclark return opp && !test->contains(opp) ? nullptr : testPtT; 22055888e44171ffd48b591d19256884a969fe4da17caryclark} 22155888e44171ffd48b591d19256884a969fe4da17caryclark 22255888e44171ffd48b591d19256884a969fe4da17caryclark// break the span so that the coincident part does not change the angle of the remainder 22355888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) { 22455888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(newT)) { 22555888e44171ffd48b591d19256884a969fe4da17caryclark return true; 22607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 22729b2563afb1677515739f1d24fb27733626eca92caryclark this->globalState()->resetAllocatedOpSpan(); 228a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!between(0, newT, 1)); 22929b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* newPtT = this->addT(newT); 23029b2563afb1677515739f1d24fb27733626eca92caryclark *startOver |= this->globalState()->allocatedOpSpan(); 23155888e44171ffd48b591d19256884a969fe4da17caryclark if (!newPtT) { 23255888e44171ffd48b591d19256884a969fe4da17caryclark return false; 23355888e44171ffd48b591d19256884a969fe4da17caryclark } 23455888e44171ffd48b591d19256884a969fe4da17caryclark newPtT->fPt = this->ptAtT(newT); 23529b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT); 23629b2563afb1677515739f1d24fb27733626eca92caryclark if (oppPrev) { 2378016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // const cast away to change linked list; pt/t values stays unchanged 23829b2563afb1677515739f1d24fb27733626eca92caryclark SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test); 23930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark writableTest->mergeMatches(newPtT->span()); 24029b2563afb1677515739f1d24fb27733626eca92caryclark writableTest->ptT()->addOpp(newPtT, oppPrev); 24155888e44171ffd48b591d19256884a969fe4da17caryclark writableTest->checkForCollapsedCoincidence(); 24255888e44171ffd48b591d19256884a969fe4da17caryclark } 24355888e44171ffd48b591d19256884a969fe4da17caryclark return true; 24407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 24507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 24655888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugAddT() 247c7c76d81fd09332a9a1d4b9f19b2a2dab3c723c3Cary ClarkSkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) { 24854359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 24929b2563afb1677515739f1d24fb27733626eca92caryclark SkOpSpanBase* spanBase = &fHead; 2504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 25129b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* result = spanBase->ptT(); 25227c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) { 25329b2563afb1677515739f1d24fb27733626eca92caryclark spanBase->bumpSpanAdds(); 254ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark return result; 25554359294a7c9dc54802d512a5d891a35c1663392caryclark } 25654359294a7c9dc54802d512a5d891a35c1663392caryclark if (t < result->fT) { 25754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prev = result->span()->prev(); 25829b2563afb1677515739f1d24fb27733626eca92caryclark FAIL_WITH_NULL_IF(!prev); 25929b2563afb1677515739f1d24fb27733626eca92caryclark // marks in global state that new op span has been allocated 26029b2563afb1677515739f1d24fb27733626eca92caryclark SkOpSpan* span = this->insert(prev); 26154359294a7c9dc54802d512a5d891a35c1663392caryclark span->init(this, prev, t, pt); 26254359294a7c9dc54802d512a5d891a35c1663392caryclark this->debugValidate(); 26354359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_ADD_T 26454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, 26554359294a7c9dc54802d512a5d891a35c1663392caryclark span->segment()->debugID(), span->debugID()); 26654359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 26708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark span->bumpSpanAdds(); 26854359294a7c9dc54802d512a5d891a35c1663392caryclark return span->ptT(); 26954359294a7c9dc54802d512a5d891a35c1663392caryclark } 27029b2563afb1677515739f1d24fb27733626eca92caryclark FAIL_WITH_NULL_IF(spanBase == &fTail); 27129b2563afb1677515739f1d24fb27733626eca92caryclark } while ((spanBase = spanBase->upCast()->next())); 27254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0); 27329b2563afb1677515739f1d24fb27733626eca92caryclark return nullptr; // we never get here, but need this to satisfy compiler 2744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 276c7c76d81fd09332a9a1d4b9f19b2a2dab3c723c3Cary ClarkSkOpPtT* SkOpSegment::addT(double t) { 277c7c76d81fd09332a9a1d4b9f19b2a2dab3c723c3Cary Clark return addT(t, this->ptAtT(t)); 278c7c76d81fd09332a9a1d4b9f19b2a2dab3c723c3Cary Clark} 279c7c76d81fd09332a9a1d4b9f19b2a2dab3c723c3Cary Clark 28055888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::calcAngles() { 28154359294a7c9dc54802d512a5d891a35c1663392caryclark bool activePrior = !fHead.isCanceled(); 28254359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior && !fHead.simple()) { 28355888e44171ffd48b591d19256884a969fe4da17caryclark addStartSpan(); 2840dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 28554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prior = &fHead; 28654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* spanBase = fHead.next(); 28754359294a7c9dc54802d512a5d891a35c1663392caryclark while (spanBase != &fTail) { 28854359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior) { 28955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate( 29055888e44171ffd48b591d19256884a969fe4da17caryclark this->globalState()->allocator()); 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) { 29855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate( 29955888e44171ffd48b591d19256884a969fe4da17caryclark this->globalState()->allocator()); 30054359294a7c9dc54802d512a5d891a35c1663392caryclark angle->set(span, next); 30154359294a7c9dc54802d512a5d891a35c1663392caryclark span->setToAngle(angle); 30254359294a7c9dc54802d512a5d891a35c1663392caryclark } 30354359294a7c9dc54802d512a5d891a35c1663392caryclark activePrior = active; 30454359294a7c9dc54802d512a5d891a35c1663392caryclark prior = span; 30554359294a7c9dc54802d512a5d891a35c1663392caryclark spanBase = next; 3064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 30754359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior && !fTail.simple()) { 30855888e44171ffd48b591d19256884a969fe4da17caryclark addEndSpan(); 3094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 31065f553182ab7069378ef863d30094d0327f178d0caryclark} 31165f553182ab7069378ef863d30094d0327f178d0caryclark 31255888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugClearAll() 31355888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::clearAll() { 31455888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpan* span = &fHead; 31555888e44171ffd48b591d19256884a969fe4da17caryclark do { 31655888e44171ffd48b591d19256884a969fe4da17caryclark this->clearOne(span); 31755888e44171ffd48b591d19256884a969fe4da17caryclark } while ((span = span->next()->upCastable())); 31855888e44171ffd48b591d19256884a969fe4da17caryclark this->globalState()->coincidence()->release(this); 31955888e44171ffd48b591d19256884a969fe4da17caryclark} 32055888e44171ffd48b591d19256884a969fe4da17caryclark 32155888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugClearOne() 32255888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::clearOne(SkOpSpan* span) { 32355888e44171ffd48b591d19256884a969fe4da17caryclark span->setWindValue(0); 32455888e44171ffd48b591d19256884a969fe4da17caryclark span->setOppValue(0); 32555888e44171ffd48b591d19256884a969fe4da17caryclark this->markDone(span); 32655888e44171ffd48b591d19256884a969fe4da17caryclark} 32755888e44171ffd48b591d19256884a969fe4da17caryclark 32830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkbool SkOpSegment::collapsed(double s, double e) const { 32930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpSpanBase* span = &fHead; 33030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark do { 33130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (span->collapsed(s, e)) { 33230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return true; 33330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 33430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } while (span->upCastable() && (span = span->upCast()->next())); 33530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return false; 33630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 33730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 33854359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 33954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 340624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* baseSegment = baseAngle->segment(); 34154359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); 34254359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding; 34354359294a7c9dc54802d512a5d891a35c1663392caryclark bool binary = includeType >= SkOpAngle::kBinarySingle; 34454359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 34554359294a7c9dc54802d512a5d891a35c1663392caryclark sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); 34654359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseSegment->operand()) { 34754359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap<int>(sumMiWinding, sumSuWinding); 3480dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 34954359294a7c9dc54802d512a5d891a35c1663392caryclark } 35054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* nextSegment = nextAngle->segment(); 35154359294a7c9dc54802d512a5d891a35c1663392caryclark int maxWinding, sumWinding; 35254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 35354359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 35454359294a7c9dc54802d512a5d891a35c1663392caryclark int oppMaxWinding, oppSumWinding; 35554359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 35654359294a7c9dc54802d512a5d891a35c1663392caryclark &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 35754359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 35854359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle); 3594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 36054359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 36154359294a7c9dc54802d512a5d891a35c1663392caryclark &maxWinding, &sumWinding); 36254359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 3634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 36454359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle->setLastMarked(last); 3654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 367624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkvoid SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, 36854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 369624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* baseSegment = baseAngle->segment(); 37054359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = baseSegment->updateWinding(baseAngle); 37154359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding; 37254359294a7c9dc54802d512a5d891a35c1663392caryclark bool binary = includeType >= SkOpAngle::kBinarySingle; 3730dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed if (binary) { 37454359294a7c9dc54802d512a5d891a35c1663392caryclark sumSuWinding = baseSegment->updateOppWinding(baseAngle); 37554359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseSegment->operand()) { 37654359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap<int>(sumMiWinding, sumSuWinding); 3770dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 3780dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 37954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* nextSegment = nextAngle->segment(); 38054359294a7c9dc54802d512a5d891a35c1663392caryclark int maxWinding, sumWinding; 38154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 38254359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 38354359294a7c9dc54802d512a5d891a35c1663392caryclark int oppMaxWinding, oppSumWinding; 38454359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 38554359294a7c9dc54802d512a5d891a35c1663392caryclark &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 38654359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 38754359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle); 3884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 38954359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 39054359294a7c9dc54802d512a5d891a35c1663392caryclark &maxWinding, &sumWinding); 39154359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 3920dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 39354359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle->setLastMarked(last); 3944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 396dac1d17027dcaa5596885a9f333979418b35001ccaryclark// at this point, the span is already ordered, or unorderable 39754359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, 39854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 3994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(includeType != SkOpAngle::kUnaryXor); 40054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* firstAngle = this->spanToAngle(end, start); 40196fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == firstAngle || nullptr == firstAngle->next()) { 4024431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return SK_NaN32; 403570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 404570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // if all angles have a computed winding, 405570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // or if no adjacent angles are orderable, 406570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // or if adjacent orderable angles have no computed winding, 407570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // there's nothing to do 408dac1d17027dcaa5596885a9f333979418b35001ccaryclark // if two orderable angles are adjacent, and both are next to orderable angles, 409dac1d17027dcaa5596885a9f333979418b35001ccaryclark // and one has winding computed, transfer to the other 41096fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpAngle* baseAngle = nullptr; 411570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool tryReverse = false; 412570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // look for counterclockwise transfers 413dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* angle = firstAngle->previous(); 414dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* next = angle->next(); 415dac1d17027dcaa5596885a9f333979418b35001ccaryclark firstAngle = next; 41607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 417dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* prior = angle; 418dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle = next; 419dac1d17027dcaa5596885a9f333979418b35001ccaryclark next = angle->next(); 420dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(prior->next() == angle); 421dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(angle->next() == next); 422dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 42396fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 4244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4254431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 42654359294a7c9dc54802d512a5d891a35c1663392caryclark int testWinding = angle->starter()->windSum(); 427dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (SK_MinS32 != testWinding) { 428dac1d17027dcaa5596885a9f333979418b35001ccaryclark baseAngle = angle; 4294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tryReverse = true; 4304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (baseAngle) { 4334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ComputeOneSum(baseAngle, angle, includeType); 43496fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 4354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 436dac1d17027dcaa5596885a9f333979418b35001ccaryclark } while (next != firstAngle); 43754359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) { 4384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org firstAngle = baseAngle; 4394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tryReverse = true; 4404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tryReverse) { 44296fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 443dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* prior = firstAngle; 444570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com do { 445dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle = prior; 446dac1d17027dcaa5596885a9f333979418b35001ccaryclark prior = angle->previous(); 447dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(prior->next() == angle); 448dac1d17027dcaa5596885a9f333979418b35001ccaryclark next = angle->next(); 449dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 45096fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 451dac1d17027dcaa5596885a9f333979418b35001ccaryclark continue; 452dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 45354359294a7c9dc54802d512a5d891a35c1663392caryclark int testWinding = angle->starter()->windSum(); 4544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SK_MinS32 != testWinding) { 4554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org baseAngle = angle; 456570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com continue; 45707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 458570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (baseAngle) { 4594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ComputeOneSumReverse(baseAngle, angle, includeType); 46096fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 461570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 462dac1d17027dcaa5596885a9f333979418b35001ccaryclark } while (prior != firstAngle); 463570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 46454359294a7c9dc54802d512a5d891a35c1663392caryclark return start->starter(end)->windSum(); 46507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 46607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 46755888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpSegment::contains(double newT) const { 46855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* spanBase = &fHead; 46955888e44171ffd48b591d19256884a969fe4da17caryclark do { 47055888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase->ptT()->contains(this, newT)) { 47155888e44171ffd48b591d19256884a969fe4da17caryclark return true; 47255888e44171ffd48b591d19256884a969fe4da17caryclark } 47355888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase == &fTail) { 47455888e44171ffd48b591d19256884a969fe4da17caryclark break; 47555888e44171ffd48b591d19256884a969fe4da17caryclark } 47655888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = spanBase->upCast()->next(); 47755888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 47855888e44171ffd48b591d19256884a969fe4da17caryclark return false; 47955888e44171ffd48b591d19256884a969fe4da17caryclark} 48055888e44171ffd48b591d19256884a969fe4da17caryclark 48118300a3aa7cb6eb55d21bb0450dffa58b6fc062cmtkleinvoid SkOpSegment::release(const SkOpSpan* span) { 48254359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 48308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark --fDoneCount; 484ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 48508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark --fCount; 4861597628fa38d24f23ad505bfb40e70e7c8617457caryclark SkOPASSERT(fCount >= fDoneCount); 4870dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed} 4880dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed 489e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark#if DEBUG_ANGLE 490e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark// called only by debugCheckNearCoincidence 49126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclarkdouble SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const { 49254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint testPt = this->dPtAtT(t); 49354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine testPerp = {{ testPt, testPt }}; 49454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector slope = this->dSlopeAtT(t); 49554359294a7c9dc54802d512a5d891a35c1663392caryclark testPerp[1].fX += slope.fY; 49654359294a7c9dc54802d512a5d891a35c1663392caryclark testPerp[1].fY -= slope.fX; 49754359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 49826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark const SkOpSegment* oppSegment = oppAngle->segment(); 4991049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); 50054359294a7c9dc54802d512a5d891a35c1663392caryclark double closestDistSq = SK_ScalarInfinity; 50154359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < i.used(); ++index) { 50254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { 50354359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 5040dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 50554359294a7c9dc54802d512a5d891a35c1663392caryclark double testDistSq = testPt.distanceSquared(i.pt(index)); 50654359294a7c9dc54802d512a5d891a35c1663392caryclark if (closestDistSq > testDistSq) { 50754359294a7c9dc54802d512a5d891a35c1663392caryclark closestDistSq = testDistSq; 5080dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 50954359294a7c9dc54802d512a5d891a35c1663392caryclark } 51054359294a7c9dc54802d512a5d891a35c1663392caryclark return closestDistSq; 5114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 512e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark#endif 5134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 51407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 51507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com The M and S variable name parts stand for the operators. 51607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Mi stands for Minuend (see wiki subtraction, analogous to difference) 51707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Su stands for Subtrahend 51807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com The Opp variable name part designates that the value is for the Opposite operator. 51907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Opposite values result from combining coincident spans. 52007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 52154359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 52254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) { 52354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 52454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 52554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 52654359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 52754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 52854359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 52907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // mark the smaller of startIndex, endIndex done, and all adjacent 53007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // spans with the same T value (but not 'other' spans) 53107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 53207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 53307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 53454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 53554359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 53696fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 537cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 53854359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 53954359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 54007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 54107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 54254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 54354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 54454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 54554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 54654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 5474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // more than one viable candidate -- measure angles to find best 54854359294a7c9dc54802d512a5d891a35c1663392caryclark int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp); 549570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool sortable = calcWinding != SK_NaN32; 5504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!sortable) { 5517eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com *unsortable = true; 55254359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 55396fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 5547eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 55554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 5564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle->unorderable()) { 55707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *unsortable = true; 55854359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 55996fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 56007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 5624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 5634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 56407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 56554359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = updateWinding(end, start); 5668cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (sumMiWinding == SK_MinS32) { 5678cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org *unsortable = true; 56854359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 56996fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 5708cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 57154359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding = updateOppWinding(end, start); 57207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 57307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap<int>(sumMiWinding, sumSuWinding); 57407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 57696fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 57707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 57807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // iterate through the angle, and compute everyone's winding 57907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 58007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 58107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 58207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 58307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), 5844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nextAngle->end(), op, &sumMiWinding, &sumSuWinding); 58507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (activeAngle) { 58607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 58707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 58807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 589570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com foundDone = nextSegment->done(nextAngle); 59007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 59107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 59207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (nextSegment->done()) { 59307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 59407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 595570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!activeAngle) { 59654359294a7c9dc54802d512a5d891a35c1663392caryclark (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 597570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 59854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = nextAngle->lastMarked(); 59907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (last) { 6004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 60107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *chase->append() = last; 60207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 60354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 60454359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 60554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 60654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum=%d", last->upCast()->windSum()); 60754359294a7c9dc54802d512a5d891a35c1663392caryclark } 60854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 60907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 61007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while ((nextAngle = nextAngle->next()) != angle); 61254359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 61307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 61496fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 61507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 61607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 61707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 61807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 61907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 62007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 62107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 62207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 62307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 62407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 62507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 62654359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase, 62754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { 62854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 62954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 63054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 63154359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 63254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 63354359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 63407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // mark the smaller of startIndex, endIndex done, and all adjacent 63507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // spans with the same T value (but not 'other' spans) 63607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 63707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 63807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 63954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 64054359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 64196fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 642570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 64354359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 64454359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 64507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 64607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 64754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 64854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 64954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 65054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 65154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 6524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // more than one viable candidate -- measure angles to find best 65354359294a7c9dc54802d512a5d891a35c1663392caryclark int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding); 654570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool sortable = calcWinding != SK_NaN32; 65507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!sortable) { 65607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *unsortable = true; 65754359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 65896fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 65954359294a7c9dc54802d512a5d891a35c1663392caryclark } 66054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 66154359294a7c9dc54802d512a5d891a35c1663392caryclark if (angle->unorderable()) { 66254359294a7c9dc54802d512a5d891a35c1663392caryclark *unsortable = true; 66354359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 66496fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 66507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 6674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 6684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 66907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 67054359294a7c9dc54802d512a5d891a35c1663392caryclark int sumWinding = updateWinding(end, start); 6714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 67296fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 67307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 67454359294a7c9dc54802d512a5d891a35c1663392caryclark // iterate through the angle, and compute everyone's winding 67507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 67607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 67707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 67807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 67907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), 6804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org &sumWinding); 68107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (activeAngle) { 68207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 68307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 68407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 68507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundDone = nextSegment->done(nextAngle); 68607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 68707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 68807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (nextSegment->done()) { 68907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 69007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 691570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!activeAngle) { 69254359294a7c9dc54802d512a5d891a35c1663392caryclark (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 693570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 69454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = nextAngle->lastMarked(); 69507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (last) { 6964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 69707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *chase->append() = last; 69807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 69954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 70054359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 70154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 70254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum=%d", last->upCast()->windSum()); 70354359294a7c9dc54802d512a5d891a35c1663392caryclark } 70454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 70507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 70607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while ((nextAngle = nextAngle->next()) != angle); 70854359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 70907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 71096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 71107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 71207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 71307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 71407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 71507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 71607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 71707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 71807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 71907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 72007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 72107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 72254359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, 72354359294a7c9dc54802d512a5d891a35c1663392caryclark bool* unsortable) { 72454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 72554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 72654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 72754359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 72854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 72954359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 73054359294a7c9dc54802d512a5d891a35c1663392caryclark // mark the smaller of startIndex, endIndex done, and all adjacent 73154359294a7c9dc54802d512a5d891a35c1663392caryclark // spans with the same T value (but not 'other' spans) 73207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 73307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 73407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 73554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 73654359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 73796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 73807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 73954359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 74054359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 74107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 74207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 74354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \ 74454359294a7c9dc54802d512a5d891a35c1663392caryclark : (*nextStart)->prev()); 74554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 74654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 74754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 74854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 74954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 75027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!angle || angle->unorderable()) { 75154359294a7c9dc54802d512a5d891a35c1663392caryclark *unsortable = true; 75254359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 75396fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 75454359294a7c9dc54802d512a5d891a35c1663392caryclark } 7554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 7564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 7574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 758570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 7594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 76096fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 76107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 76254359294a7c9dc54802d512a5d891a35c1663392caryclark // iterate through the angle, and compute everyone's winding 76307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 76407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 76507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 76607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 76707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 76807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 76907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 7704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!(foundDone = nextSegment->done(nextAngle))) { 7714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 7724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 77307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nextAngle = nextAngle->next(); 7754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (nextAngle != angle); 77654359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 77707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 77896fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 77907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 78007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 78107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 78207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 78307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 78407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 78507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 78607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 78707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 78807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 78907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 79054359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpGlobalState* SkOpSegment::globalState() const { 79155888e44171ffd48b591d19256884a969fe4da17caryclark return contour()->globalState(); 79265f553182ab7069378ef863d30094d0327f178d0caryclark} 79365f553182ab7069378ef863d30094d0327f178d0caryclark 7941049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { 79554359294a7c9dc54802d512a5d891a35c1663392caryclark fContour = contour; 79696fcdcc219d2a0d3579719b84b28bede76efba64halcanary fNext = nullptr; 79707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fPts = pts; 7981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fWeight = weight; 79907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fVerb = verb; 80054359294a7c9dc54802d512a5d891a35c1663392caryclark fCount = 0; 80154359294a7c9dc54802d512a5d891a35c1663392caryclark fDoneCount = 0; 80254359294a7c9dc54802d512a5d891a35c1663392caryclark fVisited = false; 80354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* zeroSpan = &fHead; 80496fcdcc219d2a0d3579719b84b28bede76efba64halcanary zeroSpan->init(this, nullptr, 0, fPts[0]); 80554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oneSpan = &fTail; 80654359294a7c9dc54802d512a5d891a35c1663392caryclark zeroSpan->setNext(oneSpan); 80754359294a7c9dc54802d512a5d891a35c1663392caryclark oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); 8081049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fID = globalState()->nextSegmentID()); 80954359294a7c9dc54802d512a5d891a35c1663392caryclark} 81054359294a7c9dc54802d512a5d891a35c1663392caryclark 81154359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { 81254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint cPt = this->dPtAtT(t); 8131049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); 81454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 81554359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 8161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i); 81754359294a7c9dc54802d512a5d891a35c1663392caryclark int used = i.used(); 81854359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < used; ++index) { 81954359294a7c9dc54802d512a5d891a35c1663392caryclark if (cPt.roughlyEqual(i.pt(index))) { 8200dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed return true; 8210dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 82254359294a7c9dc54802d512a5d891a35c1663392caryclark } 823a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return false; 824a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com} 825a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 82654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::isXor() const { 82754359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->isXor(); 82807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 82907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 8305b5ddd73b4baf22752924bf20d097e96236c36f8caryclarkvoid SkOpSegment::markAllDone() { 8315b5ddd73b4baf22752924bf20d097e96236c36f8caryclark SkOpSpan* span = this->head(); 8325b5ddd73b4baf22752924bf20d097e96236c36f8caryclark do { 8335b5ddd73b4baf22752924bf20d097e96236c36f8caryclark this->markDone(span); 8345b5ddd73b4baf22752924bf20d097e96236c36f8caryclark } while ((span = span->next()->upCastable())); 8355b5ddd73b4baf22752924bf20d097e96236c36f8caryclark} 8365b5ddd73b4baf22752924bf20d097e96236c36f8caryclark 83754359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) { 83854359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 83954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* minSpan = start->starter(end); 84054359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(minSpan); 84196fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 84207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* other = this; 843918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark SkOpSpan* priorDone = nullptr; 844918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark SkOpSpan* lastDone = nullptr; 84554359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &minSpan, &last))) { 84607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (other->done()) { 847dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 848dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 84907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 850918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark if (lastDone == minSpan || priorDone == minSpan) { 851918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark return nullptr; 852918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark } 85354359294a7c9dc54802d512a5d891a35c1663392caryclark other->markDone(minSpan); 854918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark priorDone = lastDone; 855918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark lastDone = minSpan; 85607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 85707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 85807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 85907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 86054359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 86154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** lastPtr) { 86254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* spanStart = start->starter(end); 86354359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 86454359294a7c9dc54802d512a5d891a35c1663392caryclark bool success = markWinding(spanStart, winding); 86596fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 8664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpSegment* other = this; 86754359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 86854359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart->windSum() != SK_MinS32) { 869b36a3cd137e2b6c328854015018594bb9967e493caryclark// SkASSERT(spanStart->windSum() == winding); // FIXME: is this assert too aggressive? 870dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 871dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 8724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 87354359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, winding); 8746f726addf3178b01949bb389ef83cf14a1d7b6b2caryclark } 87565f553182ab7069378ef863d30094d0327f178d0caryclark if (lastPtr) { 87665f553182ab7069378ef863d30094d0327f178d0caryclark *lastPtr = last; 87765f553182ab7069378ef863d30094d0327f178d0caryclark } 87865f553182ab7069378ef863d30094d0327f178d0caryclark return success; 8794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 8804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 88154359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, 88254359294a7c9dc54802d512a5d891a35c1663392caryclark int winding, int oppWinding, SkOpSpanBase** lastPtr) { 88354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* spanStart = start->starter(end); 88454359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 88554359294a7c9dc54802d512a5d891a35c1663392caryclark bool success = markWinding(spanStart, winding, oppWinding); 88696fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 88707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* other = this; 88854359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 88954359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart->windSum() != SK_MinS32) { 89054359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand() == other->operand()) { 891624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { 89254359294a7c9dc54802d512a5d891a35c1663392caryclark this->globalState()->setWindingFailed(); 89354359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 894dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 89554359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 89654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->windSum() == oppWinding); 89754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->oppSum() == winding); 898dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 899dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 900dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 901dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 90254359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand() == other->operand()) { 90354359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, winding, oppWinding); 904dac1d17027dcaa5596885a9f333979418b35001ccaryclark } else { 90554359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, oppWinding, winding); 90607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 90707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 90865f553182ab7069378ef863d30094d0327f178d0caryclark if (lastPtr) { 90965f553182ab7069378ef863d30094d0327f178d0caryclark *lastPtr = last; 91065f553182ab7069378ef863d30094d0327f178d0caryclark } 91165f553182ab7069378ef863d30094d0327f178d0caryclark return success; 91207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 91307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 91454359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) { 91507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(angle->segment() == this); 91607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (UseInnerWinding(maxWinding, sumWinding)) { 91707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com maxWinding = sumWinding; 91807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 91954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 92054359294a7c9dc54802d512a5d891a35c1663392caryclark (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last); 921570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_WINDING 922570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (last) { 92354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s last seg=%d span=%d", __FUNCTION__, 92454359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 92554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 92654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum="); 92754359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 92854359294a7c9dc54802d512a5d891a35c1663392caryclark } 92954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 930570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 931570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 93207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 93307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 93407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 93554359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, 93654359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSumWinding, const SkOpAngle* angle) { 93707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(angle->segment() == this); 93807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (UseInnerWinding(maxWinding, sumWinding)) { 93907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com maxWinding = sumWinding; 94007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 94107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { 94207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com oppMaxWinding = oppSumWinding; 94307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 94496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 94565f553182ab7069378ef863d30094d0327f178d0caryclark // caller doesn't require that this marks anything 94654359294a7c9dc54802d512a5d891a35c1663392caryclark (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last); 947570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_WINDING 948570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (last) { 94954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s last segment=%d span=%d", __FUNCTION__, 95054359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 95154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 95254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum="); 95354359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 95454359294a7c9dc54802d512a5d891a35c1663392caryclark } 95554359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" \n"); 956570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 957570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 95807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 95907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 96007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 96154359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::markDone(SkOpSpan* span) { 96254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 96354359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 9640dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed return; 9650dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 96654359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_MARK_DONE 96754359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum()); 96854359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 96954359294a7c9dc54802d512a5d891a35c1663392caryclark span->setDone(true); 97054359294a7c9dc54802d512a5d891a35c1663392caryclark ++fDoneCount; 97154359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 9720dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed} 9730dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed 97454359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markWinding(SkOpSpan* span, int winding) { 97554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 97654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(winding); 97754359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 97865f553182ab7069378ef863d30094d0327f178d0caryclark return false; 97907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 98007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_MARK_DONE 98154359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, winding); 9820dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed#endif 98354359294a7c9dc54802d512a5d891a35c1663392caryclark span->setWindSum(winding); 98454359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 98565f553182ab7069378ef863d30094d0327f178d0caryclark return true; 98607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 98707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 98854359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { 98954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 99054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(winding || oppWinding); 99154359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 99265f553182ab7069378ef863d30094d0327f178d0caryclark return false; 99307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 99407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_MARK_DONE 99554359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, winding, oppWinding); 9968cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org#endif 99754359294a7c9dc54802d512a5d891a35c1663392caryclark span->setWindSum(winding); 99854359294a7c9dc54802d512a5d891a35c1663392caryclark span->setOppSum(oppWinding); 9994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org debugValidate(); 100065f553182ab7069378ef863d30094d0327f178d0caryclark return true; 100107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 100207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 100354359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, 1004ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark const SkPoint& testPt) const { 100555888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(this == base->segment()); 100655888e44171ffd48b591d19256884a969fe4da17caryclark if (this == testParent) { 100755888e44171ffd48b591d19256884a969fe4da17caryclark if (precisely_equal(base->fT, testT)) { 100855888e44171ffd48b591d19256884a969fe4da17caryclark return true; 100955888e44171ffd48b591d19256884a969fe4da17caryclark } 101007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 101154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { 101254359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 1013e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 101455888e44171ffd48b591d19256884a969fe4da17caryclark return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); 101554359294a7c9dc54802d512a5d891a35c1663392caryclark} 101654359294a7c9dc54802d512a5d891a35c1663392caryclark 101754359294a7c9dc54802d512a5d891a35c1663392caryclarkstatic SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { 101854359294a7c9dc54802d512a5d891a35c1663392caryclark if (last) { 101954359294a7c9dc54802d512a5d891a35c1663392caryclark *last = endSpan; 102007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 102196fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 102207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 102307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 102454359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, 102554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** last) const { 102654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* origStart = *startPtr; 1027dac1d17027dcaa5596885a9f333979418b35001ccaryclark int step = *stepPtr; 102854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev(); 102954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endSpan); 103054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle(); 103154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* foundSpan; 103254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* otherEnd; 1033dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpSegment* other; 103496fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (angle == nullptr) { 103554359294a7c9dc54802d512a5d891a35c1663392caryclark if (endSpan->t() != 0 && endSpan->t() != 1) { 103696fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 1037dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 103854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* otherPtT = endSpan->ptT()->next(); 103954359294a7c9dc54802d512a5d891a35c1663392caryclark other = otherPtT->segment(); 104054359294a7c9dc54802d512a5d891a35c1663392caryclark foundSpan = otherPtT->span(); 1041343382e3acc8369f7bd4328e7c807255b5776fe5caryclark otherEnd = step > 0 1042343382e3acc8369f7bd4328e7c807255b5776fe5caryclark ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr 1043343382e3acc8369f7bd4328e7c807255b5776fe5caryclark : foundSpan->prev(); 1044dac1d17027dcaa5596885a9f333979418b35001ccaryclark } else { 1045dac1d17027dcaa5596885a9f333979418b35001ccaryclark int loopCount = angle->loopCount(); 1046dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (loopCount > 2) { 104754359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 1048dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 1049dac1d17027dcaa5596885a9f333979418b35001ccaryclark const SkOpAngle* next = angle->next(); 105096fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == next) { 105196fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 105265b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark } 1053dac1d17027dcaa5596885a9f333979418b35001ccaryclark#if DEBUG_WINDING 1054624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() 105554359294a7c9dc54802d512a5d891a35c1663392caryclark && !next->segment()->contour()->isXor()) { 1056dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDebugf("%s mismatched signs\n", __FUNCTION__); 10570dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 105854359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 1059dac1d17027dcaa5596885a9f333979418b35001ccaryclark other = next->segment(); 106054359294a7c9dc54802d512a5d891a35c1663392caryclark foundSpan = endSpan = next->start(); 1061dac1d17027dcaa5596885a9f333979418b35001ccaryclark otherEnd = next->end(); 1062570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 1063343382e3acc8369f7bd4328e7c807255b5776fe5caryclark if (!otherEnd) { 1064343382e3acc8369f7bd4328e7c807255b5776fe5caryclark return nullptr; 1065343382e3acc8369f7bd4328e7c807255b5776fe5caryclark } 106654359294a7c9dc54802d512a5d891a35c1663392caryclark int foundStep = foundSpan->step(otherEnd); 1067dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (*stepPtr != foundStep) { 106854359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 106907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 107054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(*startPtr); 107165b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark// SkASSERT(otherEnd >= 0); 107254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast(); 107354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* foundMin = foundSpan->starter(otherEnd); 107454359294a7c9dc54802d512a5d891a35c1663392caryclark if (foundMin->windValue() != origMin->windValue() 107554359294a7c9dc54802d512a5d891a35c1663392caryclark || foundMin->oppValue() != origMin->oppValue()) { 107654359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 1077dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 107854359294a7c9dc54802d512a5d891a35c1663392caryclark *startPtr = foundSpan; 1079dac1d17027dcaa5596885a9f333979418b35001ccaryclark *stepPtr = foundStep; 1080dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (minPtr) { 1081dac1d17027dcaa5596885a9f333979418b35001ccaryclark *minPtr = foundMin; 1082a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 108307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 108407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 108507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 108655888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with DebugClearVisited() 108755888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::ClearVisited(SkOpSpanBase* span) { 108854359294a7c9dc54802d512a5d891a35c1663392caryclark // reset visited flag back to false 108954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 109054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 109154359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != stopPtT) { 109254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* opp = ptT->segment(); 109354359294a7c9dc54802d512a5d891a35c1663392caryclark opp->resetVisited(); 109407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1095bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } while (!span->final() && (span = span->upCast()->next())); 109607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 109707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 109855888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugMissingCoincidence() 109954359294a7c9dc54802d512a5d891a35c1663392caryclark// look for pairs of undetected coincident curves 110054359294a7c9dc54802d512a5d891a35c1663392caryclark// assumes that segments going in have visited flag clear 110155888e44171ffd48b591d19256884a969fe4da17caryclark// Even though pairs of curves correct detect coincident runs, a run may be missed 110255888e44171ffd48b591d19256884a969fe4da17caryclark// if the coincidence is a product of multiple intersections. For instance, given 110355888e44171ffd48b591d19256884a969fe4da17caryclark// curves A, B, and C: 110455888e44171ffd48b591d19256884a969fe4da17caryclark// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near 110555888e44171ffd48b591d19256884a969fe4da17caryclark// the end of C that the intersection is replaced with the end of C. 110655888e44171ffd48b591d19256884a969fe4da17caryclark// Even though A-B correctly do not detect an intersection at point 2, 110755888e44171ffd48b591d19256884a969fe4da17caryclark// the resulting run from point 1 to point 2 is coincident on A and B. 110855888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpSegment::missingCoincidence() { 1109bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (this->done()) { 111027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return false; 1111bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 111296fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpan* prior = nullptr; 1113bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase* spanBase = &fHead; 111455888e44171ffd48b591d19256884a969fe4da17caryclark bool result = false; 111554359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1116bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; 1117c6d855f7f3d548c52f450299dc6975820cda3387caryclark SkOPASSERT(ptT->span() == spanBase); 111854359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != spanStopPtT) { 1119182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (ptT->deleted()) { 1120182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1121182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 112254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* opp = ptT->span()->segment(); 1123bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (opp->done()) { 112454359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 112554359294a7c9dc54802d512a5d891a35c1663392caryclark } 1126bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence 1127bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (!opp->visited()) { 112854359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 112954359294a7c9dc54802d512a5d891a35c1663392caryclark } 1130bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (spanBase == &fHead) { 113154359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 1132bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 113355888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->segment() == this) { 113455888e44171ffd48b591d19256884a969fe4da17caryclark continue; 113555888e44171ffd48b591d19256884a969fe4da17caryclark } 1136bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* span = spanBase->upCastable(); 1137bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // FIXME?: this assumes that if the opposite segment is coincident then no more 1138bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // coincidence needs to be detected. This may not be true. 113955888e44171ffd48b591d19256884a969fe4da17caryclark if (span && span->containsCoincidence(opp)) { 114026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark continue; 114126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 1142bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (spanBase->containsCoinEnd(opp)) { 1143bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 114455888e44171ffd48b591d19256884a969fe4da17caryclark } 114596fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpPtT* priorPtT = nullptr, * priorStopPtT; 114654359294a7c9dc54802d512a5d891a35c1663392caryclark // find prior span containing opp segment 114796fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSegment* priorOpp = nullptr; 1148bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* priorTest = spanBase->prev(); 1149bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark while (!priorOpp && priorTest) { 1150bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark priorStopPtT = priorPtT = priorTest->ptT(); 115154359294a7c9dc54802d512a5d891a35c1663392caryclark while ((priorPtT = priorPtT->next()) != priorStopPtT) { 1152182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (priorPtT->deleted()) { 1153182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1154182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 115554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = priorPtT->span()->segment(); 115654359294a7c9dc54802d512a5d891a35c1663392caryclark if (segment == opp) { 1157bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark prior = priorTest; 115854359294a7c9dc54802d512a5d891a35c1663392caryclark priorOpp = opp; 115954359294a7c9dc54802d512a5d891a35c1663392caryclark break; 116054359294a7c9dc54802d512a5d891a35c1663392caryclark } 116154359294a7c9dc54802d512a5d891a35c1663392caryclark } 1162bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark priorTest = priorTest->prev(); 116354359294a7c9dc54802d512a5d891a35c1663392caryclark } 116454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!priorOpp) { 116554359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 116654359294a7c9dc54802d512a5d891a35c1663392caryclark } 116726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (priorPtT == ptT) { 116826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark continue; 116926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 117054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* oppStart = prior->ptT(); 1171bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpPtT* oppEnd = spanBase->ptT(); 117254359294a7c9dc54802d512a5d891a35c1663392caryclark bool swapped = priorPtT->fT > ptT->fT; 117354359294a7c9dc54802d512a5d891a35c1663392caryclark if (swapped) { 117454359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(priorPtT, ptT); 117554359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppStart, oppEnd); 117654359294a7c9dc54802d512a5d891a35c1663392caryclark } 117755888e44171ffd48b591d19256884a969fe4da17caryclark SkOpCoincidence* coincidences = this->globalState()->coincidence(); 117855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootPriorPtT = priorPtT->span()->ptT(); 117955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootPtT = ptT->span()->ptT(); 118055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootOppStart = oppStart->span()->ptT(); 118155888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootOppEnd = oppEnd->span()->ptT(); 118255888e44171ffd48b591d19256884a969fe4da17caryclark if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 118354359294a7c9dc54802d512a5d891a35c1663392caryclark goto swapBack; 118454359294a7c9dc54802d512a5d891a35c1663392caryclark } 118555888e44171ffd48b591d19256884a969fe4da17caryclark if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) { 118654359294a7c9dc54802d512a5d891a35c1663392caryclark // mark coincidence 118755888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 118855888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__, 118955888e44171ffd48b591d19256884a969fe4da17caryclark rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(), 119055888e44171ffd48b591d19256884a969fe4da17caryclark rootOppEnd->debugID()); 119155888e44171ffd48b591d19256884a969fe4da17caryclark#endif 119255888e44171ffd48b591d19256884a969fe4da17caryclark if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 119355888e44171ffd48b591d19256884a969fe4da17caryclark coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd); 1194bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 119555888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 119655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)); 119755888e44171ffd48b591d19256884a969fe4da17caryclark#endif 119855888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 119954359294a7c9dc54802d512a5d891a35c1663392caryclark } 120054359294a7c9dc54802d512a5d891a35c1663392caryclark swapBack: 120154359294a7c9dc54802d512a5d891a35c1663392caryclark if (swapped) { 120254359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(priorPtT, ptT); 120354359294a7c9dc54802d512a5d891a35c1663392caryclark } 12040dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 120596fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); 120655888e44171ffd48b591d19256884a969fe4da17caryclark ClearVisited(&fHead); 120755888e44171ffd48b591d19256884a969fe4da17caryclark return result; 120854359294a7c9dc54802d512a5d891a35c1663392caryclark} 120954359294a7c9dc54802d512a5d891a35c1663392caryclark 121055888e44171ffd48b591d19256884a969fe4da17caryclark// please keep this in sync with debugMoveMultiples() 121108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark// if a span has more than one intersection, merge the other segments' span as needed 1212d78c088b6136590371fddd4cab67bfb4bf692fd3caryclarkbool SkOpSegment::moveMultiples() { 121308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark debugValidate(); 121408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* test = &fHead; 121508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 121608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark int addCount = test->spanAddsCount(); 12177eb01e00b1a1f7c649e1e78eb3f4644033ce94eeCary Clark// FAIL_IF(addCount < 1); 12187eb01e00b1a1f7c649e1e78eb3f4644033ce94eeCary Clark if (addCount <= 1) { 121908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 122008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 122108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* startPtT = test->ptT(); 122208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* testPtT = startPtT; 122308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { // iterate through all spans associated with start 122408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppSpan = testPtT->span(); 122508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSpan->spanAddsCount() == addCount) { 122608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 122708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 122808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSpan->deleted()) { 122908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 123008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 123108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSegment* oppSegment = oppSpan->segment(); 123208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSegment == this) { 123308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 123408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 123508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // find range of spans to consider merging 123608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppPrev = oppSpan; 123708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppFirst = oppSpan; 123808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppPrev = oppPrev->prev())) { 123908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (!roughly_equal(oppPrev->t(), oppSpan->t())) { 124008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark break; 124108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPrev->spanAddsCount() == addCount) { 124308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 124408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPrev->deleted()) { 124608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 124708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppFirst = oppPrev; 124908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppNext = oppSpan; 125108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppLast = oppSpan; 125296fcdcc219d2a0d3579719b84b28bede76efba64halcanary while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { 125308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (!roughly_equal(oppNext->t(), oppSpan->t())) { 125408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark break; 125508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppNext->spanAddsCount() == addCount) { 125708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 125808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppNext->deleted()) { 126008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 126108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppLast = oppNext; 126308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppFirst == oppLast) { 126508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 126608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppTest = oppFirst; 126808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 126908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppTest == oppSpan) { 127008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 127108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 127208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // check to see if the candidate meets specific criteria: 127308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // it contains spans of segments in test's loop but not including 'this' 127408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* oppStartPtT = oppTest->ptT(); 127508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* oppPtT = oppStartPtT; 127608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppPtT = oppPtT->next()) != oppStartPtT) { 127708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSegment* oppPtTSegment = oppPtT->segment(); 127808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPtTSegment == this) { 127908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto tryNextSpan; 128008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 128108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* matchPtT = startPtT; 128208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 128308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (matchPtT->segment() == oppPtTSegment) { 128408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto foundMatch; 128508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 128608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((matchPtT = matchPtT->next()) != startPtT); 128708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto tryNextSpan; 128808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark foundMatch: // merge oppTest and oppSpan 128908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSegment->debugValidate(); 129030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppTest->mergeMatches(oppSpan); 129130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppTest->addOpp(oppSpan); 129208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSegment->debugValidate(); 129308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto checkNextSpan; 129408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 129555888e44171ffd48b591d19256884a969fe4da17caryclark tryNextSpan: 129608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ; 129708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); 129808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((testPtT = testPtT->next()) != startPtT); 129955888e44171ffd48b591d19256884a969fe4da17caryclarkcheckNextSpan: 130008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ; 130196fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while ((test = test->final() ? nullptr : test->upCast()->next())); 130208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark debugValidate(); 1303d78c088b6136590371fddd4cab67bfb4bf692fd3caryclark return true; 130408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark} 130508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark 130655888e44171ffd48b591d19256884a969fe4da17caryclark// adjacent spans may have points close by 130728da2837040cd116dd2d854dd3268723ca219f11Cary Clarkbool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan, 130828da2837040cd116dd2d854dd3268723ca219f11Cary Clark bool* found) const { 130955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* refHead = refSpan->ptT(); 131055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* checkHead = checkSpan->ptT(); 131155888e44171ffd48b591d19256884a969fe4da17caryclark// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart 131230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) { 131355888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 131455888e44171ffd48b591d19256884a969fe4da17caryclark // verify that no combination of points are close 131555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* dBugRef = refHead; 131655888e44171ffd48b591d19256884a969fe4da17caryclark do { 131755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* dBugCheck = checkHead; 131855888e44171ffd48b591d19256884a969fe4da17caryclark do { 131930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt)); 132055888e44171ffd48b591d19256884a969fe4da17caryclark dBugCheck = dBugCheck->next(); 132155888e44171ffd48b591d19256884a969fe4da17caryclark } while (dBugCheck != checkHead); 132255888e44171ffd48b591d19256884a969fe4da17caryclark dBugRef = dBugRef->next(); 132355888e44171ffd48b591d19256884a969fe4da17caryclark } while (dBugRef != refHead); 132455888e44171ffd48b591d19256884a969fe4da17caryclark#endif 132528da2837040cd116dd2d854dd3268723ca219f11Cary Clark *found = false; 132628da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 132755888e44171ffd48b591d19256884a969fe4da17caryclark } 132855888e44171ffd48b591d19256884a969fe4da17caryclark // check only unique points 132955888e44171ffd48b591d19256884a969fe4da17caryclark SkScalar distSqBest = SK_ScalarMax; 133055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* refBest = nullptr; 133155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* checkBest = nullptr; 133255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ref = refHead; 133355888e44171ffd48b591d19256884a969fe4da17caryclark do { 133455888e44171ffd48b591d19256884a969fe4da17caryclark if (ref->deleted()) { 133555888e44171ffd48b591d19256884a969fe4da17caryclark continue; 133655888e44171ffd48b591d19256884a969fe4da17caryclark } 133755888e44171ffd48b591d19256884a969fe4da17caryclark while (ref->ptAlreadySeen(refHead)) { 133855888e44171ffd48b591d19256884a969fe4da17caryclark ref = ref->next(); 133955888e44171ffd48b591d19256884a969fe4da17caryclark if (ref == refHead) { 134055888e44171ffd48b591d19256884a969fe4da17caryclark goto doneCheckingDistance; 134155888e44171ffd48b591d19256884a969fe4da17caryclark } 134255888e44171ffd48b591d19256884a969fe4da17caryclark } 134355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* check = checkHead; 134455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* refSeg = ref->segment(); 134528da2837040cd116dd2d854dd3268723ca219f11Cary Clark int escapeHatch = 100000; // defend against infinite loops 134655888e44171ffd48b591d19256884a969fe4da17caryclark do { 134755888e44171ffd48b591d19256884a969fe4da17caryclark if (check->deleted()) { 134855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 134955888e44171ffd48b591d19256884a969fe4da17caryclark } 135055888e44171ffd48b591d19256884a969fe4da17caryclark while (check->ptAlreadySeen(checkHead)) { 135155888e44171ffd48b591d19256884a969fe4da17caryclark check = check->next(); 135255888e44171ffd48b591d19256884a969fe4da17caryclark if (check == checkHead) { 135355888e44171ffd48b591d19256884a969fe4da17caryclark goto nextRef; 135455888e44171ffd48b591d19256884a969fe4da17caryclark } 135555888e44171ffd48b591d19256884a969fe4da17caryclark } 135655888e44171ffd48b591d19256884a969fe4da17caryclark SkScalar distSq = ref->fPt.distanceToSqd(check->fPt); 135755888e44171ffd48b591d19256884a969fe4da17caryclark if (distSqBest > distSq && (refSeg != check->segment() 135855888e44171ffd48b591d19256884a969fe4da17caryclark || !refSeg->ptsDisjoint(*ref, *check))) { 135955888e44171ffd48b591d19256884a969fe4da17caryclark distSqBest = distSq; 136055888e44171ffd48b591d19256884a969fe4da17caryclark refBest = ref; 136155888e44171ffd48b591d19256884a969fe4da17caryclark checkBest = check; 136255888e44171ffd48b591d19256884a969fe4da17caryclark } 136328da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (--escapeHatch <= 0) { 136428da2837040cd116dd2d854dd3268723ca219f11Cary Clark return false; 136528da2837040cd116dd2d854dd3268723ca219f11Cary Clark } 136655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((check = check->next()) != checkHead); 136728da2837040cd116dd2d854dd3268723ca219f11Cary Clark nextRef: 136855888e44171ffd48b591d19256884a969fe4da17caryclark ; 136955888e44171ffd48b591d19256884a969fe4da17caryclark } while ((ref = ref->next()) != refHead); 137055888e44171ffd48b591d19256884a969fe4da17caryclarkdoneCheckingDistance: 137128da2837040cd116dd2d854dd3268723ca219f11Cary Clark *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT, 1372ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark checkBest->fPt); 137328da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 137455888e44171ffd48b591d19256884a969fe4da17caryclark} 137555888e44171ffd48b591d19256884a969fe4da17caryclark 137655888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this function in sync with debugMoveNearby() 137754359294a7c9dc54802d512a5d891a35c1663392caryclark// Move nearby t values and pts so they all hang off the same span. Alignment happens later. 137828da2837040cd116dd2d854dd3268723ca219f11Cary Clarkbool SkOpSegment::moveNearby() { 137954359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 138055888e44171ffd48b591d19256884a969fe4da17caryclark // release undeleted spans pointing to this seg that are linked to the primary span 138155888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* spanBase = &fHead; 138254359294a7c9dc54802d512a5d891a35c1663392caryclark do { 138355888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* ptT = spanBase->ptT(); 138455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* headPtT = ptT; 138555888e44171ffd48b591d19256884a969fe4da17caryclark while ((ptT = ptT->next()) != headPtT) { 138655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* test = ptT->span(); 138755888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->segment() == this && !ptT->deleted() && test != spanBase 138855888e44171ffd48b591d19256884a969fe4da17caryclark && test->ptT() == ptT) { 138955888e44171ffd48b591d19256884a969fe4da17caryclark if (test->final()) { 139055888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase == &fHead) { 139155888e44171ffd48b591d19256884a969fe4da17caryclark this->clearAll(); 139228da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 139355888e44171ffd48b591d19256884a969fe4da17caryclark } 139455888e44171ffd48b591d19256884a969fe4da17caryclark spanBase->upCast()->release(ptT); 139555888e44171ffd48b591d19256884a969fe4da17caryclark } else if (test->prev()) { 139655888e44171ffd48b591d19256884a969fe4da17caryclark test->upCast()->release(headPtT); 139755888e44171ffd48b591d19256884a969fe4da17caryclark } 139855888e44171ffd48b591d19256884a969fe4da17caryclark break; 1399570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 140007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 140155888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = spanBase->upCast()->next(); 140255888e44171ffd48b591d19256884a969fe4da17caryclark } while (!spanBase->final()); 140355888e44171ffd48b591d19256884a969fe4da17caryclark 140455888e44171ffd48b591d19256884a969fe4da17caryclark // This loop looks for adjacent spans which are near by 140555888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = &fHead; 140655888e44171ffd48b591d19256884a969fe4da17caryclark do { // iterate through all spans associated with start 140755888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* test = spanBase->upCast()->next(); 140828da2837040cd116dd2d854dd3268723ca219f11Cary Clark bool found; 140928da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (!this->spansNearby(spanBase, test, &found)) { 141028da2837040cd116dd2d854dd3268723ca219f11Cary Clark return false; 141128da2837040cd116dd2d854dd3268723ca219f11Cary Clark } 141228da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (found) { 141355888e44171ffd48b591d19256884a969fe4da17caryclark if (test->final()) { 141455888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase->prev()) { 141555888e44171ffd48b591d19256884a969fe4da17caryclark test->merge(spanBase->upCast()); 141655888e44171ffd48b591d19256884a969fe4da17caryclark } else { 141755888e44171ffd48b591d19256884a969fe4da17caryclark this->clearAll(); 141828da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 141955888e44171ffd48b591d19256884a969fe4da17caryclark } 142055888e44171ffd48b591d19256884a969fe4da17caryclark } else { 142155888e44171ffd48b591d19256884a969fe4da17caryclark spanBase->merge(test->upCast()); 142255888e44171ffd48b591d19256884a969fe4da17caryclark } 142355888e44171ffd48b591d19256884a969fe4da17caryclark } 142455888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = test; 142555888e44171ffd48b591d19256884a969fe4da17caryclark } while (!spanBase->final()); 142654359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 142728da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 1428dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1429dac1d17027dcaa5596885a9f333979418b35001ccaryclark 143054359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::operand() const { 143154359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->operand(); 14325e27e0eb1d1d4c7674e221d3ba3314500ea0b97acaryclark} 14335e27e0eb1d1d4c7674e221d3ba3314500ea0b97acaryclark 143454359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::oppXor() const { 143554359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->oppXor(); 1436ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark} 1437ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark 143854359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { 143954359294a7c9dc54802d512a5d891a35c1663392caryclark if (fVerb == SkPath::kLine_Verb) { 144054359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 14410dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 144254359294a7c9dc54802d512a5d891a35c1663392caryclark // quads (and cubics) can loop back to nearly a line so that an opposite curve 144354359294a7c9dc54802d512a5d891a35c1663392caryclark // hits in two places with very different t values. 144454359294a7c9dc54802d512a5d891a35c1663392caryclark // OPTIMIZATION: curves could be preflighted so that, for example, something like 144554359294a7c9dc54802d512a5d891a35c1663392caryclark // 'controls contained by ends' could avoid this check for common curves 144654359294a7c9dc54802d512a5d891a35c1663392caryclark // 'ends are extremes in x or y' is cheaper to compute and real-world common 144754359294a7c9dc54802d512a5d891a35c1663392caryclark // on the other hand, the below check is relatively inexpensive 144854359294a7c9dc54802d512a5d891a35c1663392caryclark double midT = (t1 + t2) / 2; 144954359294a7c9dc54802d512a5d891a35c1663392caryclark SkPoint midPt = this->ptAtT(midT); 145054359294a7c9dc54802d512a5d891a35c1663392caryclark double seDistSq = SkTMax(pt1.distanceToSqd(pt2) * 2, FLT_EPSILON * 2); 145154359294a7c9dc54802d512a5d891a35c1663392caryclark return midPt.distanceToSqd(pt1) > seDistSq || midPt.distanceToSqd(pt2) > seDistSq; 145254359294a7c9dc54802d512a5d891a35c1663392caryclark} 145354359294a7c9dc54802d512a5d891a35c1663392caryclark 145454359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 145554359294a7c9dc54802d512a5d891a35c1663392caryclark int* maxWinding, int* sumWinding) { 145654359294a7c9dc54802d512a5d891a35c1663392caryclark int deltaSum = SpanSign(start, end); 145754359294a7c9dc54802d512a5d891a35c1663392caryclark *maxWinding = *sumMiWinding; 145854359294a7c9dc54802d512a5d891a35c1663392caryclark *sumWinding = *sumMiWinding -= deltaSum; 145960e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 1460dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1461dac1d17027dcaa5596885a9f333979418b35001ccaryclark 146254359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 146354359294a7c9dc54802d512a5d891a35c1663392caryclark int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, 146454359294a7c9dc54802d512a5d891a35c1663392caryclark int* oppSumWinding) { 146554359294a7c9dc54802d512a5d891a35c1663392caryclark int deltaSum = SpanSign(start, end); 146654359294a7c9dc54802d512a5d891a35c1663392caryclark int oppDeltaSum = OppSign(start, end); 146707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 146807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *maxWinding = *sumSuWinding; 146907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *sumWinding = *sumSuWinding -= deltaSum; 147007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppMaxWinding = *sumMiWinding; 147107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppSumWinding = *sumMiWinding -= oppDeltaSum; 147207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 147307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *maxWinding = *sumMiWinding; 147407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *sumWinding = *sumMiWinding -= deltaSum; 147507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppMaxWinding = *sumSuWinding; 147607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppSumWinding = *sumSuWinding -= oppDeltaSum; 147707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 147860e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 147960e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM); 148007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 148107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1482b36a3cd137e2b6c328854015018594bb9967e493caryclarkbool SkOpSegment::sortAngles() { 148354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* span = &this->fHead; 14844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 148554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* fromAngle = span->fromAngle(); 148696fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle(); 1487dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (!fromAngle && !toAngle) { 14884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 14894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1490cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#if DEBUG_ANGLE 14914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool wroteAfterHeader = false; 1492cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#endif 149354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* baseAngle = fromAngle; 149454359294a7c9dc54802d512a5d891a35c1663392caryclark if (fromAngle && toAngle) { 14954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 149654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(), 149754359294a7c9dc54802d512a5d891a35c1663392caryclark span->debugID()); 149854359294a7c9dc54802d512a5d891a35c1663392caryclark wroteAfterHeader = true; 14994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 1500b36a3cd137e2b6c328854015018594bb9967e493caryclark FAIL_IF(!fromAngle->insert(toAngle)); 150154359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (!fromAngle) { 150254359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle = toAngle; 150307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 150454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 15054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 150654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oSpan = ptT->span(); 150754359294a7c9dc54802d512a5d891a35c1663392caryclark if (oSpan == span) { 150854359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 150954359294a7c9dc54802d512a5d891a35c1663392caryclark } 151054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* oAngle = oSpan->fromAngle(); 1511dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (oAngle) { 1512570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_ANGLE 15134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!wroteAfterHeader) { 151454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 151554359294a7c9dc54802d512a5d891a35c1663392caryclark span->t(), span->debugID()); 15164431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org wroteAfterHeader = true; 15174431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1518570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 151954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oAngle->loopContains(baseAngle)) { 15208cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org baseAngle->insert(oAngle); 15218cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 15224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 152354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oSpan->final()) { 152454359294a7c9dc54802d512a5d891a35c1663392caryclark oAngle = oSpan->upCast()->toAngle(); 152554359294a7c9dc54802d512a5d891a35c1663392caryclark if (oAngle) { 15264431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 152754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!wroteAfterHeader) { 152854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 152954359294a7c9dc54802d512a5d891a35c1663392caryclark span->t(), span->debugID()); 153054359294a7c9dc54802d512a5d891a35c1663392caryclark wroteAfterHeader = true; 153154359294a7c9dc54802d512a5d891a35c1663392caryclark } 15324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 153354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oAngle->loopContains(baseAngle)) { 153454359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle->insert(oAngle); 153554359294a7c9dc54802d512a5d891a35c1663392caryclark } 15368cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 15374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 153854359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((ptT = ptT->next()) != stopPtT); 153954359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseAngle->loopCount() == 1) { 154096fcdcc219d2a0d3579719b84b28bede76efba64halcanary span->setFromAngle(nullptr); 154154359294a7c9dc54802d512a5d891a35c1663392caryclark if (toAngle) { 154296fcdcc219d2a0d3579719b84b28bede76efba64halcanary span->upCast()->setToAngle(nullptr); 15434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 154496fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 15454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 15464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 15474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!baseAngle || baseAngle->loopCount() > 1); 15484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 154954359294a7c9dc54802d512a5d891a35c1663392caryclark } while (!span->final() && (span = span->upCast()->next())); 1550b36a3cd137e2b6c328854015018594bb9967e493caryclark return true; 1551570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1552570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 155354359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 15541049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDCurve* edge) const { 1555cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(start != end); 155654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& startPtT = *start->ptT(); 155754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& endPtT = *end->ptT(); 15581049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(edge->fVerb = fVerb); 15591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[0].set(startPtT.fPt); 1560cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int points = SkPathOpsVerbToPoints(fVerb); 15611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[points].set(endPtT.fPt); 1562cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kLine_Verb) { 1563cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1564cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 156554359294a7c9dc54802d512a5d891a35c1663392caryclark double startT = startPtT.fT; 156654359294a7c9dc54802d512a5d891a35c1663392caryclark double endT = endPtT.fT; 1567cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1568cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // don't compute midpoints if we already have them 1569cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fLine[1].set(fPts[1]); 15711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return false; 15721049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (fVerb == SkPath::kConic_Verb) { 15741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic[1].set(fPts[1]); 15751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic.fWeight = fWeight; 1576cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1577cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1578cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 157954359294a7c9dc54802d512a5d891a35c1663392caryclark if (startT == 0) { 15801049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[1].set(fPts[1]); 15811049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[2].set(fPts[2]); 1582cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1583cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 15841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[1].set(fPts[2]); 15851049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[2].set(fPts[1]); 1586cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1587cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1588cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT); 15901049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (fVerb == SkPath::kConic_Verb) { 15911049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2], 15921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark startT, endT, &edge->fConic.fWeight); 1593cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } else { 1594cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 15951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]); 1596cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1597cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return true; 159807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 159907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 160027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclarkbool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, 160155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const { 160227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // average t, find mid pt 160327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark double midT = (prior->t() + spanBase->t()) / 2; 160427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkPoint midPt = this->ptAtT(midT); 160527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark bool coincident = true; 160627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // if the mid pt is not near either end pt, project perpendicular through opp seg 160727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) 160827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { 160955888e44171ffd48b591d19256884a969fe4da17caryclark if (priorPtT->span() == ptT->span()) { 161055888e44171ffd48b591d19256884a969fe4da17caryclark return false; 161155888e44171ffd48b591d19256884a969fe4da17caryclark } 161227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark coincident = false; 161327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkIntersections i; 161455888e44171ffd48b591d19256884a969fe4da17caryclark SkDCurve curvePart; 161555888e44171ffd48b591d19256884a969fe4da17caryclark this->subDivide(prior, spanBase, &curvePart); 161655888e44171ffd48b591d19256884a969fe4da17caryclark SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f); 161755888e44171ffd48b591d19256884a969fe4da17caryclark SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f); 161855888e44171ffd48b591d19256884a969fe4da17caryclark SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}}; 161955888e44171ffd48b591d19256884a969fe4da17caryclark SkDCurve oppPart; 162055888e44171ffd48b591d19256884a969fe4da17caryclark opp->subDivide(priorPtT->span(), ptT->span(), &oppPart); 162155888e44171ffd48b591d19256884a969fe4da17caryclark (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i); 162227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // measure distance and see if it's small enough to denote coincidence 162327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark for (int index = 0; index < i.used(); ++index) { 162455888e44171ffd48b591d19256884a969fe4da17caryclark if (!between(0, i[0][index], 1)) { 162555888e44171ffd48b591d19256884a969fe4da17caryclark continue; 162655888e44171ffd48b591d19256884a969fe4da17caryclark } 162727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkDPoint oppPt = i.pt(index); 162830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (oppPt.approximatelyDEqual(midPt)) { 162955888e44171ffd48b591d19256884a969fe4da17caryclark // the coincidence can occur at almost any angle 163055888e44171ffd48b591d19256884a969fe4da17caryclark coincident = true; 163127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return coincident; 163527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 163627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 1637ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary ClarkSkOpSpan* SkOpSegment::undoneSpan() { 1638ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark SkOpSpan* span = &fHead; 1639ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark SkOpSpanBase* next; 164054359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1641ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark next = span->next(); 164254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->done()) { 1643ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark return span; 164407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1645ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark } while (!next->final() && (span = next->upCast())); 1646ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark return nullptr; 164707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 164807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 164954359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { 165054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* lesser = start->starter(end); 165154359294a7c9dc54802d512a5d891a35c1663392caryclark int oppWinding = lesser->oppSum(); 165254359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSpanWinding = SkOpSegment::OppSign(start, end); 165307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) 165407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && oppWinding != SK_MaxS32) { 165507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com oppWinding -= oppSpanWinding; 165607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 165707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return oppWinding; 165807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 165907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 166007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { 166154359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* startSpan = angle->start(); 166254359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* endSpan = angle->end(); 166354359294a7c9dc54802d512a5d891a35c1663392caryclark return updateOppWinding(endSpan, startSpan); 166407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 166507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 166607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { 166754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* startSpan = angle->start(); 166854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* endSpan = angle->end(); 166954359294a7c9dc54802d512a5d891a35c1663392caryclark return updateOppWinding(startSpan, endSpan); 167007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 167107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1672624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 1673624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* lesser = start->starter(end); 167454359294a7c9dc54802d512a5d891a35c1663392caryclark int winding = lesser->windSum(); 16758cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (winding == SK_MinS32) { 1676bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark winding = lesser->computeWindSum(); 1677624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 1678624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (winding == SK_MinS32) { 16798cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return winding; 16808cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 168154359294a7c9dc54802d512a5d891a35c1663392caryclark int spanWinding = SkOpSegment::SpanSign(start, end); 1682570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (winding && UseInnerWinding(winding - spanWinding, winding) 1683570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com && winding != SK_MaxS32) { 168407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com winding -= spanWinding; 168507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 168607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return winding; 168707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 168807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1689624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWinding(SkOpAngle* angle) { 1690624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* startSpan = angle->start(); 1691624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* endSpan = angle->end(); 169254359294a7c9dc54802d512a5d891a35c1663392caryclark return updateWinding(endSpan, startSpan); 1693570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1694570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1695624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { 1696624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* startSpan = angle->start(); 1697624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* endSpan = angle->end(); 169854359294a7c9dc54802d512a5d891a35c1663392caryclark return updateWinding(startSpan, endSpan); 1699570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1700570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1701570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// OPTIMIZATION: does the following also work, and is it any faster? 1702570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// return outerWinding * innerWinding > 0 1703570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) 1704570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { 1705570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(outerWinding != SK_MaxS32); 1706570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(innerWinding != SK_MaxS32); 170760e0fee6d4acff638ccc9670c4055aced529a7a0bungeman int absOut = SkTAbs(outerWinding); 170860e0fee6d4acff638ccc9670c4055aced529a7a0bungeman int absIn = SkTAbs(innerWinding); 1709570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 1710570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return result; 1711570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1712570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 171307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::windSum(const SkOpAngle* angle) const { 171454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* minSpan = angle->start()->starter(angle->end()); 171554359294a7c9dc54802d512a5d891a35c1663392caryclark return minSpan->windSum(); 171607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 1717