/src/skia/src/pathops/SkPathWriter.cpp

Source (jump to first uncovered line)
/*
 * 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 "src/core/SkTSort.h"
#include "src/pathops/SkOpSegment.h"
#include "src/pathops/SkOpSpan.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathWriter.h"

// wrap path to keep track of whether the contour is initialized and non-empty
SkPathWriter::SkPathWriter(SkPath& path)
    : fPathPtr(&path)
{
    init();
}

void SkPathWriter::close() {
    if (fCurrent.isEmpty()) {
        return;
    }
    SkASSERT(this->isClosed());
#if DEBUG_PATH_CONSTRUCTION
    SkDebugf("path.close();\n");
#endif
    fCurrent.close();
    fPathPtr->addPath(fCurrent);
    fCurrent.reset();
    init();
}

void SkPathWriter::conicTo(const SkPoint& pt1, const SkOpPtT* pt2, SkScalar weight) {
    SkPoint pt2pt = this->update(pt2);
#if DEBUG_PATH_CONSTRUCTION
    SkDebugf("path.conicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g);\n",
            pt1.fX, pt1.fY, pt2pt.fX, pt2pt.fY, weight);
#endif
    fCurrent.conicTo(pt1, pt2pt, weight);
}

void SkPathWriter::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkOpPtT* pt3) {
    SkPoint pt3pt = this->update(pt3);
#if DEBUG_PATH_CONSTRUCTION
    SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
            pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3pt.fX, pt3pt.fY);
#endif
    fCurrent.cubicTo(pt1, pt2, pt3pt);
}

bool SkPathWriter::deferredLine(const SkOpPtT* pt) {
    SkASSERT(fFirstPtT);
    SkASSERT(fDefer[0]);
    if (fDefer[0] == pt) {
        // FIXME: why we're adding a degenerate line? Caller should have preflighted this.
        return true;
    }
    if (pt->contains(fDefer[0])) {
        // FIXME: why we're adding a degenerate line?
        return true;
    }
    if (this->matchedLast(pt)) {
        return false;
    }
    if (fDefer[1] && this->changedSlopes(pt)) {
        this->lineTo();
        fDefer[0] = fDefer[1];
    }
    fDefer[1] = pt;
    return true;
}

void SkPathWriter::deferredMove(const SkOpPtT* pt) {
    if (!fDefer[1]) {
        fFirstPtT = fDefer[0] = pt;
        return;
    }
    SkASSERT(fDefer[0]);
    if (!this->matchedLast(pt)) {
        this->finishContour();
        fFirstPtT = fDefer[0] = pt;
    }
}

void SkPathWriter::finishContour() {
    if (!this->matchedLast(fDefer[0])) {
        if (!fDefer[1]) {
          return;
        }
        this->lineTo();
    }
    if (fCurrent.isEmpty()) {
        return;
    }
    if (this->isClosed()) {
        this->close();
    } else {
        SkASSERT(fDefer[1]);
        fEndPtTs.push_back(fFirstPtT);
        fEndPtTs.push_back(fDefer[1]);
        fPartials.push_back(fCurrent);
        this->init();
    }
}

void SkPathWriter::init() {
    fCurrent.reset();
    fFirstPtT = fDefer[0] = fDefer[1] = nullptr;
}

bool SkPathWriter::isClosed() const {
    return this->matchedLast(fFirstPtT);
}

void SkPathWriter::lineTo() {
    if (fCurrent.isEmpty()) {
        this->moveTo();
    }
#if DEBUG_PATH_CONSTRUCTION
    SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1]->fPt.fX, fDefer[1]->fPt.fY);
#endif
    fCurrent.lineTo(fDefer[1]->fPt);
}

bool SkPathWriter::matchedLast(const SkOpPtT* test) const {
    if (test == fDefer[1]) {
        return true;
    }
    if (!test) {
        return false;
    }
    if (!fDefer[1]) {
        return false;
    }
    return test->contains(fDefer[1]);
}

void SkPathWriter::moveTo() {
#if DEBUG_PATH_CONSTRUCTION
    SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fFirstPtT->fPt.fX, fFirstPtT->fPt.fY);
#endif
    fCurrent.moveTo(fFirstPtT->fPt);
}

void SkPathWriter::quadTo(const SkPoint& pt1, const SkOpPtT* pt2) {
    SkPoint pt2pt = this->update(pt2);
#if DEBUG_PATH_CONSTRUCTION
    SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
            pt1.fX, pt1.fY, pt2pt.fX, pt2pt.fY);
#endif
    fCurrent.quadTo(pt1, pt2pt);
}

// if last point to be written matches the current path's first point, alter the
// last to avoid writing a degenerate lineTo when the path is closed
SkPoint SkPathWriter::update(const SkOpPtT* pt) {
    if (!fDefer[1]) {
        this->moveTo();
    } else if (!this->matchedLast(fDefer[0])) {
        this->lineTo();
    }
    SkPoint result = pt->fPt;
    if (fFirstPtT && result != fFirstPtT->fPt && fFirstPtT->contains(pt)) {
        result = fFirstPtT->fPt;
    }
    fDefer[0] = fDefer[1] = pt;  // set both to know that there is not a pending deferred line
    return result;
}

bool SkPathWriter::someAssemblyRequired() {
    this->finishContour();
    return fEndPtTs.count() > 0;
}

bool SkPathWriter::changedSlopes(const SkOpPtT* ptT) const {
    if (matchedLast(fDefer[0])) {
        return false;
    }
    SkVector deferDxdy = fDefer[1]->fPt - fDefer[0]->fPt;
    SkVector lineDxdy = ptT->fPt - fDefer[1]->fPt;
    return deferDxdy.fX * lineDxdy.fY != deferDxdy.fY * lineDxdy.fX;
}

class DistanceLessThan {
public:
    DistanceLessThan(double* distances) : fDistances(distances) { }
    double* fDistances;
    bool operator()(const int one, const int two) const {
        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 SkPathWriter::assemble() {
    if (!this->someAssemblyRequired()) {
        return;
    }
#if DEBUG_PATH_CONSTRUCTION
    SkDebugf("%s\n", __FUNCTION__);
#endif
    SkOpPtT const* const* runs = fEndPtTs.begin();  // starts, ends of partial contours
    int endCount = fEndPtTs.count(); // all starts and ends
    SkASSERT(endCount > 0);
    SkASSERT(endCount == fPartials.count() * 2);
#if DEBUG_ASSEMBLE
    for (int index = 0; index < endCount; index += 2) {
        const SkOpPtT* eStart = runs[index];
        const SkOpPtT* eEnd = runs[index + 1];
        SkASSERT(eStart != eEnd);
        SkASSERT(!eStart->contains(eEnd));
        SkDebugf("%s contour start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", __FUNCTION__,
                eStart->fPt.fX, eStart->fPt.fY, eEnd->fPt.fX, eEnd->fPt.fY);
    }
#endif
    // lengthen any partial contour adjacent to a simple segment
    for (int pIndex = 0; pIndex < endCount; pIndex++) {
        SkOpPtT* opPtT = const_cast<SkOpPtT*>(runs[pIndex]);
        SkPath p;
        SkPathWriter partWriter(p);
        do {
            if (!zero_or_one(opPtT->fT)) {
                break;
            }
            SkOpSpanBase* opSpanBase = opPtT->span();
            SkOpSpanBase* start = opPtT->fT ? opSpanBase->prev() : opSpanBase->upCast()->next();
            int step = opPtT->fT ? 1 : -1;
            const SkOpSegment* opSegment = opSpanBase->segment();
            const SkOpSegment* nextSegment = opSegment->isSimple(&start, &step);
            if (!nextSegment) {
                break;
            }
            SkOpSpanBase* opSpanEnd = start->t() ? start->prev() : start->upCast()->next();
            if (start->starter(opSpanEnd)->alreadyAdded()) {
                break;
            }
            nextSegment->addCurveTo(start, opSpanEnd, &partWriter);
            opPtT = opSpanEnd->ptT();
            SkOpPtT** runsPtr = const_cast<SkOpPtT**>(&runs[pIndex]);
            *runsPtr = opPtT;
        } while (true);
        partWriter.finishContour();
        const SkTArray<SkPath>& partPartials = partWriter.partials();
        if (!partPartials.count()) {
            continue;
        }
        // if pIndex is even, reverse and prepend to fPartials; otherwise, append
        SkPath& partial = const_cast<SkPath&>(fPartials[pIndex >> 1]);
        const SkPath& part = partPartials[0];
        if (pIndex & 1) {
            partial.addPath(part, SkPath::kExtend_AddPathMode);
        } else {
            SkPath reverse;
            reverse.reverseAddPath(part);
            reverse.addPath(partial, SkPath::kExtend_AddPathMode);
            partial = reverse;
        }
    }
    SkTDArray<int> sLink, eLink;
    int linkCount = endCount / 2; // number of partial contours
    sLink.append(linkCount);
    eLink.append(linkCount);
    int rIndex, iIndex;
    for (rIndex = 0; rIndex < linkCount; ++rIndex) {
        sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
    }
    const int entries = endCount * (endCount - 1) / 2;  // folded triangle
    SkSTArray<8, double, true> distances(entries);
    SkSTArray<8, int, true> sortedDist(entries);
    SkSTArray<8, int, true> distLookup(entries);
    int rRow = 0;
    int dIndex = 0;
    for (rIndex = 0; rIndex < endCount - 1; ++rIndex) {
        const SkOpPtT* oPtT = runs[rIndex];
        for (iIndex = rIndex + 1; iIndex < endCount; ++iIndex) {
            const SkOpPtT* iPtT = runs[iIndex];
            double dx = iPtT->fPt.fX - oPtT->fPt.fX;
            double dy = iPtT->fPt.fY - oPtT->fPt.fY;
            double dist = dx * dx + dy * dy;
            distLookup.push_back(rRow + iIndex);
            distances.push_back(dist);  // oStart distance from iStart
            sortedDist.push_back(dIndex++);
        }
        rRow += endCount;
    }
    SkASSERT(dIndex == entries);
    SkTQSort<int>(sortedDist.begin(), sortedDist.end(), DistanceLessThan(distances.begin()));
    int remaining = linkCount;  // number of start/end pairs
    for (rIndex = 0; rIndex < entries; ++rIndex) {
        int pair = sortedDist[rIndex];
        pair = distLookup[pair];
        int row = pair / endCount;
        int col = pair - row * endCount;
        int ndxOne = row >> 1;
        bool endOne = row & 1;
        int* linkOne = endOne ? eLink.begin() : sLink.begin();
        if (linkOne[ndxOne] != SK_MaxS32) {
            continue;
        }
        int ndxTwo = col >> 1;
        bool endTwo = col & 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 < linkCount; ++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 SkPath& contour = fPartials[rIndex];
            if (!first) {
                SkPoint prior, next;
                if (!fPathPtr->getLastPt(&prior)) {
                    return;
                }
                if (forward) {
                    next = contour.getPoint(0);
                } else {
                    SkAssertResult(contour.getLastPt(&next));
                }
                if (prior != next) {
                    /* TODO: if there is a gap between open path written so far and path to come,
                       connect by following segments from one to the other, rather than introducing
                       a diagonal to connect the two.
                     */
                }
            }
            if (forward) {
                fPathPtr->addPath(contour,
                        first ? SkPath::kAppend_AddPathMode : SkPath::kExtend_AddPathMode);
            } else {
                SkASSERT(!first);
                fPathPtr->reversePathTo(contour);
            }
            if (first) {
                first = false;
            }
