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() 24773e597d0eddeaaa466101d5bb7da537c0066166aCary 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 27673e597d0eddeaaa466101d5bb7da537c0066166aCary ClarkSkOpPtT* SkOpSegment::addT(double t) { 27773e597d0eddeaaa466101d5bb7da537c0066166aCary Clark return addT(t, this->ptAtT(t)); 27873e597d0eddeaaa466101d5bb7da537c0066166aCary Clark} 27973e597d0eddeaaa466101d5bb7da537c0066166aCary 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) { 289ecc364c42691f24b41a672de1636b3a5f181160aHerb Derby SkOpAngle* priorAngle = this->globalState()->allocator()->make<SkOpAngle>(); 29054359294a7c9dc54802d512a5d891a35c1663392caryclark priorAngle->set(spanBase, prior); 29154359294a7c9dc54802d512a5d891a35c1663392caryclark spanBase->setFromAngle(priorAngle); 292ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 29354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* span = spanBase->upCast(); 29454359294a7c9dc54802d512a5d891a35c1663392caryclark bool active = !span->isCanceled(); 29554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = span->next(); 29654359294a7c9dc54802d512a5d891a35c1663392caryclark if (active) { 297ecc364c42691f24b41a672de1636b3a5f181160aHerb Derby SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>(); 29854359294a7c9dc54802d512a5d891a35c1663392caryclark angle->set(span, next); 29954359294a7c9dc54802d512a5d891a35c1663392caryclark span->setToAngle(angle); 30054359294a7c9dc54802d512a5d891a35c1663392caryclark } 30154359294a7c9dc54802d512a5d891a35c1663392caryclark activePrior = active; 30254359294a7c9dc54802d512a5d891a35c1663392caryclark prior = span; 30354359294a7c9dc54802d512a5d891a35c1663392caryclark spanBase = next; 3044431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 30554359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior && !fTail.simple()) { 30655888e44171ffd48b591d19256884a969fe4da17caryclark addEndSpan(); 3074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 30865f553182ab7069378ef863d30094d0327f178d0caryclark} 30965f553182ab7069378ef863d30094d0327f178d0caryclark 31055888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugClearAll() 31155888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::clearAll() { 31255888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpan* span = &fHead; 31355888e44171ffd48b591d19256884a969fe4da17caryclark do { 31455888e44171ffd48b591d19256884a969fe4da17caryclark this->clearOne(span); 31555888e44171ffd48b591d19256884a969fe4da17caryclark } while ((span = span->next()->upCastable())); 31655888e44171ffd48b591d19256884a969fe4da17caryclark this->globalState()->coincidence()->release(this); 31755888e44171ffd48b591d19256884a969fe4da17caryclark} 31855888e44171ffd48b591d19256884a969fe4da17caryclark 31955888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugClearOne() 32055888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::clearOne(SkOpSpan* span) { 32155888e44171ffd48b591d19256884a969fe4da17caryclark span->setWindValue(0); 32255888e44171ffd48b591d19256884a969fe4da17caryclark span->setOppValue(0); 32355888e44171ffd48b591d19256884a969fe4da17caryclark this->markDone(span); 32455888e44171ffd48b591d19256884a969fe4da17caryclark} 32555888e44171ffd48b591d19256884a969fe4da17caryclark 32630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkbool SkOpSegment::collapsed(double s, double e) const { 32730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark const SkOpSpanBase* span = &fHead; 32830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark do { 32930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (span->collapsed(s, e)) { 33030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return true; 33130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 33230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } while (span->upCastable() && (span = span->upCast()->next())); 33330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return false; 33430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 33530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 33654359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 33754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 338624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* baseSegment = baseAngle->segment(); 33954359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); 34054359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding; 34154359294a7c9dc54802d512a5d891a35c1663392caryclark bool binary = includeType >= SkOpAngle::kBinarySingle; 34254359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 34354359294a7c9dc54802d512a5d891a35c1663392caryclark sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); 34454359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseSegment->operand()) { 34554359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap<int>(sumMiWinding, sumSuWinding); 3460dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 34754359294a7c9dc54802d512a5d891a35c1663392caryclark } 34854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* nextSegment = nextAngle->segment(); 34954359294a7c9dc54802d512a5d891a35c1663392caryclark int maxWinding, sumWinding; 35054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 35154359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 35254359294a7c9dc54802d512a5d891a35c1663392caryclark int oppMaxWinding, oppSumWinding; 35354359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 35454359294a7c9dc54802d512a5d891a35c1663392caryclark &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 35554359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 35654359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle); 3574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 35854359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 35954359294a7c9dc54802d512a5d891a35c1663392caryclark &maxWinding, &sumWinding); 36054359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 3614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 36254359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle->setLastMarked(last); 3634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 365624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkvoid SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, 36654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 367624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* baseSegment = baseAngle->segment(); 36854359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = baseSegment->updateWinding(baseAngle); 36954359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding; 37054359294a7c9dc54802d512a5d891a35c1663392caryclark bool binary = includeType >= SkOpAngle::kBinarySingle; 3710dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed if (binary) { 37254359294a7c9dc54802d512a5d891a35c1663392caryclark sumSuWinding = baseSegment->updateOppWinding(baseAngle); 37354359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseSegment->operand()) { 37454359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap<int>(sumMiWinding, sumSuWinding); 3750dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 3760dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 37754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* nextSegment = nextAngle->segment(); 37854359294a7c9dc54802d512a5d891a35c1663392caryclark int maxWinding, sumWinding; 37954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 38054359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 38154359294a7c9dc54802d512a5d891a35c1663392caryclark int oppMaxWinding, oppSumWinding; 38254359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 38354359294a7c9dc54802d512a5d891a35c1663392caryclark &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 38454359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 38554359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle); 3864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 38754359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 38854359294a7c9dc54802d512a5d891a35c1663392caryclark &maxWinding, &sumWinding); 38954359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 3900dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 39154359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle->setLastMarked(last); 3924431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 3934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 394dac1d17027dcaa5596885a9f333979418b35001ccaryclark// at this point, the span is already ordered, or unorderable 39554359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, 39654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 3974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(includeType != SkOpAngle::kUnaryXor); 39854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* firstAngle = this->spanToAngle(end, start); 39996fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == firstAngle || nullptr == firstAngle->next()) { 4004431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return SK_NaN32; 401570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 402570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // if all angles have a computed winding, 403570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // or if no adjacent angles are orderable, 404570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // or if adjacent orderable angles have no computed winding, 405570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // there's nothing to do 406dac1d17027dcaa5596885a9f333979418b35001ccaryclark // if two orderable angles are adjacent, and both are next to orderable angles, 407dac1d17027dcaa5596885a9f333979418b35001ccaryclark // and one has winding computed, transfer to the other 40896fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpAngle* baseAngle = nullptr; 409570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool tryReverse = false; 410570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // look for counterclockwise transfers 411dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* angle = firstAngle->previous(); 412dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* next = angle->next(); 413dac1d17027dcaa5596885a9f333979418b35001ccaryclark firstAngle = next; 41407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 415dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* prior = angle; 416dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle = next; 417dac1d17027dcaa5596885a9f333979418b35001ccaryclark next = angle->next(); 418dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(prior->next() == angle); 419dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(angle->next() == next); 420dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 42196fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 4224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 42454359294a7c9dc54802d512a5d891a35c1663392caryclark int testWinding = angle->starter()->windSum(); 425dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (SK_MinS32 != testWinding) { 426dac1d17027dcaa5596885a9f333979418b35001ccaryclark baseAngle = angle; 4274431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tryReverse = true; 4284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4294431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (baseAngle) { 4314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ComputeOneSum(baseAngle, angle, includeType); 43296fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 4334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 434dac1d17027dcaa5596885a9f333979418b35001ccaryclark } while (next != firstAngle); 43554359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) { 4364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org firstAngle = baseAngle; 4374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tryReverse = true; 4384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tryReverse) { 44096fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 441dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* prior = firstAngle; 442570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com do { 443dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle = prior; 444dac1d17027dcaa5596885a9f333979418b35001ccaryclark prior = angle->previous(); 445dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(prior->next() == angle); 446dac1d17027dcaa5596885a9f333979418b35001ccaryclark next = angle->next(); 447dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 44896fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 449dac1d17027dcaa5596885a9f333979418b35001ccaryclark continue; 450dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 45154359294a7c9dc54802d512a5d891a35c1663392caryclark int testWinding = angle->starter()->windSum(); 4524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SK_MinS32 != testWinding) { 4534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org baseAngle = angle; 454570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com continue; 45507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 456570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (baseAngle) { 4574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ComputeOneSumReverse(baseAngle, angle, includeType); 45896fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 459570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 460dac1d17027dcaa5596885a9f333979418b35001ccaryclark } while (prior != firstAngle); 461570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 46254359294a7c9dc54802d512a5d891a35c1663392caryclark return start->starter(end)->windSum(); 46307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 46407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 46555888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpSegment::contains(double newT) const { 46655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* spanBase = &fHead; 46755888e44171ffd48b591d19256884a969fe4da17caryclark do { 46855888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase->ptT()->contains(this, newT)) { 46955888e44171ffd48b591d19256884a969fe4da17caryclark return true; 47055888e44171ffd48b591d19256884a969fe4da17caryclark } 47155888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase == &fTail) { 47255888e44171ffd48b591d19256884a969fe4da17caryclark break; 47355888e44171ffd48b591d19256884a969fe4da17caryclark } 47455888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = spanBase->upCast()->next(); 47555888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 47655888e44171ffd48b591d19256884a969fe4da17caryclark return false; 47755888e44171ffd48b591d19256884a969fe4da17caryclark} 47855888e44171ffd48b591d19256884a969fe4da17caryclark 47918300a3aa7cb6eb55d21bb0450dffa58b6fc062cmtkleinvoid SkOpSegment::release(const SkOpSpan* span) { 48054359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 48108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark --fDoneCount; 482ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 48308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark --fCount; 4841597628fa38d24f23ad505bfb40e70e7c8617457caryclark SkOPASSERT(fCount >= fDoneCount); 4850dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed} 4860dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed 487e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark#if DEBUG_ANGLE 488e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark// called only by debugCheckNearCoincidence 48926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclarkdouble SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const { 49054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint testPt = this->dPtAtT(t); 49154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine testPerp = {{ testPt, testPt }}; 49254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector slope = this->dSlopeAtT(t); 49354359294a7c9dc54802d512a5d891a35c1663392caryclark testPerp[1].fX += slope.fY; 49454359294a7c9dc54802d512a5d891a35c1663392caryclark testPerp[1].fY -= slope.fX; 49554359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 49626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark const SkOpSegment* oppSegment = oppAngle->segment(); 4971049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); 49854359294a7c9dc54802d512a5d891a35c1663392caryclark double closestDistSq = SK_ScalarInfinity; 49954359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < i.used(); ++index) { 50054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { 50154359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 5020dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 50354359294a7c9dc54802d512a5d891a35c1663392caryclark double testDistSq = testPt.distanceSquared(i.pt(index)); 50454359294a7c9dc54802d512a5d891a35c1663392caryclark if (closestDistSq > testDistSq) { 50554359294a7c9dc54802d512a5d891a35c1663392caryclark closestDistSq = testDistSq; 5060dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 50754359294a7c9dc54802d512a5d891a35c1663392caryclark } 50854359294a7c9dc54802d512a5d891a35c1663392caryclark return closestDistSq; 5094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 510e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark#endif 5114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 51207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 51307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com The M and S variable name parts stand for the operators. 51407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Mi stands for Minuend (see wiki subtraction, analogous to difference) 51507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Su stands for Subtrahend 51607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com The Opp variable name part designates that the value is for the Opposite operator. 51707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Opposite values result from combining coincident spans. 51807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 51954359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 52054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) { 52154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 52254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 52354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 52454359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 52554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 52654359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 52707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // mark the smaller of startIndex, endIndex done, and all adjacent 52807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // spans with the same T value (but not 'other' spans) 52907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 53007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 53107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 53254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 53354359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 53496fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 535cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 53654359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 53754359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 53807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 53907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 54054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 54154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 54254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 54354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 54454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 5454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // more than one viable candidate -- measure angles to find best 54654359294a7c9dc54802d512a5d891a35c1663392caryclark int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp); 547570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool sortable = calcWinding != SK_NaN32; 5484431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!sortable) { 5497eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com *unsortable = true; 55054359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 55196fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 5527eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 55354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 5544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle->unorderable()) { 55507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *unsortable = true; 55654359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 55796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 55807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 5604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 5614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 56207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 56354359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = updateWinding(end, start); 5648cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (sumMiWinding == SK_MinS32) { 5658cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org *unsortable = true; 56654359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 56796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 5688cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 56954359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding = updateOppWinding(end, start); 57007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 57107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap<int>(sumMiWinding, sumSuWinding); 57207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 57496fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 57507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 57607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // iterate through the angle, and compute everyone's winding 57707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 57807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 57907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 58007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 58107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), 5824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nextAngle->end(), op, &sumMiWinding, &sumSuWinding); 58307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (activeAngle) { 58407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 58507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 58607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 587570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com foundDone = nextSegment->done(nextAngle); 58807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 58907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 59007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (nextSegment->done()) { 59107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 59207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 593570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!activeAngle) { 59454359294a7c9dc54802d512a5d891a35c1663392caryclark (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 595570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 59654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = nextAngle->lastMarked(); 59707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (last) { 5984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 59907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *chase->append() = last; 60007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 60154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 60254359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 60354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 60454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum=%d", last->upCast()->windSum()); 60554359294a7c9dc54802d512a5d891a35c1663392caryclark } 60654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 60707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 60807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6094431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while ((nextAngle = nextAngle->next()) != angle); 61054359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 61107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 61296fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 61307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 61407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 61507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 61607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 61707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 61807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 61907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 62007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 62107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 62207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 62307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 62454359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase, 62554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { 62654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 62754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 62854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 62954359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 63054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 63154359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 63207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // mark the smaller of startIndex, endIndex done, and all adjacent 63307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // spans with the same T value (but not 'other' spans) 63407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 63507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 63607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 63754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 63854359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 63996fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 640570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 64154359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 64254359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 64307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 64407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 64554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 64654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 64754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 64854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 64954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 6504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // more than one viable candidate -- measure angles to find best 65154359294a7c9dc54802d512a5d891a35c1663392caryclark int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding); 652570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool sortable = calcWinding != SK_NaN32; 65307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!sortable) { 65407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *unsortable = true; 65554359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 65696fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 65754359294a7c9dc54802d512a5d891a35c1663392caryclark } 65854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 65954359294a7c9dc54802d512a5d891a35c1663392caryclark if (angle->unorderable()) { 66054359294a7c9dc54802d512a5d891a35c1663392caryclark *unsortable = true; 66154359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 66296fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 66307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 6654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 6664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 66707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 66854359294a7c9dc54802d512a5d891a35c1663392caryclark int sumWinding = updateWinding(end, start); 6694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 67096fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 67107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 67254359294a7c9dc54802d512a5d891a35c1663392caryclark // iterate through the angle, and compute everyone's winding 67307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 67407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 67507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 67607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 67707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), 6784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org &sumWinding); 67907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (activeAngle) { 68007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 68107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 68207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 68307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundDone = nextSegment->done(nextAngle); 68407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 68507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 68607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (nextSegment->done()) { 68707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 68807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 689570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!activeAngle) { 69054359294a7c9dc54802d512a5d891a35c1663392caryclark (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 691570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 69254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = nextAngle->lastMarked(); 69307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (last) { 6944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 69507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *chase->append() = last; 69607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 69754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 69854359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 69954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 70054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum=%d", last->upCast()->windSum()); 70154359294a7c9dc54802d512a5d891a35c1663392caryclark } 70254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 70307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 70407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while ((nextAngle = nextAngle->next()) != angle); 70654359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 70707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 70896fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 70907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 71007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 71107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 71207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 71307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 71407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 71507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 71607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 71707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 71807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 71907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 72054359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, 72154359294a7c9dc54802d512a5d891a35c1663392caryclark bool* unsortable) { 72254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 72354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 72454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 72554359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 72654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 72754359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 72854359294a7c9dc54802d512a5d891a35c1663392caryclark // mark the smaller of startIndex, endIndex done, and all adjacent 72954359294a7c9dc54802d512a5d891a35c1663392caryclark // spans with the same T value (but not 'other' spans) 73007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 73107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 73207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 73354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 73454359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 73596fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 73607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 73754359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 73854359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 73907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 74007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 74154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \ 74254359294a7c9dc54802d512a5d891a35c1663392caryclark : (*nextStart)->prev()); 74354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 74454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 74554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 74654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 74754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 74827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!angle || angle->unorderable()) { 74954359294a7c9dc54802d512a5d891a35c1663392caryclark *unsortable = true; 75054359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 75196fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 75254359294a7c9dc54802d512a5d891a35c1663392caryclark } 7534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 7544431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 7554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 756570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 7574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 75896fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkOpAngle* foundAngle = nullptr; 75907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 76054359294a7c9dc54802d512a5d891a35c1663392caryclark // iterate through the angle, and compute everyone's winding 76107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 76207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 76307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 76407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 76507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 76607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 76707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 7684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!(foundDone = nextSegment->done(nextAngle))) { 7694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 7704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 77107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nextAngle = nextAngle->next(); 7734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (nextAngle != angle); 77454359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 77507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 77696fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 77707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 77807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 77907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 78007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 78107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 78207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 78307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 78407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 78507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 78607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 78707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 78854359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpGlobalState* SkOpSegment::globalState() const { 78955888e44171ffd48b591d19256884a969fe4da17caryclark return contour()->globalState(); 79065f553182ab7069378ef863d30094d0327f178d0caryclark} 79165f553182ab7069378ef863d30094d0327f178d0caryclark 7921049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { 79354359294a7c9dc54802d512a5d891a35c1663392caryclark fContour = contour; 79496fcdcc219d2a0d3579719b84b28bede76efba64halcanary fNext = nullptr; 79507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fPts = pts; 7961049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fWeight = weight; 79707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fVerb = verb; 79854359294a7c9dc54802d512a5d891a35c1663392caryclark fCount = 0; 79954359294a7c9dc54802d512a5d891a35c1663392caryclark fDoneCount = 0; 80054359294a7c9dc54802d512a5d891a35c1663392caryclark fVisited = false; 80154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* zeroSpan = &fHead; 80296fcdcc219d2a0d3579719b84b28bede76efba64halcanary zeroSpan->init(this, nullptr, 0, fPts[0]); 80354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oneSpan = &fTail; 80454359294a7c9dc54802d512a5d891a35c1663392caryclark zeroSpan->setNext(oneSpan); 80554359294a7c9dc54802d512a5d891a35c1663392caryclark oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); 8061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fID = globalState()->nextSegmentID()); 80754359294a7c9dc54802d512a5d891a35c1663392caryclark} 80854359294a7c9dc54802d512a5d891a35c1663392caryclark 80954359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { 81054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint cPt = this->dPtAtT(t); 8111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); 81254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 81354359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 8141049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i); 81554359294a7c9dc54802d512a5d891a35c1663392caryclark int used = i.used(); 81654359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < used; ++index) { 81754359294a7c9dc54802d512a5d891a35c1663392caryclark if (cPt.roughlyEqual(i.pt(index))) { 8180dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed return true; 8190dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 82054359294a7c9dc54802d512a5d891a35c1663392caryclark } 821a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return false; 822a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com} 823a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 82454359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::isXor() const { 82554359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->isXor(); 82607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 82707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 8285b5ddd73b4baf22752924bf20d097e96236c36f8caryclarkvoid SkOpSegment::markAllDone() { 8295b5ddd73b4baf22752924bf20d097e96236c36f8caryclark SkOpSpan* span = this->head(); 8305b5ddd73b4baf22752924bf20d097e96236c36f8caryclark do { 8315b5ddd73b4baf22752924bf20d097e96236c36f8caryclark this->markDone(span); 8325b5ddd73b4baf22752924bf20d097e96236c36f8caryclark } while ((span = span->next()->upCastable())); 8335b5ddd73b4baf22752924bf20d097e96236c36f8caryclark} 8345b5ddd73b4baf22752924bf20d097e96236c36f8caryclark 83554359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) { 83654359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 83754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* minSpan = start->starter(end); 83854359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(minSpan); 83996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 84007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* other = this; 841918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark SkOpSpan* priorDone = nullptr; 842918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark SkOpSpan* lastDone = nullptr; 84354359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &minSpan, &last))) { 84407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (other->done()) { 845dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 846dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 84707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 848918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark if (lastDone == minSpan || priorDone == minSpan) { 849918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark return nullptr; 850918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark } 85154359294a7c9dc54802d512a5d891a35c1663392caryclark other->markDone(minSpan); 852918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark priorDone = lastDone; 853918fb1fe6ff5349a2d1e5fb6872139f5fb931480Cary Clark lastDone = minSpan; 85407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 85507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 85607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 85707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 85854359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 85954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** lastPtr) { 86054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* spanStart = start->starter(end); 86154359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 86254359294a7c9dc54802d512a5d891a35c1663392caryclark bool success = markWinding(spanStart, winding); 86396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 8644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpSegment* other = this; 86554359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 86654359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart->windSum() != SK_MinS32) { 867b36a3cd137e2b6c328854015018594bb9967e493caryclark// SkASSERT(spanStart->windSum() == winding); // FIXME: is this assert too aggressive? 868dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 869dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 8704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 87154359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, winding); 8726f726addf3178b01949bb389ef83cf14a1d7b6b2caryclark } 87365f553182ab7069378ef863d30094d0327f178d0caryclark if (lastPtr) { 87465f553182ab7069378ef863d30094d0327f178d0caryclark *lastPtr = last; 87565f553182ab7069378ef863d30094d0327f178d0caryclark } 87665f553182ab7069378ef863d30094d0327f178d0caryclark return success; 8774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 8784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 87954359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, 88054359294a7c9dc54802d512a5d891a35c1663392caryclark int winding, int oppWinding, SkOpSpanBase** lastPtr) { 88154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* spanStart = start->starter(end); 88254359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 88354359294a7c9dc54802d512a5d891a35c1663392caryclark bool success = markWinding(spanStart, winding, oppWinding); 88496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 88507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* other = this; 88654359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 88754359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart->windSum() != SK_MinS32) { 88854359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand() == other->operand()) { 889624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { 89054359294a7c9dc54802d512a5d891a35c1663392caryclark this->globalState()->setWindingFailed(); 89154359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 892dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 89354359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 89454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->windSum() == oppWinding); 89554359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->oppSum() == winding); 896dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 897dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 898dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 899dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 90054359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand() == other->operand()) { 90154359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, winding, oppWinding); 902dac1d17027dcaa5596885a9f333979418b35001ccaryclark } else { 90354359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, oppWinding, winding); 90407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 90507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 90665f553182ab7069378ef863d30094d0327f178d0caryclark if (lastPtr) { 90765f553182ab7069378ef863d30094d0327f178d0caryclark *lastPtr = last; 90865f553182ab7069378ef863d30094d0327f178d0caryclark } 90965f553182ab7069378ef863d30094d0327f178d0caryclark return success; 91007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 91107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 91254359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) { 91307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(angle->segment() == this); 91407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (UseInnerWinding(maxWinding, sumWinding)) { 91507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com maxWinding = sumWinding; 91607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 91754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 91854359294a7c9dc54802d512a5d891a35c1663392caryclark (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last); 919570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_WINDING 920570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (last) { 92154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s last seg=%d span=%d", __FUNCTION__, 92254359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 92354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 92454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum="); 92554359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 92654359294a7c9dc54802d512a5d891a35c1663392caryclark } 92754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 928570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 929570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 93007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 93107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 93207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 93354359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, 93454359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSumWinding, const SkOpAngle* angle) { 93507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(angle->segment() == this); 93607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (UseInnerWinding(maxWinding, sumWinding)) { 93707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com maxWinding = sumWinding; 93807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 93907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { 94007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com oppMaxWinding = oppSumWinding; 94107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 94296fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpanBase* last = nullptr; 94365f553182ab7069378ef863d30094d0327f178d0caryclark // caller doesn't require that this marks anything 94454359294a7c9dc54802d512a5d891a35c1663392caryclark (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last); 945570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_WINDING 946570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (last) { 94754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s last segment=%d span=%d", __FUNCTION__, 94854359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 94954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 95054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum="); 95154359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 95254359294a7c9dc54802d512a5d891a35c1663392caryclark } 95354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" \n"); 954570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 955570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 95607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 95707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 95807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 95954359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::markDone(SkOpSpan* span) { 96054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 96154359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 9620dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed return; 9630dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 96454359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_MARK_DONE 96554359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum()); 96654359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 96754359294a7c9dc54802d512a5d891a35c1663392caryclark span->setDone(true); 96854359294a7c9dc54802d512a5d891a35c1663392caryclark ++fDoneCount; 96954359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 9700dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed} 9710dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed 97254359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markWinding(SkOpSpan* span, int winding) { 97354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 97454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(winding); 97554359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 97665f553182ab7069378ef863d30094d0327f178d0caryclark return false; 97707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 97807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_MARK_DONE 97954359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, winding); 9800dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed#endif 98154359294a7c9dc54802d512a5d891a35c1663392caryclark span->setWindSum(winding); 98254359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 98365f553182ab7069378ef863d30094d0327f178d0caryclark return true; 98407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 98507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 98654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { 98754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 98854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(winding || oppWinding); 98954359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 99065f553182ab7069378ef863d30094d0327f178d0caryclark return false; 99107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 99207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_MARK_DONE 99354359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, winding, oppWinding); 9948cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org#endif 99554359294a7c9dc54802d512a5d891a35c1663392caryclark span->setWindSum(winding); 99654359294a7c9dc54802d512a5d891a35c1663392caryclark span->setOppSum(oppWinding); 9974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org debugValidate(); 99865f553182ab7069378ef863d30094d0327f178d0caryclark return true; 99907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 100007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 100154359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, 1002ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark const SkPoint& testPt) const { 100355888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(this == base->segment()); 100455888e44171ffd48b591d19256884a969fe4da17caryclark if (this == testParent) { 100555888e44171ffd48b591d19256884a969fe4da17caryclark if (precisely_equal(base->fT, testT)) { 100655888e44171ffd48b591d19256884a969fe4da17caryclark return true; 100755888e44171ffd48b591d19256884a969fe4da17caryclark } 100807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 100954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { 101054359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 1011e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 101255888e44171ffd48b591d19256884a969fe4da17caryclark return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); 101354359294a7c9dc54802d512a5d891a35c1663392caryclark} 101454359294a7c9dc54802d512a5d891a35c1663392caryclark 101554359294a7c9dc54802d512a5d891a35c1663392caryclarkstatic SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { 101654359294a7c9dc54802d512a5d891a35c1663392caryclark if (last) { 101754359294a7c9dc54802d512a5d891a35c1663392caryclark *last = endSpan; 101807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 101996fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 102007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 102107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 102254359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, 102354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** last) const { 102454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* origStart = *startPtr; 1025dac1d17027dcaa5596885a9f333979418b35001ccaryclark int step = *stepPtr; 102654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev(); 102754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endSpan); 102854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle(); 102954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* foundSpan; 103054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* otherEnd; 1031dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpSegment* other; 103296fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (angle == nullptr) { 103354359294a7c9dc54802d512a5d891a35c1663392caryclark if (endSpan->t() != 0 && endSpan->t() != 1) { 103496fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 1035dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 103654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* otherPtT = endSpan->ptT()->next(); 103754359294a7c9dc54802d512a5d891a35c1663392caryclark other = otherPtT->segment(); 103854359294a7c9dc54802d512a5d891a35c1663392caryclark foundSpan = otherPtT->span(); 1039343382e3acc8369f7bd4328e7c807255b5776fe5caryclark otherEnd = step > 0 1040343382e3acc8369f7bd4328e7c807255b5776fe5caryclark ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr 1041343382e3acc8369f7bd4328e7c807255b5776fe5caryclark : foundSpan->prev(); 1042dac1d17027dcaa5596885a9f333979418b35001ccaryclark } else { 1043dac1d17027dcaa5596885a9f333979418b35001ccaryclark int loopCount = angle->loopCount(); 1044dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (loopCount > 2) { 104554359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 1046dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 1047dac1d17027dcaa5596885a9f333979418b35001ccaryclark const SkOpAngle* next = angle->next(); 104896fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == next) { 104996fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 105065b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark } 1051dac1d17027dcaa5596885a9f333979418b35001ccaryclark#if DEBUG_WINDING 1052624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() 105354359294a7c9dc54802d512a5d891a35c1663392caryclark && !next->segment()->contour()->isXor()) { 1054dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDebugf("%s mismatched signs\n", __FUNCTION__); 10550dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 105654359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 1057dac1d17027dcaa5596885a9f333979418b35001ccaryclark other = next->segment(); 105854359294a7c9dc54802d512a5d891a35c1663392caryclark foundSpan = endSpan = next->start(); 1059dac1d17027dcaa5596885a9f333979418b35001ccaryclark otherEnd = next->end(); 1060570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 1061343382e3acc8369f7bd4328e7c807255b5776fe5caryclark if (!otherEnd) { 1062343382e3acc8369f7bd4328e7c807255b5776fe5caryclark return nullptr; 1063343382e3acc8369f7bd4328e7c807255b5776fe5caryclark } 106454359294a7c9dc54802d512a5d891a35c1663392caryclark int foundStep = foundSpan->step(otherEnd); 1065dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (*stepPtr != foundStep) { 106654359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 106707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 106854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(*startPtr); 106965b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark// SkASSERT(otherEnd >= 0); 107054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast(); 107154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* foundMin = foundSpan->starter(otherEnd); 107254359294a7c9dc54802d512a5d891a35c1663392caryclark if (foundMin->windValue() != origMin->windValue() 107354359294a7c9dc54802d512a5d891a35c1663392caryclark || foundMin->oppValue() != origMin->oppValue()) { 107454359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 1075dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 107654359294a7c9dc54802d512a5d891a35c1663392caryclark *startPtr = foundSpan; 1077dac1d17027dcaa5596885a9f333979418b35001ccaryclark *stepPtr = foundStep; 1078dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (minPtr) { 1079dac1d17027dcaa5596885a9f333979418b35001ccaryclark *minPtr = foundMin; 1080a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 108107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 108207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 108307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 108455888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with DebugClearVisited() 108555888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpSegment::ClearVisited(SkOpSpanBase* span) { 108654359294a7c9dc54802d512a5d891a35c1663392caryclark // reset visited flag back to false 108754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 108854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 108954359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != stopPtT) { 109054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* opp = ptT->segment(); 109154359294a7c9dc54802d512a5d891a35c1663392caryclark opp->resetVisited(); 109207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1093bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } while (!span->final() && (span = span->upCast()->next())); 109407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 109507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 109655888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugMissingCoincidence() 109754359294a7c9dc54802d512a5d891a35c1663392caryclark// look for pairs of undetected coincident curves 109854359294a7c9dc54802d512a5d891a35c1663392caryclark// assumes that segments going in have visited flag clear 109955888e44171ffd48b591d19256884a969fe4da17caryclark// Even though pairs of curves correct detect coincident runs, a run may be missed 110055888e44171ffd48b591d19256884a969fe4da17caryclark// if the coincidence is a product of multiple intersections. For instance, given 110155888e44171ffd48b591d19256884a969fe4da17caryclark// curves A, B, and C: 110255888e44171ffd48b591d19256884a969fe4da17caryclark// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near 110355888e44171ffd48b591d19256884a969fe4da17caryclark// the end of C that the intersection is replaced with the end of C. 110455888e44171ffd48b591d19256884a969fe4da17caryclark// Even though A-B correctly do not detect an intersection at point 2, 110555888e44171ffd48b591d19256884a969fe4da17caryclark// the resulting run from point 1 to point 2 is coincident on A and B. 110655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpSegment::missingCoincidence() { 1107bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (this->done()) { 110827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return false; 1109bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 111096fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSpan* prior = nullptr; 1111bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase* spanBase = &fHead; 111255888e44171ffd48b591d19256884a969fe4da17caryclark bool result = false; 111354359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1114bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; 1115c6d855f7f3d548c52f450299dc6975820cda3387caryclark SkOPASSERT(ptT->span() == spanBase); 111654359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != spanStopPtT) { 1117182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (ptT->deleted()) { 1118182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1119182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 112054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* opp = ptT->span()->segment(); 1121bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (opp->done()) { 112254359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 112354359294a7c9dc54802d512a5d891a35c1663392caryclark } 1124bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence 1125bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (!opp->visited()) { 112654359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 112754359294a7c9dc54802d512a5d891a35c1663392caryclark } 1128bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (spanBase == &fHead) { 112954359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 1130bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 113155888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->segment() == this) { 113255888e44171ffd48b591d19256884a969fe4da17caryclark continue; 113355888e44171ffd48b591d19256884a969fe4da17caryclark } 1134bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* span = spanBase->upCastable(); 1135bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // FIXME?: this assumes that if the opposite segment is coincident then no more 1136bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // coincidence needs to be detected. This may not be true. 113755888e44171ffd48b591d19256884a969fe4da17caryclark if (span && span->containsCoincidence(opp)) { 113826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark continue; 113926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 1140bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (spanBase->containsCoinEnd(opp)) { 1141bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 114255888e44171ffd48b591d19256884a969fe4da17caryclark } 114396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpPtT* priorPtT = nullptr, * priorStopPtT; 114454359294a7c9dc54802d512a5d891a35c1663392caryclark // find prior span containing opp segment 114596fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSegment* priorOpp = nullptr; 1146bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* priorTest = spanBase->prev(); 1147bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark while (!priorOpp && priorTest) { 1148bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark priorStopPtT = priorPtT = priorTest->ptT(); 114954359294a7c9dc54802d512a5d891a35c1663392caryclark while ((priorPtT = priorPtT->next()) != priorStopPtT) { 1150182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (priorPtT->deleted()) { 1151182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1152182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 115354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = priorPtT->span()->segment(); 115454359294a7c9dc54802d512a5d891a35c1663392caryclark if (segment == opp) { 1155bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark prior = priorTest; 115654359294a7c9dc54802d512a5d891a35c1663392caryclark priorOpp = opp; 115754359294a7c9dc54802d512a5d891a35c1663392caryclark break; 115854359294a7c9dc54802d512a5d891a35c1663392caryclark } 115954359294a7c9dc54802d512a5d891a35c1663392caryclark } 1160bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark priorTest = priorTest->prev(); 116154359294a7c9dc54802d512a5d891a35c1663392caryclark } 116254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!priorOpp) { 116354359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 116454359294a7c9dc54802d512a5d891a35c1663392caryclark } 116526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (priorPtT == ptT) { 116626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark continue; 116726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark } 116854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* oppStart = prior->ptT(); 1169bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpPtT* oppEnd = spanBase->ptT(); 117054359294a7c9dc54802d512a5d891a35c1663392caryclark bool swapped = priorPtT->fT > ptT->fT; 117154359294a7c9dc54802d512a5d891a35c1663392caryclark if (swapped) { 117254359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(priorPtT, ptT); 117354359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppStart, oppEnd); 117454359294a7c9dc54802d512a5d891a35c1663392caryclark } 117555888e44171ffd48b591d19256884a969fe4da17caryclark SkOpCoincidence* coincidences = this->globalState()->coincidence(); 117655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootPriorPtT = priorPtT->span()->ptT(); 117755888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootPtT = ptT->span()->ptT(); 117855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootOppStart = oppStart->span()->ptT(); 117955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* rootOppEnd = oppEnd->span()->ptT(); 118055888e44171ffd48b591d19256884a969fe4da17caryclark if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 118154359294a7c9dc54802d512a5d891a35c1663392caryclark goto swapBack; 118254359294a7c9dc54802d512a5d891a35c1663392caryclark } 118355888e44171ffd48b591d19256884a969fe4da17caryclark if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) { 118454359294a7c9dc54802d512a5d891a35c1663392caryclark // mark coincidence 118555888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 118655888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__, 118755888e44171ffd48b591d19256884a969fe4da17caryclark rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(), 118855888e44171ffd48b591d19256884a969fe4da17caryclark rootOppEnd->debugID()); 118955888e44171ffd48b591d19256884a969fe4da17caryclark#endif 119055888e44171ffd48b591d19256884a969fe4da17caryclark if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 119155888e44171ffd48b591d19256884a969fe4da17caryclark coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd); 1192bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 119355888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 119455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)); 119555888e44171ffd48b591d19256884a969fe4da17caryclark#endif 119655888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 119754359294a7c9dc54802d512a5d891a35c1663392caryclark } 119854359294a7c9dc54802d512a5d891a35c1663392caryclark swapBack: 119954359294a7c9dc54802d512a5d891a35c1663392caryclark if (swapped) { 120054359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(priorPtT, ptT); 120154359294a7c9dc54802d512a5d891a35c1663392caryclark } 12020dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 120396fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); 120455888e44171ffd48b591d19256884a969fe4da17caryclark ClearVisited(&fHead); 120555888e44171ffd48b591d19256884a969fe4da17caryclark return result; 120654359294a7c9dc54802d512a5d891a35c1663392caryclark} 120754359294a7c9dc54802d512a5d891a35c1663392caryclark 120855888e44171ffd48b591d19256884a969fe4da17caryclark// please keep this in sync with debugMoveMultiples() 120908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark// if a span has more than one intersection, merge the other segments' span as needed 1210d78c088b6136590371fddd4cab67bfb4bf692fd3caryclarkbool SkOpSegment::moveMultiples() { 121108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark debugValidate(); 121208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* test = &fHead; 121308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 121408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark int addCount = test->spanAddsCount(); 12157eb01e00b1a1f7c649e1e78eb3f4644033ce94eeCary Clark// FAIL_IF(addCount < 1); 12167eb01e00b1a1f7c649e1e78eb3f4644033ce94eeCary Clark if (addCount <= 1) { 121708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 121808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 121908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* startPtT = test->ptT(); 122008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* testPtT = startPtT; 122108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { // iterate through all spans associated with start 122208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppSpan = testPtT->span(); 122308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSpan->spanAddsCount() == addCount) { 122408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 122508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 122608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSpan->deleted()) { 122708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 122808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 122908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSegment* oppSegment = oppSpan->segment(); 123008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSegment == this) { 123108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 123208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 123308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // find range of spans to consider merging 123408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppPrev = oppSpan; 123508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppFirst = oppSpan; 123608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppPrev = oppPrev->prev())) { 123708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (!roughly_equal(oppPrev->t(), oppSpan->t())) { 123808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark break; 123908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPrev->spanAddsCount() == addCount) { 124108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 124208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPrev->deleted()) { 124408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 124508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppFirst = oppPrev; 124708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppNext = oppSpan; 124908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppLast = oppSpan; 125096fcdcc219d2a0d3579719b84b28bede76efba64halcanary while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { 125108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (!roughly_equal(oppNext->t(), oppSpan->t())) { 125208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark break; 125308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppNext->spanAddsCount() == addCount) { 125508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 125608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppNext->deleted()) { 125808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 125908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppLast = oppNext; 126108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppFirst == oppLast) { 126308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 126408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppTest = oppFirst; 126608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 126708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppTest == oppSpan) { 126808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 126908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 127008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // check to see if the candidate meets specific criteria: 127108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // it contains spans of segments in test's loop but not including 'this' 127208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* oppStartPtT = oppTest->ptT(); 127308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* oppPtT = oppStartPtT; 127408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppPtT = oppPtT->next()) != oppStartPtT) { 127508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSegment* oppPtTSegment = oppPtT->segment(); 127608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPtTSegment == this) { 127708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto tryNextSpan; 127808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 127908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* matchPtT = startPtT; 128008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 128108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (matchPtT->segment() == oppPtTSegment) { 128208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto foundMatch; 128308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 128408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((matchPtT = matchPtT->next()) != startPtT); 128508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto tryNextSpan; 128608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark foundMatch: // merge oppTest and oppSpan 128708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSegment->debugValidate(); 128830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppTest->mergeMatches(oppSpan); 128930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppTest->addOpp(oppSpan); 129008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSegment->debugValidate(); 129108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto checkNextSpan; 129208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 129355888e44171ffd48b591d19256884a969fe4da17caryclark tryNextSpan: 129408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ; 129508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); 129608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((testPtT = testPtT->next()) != startPtT); 129755888e44171ffd48b591d19256884a969fe4da17caryclarkcheckNextSpan: 129808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ; 129996fcdcc219d2a0d3579719b84b28bede76efba64halcanary } while ((test = test->final() ? nullptr : test->upCast()->next())); 130008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark debugValidate(); 1301d78c088b6136590371fddd4cab67bfb4bf692fd3caryclark return true; 130208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark} 130308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark 130455888e44171ffd48b591d19256884a969fe4da17caryclark// adjacent spans may have points close by 130528da2837040cd116dd2d854dd3268723ca219f11Cary Clarkbool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan, 130628da2837040cd116dd2d854dd3268723ca219f11Cary Clark bool* found) const { 130755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* refHead = refSpan->ptT(); 130855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* checkHead = checkSpan->ptT(); 130955888e44171ffd48b591d19256884a969fe4da17caryclark// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart 131030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) { 131155888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 131255888e44171ffd48b591d19256884a969fe4da17caryclark // verify that no combination of points are close 131355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* dBugRef = refHead; 131455888e44171ffd48b591d19256884a969fe4da17caryclark do { 131555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* dBugCheck = checkHead; 131655888e44171ffd48b591d19256884a969fe4da17caryclark do { 131730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt)); 131855888e44171ffd48b591d19256884a969fe4da17caryclark dBugCheck = dBugCheck->next(); 131955888e44171ffd48b591d19256884a969fe4da17caryclark } while (dBugCheck != checkHead); 132055888e44171ffd48b591d19256884a969fe4da17caryclark dBugRef = dBugRef->next(); 132155888e44171ffd48b591d19256884a969fe4da17caryclark } while (dBugRef != refHead); 132255888e44171ffd48b591d19256884a969fe4da17caryclark#endif 132328da2837040cd116dd2d854dd3268723ca219f11Cary Clark *found = false; 132428da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 132555888e44171ffd48b591d19256884a969fe4da17caryclark } 132655888e44171ffd48b591d19256884a969fe4da17caryclark // check only unique points 132755888e44171ffd48b591d19256884a969fe4da17caryclark SkScalar distSqBest = SK_ScalarMax; 132855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* refBest = nullptr; 132955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* checkBest = nullptr; 133055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ref = refHead; 133155888e44171ffd48b591d19256884a969fe4da17caryclark do { 133255888e44171ffd48b591d19256884a969fe4da17caryclark if (ref->deleted()) { 133355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 133455888e44171ffd48b591d19256884a969fe4da17caryclark } 133555888e44171ffd48b591d19256884a969fe4da17caryclark while (ref->ptAlreadySeen(refHead)) { 133655888e44171ffd48b591d19256884a969fe4da17caryclark ref = ref->next(); 133755888e44171ffd48b591d19256884a969fe4da17caryclark if (ref == refHead) { 133855888e44171ffd48b591d19256884a969fe4da17caryclark goto doneCheckingDistance; 133955888e44171ffd48b591d19256884a969fe4da17caryclark } 134055888e44171ffd48b591d19256884a969fe4da17caryclark } 134155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* check = checkHead; 134255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* refSeg = ref->segment(); 134328da2837040cd116dd2d854dd3268723ca219f11Cary Clark int escapeHatch = 100000; // defend against infinite loops 134455888e44171ffd48b591d19256884a969fe4da17caryclark do { 134555888e44171ffd48b591d19256884a969fe4da17caryclark if (check->deleted()) { 134655888e44171ffd48b591d19256884a969fe4da17caryclark continue; 134755888e44171ffd48b591d19256884a969fe4da17caryclark } 134855888e44171ffd48b591d19256884a969fe4da17caryclark while (check->ptAlreadySeen(checkHead)) { 134955888e44171ffd48b591d19256884a969fe4da17caryclark check = check->next(); 135055888e44171ffd48b591d19256884a969fe4da17caryclark if (check == checkHead) { 135155888e44171ffd48b591d19256884a969fe4da17caryclark goto nextRef; 135255888e44171ffd48b591d19256884a969fe4da17caryclark } 135355888e44171ffd48b591d19256884a969fe4da17caryclark } 135455888e44171ffd48b591d19256884a969fe4da17caryclark SkScalar distSq = ref->fPt.distanceToSqd(check->fPt); 135555888e44171ffd48b591d19256884a969fe4da17caryclark if (distSqBest > distSq && (refSeg != check->segment() 135655888e44171ffd48b591d19256884a969fe4da17caryclark || !refSeg->ptsDisjoint(*ref, *check))) { 135755888e44171ffd48b591d19256884a969fe4da17caryclark distSqBest = distSq; 135855888e44171ffd48b591d19256884a969fe4da17caryclark refBest = ref; 135955888e44171ffd48b591d19256884a969fe4da17caryclark checkBest = check; 136055888e44171ffd48b591d19256884a969fe4da17caryclark } 136128da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (--escapeHatch <= 0) { 136228da2837040cd116dd2d854dd3268723ca219f11Cary Clark return false; 136328da2837040cd116dd2d854dd3268723ca219f11Cary Clark } 136455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((check = check->next()) != checkHead); 136528da2837040cd116dd2d854dd3268723ca219f11Cary Clark nextRef: 136655888e44171ffd48b591d19256884a969fe4da17caryclark ; 136755888e44171ffd48b591d19256884a969fe4da17caryclark } while ((ref = ref->next()) != refHead); 136855888e44171ffd48b591d19256884a969fe4da17caryclarkdoneCheckingDistance: 136928da2837040cd116dd2d854dd3268723ca219f11Cary Clark *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT, 1370ef4f32ac858825dc443cfe4739ea878fb0bf550fcaryclark checkBest->fPt); 137128da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 137255888e44171ffd48b591d19256884a969fe4da17caryclark} 137355888e44171ffd48b591d19256884a969fe4da17caryclark 137455888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this function in sync with debugMoveNearby() 137554359294a7c9dc54802d512a5d891a35c1663392caryclark// Move nearby t values and pts so they all hang off the same span. Alignment happens later. 137628da2837040cd116dd2d854dd3268723ca219f11Cary Clarkbool SkOpSegment::moveNearby() { 137754359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 137855888e44171ffd48b591d19256884a969fe4da17caryclark // release undeleted spans pointing to this seg that are linked to the primary span 137955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* spanBase = &fHead; 138054359294a7c9dc54802d512a5d891a35c1663392caryclark do { 138155888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* ptT = spanBase->ptT(); 138255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* headPtT = ptT; 138355888e44171ffd48b591d19256884a969fe4da17caryclark while ((ptT = ptT->next()) != headPtT) { 138455888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* test = ptT->span(); 138555888e44171ffd48b591d19256884a969fe4da17caryclark if (ptT->segment() == this && !ptT->deleted() && test != spanBase 138655888e44171ffd48b591d19256884a969fe4da17caryclark && test->ptT() == ptT) { 138755888e44171ffd48b591d19256884a969fe4da17caryclark if (test->final()) { 138855888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase == &fHead) { 138955888e44171ffd48b591d19256884a969fe4da17caryclark this->clearAll(); 139028da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 139155888e44171ffd48b591d19256884a969fe4da17caryclark } 139255888e44171ffd48b591d19256884a969fe4da17caryclark spanBase->upCast()->release(ptT); 139355888e44171ffd48b591d19256884a969fe4da17caryclark } else if (test->prev()) { 139455888e44171ffd48b591d19256884a969fe4da17caryclark test->upCast()->release(headPtT); 139555888e44171ffd48b591d19256884a969fe4da17caryclark } 139655888e44171ffd48b591d19256884a969fe4da17caryclark break; 1397570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 139807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 139955888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = spanBase->upCast()->next(); 140055888e44171ffd48b591d19256884a969fe4da17caryclark } while (!spanBase->final()); 140155888e44171ffd48b591d19256884a969fe4da17caryclark 140255888e44171ffd48b591d19256884a969fe4da17caryclark // This loop looks for adjacent spans which are near by 140355888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = &fHead; 140455888e44171ffd48b591d19256884a969fe4da17caryclark do { // iterate through all spans associated with start 140555888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* test = spanBase->upCast()->next(); 140628da2837040cd116dd2d854dd3268723ca219f11Cary Clark bool found; 140728da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (!this->spansNearby(spanBase, test, &found)) { 140828da2837040cd116dd2d854dd3268723ca219f11Cary Clark return false; 140928da2837040cd116dd2d854dd3268723ca219f11Cary Clark } 141028da2837040cd116dd2d854dd3268723ca219f11Cary Clark if (found) { 141155888e44171ffd48b591d19256884a969fe4da17caryclark if (test->final()) { 141255888e44171ffd48b591d19256884a969fe4da17caryclark if (spanBase->prev()) { 141355888e44171ffd48b591d19256884a969fe4da17caryclark test->merge(spanBase->upCast()); 141455888e44171ffd48b591d19256884a969fe4da17caryclark } else { 141555888e44171ffd48b591d19256884a969fe4da17caryclark this->clearAll(); 141628da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 141755888e44171ffd48b591d19256884a969fe4da17caryclark } 141855888e44171ffd48b591d19256884a969fe4da17caryclark } else { 141955888e44171ffd48b591d19256884a969fe4da17caryclark spanBase->merge(test->upCast()); 142055888e44171ffd48b591d19256884a969fe4da17caryclark } 142155888e44171ffd48b591d19256884a969fe4da17caryclark } 142255888e44171ffd48b591d19256884a969fe4da17caryclark spanBase = test; 142355888e44171ffd48b591d19256884a969fe4da17caryclark } while (!spanBase->final()); 142454359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 142528da2837040cd116dd2d854dd3268723ca219f11Cary Clark return true; 1426dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1427dac1d17027dcaa5596885a9f333979418b35001ccaryclark 142854359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::operand() const { 142954359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->operand(); 14305e27e0eb1d1d4c7674e221d3ba3314500ea0b97acaryclark} 14315e27e0eb1d1d4c7674e221d3ba3314500ea0b97acaryclark 143254359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::oppXor() const { 143354359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->oppXor(); 1434ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark} 1435ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark 143654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { 143754359294a7c9dc54802d512a5d891a35c1663392caryclark if (fVerb == SkPath::kLine_Verb) { 143854359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 14390dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 144054359294a7c9dc54802d512a5d891a35c1663392caryclark // quads (and cubics) can loop back to nearly a line so that an opposite curve 144154359294a7c9dc54802d512a5d891a35c1663392caryclark // hits in two places with very different t values. 144254359294a7c9dc54802d512a5d891a35c1663392caryclark // OPTIMIZATION: curves could be preflighted so that, for example, something like 144354359294a7c9dc54802d512a5d891a35c1663392caryclark // 'controls contained by ends' could avoid this check for common curves 144454359294a7c9dc54802d512a5d891a35c1663392caryclark // 'ends are extremes in x or y' is cheaper to compute and real-world common 144554359294a7c9dc54802d512a5d891a35c1663392caryclark // on the other hand, the below check is relatively inexpensive 144654359294a7c9dc54802d512a5d891a35c1663392caryclark double midT = (t1 + t2) / 2; 144754359294a7c9dc54802d512a5d891a35c1663392caryclark SkPoint midPt = this->ptAtT(midT); 144854359294a7c9dc54802d512a5d891a35c1663392caryclark double seDistSq = SkTMax(pt1.distanceToSqd(pt2) * 2, FLT_EPSILON * 2); 144954359294a7c9dc54802d512a5d891a35c1663392caryclark return midPt.distanceToSqd(pt1) > seDistSq || midPt.distanceToSqd(pt2) > seDistSq; 145054359294a7c9dc54802d512a5d891a35c1663392caryclark} 145154359294a7c9dc54802d512a5d891a35c1663392caryclark 145254359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 145354359294a7c9dc54802d512a5d891a35c1663392caryclark int* maxWinding, int* sumWinding) { 145454359294a7c9dc54802d512a5d891a35c1663392caryclark int deltaSum = SpanSign(start, end); 145554359294a7c9dc54802d512a5d891a35c1663392caryclark *maxWinding = *sumMiWinding; 145654359294a7c9dc54802d512a5d891a35c1663392caryclark *sumWinding = *sumMiWinding -= deltaSum; 145760e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 1458dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1459dac1d17027dcaa5596885a9f333979418b35001ccaryclark 146054359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 146154359294a7c9dc54802d512a5d891a35c1663392caryclark int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, 146254359294a7c9dc54802d512a5d891a35c1663392caryclark int* oppSumWinding) { 146354359294a7c9dc54802d512a5d891a35c1663392caryclark int deltaSum = SpanSign(start, end); 146454359294a7c9dc54802d512a5d891a35c1663392caryclark int oppDeltaSum = OppSign(start, end); 146507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 146607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *maxWinding = *sumSuWinding; 146707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *sumWinding = *sumSuWinding -= deltaSum; 146807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppMaxWinding = *sumMiWinding; 146907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppSumWinding = *sumMiWinding -= oppDeltaSum; 147007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 147107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *maxWinding = *sumMiWinding; 147207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *sumWinding = *sumMiWinding -= deltaSum; 147307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppMaxWinding = *sumSuWinding; 147407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppSumWinding = *sumSuWinding -= oppDeltaSum; 147507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 147660e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 147760e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM); 147807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 147907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1480b36a3cd137e2b6c328854015018594bb9967e493caryclarkbool SkOpSegment::sortAngles() { 148154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* span = &this->fHead; 14824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 148354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* fromAngle = span->fromAngle(); 148496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle(); 1485dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (!fromAngle && !toAngle) { 14864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 14874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1488cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#if DEBUG_ANGLE 14894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool wroteAfterHeader = false; 1490cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#endif 149154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* baseAngle = fromAngle; 149254359294a7c9dc54802d512a5d891a35c1663392caryclark if (fromAngle && toAngle) { 14934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 149454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(), 149554359294a7c9dc54802d512a5d891a35c1663392caryclark span->debugID()); 149654359294a7c9dc54802d512a5d891a35c1663392caryclark wroteAfterHeader = true; 14974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 1498b36a3cd137e2b6c328854015018594bb9967e493caryclark FAIL_IF(!fromAngle->insert(toAngle)); 149954359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (!fromAngle) { 150054359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle = toAngle; 150107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 150254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 15034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 150454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oSpan = ptT->span(); 150554359294a7c9dc54802d512a5d891a35c1663392caryclark if (oSpan == span) { 150654359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 150754359294a7c9dc54802d512a5d891a35c1663392caryclark } 150854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* oAngle = oSpan->fromAngle(); 1509dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (oAngle) { 1510570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_ANGLE 15114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!wroteAfterHeader) { 151254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 151354359294a7c9dc54802d512a5d891a35c1663392caryclark span->t(), span->debugID()); 15144431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org wroteAfterHeader = true; 15154431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1516570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 151754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oAngle->loopContains(baseAngle)) { 15188cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org baseAngle->insert(oAngle); 15198cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 15204431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 152154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oSpan->final()) { 152254359294a7c9dc54802d512a5d891a35c1663392caryclark oAngle = oSpan->upCast()->toAngle(); 152354359294a7c9dc54802d512a5d891a35c1663392caryclark if (oAngle) { 15244431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 152554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!wroteAfterHeader) { 152654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 152754359294a7c9dc54802d512a5d891a35c1663392caryclark span->t(), span->debugID()); 152854359294a7c9dc54802d512a5d891a35c1663392caryclark wroteAfterHeader = true; 152954359294a7c9dc54802d512a5d891a35c1663392caryclark } 15304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 153154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oAngle->loopContains(baseAngle)) { 153254359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle->insert(oAngle); 153354359294a7c9dc54802d512a5d891a35c1663392caryclark } 15348cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 15354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 153654359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((ptT = ptT->next()) != stopPtT); 153754359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseAngle->loopCount() == 1) { 153896fcdcc219d2a0d3579719b84b28bede76efba64halcanary span->setFromAngle(nullptr); 153954359294a7c9dc54802d512a5d891a35c1663392caryclark if (toAngle) { 154096fcdcc219d2a0d3579719b84b28bede76efba64halcanary span->upCast()->setToAngle(nullptr); 15414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 154296fcdcc219d2a0d3579719b84b28bede76efba64halcanary baseAngle = nullptr; 15434431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 15444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 15454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!baseAngle || baseAngle->loopCount() > 1); 15464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 154754359294a7c9dc54802d512a5d891a35c1663392caryclark } while (!span->final() && (span = span->upCast()->next())); 1548b36a3cd137e2b6c328854015018594bb9967e493caryclark return true; 1549570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1550570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 155154359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 15521049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDCurve* edge) const { 1553cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(start != end); 155454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& startPtT = *start->ptT(); 155554359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& endPtT = *end->ptT(); 15561049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(edge->fVerb = fVerb); 15571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[0].set(startPtT.fPt); 1558cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int points = SkPathOpsVerbToPoints(fVerb); 15591049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[points].set(endPtT.fPt); 1560cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kLine_Verb) { 1561cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1562cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 156354359294a7c9dc54802d512a5d891a35c1663392caryclark double startT = startPtT.fT; 156454359294a7c9dc54802d512a5d891a35c1663392caryclark double endT = endPtT.fT; 1565cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1566cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // don't compute midpoints if we already have them 1567cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fLine[1].set(fPts[1]); 15691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return false; 15701049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15711049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (fVerb == SkPath::kConic_Verb) { 15721049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic[1].set(fPts[1]); 15731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic.fWeight = fWeight; 1574cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1575cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1576cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 157754359294a7c9dc54802d512a5d891a35c1663392caryclark if (startT == 0) { 15781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[1].set(fPts[1]); 15791049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[2].set(fPts[2]); 1580cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1581cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 15821049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[1].set(fPts[2]); 15831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[2].set(fPts[1]); 1584cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1585cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1586cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT); 15881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (fVerb == SkPath::kConic_Verb) { 15891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2], 15901049f1246e7be4ccb68001361efceb8933e6f81ccaryclark startT, endT, &edge->fConic.fWeight); 1591cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } else { 1592cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 15931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]); 1594cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1595cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return true; 159607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 159707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 159827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclarkbool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, 159955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const { 160027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // average t, find mid pt 160127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark double midT = (prior->t() + spanBase->t()) / 2; 160227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkPoint midPt = this->ptAtT(midT); 160327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark bool coincident = true; 160427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // if the mid pt is not near either end pt, project perpendicular through opp seg 160527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) 160627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { 160755888e44171ffd48b591d19256884a969fe4da17caryclark if (priorPtT->span() == ptT->span()) { 160855888e44171ffd48b591d19256884a969fe4da17caryclark return false; 160955888e44171ffd48b591d19256884a969fe4da17caryclark } 161027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark coincident = false; 161127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkIntersections i; 161255888e44171ffd48b591d19256884a969fe4da17caryclark SkDCurve curvePart; 161355888e44171ffd48b591d19256884a969fe4da17caryclark this->subDivide(prior, spanBase, &curvePart); 161455888e44171ffd48b591d19256884a969fe4da17caryclark SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f); 161555888e44171ffd48b591d19256884a969fe4da17caryclark SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f); 161655888e44171ffd48b591d19256884a969fe4da17caryclark SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}}; 161755888e44171ffd48b591d19256884a969fe4da17caryclark SkDCurve oppPart; 161855888e44171ffd48b591d19256884a969fe4da17caryclark opp->subDivide(priorPtT->span(), ptT->span(), &oppPart); 161955888e44171ffd48b591d19256884a969fe4da17caryclark (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i); 162027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // measure distance and see if it's small enough to denote coincidence 162127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark for (int index = 0; index < i.used(); ++index) { 162255888e44171ffd48b591d19256884a969fe4da17caryclark if (!between(0, i[0][index], 1)) { 162355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 162455888e44171ffd48b591d19256884a969fe4da17caryclark } 162527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkDPoint oppPt = i.pt(index); 162630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (oppPt.approximatelyDEqual(midPt)) { 162755888e44171ffd48b591d19256884a969fe4da17caryclark // the coincidence can occur at almost any angle 162855888e44171ffd48b591d19256884a969fe4da17caryclark coincident = true; 162927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 163227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return coincident; 163327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 163427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 1635ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary ClarkSkOpSpan* SkOpSegment::undoneSpan() { 1636ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark SkOpSpan* span = &fHead; 1637ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark SkOpSpanBase* next; 163854359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1639ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark next = span->next(); 164054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->done()) { 1641ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark return span; 164207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1643ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark } while (!next->final() && (span = next->upCast())); 1644ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark return nullptr; 164507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 164607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 164754359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { 164854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* lesser = start->starter(end); 164954359294a7c9dc54802d512a5d891a35c1663392caryclark int oppWinding = lesser->oppSum(); 165054359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSpanWinding = SkOpSegment::OppSign(start, end); 165107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) 165207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && oppWinding != SK_MaxS32) { 165307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com oppWinding -= oppSpanWinding; 165407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 165507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return oppWinding; 165607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 165707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 165807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { 165954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* startSpan = angle->start(); 166054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* endSpan = angle->end(); 166154359294a7c9dc54802d512a5d891a35c1663392caryclark return updateOppWinding(endSpan, startSpan); 166207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 166307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 166407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { 166554359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* startSpan = angle->start(); 166654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* endSpan = angle->end(); 166754359294a7c9dc54802d512a5d891a35c1663392caryclark return updateOppWinding(startSpan, endSpan); 166807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 166907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1670624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 1671624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* lesser = start->starter(end); 167254359294a7c9dc54802d512a5d891a35c1663392caryclark int winding = lesser->windSum(); 16738cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (winding == SK_MinS32) { 1674bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark winding = lesser->computeWindSum(); 1675624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 1676624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (winding == SK_MinS32) { 16778cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return winding; 16788cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 167954359294a7c9dc54802d512a5d891a35c1663392caryclark int spanWinding = SkOpSegment::SpanSign(start, end); 1680570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (winding && UseInnerWinding(winding - spanWinding, winding) 1681570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com && winding != SK_MaxS32) { 168207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com winding -= spanWinding; 168307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 168407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return winding; 168507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 168607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1687624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWinding(SkOpAngle* angle) { 1688624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* startSpan = angle->start(); 1689624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* endSpan = angle->end(); 169054359294a7c9dc54802d512a5d891a35c1663392caryclark return updateWinding(endSpan, startSpan); 1691570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1692570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1693624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { 1694624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* startSpan = angle->start(); 1695624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* endSpan = angle->end(); 169654359294a7c9dc54802d512a5d891a35c1663392caryclark return updateWinding(startSpan, endSpan); 1697570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1698570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1699570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// OPTIMIZATION: does the following also work, and is it any faster? 1700570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// return outerWinding * innerWinding > 0 1701570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) 1702570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { 1703570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(outerWinding != SK_MaxS32); 1704570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(innerWinding != SK_MaxS32); 170560e0fee6d4acff638ccc9670c4055aced529a7a0bungeman int absOut = SkTAbs(outerWinding); 170660e0fee6d4acff638ccc9670c4055aced529a7a0bungeman int absIn = SkTAbs(innerWinding); 1707570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 1708570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return result; 1709570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1710570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 171107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::windSum(const SkOpAngle* angle) const { 171254359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* minSpan = angle->start()->starter(angle->end()); 171354359294a7c9dc54802d512a5d891a35c1663392caryclark return minSpan->windSum(); 171407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 1715