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 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 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 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 46 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 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 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 80 bool SkDConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const { 81 return cubic.hullIntersects(*this, isLinear); 82 } 83 84 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 */ 120 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 161 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
