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 14 SkPathWriter::SkPathWriter(SkPath& path) 15 : fPathPtr(&path) 16 { 17 init(); 18 } 19 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 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 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 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 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 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 107 void SkPathWriter::init() { 108 fCurrent.reset(); 109 fFirstPtT = fDefer[0] = fDefer[1] = nullptr; 110 } 111 112 bool SkPathWriter::isClosed() const { 113 return this->matchedLast(fFirstPtT); 114 } 115 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 126 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 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 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 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 171 bool SkPathWriter::someAssemblyRequired() { 172 this->finishContour(); 173 return fEndPtTs.count() > 0; 174 } 175 176 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: 187 DistanceLessThan(double* distances) : fDistances(distances) { } 188 double* fDistances; 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 */ 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