1/*
2 * Copyright 2015 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
8#include "SubsetPath.h"
9#include "SkMathPriv.h"
10
11SubsetPath::SubsetPath(const SkPath& path)
12        : fPath(path)
13        , fSubset(1) {
14}
15
16int SubsetPath::range(int* end) const {
17    int leadingZero = SkCLZ(fSubset);
18    int parts = 1 << (31 - leadingZero);
19    int partIndex = fSubset - parts;
20    SkASSERT(partIndex >= 0);
21    int count = fSelected.count();
22    int start = count * partIndex / parts;
23    *end = count * (partIndex + 1) / parts;
24    return start;
25}
26
27bool SubsetPath::subset(bool testFailed, SkPath* sub) {
28    int start, end;
29    if (!testFailed) {
30        start = range(&end);
31        for (; start < end; ++start) {
32            fSelected[start] = true;
33        }
34    }
35    do {
36        do {
37            ++fSubset;
38            start = range(&end);
39 //           SkDebugf("%d s=%d e=%d t=%d\n", fSubset, start, end, fTries);
40            if (end - start > 1) {
41                fTries = fSelected.count();
42            } else if (end - start == 1) {
43                if (--fTries <= 0) {
44                    return false;
45                }
46            }
47        } while (start == end);
48    } while (!fSelected[start]);
49    for (; start < end; ++start) {
50        fSelected[start] = false;
51    }
52#if 1
53    SkDebugf("selected: ");
54    for (int index = 0; index < fSelected.count(); ++index) {
55        SkDebugf("%c", fSelected[index] ? 'x' : '-');
56    }
57#endif
58    *sub = getSubsetPath();
59    return true;
60}
61
62SubsetContours::SubsetContours(const SkPath& path)
63        : SubsetPath(path) {
64    SkPath::RawIter iter(fPath);
65    uint8_t verb;
66    SkPoint pts[4];
67    bool foundCurve = false;
68    int contourCount = 0;
69    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
70        switch (verb) {
71            case SkPath::kMove_Verb:
72                break;
73            case SkPath::kLine_Verb:
74            case SkPath::kQuad_Verb:
75            case SkPath::kConic_Verb:
76            case SkPath::kCubic_Verb:
77                foundCurve = true;
78                break;
79            case SkPath::kClose_Verb:
80                ++contourCount;
81                foundCurve = false;
82                break;
83            default:
84                SkDEBUGFAIL("bad verb");
85                return;
86        }
87    }
88    contourCount += foundCurve;
89    for (int index = 0; index < contourCount; ++index) {
90        *fSelected.append() = true;
91    }
92    fTries = contourCount;
93}
94
95SkPath SubsetContours::getSubsetPath() const {
96    SkPath result;
97    result.setFillType(fPath.getFillType());
98    if (!fSelected.count()) {
99        return result;
100    }
101    SkPath::RawIter iter(fPath);
102    uint8_t verb;
103    SkPoint pts[4];
104    int contourCount = 0;
105    bool enabled = fSelected[0];
106    bool addMoveTo = true;
107    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
108        if (enabled && addMoveTo) {
109            result.moveTo(pts[0]);
110            addMoveTo = false;
111        }
112        switch (verb) {
113            case SkPath::kMove_Verb:
114                break;
115            case SkPath::kLine_Verb:
116                if (enabled) {
117                    result.lineTo(pts[1]);
118                }
119                break;
120            case SkPath::kQuad_Verb:
121                if (enabled) {
122                    result.quadTo(pts[1], pts[2]);
123                }
124                break;
125            case SkPath::kConic_Verb:
126                if (enabled) {
127                    result.conicTo(pts[1], pts[2], iter.conicWeight());
128                }
129                break;
130            case SkPath::kCubic_Verb:
131                 if (enabled) {
132                    result.cubicTo(pts[1], pts[2], pts[3]);
133                }
134                break;
135            case SkPath::kClose_Verb:
136                if (enabled) {
137                    result.close();
138                }
139                if (++contourCount >= fSelected.count()) {
140                    break;
141                }
142                enabled = fSelected[contourCount];
143                addMoveTo = true;
144                continue;
145            default:
146                SkDEBUGFAIL("bad verb");
147                return result;
148        }
149    }
150    return result;
151}
152
153SubsetVerbs::SubsetVerbs(const SkPath& path)
154        : SubsetPath(path) {
155    SkPath::RawIter iter(fPath);
156    uint8_t verb;
157    SkPoint pts[4];
158    int verbCount = 0;
159    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
160        switch (verb) {
161            case SkPath::kMove_Verb:
162                break;
163            case SkPath::kLine_Verb:
164            case SkPath::kQuad_Verb:
165            case SkPath::kConic_Verb:
166            case SkPath::kCubic_Verb:
167                ++verbCount;
168                break;
169            case SkPath::kClose_Verb:
170                break;
171            default:
172                SkDEBUGFAIL("bad verb");
173                return;
174        }
175    }
176    for (int index = 0; index < verbCount; ++index) {
177        *fSelected.append() = true;
178    }
179    fTries = verbCount;
180}
181
182SkPath SubsetVerbs::getSubsetPath() const {
183    SkPath result;
184    result.setFillType(fPath.getFillType());
185    if (!fSelected.count()) {
186        return result;
187    }
188    SkPath::RawIter iter(fPath);
189    uint8_t verb;
190    SkPoint pts[4];
191    int verbIndex = 0;
192    bool addMoveTo = true;
193    bool addLineTo = false;
194    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
195        bool enabled = SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb
196            ? fSelected[verbIndex++] : false;
197        if (enabled) {
198            if (addMoveTo) {
199                result.moveTo(pts[0]);
200                addMoveTo = false;
201            } else if (addLineTo) {
202                result.lineTo(pts[0]);
203                addLineTo = false;
204            }
205        }
206        switch (verb) {
207            case SkPath::kMove_Verb:
208                break;
209            case SkPath::kLine_Verb:
210                if (enabled) {
211                    result.lineTo(pts[1]);
212                }
213                break;
214            case SkPath::kQuad_Verb:
215                if (enabled) {
216                    result.quadTo(pts[1], pts[2]);
217                }
218                break;
219            case SkPath::kConic_Verb:
220                if (enabled) {
221                    result.conicTo(pts[1], pts[2], iter.conicWeight());
222                }
223                break;
224            case SkPath::kCubic_Verb:
225                 if (enabled) {
226                    result.cubicTo(pts[1], pts[2], pts[3]);
227                }
228                break;
229            case SkPath::kClose_Verb:
230                result.close();
231                addMoveTo = true;
232                addLineTo = false;
233                continue;
234            default:
235                SkDEBUGFAIL("bad verb");
236                return result;
237        }
238        addLineTo = !enabled;
239    }
240    return result;
241}
242