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 "SkOpSegment.h"
8 #include "SkOpSpan.h"
9 #include "SkPathOpsPoint.h"
10 #include "SkPathWriter.h"
11 #include "SkTSort.h"
12
13 // wrap path to keep track of whether the contour is initialized and non-empty
SkPathWriter(SkPath & path)14 SkPathWriter::SkPathWriter(SkPath& path)
15 : fPathPtr(&path)
16 {
17 init();
18 }
19
close()20 void 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
conicTo(const SkPoint & pt1,const SkOpPtT * pt2,SkScalar weight)34 void 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
cubicTo(const SkPoint & pt1,const SkPoint & pt2,const SkOpPtT * pt3)43 void 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
deferredLine(const SkOpPtT * pt)52 bool 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
deferredMove(const SkOpPtT * pt)74 void 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
finishContour()86 void 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
init()107 void SkPathWriter::init() {
108 fCurrent.reset();
109 fFirstPtT = fDefer[0] = fDefer[1] = nullptr;
110 }
111
isClosed() const112 bool SkPathWriter::isClosed() const {
113 return this->matchedLast(fFirstPtT);
114 }
115
lineTo()116 void 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
matchedLast(const SkOpPtT * test) const126 bool 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
moveTo()139 void 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
quadTo(const SkPoint & pt1,const SkOpPtT * pt2)146 void 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
update(const SkOpPtT * pt)157 SkPoint 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
someAssemblyRequired()171 bool SkPathWriter::someAssemblyRequired() {
172 this->finishContour();
173 return fEndPtTs.count() > 0;
174 }
175
changedSlopes(const SkOpPtT * ptT) const176 bool 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
185 class DistanceLessThan {
186 public:
DistanceLessThan(double * distances)187 DistanceLessThan(double* distances) : fDistances(distances) { }
188 double* fDistances;
operator ()(const int one,const int two)189 bool operator()(const int one, const int two) {
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 */
assemble()201 void SkPathWriter::assemble() {
202 #if DEBUG_SHOW_TEST_NAME
203 SkDebugf("</div>\n");
204 #endif
205 if (!this->someAssemblyRequired()) {
206 return;
207 }
208 #if DEBUG_PATH_CONSTRUCTION
209 SkDebugf("%s\n", __FUNCTION__);
210 #endif
211 SkOpPtT const* const* runs = fEndPtTs.begin(); // starts, ends of partial contours
212 int endCount = fEndPtTs.count(); // all starts and ends
213 SkASSERT(endCount > 0);
214 SkASSERT(endCount == fPartials.count() * 2);
215 #if DEBUG_ASSEMBLE
216 for (int index = 0; index < endCount; index += 2) {
217 const SkOpPtT* eStart = runs[index];
218 const SkOpPtT* eEnd = runs[index + 1];
219 SkASSERT(eStart != eEnd);
220 SkASSERT(!eStart->contains(eEnd));
221 SkDebugf("%s contour start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", __FUNCTION__,
222 eStart->fPt.fX, eStart->fPt.fY, eEnd->fPt.fX, eEnd->fPt.fY);
223 }
224 #endif
225 // lengthen any partial contour adjacent to a simple segment
226 for (int pIndex = 0; pIndex < endCount; pIndex++) {
227 SkOpPtT* opPtT = const_cast<SkOpPtT*>(runs[pIndex]);
228 SkPath dummy;
229 SkPathWriter partWriter(dummy);
230 do {
231 if (!zero_or_one(opPtT->fT)) {
232 break;
233 }
234 SkOpSpanBase* opSpanBase = opPtT->span();
235 SkOpSpanBase* start = opPtT->fT ? opSpanBase->prev() : opSpanBase->upCast()->next();
236 int step = opPtT->fT ? 1 : -1;
237 const SkOpSegment* opSegment = opSpanBase->segment();
238 const SkOpSegment* nextSegment = opSegment->isSimple(&start, &step);
239 if (!nextSegment) {
240 break;
241 }
242 SkOpSpanBase* opSpanEnd = start->t() ? start->prev() : start->upCast()->next();
243 if (start->starter(opSpanEnd)->alreadyAdded()) {
244 break;
245 }
246 nextSegment->addCurveTo(start, opSpanEnd, &partWriter);
247 opPtT = opSpanEnd->ptT();
248 SkOpPtT** runsPtr = const_cast<SkOpPtT**>(&runs[pIndex]);
249 *runsPtr = opPtT;
250 } while (true);
251 partWriter.finishContour();
252 const SkTArray<SkPath>& partPartials = partWriter.partials();
253 if (!partPartials.count()) {
254 continue;
255 }
256 // if pIndex is even, reverse and prepend to fPartials; otherwise, append
257 SkPath& partial = const_cast<SkPath&>(fPartials[pIndex >> 1]);
258 const SkPath& part = partPartials[0];
259 if (pIndex & 1) {
260 partial.addPath(part, SkPath::kExtend_AddPathMode);
261 } else {
262 SkPath reverse;
263 reverse.reverseAddPath(part);
264 reverse.addPath(partial, SkPath::kExtend_AddPathMode);
265 partial = reverse;
266 }
267 }
268 SkTDArray<int> sLink, eLink;
269 int linkCount = endCount / 2; // number of partial contours
270 sLink.append(linkCount);
271 eLink.append(linkCount);
272 int rIndex, iIndex;
273 for (rIndex = 0; rIndex < linkCount; ++rIndex) {
274 sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
275 }
276 const int entries = endCount * (endCount - 1) / 2; // folded triangle
277 SkSTArray<8, double, true> distances(entries);
278 SkSTArray<8, int, true> sortedDist(entries);
279 SkSTArray<8, int, true> distLookup(entries);
280 int rRow = 0;
281 int dIndex = 0;
282 for (rIndex = 0; rIndex < endCount - 1; ++rIndex) {
283 const SkOpPtT* oPtT = runs[rIndex];
284 for (iIndex = rIndex + 1; iIndex < endCount; ++iIndex) {
285 const SkOpPtT* iPtT = runs[iIndex];
286 double dx = iPtT->fPt.fX - oPtT->fPt.fX;
287 double dy = iPtT->fPt.fY - oPtT->fPt.fY;
288 double dist = dx * dx + dy * dy;
289 distLookup.push_back(rRow + iIndex);
290 distances.push_back(dist); // oStart distance from iStart
291 sortedDist.push_back(dIndex++);
292 }
293 rRow += endCount;
294 }
295 SkASSERT(dIndex == entries);
296 SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
297 int remaining = linkCount; // number of start/end pairs
298 for (rIndex = 0; rIndex < entries; ++rIndex) {
299 int pair = sortedDist[rIndex];
300 pair = distLookup[pair];
301 int row = pair / endCount;
302 int col = pair - row * endCount;
303 int ndxOne = row >> 1;
304 bool endOne = row & 1;
305 int* linkOne = endOne ? eLink.begin() : sLink.begin();
306 if (linkOne[ndxOne] != SK_MaxS32) {
307 continue;
308 }
309 int ndxTwo = col >> 1;
310 bool endTwo = col & 1;
311 int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
312 if (linkTwo[ndxTwo] != SK_MaxS32) {
313 continue;
314 }
315 SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
316 bool flip = endOne == endTwo;
317 linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
318 linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
319 if (!--remaining) {
320 break;
321 }
322 }
323 SkASSERT(!remaining);
324 #if DEBUG_ASSEMBLE
325 for (rIndex = 0; rIndex < linkCount; ++rIndex) {
326 int s = sLink[rIndex];
327 int e = eLink[rIndex];
328 SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
329 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
330 }
331 #endif
332 rIndex = 0;
333 do {
334 bool forward = true;
335 bool first = true;
336 int sIndex = sLink[rIndex];
337 SkASSERT(sIndex != SK_MaxS32);
338 sLink[rIndex] = SK_MaxS32;
339 int eIndex;
340 if (sIndex < 0) {
341 eIndex = sLink[~sIndex];
342 sLink[~sIndex] = SK_MaxS32;
343 } else {
344 eIndex = eLink[sIndex];
345 eLink[sIndex] = SK_MaxS32;
346 }
347 SkASSERT(eIndex != SK_MaxS32);
348 #if DEBUG_ASSEMBLE
349 SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
350 sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
351 eIndex < 0 ? ~eIndex : eIndex);
352 #endif
353 do {
354 const SkPath& contour = fPartials[rIndex];
355 if (!first) {
356 SkPoint prior, next;
357 if (!fPathPtr->getLastPt(&prior)) {
358 return;
359 }
360 if (forward) {
361 next = contour.getPoint(0);
362 } else {
363 SkAssertResult(contour.getLastPt(&next));
364 }
365 if (prior != next) {
366 /* TODO: if there is a gap between open path written so far and path to come,
367 connect by following segments from one to the other, rather than introducing
368 a diagonal to connect the two.
369 */
370 SkDebugf("");
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