#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)) {
                fPathPtr->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 < linkCount; ++rIndex) {
            if (sLink[rIndex] != SK_MaxS32) {
                break;
            }
        }
    } while (rIndex < linkCount);
#if DEBUG_ASSEMBLE
    for (rIndex = 0; rIndex < linkCount; ++rIndex) {
       SkASSERT(sLink[rIndex] == SK_MaxS32);
       SkASSERT(eLink[rIndex] == SK_MaxS32);
    }
#endif
    return;
}

Coverage Report

Created: 2021-08-22 09:07

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright 2012 Google Inc.
3		*
4		* Use of this source code is governed by a BSD-style license that can be
5		* found in the LICENSE file.
6		*/
7		#include "src/core/SkTSort.h"
8		#include "src/pathops/SkOpSegment.h"
9		#include "src/pathops/SkOpSpan.h"
10		#include "src/pathops/SkPathOpsPoint.h"
11		#include "src/pathops/SkPathWriter.h"
12
13		// wrap path to keep track of whether the contour is initialized and non-empty
14		SkPathWriter::SkPathWriter(SkPath& path)
15		: fPathPtr(&path)
16	1.26M	{
17	1.26M	init();
18	1.26M	}
19
20	1.20M	void SkPathWriter::close() {
21	1.20M	if (fCurrent.isEmpty()) {
22	0	return;
23	0	}
24	1.20M	SkASSERT(this->isClosed());
25		#if DEBUG_PATH_CONSTRUCTION
26		SkDebugf("path.close();\n");
27		#endif
28	1.20M	fCurrent.close();
29	1.20M	fPathPtr->addPath(fCurrent);
30	1.20M	fCurrent.reset();
31	1.20M	init();
32	1.20M	}
33
34	711k	void SkPathWriter::conicTo(const SkPoint& pt1, const SkOpPtT* pt2, SkScalar weight) {
35	711k	SkPoint pt2pt = this->update(pt2);
36		#if DEBUG_PATH_CONSTRUCTION
37		SkDebugf("path.conicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g);\n",
38		pt1.fX, pt1.fY, pt2pt.fX, pt2pt.fY, weight);
39		#endif
40	711k	fCurrent.conicTo(pt1, pt2pt, weight);
41	711k	}
42
43	2.50M	void SkPathWriter::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkOpPtT* pt3) {
44	2.50M	SkPoint pt3pt = this->update(pt3);
45		#if DEBUG_PATH_CONSTRUCTION
46		SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
47		pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3pt.fX, pt3pt.fY);
48		#endif
49	2.50M	fCurrent.cubicTo(pt1, pt2, pt3pt);
50	2.50M	}
51
52	6.90M	bool SkPathWriter::deferredLine(const SkOpPtT* pt) {
53	6.90M	SkASSERT(fFirstPtT);
54	6.90M	SkASSERT(fDefer[0]);
55	6.90M	if (fDefer[0] == pt) {
56		// FIXME: why we're adding a degenerate line? Caller should have preflighted this.
57	2.77k	return true;
58	2.77k	}
59	6.89M	if (pt->contains(fDefer[0])) {
60		// FIXME: why we're adding a degenerate line?
61	27.9k	return true;
62	27.9k	}
63	6.86M	if (this->matchedLast(pt)) {
64	569	return false;
65	569	}
66	6.86M	if (fDefer[1] && this->changedSlopes(pt)) {
67	4.20M	this->lineTo();
68	4.20M	fDefer[0] = fDefer[1];
69	4.20M	}
70	6.86M	fDefer[1] = pt;
71	6.86M	return true;
72	6.86M	}
73
74	12.6M	void SkPathWriter::deferredMove(const SkOpPtT* pt) {
75	12.6M	if (!fDefer[1]) {
76	1.70M	fFirstPtT = fDefer[0] = pt;
77	1.70M	return;
78	1.70M	}
79	10.9M	SkASSERT(fDefer[0]);
80	10.9M	if (!this->matchedLast(pt)) {
81	13.7k	this->finishContour();
82	13.7k	fFirstPtT = fDefer[0] = pt;
83	13.7k	}
84	10.9M	}
85
86	15.9M	void SkPathWriter::finishContour() {
87	15.9M	if (!this->matchedLast(fDefer[0])) {
88	955k	if (!fDefer[1]) {
89	556	return;
90	556	}
91	955k	this->lineTo();
92	955k	}
93	15.9M	if (fCurrent.isEmpty()) {
94	14.2M	return;
95	14.2M	}
96	1.70M	if (this->isClosed()) {
97	1.20M	this->close();
98	498k	} else {
99	498k	SkASSERT(fDefer[1]);
100	498k	fEndPtTs.push_back(fFirstPtT);
101	498k	fEndPtTs.push_back(fDefer[1]);
102	498k	fPartials.push_back(fCurrent);
103	498k	this->init();
104	498k	}
105	1.70M	}
106
107	2.96M	void SkPathWriter::init() {
108	2.96M	fCurrent.reset();
109	2.96M	fFirstPtT = fDefer[0] = fDefer[1] = nullptr;
110	2.96M	}
111
112	28.3M	bool SkPathWriter::isClosed() const {
113	28.3M	return this->matchedLast(fFirstPtT);
114	28.3M	}
115
116	6.75M	void SkPathWriter::lineTo() {
117	6.75M	if (fCurrent.isEmpty()) {
118	960k	this->moveTo();
119	960k	}
120		#if DEBUG_PATH_CONSTRUCTION
121		SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1]->fPt.fX, fDefer[1]->fPt.fY);
122		#endif
123	6.75M	fCurrent.lineTo(fDefer[1]->fPt);
124	6.75M	}
125
126	72.9M	bool SkPathWriter::matchedLast(const SkOpPtT* test) const {
127	72.9M	if (test == fDefer[1]) {
128	33.2M	return true;
129	33.2M	}
130	39.7M	if (!test) {
131	0	return false;
132	0	}
133	39.7M	if (!fDefer[1]) {
134	963k	return false;
135	963k	}
136	38.7M	return test->contains(fDefer[1]);
137	38.7M	}
138
139	1.71M	void SkPathWriter::moveTo() {
140		#if DEBUG_PATH_CONSTRUCTION
141		SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fFirstPtT->fPt.fX, fFirstPtT->fPt.fY);
142		#endif
143	1.71M	fCurrent.moveTo(fFirstPtT->fPt);
144	1.71M	}
145
146	2.49M	void SkPathWriter::quadTo(const SkPoint& pt1, const SkOpPtT* pt2) {
147	2.49M	SkPoint pt2pt = this->update(pt2);
148		#if DEBUG_PATH_CONSTRUCTION
149		SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
150		pt1.fX, pt1.fY, pt2pt.fX, pt2pt.fY);
151		#endif
152	2.49M	fCurrent.quadTo(pt1, pt2pt);
153	2.49M	}
154
155		// if last point to be written matches the current path's first point, alter the
156		// last to avoid writing a degenerate lineTo when the path is closed
157	5.71M	SkPoint SkPathWriter::update(const SkOpPtT* pt) {
158	5.71M	if (!fDefer[1]) {
159	754k	this->moveTo();
160	4.95M	} else if (!this->matchedLast(fDefer[0])) {
161	1.59M	this->lineTo();
162	1.59M	}
163	5.71M	SkPoint result = pt->fPt;
164	5.71M	if (fFirstPtT && result != fFirstPtT->fPt && fFirstPtT->contains(pt)) {
165	51.4k	result = fFirstPtT->fPt;
166	51.4k	}
167	5.71M	fDefer[0] = fDefer[1] = pt; // set both to know that there is not a pending deferred line
168	5.71M	return result;
169	5.71M	}
170
171	378k	bool SkPathWriter::someAssemblyRequired() {
172	378k	this->finishContour();
173	378k	return fEndPtTs.count() > 0;
174	378k	}
175
176	5.90M	bool SkPathWriter::changedSlopes(const SkOpPtT* ptT) const {
177	5.90M	if (matchedLast(fDefer[0])) {
178	1.59M	return false;
179	1.59M	}
180	4.31M	SkVector deferDxdy = fDefer[1]->fPt - fDefer[0]->fPt;
181	4.31M	SkVector lineDxdy = ptT->fPt - fDefer[1]->fPt;
182	4.31M	return deferDxdy.fX * lineDxdy.fY != deferDxdy.fY * lineDxdy.fX;
183	4.31M	}
184
185		class DistanceLessThan {
186		public:
187	94.5k	DistanceLessThan(double* distances) : fDistances(distances) { }
188		double* fDistances;
189	1.27G	bool operator()(const int one, const int two) const {
190	1.27G	return fDistances[one] < fDistances[two];
191	1.27G	}
192		};
193
194		/*
195		check start and end of each contour
196		if not the same, record them
197		match them up
198		connect closest
199		reassemble contour pieces into new path
200		*/
201	378k	void SkPathWriter::assemble() {
202	378k	if (!this->someAssemblyRequired()) {
203	283k	return;
204	283k	}
205		#if DEBUG_PATH_CONSTRUCTION
206		SkDebugf("%s\n", __FUNCTION__);
207		#endif
208	94.5k	SkOpPtT const* const* runs = fEndPtTs.begin(); // starts, ends of partial contours
209	94.5k	int endCount = fEndPtTs.count(); // all starts and ends
210	94.5k	SkASSERT(endCount > 0);
211	94.5k	SkASSERT(endCount == fPartials.count() * 2);
212		#if DEBUG_ASSEMBLE
213		for (int index = 0; index < endCount; index += 2) {
214		const SkOpPtT* eStart = runs[index];
215		const SkOpPtT* eEnd = runs[index + 1];
216		SkASSERT(eStart != eEnd);
217		SkASSERT(!eStart->contains(eEnd));
218		SkDebugf("%s contour start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", __FUNCTION__,
219		eStart->fPt.fX, eStart->fPt.fY, eEnd->fPt.fX, eEnd->fPt.fY);
220		}
221		#endif
222		// lengthen any partial contour adjacent to a simple segment
223	1.00M	for (int pIndex = 0; pIndex < endCount; pIndex++) {
224	911k	SkOpPtT* opPtT = const_cast<SkOpPtT*>(runs[pIndex]);
225	911k	SkPath p;
226	911k	SkPathWriter partWriter(p);
227	935k	do {
228	935k	if (!zero_or_one(opPtT->fT)) {
229	365k	break;
230	365k	}
231	569k	SkOpSpanBase* opSpanBase = opPtT->span();
232	309k	SkOpSpanBase* start = opPtT->fT ? opSpanBase->prev() : opSpanBase->upCast()->next();
233	309k	int step = opPtT->fT ? 1 : -1;
234	569k	const SkOpSegment* opSegment = opSpanBase->segment();
235	569k	const SkOpSegment* nextSegment = opSegment->isSimple(&start, &step);
236	569k	if (!nextSegment) {
237	280k	break;
238	280k	}
239	289k	SkOpSpanBase* opSpanEnd = start->t() ? start->prev() : start->upCast()->next();
240	289k	if (start->starter(opSpanEnd)->alreadyAdded()) {
241	265k	break;
242	265k	}
243	23.1k	nextSegment->addCurveTo(start, opSpanEnd, &partWriter);
244	23.1k	opPtT = opSpanEnd->ptT();
245	23.1k	SkOpPtT runsPtr = const_cast<SkOpPtT>(&runs[pIndex]);
246	23.1k	*runsPtr = opPtT;
247	23.1k	} while (true);
248	911k	partWriter.finishContour();
249	911k	const SkTArray<SkPath>& partPartials = partWriter.partials();
250	911k	if (!partPartials.count()) {
251	898k	continue;
252	898k	}
253		// if pIndex is even, reverse and prepend to fPartials; otherwise, append
254	13.8k	SkPath& partial = const_cast<SkPath&>(fPartials[pIndex >> 1]);
255	13.8k	const SkPath& part = partPartials[0];
256	13.8k	if (pIndex & 1) {
257	6.99k	partial.addPath(part, SkPath::kExtend_AddPathMode);
258	6.87k	} else {
259	6.87k	SkPath reverse;
260	6.87k	reverse.reverseAddPath(part);
261	6.87k	reverse.addPath(partial, SkPath::kExtend_AddPathMode);
262	6.87k	partial = reverse;
263	6.87k	}
264	13.8k	}
265	94.5k	SkTDArray<int> sLink, eLink;
266	94.5k	int linkCount = endCount / 2; // number of partial contours
267	94.5k	sLink.append(linkCount);
268	94.5k	eLink.append(linkCount);
269	94.5k	int rIndex, iIndex;
270	550k	for (rIndex = 0; rIndex < linkCount; ++rIndex) {
271	455k	sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
272	455k	}
273	94.5k	const int entries = endCount * (endCount - 1) / 2; // folded triangle
274	94.5k	SkSTArray<8, double, true> distances(entries);
275	94.5k	SkSTArray<8, int, true> sortedDist(entries);
276	94.5k	SkSTArray<8, int, true> distLookup(entries);
277	94.5k	int rRow = 0;
278	94.5k	int dIndex = 0;
279	911k	for (rIndex = 0; rIndex < endCount - 1; ++rIndex) {
280	817k	const SkOpPtT* oPtT = runs[rIndex];
281	52.7M	for (iIndex = rIndex + 1; iIndex < endCount; ++iIndex) {
282	51.9M	const SkOpPtT* iPtT = runs[iIndex];
283	51.9M	double dx = iPtT->fPt.fX - oPtT->fPt.fX;
284	51.9M	double dy = iPtT->fPt.fY - oPtT->fPt.fY;
285	51.9M	double dist = dx * dx + dy * dy;
286	51.9M	distLookup.push_back(rRow + iIndex);
287	51.9M	distances.push_back(dist); // oStart distance from iStart
288	51.9M	sortedDist.push_back(dIndex++);
289	51.9M	}
290	817k	rRow += endCount;
291	817k	}
292	94.5k	SkASSERT(dIndex == entries);
293	94.5k	SkTQSort<int>(sortedDist.begin(), sortedDist.end(), DistanceLessThan(distances.begin()));
294	94.5k	int remaining = linkCount; // number of start/end pairs
295	45.6M	for (rIndex = 0; rIndex < entries; ++rIndex) {
296	45.6M	int pair = sortedDist[rIndex];
297	45.6M	pair = distLookup[pair];
298	45.6M	int row = pair / endCount;
299	45.6M	int col = pair - row * endCount;
300	45.6M	int ndxOne = row >> 1;
301	45.6M	bool endOne = row & 1;
302	23.0M	int* linkOne = endOne ? eLink.begin() : sLink.begin();
303	45.6M	if (linkOne[ndxOne] != SK_MaxS32) {
304	44.5M	continue;
305	44.5M	}
306	1.05M	int ndxTwo = col >> 1;
307	1.05M	bool endTwo = col & 1;
308	647k	int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
309	1.05M	if (linkTwo[ndxTwo] != SK_MaxS32) {
310	603k	continue;
311	603k	}
312	455k	SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
313	455k	bool flip = endOne == endTwo;
314	334k	linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
315	334k	linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
316	455k	if (!--remaining) {
317	94.5k	break;
318	94.5k	}
319	455k	}
320	94.5k	SkASSERT(!remaining);
321		#if DEBUG_ASSEMBLE
322		for (rIndex = 0; rIndex < linkCount; ++rIndex) {
323		int s = sLink[rIndex];
324		int e = eLink[rIndex];
325		SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
326		s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
327		}
328		#endif
329	94.5k	rIndex = 0;
330	127k	do {
331	127k	bool forward = true;
332	127k	bool first = true;
333	127k	int sIndex = sLink[rIndex];
334	127k	SkASSERT(sIndex != SK_MaxS32);
335	127k	sLink[rIndex] = SK_MaxS32;
336	127k	int eIndex;
337	127k	if (sIndex < 0) {
338	18.6k	eIndex = sLink[~sIndex];
339	18.6k	sLink[~sIndex] = SK_MaxS32;
340	109k	} else {
341	109k	eIndex = eLink[sIndex];
342	109k	eLink[sIndex] = SK_MaxS32;
343	109k	}
344	127k	SkASSERT(eIndex != SK_MaxS32);
345		#if DEBUG_ASSEMBLE
346		SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
347		sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
348		eIndex < 0 ? ~eIndex : eIndex);
349		#endif
350	455k	do {
351	455k	const SkPath& contour = fPartials[rIndex];
352	455k	if (!first) {
353	328k	SkPoint prior, next;
354	328k	if (!fPathPtr->getLastPt(&prior)) {
355	0	return;
356	0	}
357	328k	if (forward) {
358	229k	next = contour.getPoint(0);
359	99.2k	} else {
360	99.2k	SkAssertResult(contour.getLastPt(&next));
361	99.2k	}
362	328k	if (prior != next) {
363		/* TODO: if there is a gap between open path written so far and path to come,
364		connect by following segments from one to the other, rather than introducing
365		a diagonal to connect the two.
366		*/
367	130k	}
368	328k	}
369	455k	if (forward) {
370	356k	fPathPtr->addPath(contour,
371	229k	first ? SkPath::kAppend_AddPathMode : SkPath::kExtend_AddPathMode);
372	99.2k	} else {
373	99.2k	SkASSERT(!first);
374	99.2k	fPathPtr->reversePathTo(contour);
375	99.2k	}
376	455k	if (first) {
377	127k	first = false;
378	127k	}
379		#if DEBUG_ASSEMBLE
380		SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
381		eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
382		sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
383		#endif
384	455k	if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
385	127k	fPathPtr->close();
386	127k	break;
387	127k	}
388	328k	if (forward) {
389	247k	eIndex = eLink[rIndex];
390	247k	SkASSERT(eIndex != SK_MaxS32);
391	247k	eLink[rIndex] = SK_MaxS32;
392	247k	if (eIndex >= 0) {
393	187k	SkASSERT(sLink[eIndex] == rIndex);
394	187k	sLink[eIndex] = SK_MaxS32;
395	60.6k	} else {
396	60.6k	SkASSERT(eLink[~eIndex] == ~rIndex);
397	60.6k	eLink[~eIndex] = SK_MaxS32;
398	60.6k	}
399	80.5k	} else {
400	80.5k	eIndex = sLink[rIndex];
401	80.5k	SkASSERT(eIndex != SK_MaxS32);
402	80.5k	sLink[rIndex] = SK_MaxS32;
403	80.5k	if (eIndex >= 0) {
404	38.5k	SkASSERT(eLink[eIndex] == rIndex);
405	38.5k	eLink[eIndex] = SK_MaxS32;
406	42.0k	} else {
407	42.0k	SkASSERT(sLink[~eIndex] == ~rIndex);
408	42.0k	sLink[~eIndex] = SK_MaxS32;
409	42.0k	}
410	80.5k	}
411	328k	rIndex = eIndex;
412	328k	if (rIndex < 0) {
413	102k	forward ^= 1;
414	102k	rIndex = ~rIndex;
415	102k	}
416	328k	} while (true);
417	1.25M	for (rIndex = 0; rIndex < linkCount; ++rIndex) {
418	1.16M	if (sLink[rIndex] != SK_MaxS32) {
419	33.1k	break;
420	33.1k	}
421	1.16M	}
422	127k	} while (rIndex < linkCount);
423		#if DEBUG_ASSEMBLE
424		for (rIndex = 0; rIndex < linkCount; ++rIndex) {
425		SkASSERT(sLink[rIndex] == SK_MaxS32);
426		SkASSERT(eLink[rIndex] == SK_MaxS32);
427		}
428		#endif
429	94.5k	return;
430	94.5k	}