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