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