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
14SkPathWriter::SkPathWriter(SkPath& path)
15    : fPathPtr(&path)
16{
17    init();
18}
19
20void SkPathWriter::close() {
21    if (fCurrent.isEmpty()) {
22        return;
23    }
24    SkASSERT(this->isClosed());
25#if DEBUG_PATH_CONSTRUCTION
26    SkDebugf("path.close();\n");
27#endif
28    fCurrent.close();
29    fPathPtr->addPath(fCurrent);
30    fCurrent.reset();
31    init();
32}
33
34void SkPathWriter::conicTo(const SkPoint& pt1, const SkOpPtT* pt2, SkScalar weight) {
35    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    fCurrent.conicTo(pt1, pt2pt, weight);
41}
42
43void SkPathWriter::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkOpPtT* pt3) {
44    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    fCurrent.cubicTo(pt1, pt2, pt3pt);
50}
51
52bool SkPathWriter::deferredLine(const SkOpPtT* pt) {
53    SkASSERT(fFirstPtT);
54    SkASSERT(fDefer[0]);
55    if (fDefer[0] == pt) {
56        // FIXME: why we're adding a degenerate line? Caller should have preflighted this.
57        return true;
58    }
59    if (pt->contains(fDefer[0])) {
60        // FIXME: why we're adding a degenerate line?
61        return true;
62    }
63    if (this->matchedLast(pt)) {
64        return false;
65    }
66    if (fDefer[1] && this->changedSlopes(pt)) {
67        this->lineTo();
68        fDefer[0] = fDefer[1];
69    }
70    fDefer[1] = pt;
71    return true;
72}
73
74void SkPathWriter::deferredMove(const SkOpPtT* pt) {
75    if (!fDefer[1]) {
76        fFirstPtT = fDefer[0] = pt;
77        return;
78    }
79    SkASSERT(fDefer[0]);
80    if (!this->matchedLast(pt)) {
81        this->finishContour();
82        fFirstPtT = fDefer[0] = pt;
83    }
84}
85
86void SkPathWriter::finishContour() {
87    if (!this->matchedLast(fDefer[0])) {
88        if (!fDefer[1]) {
89          return;
90        }
91        this->lineTo();
92    }
93    if (fCurrent.isEmpty()) {
94        return;
95    }
96    if (this->isClosed()) {
97        this->close();
98    } else {
99        SkASSERT(fDefer[1]);
100        fEndPtTs.push_back(fFirstPtT);
101        fEndPtTs.push_back(fDefer[1]);
102        fPartials.push_back(fCurrent);
103        this->init();
104    }
105}
106
107void SkPathWriter::init() {
108    fCurrent.reset();
109    fFirstPtT = fDefer[0] = fDefer[1] = nullptr;
110}
111
112bool SkPathWriter::isClosed() const {
113    return this->matchedLast(fFirstPtT);
114}
115
116void SkPathWriter::lineTo() {
117    if (fCurrent.isEmpty()) {
118        this->moveTo();
119    }
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    fCurrent.lineTo(fDefer[1]->fPt);
124}
125
126bool SkPathWriter::matchedLast(const SkOpPtT* test) const {
127    if (test == fDefer[1]) {
128        return true;
129    }
130    if (!test) {
131        return false;
132    }
133    if (!fDefer[1]) {
134        return false;
135    }
136    return test->contains(fDefer[1]);
137}
138
139void 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    fCurrent.moveTo(fFirstPtT->fPt);
144}
145
146void SkPathWriter::quadTo(const SkPoint& pt1, const SkOpPtT* pt2) {
147    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    fCurrent.quadTo(pt1, pt2pt);
153}
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
157SkPoint SkPathWriter::update(const SkOpPtT* pt) {
158    if (!fDefer[1]) {
159        this->moveTo();
160    } else if (!this->matchedLast(fDefer[0])) {
161        this->lineTo();
162    }
163    SkPoint result = pt->fPt;
164    if (fFirstPtT && result != fFirstPtT->fPt && fFirstPtT->contains(pt)) {
165        result = fFirstPtT->fPt;
166    }
167    fDefer[0] = fDefer[1] = pt;  // set both to know that there is not a pending deferred line
168    return result;
169}
170
171bool SkPathWriter::someAssemblyRequired() {
172    this->finishContour();
173    return fEndPtTs.count() > 0;
174}
175
176bool SkPathWriter::changedSlopes(const SkOpPtT* ptT) const {
177    if (matchedLast(fDefer[0])) {
178        return false;
179    }
180    SkVector deferDxdy = fDefer[1]->fPt - fDefer[0]->fPt;
181    SkVector lineDxdy = ptT->fPt - fDefer[1]->fPt;
182    return deferDxdy.fX * lineDxdy.fY != deferDxdy.fY * lineDxdy.fX;
183}
184
185class DistanceLessThan {
186public:
187    DistanceLessThan(double* distances) : fDistances(distances) { }
188    double* fDistances;
189    bool operator()(const int one, const int two) const {
190        return fDistances[one] < fDistances[two];
191    }
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    */
201void SkPathWriter::assemble() {
202    if (!this->someAssemblyRequired()) {
203        return;
204    }
205#if DEBUG_PATH_CONSTRUCTION
206    SkDebugf("%s\n", __FUNCTION__);
207#endif
208    SkOpPtT const* const* runs = fEndPtTs.begin();  // starts, ends of partial contours
209    int endCount = fEndPtTs.count(); // all starts and ends
210    SkASSERT(endCount > 0);
211    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    for (int pIndex = 0; pIndex < endCount; pIndex++) {
224        SkOpPtT* opPtT = const_cast<SkOpPtT*>(runs[pIndex]);
225        SkPath p;
226        SkPathWriter partWriter(p);
227        do {
228            if (!zero_or_one(opPtT->fT)) {
229                break;
230            }
231            SkOpSpanBase* opSpanBase = opPtT->span();
232            SkOpSpanBase* start = opPtT->fT ? opSpanBase->prev() : opSpanBase->upCast()->next();
233            int step = opPtT->fT ? 1 : -1;
234            const SkOpSegment* opSegment = opSpanBase->segment();
235            const SkOpSegment* nextSegment = opSegment->isSimple(&start, &step);
236            if (!nextSegment) {
237                break;
238            }
239            SkOpSpanBase* opSpanEnd = start->t() ? start->prev() : start->upCast()->next();
240            if (start->starter(opSpanEnd)->alreadyAdded()) {
241                break;
242            }
243            nextSegment->addCurveTo(start, opSpanEnd, &partWriter);
244            opPtT = opSpanEnd->ptT();
245            SkOpPtT** runsPtr = const_cast<SkOpPtT**>(&runs[pIndex]);
246            *runsPtr = opPtT;
247        } while (true);
248        partWriter.finishContour();
249        const SkTArray<SkPath>& partPartials = partWriter.partials();
250        if (!partPartials.count()) {
251            continue;
252        }
253        // if pIndex is even, reverse and prepend to fPartials; otherwise, append
254        SkPath& partial = const_cast<SkPath&>(fPartials[pIndex >> 1]);
255        const SkPath& part = partPartials[0];
256        if (pIndex & 1) {
257            partial.addPath(part, SkPath::kExtend_AddPathMode);
258        } else {
259            SkPath reverse;
260            reverse.reverseAddPath(part);
261            reverse.addPath(partial, SkPath::kExtend_AddPathMode);
262            partial = reverse;
263        }
264    }
265    SkTDArray<int> sLink, eLink;
266    int linkCount = endCount / 2; // number of partial contours
267    sLink.append(linkCount);
268    eLink.append(linkCount);
269    int rIndex, iIndex;
270    for (rIndex = 0; rIndex < linkCount; ++rIndex) {
271        sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
272    }
273    const int entries = endCount * (endCount - 1) / 2;  // folded triangle
274    SkSTArray<8, double, true> distances(entries);
275    SkSTArray<8, int, true> sortedDist(entries);
276    SkSTArray<8, int, true> distLookup(entries);
277    int rRow = 0;
278    int dIndex = 0;
279    for (rIndex = 0; rIndex < endCount - 1; ++rIndex) {
280        const SkOpPtT* oPtT = runs[rIndex];
281        for (iIndex = rIndex + 1; iIndex < endCount; ++iIndex) {
282            const SkOpPtT* iPtT = runs[iIndex];
283            double dx = iPtT->fPt.fX - oPtT->fPt.fX;
284            double dy = iPtT->fPt.fY - oPtT->fPt.fY;
285            double dist = dx * dx + dy * dy;
286            distLookup.push_back(rRow + iIndex);
287            distances.push_back(dist);  // oStart distance from iStart
288            sortedDist.push_back(dIndex++);
289        }
290        rRow += endCount;
291    }
292    SkASSERT(dIndex == entries);
293    SkTQSort<int>(sortedDist.begin(), sortedDist.end(), DistanceLessThan(distances.begin()));
294    int remaining = linkCount;  // number of start/end pairs
295    for (rIndex = 0; rIndex < entries; ++rIndex) {
296        int pair = sortedDist[rIndex];
297        pair = distLookup[pair];
298        int row = pair / endCount;
299        int col = pair - row * endCount;
300        int ndxOne = row >> 1;
301        bool endOne = row & 1;
302        int* linkOne = endOne ? eLink.begin() : sLink.begin();
303        if (linkOne[ndxOne] != SK_MaxS32) {
304            continue;
305        }
306        int ndxTwo = col >> 1;
307        bool endTwo = col & 1;
308        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
309        if (linkTwo[ndxTwo] != SK_MaxS32) {
310            continue;
311        }
312        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
313        bool flip = endOne == endTwo;
314        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
315        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
316        if (!--remaining) {
317            break;
318        }
319    }
320    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    rIndex = 0;
330    do {
331        bool forward = true;
332        bool first = true;
333        int sIndex = sLink[rIndex];
334        SkASSERT(sIndex != SK_MaxS32);
335        sLink[rIndex] = SK_MaxS32;
336        int eIndex;
337        if (sIndex < 0) {
338            eIndex = sLink[~sIndex];
339            sLink[~sIndex] = SK_MaxS32;
340        } else {
341            eIndex = eLink[sIndex];
342            eLink[sIndex] = SK_MaxS32;
343        }
344        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        do {
351            const SkPath& contour = fPartials[rIndex];
352            if (!first) {
353                SkPoint prior, next;
354                if (!fPathPtr->getLastPt(&prior)) {
355                    return;
356                }
357                if (forward) {
358                    next = contour.getPoint(0);
359                } else {
360                    SkAssertResult(contour.getLastPt(&next));
361                }
362                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                }
368            }
369            if (forward) {
370                fPathPtr->addPath(contour,
371                        first ? SkPath::kAppend_AddPathMode : SkPath::kExtend_AddPathMode);
372            } else {
373                SkASSERT(!first);
374                fPathPtr->reversePathTo(contour);
375            }
376            if (first) {
377                first = false;
378            }
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            if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
385                fPathPtr->close();
386                break;
387            }
388            if (forward) {
389                eIndex = eLink[rIndex];
390                SkASSERT(eIndex != SK_MaxS32);
391                eLink[rIndex] = SK_MaxS32;
392                if (eIndex >= 0) {
393                    SkASSERT(sLink[eIndex] == rIndex);
394                    sLink[eIndex] = SK_MaxS32;
395                } else {
396                    SkASSERT(eLink[~eIndex] == ~rIndex);
397                    eLink[~eIndex] = SK_MaxS32;
398                }
399            } else {
400                eIndex = sLink[rIndex];
401                SkASSERT(eIndex != SK_MaxS32);
402                sLink[rIndex] = SK_MaxS32;
403                if (eIndex >= 0) {
404                    SkASSERT(eLink[eIndex] == rIndex);
405                    eLink[eIndex] = SK_MaxS32;
406                } else {
407                    SkASSERT(sLink[~eIndex] == ~rIndex);
408                    sLink[~eIndex] = SK_MaxS32;
409                }
410            }
411            rIndex = eIndex;
412            if (rIndex < 0) {
413                forward ^= 1;
414                rIndex = ~rIndex;
415            }
416        } while (true);
417        for (rIndex = 0; rIndex < linkCount; ++rIndex) {
418            if (sLink[rIndex] != SK_MaxS32) {
419                break;
420            }
421        }
422    } 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    return;
430}
431