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