1 /* 2 * Copyright 2015 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 8 // given a prospective edge, compute its initial winding by projecting a ray 9 // if the ray hits another edge 10 // if the edge doesn't have a winding yet, hop up to that edge and start over 11 // concern : check for hops forming a loop 12 // if the edge is unsortable, or 13 // the intersection is nearly at the ends, or 14 // the tangent at the intersection is nearly coincident to the ray, 15 // choose a different ray and try again 16 // concern : if it is unable to succeed after N tries, try another edge? direction? 17 // if no edge is hit, compute the winding directly 18 19 // given the top span, project the most perpendicular ray and look for intersections 20 // let's try up and then down. What the hey 21 22 // bestXY is initialized by caller with basePt 23 24 #include "SkOpContour.h" 25 #include "SkOpSegment.h" 26 #include "SkPathOpsCurve.h" 27 28 enum class SkOpRayDir { 29 kLeft, 30 kTop, 31 kRight, 32 kBottom, 33 }; 34 35 #if DEBUG_WINDING 36 const char* gDebugRayDirName[] = { 37 "kLeft", 38 "kTop", 39 "kRight", 40 "kBottom" 41 }; 42 #endif 43 44 static int xy_index(SkOpRayDir dir) { 45 return static_cast<int>(dir) & 1; 46 } 47 48 static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) { 49 return (&pt.fX)[xy_index(dir)]; 50 } 51 52 static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) { 53 return (&pt.fX)[!xy_index(dir)]; 54 } 55 56 static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) { 57 return (&v.fX)[xy_index(dir)]; 58 } 59 60 static double pt_dydx(const SkDVector& v, SkOpRayDir dir) { 61 return (&v.fX)[!xy_index(dir)]; 62 } 63 64 static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) { 65 return (&r.fLeft)[static_cast<int>(dir)]; 66 } 67 68 static bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) { 69 int i = !xy_index(dir); 70 return approximately_between((&rect.fLeft)[i], (&pt.fX)[i], (&rect.fRight)[i]); 71 } 72 73 static bool less_than(SkOpRayDir dir) { 74 return static_cast<bool>((static_cast<int>(dir) & 2) == 0); 75 } 76 77 static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) { 78 bool vPartPos = pt_dydx(v, dir) > 0; 79 bool leftBottom = ((static_cast<int>(dir) + 1) & 2) != 0; 80 return vPartPos == leftBottom; 81 } 82 83 struct SkOpRayHit { 84 SkOpRayDir makeTestBase(SkOpSpan* span, double t) { 85 fNext = nullptr; 86 fSpan = span; 87 fT = span->t() * (1 - t) + span->next()->t() * t; 88 SkOpSegment* segment = span->segment(); 89 fSlope = segment->dSlopeAtT(fT); 90 fPt = segment->ptAtT(fT); 91 fValid = true; 92 return fabs(fSlope.fX) < fabs(fSlope.fY) ? SkOpRayDir::kLeft : SkOpRayDir::kTop; 93 } 94 95 SkOpRayHit* fNext; 96 SkOpSpan* fSpan; 97 SkPoint fPt; 98 double fT; 99 SkDVector fSlope; 100 bool fValid; 101 }; 102 103 void SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, 104 SkArenaAlloc* allocator) { 105 // if the bounds extreme is outside the best, we're done 106 SkScalar baseXY = pt_xy(base.fPt, dir); 107 SkScalar boundsXY = rect_side(fBounds, dir); 108 bool checkLessThan = less_than(dir); 109 if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) { 110 return; 111 } 112 SkOpSegment* testSegment = &fHead; 113 do { 114 testSegment->rayCheck(base, dir, hits, allocator); 115 } while ((testSegment = testSegment->next())); 116 } 117 118 void SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, 119 SkArenaAlloc* allocator) { 120 if (!sideways_overlap(fBounds, base.fPt, dir)) { 121 return; 122 } 123 SkScalar baseXY = pt_xy(base.fPt, dir); 124 SkScalar boundsXY = rect_side(fBounds, dir); 125 bool checkLessThan = less_than(dir); 126 if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) { 127 return; 128 } 129 double tVals[3]; 130 SkScalar baseYX = pt_yx(base.fPt, dir); 131 int roots = (*CurveIntercept[fVerb * 2 + xy_index(dir)])(fPts, fWeight, baseYX, tVals); 132 for (int index = 0; index < roots; ++index) { 133 double t = tVals[index]; 134 if (base.fSpan->segment() == this && approximately_equal(base.fT, t)) { 135 continue; 136 } 137 SkDVector slope; 138 SkPoint pt; 139 SkDEBUGCODE(sk_bzero(&slope, sizeof(slope))); 140 bool valid = false; 141 if (approximately_zero(t)) { 142 pt = fPts[0]; 143 } else if (approximately_equal(t, 1)) { 144 pt = fPts[SkPathOpsVerbToPoints(fVerb)]; 145 } else { 146 SkASSERT(between(0, t, 1)); 147 pt = this->ptAtT(t); 148 if (SkDPoint::ApproximatelyEqual(pt, base.fPt)) { 149 if (base.fSpan->segment() == this) { 150 continue; 151 } 152 } else { 153 SkScalar ptXY = pt_xy(pt, dir); 154 if (!approximately_equal(baseXY, ptXY) && (baseXY < ptXY) == checkLessThan) { 155 continue; 156 } 157 slope = this->dSlopeAtT(t); 158 if (fVerb == SkPath::kCubic_Verb && base.fSpan->segment() == this 159 && roughly_equal(base.fT, t) 160 && SkDPoint::RoughlyEqual(pt, base.fPt)) { 161 #if DEBUG_WINDING 162 SkDebugf("%s (rarely expect this)\n", __FUNCTION__); 163 #endif 164 continue; 165 } 166 if (fabs(pt_dydx(slope, dir) * 10000) > fabs(pt_dxdy(slope, dir))) { 167 valid = true; 168 } 169 } 170 } 171 SkOpSpan* span = this->windingSpanAtT(t); 172 if (!span) { 173 valid = false; 174 } else if (!span->windValue() && !span->oppValue()) { 175 continue; 176 } 177 SkOpRayHit* newHit = SkOpTAllocator<SkOpRayHit>::Allocate(allocator); 178 newHit->fNext = *hits; 179 newHit->fPt = pt; 180 newHit->fSlope = slope; 181 newHit->fSpan = span; 182 newHit->fT = t; 183 newHit->fValid = valid; 184 *hits = newHit; 185 } 186 } 187 188 SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) { 189 SkOpSpan* span = &fHead; 190 SkOpSpanBase* next; 191 do { 192 next = span->next(); 193 if (approximately_equal(tHit, next->t())) { 194 return nullptr; 195 } 196 if (tHit < next->t()) { 197 return span; 198 } 199 } while (!next->final() && (span = next->upCast())); 200 return nullptr; 201 } 202 203 static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { 204 return a->fPt.fX < b->fPt.fX; 205 } 206 207 static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { 208 return b->fPt.fX < a->fPt.fX; 209 } 210 211 static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { 212 return a->fPt.fY < b->fPt.fY; 213 } 214 215 static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { 216 return b->fPt.fY < a->fPt.fY; 217 } 218 219 static double get_t_guess(int tTry, int* dirOffset) { 220 double t = 0.5; 221 *dirOffset = tTry & 1; 222 int tBase = tTry >> 1; 223 int tBits = 0; 224 while (tTry >>= 1) { 225 t /= 2; 226 ++tBits; 227 } 228 if (tBits) { 229 int tIndex = (tBase - 1) & ((1 << tBits) - 1); 230 t += t * 2 * tIndex; 231 } 232 return t; 233 } 234 235 bool SkOpSpan::sortableTop(SkOpContour* contourHead) { 236 char storage[1024]; 237 SkArenaAlloc allocator(storage); 238 int dirOffset; 239 double t = get_t_guess(fTopTTry++, &dirOffset); 240 SkOpRayHit hitBase; 241 SkOpRayDir dir = hitBase.makeTestBase(this, t); 242 if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) { 243 return false; 244 } 245 SkOpRayHit* hitHead = &hitBase; 246 dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset); 247 if (hitBase.fSpan && hitBase.fSpan->segment()->verb() > SkPath::kLine_Verb 248 && !pt_yx(hitBase.fSlope.asSkVector(), dir)) { 249 return false; 250 } 251 SkOpContour* contour = contourHead; 252 do { 253 if (!contour->count()) { 254 continue; 255 } 256 contour->rayCheck(hitBase, dir, &hitHead, &allocator); 257 } while ((contour = contour->next())); 258 // sort hits 259 SkSTArray<1, SkOpRayHit*> sorted; 260 SkOpRayHit* hit = hitHead; 261 while (hit) { 262 sorted.push_back(hit); 263 hit = hit->fNext; 264 } 265 int count = sorted.count(); 266 SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir) 267 ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y 268 : less_than(dir) ? hit_compare_x : reverse_hit_compare_x); 269 // verify windings 270 #if DEBUG_WINDING 271 SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__, 272 gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(), 273 hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY); 274 for (int index = 0; index < count; ++index) { 275 hit = sorted[index]; 276 SkOpSpan* span = hit->fSpan; 277 SkOpSegment* hitSegment = span ? span->segment() : nullptr; 278 bool operand = span ? hitSegment->operand() : false; 279 bool ccw = ccw_dxdy(hit->fSlope, dir); 280 SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index, 281 hit->fValid, operand, span ? span->debugID() : -1, ccw); 282 if (span) { 283 hitSegment->dumpPtsInner(); 284 } 285 SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT, 286 hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY); 287 } 288 #endif 289 const SkPoint* last = nullptr; 290 int wind = 0; 291 int oppWind = 0; 292 for (int index = 0; index < count; ++index) { 293 hit = sorted[index]; 294 if (!hit->fValid) { 295 return false; 296 } 297 bool ccw = ccw_dxdy(hit->fSlope, dir); 298 // SkASSERT(!approximately_zero(hit->fT) || !hit->fValid); 299 SkOpSpan* span = hit->fSpan; 300 if (!span) { 301 return false; 302 } 303 SkOpSegment* hitSegment = span->segment(); 304 if (span->windValue() == 0 && span->oppValue() == 0) { 305 continue; 306 } 307 if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) { 308 return false; 309 } 310 if (index < count - 1) { 311 const SkPoint& next = sorted[index + 1]->fPt; 312 if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) { 313 return false; 314 } 315 } 316 bool operand = hitSegment->operand(); 317 if (operand) { 318 SkTSwap(wind, oppWind); 319 } 320 int lastWind = wind; 321 int lastOpp = oppWind; 322 int windValue = ccw ? -span->windValue() : span->windValue(); 323 int oppValue = ccw ? -span->oppValue() : span->oppValue(); 324 wind += windValue; 325 oppWind += oppValue; 326 bool sumSet = false; 327 int spanSum = span->windSum(); 328 int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind; 329 if (spanSum == SK_MinS32) { 330 span->setWindSum(windSum); 331 sumSet = true; 332 } else { 333 // the need for this condition suggests that UseInnerWinding is flawed 334 // happened when last = 1 wind = -1 335 #if 0 336 SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum) 337 || (abs(wind) == abs(lastWind) 338 && (windSum ^ wind ^ lastWind) == spanSum)); 339 #endif 340 } 341 int oSpanSum = span->oppSum(); 342 int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp; 343 if (oSpanSum == SK_MinS32) { 344 span->setOppSum(oppSum); 345 } else { 346 #if 0 347 SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum 348 || (abs(oppWind) == abs(lastOpp) 349 && (oppSum ^ oppWind ^ lastOpp) == oSpanSum)); 350 #endif 351 } 352 if (sumSet) { 353 if (this->globalState()->phase() == SkOpPhase::kFixWinding) { 354 hitSegment->contour()->setCcw(ccw); 355 } else { 356 (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, nullptr); 357 (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, nullptr); 358 } 359 } 360 if (operand) { 361 SkTSwap(wind, oppWind); 362 } 363 last = &hit->fPt; 364 this->globalState()->bumpNested(); 365 } 366 return true; 367 } 368 369 SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) { 370 SkOpSpan* span = &fHead; 371 SkOpSpanBase* next; 372 do { 373 next = span->next(); 374 if (span->done()) { 375 continue; 376 } 377 if (span->windSum() != SK_MinS32) { 378 return span; 379 } 380 if (span->sortableTop(contourHead)) { 381 return span; 382 } 383 } while (!next->final() && (span = next->upCast())); 384 return nullptr; 385 } 386 387 SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) { 388 bool allDone = true; 389 if (fCount) { 390 SkOpSegment* testSegment = &fHead; 391 do { 392 if (testSegment->done()) { 393 continue; 394 } 395 allDone = false; 396 SkOpSpan* result = testSegment->findSortableTop(contourHead); 397 if (result) { 398 return result; 399 } 400 } while ((testSegment = testSegment->next())); 401 } 402 if (allDone) { 403 fDone = true; 404 } 405 return nullptr; 406 } 407 408 SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) { 409 for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) { 410 SkOpContour* contour = contourHead; 411 do { 412 if (contour->done()) { 413 continue; 414 } 415 SkOpSpan* result = contour->findSortableTop(contourHead); 416 if (result) { 417 return result; 418 } 419 } while ((contour = contour->next())); 420 } 421 return nullptr; 422 } 423
