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