diff options
author | caryclark <caryclark@google.com> | 2016-09-14 07:18:20 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2016-09-14 07:18:20 -0700 |
commit | eed356d281adbf93ecbd89cb23913a7861cd8578 (patch) | |
tree | e1f354471538f9484de7bd53eb9fafebd18f411a /src/pathops/SkPathOpsCommon.cpp | |
parent | 8bbcd5aab81dc0742c3367479c0c9d97363b1203 (diff) |
Rewriting path writer
The path writer takes constructs the output path out of
curves that satisfy the pathop operation.
Curves contain lists of t/point pairs that may not be
comparable to each other. To match up curve ends in the
output path, look for adjacent curves to have a shared
membership rather than comparing point values.
Use path utilities to connect partial curve lists into
closed contours.
Share the angle code that determines if a curve has become
a degenerate line with the path writer.
Clean up some code on the way, and delete some unused
functions.
TBR=reed@google.com
BUG=5188
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2321973005
Review-Url: https://codereview.chromium.org/2321973005
Diffstat (limited to 'src/pathops/SkPathOpsCommon.cpp')
-rw-r--r-- | src/pathops/SkPathOpsCommon.cpp | 209 |
1 files changed, 0 insertions, 209 deletions
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 34895db23c..a1ca873fe8 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -198,215 +198,6 @@ bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOd return true; } -class DistanceLessThan { -public: - DistanceLessThan(double* distances) : fDistances(distances) { } - double* fDistances; - bool operator()(const int one, const int two) { - return fDistances[one] < fDistances[two]; - } -}; - - /* - check start and end of each contour - if not the same, record them - match them up - connect closest - reassemble contour pieces into new path - */ -void Assemble(const SkPathWriter& path, SkPathWriter* simple) { - SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune - SkOpContourHead contour; - SkOpGlobalState globalState(&contour, &allocator SkDEBUGPARAMS(false) - SkDEBUGPARAMS(nullptr)); -#if DEBUG_SHOW_TEST_NAME - SkDebugf("</div>\n"); -#endif -#if DEBUG_PATH_CONSTRUCTION - SkDebugf("%s\n", __FUNCTION__); -#endif - SkOpEdgeBuilder builder(path, &contour, &globalState); - builder.finish(); - SkTDArray<const SkOpContour* > runs; // indices of partial contours - const SkOpContour* eContour = builder.head(); - do { - if (!eContour->count()) { - continue; - } - const SkPoint& eStart = eContour->start(); - const SkPoint& eEnd = eContour->end(); -#if DEBUG_ASSEMBLE - SkDebugf("%s contour", __FUNCTION__); - if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) { - SkDebugf("[%d]", runs.count()); - } else { - SkDebugf(" "); - } - SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", - eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); -#endif - if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { - eContour->toPath(simple); - continue; - } - *runs.append() = eContour; - } while ((eContour = eContour->next())); - int count = runs.count(); - if (count == 0) { - return; - } - SkTDArray<int> sLink, eLink; - sLink.append(count); - eLink.append(count); - int rIndex, iIndex; - for (rIndex = 0; rIndex < count; ++rIndex) { - sLink[rIndex] = eLink[rIndex] = SK_MaxS32; - } - const int ends = count * 2; // all starts and ends - const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 - SkTDArray<double> distances; - distances.append(entries); - for (rIndex = 0; rIndex < ends - 1; ++rIndex) { - const SkOpContour* oContour = runs[rIndex >> 1]; - const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start(); - const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) - * ends - rIndex - 1; - for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { - const SkOpContour* iContour = runs[iIndex >> 1]; - const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start(); - double dx = iPt.fX - oPt.fX; - double dy = iPt.fY - oPt.fY; - double dist = dx * dx + dy * dy; - distances[row + iIndex] = dist; // oStart distance from iStart - } - } - SkTDArray<int> sortedDist; - sortedDist.append(entries); - for (rIndex = 0; rIndex < entries; ++rIndex) { - sortedDist[rIndex] = rIndex; - } - SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin())); - int remaining = count; // number of start/end pairs - for (rIndex = 0; rIndex < entries; ++rIndex) { - int pair = sortedDist[rIndex]; - int row = pair / ends; - int col = pair - row * ends; - int thingOne = row < col ? row : ends - row - 2; - int ndxOne = thingOne >> 1; - bool endOne = thingOne & 1; - int* linkOne = endOne ? eLink.begin() : sLink.begin(); - if (linkOne[ndxOne] != SK_MaxS32) { - continue; - } - int thingTwo = row < col ? col : ends - row + col - 1; - int ndxTwo = thingTwo >> 1; - bool endTwo = thingTwo & 1; - int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); - if (linkTwo[ndxTwo] != SK_MaxS32) { - continue; - } - SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); - bool flip = endOne == endTwo; - linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; - linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; - if (!--remaining) { - break; - } - } - SkASSERT(!remaining); -#if DEBUG_ASSEMBLE - for (rIndex = 0; rIndex < count; ++rIndex) { - int s = sLink[rIndex]; - int e = eLink[rIndex]; - SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', - s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); - } -#endif - rIndex = 0; - do { - bool forward = true; - bool first = true; - int sIndex = sLink[rIndex]; - SkASSERT(sIndex != SK_MaxS32); - sLink[rIndex] = SK_MaxS32; - int eIndex; - if (sIndex < 0) { - eIndex = sLink[~sIndex]; - sLink[~sIndex] = SK_MaxS32; - } else { - eIndex = eLink[sIndex]; - eLink[sIndex] = SK_MaxS32; - } - SkASSERT(eIndex != SK_MaxS32); -#if DEBUG_ASSEMBLE - SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', - sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', - eIndex < 0 ? ~eIndex : eIndex); -#endif - do { - const SkOpContour* contour = runs[rIndex]; - if (first) { - first = false; - const SkPoint* startPtr = &contour->start(); - simple->deferredMove(startPtr[0]); - } - if (forward) { - contour->toPartialForward(simple); - } else { - contour->toPartialBackward(simple); - } -#if DEBUG_ASSEMBLE - SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, - eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, - sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); -#endif - if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { - simple->close(); - break; - } - if (forward) { - eIndex = eLink[rIndex]; - SkASSERT(eIndex != SK_MaxS32); - eLink[rIndex] = SK_MaxS32; - if (eIndex >= 0) { - SkASSERT(sLink[eIndex] == rIndex); - sLink[eIndex] = SK_MaxS32; - } else { - SkASSERT(eLink[~eIndex] == ~rIndex); - eLink[~eIndex] = SK_MaxS32; - } - } else { - eIndex = sLink[rIndex]; - SkASSERT(eIndex != SK_MaxS32); - sLink[rIndex] = SK_MaxS32; - if (eIndex >= 0) { - SkASSERT(eLink[eIndex] == rIndex); - eLink[eIndex] = SK_MaxS32; - } else { - SkASSERT(sLink[~eIndex] == ~rIndex); - sLink[~eIndex] = SK_MaxS32; - } - } - rIndex = eIndex; - if (rIndex < 0) { - forward ^= 1; - rIndex = ~rIndex; - } - } while (true); - for (rIndex = 0; rIndex < count; ++rIndex) { - if (sLink[rIndex] != SK_MaxS32) { - break; - } - } - } while (rIndex < count); -#if DEBUG_ASSEMBLE - for (rIndex = 0; rIndex < count; ++rIndex) { - SkASSERT(sLink[rIndex] == SK_MaxS32); - SkASSERT(eLink[rIndex] == SK_MaxS32); - } -#endif -} - static void calcAngles(SkOpContourHead* contourList) { SkOpContour* contour = contourList; do { |