blob: 82f3a7b0ccfe0be6eaa2d2bbd6869e4358a070cc [file] [log] [blame]
 /* * Copyright 2015 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #include "SkIntersections.h" #include "SkLineParameters.h" #include "SkPathOpsConic.h" #include "SkPathOpsCubic.h" #include "SkPathOpsQuad.h" // cribbed from the float version in SkGeometry.cpp static void conic_deriv_coeff(const double src[], SkScalar w, double coeff) { const double P20 = src - src; const double P10 = src - src; const double wP10 = w * P10; coeff = w * P20 - P20; coeff = P20 - 2 * wP10; coeff = wP10; } static double conic_eval_tan(const double coord[], SkScalar w, double t) { double coeff; conic_deriv_coeff(coord, w, coeff); return t * (t * coeff + coeff) + coeff; } int SkDConic::FindExtrema(const double src[], SkScalar w, double t) { double coeff; conic_deriv_coeff(src, w, coeff); double tValues; int roots = SkDQuad::RootsValidT(coeff, coeff, coeff, tValues); // In extreme cases, the number of roots returned can be 2. Pathops // will fail later on, so there's no advantage to plumbing in an error // return here. // SkASSERT(0 == roots || 1 == roots); if (1 == roots) { t = tValues; return 1; } return 0; } SkDVector SkDConic::dxdyAtT(double t) const { SkDVector result = { conic_eval_tan(&fPts.fX, fWeight, t), conic_eval_tan(&fPts.fY, fWeight, t) }; if (result.fX == 0 && result.fY == 0) { if (zero_or_one(t)) { result = fPts - fPts; } else { // incomplete SkDebugf("!k"); } } return result; } static double conic_eval_numerator(const double src[], SkScalar w, double t) { SkASSERT(src); SkASSERT(t >= 0 && t <= 1); double src2w = src * w; double C = src; double A = src - 2 * src2w + C; double B = 2 * (src2w - C); return (A * t + B) * t + C; } static double conic_eval_denominator(SkScalar w, double t) { double B = 2 * (w - 1); double C = 1; double A = -B; return (A * t + B) * t + C; } bool SkDConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const { return cubic.hullIntersects(*this, isLinear); } SkDPoint SkDConic::ptAtT(double t) const { if (t == 0) { return fPts; } if (t == 1) { return fPts; } double denominator = conic_eval_denominator(fWeight, t); SkDPoint result = { conic_eval_numerator(&fPts.fX, fWeight, t) / denominator, conic_eval_numerator(&fPts.fY, fWeight, t) / denominator }; return result; } /* see quad subdivide for point rationale */ /* w rationale : the mid point between t1 and t2 could be determined from the computed a/b/c values if the computed w was known. Since we know the mid point at (t1+t2)/2, we'll assume that it is the same as the point on the new curve t==(0+1)/2. d / dz == conic_poly(dst, unknownW, .5) / conic_weight(unknownW, .5); conic_poly(dst, unknownW, .5) = a / 4 + (b * unknownW) / 2 + c / 4 = (a + c) / 4 + (bx * unknownW) / 2 conic_weight(unknownW, .5) = unknownW / 2 + 1 / 2 d / dz == ((a + c) / 2 + b * unknownW) / (unknownW + 1) d / dz * (unknownW + 1) == (a + c) / 2 + b * unknownW unknownW = ((a + c) / 2 - d / dz) / (d / dz - b) Thus, w is the ratio of the distance from the mid of end points to the on-curve point, and the distance of the on-curve point to the control point. */ SkDConic SkDConic::subDivide(double t1, double t2) const { double ax, ay, az; if (t1 == 0) { ax = fPts.fX; ay = fPts.fY; az = 1; } else if (t1 != 1) { ax = conic_eval_numerator(&fPts.fX, fWeight, t1); ay = conic_eval_numerator(&fPts.fY, fWeight, t1); az = conic_eval_denominator(fWeight, t1); } else { ax = fPts.fX; ay = fPts.fY; az = 1; } double midT = (t1 + t2) / 2; double dx = conic_eval_numerator(&fPts.fX, fWeight, midT); double dy = conic_eval_numerator(&fPts.fY, fWeight, midT); double dz = conic_eval_denominator(fWeight, midT); double cx, cy, cz; if (t2 == 1) { cx = fPts.fX; cy = fPts.fY; cz = 1; } else if (t2 != 0) { cx = conic_eval_numerator(&fPts.fX, fWeight, t2); cy = conic_eval_numerator(&fPts.fY, fWeight, t2); cz = conic_eval_denominator(fWeight, t2); } else { cx = fPts.fX; cy = fPts.fY; cz = 1; } double bx = 2 * dx - (ax + cx) / 2; double by = 2 * dy - (ay + cy) / 2; double bz = 2 * dz - (az + cz) / 2; SkDConic dst = {{{{ax / az, ay / az}, {bx / bz, by / bz}, {cx / cz, cy / cz}} SkDEBUGPARAMS(fPts.fDebugGlobalState) }, SkDoubleToScalar(bz / sqrt(az * cz)) }; return dst; } SkDPoint SkDConic::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2, SkScalar* weight) const { SkDConic chopped = this->subDivide(t1, t2); *weight = chopped.fWeight; return chopped; }