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