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 #include "SkPathOpsRect.h" 13 14 // cribbed from the float version in SkGeometry.cpp 15 static 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 26 static 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 32 int 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 50 SkDVector 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 66 static 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 77 static 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 84 bool SkDConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const { 85 return cubic.hullIntersects(*this, isLinear); 86 } 87 88 SkDPoint 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 */ 124 SkDConic 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 169 SkDPoint 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 176 int SkTConic::intersectRay(SkIntersections* i, const SkDLine& line) const { 177 return i->intersectRay(fConic, line); 178 } 179 180 bool SkTConic::hullIntersects(const SkDQuad& quad, bool* isLinear) const { 181 return quad.hullIntersects(fConic, isLinear); 182 } 183 184 bool SkTConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const { 185 return cubic.hullIntersects(fConic, isLinear); 186 } 187 188 void SkTConic::setBounds(SkDRect* rect) const { 189 rect->setBounds(fConic); 190 } 191