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/SkPathOpsConic.h"
8
9 #include "include/core/SkTypes.h"
10 #include "include/private/base/SkFloatingPoint.h"
11 #include "src/pathops/SkIntersections.h"
12 #include "src/pathops/SkPathOpsCubic.h"
13 #include "src/pathops/SkPathOpsQuad.h"
14 #include "src/pathops/SkPathOpsRect.h"
15 #include "src/pathops/SkPathOpsTypes.h"
16
17 #include <cmath>
18
19 struct SkDLine;
20
21 // cribbed from the float version in SkGeometry.cpp
conic_deriv_coeff(const double src[],SkScalar w,double coeff[3])22 static void conic_deriv_coeff(const double src[],
23 SkScalar w,
24 double coeff[3]) {
25 const double P20 = src[4] - src[0];
26 const double P10 = src[2] - src[0];
27 const double wP10 = w * P10;
28 coeff[0] = w * P20 - P20;
29 coeff[1] = P20 - 2 * wP10;
30 coeff[2] = wP10;
31 }
32
conic_eval_tan(const double coord[],SkScalar w,double t)33 static double conic_eval_tan(const double coord[], SkScalar w, double t) {
34 double coeff[3];
35 conic_deriv_coeff(coord, w, coeff);
36 return t * (t * coeff[0] + coeff[1]) + coeff[2];
37 }
38
FindExtrema(const double src[],SkScalar w,double t[1])39 int SkDConic::FindExtrema(const double src[], SkScalar w, double t[1]) {
40 double coeff[3];
41 conic_deriv_coeff(src, w, coeff);
42
43 double tValues[2];
44 int roots = SkDQuad::RootsValidT(coeff[0], coeff[1], coeff[2], tValues);
45 // In extreme cases, the number of roots returned can be 2. Pathops
46 // will fail later on, so there's no advantage to plumbing in an error
47 // return here.
48 // SkASSERT(0 == roots || 1 == roots);
49
50 if (1 == roots) {
51 t[0] = tValues[0];
52 return 1;
53 }
54 return 0;
55 }
56
dxdyAtT(double t) const57 SkDVector SkDConic::dxdyAtT(double t) const {
58 SkDVector result = {
59 conic_eval_tan(&fPts[0].fX, fWeight, t),
60 conic_eval_tan(&fPts[0].fY, fWeight, t)
61 };
62 if (result.fX == 0 && result.fY == 0) {
63 if (zero_or_one(t)) {
64 result = fPts[2] - fPts[0];
65 } else {
66 // incomplete
67 SkDebugf("!k");
68 }
69 }
70 return result;
71 }
72
conic_eval_numerator(const double src[],SkScalar w,double t)73 static double conic_eval_numerator(const double src[], SkScalar w, double t) {
74 SkASSERT(src);
75 SkASSERT(t >= 0 && t <= 1);
76 double src2w = src[2] * w;
77 double C = src[0];
78 double A = src[4] - 2 * src2w + C;
79 double B = 2 * (src2w - C);
80 return (A * t + B) * t + C;
81 }
82
83
conic_eval_denominator(SkScalar w,double t)84 static double conic_eval_denominator(SkScalar w, double t) {
85 double B = 2 * (w - 1);
86 double C = 1;
87 double A = -B;
88 return (A * t + B) * t + C;
89 }
90
hullIntersects(const SkDCubic & cubic,bool * isLinear) const91 bool SkDConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
92 return cubic.hullIntersects(*this, isLinear);
93 }
94
ptAtT(double t) const95 SkDPoint SkDConic::ptAtT(double t) const {
96 if (t == 0) {
97 return fPts[0];
98 }
99 if (t == 1) {
100 return fPts[2];
101 }
102 double denominator = conic_eval_denominator(fWeight, t);
103 SkDPoint result = {
104 sk_ieee_double_divide(conic_eval_numerator(&fPts[0].fX, fWeight, t), denominator),
105 sk_ieee_double_divide(conic_eval_numerator(&fPts[0].fY, fWeight, t), denominator)
106 };
107 return result;
108 }
109
110 /* see quad subdivide for point rationale */
111 /* w rationale : the mid point between t1 and t2 could be determined from the computed a/b/c
112 values if the computed w was known. Since we know the mid point at (t1+t2)/2, we'll assume
113 that it is the same as the point on the new curve t==(0+1)/2.
114
115 d / dz == conic_poly(dst, unknownW, .5) / conic_weight(unknownW, .5);
116
117 conic_poly(dst, unknownW, .5)
118 = a / 4 + (b * unknownW) / 2 + c / 4
119 = (a + c) / 4 + (bx * unknownW) / 2
120
121 conic_weight(unknownW, .5)
122 = unknownW / 2 + 1 / 2
123
124 d / dz == ((a + c) / 2 + b * unknownW) / (unknownW + 1)
125 d / dz * (unknownW + 1) == (a + c) / 2 + b * unknownW
126 unknownW = ((a + c) / 2 - d / dz) / (d / dz - b)
127
128 Thus, w is the ratio of the distance from the mid of end points to the on-curve point, and the
129 distance of the on-curve point to the control point.
130 */
subDivide(double t1,double t2) const131 SkDConic SkDConic::subDivide(double t1, double t2) const {
132 double ax, ay, az;
133 if (t1 == 0) {
134 ax = fPts[0].fX;
135 ay = fPts[0].fY;
136 az = 1;
137 } else if (t1 != 1) {
138 ax = conic_eval_numerator(&fPts[0].fX, fWeight, t1);
139 ay = conic_eval_numerator(&fPts[0].fY, fWeight, t1);
140 az = conic_eval_denominator(fWeight, t1);
141 } else {
142 ax = fPts[2].fX;
143 ay = fPts[2].fY;
144 az = 1;
145 }
146 double midT = (t1 + t2) / 2;
147 double dx = conic_eval_numerator(&fPts[0].fX, fWeight, midT);
148 double dy = conic_eval_numerator(&fPts[0].fY, fWeight, midT);
149 double dz = conic_eval_denominator(fWeight, midT);
150 double cx, cy, cz;
151 if (t2 == 1) {
152 cx = fPts[2].fX;
153 cy = fPts[2].fY;
154 cz = 1;
155 } else if (t2 != 0) {
156 cx = conic_eval_numerator(&fPts[0].fX, fWeight, t2);
157 cy = conic_eval_numerator(&fPts[0].fY, fWeight, t2);
158 cz = conic_eval_denominator(fWeight, t2);
159 } else {
160 cx = fPts[0].fX;
161 cy = fPts[0].fY;
162 cz = 1;
163 }
164 double bx = 2 * dx - (ax + cx) / 2;
165 double by = 2 * dy - (ay + cy) / 2;
166 double bz = 2 * dz - (az + cz) / 2;
167 if (!bz) {
168 bz = 1; // if bz is 0, weight is 0, control point has no effect: any value will do
169 }
170 SkDConic dst = {{{{ax / az, ay / az}, {bx / bz, by / bz}, {cx / cz, cy / cz}}
171 SkDEBUGPARAMS(fPts.fDebugGlobalState) },
172 SkDoubleToScalar(bz / sqrt(az * cz)) };
173 return dst;
174 }
175
subDivide(const SkDPoint & a,const SkDPoint & c,double t1,double t2,SkScalar * weight) const176 SkDPoint SkDConic::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2,
177 SkScalar* weight) const {
178 SkDConic chopped = this->subDivide(t1, t2);
179 *weight = chopped.fWeight;
180 return chopped[1];
181 }
182
intersectRay(SkIntersections * i,const SkDLine & line) const183 int SkTConic::intersectRay(SkIntersections* i, const SkDLine& line) const {
184 return i->intersectRay(fConic, line);
185 }
186
hullIntersects(const SkDQuad & quad,bool * isLinear) const187 bool SkTConic::hullIntersects(const SkDQuad& quad, bool* isLinear) const {
188 return quad.hullIntersects(fConic, isLinear);
189 }
190
hullIntersects(const SkDCubic & cubic,bool * isLinear) const191 bool SkTConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
192 return cubic.hullIntersects(fConic, isLinear);
193 }
194
setBounds(SkDRect * rect) const195 void SkTConic::setBounds(SkDRect* rect) const {
196 rect->setBounds(fConic);
197 }
198