Rewriting path writer

src/pathops/SkPathOpsCommon.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkAddIntersections.h"
 #include "SkOpCoincidence.h"
 #include "SkOpEdgeBuilder.h"
 #include "SkPathOpsCommon.h"
@@ skipping 180 matching lines @@
     *contourList = contourHead;
     for (int index = 1; index < count; ++index) {
         SkOpContour* next = list[index];
         contour->setNext(next);
         contour = next;
     }
     contour->setNext(nullptr);
     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 {
         contour->calcAngles();
     } while ((contour = contour->next()));
 }
 
 static bool missingCoincidence(SkOpContourHead* contourList) {
     SkOpContour* contour = contourList;
     bool result = false;
@@ skipping 172 matching lines @@
     }
 #if DEBUG_COINCIDENCE_VERBOSE
     coincidence->debugShowCoincidence();
 #endif
 #if DEBUG_COINCIDENCE
     coincidence->debugValidate();
 #endif
     SkPathOpsDebug::ShowActiveSpans(contourList);
     return true;
 }