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