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