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