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