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#include "SkPathOpsBounds.h"
8#include "SkPathOpsRect.h"
9#include "SkPathOpsCurve.h"
10
11 // this cheats and assumes that the perpendicular to the point is the closest ray to the curve
12 // this case (where the line and the curve are nearly coincident) may be the only case that counts
13double SkDCurve::nearPoint(SkPath::Verb verb, const SkDPoint& xy, const SkDPoint& opp) const {
14    int count = SkPathOpsVerbToPoints(verb);
15    double minX = fCubic.fPts[0].fX;
16    double maxX = minX;
17    for (int index = 1; index <= count; ++index) {
18        minX = SkTMin(minX, fCubic.fPts[index].fX);
19        maxX = SkTMax(maxX, fCubic.fPts[index].fX);
20    }
21    if (!AlmostBetweenUlps(minX, xy.fX, maxX)) {
22        return -1;
23    }
24    double minY = fCubic.fPts[0].fY;
25    double maxY = minY;
26    for (int index = 1; index <= count; ++index) {
27        minY = SkTMin(minY, fCubic.fPts[index].fY);
28        maxY = SkTMax(maxY, fCubic.fPts[index].fY);
29    }
30    if (!AlmostBetweenUlps(minY, xy.fY, maxY)) {
31        return -1;
32    }
33    SkIntersections i;
34    SkDLine perp = {{ xy, { xy.fX + opp.fY - xy.fY, xy.fY + xy.fX - opp.fX }}};
35    (*CurveDIntersectRay[verb])(*this, perp, &i);
36    int minIndex = -1;
37    double minDist = FLT_MAX;
38    for (int index = 0; index < i.used(); ++index) {
39        double dist = xy.distance(i.pt(index));
40        if (minDist > dist) {
41            minDist = dist;
42            minIndex = index;
43        }
44    }
45    if (minIndex < 0) {
46        return -1;
47    }
48    double largest = SkTMax(SkTMax(maxX, maxY), -SkTMin(minX, minY));
49    if (!AlmostEqualUlps_Pin(largest, largest + minDist)) { // is distance within ULPS tolerance?
50        return -1;
51    }
52    return SkPinT(i[0][minIndex]);
53}
54
55void SkDCurve::offset(SkPath::Verb verb, const SkDVector& off) {
56    int count = SkPathOpsVerbToPoints(verb);
57    for (int index = 0; index <= count; ++index) {
58        fCubic.fPts[index] += off;
59    }
60}
61
62void SkDCurve::setConicBounds(const SkPoint curve[3], SkScalar curveWeight,
63        double tStart, double tEnd, SkPathOpsBounds* bounds) {
64    SkDConic dCurve;
65    dCurve.set(curve, curveWeight);
66    SkDRect dRect;
67    dRect.setBounds(dCurve, fConic, tStart, tEnd);
68    bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
69            SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
70}
71
72void SkDCurve::setCubicBounds(const SkPoint curve[4], SkScalar ,
73        double tStart, double tEnd, SkPathOpsBounds* bounds) {
74    SkDCubic dCurve;
75    dCurve.set(curve);
76    SkDRect dRect;
77    dRect.setBounds(dCurve, fCubic, tStart, tEnd);
78    bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
79            SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
80}
81
82void SkDCurve::setQuadBounds(const SkPoint curve[3], SkScalar ,
83        double tStart, double tEnd, SkPathOpsBounds* bounds) {
84    SkDQuad dCurve;
85    dCurve.set(curve);
86    SkDRect dRect;
87    dRect.setBounds(dCurve, fQuad, tStart, tEnd);
88    bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
89            SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
90}
91
92void SkDCurveSweep::setCurveHullSweep(SkPath::Verb verb) {
93    fOrdered = true;
94    fSweep[0] = fCurve[1] - fCurve[0];
95    if (SkPath::kLine_Verb == verb) {
96        fSweep[1] = fSweep[0];
97        fIsCurve = false;
98        return;
99    }
100    fSweep[1] = fCurve[2] - fCurve[0];
101    // OPTIMIZE: I do the following float check a lot -- probably need a
102    // central place for this val-is-small-compared-to-curve check
103    double maxVal = 0;
104    for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) {
105        maxVal = SkTMax(maxVal, SkTMax(SkTAbs(fCurve[index].fX),
106                SkTAbs(fCurve[index].fY)));
107    }
108    {
109        if (SkPath::kCubic_Verb != verb) {
110            if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal)
111                    && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) {
112                fSweep[0] = fSweep[1];
113            }
114            goto setIsCurve;
115        }
116        SkDVector thirdSweep = fCurve[3] - fCurve[0];
117        if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
118            fSweep[0] = fSweep[1];
119            fSweep[1] = thirdSweep;
120            if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal)
121                    && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) {
122                fSweep[0] = fSweep[1];
123                fCurve[1] = fCurve[3];
124            }
125            goto setIsCurve;
126        }
127        double s1x3 = fSweep[0].crossCheck(thirdSweep);
128        double s3x2 = thirdSweep.crossCheck(fSweep[1]);
129        if (s1x3 * s3x2 >= 0) {  // if third vector is on or between first two vectors
130            goto setIsCurve;
131        }
132        double s2x1 = fSweep[1].crossCheck(fSweep[0]);
133        // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble
134        // probably such wide sweeps should be artificially subdivided earlier so that never happens
135        SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0);
136        if (s3x2 * s2x1 < 0) {
137            SkASSERT(s2x1 * s1x3 > 0);
138            fSweep[0] = fSweep[1];
139            fOrdered = false;
140        }
141        fSweep[1] = thirdSweep;
142    }
143setIsCurve:
144    fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0;
145}
146