SkPathOpsCubic.cpp | Explore in Territory

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#include "src/pathops/SkPathOpsCubic.h"

#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkTPin.h"
#include "include/private/base/SkTo.h"
#include "src/base/SkTSort.h"
#include "src/core/SkGeometry.h"
#include "src/pathops/SkIntersections.h"
#include "src/pathops/SkLineParameters.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsQuad.h"
#include "src/pathops/SkPathOpsRect.h"
#include "src/pathops/SkPathOpsTypes.h"

#include <algorithm>
#include <cmath>

struct SkDLine;

const int SkDCubic::gPrecisionUnit = …;  // FIXME: test different values in test framework

void SkDCubic::align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const { … }

// give up when changing t no longer moves point
// also, copy point rather than recompute it when it does change
double SkDCubic::binarySearch(double min, double max, double axisIntercept,
        SearchAxis xAxis) const { … }

// get the rough scale of the cubic; used to determine if curvature is extreme
double SkDCubic::calcPrecision() const { … }

/* classic one t subdivision */
static void interp_cubic_coords(const double* src, double* dst, double t) { … }

SkDCubicPair SkDCubic::chopAt(double t) const { … }

// TODO(skbug.com/14063) deduplicate this with SkBezierCubic::ConvertToPolynomial
void SkDCubic::Coefficients(const double* src, double* A, double* B, double* C, double* D) { … }

bool SkDCubic::endsAreExtremaInXOrY() const { … }

// Do a quick reject by rotating all points relative to a line formed by
// a pair of one cubic's points. If the 2nd cubic's points
// are on the line or on the opposite side from the 1st cubic's 'odd man', the
// curves at most intersect at the endpoints.
/* if returning true, check contains true if cubic's hull collapsed, making the cubic linear
   if returning false, check contains true if the the cubic pair have only the end point in common
*/
bool SkDCubic::hullIntersects(const SkDPoint* pts, int ptCount, bool* isLinear) const { … }

bool SkDCubic::hullIntersects(const SkDCubic& c2, bool* isLinear) const { … }

bool SkDCubic::hullIntersects(const SkDQuad& quad, bool* isLinear) const { … }

bool SkDCubic::hullIntersects(const SkDConic& conic, bool* isLinear) const { … }

bool SkDCubic::isLinear(int startIndex, int endIndex) const { … }

// from http://www.cs.sunysb.edu/~qin/courses/geometry/4.pdf
// c(t)  = a(1-t)^3 + 3bt(1-t)^2 + 3c(1-t)t^2 + dt^3
// c'(t) = -3a(1-t)^2 + 3b((1-t)^2 - 2t(1-t)) + 3c(2t(1-t) - t^2) + 3dt^2
//       = 3(b-a)(1-t)^2 + 6(c-b)t(1-t) + 3(d-c)t^2
static double derivative_at_t(const double* src, double t) { … }

int SkDCubic::ComplexBreak(const SkPoint pointsPtr[4], SkScalar* t) { … }

bool SkDCubic::monotonicInX() const { … }

bool SkDCubic::monotonicInY() const { … }

void SkDCubic::otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const { … }

int SkDCubic::searchRoots(double extremeTs[6], int extrema, double axisIntercept,
        SearchAxis xAxis, double* validRoots) const { … }

// cubic roots

static const double PI = …;

// from SkGeometry.cpp (and Numeric Solutions, 5.6)
// // TODO(skbug.com/14063) Deduplicate with SkCubics::RootsValidT
int SkDCubic::RootsValidT(double A, double B, double C, double D, double t[3]) { … }

// TODO(skbug.com/14063) Deduplicate with SkCubics::RootsReal
int SkDCubic::RootsReal(double A, double B, double C, double D, double s[3]) { … }

// OPTIMIZE? compute t^2, t(1-t), and (1-t)^2 and pass them to another version of derivative at t?
SkDVector SkDCubic::dxdyAtT(double t) const { … }

// OPTIMIZE? share code with formulate_F1DotF2
// e.g. https://stackoverflow.com/a/35927917
int SkDCubic::findInflections(double tValues[2]) const { … }

static void formulate_F1DotF2(const double src[], double coeff[4]) { … }

