1235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com/* 2235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com * Copyright 2012 Google Inc. 3235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com * 4235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com * Use of this source code is governed by a BSD-style license that can be 5235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com * found in the LICENSE file. 6235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com */ 7b0a327e9390da5865d4c56db5e5259adc3380d37skia.committer@gmail.com 8235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#include "Simplify.h" 9235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 10235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comnamespace Op { 11235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 127ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com#define INCLUDED_BY_SHAPE_OPS 1 137ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com 14235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#include "Simplify.cpp" 15235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 1631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com// FIXME: this and find chase should be merge together, along with 1731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com// other code that walks winding in angles 1831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com// OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure 1931143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com// so it isn't duplicated by walkers like this one 207fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.comstatic Segment* findChaseOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd) { 2131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com while (chase.count()) { 2231143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com Span* span; 2331143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com chase.pop(&span); 2431143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com const Span& backPtr = span->fOther->span(span->fOtherIndex); 2531143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com Segment* segment = backPtr.fOther; 267fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com nextStart = backPtr.fOtherIndex; 2731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com SkTDArray<Angle> angles; 2831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com int done = 0; 297fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (segment->activeAngle(nextStart, done, angles)) { 3031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com Angle* last = angles.end() - 1; 317fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com nextStart = last->start(); 327fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com nextEnd = last->end(); 3331143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com #if TRY_ROTATE 3431143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com *chase.insert(0) = span; 3531143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com #else 3631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com *chase.append() = span; 3731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com #endif 3831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com return last->segment(); 3931143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 4031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com if (done == angles.count()) { 4131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com continue; 4231143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 4331143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com SkTDArray<Angle*> sorted; 4431143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com bool sortable = Segment::SortAngles(angles, sorted); 457fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int angleCount = sorted.count(); 4631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com#if DEBUG_SORT 477fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0); 4831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com#endif 4931143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com if (!sortable) { 5031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com continue; 5131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 5231143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com // find first angle, initialize winding to computed fWindSum 5331143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com int firstIndex = -1; 5431143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com const Angle* angle; 5531143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com do { 5631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com angle = sorted[++firstIndex]; 5731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com segment = angle->segment(); 587fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com } while (segment->windSum(angle) == SK_MinS32); 597fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com #if DEBUG_SORT 607fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com segment->debugShowSort(__FUNCTION__, sorted, firstIndex); 6131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com #endif 627fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int sumMiWinding = segment->updateWindingReverse(angle); 637fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int sumSuWinding = segment->updateOppWindingReverse(angle); 647fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (segment->operand()) { 657fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com SkTSwap<int>(sumMiWinding, sumSuWinding); 6631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 6731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com int nextIndex = firstIndex + 1; 6831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 697fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com Segment* first = NULL; 7031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com do { 7131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com SkASSERT(nextIndex != firstIndex); 7231143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com if (nextIndex == angleCount) { 7331143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com nextIndex = 0; 7431143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 7531143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com angle = sorted[nextIndex]; 7631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com segment = angle->segment(); 777fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int start = angle->start(); 787fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int end = angle->end(); 79db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 807fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com segment->setUpWindings(start, end, sumMiWinding, sumSuWinding, 817fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com maxWinding, sumWinding, oppMaxWinding, oppSumWinding); 827fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (!segment->done(angle)) { 837fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (!first) { 847fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com first = segment; 857fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com nextStart = start; 867fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com nextEnd = end; 8731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 887fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, 897fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com oppSumWinding, true, angle); 9031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 9131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } while (++nextIndex != lastIndex); 927fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (first) { 937fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com #if TRY_ROTATE 947fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com *chase.insert(0) = span; 957fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com #else 967fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com *chase.append() = span; 977fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com #endif 987fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com return first; 997fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com } 10031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 10131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com return NULL; 102235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com} 103235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 1047fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com/* 10557cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.comstatic bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding, 10631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com bool windingIsOp, ShapeOp op) { 10731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com bool active = windingIsActive(winding, spanWinding); 10831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com if (!active) { 10931143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com return false; 11031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 11157cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) { 1127fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com switch (op) { 1137fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com case kIntersect_Op: 1147fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com case kUnion_Op: 1157fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com return true; 1167fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com case kDifference_Op: { 1177fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int absSpan = abs(spanWinding); 1187fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int absOpp = abs(oppSpanWinding); 1197fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com return windingIsOp ? absSpan < absOpp : absSpan > absOpp; 1207fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com } 1217fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com case kXor_Op: 1227fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com return spanWinding != oppSpanWinding; 1237fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com default: 1247fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com SkASSERT(0); 1257fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com } 12657cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com } 12731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com bool opActive = oppWinding != 0; 12831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com return gOpLookup[op][opActive][windingIsOp]; 12931143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com} 1307fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com*/ 13157cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com 13231143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.comstatic bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, 1337fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com const int xorMask, const int xorOpMask, PathWrapper& simple) { 134235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com bool firstContour = true; 13531143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com bool unsortable = false; 136e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com bool topUnsortable = false; 137f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; 138235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com do { 139fb51afb03e76c5701fffaa847584a8b7b2c18a7ecaryclark@google.com int index, endIndex; 140db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com bool done; 1413586ece1ddbb48cabb2e7a4792be9ff5d74e40d9caryclark@google.com Segment* current = findSortableTop(contourList, firstContour, index, endIndex, topLeft, 142db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com topUnsortable, done, true); 143fb51afb03e76c5701fffaa847584a8b7b2c18a7ecaryclark@google.com if (!current) { 144db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com if (topUnsortable || !done) { 145e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com topUnsortable = false; 1464aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); 147e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com topLeft.fX = topLeft.fY = SK_ScalarMin; 148e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com continue; 149235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 150e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com break; 151235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 152235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com SkTDArray<Span*> chaseArray; 153235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com do { 1547fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) { 1557fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com do { 1567fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com #if DEBUG_ACTIVE_SPANS 1577fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (!unsortable && current->done()) { 1587fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com debugShowActiveSpans(contourList); 159235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 1607fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com #endif 1617fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com SkASSERT(unsortable || !current->done()); 1627fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int nextStart = index; 1637fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com int nextEnd = endIndex; 1647fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com Segment* next = current->findNextOp(chaseArray, nextStart, nextEnd, 1657fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com unsortable, op, xorMask, xorOpMask); 1667fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (!next) { 1677fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com if (!unsortable && simple.hasMove() 1687fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com && current->verb() != SkPath::kLine_Verb 1697fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com && !simple.isClosed()) { 1707fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com current->addCurveTo(index, endIndex, simple, true); 1717fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com SkASSERT(simple.isClosed()); 1727fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com } 1737fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com break; 1747fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com } 1754aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com #if DEBUG_FLOW 1764aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 1774aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY, 1784aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY); 1794aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com #endif 1807fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com current->addCurveTo(index, endIndex, simple, true); 1817fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com current = next; 1827fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com index = nextStart; 1837fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com endIndex = nextEnd; 1844aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com } while (!simple.isClosed() && ((!unsortable) 1854aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com || !current->done(SkMin32(index, endIndex)))); 1864aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com if (current->activeWinding(index, endIndex) && !simple.isClosed()) { 18731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com SkASSERT(unsortable); 18831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com int min = SkMin32(index, endIndex); 18931143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com if (!current->done(min)) { 19031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com current->addCurveTo(index, endIndex, simple, true); 1917fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com current->markDoneBinary(min); 19231143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 19331143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com } 194235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com simple.close(); 1957fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com } else { 1967fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com Span* last = current->markAndChaseDoneBinary(index, endIndex); 1974aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com if (last && !last->fLoop) { 1987fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com *chaseArray.append() = last; 1997fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com } 200235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 20131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com current = findChaseOp(chaseArray, index, endIndex); 202235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com #if DEBUG_ACTIVE_SPANS 203235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com debugShowActiveSpans(contourList); 204235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com #endif 205235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (!current) { 206235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com break; 207235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 208235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } while (true); 209235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } while (true); 2104aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com return simple.someAssemblyRequired(); 211235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com} 212235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 213235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com} // end of Op namespace 214235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 215235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 216235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comvoid operate(const SkPath& one, const SkPath& two, ShapeOp op, SkPath& result) { 2171304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com#if DEBUG_SORT || DEBUG_SWAP_TOP 218c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com Op::gDebugSortCount = Op::gDebugSortCountDefault; 219c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com#endif 220235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com result.reset(); 221235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com result.setFillType(SkPath::kEvenOdd_FillType); 222235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // turn path into list of segments 223235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com SkTArray<Op::Contour> contours; 224235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // FIXME: add self-intersecting cubics' T values to segment 225235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com Op::EdgeBuilder builder(one, contours); 2267fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com const int xorMask = builder.xorMask(); 227235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com builder.addOperand(two); 228235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com builder.finish(); 2297fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com const int xorOpMask = builder.xorMask(); 230235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com SkTDArray<Op::Contour*> contourList; 2314eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com makeContourList(contours, contourList, xorMask == kEvenOdd_Mask, 2324eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com xorOpMask == kEvenOdd_Mask); 233235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com Op::Contour** currentPtr = contourList.begin(); 234235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (!currentPtr) { 235235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com return; 236235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 237235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com Op::Contour** listEnd = contourList.end(); 238235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // find all intersections between segments 239235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com do { 240235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com Op::Contour** nextPtr = currentPtr; 241235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com Op::Contour* current = *currentPtr++; 242c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com if (current->containsCubics()) { 243c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com addSelfIntersectTs(current); 244c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com } 245235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com Op::Contour* next; 246235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com do { 247235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com next = *nextPtr++; 248235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } while (addIntersectTs(current, next) && nextPtr != listEnd); 249235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } while (currentPtr != listEnd); 250235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // eat through coincident edges 251b0a327e9390da5865d4c56db5e5259adc3380d37skia.committer@gmail.com 2527ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com int total = 0; 2537ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com int index; 2547ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com for (index = 0; index < contourList.count(); ++index) { 2557ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com total += contourList[index]->segments().count(); 2567ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com } 257729e1c46cea63dfaa6e4a05608b8f3be41e19dcecaryclark@google.com#if DEBUG_SHOW_WINDING 2587ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com Op::Contour::debugShowWindingValues(contourList); 2597ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com#endif 2604eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com coincidenceCheck(contourList, total); 261729e1c46cea63dfaa6e4a05608b8f3be41e19dcecaryclark@google.com#if DEBUG_SHOW_WINDING 2627ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com Op::Contour::debugShowWindingValues(contourList); 2637ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com#endif 264235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com fixOtherTIndex(contourList); 26531143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com sortSegments(contourList); 26631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com#if DEBUG_ACTIVE_SPANS 26731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com debugShowActiveSpans(contourList); 26831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com#endif 269235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // construct closed contours 270f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com Op::PathWrapper wrapper(result); 2717fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com bridgeOp(contourList, op, xorMask, xorOpMask, wrapper); 2721304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com { // if some edges could not be resolved, assemble remaining fragments 2731304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkPath temp; 2741304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com temp.setFillType(SkPath::kEvenOdd_FillType); 2751304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com Op::PathWrapper assembled(temp); 2761304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com assemble(wrapper, assembled); 2771304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com result = *assembled.nativePath(); 2781304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com } 279235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com} 280