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