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 } 534431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return NULL; 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 } 944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return NULL; 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 16254359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, 16354359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathWriter* path, bool active) const { 1641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkOpCurve edge; 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkPoint* ePtr; 1661049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkScalar eWeight; 16754359294a7c9dc54802d512a5d891a35c1663392caryclark if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead)) { 16807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ePtr = fPts; 1691049f1246e7be4ccb68001361efceb8933e6f81ccaryclark eWeight = fWeight; 17007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 17107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZE? if not active, skip remainder and return xyAtT(end) 1721049f1246e7be4ccb68001361efceb8933e6f81ccaryclark subDivide(start, end, &edge); 1731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark ePtr = edge.fPts; 1741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark eWeight = edge.fWeight; 17507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (active) { 17754359294a7c9dc54802d512a5d891a35c1663392caryclark bool reverse = ePtr == fPts && start != &fHead; 17807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (reverse) { 179277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]); 18007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com switch (fVerb) { 18107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kLine_Verb: 18207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com path->deferredLine(ePtr[0]); 18307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 18407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kQuad_Verb: 18507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com path->quadTo(ePtr[1], ePtr[0]); 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 1871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark case SkPath::kConic_Verb: 1881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark path->conicTo(ePtr[1], ePtr[0], eWeight); 1891049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 19007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kCubic_Verb: 19107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com path->cubicTo(ePtr[2], ePtr[1], ePtr[0]); 19207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 19307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com default: 19407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(0); 19507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 19607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 19707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com path->deferredMoveLine(ePtr[0]); 19807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com switch (fVerb) { 19907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kLine_Verb: 20007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com path->deferredLine(ePtr[1]); 20107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 20207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kQuad_Verb: 20307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com path->quadTo(ePtr[1], ePtr[2]); 20407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 2051049f1246e7be4ccb68001361efceb8933e6f81ccaryclark case SkPath::kConic_Verb: 2061049f1246e7be4ccb68001361efceb8933e6f81ccaryclark path->conicTo(ePtr[1], ePtr[2], eWeight); 2071049f1246e7be4ccb68001361efceb8933e6f81ccaryclark break; 20807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kCubic_Verb: 20907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com path->cubicTo(ePtr[1], ePtr[2], ePtr[3]); 21007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 21107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com default: 21207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(0); 21307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 21707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 21854359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpPtT* SkOpSegment::addMissing(double t, SkOpSegment* opp, SkChunkAlloc* allocator) { 21954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* existing = NULL; 22054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* test = &fHead; 22154359294a7c9dc54802d512a5d891a35c1663392caryclark double testT; 2224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 22354359294a7c9dc54802d512a5d891a35c1663392caryclark if ((testT = test->ptT()->fT) >= t) { 22454359294a7c9dc54802d512a5d891a35c1663392caryclark if (testT == t) { 22554359294a7c9dc54802d512a5d891a35c1663392caryclark existing = test; 22654359294a7c9dc54802d512a5d891a35c1663392caryclark } 22754359294a7c9dc54802d512a5d891a35c1663392caryclark break; 22854359294a7c9dc54802d512a5d891a35c1663392caryclark } 22954359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = test->upCast()->next())); 23054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* result; 23154359294a7c9dc54802d512a5d891a35c1663392caryclark if (existing && existing->contains(opp)) { 23254359294a7c9dc54802d512a5d891a35c1663392caryclark result = existing->ptT(); 23354359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 23454359294a7c9dc54802d512a5d891a35c1663392caryclark result = this->addT(t, SkOpSegment::kNoAlias, allocator); 23507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 23654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(result); 23754359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 23807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 23907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 24054359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* allocator) { 24154359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 24254359294a7c9dc54802d512a5d891a35c1663392caryclark SkPoint pt = this->ptAtT(t); 24354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* span = &fHead; 2444431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 24554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* result = span->ptT(); 24608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* loop; 24708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark bool duplicatePt; 24854359294a7c9dc54802d512a5d891a35c1663392caryclark if (t == result->fT) { 24908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto bumpSpan; 25054359294a7c9dc54802d512a5d891a35c1663392caryclark } 25154359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->match(result, this, t, pt)) { 25254359294a7c9dc54802d512a5d891a35c1663392caryclark // see if any existing alias matches segment, pt, and t 25308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark loop = result->next(); 25408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark duplicatePt = false; 25554359294a7c9dc54802d512a5d891a35c1663392caryclark while (loop != result) { 25654359294a7c9dc54802d512a5d891a35c1663392caryclark bool ptMatch = loop->fPt == pt; 25754359294a7c9dc54802d512a5d891a35c1663392caryclark if (loop->segment() == this && loop->fT == t && ptMatch) { 25808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto bumpSpan; 25954359294a7c9dc54802d512a5d891a35c1663392caryclark } 26054359294a7c9dc54802d512a5d891a35c1663392caryclark duplicatePt |= ptMatch; 26154359294a7c9dc54802d512a5d891a35c1663392caryclark loop = loop->next(); 26254359294a7c9dc54802d512a5d891a35c1663392caryclark } 26354359294a7c9dc54802d512a5d891a35c1663392caryclark if (kNoAlias == allowAlias) { 26408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark bumpSpan: 26508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark span->bumpSpanAdds(); 26654359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 26754359294a7c9dc54802d512a5d891a35c1663392caryclark } 26854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator); 26954359294a7c9dc54802d512a5d891a35c1663392caryclark alias->init(result->span(), t, pt, duplicatePt); 27054359294a7c9dc54802d512a5d891a35c1663392caryclark result->insert(alias); 27154359294a7c9dc54802d512a5d891a35c1663392caryclark result->span()->unaligned(); 27254359294a7c9dc54802d512a5d891a35c1663392caryclark this->debugValidate(); 27354359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_ADD_T 27454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, 27554359294a7c9dc54802d512a5d891a35c1663392caryclark alias->segment()->debugID(), alias->span()->debugID()); 27654359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 27708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark span->bumpSpanAdds(); 27854359294a7c9dc54802d512a5d891a35c1663392caryclark return alias; 27954359294a7c9dc54802d512a5d891a35c1663392caryclark } 28054359294a7c9dc54802d512a5d891a35c1663392caryclark if (t < result->fT) { 28154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prev = result->span()->prev(); 28254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* span = insert(prev, allocator); 28354359294a7c9dc54802d512a5d891a35c1663392caryclark span->init(this, prev, t, pt); 28454359294a7c9dc54802d512a5d891a35c1663392caryclark this->debugValidate(); 28554359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_ADD_T 28654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, 28754359294a7c9dc54802d512a5d891a35c1663392caryclark span->segment()->debugID(), span->debugID()); 28854359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 28908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark span->bumpSpanAdds(); 29054359294a7c9dc54802d512a5d891a35c1663392caryclark return span->ptT(); 29154359294a7c9dc54802d512a5d891a35c1663392caryclark } 29254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span != &fTail); 29354359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((span = span->upCast()->next())); 29454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(0); 29554359294a7c9dc54802d512a5d891a35c1663392caryclark return NULL; 2964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 2974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 29854359294a7c9dc54802d512a5d891a35c1663392caryclark// choose a solitary t and pt value; remove aliases; align the opposite ends 29954359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::align() { 30054359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 30154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* span = &fHead; 30254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->aligned()) { 30354359294a7c9dc54802d512a5d891a35c1663392caryclark span->alignEnd(0, fPts[0]); 30454359294a7c9dc54802d512a5d891a35c1663392caryclark } 30554359294a7c9dc54802d512a5d891a35c1663392caryclark while ((span = span->upCast()->next())) { 30654359294a7c9dc54802d512a5d891a35c1663392caryclark if (span == &fTail) { 30707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 30807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 30954359294a7c9dc54802d512a5d891a35c1663392caryclark span->align(); 31007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 31154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->aligned()) { 31254359294a7c9dc54802d512a5d891a35c1663392caryclark span->alignEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]); 31307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 314bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (this->collapsed()) { 315bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* span = &fHead; 316bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark do { 317bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark span->setWindValue(0); 318bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark span->setOppValue(0); 319bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark this->markDone(span); 320bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } while ((span = span->next()->upCastable())); 321bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 32254359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 32354359294a7c9dc54802d512a5d891a35c1663392caryclark} 32454359294a7c9dc54802d512a5d891a35c1663392caryclark 32554359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::calcAngles(SkChunkAlloc* allocator) { 32654359294a7c9dc54802d512a5d891a35c1663392caryclark bool activePrior = !fHead.isCanceled(); 32754359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior && !fHead.simple()) { 32854359294a7c9dc54802d512a5d891a35c1663392caryclark addStartSpan(allocator); 3290dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 33054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prior = &fHead; 33154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* spanBase = fHead.next(); 33254359294a7c9dc54802d512a5d891a35c1663392caryclark while (spanBase != &fTail) { 33354359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior) { 33454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); 33554359294a7c9dc54802d512a5d891a35c1663392caryclark priorAngle->set(spanBase, prior); 33654359294a7c9dc54802d512a5d891a35c1663392caryclark spanBase->setFromAngle(priorAngle); 337ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 33854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* span = spanBase->upCast(); 33954359294a7c9dc54802d512a5d891a35c1663392caryclark bool active = !span->isCanceled(); 34054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = span->next(); 34154359294a7c9dc54802d512a5d891a35c1663392caryclark if (active) { 34254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); 34354359294a7c9dc54802d512a5d891a35c1663392caryclark angle->set(span, next); 34454359294a7c9dc54802d512a5d891a35c1663392caryclark span->setToAngle(angle); 34554359294a7c9dc54802d512a5d891a35c1663392caryclark } 34654359294a7c9dc54802d512a5d891a35c1663392caryclark activePrior = active; 34754359294a7c9dc54802d512a5d891a35c1663392caryclark prior = span; 34854359294a7c9dc54802d512a5d891a35c1663392caryclark spanBase = next; 3494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 35054359294a7c9dc54802d512a5d891a35c1663392caryclark if (activePrior && !fTail.simple()) { 35154359294a7c9dc54802d512a5d891a35c1663392caryclark addEndSpan(allocator); 3524431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 35365f553182ab7069378ef863d30094d0327f178d0caryclark} 35465f553182ab7069378ef863d30094d0327f178d0caryclark 35554359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::checkAngleCoin(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) { 35654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* base = &fHead; 35754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* span; 35865f553182ab7069378ef863d30094d0327f178d0caryclark do { 35954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = base->fromAngle(); 36054359294a7c9dc54802d512a5d891a35c1663392caryclark if (angle && angle->fCheckCoincidence) { 36154359294a7c9dc54802d512a5d891a35c1663392caryclark angle->checkNearCoincidence(); 36265f553182ab7069378ef863d30094d0327f178d0caryclark } 36354359294a7c9dc54802d512a5d891a35c1663392caryclark if (base->final()) { 36454359294a7c9dc54802d512a5d891a35c1663392caryclark break; 36565f553182ab7069378ef863d30094d0327f178d0caryclark } 36654359294a7c9dc54802d512a5d891a35c1663392caryclark span = base->upCast(); 36754359294a7c9dc54802d512a5d891a35c1663392caryclark angle = span->toAngle(); 36854359294a7c9dc54802d512a5d891a35c1663392caryclark if (angle && angle->fCheckCoincidence) { 36954359294a7c9dc54802d512a5d891a35c1663392caryclark angle->checkNearCoincidence(); 37065f553182ab7069378ef863d30094d0327f178d0caryclark } 37154359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((base = span->next())); 37207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 37307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 374bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclarkbool SkOpSegment::collapsed() const { 375bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark return fVerb == SkPath::kLine_Verb && fHead.pt() == fTail.pt(); 376bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark} 377bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark 37854359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 37954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 380624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* baseSegment = baseAngle->segment(); 38154359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); 38254359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding; 38354359294a7c9dc54802d512a5d891a35c1663392caryclark bool binary = includeType >= SkOpAngle::kBinarySingle; 38454359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 38554359294a7c9dc54802d512a5d891a35c1663392caryclark sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); 38654359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseSegment->operand()) { 38754359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap<int>(sumMiWinding, sumSuWinding); 3880dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 38954359294a7c9dc54802d512a5d891a35c1663392caryclark } 39054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* nextSegment = nextAngle->segment(); 39154359294a7c9dc54802d512a5d891a35c1663392caryclark int maxWinding, sumWinding; 39254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 39354359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 39454359294a7c9dc54802d512a5d891a35c1663392caryclark int oppMaxWinding, oppSumWinding; 39554359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 39654359294a7c9dc54802d512a5d891a35c1663392caryclark &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 39754359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 39854359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle); 3994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 40054359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 40154359294a7c9dc54802d512a5d891a35c1663392caryclark &maxWinding, &sumWinding); 40254359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 4034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 40454359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle->setLastMarked(last); 4054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 4064431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 407624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkvoid SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, 40854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 409624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* baseSegment = baseAngle->segment(); 41054359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = baseSegment->updateWinding(baseAngle); 41154359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding; 41254359294a7c9dc54802d512a5d891a35c1663392caryclark bool binary = includeType >= SkOpAngle::kBinarySingle; 4130dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed if (binary) { 41454359294a7c9dc54802d512a5d891a35c1663392caryclark sumSuWinding = baseSegment->updateOppWinding(baseAngle); 41554359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseSegment->operand()) { 41654359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap<int>(sumMiWinding, sumSuWinding); 4170dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 4180dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 41954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* nextSegment = nextAngle->segment(); 42054359294a7c9dc54802d512a5d891a35c1663392caryclark int maxWinding, sumWinding; 42154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 42254359294a7c9dc54802d512a5d891a35c1663392caryclark if (binary) { 42354359294a7c9dc54802d512a5d891a35c1663392caryclark int oppMaxWinding, oppSumWinding; 42454359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 42554359294a7c9dc54802d512a5d891a35c1663392caryclark &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 42654359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 42754359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle); 4284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else { 42954359294a7c9dc54802d512a5d891a35c1663392caryclark nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 43054359294a7c9dc54802d512a5d891a35c1663392caryclark &maxWinding, &sumWinding); 43154359294a7c9dc54802d512a5d891a35c1663392caryclark last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 4320dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 43354359294a7c9dc54802d512a5d891a35c1663392caryclark nextAngle->setLastMarked(last); 4344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 4354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 436dac1d17027dcaa5596885a9f333979418b35001ccaryclark// at this point, the span is already ordered, or unorderable 43754359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, 43854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle::IncludeType includeType) { 4394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(includeType != SkOpAngle::kUnaryXor); 44054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* firstAngle = this->spanToAngle(end, start); 44165b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark if (NULL == firstAngle || NULL == firstAngle->next()) { 4424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return SK_NaN32; 443570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 444570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // if all angles have a computed winding, 445570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // or if no adjacent angles are orderable, 446570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // or if adjacent orderable angles have no computed winding, 447570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // there's nothing to do 448dac1d17027dcaa5596885a9f333979418b35001ccaryclark // if two orderable angles are adjacent, and both are next to orderable angles, 449dac1d17027dcaa5596885a9f333979418b35001ccaryclark // and one has winding computed, transfer to the other 4504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* baseAngle = NULL; 451570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool tryReverse = false; 452570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // look for counterclockwise transfers 453dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* angle = firstAngle->previous(); 454dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* next = angle->next(); 455dac1d17027dcaa5596885a9f333979418b35001ccaryclark firstAngle = next; 45607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 457dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* prior = angle; 458dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle = next; 459dac1d17027dcaa5596885a9f333979418b35001ccaryclark next = angle->next(); 460dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(prior->next() == angle); 461dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(angle->next() == next); 462dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 463dac1d17027dcaa5596885a9f333979418b35001ccaryclark baseAngle = NULL; 4644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4654431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 46654359294a7c9dc54802d512a5d891a35c1663392caryclark int testWinding = angle->starter()->windSum(); 467dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (SK_MinS32 != testWinding) { 468dac1d17027dcaa5596885a9f333979418b35001ccaryclark baseAngle = angle; 4694431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tryReverse = true; 4704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 4714431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (baseAngle) { 4734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ComputeOneSum(baseAngle, angle, includeType); 47454359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : NULL; 4754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 476dac1d17027dcaa5596885a9f333979418b35001ccaryclark } while (next != firstAngle); 47754359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) { 4784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org firstAngle = baseAngle; 4794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org tryReverse = true; 4804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 4814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (tryReverse) { 4824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org baseAngle = NULL; 483dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpAngle* prior = firstAngle; 484570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com do { 485dac1d17027dcaa5596885a9f333979418b35001ccaryclark angle = prior; 486dac1d17027dcaa5596885a9f333979418b35001ccaryclark prior = angle->previous(); 487dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(prior->next() == angle); 488dac1d17027dcaa5596885a9f333979418b35001ccaryclark next = angle->next(); 489dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 490dac1d17027dcaa5596885a9f333979418b35001ccaryclark baseAngle = NULL; 491dac1d17027dcaa5596885a9f333979418b35001ccaryclark continue; 492dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 49354359294a7c9dc54802d512a5d891a35c1663392caryclark int testWinding = angle->starter()->windSum(); 4944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (SK_MinS32 != testWinding) { 4954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org baseAngle = angle; 496570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com continue; 49707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 498570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (baseAngle) { 4994431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org ComputeOneSumReverse(baseAngle, angle, includeType); 50054359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : NULL; 501570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 502dac1d17027dcaa5596885a9f333979418b35001ccaryclark } while (prior != firstAngle); 503570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 50454359294a7c9dc54802d512a5d891a35c1663392caryclark return start->starter(end)->windSum(); 50507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 50607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 50754359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::detach(const SkOpSpan* span) { 50854359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 50908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark --fDoneCount; 510ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 51108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark --fCount; 51208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkASSERT(fCount >= fDoneCount); 5130dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed} 5140dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed 51554359294a7c9dc54802d512a5d891a35c1663392caryclarkdouble SkOpSegment::distSq(double t, SkOpAngle* oppAngle) { 51654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint testPt = this->dPtAtT(t); 51754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine testPerp = {{ testPt, testPt }}; 51854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector slope = this->dSlopeAtT(t); 51954359294a7c9dc54802d512a5d891a35c1663392caryclark testPerp[1].fX += slope.fY; 52054359294a7c9dc54802d512a5d891a35c1663392caryclark testPerp[1].fY -= slope.fX; 52154359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 52254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* oppSegment = oppAngle->segment(); 5231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); 52454359294a7c9dc54802d512a5d891a35c1663392caryclark double closestDistSq = SK_ScalarInfinity; 52554359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < i.used(); ++index) { 52654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { 52754359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 5280dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 52954359294a7c9dc54802d512a5d891a35c1663392caryclark double testDistSq = testPt.distanceSquared(i.pt(index)); 53054359294a7c9dc54802d512a5d891a35c1663392caryclark if (closestDistSq > testDistSq) { 53154359294a7c9dc54802d512a5d891a35c1663392caryclark closestDistSq = testDistSq; 5320dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 53354359294a7c9dc54802d512a5d891a35c1663392caryclark } 53454359294a7c9dc54802d512a5d891a35c1663392caryclark return closestDistSq; 5354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 5364431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 53707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 53807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com The M and S variable name parts stand for the operators. 53907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Mi stands for Minuend (see wiki subtraction, analogous to difference) 54007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Su stands for Subtrahend 54107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com The Opp variable name part designates that the value is for the Opposite operator. 54207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Opposite values result from combining coincident spans. 54307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 54454359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 54554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) { 54654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 54754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 54854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 54954359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 55054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 55154359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 55207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // mark the smaller of startIndex, endIndex done, and all adjacent 55307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // spans with the same T value (but not 'other' spans) 55407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 55507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 55607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 55754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 55854359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 559cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return NULL; 560cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 56154359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 56254359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 56307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 56407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 56554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 56654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 56754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 56854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 56954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 5704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // more than one viable candidate -- measure angles to find best 57154359294a7c9dc54802d512a5d891a35c1663392caryclark int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp); 572570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool sortable = calcWinding != SK_NaN32; 5734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!sortable) { 5747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com *unsortable = true; 57554359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 5767eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return NULL; 5777eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 57854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 5794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (angle->unorderable()) { 58007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *unsortable = true; 58154359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 58207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return NULL; 58307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 5854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 5864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 58707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 58854359294a7c9dc54802d512a5d891a35c1663392caryclark int sumMiWinding = updateWinding(end, start); 5898cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (sumMiWinding == SK_MinS32) { 5908cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org *unsortable = true; 59154359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 5928cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return NULL; 5938cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 59454359294a7c9dc54802d512a5d891a35c1663392caryclark int sumSuWinding = updateOppWinding(end, start); 59507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 59607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap<int>(sumMiWinding, sumSuWinding); 59707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 59907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkOpAngle* foundAngle = NULL; 60007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 60107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // iterate through the angle, and compute everyone's winding 60207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 60307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 60407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 60507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 60607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), 6074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nextAngle->end(), op, &sumMiWinding, &sumSuWinding); 60807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (activeAngle) { 60907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 61007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 61107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 612570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com foundDone = nextSegment->done(nextAngle); 61307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 61407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 61507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (nextSegment->done()) { 61607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 61707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 618570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!activeAngle) { 61954359294a7c9dc54802d512a5d891a35c1663392caryclark (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 620570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 62154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = nextAngle->lastMarked(); 62207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (last) { 6234431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 62407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *chase->append() = last; 62507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 62654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 62754359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 62854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 62954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum=%d", last->upCast()->windSum()); 63054359294a7c9dc54802d512a5d891a35c1663392caryclark } 63154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 63207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 63307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while ((nextAngle = nextAngle->next()) != angle); 63554359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 63607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 63707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return NULL; 63807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 63907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 64007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 64107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 64207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 64307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 64407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 64507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 64607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 64707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 64807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 64954359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase, 65054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { 65154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 65254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 65354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 65454359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 65554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 65654359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 65707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // mark the smaller of startIndex, endIndex done, and all adjacent 65807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // spans with the same T value (but not 'other' spans) 65907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 66007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 66107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 66254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 66354359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 664570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return NULL; 665570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 66654359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 66754359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 66807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 66907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 67054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 67154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 67254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 67354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 67454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 6754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // more than one viable candidate -- measure angles to find best 67654359294a7c9dc54802d512a5d891a35c1663392caryclark int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding); 677570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool sortable = calcWinding != SK_NaN32; 67807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!sortable) { 67907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *unsortable = true; 68054359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 68154359294a7c9dc54802d512a5d891a35c1663392caryclark return NULL; 68254359294a7c9dc54802d512a5d891a35c1663392caryclark } 68354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 68454359294a7c9dc54802d512a5d891a35c1663392caryclark if (angle->unorderable()) { 68554359294a7c9dc54802d512a5d891a35c1663392caryclark *unsortable = true; 68654359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 68707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return NULL; 68807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6894431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 6904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 6914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 69207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 69354359294a7c9dc54802d512a5d891a35c1663392caryclark int sumWinding = updateWinding(end, start); 6944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 69507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkOpAngle* foundAngle = NULL; 69607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 69754359294a7c9dc54802d512a5d891a35c1663392caryclark // iterate through the angle, and compute everyone's winding 69807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 69907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 70007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 70107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 70207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), 7034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org &sumWinding); 70407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (activeAngle) { 70507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 70607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 70707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 70807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundDone = nextSegment->done(nextAngle); 70907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 71007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 71107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (nextSegment->done()) { 71207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 71307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 714570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!activeAngle) { 71554359294a7c9dc54802d512a5d891a35c1663392caryclark (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 716570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 71754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = nextAngle->lastMarked(); 71807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (last) { 7194431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 72007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *chase->append() = last; 72107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 72254359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 72354359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 72454359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 72554359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum=%d", last->upCast()->windSum()); 72654359294a7c9dc54802d512a5d891a35c1663392caryclark } 72754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 72807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 72907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7304431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while ((nextAngle = nextAngle->next()) != angle); 73154359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 73207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 73307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return NULL; 73407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 73507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 73607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 73707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 73807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 73907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 74007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 74107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 74207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 74307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 74407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 74554359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, 74654359294a7c9dc54802d512a5d891a35c1663392caryclark bool* unsortable) { 74754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* start = *nextStart; 74854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* end = *nextEnd; 74954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != end); 75054359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 75154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 75254359294a7c9dc54802d512a5d891a35c1663392caryclark if (other) { 75354359294a7c9dc54802d512a5d891a35c1663392caryclark // mark the smaller of startIndex, endIndex done, and all adjacent 75454359294a7c9dc54802d512a5d891a35c1663392caryclark // spans with the same T value (but not 'other' spans) 75507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 75607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s simple\n", __FUNCTION__); 75707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 75854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* startSpan = start->starter(end); 75954359294a7c9dc54802d512a5d891a35c1663392caryclark if (startSpan->done()) { 76007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return NULL; 76107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 76254359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(startSpan); 76354359294a7c9dc54802d512a5d891a35c1663392caryclark *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 76407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 76507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 76654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \ 76754359294a7c9dc54802d512a5d891a35c1663392caryclark : (*nextStart)->prev()); 76854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear == end); // is this ever not end? 76954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endNear); 77054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start != endNear); 77154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 77254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = this->spanToAngle(end, start); 77354359294a7c9dc54802d512a5d891a35c1663392caryclark if (angle->unorderable()) { 77454359294a7c9dc54802d512a5d891a35c1663392caryclark *unsortable = true; 77554359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(start->starter(end)); 77654359294a7c9dc54802d512a5d891a35c1663392caryclark return NULL; 77754359294a7c9dc54802d512a5d891a35c1663392caryclark } 7784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 7794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkDebugf("%s\n", __FUNCTION__); 7804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org angle->debugLoop(); 781570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 7824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpAngle* nextAngle = angle->next(); 78307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkOpAngle* foundAngle = NULL; 78407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundDone = false; 78554359294a7c9dc54802d512a5d891a35c1663392caryclark // iterate through the angle, and compute everyone's winding 78607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* nextSegment; 78707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int activeCount = 0; 78807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 78907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = nextAngle->segment(); 79007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++activeCount; 79107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle || (foundDone && activeCount & 1)) { 79207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundAngle = nextAngle; 7934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!(foundDone = nextSegment->done(nextAngle))) { 7944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org break; 7954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 79607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org nextAngle = nextAngle->next(); 7984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } while (nextAngle != angle); 79954359294a7c9dc54802d512a5d891a35c1663392caryclark start->segment()->markDone(start->starter(end)); 80007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!foundAngle) { 80107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return NULL; 80207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 80307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextStart = foundAngle->start(); 80407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *nextEnd = foundAngle->end(); 80507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com nextSegment = foundAngle->segment(); 80607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_WINDING 80707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 80807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 80907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 81007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return nextSegment; 81107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 81207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 81354359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpGlobalState* SkOpSegment::globalState() const { 81454359294a7c9dc54802d512a5d891a35c1663392caryclark return contour()->globalState(); 81565f553182ab7069378ef863d30094d0327f178d0caryclark} 81665f553182ab7069378ef863d30094d0327f178d0caryclark 8171049f1246e7be4ccb68001361efceb8933e6f81ccaryclarkvoid SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { 81854359294a7c9dc54802d512a5d891a35c1663392caryclark fContour = contour; 81954359294a7c9dc54802d512a5d891a35c1663392caryclark fNext = NULL; 82007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fPts = pts; 8211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark fWeight = weight; 82207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fVerb = verb; 82303b03cad01628146bbb8d4f33c073bd0c77ee558caryclark fCubicType = SkDCubic::kUnsplit_SkDCubicType; 82454359294a7c9dc54802d512a5d891a35c1663392caryclark fCount = 0; 82554359294a7c9dc54802d512a5d891a35c1663392caryclark fDoneCount = 0; 826624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fTopsFound = false; 82754359294a7c9dc54802d512a5d891a35c1663392caryclark fVisited = false; 82854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* zeroSpan = &fHead; 82954359294a7c9dc54802d512a5d891a35c1663392caryclark zeroSpan->init(this, NULL, 0, fPts[0]); 83054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oneSpan = &fTail; 83154359294a7c9dc54802d512a5d891a35c1663392caryclark zeroSpan->setNext(oneSpan); 83254359294a7c9dc54802d512a5d891a35c1663392caryclark oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); 8331049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(fID = globalState()->nextSegmentID()); 83454359294a7c9dc54802d512a5d891a35c1663392caryclark} 83554359294a7c9dc54802d512a5d891a35c1663392caryclark 83654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { 83754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint cPt = this->dPtAtT(t); 8381049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); 83954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 84054359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 8411049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i); 84254359294a7c9dc54802d512a5d891a35c1663392caryclark int used = i.used(); 84354359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < used; ++index) { 84454359294a7c9dc54802d512a5d891a35c1663392caryclark if (cPt.roughlyEqual(i.pt(index))) { 8450dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed return true; 8460dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 84754359294a7c9dc54802d512a5d891a35c1663392caryclark } 848a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return false; 849a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com} 850a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 85154359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::isXor() const { 85254359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->isXor(); 85307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 85407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 85554359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) { 85654359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 85754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* minSpan = start->starter(end); 85854359294a7c9dc54802d512a5d891a35c1663392caryclark markDone(minSpan); 85954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = NULL; 86007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* other = this; 86154359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &minSpan, &last))) { 86207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (other->done()) { 863dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 864dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 86507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 86654359294a7c9dc54802d512a5d891a35c1663392caryclark other->markDone(minSpan); 86707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 86807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 86907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 87007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 87154359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 87254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** lastPtr) { 87354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* spanStart = start->starter(end); 87454359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 87554359294a7c9dc54802d512a5d891a35c1663392caryclark bool success = markWinding(spanStart, winding); 87654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = NULL; 8774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkOpSegment* other = this; 87854359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 87954359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart->windSum() != SK_MinS32) { 88054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->windSum() == winding); 881dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 882dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 8834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 88454359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, winding); 8856f726addf3178b01949bb389ef83cf14a1d7b6b2caryclark } 88665f553182ab7069378ef863d30094d0327f178d0caryclark if (lastPtr) { 88765f553182ab7069378ef863d30094d0327f178d0caryclark *lastPtr = last; 88865f553182ab7069378ef863d30094d0327f178d0caryclark } 88965f553182ab7069378ef863d30094d0327f178d0caryclark return success; 8904431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org} 8914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 89254359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, 89354359294a7c9dc54802d512a5d891a35c1663392caryclark int winding, int oppWinding, SkOpSpanBase** lastPtr) { 89454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* spanStart = start->starter(end); 89554359294a7c9dc54802d512a5d891a35c1663392caryclark int step = start->step(end); 89654359294a7c9dc54802d512a5d891a35c1663392caryclark bool success = markWinding(spanStart, winding, oppWinding); 89754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = NULL; 89807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpSegment* other = this; 89954359294a7c9dc54802d512a5d891a35c1663392caryclark while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 90054359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanStart->windSum() != SK_MinS32) { 90154359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand() == other->operand()) { 902624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { 90354359294a7c9dc54802d512a5d891a35c1663392caryclark this->globalState()->setWindingFailed(); 90454359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 905dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 90654359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 90754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->windSum() == oppWinding); 90854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(spanStart->oppSum() == winding); 909dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 910dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(!last); 911dac1d17027dcaa5596885a9f333979418b35001ccaryclark break; 912dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 91354359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->operand() == other->operand()) { 91454359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, winding, oppWinding); 915dac1d17027dcaa5596885a9f333979418b35001ccaryclark } else { 91654359294a7c9dc54802d512a5d891a35c1663392caryclark (void) other->markWinding(spanStart, oppWinding, winding); 91707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 91807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 91965f553182ab7069378ef863d30094d0327f178d0caryclark if (lastPtr) { 92065f553182ab7069378ef863d30094d0327f178d0caryclark *lastPtr = last; 92165f553182ab7069378ef863d30094d0327f178d0caryclark } 92265f553182ab7069378ef863d30094d0327f178d0caryclark return success; 92307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 92407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 92554359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) { 92607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(angle->segment() == this); 92707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (UseInnerWinding(maxWinding, sumWinding)) { 92807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com maxWinding = sumWinding; 92907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 93054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last; 93154359294a7c9dc54802d512a5d891a35c1663392caryclark (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last); 932570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_WINDING 933570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (last) { 93454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s last seg=%d span=%d", __FUNCTION__, 93554359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 93654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 93754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum="); 93854359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 93954359294a7c9dc54802d512a5d891a35c1663392caryclark } 94054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("\n"); 941570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 942570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 94307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 94407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 94507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 94654359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, 94754359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSumWinding, const SkOpAngle* angle) { 94807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(angle->segment() == this); 94907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (UseInnerWinding(maxWinding, sumWinding)) { 95007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com maxWinding = sumWinding; 95107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 95207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { 95307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com oppMaxWinding = oppSumWinding; 95407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 95554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* last = NULL; 95665f553182ab7069378ef863d30094d0327f178d0caryclark // caller doesn't require that this marks anything 95754359294a7c9dc54802d512a5d891a35c1663392caryclark (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last); 958570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_WINDING 959570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (last) { 96054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s last segment=%d span=%d", __FUNCTION__, 96154359294a7c9dc54802d512a5d891a35c1663392caryclark last->segment()->debugID(), last->debugID()); 96254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!last->final()) { 96354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" windSum="); 96454359294a7c9dc54802d512a5d891a35c1663392caryclark SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 96554359294a7c9dc54802d512a5d891a35c1663392caryclark } 96654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf(" \n"); 967570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 968570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 96907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return last; 97007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 97107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 97254359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::markDone(SkOpSpan* span) { 97354359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 97454359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 9750dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed return; 9760dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 97754359294a7c9dc54802d512a5d891a35c1663392caryclark#if DEBUG_MARK_DONE 97854359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum()); 97954359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 98054359294a7c9dc54802d512a5d891a35c1663392caryclark span->setDone(true); 98154359294a7c9dc54802d512a5d891a35c1663392caryclark ++fDoneCount; 98254359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 9830dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed} 9840dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed 98554359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markWinding(SkOpSpan* span, int winding) { 98654359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 98754359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(winding); 98854359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 98965f553182ab7069378ef863d30094d0327f178d0caryclark return false; 99007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 99107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_MARK_DONE 99254359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, winding); 9930dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed#endif 99454359294a7c9dc54802d512a5d891a35c1663392caryclark span->setWindSum(winding); 99554359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 99665f553182ab7069378ef863d30094d0327f178d0caryclark return true; 99707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 99807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 99954359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { 100054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(this == span->segment()); 100154359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(winding || oppWinding); 100254359294a7c9dc54802d512a5d891a35c1663392caryclark if (span->done()) { 100365f553182ab7069378ef863d30094d0327f178d0caryclark return false; 100407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 100507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_MARK_DONE 100654359294a7c9dc54802d512a5d891a35c1663392caryclark debugShowNewWinding(__FUNCTION__, span, winding, oppWinding); 10078cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org#endif 100854359294a7c9dc54802d512a5d891a35c1663392caryclark span->setWindSum(winding); 100954359294a7c9dc54802d512a5d891a35c1663392caryclark span->setOppSum(oppWinding); 10104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org debugValidate(); 101165f553182ab7069378ef863d30094d0327f178d0caryclark return true; 101207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 101307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 101454359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, 101554359294a7c9dc54802d512a5d891a35c1663392caryclark const SkPoint& testPt) const { 101654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSegment* baseParent = base->segment(); 101754359294a7c9dc54802d512a5d891a35c1663392caryclark if (this == baseParent && this == testParent && precisely_equal(base->fT, testT)) { 101854359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 101907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 102054359294a7c9dc54802d512a5d891a35c1663392caryclark if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { 102154359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 1022e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 102308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark return !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); 102454359294a7c9dc54802d512a5d891a35c1663392caryclark} 102554359294a7c9dc54802d512a5d891a35c1663392caryclark 102654359294a7c9dc54802d512a5d891a35c1663392caryclarkstatic SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { 102754359294a7c9dc54802d512a5d891a35c1663392caryclark if (last) { 102854359294a7c9dc54802d512a5d891a35c1663392caryclark *last = endSpan; 102907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 103054359294a7c9dc54802d512a5d891a35c1663392caryclark return NULL; 103107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 103207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 103354359294a7c9dc54802d512a5d891a35c1663392caryclarkSkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, 103454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase** last) const { 103554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* origStart = *startPtr; 1036dac1d17027dcaa5596885a9f333979418b35001ccaryclark int step = *stepPtr; 103754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev(); 103854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(endSpan); 103954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle(); 104054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* foundSpan; 104154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* otherEnd; 1042dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkOpSegment* other; 1043dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (angle == NULL) { 104454359294a7c9dc54802d512a5d891a35c1663392caryclark if (endSpan->t() != 0 && endSpan->t() != 1) { 1045dac1d17027dcaa5596885a9f333979418b35001ccaryclark return NULL; 1046dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 104754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* otherPtT = endSpan->ptT()->next(); 104854359294a7c9dc54802d512a5d891a35c1663392caryclark other = otherPtT->segment(); 104954359294a7c9dc54802d512a5d891a35c1663392caryclark foundSpan = otherPtT->span(); 105054359294a7c9dc54802d512a5d891a35c1663392caryclark otherEnd = step > 0 ? foundSpan->upCast()->next() : foundSpan->prev(); 1051dac1d17027dcaa5596885a9f333979418b35001ccaryclark } else { 1052dac1d17027dcaa5596885a9f333979418b35001ccaryclark int loopCount = angle->loopCount(); 1053dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (loopCount > 2) { 105454359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 1055dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 1056dac1d17027dcaa5596885a9f333979418b35001ccaryclark const SkOpAngle* next = angle->next(); 105765b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark if (NULL == next) { 105865b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark return NULL; 105965b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark } 1060dac1d17027dcaa5596885a9f333979418b35001ccaryclark#if DEBUG_WINDING 1061624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() 106254359294a7c9dc54802d512a5d891a35c1663392caryclark && !next->segment()->contour()->isXor()) { 1063dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDebugf("%s mismatched signs\n", __FUNCTION__); 10640dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 106554359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 1066dac1d17027dcaa5596885a9f333979418b35001ccaryclark other = next->segment(); 106754359294a7c9dc54802d512a5d891a35c1663392caryclark foundSpan = endSpan = next->start(); 1068dac1d17027dcaa5596885a9f333979418b35001ccaryclark otherEnd = next->end(); 1069570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 107054359294a7c9dc54802d512a5d891a35c1663392caryclark int foundStep = foundSpan->step(otherEnd); 1071dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (*stepPtr != foundStep) { 107254359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 107307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 107454359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(*startPtr); 107554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!otherEnd) { 107665b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark return NULL; 107765b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark } 107865b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark// SkASSERT(otherEnd >= 0); 107954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast(); 108054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* foundMin = foundSpan->starter(otherEnd); 108154359294a7c9dc54802d512a5d891a35c1663392caryclark if (foundMin->windValue() != origMin->windValue() 108254359294a7c9dc54802d512a5d891a35c1663392caryclark || foundMin->oppValue() != origMin->oppValue()) { 108354359294a7c9dc54802d512a5d891a35c1663392caryclark return set_last(last, endSpan); 1084dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 108554359294a7c9dc54802d512a5d891a35c1663392caryclark *startPtr = foundSpan; 1086dac1d17027dcaa5596885a9f333979418b35001ccaryclark *stepPtr = foundStep; 1087dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (minPtr) { 1088dac1d17027dcaa5596885a9f333979418b35001ccaryclark *minPtr = foundMin; 1089a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 109007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return other; 109107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 109207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1093bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclarkstatic void clear_visited(SkOpSpanBase* span) { 109454359294a7c9dc54802d512a5d891a35c1663392caryclark // reset visited flag back to false 109554359294a7c9dc54802d512a5d891a35c1663392caryclark do { 109654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 109754359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != stopPtT) { 109854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* opp = ptT->segment(); 109954359294a7c9dc54802d512a5d891a35c1663392caryclark opp->resetVisited(); 110007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1101bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } while (!span->final() && (span = span->upCast()->next())); 110207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 110307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 110454359294a7c9dc54802d512a5d891a35c1663392caryclark// look for pairs of undetected coincident curves 110554359294a7c9dc54802d512a5d891a35c1663392caryclark// assumes that segments going in have visited flag clear 110654359294a7c9dc54802d512a5d891a35c1663392caryclark// curve/curve intersection should now do a pretty good job of finding coincident runs so 110754359294a7c9dc54802d512a5d891a35c1663392caryclark// this may be only be necessary for line/curve pairs -- so skip unless this is a line and the 110854359294a7c9dc54802d512a5d891a35c1663392caryclark// the opp is not a line 110954359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) { 111054359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->verb() != SkPath::kLine_Verb) { 111154359294a7c9dc54802d512a5d891a35c1663392caryclark return; 111254359294a7c9dc54802d512a5d891a35c1663392caryclark } 1113bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (this->done()) { 1114bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark return; 1115bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 111654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* prior = NULL; 1117bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpanBase* spanBase = &fHead; 111854359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1119bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; 1120bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkASSERT(ptT->span() == spanBase); 112154359294a7c9dc54802d512a5d891a35c1663392caryclark while ((ptT = ptT->next()) != spanStopPtT) { 1122182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (ptT->deleted()) { 1123182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1124182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 112554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* opp = ptT->span()->segment(); 1126bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (opp->verb() == SkPath::kLine_Verb) { 1127ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark continue; 1128ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark } 1129bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (opp->done()) { 113054359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 113154359294a7c9dc54802d512a5d891a35c1663392caryclark } 1132bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence 1133bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (!opp->visited()) { 113454359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 113554359294a7c9dc54802d512a5d891a35c1663392caryclark } 1136bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (spanBase == &fHead) { 113754359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 1138bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 1139bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* span = spanBase->upCastable(); 1140bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // FIXME?: this assumes that if the opposite segment is coincident then no more 1141bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark // coincidence needs to be detected. This may not be true. 1142bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (span && span->containsCoincidence(opp)) { 114354359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 114454359294a7c9dc54802d512a5d891a35c1663392caryclark } 1145bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark if (spanBase->containsCoinEnd(opp)) { 1146bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 1147bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 114854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* priorPtT = NULL, * priorStopPtT; 114954359294a7c9dc54802d512a5d891a35c1663392caryclark // find prior span containing opp segment 115054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* priorOpp = NULL; 1151bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpSpan* priorTest = spanBase->prev(); 1152bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark while (!priorOpp && priorTest) { 1153bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark priorStopPtT = priorPtT = priorTest->ptT(); 115454359294a7c9dc54802d512a5d891a35c1663392caryclark while ((priorPtT = priorPtT->next()) != priorStopPtT) { 1155182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (priorPtT->deleted()) { 1156182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1157182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 115854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = priorPtT->span()->segment(); 115954359294a7c9dc54802d512a5d891a35c1663392caryclark if (segment == opp) { 1160bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark prior = priorTest; 116154359294a7c9dc54802d512a5d891a35c1663392caryclark priorOpp = opp; 116254359294a7c9dc54802d512a5d891a35c1663392caryclark break; 116354359294a7c9dc54802d512a5d891a35c1663392caryclark } 116454359294a7c9dc54802d512a5d891a35c1663392caryclark } 1165bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark priorTest = priorTest->prev(); 116654359294a7c9dc54802d512a5d891a35c1663392caryclark } 116754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!priorOpp) { 116854359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 116954359294a7c9dc54802d512a5d891a35c1663392caryclark } 117054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* oppStart = prior->ptT(); 1171bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark SkOpPtT* oppEnd = spanBase->ptT(); 117254359294a7c9dc54802d512a5d891a35c1663392caryclark bool swapped = priorPtT->fT > ptT->fT; 117354359294a7c9dc54802d512a5d891a35c1663392caryclark if (swapped) { 117454359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(priorPtT, ptT); 117554359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oppStart, oppEnd); 117654359294a7c9dc54802d512a5d891a35c1663392caryclark } 117754359294a7c9dc54802d512a5d891a35c1663392caryclark bool flipped = oppStart->fT > oppEnd->fT; 117854359294a7c9dc54802d512a5d891a35c1663392caryclark bool coincident; 117954359294a7c9dc54802d512a5d891a35c1663392caryclark if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) { 118054359294a7c9dc54802d512a5d891a35c1663392caryclark goto swapBack; 118154359294a7c9dc54802d512a5d891a35c1663392caryclark } 118254359294a7c9dc54802d512a5d891a35c1663392caryclark { 118354359294a7c9dc54802d512a5d891a35c1663392caryclark // average t, find mid pt 1184bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark double midT = (prior->t() + spanBase->t()) / 2; 118554359294a7c9dc54802d512a5d891a35c1663392caryclark SkPoint midPt = this->ptAtT(midT); 118654359294a7c9dc54802d512a5d891a35c1663392caryclark coincident = true; 118754359294a7c9dc54802d512a5d891a35c1663392caryclark // if the mid pt is not near either end pt, project perpendicular through opp seg 118854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) 118954359294a7c9dc54802d512a5d891a35c1663392caryclark && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { 119054359294a7c9dc54802d512a5d891a35c1663392caryclark coincident = false; 119154359294a7c9dc54802d512a5d891a35c1663392caryclark SkIntersections i; 11921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT); 119354359294a7c9dc54802d512a5d891a35c1663392caryclark SkDLine ray = {{{midPt.fX, midPt.fY}, 119454359294a7c9dc54802d512a5d891a35c1663392caryclark {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}}; 11951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i); 119654359294a7c9dc54802d512a5d891a35c1663392caryclark // measure distance and see if it's small enough to denote coincidence 119754359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < i.used(); ++index) { 119854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint oppPt = i.pt(index); 119954359294a7c9dc54802d512a5d891a35c1663392caryclark if (oppPt.approximatelyEqual(midPt)) { 12001049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(), 12011049f1246e7be4ccb68001361efceb8933e6f81ccaryclark opp->weight(), i[index][0]); 120254359294a7c9dc54802d512a5d891a35c1663392caryclark oppDxdy.normalize(); 120354359294a7c9dc54802d512a5d891a35c1663392caryclark dxdy.normalize(); 120454359294a7c9dc54802d512a5d891a35c1663392caryclark SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON); 120554359294a7c9dc54802d512a5d891a35c1663392caryclark coincident |= flatness < 5000; // FIXME: replace with tuned value 120654359294a7c9dc54802d512a5d891a35c1663392caryclark } 120754359294a7c9dc54802d512a5d891a35c1663392caryclark } 120854359294a7c9dc54802d512a5d891a35c1663392caryclark } 120954359294a7c9dc54802d512a5d891a35c1663392caryclark } 121054359294a7c9dc54802d512a5d891a35c1663392caryclark if (coincident) { 121154359294a7c9dc54802d512a5d891a35c1663392caryclark // mark coincidence 1212182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd) 1213182b499cd75c971f85cdf52c1827b3c220cc9011caryclark && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT)) { 1214bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator); 1215bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 121654359294a7c9dc54802d512a5d891a35c1663392caryclark clear_visited(&fHead); 121754359294a7c9dc54802d512a5d891a35c1663392caryclark return; 121854359294a7c9dc54802d512a5d891a35c1663392caryclark } 121954359294a7c9dc54802d512a5d891a35c1663392caryclark swapBack: 122054359294a7c9dc54802d512a5d891a35c1663392caryclark if (swapped) { 122154359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(priorPtT, ptT); 122254359294a7c9dc54802d512a5d891a35c1663392caryclark } 12230dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 1224bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } while ((spanBase = spanBase->final() ? NULL : spanBase->upCast()->next())); 122554359294a7c9dc54802d512a5d891a35c1663392caryclark clear_visited(&fHead); 122654359294a7c9dc54802d512a5d891a35c1663392caryclark} 122754359294a7c9dc54802d512a5d891a35c1663392caryclark 122808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark// if a span has more than one intersection, merge the other segments' span as needed 122908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclarkvoid SkOpSegment::moveMultiples() { 123008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark debugValidate(); 123108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* test = &fHead; 123208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 123308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark int addCount = test->spanAddsCount(); 123408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkASSERT(addCount >= 1); 123508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (addCount == 1) { 123608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 123708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 123808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* startPtT = test->ptT(); 123908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* testPtT = startPtT; 124008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { // iterate through all spans associated with start 124108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppSpan = testPtT->span(); 124208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSpan->spanAddsCount() == addCount) { 124308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 124408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSpan->deleted()) { 124608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 124708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 124808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSegment* oppSegment = oppSpan->segment(); 124908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppSegment == this) { 125008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 125108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // find range of spans to consider merging 125308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppPrev = oppSpan; 125408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppFirst = oppSpan; 125508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppPrev = oppPrev->prev())) { 125608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (!roughly_equal(oppPrev->t(), oppSpan->t())) { 125708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark break; 125808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 125908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPrev->spanAddsCount() == addCount) { 126008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 126108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPrev->deleted()) { 126308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 126408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppFirst = oppPrev; 126608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 126708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppNext = oppSpan; 126808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppLast = oppSpan; 126908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppNext = oppNext->final() ? NULL : oppNext->upCast()->next())) { 127008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (!roughly_equal(oppNext->t(), oppSpan->t())) { 127108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark break; 127208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 127308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppNext->spanAddsCount() == addCount) { 127408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 127508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 127608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppNext->deleted()) { 127708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 127808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 127908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppLast = oppNext; 128008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 128108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppFirst == oppLast) { 128208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 128308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 128408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSpanBase* oppTest = oppFirst; 128508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 128608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppTest == oppSpan) { 128708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark continue; 128808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 128908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // check to see if the candidate meets specific criteria: 129008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark // it contains spans of segments in test's loop but not including 'this' 129108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* oppStartPtT = oppTest->ptT(); 129208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* oppPtT = oppStartPtT; 129308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark while ((oppPtT = oppPtT->next()) != oppStartPtT) { 129408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpSegment* oppPtTSegment = oppPtT->segment(); 129508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppPtTSegment == this) { 129608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto tryNextSpan; 129708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 129808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkOpPtT* matchPtT = startPtT; 129908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark do { 130008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (matchPtT->segment() == oppPtTSegment) { 130108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto foundMatch; 130208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 130308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((matchPtT = matchPtT->next()) != startPtT); 130408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto tryNextSpan; 130508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark foundMatch: // merge oppTest and oppSpan 130608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSegment->debugValidate(); 130708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) { 130808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse 130908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark SkASSERT(oppSpan != &oppSegment->fTail); 131008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppTest->merge(oppSpan->upCast()); 131108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } else { 131208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSpan->merge(oppTest->upCast()); 131308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 131408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark oppSegment->debugValidate(); 131508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark goto checkNextSpan; 131608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } 131708bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark tryNextSpan: 131808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ; 131908bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); 132008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((testPtT = testPtT->next()) != startPtT); 132108bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclarkcheckNextSpan: 132208bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark ; 132308bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark } while ((test = test->final() ? NULL : test->upCast()->next())); 132408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark debugValidate(); 132508bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark} 132608bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark 132754359294a7c9dc54802d512a5d891a35c1663392caryclark// Move nearby t values and pts so they all hang off the same span. Alignment happens later. 132808bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclarkvoid SkOpSegment::moveNearby() { 132954359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 133054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* spanS = &fHead; 133154359294a7c9dc54802d512a5d891a35c1663392caryclark do { 133254359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* test = spanS->upCast()->next(); 133354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next; 133454359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanS->contains(test)) { 133554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!test->final()) { 133654359294a7c9dc54802d512a5d891a35c1663392caryclark test->upCast()->detach(spanS->ptT()); 133754359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 133854359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (spanS != &fHead) { 133954359294a7c9dc54802d512a5d891a35c1663392caryclark spanS->upCast()->detach(test->ptT()); 134054359294a7c9dc54802d512a5d891a35c1663392caryclark spanS = test; 1341570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com continue; 1342570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 134307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 134454359294a7c9dc54802d512a5d891a35c1663392caryclark do { // iterate through all spans associated with start 134554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* startBase = spanS->ptT(); 134654359294a7c9dc54802d512a5d891a35c1663392caryclark next = test->final() ? NULL : test->upCast()->next(); 134754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 134854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* testBase = test->ptT(); 134954359294a7c9dc54802d512a5d891a35c1663392caryclark do { 135054359294a7c9dc54802d512a5d891a35c1663392caryclark if (startBase == testBase) { 135154359294a7c9dc54802d512a5d891a35c1663392caryclark goto checkNextSpan; 135254359294a7c9dc54802d512a5d891a35c1663392caryclark } 135354359294a7c9dc54802d512a5d891a35c1663392caryclark if (testBase->duplicate()) { 135454359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 135554359294a7c9dc54802d512a5d891a35c1663392caryclark } 135654359294a7c9dc54802d512a5d891a35c1663392caryclark if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) { 135754359294a7c9dc54802d512a5d891a35c1663392caryclark if (test == &this->fTail) { 135854359294a7c9dc54802d512a5d891a35c1663392caryclark if (spanS == &fHead) { 135954359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 136008bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark return; // if this span has collapsed, remove it from parent 136154359294a7c9dc54802d512a5d891a35c1663392caryclark } 136254359294a7c9dc54802d512a5d891a35c1663392caryclark this->fTail.merge(spanS->upCast()); 136354359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 136408bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8caryclark return; 136554359294a7c9dc54802d512a5d891a35c1663392caryclark } 136654359294a7c9dc54802d512a5d891a35c1663392caryclark spanS->merge(test->upCast()); 136754359294a7c9dc54802d512a5d891a35c1663392caryclark spanS->upCast()->setNext(next); 136854359294a7c9dc54802d512a5d891a35c1663392caryclark goto checkNextSpan; 136954359294a7c9dc54802d512a5d891a35c1663392caryclark } 137054359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((testBase = testBase->next()) != test->ptT()); 137154359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((startBase = startBase->next()) != spanS->ptT()); 137254359294a7c9dc54802d512a5d891a35c1663392caryclark checkNextSpan: 137354359294a7c9dc54802d512a5d891a35c1663392caryclark ; 137454359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((test = next)); 137554359294a7c9dc54802d512a5d891a35c1663392caryclark spanS = spanS->upCast()->next(); 137654359294a7c9dc54802d512a5d891a35c1663392caryclark } while (!spanS->final()); 137754359294a7c9dc54802d512a5d891a35c1663392caryclark debugValidate(); 1378dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1379dac1d17027dcaa5596885a9f333979418b35001ccaryclark 138054359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::operand() const { 138154359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->operand(); 13825e27e0eb1d1d4c7674e221d3ba3314500ea0b97acaryclark} 13835e27e0eb1d1d4c7674e221d3ba3314500ea0b97acaryclark 138454359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::oppXor() const { 138554359294a7c9dc54802d512a5d891a35c1663392caryclark return fContour->oppXor(); 1386ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark} 1387ccec0f958ffc71a9986d236bc2eb335cb2111119caryclark 138854359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { 138954359294a7c9dc54802d512a5d891a35c1663392caryclark if (fVerb == SkPath::kLine_Verb) { 139054359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 13910dc4dd6dda9a7912f696b46d9c02155ec1d1ba5freed } 139254359294a7c9dc54802d512a5d891a35c1663392caryclark // quads (and cubics) can loop back to nearly a line so that an opposite curve 139354359294a7c9dc54802d512a5d891a35c1663392caryclark // hits in two places with very different t values. 139454359294a7c9dc54802d512a5d891a35c1663392caryclark // OPTIMIZATION: curves could be preflighted so that, for example, something like 139554359294a7c9dc54802d512a5d891a35c1663392caryclark // 'controls contained by ends' could avoid this check for common curves 139654359294a7c9dc54802d512a5d891a35c1663392caryclark // 'ends are extremes in x or y' is cheaper to compute and real-world common 139754359294a7c9dc54802d512a5d891a35c1663392caryclark // on the other hand, the below check is relatively inexpensive 139854359294a7c9dc54802d512a5d891a35c1663392caryclark double midT = (t1 + t2) / 2; 139954359294a7c9dc54802d512a5d891a35c1663392caryclark SkPoint midPt = this->ptAtT(midT); 140054359294a7c9dc54802d512a5d891a35c1663392caryclark double seDistSq = SkTMax(pt1.distanceToSqd(pt2) * 2, FLT_EPSILON * 2); 140154359294a7c9dc54802d512a5d891a35c1663392caryclark return midPt.distanceToSqd(pt1) > seDistSq || midPt.distanceToSqd(pt2) > seDistSq; 140254359294a7c9dc54802d512a5d891a35c1663392caryclark} 140354359294a7c9dc54802d512a5d891a35c1663392caryclark 140454359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 140554359294a7c9dc54802d512a5d891a35c1663392caryclark int* maxWinding, int* sumWinding) { 140654359294a7c9dc54802d512a5d891a35c1663392caryclark int deltaSum = SpanSign(start, end); 140754359294a7c9dc54802d512a5d891a35c1663392caryclark *maxWinding = *sumMiWinding; 140854359294a7c9dc54802d512a5d891a35c1663392caryclark *sumWinding = *sumMiWinding -= deltaSum; 140954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 1410dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 1411dac1d17027dcaa5596885a9f333979418b35001ccaryclark 141254359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 141354359294a7c9dc54802d512a5d891a35c1663392caryclark int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, 141454359294a7c9dc54802d512a5d891a35c1663392caryclark int* oppSumWinding) { 141554359294a7c9dc54802d512a5d891a35c1663392caryclark int deltaSum = SpanSign(start, end); 141654359294a7c9dc54802d512a5d891a35c1663392caryclark int oppDeltaSum = OppSign(start, end); 141707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (operand()) { 141807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *maxWinding = *sumSuWinding; 141907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *sumWinding = *sumSuWinding -= deltaSum; 142007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppMaxWinding = *sumMiWinding; 142107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppSumWinding = *sumMiWinding -= oppDeltaSum; 142207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 142307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *maxWinding = *sumMiWinding; 142407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *sumWinding = *sumMiWinding -= deltaSum; 142507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppMaxWinding = *sumSuWinding; 142607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *oppSumWinding = *sumSuWinding -= oppDeltaSum; 142707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 142854359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 142954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM); 143007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 143107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 14324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.orgvoid SkOpSegment::sortAngles() { 143354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* span = &this->fHead; 14344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 143554359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* fromAngle = span->fromAngle(); 143654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* toAngle = span->final() ? NULL : span->upCast()->toAngle(); 1437dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (!fromAngle && !toAngle) { 14384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org continue; 14394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1440cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#if DEBUG_ANGLE 14414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool wroteAfterHeader = false; 1442cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#endif 144354359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* baseAngle = fromAngle; 144454359294a7c9dc54802d512a5d891a35c1663392caryclark if (fromAngle && toAngle) { 14454431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 144654359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(), 144754359294a7c9dc54802d512a5d891a35c1663392caryclark span->debugID()); 144854359294a7c9dc54802d512a5d891a35c1663392caryclark wroteAfterHeader = true; 14494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 145054359294a7c9dc54802d512a5d891a35c1663392caryclark fromAngle->insert(toAngle); 145154359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (!fromAngle) { 145254359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle = toAngle; 145307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 145454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 14554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org do { 145654359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oSpan = ptT->span(); 145754359294a7c9dc54802d512a5d891a35c1663392caryclark if (oSpan == span) { 145854359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 145954359294a7c9dc54802d512a5d891a35c1663392caryclark } 146054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpAngle* oAngle = oSpan->fromAngle(); 1461dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (oAngle) { 1462570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#if DEBUG_ANGLE 14634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!wroteAfterHeader) { 146454359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 146554359294a7c9dc54802d512a5d891a35c1663392caryclark span->t(), span->debugID()); 14664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org wroteAfterHeader = true; 14674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 1468570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com#endif 146954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oAngle->loopContains(baseAngle)) { 14708cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org baseAngle->insert(oAngle); 14718cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 14724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 147354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oSpan->final()) { 147454359294a7c9dc54802d512a5d891a35c1663392caryclark oAngle = oSpan->upCast()->toAngle(); 147554359294a7c9dc54802d512a5d891a35c1663392caryclark if (oAngle) { 14764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_ANGLE 147754359294a7c9dc54802d512a5d891a35c1663392caryclark if (!wroteAfterHeader) { 147854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 147954359294a7c9dc54802d512a5d891a35c1663392caryclark span->t(), span->debugID()); 148054359294a7c9dc54802d512a5d891a35c1663392caryclark wroteAfterHeader = true; 148154359294a7c9dc54802d512a5d891a35c1663392caryclark } 14824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 148354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oAngle->loopContains(baseAngle)) { 148454359294a7c9dc54802d512a5d891a35c1663392caryclark baseAngle->insert(oAngle); 148554359294a7c9dc54802d512a5d891a35c1663392caryclark } 14868cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 14874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 148854359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((ptT = ptT->next()) != stopPtT); 148954359294a7c9dc54802d512a5d891a35c1663392caryclark if (baseAngle->loopCount() == 1) { 149054359294a7c9dc54802d512a5d891a35c1663392caryclark span->setFromAngle(NULL); 149154359294a7c9dc54802d512a5d891a35c1663392caryclark if (toAngle) { 149254359294a7c9dc54802d512a5d891a35c1663392caryclark span->upCast()->setToAngle(NULL); 14934431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 14944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org baseAngle = NULL; 14954431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 14964431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if DEBUG_SORT 14974431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(!baseAngle || baseAngle->loopCount() > 1); 14984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 149954359294a7c9dc54802d512a5d891a35c1663392caryclark } while (!span->final() && (span = span->upCast()->next())); 1500570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1501570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1502cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com// return true if midpoints were computed 150354359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 15041049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkOpCurve* edge) const { 1505cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(start != end); 150654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& startPtT = *start->ptT(); 150754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& endPtT = *end->ptT(); 15081049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(edge->fVerb = fVerb); 15091049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[0] = startPtT.fPt; 1510cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int points = SkPathOpsVerbToPoints(fVerb); 15111049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[points] = endPtT.fPt; 15121049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fWeight = 1; 1513cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kLine_Verb) { 1514cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1515cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 151654359294a7c9dc54802d512a5d891a35c1663392caryclark double startT = startPtT.fT; 151754359294a7c9dc54802d512a5d891a35c1663392caryclark double endT = endPtT.fT; 1518cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1519cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // don't compute midpoints if we already have them 152007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15211049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[1] = fPts[1]; 15221049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return false; 15231049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15241049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (fVerb == SkPath::kConic_Verb) { 15251049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[1] = fPts[1]; 15261049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fWeight = fWeight; 1527cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 152807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1529cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 1530cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (start < end) { 15311049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[1] = fPts[1]; 15321049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[2] = fPts[2]; 1533cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1534cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 15351049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[1] = fPts[2]; 15361049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[2] = fPts[1]; 1537cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1538cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 15391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark const SkDPoint sub[2] = {{ edge->fPts[0].fX, edge->fPts[0].fY}, 15401049f1246e7be4ccb68001361efceb8933e6f81ccaryclark {edge->fPts[points].fX, edge->fPts[points].fY }}; 1541cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15421049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint(); 15431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (fVerb == SkPath::kConic_Verb) { 15441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[1] = SkDConic::SubDivide(fPts, fWeight, sub[0], sub[1], 15451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark startT, endT, &edge->fWeight).asSkPoint(); 1546cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } else { 1547cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 1548cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDPoint ctrl[2]; 1549cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl); 15501049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[1] = ctrl[0].asSkPoint(); 15511049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fPts[2] = ctrl[1].asSkPoint(); 155207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1553cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return true; 1554cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com} 1555cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com 155654359294a7c9dc54802d512a5d891a35c1663392caryclarkbool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 15571049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDCurve* edge) const { 1558cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(start != end); 155954359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& startPtT = *start->ptT(); 156054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT& endPtT = *end->ptT(); 15611049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDEBUGCODE(edge->fVerb = fVerb); 15621049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[0].set(startPtT.fPt); 1563cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int points = SkPathOpsVerbToPoints(fVerb); 15641049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[points].set(endPtT.fPt); 1565cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kLine_Verb) { 1566cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1567cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 156854359294a7c9dc54802d512a5d891a35c1663392caryclark double startT = startPtT.fT; 156954359294a7c9dc54802d512a5d891a35c1663392caryclark double endT = endPtT.fT; 1570cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1571cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // don't compute midpoints if we already have them 1572cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15731049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fLine[1].set(fPts[1]); 15741049f1246e7be4ccb68001361efceb8933e6f81ccaryclark return false; 15751049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 15761049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (fVerb == SkPath::kConic_Verb) { 15771049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic[1].set(fPts[1]); 15781049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic.fWeight = fWeight; 1579cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1580cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1581cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 158254359294a7c9dc54802d512a5d891a35c1663392caryclark if (startT == 0) { 15831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[1].set(fPts[1]); 15841049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[2].set(fPts[2]); 1585cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1586cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 15871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[1].set(fPts[2]); 15881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fCubic[2].set(fPts[1]); 1589cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return false; 1590cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1591cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fVerb == SkPath::kQuad_Verb) { 15921049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT); 15931049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } else if (fVerb == SkPath::kConic_Verb) { 15941049f1246e7be4ccb68001361efceb8933e6f81ccaryclark edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2], 15951049f1246e7be4ccb68001361efceb8933e6f81ccaryclark startT, endT, &edge->fConic.fWeight); 1596cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } else { 1597cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(fVerb == SkPath::kCubic_Verb); 15981049f1246e7be4ccb68001361efceb8933e6f81ccaryclark SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]); 1599cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1600cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return true; 160107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 160207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 160354359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) { 160454359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpan* span = this->head(); 160554359294a7c9dc54802d512a5d891a35c1663392caryclark do { 160654359294a7c9dc54802d512a5d891a35c1663392caryclark if (!span->done()) { 160707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 160807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 160954359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((span = span->next()->upCastable())); 161054359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(span); 161154359294a7c9dc54802d512a5d891a35c1663392caryclark *start = span; 161254359294a7c9dc54802d512a5d891a35c1663392caryclark *end = span->next(); 161307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 161407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 161554359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { 161654359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* lesser = start->starter(end); 161754359294a7c9dc54802d512a5d891a35c1663392caryclark int oppWinding = lesser->oppSum(); 161854359294a7c9dc54802d512a5d891a35c1663392caryclark int oppSpanWinding = SkOpSegment::OppSign(start, end); 161907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) 162007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && oppWinding != SK_MaxS32) { 162107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com oppWinding -= oppSpanWinding; 162207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 162307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return oppWinding; 162407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 162507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 162607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { 162754359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* startSpan = angle->start(); 162854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* endSpan = angle->end(); 162954359294a7c9dc54802d512a5d891a35c1663392caryclark return updateOppWinding(endSpan, startSpan); 163007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 163107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 163207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { 163354359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* startSpan = angle->start(); 163454359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpanBase* endSpan = angle->end(); 163554359294a7c9dc54802d512a5d891a35c1663392caryclark return updateOppWinding(startSpan, endSpan); 163607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 163707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1638624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 1639624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* lesser = start->starter(end); 164054359294a7c9dc54802d512a5d891a35c1663392caryclark int winding = lesser->windSum(); 16418cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (winding == SK_MinS32) { 1642bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark winding = lesser->computeWindSum(); 1643624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 1644624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (winding == SK_MinS32) { 16458cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return winding; 16468cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 164754359294a7c9dc54802d512a5d891a35c1663392caryclark int spanWinding = SkOpSegment::SpanSign(start, end); 1648570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (winding && UseInnerWinding(winding - spanWinding, winding) 1649570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com && winding != SK_MaxS32) { 165007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com winding -= spanWinding; 165107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 165207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return winding; 165307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 165407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1655624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWinding(SkOpAngle* angle) { 1656624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* startSpan = angle->start(); 1657624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* endSpan = angle->end(); 165854359294a7c9dc54802d512a5d891a35c1663392caryclark return updateWinding(endSpan, startSpan); 1659570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1660570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1661624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { 1662624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* startSpan = angle->start(); 1663624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* endSpan = angle->end(); 166454359294a7c9dc54802d512a5d891a35c1663392caryclark return updateWinding(startSpan, endSpan); 1665570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1666570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 1667570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// OPTIMIZATION: does the following also work, and is it any faster? 1668570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// return outerWinding * innerWinding > 0 1669570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) 1670570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { 1671570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(outerWinding != SK_MaxS32); 1672570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkASSERT(innerWinding != SK_MaxS32); 1673570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int absOut = abs(outerWinding); 1674570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int absIn = abs(innerWinding); 1675570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 1676570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return result; 1677570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 1678570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 167907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkOpSegment::windSum(const SkOpAngle* angle) const { 168054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpSpan* minSpan = angle->start()->starter(angle->end()); 168154359294a7c9dc54802d512a5d891a35c1663392caryclark return minSpan->windSum(); 168207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 1683