1/*
2 * Copyright 2012 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#include "SkIntersections.h"
8#include "SkOpAngle.h"
9#include "SkOpSegment.h"
10#include "SkPathOpsCurve.h"
11#include "SkTSort.h"
12
13#if DEBUG_ANGLE
14#include "SkString.h"
15
16static const char funcName[] = "SkOpSegment::operator<";
17static const int bugChar = strlen(funcName) + 1;
18#endif
19
20/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
21   positive y. The largest angle has a positive x and a zero y. */
22
23#if DEBUG_ANGLE
24    static bool CompareResult(SkString* bugOut, const char* append, bool compare) {
25        bugOut->appendf("%s", append);
26        bugOut->writable_str()[bugChar] = "><"[compare];
27        SkDebugf("%s\n", bugOut->c_str());
28        return compare;
29    }
30
31    #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare)
32#else
33    #define COMPARE_RESULT(append, compare) compare
34#endif
35
36bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{
37    double absX = fabs(x);
38    double absY = fabs(y);
39    double length = absX < absY ? absX / 2 + absY : absX + absY / 2;
40    int exponent;
41    (void) frexp(length, &exponent);
42    double epsilon = ldexp(FLT_EPSILON, exponent);
43    SkPath::Verb verb = fSegment->verb();
44    SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb);
45    // FIXME: the quad and cubic factors are made up ; determine actual values
46    double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon;
47    double xSlop = slop;
48    double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ?
49    double x1 = x - xSlop;
50    double y1 = y + ySlop;
51    double x_ry1 = x1 * ry;
52    double rx_y1 = rx * y1;
53    *result = x_ry1 < rx_y1;
54    double x2 = x + xSlop;
55    double y2 = y - ySlop;
56    double x_ry2 = x2 * ry;
57    double rx_y2 = rx * y2;
58    bool less2 = x_ry2 < rx_y2;
59    return *result == less2;
60}
61
62/*
63for quads and cubics, set up a parameterized line (e.g. LineParameters )
64for points [0] to [1]. See if point [2] is on that line, or on one side
65or the other. If it both quads' end points are on the same side, choose
66the shorter tangent. If the tangents are equal, choose the better second
67tangent angle
68
69FIXME: maybe I could set up LineParameters lazily
70*/
71bool SkOpAngle::operator<(const SkOpAngle& rh) const {  // this/lh: left-hand; rh: right-hand
72    double y = dy();
73    double ry = rh.dy();
74#if DEBUG_ANGLE
75    SkString bugOut;
76    bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g"
77        " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName,
78        fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd),
79        rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
80#endif
81    double y_ry = y * ry;
82    if (y_ry < 0) {  // if y's are opposite signs, we can do a quick return
83        return COMPARE_RESULT("1 y * ry < 0", y < 0);
84    }
85    // at this point, both y's must be the same sign, or one (or both) is zero
86    double x = dx();
87    double rx = rh.dx();
88    if (x * rx < 0) {  // if x's are opposite signs, use y to determine first or second half
89        if (y < 0 && ry < 0) {  // if y's are negative, lh x is smaller if positive
90            return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0);
91        }
92        if (y >= 0 && ry >= 0) {  // if y's are zero or positive, lh x is smaller if negative
93            return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0);
94        }
95        SkASSERT((y == 0) ^ (ry == 0));  // if one y is zero and one is negative, neg y is smaller
96        return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0);
97    }
98    // at this point, both x's must be the same sign, or one (or both) is zero
99    if (y_ry == 0) { // if either y is zero
100        if (y + ry < 0) { // if the other y is less than zero, it must be smaller
101            return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0);
102        }
103        if (y + ry > 0) { // if a y is greater than zero and an x is positive,  non zero is smaller
104            return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0));
105        }
106        // at this point, both y's are zero, so lines are coincident or one is degenerate
107        SkASSERT(x * rx != 0);  // and a degenerate line should haven't gotten this far
108    }
109    // see if either curve can be lengthened before trying the tangent
110    if (fSegment->other(fEnd) != rh.fSegment  // tangents not absolutely identical
111            && rh.fSegment->other(rh.fEnd) != fSegment) {  // and not intersecting
112        SkOpAngle longer = *this;
113        SkOpAngle rhLonger = rh;
114        if ((longer.lengthen(rh) | rhLonger.lengthen(*this))  // lengthen both
115                && (fUnorderable || !longer.fUnorderable)
116                && (rh.fUnorderable || !rhLonger.fUnorderable)) {
117#if DEBUG_ANGLE
118            bugOut.prepend("  ");
119#endif
120            return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger);
121        }
122    }
123    if (y_ry != 0) { // if they aren't coincident, look for a stable cross product
124        // at this point, y's are the same sign, neither is zero
125        //   and x's are the same sign, or one (or both) is zero
126        double x_ry = x * ry;
127        double rx_y = rx * y;
128        if (!fComputed && !rh.fComputed) {
129            if (!AlmostEqualUlps(x_ry, rx_y)) {
130                return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y);
131            }
132        } else {
133            // if the vector was a result of subdividing a curve, see if it is stable
134            bool sloppy1 = x_ry < rx_y;
135            bool sloppy2 = !sloppy1;
136            if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1))
137                    && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2))
138                    && sloppy1 != sloppy2) {
139                return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1);
140            }
141        }
142    }
143    if (fSide * rh.fSide == 0) {
144        SkASSERT(fSide + rh.fSide != 0); // hitting this assert means coincidence was undetected
145        return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide);
146    }
147    // at this point, the initial tangent line is nearly coincident
148    // see if edges curl away from each other
149    if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) {
150        return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide);
151    }
152    if (fUnsortable || rh.fUnsortable) {
153        // even with no solution, return a stable sort
154        return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh);
155    }
156    SkPath::Verb verb = fSegment->verb();
157    SkPath::Verb rVerb = rh.fSegment->verb();
158    if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x))
159            || (rVerb == SkPath::kLine_Verb
160            && approximately_zero(ry) && approximately_zero(rx))) {
161        // See general unsortable comment below. This case can happen when
162        // one line has a non-zero change in t but no change in x and y.
163        fUnsortable = true;
164        return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh);
165    }
166    if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) {
167        fUnsortable = true;
168        return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh);
169    }
170    SkASSERT(verb >= SkPath::kQuad_Verb);
171    SkASSERT(rVerb >= SkPath::kQuad_Verb);
172    // FIXME: until I can think of something better, project a ray from the
173    // end of the shorter tangent to midway between the end points
174    // through both curves and use the resulting angle to sort
175    // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
176    double len = fTangent1.normalSquared();
177    double rlen = rh.fTangent1.normalSquared();
178    SkDLine ray;
179    SkIntersections i, ri;
180    int roots, rroots;
181    bool flip = false;
182    bool useThis;
183    bool leftLessThanRight = fSide > 0;
184    do {
185        useThis = (len < rlen) ^ flip;
186        const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart;
187        SkPath::Verb partVerb = useThis ? verb : rVerb;
188        ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
189            part[2] : part[1];
190        ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]);
191        SkASSERT(ray[0] != ray[1]);
192        roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray);
193        rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray);
194    } while ((roots == 0 || rroots == 0) && (flip ^= true));
195    if (roots == 0 || rroots == 0) {
196        // FIXME: we don't have a solution in this case. The interim solution
197        // is to mark the edges as unsortable, exclude them from this and
198        // future computations, and allow the returned path to be fragmented
199        fUnsortable = true;
200        return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh);
201    }
202    SkASSERT(fSide != 0 && rh.fSide != 0);
203    SkASSERT(fSide * rh.fSide > 0); // both are the same sign
204    SkDPoint lLoc;
205    double best = SK_ScalarInfinity;
206#if DEBUG_SORT
207    SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n",
208            fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY,
209            ray[1].fX, ray[1].fY, "-+"[fSide > 0]);
210#endif
211    for (int index = 0; index < roots; ++index) {
212        SkDPoint loc = i.pt(index);
213        SkDVector dxy = loc - ray[0];
214        double dist = dxy.lengthSquared();
215#if DEBUG_SORT
216        SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n",
217                best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY);
218#endif
219        if (best > dist) {
220            lLoc = loc;
221            best = dist;
222        }
223    }
224    flip = false;
225    SkDPoint rLoc;
226    for (int index = 0; index < rroots; ++index) {
227        rLoc = ri.pt(index);
228        SkDVector dxy = rLoc - ray[0];
229        double dist = dxy.lengthSquared();
230#if DEBUG_SORT
231        SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n",
232                best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY);
233#endif
234        if (best > dist) {
235            flip = true;
236            break;
237        }
238    }
239    if (flip) {
240        leftLessThanRight = !leftLessThanRight;
241    }
242    return COMPARE_RESULT("14 leftLessThanRight", leftLessThanRight);
243}
244
245bool SkOpAngle::isHorizontal() const {
246    return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb;
247}
248
249// lengthen cannot cross opposite angle
250bool SkOpAngle::lengthen(const SkOpAngle& opp) {
251    if (fSegment->other(fEnd) == opp.fSegment) {
252        return false;
253    }
254    // FIXME: make this a while loop instead and make it as large as possible?
255    int newEnd = fEnd;
256    if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) {
257        fEnd = newEnd;
258        setSpans();
259        return true;
260    }
261    return false;
262}
263
264void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
265    fSegment = segment;
266    fStart = start;
267    fEnd = end;
268    setSpans();
269}
270
271void SkOpAngle::setSpans() {
272    fUnorderable = false;
273    if (fSegment->verb() == SkPath::kLine_Verb) {
274        fUnsortable = false;
275    } else {
276        // if start-1 exists and is tiny, then start pt may have moved
277        int smaller = SkMin32(fStart, fEnd);
278        int tinyCheck = smaller;
279        while (tinyCheck > 0 && fSegment->isTiny(tinyCheck - 1)) {
280            --tinyCheck;
281        }
282        if ((fUnsortable = smaller > 0 && tinyCheck == 0)) {
283            return;
284        }
285        int larger = SkMax32(fStart, fEnd);
286        tinyCheck = larger;
287        int max = fSegment->count() - 1;
288        while (tinyCheck < max && fSegment->isTiny(tinyCheck + 1)) {
289            ++tinyCheck;
290        }
291        if ((fUnsortable = larger < max && tinyCheck == max)) {
292            return;
293        }
294    }
295    fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart);
296    // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try
297    // rounding the curve part to float precision here
298    // fCurvePart.round(fSegment->verb());
299    switch (fSegment->verb()) {
300    case SkPath::kLine_Verb: {
301        // OPTIMIZATION: for pure line compares, we never need fTangent1.c
302        fTangent1.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart));
303        fSide = 0;
304        } break;
305    case SkPath::kQuad_Verb: {
306        SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart);
307        fTangent1.quadEndPoints(quad);
308        fSide = -fTangent1.pointDistance(fCurvePart[2]);  // not normalized -- compare sign only
309        if (fComputed && dx() > 0 && approximately_zero(dy())) {
310            SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
311            int last = fSegment->count() - 1;
312            fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
313            SkLineParameters origTan;
314            origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve));
315            if ((fUnorderable = origTan.dx() <= 0
316                    || (dy() != origTan.dy() && dy() * origTan.dy() <= 0))) { // signs match?
317                return;
318            }
319        }
320        } break;
321    case SkPath::kCubic_Verb: {
322        fTangent1.cubicEndPoints(fCurvePart);
323        double testTs[4];
324        // OPTIMIZATION: keep inflections precomputed with cubic segment?
325        const SkPoint* pts = fSegment->pts();
326        int testCount = SkDCubic::FindInflections(pts, testTs);
327        double startT = fSegment->t(fStart);
328        double endT = fSegment->t(fEnd);
329        double limitT = endT;
330        int index;
331        for (index = 0; index < testCount; ++index) {
332            if (!between(startT, testTs[index], limitT)) {
333                testTs[index] = -1;
334            }
335        }
336        testTs[testCount++] = startT;
337        testTs[testCount++] = endT;
338        SkTQSort<double>(testTs, &testTs[testCount - 1]);
339        double bestSide = 0;
340        int testCases = (testCount << 1) - 1;
341        index = 0;
342        while (testTs[index] < 0) {
343            ++index;
344        }
345        index <<= 1;
346        for (; index < testCases; ++index) {
347            int testIndex = index >> 1;
348            double testT = testTs[testIndex];
349            if (index & 1) {
350                testT = (testT + testTs[testIndex + 1]) / 2;
351            }
352            // OPTIMIZE: could avoid call for t == startT, endT
353            SkDPoint pt = dcubic_xy_at_t(pts, testT);
354            double testSide = fTangent1.pointDistance(pt);
355            if (fabs(bestSide) < fabs(testSide)) {
356                bestSide = testSide;
357            }
358        }
359        fSide = -bestSide;  // compare sign only
360        if (fComputed && dx() > 0 && approximately_zero(dy())) {
361            SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
362            int last = fSegment->count() - 1;
363            fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
364            SkLineParameters origTan;
365            origTan.cubicEndPoints(origCurve);
366            if ((fUnorderable = origTan.dx() <= 0)) {
367                fUnsortable = fSegment->isTiny(this);
368                return;
369            }
370            // if one is < 0 and the other is >= 0
371            if ((fUnorderable = (dy() < 0) ^ (origTan.dy() < 0))) {
372                fUnsortable = fSegment->isTiny(this);
373                return;
374            }
375            SkDCubicPair split = origCurve.chopAt(startT);
376            SkLineParameters splitTan;
377            splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first());
378            if ((fUnorderable = splitTan.dx() <= 0)) {
379                fUnsortable = fSegment->isTiny(this);
380                return;
381            }
382            // if one is < 0 and the other is >= 0
383            if ((fUnorderable = (dy() < 0) ^ (splitTan.dy() < 0))) {
384                fUnsortable = fSegment->isTiny(this);
385                return;
386            }
387        }
388        } break;
389    default:
390        SkASSERT(0);
391    }
392    if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) {
393        return;
394    }
395    SkASSERT(fStart != fEnd);
396    int step = fStart < fEnd ? 1 : -1;  // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
397    for (int index = fStart; index != fEnd; index += step) {
398#if 1
399        const SkOpSpan& thisSpan = fSegment->span(index);
400        const SkOpSpan& nextSpan = fSegment->span(index + step);
401        if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) {
402            continue;
403        }
404        fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
405#if DEBUG_UNSORTABLE
406        if (fUnsortable) {
407            SkPoint iPt = fSegment->xyAtT(index);
408            SkPoint ePt = fSegment->xyAtT(index + step);
409            SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
410                    index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
411        }
412#endif
413        return;
414#else
415        if ((*fSpans)[index].fUnsortableStart) {
416            fUnsortable = true;
417            return;
418        }
419#endif
420    }
421#if 1
422#if DEBUG_UNSORTABLE
423    SkPoint iPt = fSegment->xyAtT(fStart);
424    SkPoint ePt = fSegment->xyAtT(fEnd);
425    SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
426        fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
427#endif
428    fUnsortable = true;
429#endif
430}
431