17839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger/* 27839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * Copyright 2012 Google Inc. 37839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 47839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * Use of this source code is governed by a BSD-style license that can be 57839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * found in the LICENSE file. 67839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger */ 77839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkAddIntersections.h" 87839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkOpEdgeBuilder.h" 97839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkPathOpsCommon.h" 107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkPathWriter.h" 117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// FIXME: this and find chase should be merge together, along with 137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// other code that walks winding in angles 147839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure 157839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// so it isn't duplicated by walkers like this one 167839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerstatic SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd) { 177839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger while (chase.count()) { 187839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpSpan* span; 197839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger chase.pop(&span); 207839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex); 217839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpSegment* segment = backPtr.fOther; 227839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger nextStart = backPtr.fOtherIndex; 2358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; 247839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int done = 0; 257839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (segment->activeAngle(nextStart, &done, &angles)) { 267839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpAngle* last = angles.end() - 1; 277839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger nextStart = last->start(); 287839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger nextEnd = last->end(); 297839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #if TRY_ROTATE 307839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger *chase.insert(0) = span; 317839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #else 327839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger *chase.append() = span; 337839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #endif 347839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return last->segment(); 357839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 367839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (done == angles.count()) { 377839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger continue; 387839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; 4058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bool sortable = SkOpSegment::SortAngles(angles, &sorted, 4158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkOpSegment::kMayBeUnordered_SortAngleKind); 427839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int angleCount = sorted.count(); 437839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if DEBUG_SORT 4458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable); 457839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 467839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!sortable) { 477839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger continue; 487839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 497839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // find first angle, initialize winding to computed fWindSum 507839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int firstIndex = -1; 517839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger const SkOpAngle* angle; 520a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger bool foundAngle = true; 537839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger do { 540a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger ++firstIndex; 550a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger if (firstIndex >= angleCount) { 560a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger foundAngle = false; 570a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger break; 580a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger } 590a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger angle = sorted[firstIndex]; 607839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger segment = angle->segment(); 617839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } while (segment->windSum(angle) == SK_MinS32); 620a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger if (!foundAngle) { 630a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger continue; 640a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger } 657839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #if DEBUG_SORT 6658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); 677839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #endif 687839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int sumMiWinding = segment->updateWindingReverse(angle); 697839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int sumSuWinding = segment->updateOppWindingReverse(angle); 707839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (segment->operand()) { 717839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkTSwap<int>(sumMiWinding, sumSuWinding); 727839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 737839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int nextIndex = firstIndex + 1; 747839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 757839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpSegment* first = NULL; 767839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger do { 777839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(nextIndex != firstIndex); 787839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (nextIndex == angleCount) { 797839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger nextIndex = 0; 807839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 817839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger angle = sorted[nextIndex]; 827839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger segment = angle->segment(); 837839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int start = angle->start(); 847839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int end = angle->end(); 857839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 867839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding, 877839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 887839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!segment->done(angle)) { 897839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!first) { 907839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger first = segment; 917839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger nextStart = start; 927839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger nextEnd = end; 937839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 947839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, 95910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger oppSumWinding, angle); 967839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 977839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } while (++nextIndex != lastIndex); 987839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (first) { 997839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #if TRY_ROTATE 1007839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger *chase.insert(0) = span; 1017839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #else 1027839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger *chase.append() = span; 1037839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #endif 1047839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return first; 1057839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1067839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1077839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return NULL; 1087839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 1097839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 1107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger/* 1117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerstatic bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding, 1127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool windingIsOp, PathOp op) { 1137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool active = windingIsActive(winding, spanWinding); 1147839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!active) { 1157839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return false; 1167839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1177839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) { 1187839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger switch (op) { 1197839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger case kIntersect_Op: 1207839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger case kUnion_Op: 1217839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return true; 1227839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger case kDifference_Op: { 1237839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int absSpan = abs(spanWinding); 1247839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int absOpp = abs(oppSpanWinding); 1257839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return windingIsOp ? absSpan < absOpp : absSpan > absOpp; 1267839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1277839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger case kXor_Op: 1287839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return spanWinding != oppSpanWinding; 1297839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger default: 1307839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(0); 1317839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1327839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1337839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool opActive = oppWinding != 0; 1347839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return gOpLookup[op][opActive][windingIsOp]; 1357839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 1367839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger*/ 1377839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 13858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerstatic bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op, 1397839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger const int xorMask, const int xorOpMask, SkPathWriter* simple) { 1407839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool firstContour = true; 1417839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool unsortable = false; 1427839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool topUnsortable = false; 1437839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; 1447839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger do { 1457839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int index, endIndex; 1467839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool done; 1470a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour, 1480a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger &index, &endIndex, &topLeft, &topUnsortable, &done); 1497839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!current) { 1507839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (topUnsortable || !done) { 1517839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger topUnsortable = false; 1527839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); 1537839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger topLeft.fX = topLeft.fY = SK_ScalarMin; 1547839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger continue; 1557839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1567839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger break; 1577839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1587839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkTDArray<SkOpSpan*> chaseArray; 1597839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger do { 1607839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) { 1617839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger do { 1627839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!unsortable && current->done()) { 1637839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #if DEBUG_ACTIVE_SPANS 1647839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger DebugShowActiveSpans(contourList); 1657839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #endif 1667839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (simple->isEmpty()) { 1677839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger simple->init(); 1687839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1690a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger break; 1707839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1717839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(unsortable || !current->done()); 1727839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int nextStart = index; 1737839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int nextEnd = endIndex; 1747839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpSegment* next = current->findNextOp(&chaseArray, &nextStart, &nextEnd, 1757839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger &unsortable, op, xorMask, xorOpMask); 1767839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!next) { 1777839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!unsortable && simple->hasMove() 1787839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger && current->verb() != SkPath::kLine_Verb 1797839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger && !simple->isClosed()) { 1807839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger current->addCurveTo(index, endIndex, simple, true); 1817839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkASSERT(simple->isClosed()); 1827839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1837839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger break; 1847839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1857839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #if DEBUG_FLOW 1867839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 1877839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY, 1887839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY); 1897839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #endif 1907839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger current->addCurveTo(index, endIndex, simple, true); 1917839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger current = next; 1927839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger index = nextStart; 1937839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger endIndex = nextEnd; 1947839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } while (!simple->isClosed() && (!unsortable 1957839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger || !current->done(SkMin32(index, endIndex)))); 1967839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (current->activeWinding(index, endIndex) && !simple->isClosed()) { 1970a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger // FIXME : add to simplify, xor cpaths 1987839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int min = SkMin32(index, endIndex); 1990a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger if (!unsortable && !simple->isEmpty()) { 2000a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger unsortable = current->checkSmall(min); 2010a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger } 2020a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger SkASSERT(unsortable || simple->isEmpty()); 2037839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!current->done(min)) { 2047839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger current->addCurveTo(index, endIndex, simple, true); 2057839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger current->markDoneBinary(min); 2067839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2077839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2087839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger simple->close(); 2097839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } else { 2107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex); 2117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (last && !last->fLoop) { 2127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger *chaseArray.append() = last; 2137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2147839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2157839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger current = findChaseOp(chaseArray, index, endIndex); 2167839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #if DEBUG_ACTIVE_SPANS 2177839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger DebugShowActiveSpans(contourList); 2187839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger #endif 2197839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!current) { 2207839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger break; 2217839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2227839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } while (true); 2237839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } while (true); 2247839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return simple->someAssemblyRequired(); 2257839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 2267839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 2277839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// pretty picture: 2287839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing 2297839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerstatic const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = { 2307839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// inside minuend outside minuend 2317839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// inside subtrahend outside subtrahend inside subtrahend outside subtrahend 2327839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ kDifference_PathOp, kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }}, 2337839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ kIntersect_PathOp, kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }}, 2347839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp, kIntersect_PathOp }}, 2357839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ kXOR_PathOp, kXOR_PathOp }, { kXOR_PathOp, kXOR_PathOp }}, 2367839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp, kDifference_PathOp }}, 2377839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger}; 2387839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 2397839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerstatic const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = { 2407839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ false, false }, { true, false }}, // diff 2417839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ false, false }, { false, true }}, // sect 2427839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ false, true }, { true, true }}, // union 2437839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ false, true }, { true, false }}, // xor 2447839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger {{ false, true }, { false, false }}, // rev diff 2457839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger}; 2467839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 2477839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerbool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { 24858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#if DEBUG_SHOW_TEST_NAME 24958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger char* debugName = DEBUG_FILENAME_STRING; 25058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (debugName && debugName[0]) { 2510a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger SkPathOpsDebug::BumpTestName(debugName); 2520a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger SkPathOpsDebug::ShowPath(one, two, op, debugName); 25358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 2547839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 2557839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; 2567839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] 2577839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; 2587839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger const SkPath* minuend = &one; 2597839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger const SkPath* subtrahend = &two; 2607839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (op == kReverseDifference_PathOp) { 2617839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger minuend = &two; 2627839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger subtrahend = &one; 2637839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger op = kDifference_PathOp; 2647839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2657839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#if DEBUG_SORT || DEBUG_SWAP_TOP 2660a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 2677839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#endif 2687839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // turn path into list of segments 2697839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkTArray<SkOpContour> contours; 2707839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // FIXME: add self-intersecting cubics' T values to segment 2717839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpEdgeBuilder builder(*minuend, contours); 2727839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger const int xorMask = builder.xorMask(); 2737839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger builder.addOperand(*subtrahend); 2747839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!builder.finish()) { 2757839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return false; 2767839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2777839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger result->reset(); 2787839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger result->setFillType(fillType); 2797839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger const int xorOpMask = builder.xorMask(); 28058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkTArray<SkOpContour*, true> contourList; 2817839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask, 2827839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger xorOpMask == kEvenOdd_PathOpsMask); 2837839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpContour** currentPtr = contourList.begin(); 2847839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (!currentPtr) { 2857839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return true; 2867839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2877839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpContour** listEnd = contourList.end(); 2887839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // find all intersections between segments 2897839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger do { 2907839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpContour** nextPtr = currentPtr; 2917839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpContour* current = *currentPtr++; 2927839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (current->containsCubics()) { 2937839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger AddSelfIntersectTs(current); 2947839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 2957839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkOpContour* next; 2967839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger do { 2977839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger next = *nextPtr++; 2987839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } while (AddIntersectTs(current, next) && nextPtr != listEnd); 2997839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } while (currentPtr != listEnd); 3007839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // eat through coincident edges 3017839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 3027839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int total = 0; 3037839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int index; 3047839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger for (index = 0; index < contourList.count(); ++index) { 3057839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger total += contourList[index]->segments().count(); 3067839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3070a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger HandleCoincidence(&contourList, total); 3087839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // construct closed contours 3097839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkPathWriter wrapper(*result); 3107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper); 3117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger { // if some edges could not be resolved, assemble remaining fragments 3127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkPath temp; 3137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger temp.setFillType(fillType); 3147839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkPathWriter assembled(temp); 3157839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger Assemble(wrapper, &assembled); 3167839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger *result = *assembled.nativePath(); 3177839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger result->setFillType(fillType); 3187839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 3197839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return true; 3207839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 321