SkPathOpsCommon.cpp revision dae6b97705fde08958b1a36fa6ce685d28fc692c
1033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim/* 2033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim * Copyright 2012 Google Inc. 3033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim * 4033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim * Use of this source code is governed by a BSD-style license that can be 5033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim * found in the LICENSE file. 6033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim */ 7033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#include "SkAddIntersections.h" 8033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#include "SkOpCoincidence.h" 9033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#include "SkOpEdgeBuilder.h" 10033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#include "SkPathOpsCommon.h" 11033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#include "SkPathWriter.h" 12033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#include "SkTSort.h" 13033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 14033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimconst SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr, 15033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool* sortablePtr) { 16033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // find first angle, initialize winding to computed fWindSum 17033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpSegment* segment = start->segment(); 18033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkOpAngle* angle = segment->spanToAngle(start, end); 19033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!angle) { 20033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim *windingPtr = SK_MinS32; 21033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return nullptr; 22033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 23033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool computeWinding = false; 24277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim const SkOpAngle* firstAngle = angle; 25033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool loop = false; 26033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool unorderable = false; 27033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int winding = SK_MinS32; 28033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 29033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim angle = angle->next(); 30033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim unorderable |= angle->unorderable(); 31033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if ((computeWinding = unorderable || (angle == firstAngle && loop))) { 32033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim break; // if we get here, there's no winding, loop is unorderable 33033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 34033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim loop |= angle == firstAngle; 35033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim segment = angle->segment(); 36033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim winding = segment->windSum(angle); 37033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while (winding == SK_MinS32); 38033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // if the angle loop contains an unorderable span, the angle order may be useless 39033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // directly compute the winding in this case for each span 40033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (computeWinding) { 41033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim firstAngle = angle; 42033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim winding = SK_MinS32; 43033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 44033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpSpanBase* startSpan = angle->start(); 45033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpSpanBase* endSpan = angle->end(); 46033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpSpan* lesser = startSpan->starter(endSpan); 47033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int testWinding = lesser->windSum(); 48033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (testWinding == SK_MinS32) { 49033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim testWinding = lesser->computeWindSum(); 50033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 51033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (testWinding != SK_MinS32) { 52033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim segment = angle->segment(); 53033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim winding = testWinding; 54277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 55277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim angle = angle->next(); 56277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } while (angle != firstAngle); 57277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 58277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *sortablePtr = !unorderable; 59277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *windingPtr = winding; 60277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim return angle; 61277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim} 62277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim 63277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik KimSkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr, 64277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpSpanBase** endPtr) { 65277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpSegment* result; 66277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpContour* contour = contourList; 67277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim do { 68277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim result = contour->undoneSegment(startPtr, endPtr); 69277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (result) { 70277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim return result; 71277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 72277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } while ((contour = contour->next())); 73277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim return nullptr; 74277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim} 75277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim 76277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik KimSkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, 77277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpSpanBase** endPtr) { 78277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim while (chase->count()) { 79277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpSpanBase* span; 80277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim chase->pop(&span); 81277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpSegment* segment = span->segment(); 82277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *startPtr = span->ptT()->next()->span(); 83277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim bool done = true; 84277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *endPtr = nullptr; 85277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) { 86277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *startPtr = last->start(); 87277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *endPtr = last->end(); 88277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim #if TRY_ROTATE 89277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *chase->insert(0) = span; 90277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim #else 91277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *chase->append() = span; 92277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim #endif 93277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim return last->segment(); 94277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 95277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (done) { 96277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim continue; 97277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 98277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim // find first angle, initialize winding to computed wind sum 99277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim int winding; 100277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim bool sortable; 101277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); 102277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (winding == SK_MinS32) { 103277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim continue; 104277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 105277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim int sumWinding SK_INIT_TO_AVOID_WARNING; 106277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (sortable) { 107277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim segment = angle->segment(); 108277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim sumWinding = segment->updateWindingReverse(angle); 109277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 110277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpSegment* first = nullptr; 111277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim const SkOpAngle* firstAngle = angle; 112277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim while ((angle = angle->next()) != firstAngle) { 113277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim segment = angle->segment(); 114277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpSpanBase* start = angle->start(); 115277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpSpanBase* end = angle->end(); 116277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim int maxWinding SK_INIT_TO_AVOID_WARNING; 117277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (sortable) { 118277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim segment->setUpWinding(start, end, &maxWinding, &sumWinding); 119277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 120277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (!segment->done(angle)) { 121277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) { 122277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim first = segment; 123277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *startPtr = start; 124277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *endPtr = end; 125277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 126033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // OPTIMIZATION: should this also add to the chase? 127277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (sortable) { 128277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim (void) segment->markAngle(maxWinding, sumWinding, angle); 129277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 130277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 131277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 132277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (first) { 133277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim #if TRY_ROTATE 134277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *chase->insert(0) = span; 135277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim #else 136277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim *chase->append() = span; 137033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim #endif 138033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return first; 139033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 140033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 141033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return nullptr; 142033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 143033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 144033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_ACTIVE_SPANS 145033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimvoid DebugShowActiveSpans(SkOpContourHead* contourList) { 146033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = contourList; 147033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 148033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->debugShowActiveSpans(); 149033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((contour = contour->next())); 150033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 151033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 152033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 153033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimbool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) { 154033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkTDArray<SkOpContour* > list; 155033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = *contourList; 156033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 157033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (contour->count()) { 158033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); 159033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim *list.append() = contour; 160033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 161033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((contour = contour->next())); 162033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int count = list.count(); 163033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!count) { 164033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return false; 165033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 166033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (count > 1) { 167033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkTQSort<SkOpContour>(list.begin(), list.end() - 1); 168033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 169033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour = list[0]; 170033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour); 171033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->globalState()->setContourHead(contourHead); 172033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim *contourList = contourHead; 173033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim for (int index = 1; index < count; ++index) { 174033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* next = list[index]; 175033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->setNext(next); 176033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour = next; 177033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 178033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->setNext(nullptr); 179033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return true; 180033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 181033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 182033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimclass DistanceLessThan { 183033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimpublic: 184033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DistanceLessThan(double* distances) : fDistances(distances) { } 185033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim double* fDistances; 186033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool operator()(const int one, const int two) { 187033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return fDistances[one] < fDistances[two]; 188033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 189033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim}; 190033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 191033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim /* 192033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim check start and end of each contour 193033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if not the same, record them 194033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim match them up 195033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim connect closest 196033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim reassemble contour pieces into new path 197033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim */ 198033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimvoid Assemble(const SkPathWriter& path, SkPathWriter* simple) { 199033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune 200033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContourHead contour; 201033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpGlobalState globalState(nullptr, &contour SkDEBUGPARAMS(false) 202033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDEBUGPARAMS(nullptr)); 203033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_SHOW_TEST_NAME 204033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf("</div>\n"); 205033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 206033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_PATH_CONSTRUCTION 207033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf("%s\n", __FUNCTION__); 208033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 209033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState); 210033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim builder.finish(&allocator); 211033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkTDArray<const SkOpContour* > runs; // indices of partial contours 212033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkOpContour* eContour = builder.head(); 213033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 214033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!eContour->count()) { 215033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim continue; 216033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 217033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkPoint& eStart = eContour->start(); 218033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkPoint& eEnd = eContour->end(); 219033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_ASSEMBLE 220033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf("%s contour", __FUNCTION__); 221033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) { 222033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf("[%d]", runs.count()); 223033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } else { 224033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf(" "); 225033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 226033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", 227033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); 228033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 229033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { 230033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eContour->toPath(simple); 231033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim continue; 232033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 233033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim *runs.append() = eContour; 234033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((eContour = eContour->next())); 235033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int count = runs.count(); 236033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (count == 0) { 237033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return; 238033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 239033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkTDArray<int> sLink, eLink; 240033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sLink.append(count); 241033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eLink.append(count); 242033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int rIndex, iIndex; 243033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim for (rIndex = 0; rIndex < count; ++rIndex) { 244033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sLink[rIndex] = eLink[rIndex] = SK_MaxS32; 245033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 246033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const int ends = count * 2; // all starts and ends 247033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 248033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkTDArray<double> distances; 249033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim distances.append(entries); 250033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim for (rIndex = 0; rIndex < ends - 1; ++rIndex) { 251033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkOpContour* oContour = runs[rIndex >> 1]; 252033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start(); 253033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) 254033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim * ends - rIndex - 1; 255033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { 256033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkOpContour* iContour = runs[iIndex >> 1]; 257033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start(); 258033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim double dx = iPt.fX - oPt.fX; 259033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim double dy = iPt.fY - oPt.fY; 260033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim double dist = dx * dx + dy * dy; 261033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim distances[row + iIndex] = dist; // oStart distance from iStart 262033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 263033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 264033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkTDArray<int> sortedDist; 265033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sortedDist.append(entries); 266033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim for (rIndex = 0; rIndex < entries; ++rIndex) { 267033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sortedDist[rIndex] = rIndex; 268033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 269033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin())); 270033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int remaining = count; // number of start/end pairs 271033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim for (rIndex = 0; rIndex < entries; ++rIndex) { 272033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int pair = sortedDist[rIndex]; 273033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int row = pair / ends; 274033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int col = pair - row * ends; 275033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int thingOne = row < col ? row : ends - row - 2; 276033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int ndxOne = thingOne >> 1; 277033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool endOne = thingOne & 1; 278033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int* linkOne = endOne ? eLink.begin() : sLink.begin(); 279033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (linkOne[ndxOne] != SK_MaxS32) { 280033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim continue; 281033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 282033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int thingTwo = row < col ? col : ends - row + col - 1; 283033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int ndxTwo = thingTwo >> 1; 284033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool endTwo = thingTwo & 1; 285033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); 286033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (linkTwo[ndxTwo] != SK_MaxS32) { 287033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim continue; 288033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 289033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); 290033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool flip = endOne == endTwo; 291033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; 292033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; 293033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!--remaining) { 294033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim break; 295033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 296033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 297033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(!remaining); 298033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_ASSEMBLE 299033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim for (rIndex = 0; rIndex < count; ++rIndex) { 300033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int s = sLink[rIndex]; 301033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int e = eLink[rIndex]; 302033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', 303033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); 304033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 305033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 306033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim rIndex = 0; 307033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 308033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool forward = true; 309033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim bool first = true; 310033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int sIndex = sLink[rIndex]; 311033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(sIndex != SK_MaxS32); 312033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sLink[rIndex] = SK_MaxS32; 313033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim int eIndex; 314033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (sIndex < 0) { 315033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eIndex = sLink[~sIndex]; 316033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sLink[~sIndex] = SK_MaxS32; 317033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } else { 318033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eIndex = eLink[sIndex]; 319033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eLink[sIndex] = SK_MaxS32; 320033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 321033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(eIndex != SK_MaxS32); 322033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_ASSEMBLE 323033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', 324033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', 325033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eIndex < 0 ? ~eIndex : eIndex); 326033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 327033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 328033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkOpContour* contour = runs[rIndex]; 329033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (first) { 330033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim first = false; 331033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim const SkPoint* startPtr = &contour->start(); 332033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim simple->deferredMove(startPtr[0]); 333033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 334033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (forward) { 335033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->toPartialForward(simple); 336033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } else { 337033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->toPartialBackward(simple); 338033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 339033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_ASSEMBLE 340033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, 341033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, 342033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); 343033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 344033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { 345033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim simple->close(); 346033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim break; 347033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 348033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (forward) { 349033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eIndex = eLink[rIndex]; 350033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(eIndex != SK_MaxS32); 351033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eLink[rIndex] = SK_MaxS32; 352277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (eIndex >= 0) { 353033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(sLink[eIndex] == rIndex); 354033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sLink[eIndex] = SK_MaxS32; 355033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } else { 356033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(eLink[~eIndex] == ~rIndex); 357033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eLink[~eIndex] = SK_MaxS32; 358033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 359033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } else { 360033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eIndex = sLink[rIndex]; 361033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(eIndex != SK_MaxS32); 362033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sLink[rIndex] = SK_MaxS32; 363033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (eIndex >= 0) { 364033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(eLink[eIndex] == rIndex); 365033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim eLink[eIndex] = SK_MaxS32; 366033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } else { 367033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkASSERT(sLink[~eIndex] == ~rIndex); 368033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sLink[~eIndex] = SK_MaxS32; 369033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 370033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 371033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim rIndex = eIndex; 372033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (rIndex < 0) { 373033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim forward ^= 1; 374033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim rIndex = ~rIndex; 375033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 376277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } while (true); 377033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim for (rIndex = 0; rIndex < count; ++rIndex) { 378277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim if (sLink[rIndex] != SK_MaxS32) { 379277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim break; 380033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 381277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 382277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } while (rIndex < count); 383277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim#if DEBUG_ASSEMBLE 384277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim for (rIndex = 0; rIndex < count; ++rIndex) { 385277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkASSERT(sLink[rIndex] == SK_MaxS32); 386277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkASSERT(eLink[rIndex] == SK_MaxS32); 387277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } 388277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim#endif 389033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 390033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 391033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimstatic void align(SkOpContourHead* contourList) { 392033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = contourList; 393033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 394033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->align(); 395033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((contour = contour->next())); 396033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 397033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 398033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimstatic void addAlignIntersections(SkOpContourHead* contourList, SkChunkAlloc* allocator) { 399033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = contourList; 400033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 401033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->addAlignIntersections(contourList, allocator); 402033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((contour = contour->next())); 403033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 404033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 405033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimstatic void calcAngles(SkOpContourHead* contourList, SkChunkAlloc* allocator) { 406033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = contourList; 407033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 408033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->calcAngles(allocator); 409033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((contour = contour->next())); 410033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 411033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 412033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimstatic void findCollapsed(SkOpContourHead* contourList) { 413033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = contourList; 414033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 415277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim contour->findCollapsed(); 416277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } while ((contour = contour->next())); 417033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 418277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim 419277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kimstatic bool missingCoincidence(SkOpContourHead* contourList, 420277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpCoincidence* coincidence, SkChunkAlloc* allocator) { 421277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim SkOpContour* contour = contourList; 422277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim bool result = false; 423277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim do { 424277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim result |= contour->missingCoincidence(coincidence, allocator); 425277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim } while ((contour = contour->next())); 426033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return result; 427033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 428033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 429033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimstatic bool moveMultiples(SkOpContourHead* contourList) { 430033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = contourList; 431033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 432033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!contour->moveMultiples()) { 433033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return false; 434033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 435033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((contour = contour->next())); 436033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return true; 437033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 438033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 439033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimstatic void moveNearby(SkOpContourHead* contourList) { 440033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = contourList; 441033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 442033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->moveNearby(); 443033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((contour = contour->next())); 444033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 445033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 446277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kimstatic void sortAngles(SkOpContourHead* contourList) { 447033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpContour* contour = contourList; 448033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 449033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim contour->sortAngles(); 450033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while ((contour = contour->next())); 451033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 452033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim 453033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kimbool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence, 454033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkChunkAlloc* allocator) { 455033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpGlobalState* globalState = contourList->globalState(); 456033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // combine t values when multiple intersections occur on some segments but not others 457033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "start"); 458033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!moveMultiples(contourList)) { 459033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return false; 460033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 461033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples"); 462033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim findCollapsed(contourList); 463033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "findCollapsed"); 464033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // move t values and points together to eliminate small/tiny gaps 465033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim moveNearby(contourList); 466033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby"); 467033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim align(contourList); // give all span members common values 468033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "align"); 469033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim coincidence->fixAligned(); // aligning may have marked a coincidence pt-t deleted 470033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "fixAligned"); 471033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_VALIDATE 472033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim globalState->setPhase(SkOpGlobalState::kIntersecting); 473033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 474033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // look for intersections on line segments formed by moving end points 475033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim addAlignIntersections(contourList, allocator); 476033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "addAlignIntersections"); 477033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (coincidence->addMissing(allocator)) { 478033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing"); 479033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim moveNearby(contourList); 480033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby2"); 481033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim align(contourList); // give all span members common values 482033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "align2"); 483033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim coincidence->fixAligned(); // aligning may have marked a coincidence pt-t deleted 484033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "fixAligned2"); 485033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 486033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_VALIDATE 487033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim globalState->setPhase(SkOpGlobalState::kWalking); 488033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 489033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // check to see if, loosely, coincident ranges may be expanded 490033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (coincidence->expand()) { 491033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "expand1"); 492033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState))) { 493277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim return false; 494033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 495033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 496033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "expand2"); 497033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // the expanded ranges may not align -- add the missing spans 498033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!coincidence->mark()) { // mark spans of coincident segments as coincident 499033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return false; 500033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 501277b7295f317c6597fadb116b6aee5ca3be106c1Wonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "mark1"); 502033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // look for coincidence missed earlier 503033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (missingCoincidence(contourList, coincidence, allocator)) { 504033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence1"); 505033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim (void) coincidence->expand(); 506033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "expand3"); 507033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState))) { 508033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return false; 509033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 510033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded2"); 511033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim coincidence->mark(); 512033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 513033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence2"); 514033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpCoincidence overlaps; 515033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim do { 516033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps; 517033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!pairs->apply()) { // adjust the winding value to account for coincident edges 518033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return false; 519033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 520033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->apply"); 521033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // For each coincident pair that overlaps another, when the receivers (the 1st of the pair) 522033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim // are different, construct a new pair to resolve their mutual span 523033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim pairs->findOverlaps(&overlaps, allocator); 524033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->findOverlaps"); 525033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } while (!overlaps.isEmpty()); 526033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim calcAngles(contourList, allocator); 527033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim sortAngles(contourList); 528033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (globalState->angleCoincidence()) { 529033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim (void) missingCoincidence(contourList, coincidence, allocator); 530033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim if (!coincidence->apply()) { 531033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return false; 532033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 533033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim } 534033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#if DEBUG_ACTIVE_SPANS 535033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim coincidence->debugShowCoincidence(); 536033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim DebugShowActiveSpans(contourList); 537033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim#endif 538033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim return true; 539033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim} 540033ea548eec7ec220082ea6b199bf6e77f67a40dWonsik Kim