chromium/third_party/skia/src/pathops/SkPathOpsQuad.cpp

/*
 * 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/SkPathOpsQuad.h"

#include "src/pathops/SkIntersections.h"
#include "src/pathops/SkLineParameters.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsLine.h"
#include "src/pathops/SkPathOpsRect.h"
#include "src/pathops/SkPathOpsTypes.h"

#include <algorithm>
#include <cmath>

// from blackpawn.com/texts/pointinpoly
static bool pointInTriangle(const SkDPoint fPts[3], const SkDPoint& test) { … }

static bool matchesEnd(const SkDPoint fPts[3], const SkDPoint& test) { … }

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

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

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

/* bit twiddling for finding the off curve index (x&~m is the pair in [0,1,2] excluding oddMan)
oddMan    opp   x=oddMan^opp  x=x-oddMan  m=x>>2   x&~m
    0       1         1            1         0       1
            2         2            2         0       2
    1       1         0           -1        -1       0
            2         3            2         0       2
    2       1         3            1         0       1
            2         0           -2        -1       0
*/
void SkDQuad::otherPts(int oddMan, const SkDPoint* endPt[2]) const { … }

int SkDQuad::AddValidTs(double s[], int realRoots, double* t) { … }

// note: caller expects multiple results to be sorted smaller first
// note: http://en.wikipedia.org/wiki/Loss_of_significance has an interesting
//  analysis of the quadratic equation, suggesting why the following looks at
//  the sign of B -- and further suggesting that the greatest loss of precision
//  is in b squared less two a c
int SkDQuad::RootsValidT(double A, double B, double C, double t[2]) { … }

static int handle_zero(const double B, const double C, double s[2]) { … }

/*
Numeric Solutions (5.6) suggests to solve the quadratic by computing
       Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C))
and using the roots
      t1 = Q / A
      t2 = C / Q
*/
// this does not discard real roots <= 0 or >= 1
// TODO(skbug.com/14063) Deduplicate with SkQuads::RootsReal
int SkDQuad::RootsReal(const double A, const double B, const double C, double s[2]) { … }

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

SkDVector SkDQuad::dxdyAtT(double t) const { … }

// OPTIMIZE: assert if caller passes in t == 0 / t == 1 ?
SkDPoint SkDQuad::ptAtT(double t) const { … }

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

bool SkDQuad::monotonicInX() const { … }

bool SkDQuad::monotonicInY() const { … }

/*
Given a quadratic q, t1, and t2, find a small quadratic segment.

The new quadratic is defined by A, B, and C, where
 A = c[0]*(1 - t1)*(1 - t1) + 2*c[1]*t1*(1 - t1) + c[2]*t1*t1
 C = c[3]*(1 - t1)*(1 - t1) + 2*c[2]*t1*(1 - t1) + c[1]*t1*t1

To find B, compute the point halfway between t1 and t2:

q(at (t1 + t2)/2) == D

Next, compute where D must be if we know the value of B:

_12 = A/2 + B/2
12_ = B/2 + C/2
123 = A/4 + B/2 + C/4
    = D

Group the known values on one side:

B   = D*2 - A/2 - C/2
*/

// OPTIMIZE? : special case  t1 = 1 && t2 = 0
SkDQuad SkDQuad::subDivide(double t1, double t2) const { … }

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

SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const { … }

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

SkDQuadPair SkDQuad::chopAt(double t) const
{ … }

static int valid_unit_divide(double numer, double denom, double* ratio)
{ … }

/** Quad'(t) = At + B, where
    A = 2(a - 2b + c)
    B = 2(b - a)
    Solve for t, only if it fits between 0 < t < 1
*/
int SkDQuad::FindExtrema(const double src[], double tValue[1]) { … }

/* Parameterization form, given A*t*t + 2*B*t*(1-t) + C*(1-t)*(1-t)
 *
 * a = A - 2*B +   C
 * b =     2*B - 2*C
 * c =             C
 */
void SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) { … }

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

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

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

void SkTQuad::setBounds(SkDRect* rect) const { … }