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