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