/** SkDCubic'(t) = At^2 + Bt + C, where
    A = 3(-a + 3(b - c) + d)
    B = 6(a - 2b + c)
    C = 3(b - a)
    Solve for t, keeping only those that fit between 0 < t < 1
*/
int SkDCubic::FindExtrema(const double src[], double tValues[2]) { … }

/*  from SkGeometry.cpp
    Looking for F' dot F'' == 0

    A = b - a
    B = c - 2b + a
    C = d - 3c + 3b - a

    F' = 3Ct^2 + 6Bt + 3A
    F'' = 6Ct + 6B

    F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB
*/
int SkDCubic::findMaxCurvature(double tValues[]) const { … }

SkDPoint SkDCubic::ptAtT(double t) const { … }

/*
 Given a cubic c, t1, and t2, find a small cubic segment.

 The new cubic is defined as points A, B, C, and D, where
 s1 = 1 - t1
 s2 = 1 - t2
 A = c[0]*s1*s1*s1 + 3*c[1]*s1*s1*t1 + 3*c[2]*s1*t1*t1 + c[3]*t1*t1*t1
 D = c[0]*s2*s2*s2 + 3*c[1]*s2*s2*t2 + 3*c[2]*s2*t2*t2 + c[3]*t2*t2*t2

 We don't have B or C. So We define two equations to isolate them.
 First, compute two reference T values 1/3 and 2/3 from t1 to t2:

 c(at (2*t1 + t2)/3) == E
 c(at (t1 + 2*t2)/3) == F

 Next, compute where those values must be if we know the values of B and C:

 _12   =  A*2/3 + B*1/3
 12_   =  A*1/3 + B*2/3
 _23   =  B*2/3 + C*1/3
 23_   =  B*1/3 + C*2/3
 _34   =  C*2/3 + D*1/3
 34_   =  C*1/3 + D*2/3
 _123  = (A*2/3 + B*1/3)*2/3 + (B*2/3 + C*1/3)*1/3 = A*4/9 + B*4/9 + C*1/9
 123_  = (A*1/3 + B*2/3)*1/3 + (B*1/3 + C*2/3)*2/3 = A*1/9 + B*4/9 + C*4/9
 _234  = (B*2/3 + C*1/3)*2/3 + (C*2/3 + D*1/3)*1/3 = B*4/9 + C*4/9 + D*1/9
 234_  = (B*1/3 + C*2/3)*1/3 + (C*1/3 + D*2/3)*2/3 = B*1/9 + C*4/9 + D*4/9
 _1234 = (A*4/9 + B*4/9 + C*1/9)*2/3 + (B*4/9 + C*4/9 + D*1/9)*1/3
       =  A*8/27 + B*12/27 + C*6/27 + D*1/27
       =  E
 1234_ = (A*1/9 + B*4/9 + C*4/9)*1/3 + (B*1/9 + C*4/9 + D*4/9)*2/3
       =  A*1/27 + B*6/27 + C*12/27 + D*8/27
       =  F
 E*27  =  A*8    + B*12   + C*6     + D
 F*27  =  A      + B*6    + C*12    + D*8

Group the known values on one side:

 M       = E*27 - A*8 - D     = B*12 + C* 6
 N       = F*27 - A   - D*8   = B* 6 + C*12
 M*2 - N = B*18
 N*2 - M = C*18
 B       = (M*2 - N)/18
 C       = (N*2 - M)/18
 */

static double interp_cubic_coords(const double* src, double t) { … }

SkDCubic SkDCubic::subDivide(double t1, double t2) const { … }

void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d,
                         double t1, double t2, SkDPoint dst[2]) const { … }

bool SkDCubic::toFloatPoints(SkPoint* pts) const { … }

double SkDCubic::top(const SkDCubic& dCurve, double startT, double endT, SkDPoint*topPt) const { … }

int SkTCubic::intersectRay(SkIntersections* i, const SkDLine& line) const { … }

bool SkTCubic::hullIntersects(const SkDQuad& quad, bool* isLinear) const { … }

bool SkTCubic::hullIntersects(const SkDConic& conic, bool* isLinear) const  { … }

void SkTCubic::setBounds(SkDRect* rect) const { … }
chromium/third_party/skia/src/pathops/SkPathOpsCubic.cpp
