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 = allocator->make<SkOpRayHit>(); 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 SkSTArenaAlloc<1024> allocator; 237 int dirOffset; 238 double t = get_t_guess(fTopTTry++, &dirOffset); 239 SkOpRayHit hitBase; 240 SkOpRayDir dir = hitBase.makeTestBase(this, t); 241 if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) { 242 return false; 243 } 244 SkOpRayHit* hitHead = &hitBase; 245 dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset); 246 if (hitBase.fSpan && hitBase.fSpan->segment()->verb() > SkPath::kLine_Verb 247 && !pt_yx(hitBase.fSlope.asSkVector(), dir)) { 248 return false; 249 } 250 SkOpContour* contour = contourHead; 251 do { 252 if (!contour->count()) { 253 continue; 254 } 255 contour->rayCheck(hitBase, dir, &hitHead, &allocator); 256 } while ((contour = contour->next())); 257 // sort hits 258 SkSTArray<1, SkOpRayHit*> sorted; 259 SkOpRayHit* hit = hitHead; 260 while (hit) { 261 sorted.push_back(hit); 262 hit = hit->fNext; 263 } 264 int count = sorted.count(); 265 SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir) 266 ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y 267 : less_than(dir) ? hit_compare_x : reverse_hit_compare_x); 268 // verify windings 269 #if DEBUG_WINDING 270 SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__, 271 gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(), 272 hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY); 273 for (int index = 0; index < count; ++index) { 274 hit = sorted[index]; 275 SkOpSpan* span = hit->fSpan; 276 SkOpSegment* hitSegment = span ? span->segment() : nullptr; 277 bool operand = span ? hitSegment->operand() : false; 278 bool ccw = ccw_dxdy(hit->fSlope, dir); 279 SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index, 280 hit->fValid, operand, span ? span->debugID() : -1, ccw); 281 if (span) { 282 hitSegment->dumpPtsInner(); 283 } 284 SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT, 285 hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY); 286 } 287 #endif 288 const SkPoint* last = nullptr; 289 int wind = 0; 290 int oppWind = 0; 291 for (int index = 0; index < count; ++index) { 292 hit = sorted[index]; 293 if (!hit->fValid) { 294 return false; 295 } 296 bool ccw = ccw_dxdy(hit->fSlope, dir); 297 // SkASSERT(!approximately_zero(hit->fT) || !hit->fValid); 298 SkOpSpan* span = hit->fSpan; 299 if (!span) { 300 return false; 301 } 302 SkOpSegment* hitSegment = span->segment(); 303 if (span->windValue() == 0 && span->oppValue() == 0) { 304 continue; 305 } 306 if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) { 307 return false; 308 } 309 if (index < count - 1) { 310 const SkPoint& next = sorted[index + 1]->fPt; 311 if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) { 312 return false; 313 } 314 } 315 bool operand = hitSegment->operand(); 316 if (operand) { 317 SkTSwap(wind, oppWind); 318 } 319 int lastWind = wind; 320 int lastOpp = oppWind; 321 int windValue = ccw ? -span->windValue() : span->windValue(); 322 int oppValue = ccw ? -span->oppValue() : span->oppValue(); 323 wind += windValue; 324 oppWind += oppValue; 325 bool sumSet = false; 326 int spanSum = span->windSum(); 327 int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind; 328 if (spanSum == SK_MinS32) { 329 span->setWindSum(windSum); 330 sumSet = true; 331 } else { 332 // the need for this condition suggests that UseInnerWinding is flawed 333 // happened when last = 1 wind = -1 334 #if 0 335 SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum) 336 || (abs(wind) == abs(lastWind) 337 && (windSum ^ wind ^ lastWind) == spanSum)); 338 #endif 339 } 340 int oSpanSum = span->oppSum(); 341 int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp; 342 if (oSpanSum == SK_MinS32) { 343 span->setOppSum(oppSum); 344 } else { 345 #if 0 346 SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum 347 || (abs(oppWind) == abs(lastOpp) 348 && (oppSum ^ oppWind ^ lastOpp) == oSpanSum)); 349 #endif 350 } 351 if (sumSet) { 352 if (this->globalState()->phase() == SkOpPhase::kFixWinding) { 353 hitSegment->contour()->setCcw(ccw); 354 } else { 355 (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, nullptr); 356 (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, nullptr); 357 } 358 } 359 if (operand) { 360 SkTSwap(wind, oppWind); 361 } 362 last = &hit->fPt; 363 this->globalState()->bumpNested(); 364 } 365 return true; 366 } 367 368 SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) { 369 SkOpSpan* span = &fHead; 370 SkOpSpanBase* next; 371 do { 372 next = span->next(); 373 if (span->done()) { 374 continue; 375 } 376 if (span->windSum() != SK_MinS32) { 377 return span; 378 } 379 if (span->sortableTop(contourHead)) { 380 return span; 381 } 382 } while (!next->final() && (span = next->upCast())); 383 return nullptr; 384 } 385 386 SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) { 387 bool allDone = true; 388 if (fCount) { 389 SkOpSegment* testSegment = &fHead; 390 do { 391 if (testSegment->done()) { 392 continue; 393 } 394 allDone = false; 395 SkOpSpan* result = testSegment->findSortableTop(contourHead); 396 if (result) { 397 return result; 398 } 399 } while ((testSegment = testSegment->next())); 400 } 401 if (allDone) { 402 fDone = true; 403 } 404 return nullptr; 405 } 406 407 SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) { 408 for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) { 409 SkOpContour* contour = contourHead; 410 do { 411 if (contour->done()) { 412 continue; 413 } 414 SkOpSpan* result = contour->findSortableTop(contourHead); 415 if (result) { 416 return result; 417 } 418 } while ((contour = contour->next())); 419 } 420 return nullptr; 421 } 422
