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 "SkOpSpan.h"
8#include "SkPathOpsPoint.h"
9#include "SkPathWriter.h"
10#include "SkTSort.h"
11
12// wrap path to keep track of whether the contour is initialized and non-empty
13SkPathWriter::SkPathWriter(SkPath& path)
14    : fPathPtr(&path)
15{
16    init();
17}
18
19void SkPathWriter::close() {
20    if (fCurrent.isEmpty()) {
21        return;
22    }
23    SkASSERT(this->isClosed());
24#if DEBUG_PATH_CONSTRUCTION
25    SkDebugf("path.close();\n");
26#endif
27    fCurrent.close();
28    fPathPtr->addPath(fCurrent);
29    fCurrent.reset();
30    init();
31}
32
33void SkPathWriter::conicTo(const SkPoint& pt1, const SkOpPtT* pt2, SkScalar weight) {
34    this->update(pt2);
35#if DEBUG_PATH_CONSTRUCTION
36    SkDebugf("path.conicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g);\n",
37            pt1.fX, pt1.fY, pt2->fPt.fX, pt2->fPt.fY, weight);
38#endif
39    fCurrent.conicTo(pt1, pt2->fPt, weight);
40}
41
42void SkPathWriter::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkOpPtT* pt3) {
43    this->update(pt3);
44#if DEBUG_PATH_CONSTRUCTION
45    SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
46            pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3->fPt.fX, pt3->fPt.fY);
47#endif
48    fCurrent.cubicTo(pt1, pt2, pt3->fPt);
49}
50
51bool SkPathWriter::deferredLine(const SkOpPtT* pt) {
52    SkASSERT(fFirstPtT);
53    SkASSERT(fDefer[0]);
54    if (fDefer[0] == pt) {
55        // FIXME: why we're adding a degenerate line? Caller should have preflighted this.
56        return true;
57    }
58    if (pt->contains(fDefer[0])) {
59        // FIXME: why we're adding a degenerate line?
60        return true;
61    }
62    if (this->matchedLast(pt)) {
63        return false;
64    }
65    if (fDefer[1] && this->changedSlopes(pt)) {
66        this->lineTo();
67        fDefer[0] = fDefer[1];
68    }
69    fDefer[1] = pt;
70    return true;
71}
72
73void SkPathWriter::deferredMove(const SkOpPtT* pt) {
74    if (!fDefer[1]) {
75        fFirstPtT = fDefer[0] = pt;
76        return;
77    }
78    SkASSERT(fDefer[0]);
79    if (!this->matchedLast(pt)) {
80        this->finishContour();
81        fFirstPtT = fDefer[0] = pt;
82    }
83}
84
85void SkPathWriter::finishContour() {
86    if (!this->matchedLast(fDefer[0])) {
87        if (!fDefer[1]) {
88          return;
89        }
90        this->lineTo();
91    }
92    if (fCurrent.isEmpty()) {
93        return;
94    }
95    if (this->isClosed()) {
96        this->close();
97    } else {
98        SkASSERT(fDefer[1]);
99        fEndPtTs.push(fFirstPtT);
100        fEndPtTs.push(fDefer[1]);
101        fPartials.push_back(fCurrent);
102        this->init();
103    }
104}
105
106void SkPathWriter::init() {
107    fCurrent.reset();
108    fFirstPtT = fDefer[0] = fDefer[1] = nullptr;
109}
110
111bool SkPathWriter::isClosed() const {
112    return this->matchedLast(fFirstPtT);
113}
114
115void SkPathWriter::lineTo() {
116    if (fCurrent.isEmpty()) {
117        this->moveTo();
118    }
119#if DEBUG_PATH_CONSTRUCTION
120    SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1]->fPt.fX, fDefer[1]->fPt.fY);
121#endif
122    fCurrent.lineTo(fDefer[1]->fPt);
123}
124
125bool SkPathWriter::matchedLast(const SkOpPtT* test) const {
126    if (test == fDefer[1]) {
127        return true;
128    }
129    if (!test) {
130        return false;
131    }
132    if (!fDefer[1]) {
133        return false;
134    }
135    return test->contains(fDefer[1]);
136}
137
138void SkPathWriter::moveTo() {
139#if DEBUG_PATH_CONSTRUCTION
140    SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fFirstPtT->fPt.fX, fFirstPtT->fPt.fY);
141#endif
142    fCurrent.moveTo(fFirstPtT->fPt);
143}
144
145void SkPathWriter::quadTo(const SkPoint& pt1, const SkOpPtT* pt2) {
146    this->update(pt2);
147#if DEBUG_PATH_CONSTRUCTION
148    SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
149            pt1.fX, pt1.fY, pt2->fPt.fX, pt2->fPt.fY);
150#endif
151    fCurrent.quadTo(pt1, pt2->fPt);
152}
153
154void SkPathWriter::update(const SkOpPtT* pt) {
155    if (!fDefer[1]) {
156        this->moveTo();
157    } else if (!this->matchedLast(fDefer[0])) {
158        this->lineTo();
159    }
160    fDefer[0] = fDefer[1] = pt;  // set both to know that there is not a pending deferred line
161}
162
163bool SkPathWriter::someAssemblyRequired() {
164    this->finishContour();
165    return fEndPtTs.count() > 0;
166}
167
168bool SkPathWriter::changedSlopes(const SkOpPtT* ptT) const {
169    if (matchedLast(fDefer[0])) {
170        return false;
171    }
172    SkVector deferDxdy = fDefer[1]->fPt - fDefer[0]->fPt;
173    SkVector lineDxdy = ptT->fPt - fDefer[1]->fPt;
174    return deferDxdy.fX * lineDxdy.fY != deferDxdy.fY * lineDxdy.fX;
175}
176
177class DistanceLessThan {
178public:
179    DistanceLessThan(double* distances) : fDistances(distances) { }
180    double* fDistances;
181    bool operator()(const int one, const int two) {
182        return fDistances[one] < fDistances[two];
183    }
184};
185
186    /*
187        check start and end of each contour
188        if not the same, record them
189        match them up
190        connect closest
191        reassemble contour pieces into new path
192    */
193void SkPathWriter::assemble() {
194#if DEBUG_SHOW_TEST_NAME
195    SkDebugf("</div>\n");
196#endif
197    if (!this->someAssemblyRequired()) {
198        return;
199    }
200#if DEBUG_PATH_CONSTRUCTION
201    SkDebugf("%s\n", __FUNCTION__);
202#endif
203    SkOpPtT const* const* runs = fEndPtTs.begin();  // starts, ends of partial contours
204    int endCount = fEndPtTs.count(); // all starts and ends
205    SkASSERT(endCount > 0);
206    SkASSERT(endCount == fPartials.count() * 2);
207#if DEBUG_ASSEMBLE
208    for (int index = 0; index < endCount; index += 2) {
209        const SkOpPtT* eStart = runs[index];
210        const SkOpPtT* eEnd = runs[index + 1];
211        SkASSERT(eStart != eEnd);
212        SkASSERT(!eStart->contains(eEnd));
213        SkDebugf("%s contour start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", __FUNCTION__,
214                eStart->fPt.fX, eStart->fPt.fY, eEnd->fPt.fX, eEnd->fPt.fY);
215    }
216#endif
217    SkTDArray<int> sLink, eLink;
218    int linkCount = endCount / 2; // number of partial contours
219    sLink.append(linkCount);
220    eLink.append(linkCount);
221    int rIndex, iIndex;
222    for (rIndex = 0; rIndex < linkCount; ++rIndex) {
223        sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
224    }
225    const int entries = endCount * (endCount - 1) / 2;  // folded triangle
226    SkSTArray<8, double, true> distances(entries);
227    SkSTArray<8, int, true> sortedDist(entries);
228    SkSTArray<8, int, true> distLookup(entries);
229    int rRow = 0;
230    int dIndex = 0;
231    for (rIndex = 0; rIndex < endCount - 1; ++rIndex) {
232        const SkOpPtT* oPtT = runs[rIndex];
233        for (iIndex = rIndex + 1; iIndex < endCount; ++iIndex) {
234            const SkOpPtT* iPtT = runs[iIndex];
235            double dx = iPtT->fPt.fX - oPtT->fPt.fX;
236            double dy = iPtT->fPt.fY - oPtT->fPt.fY;
237            double dist = dx * dx + dy * dy;
238            distLookup.push_back(rRow + iIndex);
239            distances.push_back(dist);  // oStart distance from iStart
240            sortedDist.push_back(dIndex++);
241        }
242        rRow += endCount;
243    }
244    SkASSERT(dIndex == entries);
245    SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
246    int remaining = linkCount;  // number of start/end pairs
247    for (rIndex = 0; rIndex < entries; ++rIndex) {
248        int pair = sortedDist[rIndex];
249        pair = distLookup[pair];
250        int row = pair / endCount;
251        int col = pair - row * endCount;
252        int ndxOne = row >> 1;
253        bool endOne = row & 1;
254        int* linkOne = endOne ? eLink.begin() : sLink.begin();
255        if (linkOne[ndxOne] != SK_MaxS32) {
256            continue;
257        }
258        int ndxTwo = col >> 1;
259        bool endTwo = col & 1;
260        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
261        if (linkTwo[ndxTwo] != SK_MaxS32) {
262            continue;
263        }
264        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
265        bool flip = endOne == endTwo;
266        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
267        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
268        if (!--remaining) {
269            break;
270        }
271    }
272    SkASSERT(!remaining);
273#if DEBUG_ASSEMBLE
274    for (rIndex = 0; rIndex < linkCount; ++rIndex) {
275        int s = sLink[rIndex];
276        int e = eLink[rIndex];
277        SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
278                s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
279    }
280#endif
281    rIndex = 0;
282    do {
283        bool forward = true;
284        bool first = true;
285        int sIndex = sLink[rIndex];
286        SkASSERT(sIndex != SK_MaxS32);
287        sLink[rIndex] = SK_MaxS32;
288        int eIndex;
289        if (sIndex < 0) {
290            eIndex = sLink[~sIndex];
291            sLink[~sIndex] = SK_MaxS32;
292        } else {
293            eIndex = eLink[sIndex];
294            eLink[sIndex] = SK_MaxS32;
295        }
296        SkASSERT(eIndex != SK_MaxS32);
297#if DEBUG_ASSEMBLE
298        SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
299                    sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
300                    eIndex < 0 ? ~eIndex : eIndex);
301#endif
302        do {
303            const SkPath& contour = fPartials[rIndex];
304            if (forward) {
305                fPathPtr->addPath(contour,
306                        first ? SkPath::kAppend_AddPathMode : SkPath::kExtend_AddPathMode);
307            } else {
308                SkASSERT(!first);
309                fPathPtr->reversePathTo(contour);
310            }
311            if (first) {
312                first = false;
313            }
314#if DEBUG_ASSEMBLE
315            SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
316                eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
317                sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
318#endif
319            if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
320                fPathPtr->close();
321                break;
322            }
323            if (forward) {
324                eIndex = eLink[rIndex];
325                SkASSERT(eIndex != SK_MaxS32);
326                eLink[rIndex] = SK_MaxS32;
327                if (eIndex >= 0) {
328                    SkASSERT(sLink[eIndex] == rIndex);
329                    sLink[eIndex] = SK_MaxS32;
330                } else {
331                    SkASSERT(eLink[~eIndex] == ~rIndex);
332                    eLink[~eIndex] = SK_MaxS32;
333                }
334            } else {
335                eIndex = sLink[rIndex];
336                SkASSERT(eIndex != SK_MaxS32);
337                sLink[rIndex] = SK_MaxS32;
338                if (eIndex >= 0) {
339                    SkASSERT(eLink[eIndex] == rIndex);
340                    eLink[eIndex] = SK_MaxS32;
341                } else {
342                    SkASSERT(sLink[~eIndex] == ~rIndex);
343                    sLink[~eIndex] = SK_MaxS32;
344                }
345            }
346            rIndex = eIndex;
347            if (rIndex < 0) {
348                forward ^= 1;
349                rIndex = ~rIndex;
350            }
351        } while (true);
352        for (rIndex = 0; rIndex < linkCount; ++rIndex) {
353            if (sLink[rIndex] != SK_MaxS32) {
354                break;
355            }
356        }
357    } while (rIndex < linkCount);
358#if DEBUG_ASSEMBLE
359    for (rIndex = 0; rIndex < linkCount; ++rIndex) {
360       SkASSERT(sLink[rIndex] == SK_MaxS32);
361       SkASSERT(eLink[rIndex] == SK_MaxS32);
362    }
363#endif
364    return;
365}
366