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 return result; 52 } 53 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 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 72 bool SkDConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const { 73 return cubic.hullIntersects(*this, isLinear); 74 } 75 76 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 */ 86 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 108 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