• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 "src/pathops/SkPathOpsBounds.h"
8 #include "src/pathops/SkPathOpsCurve.h"
9 #include "src/pathops/SkPathOpsRect.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
nearPoint(SkPath::Verb verb,const SkDPoint & xy,const SkDPoint & opp) const13 double 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 = std::min(minX, fCubic.fPts[index].fX);
19         maxX = std::max(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 = std::min(minY, fCubic.fPts[index].fY);
28         maxY = std::max(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 = std::max(std::max(maxX, maxY), -std::min(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 
offset(SkPath::Verb verb,const SkDVector & off)55 void 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 
setConicBounds(const SkPoint curve[3],SkScalar curveWeight,double tStart,double tEnd,SkPathOpsBounds * bounds)62 void 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->setLTRB(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
69                     SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
70 }
71 
setCubicBounds(const SkPoint curve[4],SkScalar,double tStart,double tEnd,SkPathOpsBounds * bounds)72 void 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->setLTRB(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
79                     SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
80 }
81 
setQuadBounds(const SkPoint curve[3],SkScalar,double tStart,double tEnd,SkPathOpsBounds * bounds)82 void 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->setLTRB(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
89                     SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
90 }
91 
setCurveHullSweep(SkPath::Verb verb)92 void 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 = std::max(maxVal, std::max(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     }
143 setIsCurve:
144     fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0;
145 }
146