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