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 #include <utility>
29 
30 enum class SkOpRayDir {
31     kLeft,
32     kTop,
33     kRight,
34     kBottom,
35 };
36 
37 #if DEBUG_WINDING
38 const char* gDebugRayDirName[] = {
39     "kLeft",
40     "kTop",
41     "kRight",
42     "kBottom"
43 };
44 #endif
45 
46 static int xy_index(SkOpRayDir dir) {
47     return static_cast<int>(dir) & 1;
48 }
49 
50 static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) {
51     return (&pt.fX)[xy_index(dir)];
52 }
53 
54 static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) {
55     return (&pt.fX)[!xy_index(dir)];
56 }
57 
58 static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) {
59     return (&v.fX)[xy_index(dir)];
60 }
61 
62 static double pt_dydx(const SkDVector& v, SkOpRayDir dir) {
63     return (&v.fX)[!xy_index(dir)];
64 }
65 
66 static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) {
67     return (&r.fLeft)[static_cast<int>(dir)];
68 }
69 
70 static 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 
75 static bool less_than(SkOpRayDir dir) {
76     return static_cast<bool>((static_cast<int>(dir) & 2) == 0);
77 }
78 
79 static 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 
85 struct 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 
105 void 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 
120 void 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 
190 SkOpSpan* 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 
205 static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
206     return a->fPt.fX < b->fPt.fX;
207 }
208 
209 static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
210     return b->fPt.fX  < a->fPt.fX;
211 }
212 
213 static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
214     return a->fPt.fY < b->fPt.fY;
215 }
216 
217 static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
218     return b->fPt.fY  < a->fPt.fY;
219 }
220 
221 static 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 
237 bool 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 
372 SkOpSpan* 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 
390 SkOpSpan* 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 
411 SkOpSpan* 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