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 return result;
52 }
53
conic_eval_numerator(const double src[],SkScalar w,double t)54 static double conic_eval_numerator(const double src[], SkScalar w, double t) {
55 SkASSERT(src);
56 SkASSERT(t >= 0 && t <= 1);
57 double src2w = src[2] * w;
58 double C = src[0];
59 double A = src[4] - 2 * src2w + C;
60 double B = 2 * (src2w - C);
61 return (A * t + B) * t + C;
62 }
63
64
conic_eval_denominator(SkScalar w,double t)65 static double conic_eval_denominator(SkScalar w, double t) {
66 double B = 2 * (w - 1);
67 double C = 1;
68 double A = -B;
69 return (A * t + B) * t + C;
70 }
71
hullIntersects(const SkDCubic & cubic,bool * isLinear) const72 bool SkDConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
73 return cubic.hullIntersects(*this, isLinear);
74 }
75
ptAtT(double t) const76 SkDPoint SkDConic::ptAtT(double t) const {
77 double denominator = conic_eval_denominator(fWeight, t);
78 SkDPoint result = {
79 conic_eval_numerator(&fPts[0].fX, fWeight, t) / denominator,
80 conic_eval_numerator(&fPts[0].fY, fWeight, t) / denominator
81 };
82 return result;
83 }
84
85 /* see quad subdivide for rationale */
subDivide(double t1,double t2) const86 SkDConic SkDConic::subDivide(double t1, double t2) const {
87 double ax = conic_eval_numerator(&fPts[0].fX, fWeight, t1);
88 double ay = conic_eval_numerator(&fPts[0].fY, fWeight, t1);
89 double az = conic_eval_denominator(fWeight, t1);
90 double midT = (t1 + t2) / 2;
91 double dx = conic_eval_numerator(&fPts[0].fX, fWeight, midT);
92 double dy = conic_eval_numerator(&fPts[0].fY, fWeight, midT);
93 double dz = conic_eval_denominator(fWeight, midT);
94 double cx = conic_eval_numerator(&fPts[0].fX, fWeight, t2);
95 double cy = conic_eval_numerator(&fPts[0].fY, fWeight, t2);
96 double cz = conic_eval_denominator(fWeight, t2);
97 double bx = 2 * dx - (ax + cx) / 2;
98 double by = 2 * dy - (ay + cy) / 2;
99 double bz = 2 * dz - (az + cz) / 2;
100 double dt = t2 - t1;
101 double dt_1 = 1 - dt;
102 SkScalar w = SkDoubleToScalar((1 + dt * (fWeight - 1))
103 / sqrt(dt * dt + 2 * dt * dt_1 * fWeight + dt_1 * dt_1));
104 SkDConic dst = {{{{ax / az, ay / az}, {bx / bz, by / bz}, {cx / cz, cy / cz}}}, w };
105 return dst;
106 }
107
subDivide(const SkDPoint & a,const SkDPoint & c,double t1,double t2,SkScalar * weight) const108 SkDPoint SkDConic::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2,
109 SkScalar* weight) const {
110 SkDConic chopped = this->subDivide(t1, t2);
111 *weight = chopped.fWeight;
112 return chopped[1];
113 }
114