SkGeometry.cpp File Reference

#include "src/core/SkGeometry.h"
#include "include/core/SkMatrix.h"
#include "include/core/SkPoint3.h"
#include "include/core/SkRect.h"
#include "include/core/SkScalar.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkTPin.h"
#include "include/private/base/SkTo.h"
#include "src/base/SkBezierCurves.h"
#include "src/base/SkCubics.h"
#include "src/base/SkUtils.h"
#include "src/base/SkVx.h"
#include "src/core/SkPointPriv.h"
#include <algorithm>
#include <array>
#include <cmath>
#include <cstddef>
#include <cstdint>

Go to the source code of this file.

Macros
#define	AS_QUAD_ERROR_SETUP
#define	kMaxConicToQuadPOW2   5

Functions
int	SkFindUnitQuadRoots (SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2])
void	SkEvalQuadAt (const SkPoint src[3], SkScalar t, SkPoint *pt, SkVector *tangent)
SkPoint	SkEvalQuadAt (const SkPoint src[3], SkScalar t)
SkVector	SkEvalQuadTangentAt (const SkPoint src[3], SkScalar t)
static float2	interp (const float2 &v0, const float2 &v1, const float2 &t)
void	SkChopQuadAt (const SkPoint src[3], SkPoint dst[5], SkScalar t)
void	SkChopQuadAtHalf (const SkPoint src[3], SkPoint dst[5])
float	SkMeasureAngleBetweenVectors (SkVector a, SkVector b)
SkVector	SkFindBisector (SkVector a, SkVector b)
float	SkFindQuadMidTangent (const SkPoint src[3])
int	SkFindQuadExtrema (SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1])
static void	flatten_double_quad_extrema (SkScalar coords[14])
int	SkChopQuadAtYExtrema (const SkPoint src[3], SkPoint dst[5])
int	SkChopQuadAtXExtrema (const SkPoint src[3], SkPoint dst[5])
SkScalar	SkFindQuadMaxCurvature (const SkPoint src[3])
int	SkChopQuadAtMaxCurvature (const SkPoint src[3], SkPoint dst[5])
void	SkConvertQuadToCubic (const SkPoint src[3], SkPoint dst[4])
static SkVector	eval_cubic_derivative (const SkPoint src[4], SkScalar t)
static SkVector	eval_cubic_2ndDerivative (const SkPoint src[4], SkScalar t)
void	SkEvalCubicAt (const SkPoint src[4], SkScalar t, SkPoint *loc, SkVector *tangent, SkVector *curvature)
int	SkFindCubicExtrema (SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar tValues[2])
template<int N, typename T >
static skvx::Vec< N, T >	unchecked_mix (const skvx::Vec< N, T > &a, const skvx::Vec< N, T > &b, const skvx::Vec< N, T > &t)
void	SkChopCubicAt (const SkPoint src[4], SkPoint dst[7], SkScalar t)
void	SkChopCubicAt (const SkPoint src[4], SkPoint dst[10], float t0, float t1)
void	SkChopCubicAt (const SkPoint src[4], SkPoint dst[], const SkScalar tValues[], int tCount)
void	SkChopCubicAtHalf (const SkPoint src[4], SkPoint dst[7])
float	SkMeasureNonInflectCubicRotation (const SkPoint pts[4])
static skvx::float4	fma (const skvx::float4 &f, float m, const skvx::float4 &a)
static float	solve_quadratic_equation_for_midtangent (float a, float b, float c, float discr)
static float	solve_quadratic_equation_for_midtangent (float a, float b, float c)
float	SkFindCubicMidTangent (const SkPoint src[4])
static void	flatten_double_cubic_extrema (SkScalar coords[14])
int	SkChopCubicAtYExtrema (const SkPoint src[4], SkPoint dst[10])
int	SkChopCubicAtXExtrema (const SkPoint src[4], SkPoint dst[10])
int	SkFindCubicInflections (const SkPoint src[4], SkScalar tValues[2])
int	SkChopCubicAtInflections (const SkPoint src[4], SkPoint dst[10])
static double	calc_dot_cross_cubic (const SkPoint &p0, const SkPoint &p1, const SkPoint &p2)
static double	previous_inverse_pow2 (double n)
static void	write_cubic_inflection_roots (double t0, double s0, double t1, double s1, double *t, double *s)
SkCubicType	SkClassifyCubic (const SkPoint P[4], double t[2], double s[2], double d[4])
template<typename T >
void	bubble_sort (T array[], int count)
static int	collaps_duplicates (SkScalar array[], int count)
static SkScalar	SkScalarCubeRoot (SkScalar x)
static int	solve_cubic_poly (const SkScalar coeff[4], SkScalar tValues[3])
static void	formulate_F1DotF2 (const SkScalar src[], SkScalar coeff[4])
int	SkFindCubicMaxCurvature (const SkPoint src[4], SkScalar tValues[3])
int	SkChopCubicAtMaxCurvature (const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3])
static SkScalar	calc_cubic_precision (const SkPoint src[4])
static bool	on_same_side (const SkPoint src[4], int testIndex, int lineIndex)
SkScalar	SkFindCubicCusp (const SkPoint src[4])
static bool	close_enough_to_zero (double x)
static bool	first_axis_intersection (const double coefficients[8], bool yDirection, double axisIntercept, double *solution)
bool	SkChopMonoCubicAtY (const SkPoint src[4], SkScalar y, SkPoint dst[7])
bool	SkChopMonoCubicAtX (const SkPoint src[4], SkScalar x, SkPoint dst[7])
static void	conic_deriv_coeff (const SkScalar src[], SkScalar w, SkScalar coeff[3])
static bool	conic_find_extrema (const SkScalar src[], SkScalar w, SkScalar *t)
static void	p3d_interp (const SkScalar src[7], SkScalar dst[7], SkScalar t)
static void	ratquad_mapTo3D (const SkPoint src[3], SkScalar w, SkPoint3 dst[3])
static SkPoint	project_down (const SkPoint3 &src)
static SkScalar	subdivide_w_value (SkScalar w)
static bool	between (SkScalar a, SkScalar b, SkScalar c)
static SkPoint *	subdivide (const SkConic &src, SkPoint pts[], int level)

Macro Definition Documentation

AS_QUAD_ERROR_SETUP

#define AS_QUAD_ERROR_SETUP

Value:

    SkScalar a = fW - 1;                                            \
    SkScalar k = a / (4 * (2 + a));                                 \
    SkScalar x = k * (fPts[0].fX - 2 * fPts[1].fX + fPts[2].fX);    \
    SkScalar y = k * (fPts[0].fY - 2 * fPts[1].fY + fPts[2].fY);

Definition at line 1469 of file SkGeometry.cpp.

kMaxConicToQuadPOW2

#define kMaxConicToQuadPOW2   5

Definition at line 1486 of file SkGeometry.cpp.

Function Documentation

between()

static bool between ( SkScalar  a, SkScalar  b, SkScalar  c  )

static

Definition at line 1525 of file SkGeometry.cpp.

                                                        {
    return (a - b) * (c - b) <= 0;
}

bubble_sort()

template<typename T >

void bubble_sort	(	T	array[],
		int	count
	)

Definition at line 881 of file SkGeometry.cpp.

                                                             {
    for (int i = count - 1; i > 0; --i)
        for (int j = i; j > 0; --j)
            if (array[j] < array[j-1])
            {
                T   tmp(array[j]);
                array[j] = array[j-1];
                array[j-1] = tmp;
            }
}

calc_cubic_precision()

static SkScalar calc_cubic_precision ( const SkPoint  src[4] )

static

Definition at line 1091 of file SkGeometry.cpp.

                                                           {
    return (SkPointPriv::DistanceToSqd(src[1], src[0]) + SkPointPriv::DistanceToSqd(src[2], src[1])
            + SkPointPriv::DistanceToSqd(src[3], src[2])) * 1e-8f;
}

calc_dot_cross_cubic()

static double calc_dot_cross_cubic ( const SkPoint &  p0, const SkPoint &  p1, const SkPoint &  p2  )

static

Definition at line 771 of file SkGeometry.cpp.

                                                                                            {
    const double xComp = (double) p0.fX * ((double) p1.fY - (double) p2.fY);
    const double yComp = (double) p0.fY * ((double) p2.fX - (double) p1.fX);
    const double wComp = (double) p1.fX * (double) p2.fY - (double) p1.fY * (double) p2.fX;
    return (xComp + yComp + wComp);
}

close_enough_to_zero()

static bool close_enough_to_zero ( double  x )

static

Definition at line 1152 of file SkGeometry.cpp.

                                           {
    return std::fabs(x) < 0.00001;
}

collaps_duplicates()

static int collaps_duplicates ( SkScalar  array[], int  count  )

static

Given an array and count, remove all pair-wise duplicates from the array, keeping the existing sorting, and return the new count

Definition at line 896 of file SkGeometry.cpp.

                                                           {
    for (int n = count; n > 1; --n) {
        if (array[0] == array[1]) {
            for (int i = 1; i < n; ++i) {
                array[i - 1] = array[i];
            }
            count -= 1;
        } else {
            array += 1;
        }
    }
    return count;
}

conic_deriv_coeff()

static void conic_deriv_coeff ( const SkScalar  src[], SkScalar  w, SkScalar  coeff[3]  )

static

Definition at line 1251 of file SkGeometry.cpp.

                                                 {
    const SkScalar P20 = src[4] - src[0];
    const SkScalar P10 = src[2] - src[0];
    const SkScalar wP10 = w * P10;
    coeff[0] = w * P20 - P20;
    coeff[1] = P20 - 2 * wP10;
    coeff[2] = wP10;
}

conic_find_extrema()

static bool conic_find_extrema ( const SkScalar  src[], SkScalar  w, SkScalar *  t  )

static

Definition at line 1262 of file SkGeometry.cpp.

                                                                              {
    SkScalar coeff[3];
    conic_deriv_coeff(src, w, coeff);
 
    SkScalar tValues[2];
    int roots = SkFindUnitQuadRoots(coeff[0], coeff[1], coeff[2], tValues);
    SkASSERT(0 == roots || 1 == roots);
 
    if (1 == roots) {
        *t = tValues[0];
        return true;
    }
    return false;
}

eval_cubic_2ndDerivative()

static SkVector eval_cubic_2ndDerivative ( const SkPoint  src[4], SkScalar  t  )

static

Definition at line 407 of file SkGeometry.cpp.

                                                                           {
    float2 P0 = from_point(src[0]);
    float2 P1 = from_point(src[1]);
    float2 P2 = from_point(src[2]);
    float2 P3 = from_point(src[3]);
    float2 A = P3 + 3 * (P1 - P2) - P0;
    float2 B = P2 - times_2(P1) + P0;
 
    return to_vector(A * t + B);
}

eval_cubic_derivative()

static SkVector eval_cubic_derivative ( const SkPoint  src[4], SkScalar  t  )

static

Definition at line 394 of file SkGeometry.cpp.

                                                                        {
    SkQuadCoeff coeff;
    float2 P0 = from_point(src[0]);
    float2 P1 = from_point(src[1]);
    float2 P2 = from_point(src[2]);
    float2 P3 = from_point(src[3]);
 
    coeff.fA = P3 + 3 * (P1 - P2) - P0;
    coeff.fB = times_2(P2 - times_2(P1) + P0);
    coeff.fC = P1 - P0;
    return to_vector(coeff.eval(t));
}

first_axis_intersection()

static bool first_axis_intersection ( const double  coefficients[8], bool  yDirection, double  axisIntercept, double *  solution  )

static

Definition at line 1156 of file SkGeometry.cpp.

                                                                            {
    auto [A, B, C, D] = SkBezierCubic::ConvertToPolynomial(coefficients, yDirection);
    D -= axisIntercept;
    double roots[3] = {0, 0, 0};
    int count = SkCubics::RootsValidT(A, B, C, D, roots);
    if (count == 0) {
        return false;
    }
    // Verify that at least one of the roots is accurate.
    for (int i = 0; i < count; i++) {
        if (close_enough_to_zero(SkCubics::EvalAt(A, B, C, D, roots[i]))) {
            *solution = roots[i];
            return true;
        }
    }
    // None of the roots returned by our normal cubic solver were correct enough
    // (e.g. https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=55732)
    // So we need to fallback to a more accurate solution.
    count = SkCubics::BinarySearchRootsValidT(A, B, C, D, roots);
    if (count == 0) {
        return false;
    }
    for (int i = 0; i < count; i++) {
        if (close_enough_to_zero(SkCubics::EvalAt(A, B, C, D, roots[i]))) {
            *solution = roots[i];
            return true;
        }
    }
    return false;
}

flatten_double_cubic_extrema()

static void flatten_double_cubic_extrema ( SkScalar  coords[14] )

static

Definition at line 686 of file SkGeometry.cpp.

                                                              {
    coords[4] = coords[8] = coords[6];
}

flatten_double_quad_extrema()

static void flatten_double_quad_extrema ( SkScalar  coords[14] )

inlinestatic

Definition at line 272 of file SkGeometry.cpp.

                                                                    {
    coords[2] = coords[6] = coords[4];
}

fma()

static skvx::float4 fma ( const skvx::float4 &  f, float  m, const skvx::float4 &  a  )

static

Definition at line 597 of file SkGeometry.cpp.

                                                                         {
    return skvx::fma(f, skvx::float4(m), a);
}

formulate_F1DotF2()

static void formulate_F1DotF2 ( const SkScalar  src[], SkScalar  coeff[4]  )

static

Definition at line 1021 of file SkGeometry.cpp.

                                                                       {
    SkScalar    a = src[2] - src[0];
    SkScalar    b = src[4] - 2 * src[2] + src[0];
    SkScalar    c = src[6] + 3 * (src[2] - src[4]) - src[0];
 
    coeff[0] = c * c;
    coeff[1] = 3 * b * c;
    coeff[2] = 2 * b * b + c * a;
    coeff[3] = a * b;
}

interp()

static float2 interp ( const float2 &  v0, const float2 &  v1, const float2 &  t  )

inlinestatic

Definition at line 169 of file SkGeometry.cpp.

                                             {
    return v0 + (v1 - v0) * t;
}

on_same_side()

static bool on_same_side ( const SkPoint  src[4], int  testIndex, int  lineIndex  )

static

Definition at line 1098 of file SkGeometry.cpp.

                                                                             {
    SkPoint origin = src[lineIndex];
    SkVector line = src[lineIndex + 1] - origin;
    SkScalar crosses[2];
    for (int index = 0; index < 2; ++index) {
        SkVector testLine = src[testIndex + index] - origin;
        crosses[index] = line.cross(testLine);
    }
    return crosses[0] * crosses[1] >= 0;
}

p3d_interp()

static void p3d_interp ( const SkScalar  src[7], SkScalar  dst[7], SkScalar  t  )

static

Definition at line 1278 of file SkGeometry.cpp.

                                                                           {
    SkScalar ab = SkScalarInterp(src[0], src[3], t);
    SkScalar bc = SkScalarInterp(src[3], src[6], t);
    dst[0] = ab;
    dst[3] = SkScalarInterp(ab, bc, t);
    dst[6] = bc;
}

previous_inverse_pow2()

static double previous_inverse_pow2 ( double  n )

inlinestatic

Definition at line 782 of file SkGeometry.cpp.

                                                     {
    uint64_t bits;
    memcpy(&bits, &n, sizeof(double));
    bits = ((1023llu*2 << 52) + ((1llu << 52) - 1)) - bits; // exp=-exp
    bits &= (0x7ffllu) << 52; // mantissa=1.0, sign=0
    memcpy(&n, &bits, sizeof(double));
    return n;
}

project_down()

static SkPoint project_down ( const SkPoint3 &  src )

static

Definition at line 1292 of file SkGeometry.cpp.

                                                 {
    return {src.fX / src.fZ, src.fY / src.fZ};
}

ratquad_mapTo3D()

static void ratquad_mapTo3D ( const SkPoint  src[3], SkScalar  w, SkPoint3  dst[3]  )

static

Definition at line 1286 of file SkGeometry.cpp.

                                                                               {
    dst[0].set(src[0].fX * 1, src[0].fY * 1, 1);
    dst[1].set(src[1].fX * w, src[1].fY * w, w);
    dst[2].set(src[2].fX * 1, src[2].fY * 1, 1);
}

SkChopCubicAt() [1/3]

void SkChopCubicAt	(	const SkPoint	src[4],
		SkPoint	dst[10],
		float	t0,
		float	t1
	)

Given a src cubic bezier, chop it at the specified t0 and t1 values, where 0 <= t0 <= t1 <= 1, and return the three new cubics in dst: dst[0..3], dst[3..6], and dst[6..9]

Definition at line 504 of file SkGeometry.cpp.

                                                                              {
    SkASSERT(0 <= t0 && t0 <= t1 && t1 <= 1);
 
    if (t1 == 1) {
        SkChopCubicAt(src, dst, t0);
        dst[7] = dst[8] = dst[9] = src[3];
        return;
    }
 
    // Perform both chops in parallel using 4-lane SIMD.
    float4 p00, p11, p22, p33, T;
    p00.lo = p00.hi = sk_bit_cast<float2>(src[0]);
    p11.lo = p11.hi = sk_bit_cast<float2>(src[1]);
    p22.lo = p22.hi = sk_bit_cast<float2>(src[2]);
    p33.lo = p33.hi = sk_bit_cast<float2>(src[3]);
    T.lo = t0;
    T.hi = t1;
 
    float4 ab = unchecked_mix(p00, p11, T);
    float4 bc = unchecked_mix(p11, p22, T);
    float4 cd = unchecked_mix(p22, p33, T);
    float4 abc = unchecked_mix(ab, bc, T);
    float4 bcd = unchecked_mix(bc, cd, T);
    float4 abcd = unchecked_mix(abc, bcd, T);
    float4 middle = unchecked_mix(abc, bcd, skvx::shuffle<2,3,0,1>(T));
 
    dst[0] = sk_bit_cast<SkPoint>(p00.lo);
    dst[1] = sk_bit_cast<SkPoint>(ab.lo);
    dst[2] = sk_bit_cast<SkPoint>(abc.lo);
    dst[3] = sk_bit_cast<SkPoint>(abcd.lo);
    middle.store(dst + 4);
    dst[6] = sk_bit_cast<SkPoint>(abcd.hi);
    dst[7] = sk_bit_cast<SkPoint>(bcd.hi);
    dst[8] = sk_bit_cast<SkPoint>(cd.hi);
    dst[9] = sk_bit_cast<SkPoint>(p33.hi);
}

SkChopCubicAt() [2/3]

void SkChopCubicAt	(	const SkPoint	src[4],
		SkPoint	dst[7],
		SkScalar	t
	)

Given a src cubic bezier, chop it at the specified t value, where 0 <= t <= 1, and return the two new cubics in dst: dst[0..3] and dst[3..6]

Definition at line 473 of file SkGeometry.cpp.

                                                                     {
    SkASSERT(0 <= t && t <= 1);
 
    if (t == 1) {
        memcpy(dst, src, sizeof(SkPoint) * 4);
        dst[4] = dst[5] = dst[6] = src[3];
        return;
    }
 
    float2 p0 = sk_bit_cast<float2>(src[0]);
    float2 p1 = sk_bit_cast<float2>(src[1]);
    float2 p2 = sk_bit_cast<float2>(src[2]);
    float2 p3 = sk_bit_cast<float2>(src[3]);
    float2 T = t;
 
    float2 ab = unchecked_mix(p0, p1, T);
    float2 bc = unchecked_mix(p1, p2, T);
    float2 cd = unchecked_mix(p2, p3, T);
    float2 abc = unchecked_mix(ab, bc, T);
    float2 bcd = unchecked_mix(bc, cd, T);
    float2 abcd = unchecked_mix(abc, bcd, T);
 
    dst[0] = sk_bit_cast<SkPoint>(p0);
    dst[1] = sk_bit_cast<SkPoint>(ab);
    dst[2] = sk_bit_cast<SkPoint>(abc);
    dst[3] = sk_bit_cast<SkPoint>(abcd);
    dst[4] = sk_bit_cast<SkPoint>(bcd);
    dst[5] = sk_bit_cast<SkPoint>(cd);
    dst[6] = sk_bit_cast<SkPoint>(p3);
}

SkChopCubicAt() [3/3]

void SkChopCubicAt	(	const SkPoint	src[4],
		SkPoint	dst[],
		const SkScalar	t[],
		int	t_count
	)

Given a src cubic bezier, chop it at the specified t values, where 0 <= t0 <= t1 <= ... <= 1, and return the new cubics in dst: dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)]

Definition at line 541 of file SkGeometry.cpp.

                                                         {
    SkASSERT(std::all_of(tValues, tValues + tCount, [](SkScalar t) { return t >= 0 && t <= 1; }));
    SkASSERT(std::is_sorted(tValues, tValues + tCount));
 
    if (dst) {
        if (tCount == 0) { // nothing to chop
            memcpy(dst, src, 4*sizeof(SkPoint));
        } else {
            int i = 0;
            for (; i < tCount - 1; i += 2) {
                // Do two chops at once.
                float2 tt = float2::Load(tValues + i);
                if (i != 0) {
                    float lastT = tValues[i - 1];
                    tt = skvx::pin((tt - lastT) / (1 - lastT), float2(0), float2(1));
                }
                SkChopCubicAt(src, dst, tt[0], tt[1]);
                src = dst = dst + 6;
            }
            if (i < tCount) {
                // Chop the final cubic if there was an odd number of chops.
                SkASSERT(i + 1 == tCount);
                float t = tValues[i];
                if (i != 0) {
                    float lastT = tValues[i - 1];
                    t = SkTPin(sk_ieee_float_divide(t - lastT, 1 - lastT), 0.f, 1.f);
                }
                SkChopCubicAt(src, dst, t);
            }
        }
    }
}

SkChopCubicAtHalf()

void SkChopCubicAtHalf	(	const SkPoint	src[4],
		SkPoint	dst[7]
	)

Given a src cubic bezier, chop it at the specified t == 1/2, The new cubics are returned in dst[0..3] and dst[3..6]

Definition at line 575 of file SkGeometry.cpp.

                                                             {
    SkChopCubicAt(src, dst, 0.5f);
}

SkChopCubicAtInflections()

int SkChopCubicAtInflections	(	const SkPoint	src[4],
		SkPoint	dst[10]
	)

Return 1 for no chop, 2 for having chopped the cubic at a single inflection point, 3 for having chopped at 2 inflection points. dst will hold the resulting 1, 2, or 3 cubics.

Definition at line 755 of file SkGeometry.cpp.

                                                                    {
    SkScalar    tValues[2];
    int         count = SkFindCubicInflections(src, tValues);
 
    if (dst) {
        if (count == 0) {
            memcpy(dst, src, 4 * sizeof(SkPoint));
        } else {
            SkChopCubicAt(src, dst, tValues, count);
        }
    }
    return count + 1;
}

SkChopCubicAtMaxCurvature()

int SkChopCubicAtMaxCurvature	(	const SkPoint	src[4],
		SkPoint	dst[13],
		SkScalar	tValues[3]
	)

Definition at line 1060 of file SkGeometry.cpp.

                                                   {
    SkScalar    t_storage[3];
 
    if (tValues == nullptr) {
        tValues = t_storage;
    }
 
    SkScalar roots[3];
    int rootCount = SkFindCubicMaxCurvature(src, roots);
 
    // Throw out values not inside 0..1.
    int count = 0;
    for (int i = 0; i < rootCount; ++i) {
        if (0 < roots[i] && roots[i] < 1) {
            tValues[count++] = roots[i];
        }
    }
 
    if (dst) {
        if (count == 0) {
            memcpy(dst, src, 4 * sizeof(SkPoint));
        } else {
            SkChopCubicAt(src, dst, tValues, count);
        }
    }
    return count + 1;
}

SkChopCubicAtXExtrema()

int SkChopCubicAtXExtrema	(	const SkPoint	src[4],
		SkPoint	dst[10]
	)

Definition at line 714 of file SkGeometry.cpp.

                                                                 {
    SkScalar    tValues[2];
    int         roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX,
                                           src[3].fX, tValues);
 
    SkChopCubicAt(src, dst, tValues, roots);
    if (dst && roots > 0) {
        // we do some cleanup to ensure our Y extrema are flat
        flatten_double_cubic_extrema(&dst[0].fX);
        if (roots == 2) {
            flatten_double_cubic_extrema(&dst[3].fX);
        }
    }
    return roots;
}

SkChopCubicAtYExtrema()

int SkChopCubicAtYExtrema	(	const SkPoint	src[4],
		SkPoint	dst[10]
	)

Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that the resulting beziers are monotonic in Y. This is called by the scan converter. Depending on what is returned, dst[] is treated as follows: 0 dst[0..3] is the original cubic 1 dst[0..3] and dst[3..6] are the two new cubics 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics If dst == null, it is ignored and only the count is returned.

Definition at line 698 of file SkGeometry.cpp.

                                                                 {
    SkScalar    tValues[2];
    int         roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY,
                                           src[3].fY, tValues);
 
    SkChopCubicAt(src, dst, tValues, roots);
    if (dst && roots > 0) {
        // we do some cleanup to ensure our Y extrema are flat
        flatten_double_cubic_extrema(&dst[0].fY);
        if (roots == 2) {
            flatten_double_cubic_extrema(&dst[3].fY);
        }
    }
    return roots;
}

SkChopMonoCubicAtX()

bool SkChopMonoCubicAtX	(	const SkPoint	src[4],
		SkScalar	x,
		SkPoint	dst[7]
	)

Given a monotonically increasing or decreasing cubic bezier src, chop it where the X value is the specified value. The returned cubics will be in dst, sharing the middle point. That is, the first cubic is dst[0..3] and the second dst[3..6].

If the cubic provided is not monotone, it will be chopped at the first time the curve has the specified X value.

If the cubic never reaches the specified value, the function returns false.

Definition at line 1204 of file SkGeometry.cpp.

                                                                          {
    double coefficients[8] = {src[0].fX, src[0].fY, src[1].fX, src[1].fY,
                                  src[2].fX, src[2].fY, src[3].fX, src[3].fY};
    double solution = 0;
    if (first_axis_intersection(coefficients, false, x, &solution)) {
        double cubicPair[14];
        SkBezierCubic::Subdivide(coefficients, solution, cubicPair);
        for (int i = 0; i < 7; i ++) {
            dst[i].fX = sk_double_to_float(cubicPair[i*2]);
            dst[i].fY = sk_double_to_float(cubicPair[i*2 + 1]);
        }
        return true;
    }
    return false;
}

SkChopMonoCubicAtY()

bool SkChopMonoCubicAtY	(	const SkPoint	src[4],
		SkScalar	y,
		SkPoint	dst[7]
	)

Given a monotonically increasing or decreasing cubic bezier src, chop it where the Y value is the specified value. The returned cubics will be in dst, sharing the middle point. That is, the first cubic is dst[0..3] and the second dst[3..6].

If the cubic provided is not monotone, it will be chopped at the first time the curve has the specified Y value.

If the cubic never reaches the specified value, the function returns false.

Definition at line 1188 of file SkGeometry.cpp.

                                                                          {
    double coefficients[8] = {src[0].fX, src[0].fY, src[1].fX, src[1].fY,
                              src[2].fX, src[2].fY, src[3].fX, src[3].fY};
    double solution = 0;
    if (first_axis_intersection(coefficients, true, y, &solution)) {
        double cubicPair[14];
        SkBezierCubic::Subdivide(coefficients, solution, cubicPair);
        for (int i = 0; i < 7; i ++) {
            dst[i].fX = sk_double_to_float(cubicPair[i*2]);
            dst[i].fY = sk_double_to_float(cubicPair[i*2 + 1]);
        }
        return true;
    }
    return false;
}

SkChopQuadAt()

void SkChopQuadAt	(	const SkPoint	src[3],
		SkPoint	dst[5],
		SkScalar	t
	)

Given a src quadratic bezier, chop it at the specified t value, where 0 < t < 1, and return the two new quadratics in dst: dst[0..2] and dst[2..4]

Definition at line 175 of file SkGeometry.cpp.

                                                                    {
    SkASSERT(t > 0 && t < SK_Scalar1);
 
    float2 p0 = from_point(src[0]);
    float2 p1 = from_point(src[1]);
    float2 p2 = from_point(src[2]);
    float2 tt(t);
 
    float2 p01 = interp(p0, p1, tt);
    float2 p12 = interp(p1, p2, tt);
 
    dst[0] = to_point(p0);
    dst[1] = to_point(p01);
    dst[2] = to_point(interp(p01, p12, tt));
    dst[3] = to_point(p12);
    dst[4] = to_point(p2);
}

SkChopQuadAtHalf()

void SkChopQuadAtHalf	(	const SkPoint	src[3],
		SkPoint	dst[5]
	)

Given a src quadratic bezier, chop it at the specified t == 1/2, The new quads are returned in dst[0..2] and dst[2..4]

Definition at line 193 of file SkGeometry.cpp.

                                                            {
    SkChopQuadAt(src, dst, 0.5f);
}

SkChopQuadAtMaxCurvature()

int SkChopQuadAtMaxCurvature	(	const SkPoint	src[3],
		SkPoint	dst[5]
	)

Given 3 points on a quadratic bezier, divide it into 2 quadratics if the point of maximum curvature exists on the quad segment. Depending on what is returned, dst[] is treated as follows 1 dst[0..2] is the original quad 2 dst[0..2] and dst[2..4] are the two new quads If dst == null, it is ignored and only the count is returned.

Definition at line 367 of file SkGeometry.cpp.

                                                                   {
    SkScalar t = SkFindQuadMaxCurvature(src);
    if (t > 0 && t < 1) {
        SkChopQuadAt(src, dst, t);
        return 2;
    } else {
        memcpy(dst, src, 3 * sizeof(SkPoint));
        return 1;
    }
}

SkChopQuadAtXExtrema()

int SkChopQuadAtXExtrema	(	const SkPoint	src[3],
		SkPoint	dst[5]
	)

Definition at line 307 of file SkGeometry.cpp.

                                                               {
    SkASSERT(src);
    SkASSERT(dst);
 
    SkScalar a = src[0].fX;
    SkScalar b = src[1].fX;
    SkScalar c = src[2].fX;
 
    if (is_not_monotonic(a, b, c)) {
        SkScalar tValue;
        if (valid_unit_divide(a - b, a - b - b + c, &tValue)) {
            SkChopQuadAt(src, dst, tValue);
            flatten_double_quad_extrema(&dst[0].fX);
            return 1;
        }
        // if we get here, we need to force dst to be monotonic, even though
        // we couldn't compute a unit_divide value (probably underflow).
        b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c;
    }
    dst[0].set(a, src[0].fY);
    dst[1].set(b, src[1].fY);
    dst[2].set(c, src[2].fY);
    return 0;
}

SkChopQuadAtYExtrema()

int SkChopQuadAtYExtrema	(	const SkPoint	src[3],
		SkPoint	dst[5]
	)

Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that the resulting beziers are monotonic in Y. This is called by the scan converter. Depending on what is returned, dst[] is treated as follows 0 dst[0..2] is the original quad 1 dst[0..2] and dst[2..4] are the two new quads

Definition at line 279 of file SkGeometry.cpp.

                                                               {
    SkASSERT(src);
    SkASSERT(dst);
 
    SkScalar a = src[0].fY;
    SkScalar b = src[1].fY;
    SkScalar c = src[2].fY;
 
    if (is_not_monotonic(a, b, c)) {
        SkScalar    tValue;
        if (valid_unit_divide(a - b, a - b - b + c, &tValue)) {
            SkChopQuadAt(src, dst, tValue);
            flatten_double_quad_extrema(&dst[0].fY);
            return 1;
        }
        // if we get here, we need to force dst to be monotonic, even though
        // we couldn't compute a unit_divide value (probably underflow).
        b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c;
    }
    dst[0].set(src[0].fX, a);
    dst[1].set(src[1].fX, b);
    dst[2].set(src[2].fX, c);
    return 0;
}

SkClassifyCubic()

SkCubicType SkClassifyCubic	(	const SkPoint	p[4],
		double	t[2] = nullptr,
		double	s[2] = nullptr,
		double	d[4] = nullptr
	)

Returns the cubic classification.

t[],s[] are set to the two homogeneous parameter values at which points the lines L & M intersect with K, sorted from smallest to largest and oriented so positive values of the implicit are on the "left" side. For a serpentine curve they are the inflection points. For a loop they are the double point. For a local cusp, they are both equal and denote the cusp point. For a cusp at an infinite parameter value, one will be the local inflection point and the other +inf (t,s = 1,0). If the curve is degenerate (i.e. quadratic or linear) they are both set to a parameter value of +inf (t,s = 1,0).

d[] is filled with the cubic inflection function coefficients. See "Resolution Independent Curve Rendering using Programmable Graphics Hardware", 4.2 Curve Categorization:

If the input points contain infinities or NaN, the return values are undefined.

https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf

Definition at line 809 of file SkGeometry.cpp.

                                                                                       {
    // Find the cubic's inflection function, I = [T^3  -3T^2  3T  -1] dot D. (D0 will always be 0
    // for integral cubics.)
    //
    // See "Resolution Independent Curve Rendering using Programmable Graphics Hardware",
    // 4.2 Curve Categorization:
    //
    // https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
    double A1 = calc_dot_cross_cubic(P[0], P[3], P[2]);
    double A2 = calc_dot_cross_cubic(P[1], P[0], P[3]);
    double A3 = calc_dot_cross_cubic(P[2], P[1], P[0]);
 
    double D3 = 3 * A3;
    double D2 = D3 - A2;
    double D1 = D2 - A2 + A1;
 
    // Shift the exponents in D so the largest magnitude falls somewhere in 1..2. This protects us
    // from overflow down the road while solving for roots and KLM functionals.
    double Dmax = std::max(std::max(fabs(D1), fabs(D2)), fabs(D3));
    double norm = previous_inverse_pow2(Dmax);
    D1 *= norm;
    D2 *= norm;
    D3 *= norm;
 
    if (d) {
        d[3] = D3;
        d[2] = D2;
        d[1] = D1;
        d[0] = 0;
    }
 
    // Now use the inflection function to classify the cubic.
    //
    // See "Resolution Independent Curve Rendering using Programmable Graphics Hardware",
    // 4.4 Integral Cubics:
    //
    // https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
    if (0 != D1) {
        double discr = 3*D2*D2 - 4*D1*D3;
        if (discr > 0) { // Serpentine.
            if (t && s) {
                double q = 3*D2 + copysign(sqrt(3*discr), D2);
                write_cubic_inflection_roots(q, 6*D1, 2*D3, q, t, s);
            }
            return SkCubicType::kSerpentine;
        } else if (discr < 0) { // Loop.
            if (t && s) {
                double q = D2 + copysign(sqrt(-discr), D2);
                write_cubic_inflection_roots(q, 2*D1, 2*(D2*D2 - D3*D1), D1*q, t, s);
            }
            return SkCubicType::kLoop;
        } else { // Cusp.
            if (t && s) {
                write_cubic_inflection_roots(D2, 2*D1, D2, 2*D1, t, s);
            }
            return SkCubicType::kLocalCusp;
        }
    } else {
        if (0 != D2) { // Cusp at T=infinity.
            if (t && s) {
                write_cubic_inflection_roots(D3, 3*D2, 1, 0, t, s); // T1=infinity.
            }
            return SkCubicType::kCuspAtInfinity;
        } else { // Degenerate.
            if (t && s) {
                write_cubic_inflection_roots(1, 0, 1, 0, t, s); // T0=T1=infinity.
            }
            return 0 != D3 ? SkCubicType::kQuadratic : SkCubicType::kLineOrPoint;
        }
    }
}

SkConvertQuadToCubic()

void SkConvertQuadToCubic	(	const SkPoint	src[3],
		SkPoint	dst[4]
	)

Given 3 points on a quadratic bezier, use degree elevation to convert it into the cubic fitting the same curve. The new cubic curve is returned in dst[0..3].

Definition at line 378 of file SkGeometry.cpp.

                                                                {
    float2 scale(SkDoubleToScalar(2.0 / 3.0));
    float2 s0 = from_point(src[0]);
    float2 s1 = from_point(src[1]);
    float2 s2 = from_point(src[2]);
 
    dst[0] = to_point(s0);
    dst[1] = to_point(s0 + (s1 - s0) * scale);
    dst[2] = to_point(s2 + (s1 - s2) * scale);
    dst[3] = to_point(s2);
}

SkEvalCubicAt()

void SkEvalCubicAt	(	const SkPoint	src[4],
		SkScalar	t,
		SkPoint *	locOrNull,
		SkVector *	tangentOrNull,
		SkVector *	curvatureOrNull
	)

Set pt to the point on the src cubic specified by t. t must be 0 <= t <= 1.0

Definition at line 418 of file SkGeometry.cpp.

                                                           {
    SkASSERT(src);
    SkASSERT(t >= 0 && t <= SK_Scalar1);
 
    if (loc) {
        *loc = to_point(SkCubicCoeff(src).eval(t));
    }
    if (tangent) {
        // The derivative equation returns a zero tangent vector when t is 0 or 1, and the
        // adjacent control point is equal to the end point. In this case, use the
        // next control point or the end points to compute the tangent.
        if ((t == 0 && src[0] == src[1]) || (t == 1 && src[2] == src[3])) {
            if (t == 0) {
                *tangent = src[2] - src[0];
            } else {
                *tangent = src[3] - src[1];
            }
            if (!tangent->fX && !tangent->fY) {
                *tangent = src[3] - src[0];
            }
        } else {
            *tangent = eval_cubic_derivative(src, t);
        }
    }
    if (curvature) {
        *curvature = eval_cubic_2ndDerivative(src, t);
    }
}

SkEvalQuadAt() [1/2]

SkPoint SkEvalQuadAt	(	const SkPoint	src[3],
		SkScalar	t
	)

Definition at line 144 of file SkGeometry.cpp.

                                                       {
    return to_point(SkQuadCoeff(src).eval(t));
}

SkEvalQuadAt() [2/2]

void SkEvalQuadAt	(	const SkPoint	src[3],
		SkScalar	t,
		SkPoint *	pt,
		SkVector *	tangent = nullptr
	)

Set pt to the point on the src quadratic specified by t. t must be 0 <= t <= 1.0

Definition at line 132 of file SkGeometry.cpp.

                                                                                    {
    SkASSERT(src);
    SkASSERT(t >= 0 && t <= SK_Scalar1);
 
    if (pt) {
        *pt = SkEvalQuadAt(src, t);
    }
    if (tangent) {
        *tangent = SkEvalQuadTangentAt(src, t);
    }
}

SkEvalQuadTangentAt()

SkVector SkEvalQuadTangentAt	(	const SkPoint	src[3],
		SkScalar	t
	)

Definition at line 148 of file SkGeometry.cpp.

                                                               {
    // The derivative equation is 2(b - a +(a - 2b +c)t). This returns a
    // zero tangent vector when t is 0 or 1, and the control point is equal
    // to the end point. In this case, use the quad end points to compute the tangent.
    if ((t == 0 && src[0] == src[1]) || (t == 1 && src[1] == src[2])) {
        return src[2] - src[0];
    }
    SkASSERT(src);
    SkASSERT(t >= 0 && t <= SK_Scalar1);
 
    float2 P0 = from_point(src[0]);
    float2 P1 = from_point(src[1]);
    float2 P2 = from_point(src[2]);
 
    float2 B = P1 - P0;
    float2 A = P2 - P1 - B;
    float2 T = A * t + B;
 
    return to_vector(T + T);
}

SkFindBisector()

SkVector SkFindBisector	(	SkVector	a,
		SkVector	b
	)

Returns a new, arbitrarily scaled vector that bisects the given vectors. The returned bisector will always point toward the interior of the provided vectors.

Definition at line 204 of file SkGeometry.cpp.

                                                {
    std::array<SkVector, 2> v;
    if (a.dot(b) >= 0) {
        // a,b are within +/-90 degrees apart.
        v = {a, b};
    } else if (a.cross(b) >= 0) {
        // a,b are >90 degrees apart. Find the bisector of their interior normals instead. (Above 90
        // degrees, the original vectors start cancelling each other out which eventually becomes
        // unstable.)
        v[0].set(-a.fY, +a.fX);
        v[1].set(+b.fY, -b.fX);
    } else {
        // a,b are <-90 degrees apart. Find the bisector of their interior normals instead. (Below
        // -90 degrees, the original vectors start cancelling each other out which eventually
        // becomes unstable.)
        v[0].set(+a.fY, -a.fX);
        v[1].set(-b.fY, +b.fX);
    }
    // Return "normalize(v[0]) + normalize(v[1])".
    skvx::float2 x0_x1{v[0].fX, v[1].fX};
    skvx::float2 y0_y1{v[0].fY, v[1].fY};
    auto invLengths = 1.0f / sqrt(x0_x1 * x0_x1 + y0_y1 * y0_y1);
    x0_x1 *= invLengths;
    y0_y1 *= invLengths;
    return SkPoint{x0_x1[0] + x0_x1[1], y0_y1[0] + y0_y1[1]};
}

SkFindCubicCusp()

SkScalar SkFindCubicCusp

(

const SkPoint

src[4]

)

Returns t value of cusp if cubic has one; returns -1 otherwise.

Definition at line 1112 of file SkGeometry.cpp.

                                               {
    // When the adjacent control point matches the end point, it behaves as if
    // the cubic has a cusp: there's a point of max curvature where the derivative
    // goes to zero. Ideally, this would be where t is zero or one, but math
    // error makes not so. It is not uncommon to create cubics this way; skip them.
    if (src[0] == src[1]) {
        return -1;
    }
    if (src[2] == src[3]) {
        return -1;
    }
    // Cubics only have a cusp if the line segments formed by the control and end points cross.
    // Detect crossing if line ends are on opposite sides of plane formed by the other line.
    if (on_same_side(src, 0, 2) || on_same_side(src, 2, 0)) {
        return -1;
    }
    // Cubics may have multiple points of maximum curvature, although at most only
    // one is a cusp.
    SkScalar maxCurvature[3];
    int roots = SkFindCubicMaxCurvature(src, maxCurvature);
    for (int index = 0; index < roots; ++index) {
        SkScalar testT = maxCurvature[index];
        if (0 >= testT || testT >= 1) {  // no need to consider max curvature on the end
            continue;
        }
        // A cusp is at the max curvature, and also has a derivative close to zero.
        // Choose the 'close to zero' meaning by comparing the derivative length
        // with the overall cubic size.
        SkVector dPt = eval_cubic_derivative(src, testT);
        SkScalar dPtMagnitude = SkPointPriv::LengthSqd(dPt);
        SkScalar precision = calc_cubic_precision(src);
        if (dPtMagnitude < precision) {
            // All three max curvature t values may be close to the cusp;
            // return the first one.
            return testT;
        }
    }
    return -1;
}

SkFindCubicExtrema()

int SkFindCubicExtrema	(	SkScalar	a,
		SkScalar	b,
		SkScalar	c,
		SkScalar	d,
		SkScalar	tValues[2]
	)

Cubic'(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 betwee 0 < t < 1

Definition at line 454 of file SkGeometry.cpp.

                                            {
    // we divide A,B,C by 3 to simplify
    SkScalar A = d - a + 3*(b - c);
    SkScalar B = 2*(a - b - b + c);
    SkScalar C = b - a;
 
    return SkFindUnitQuadRoots(A, B, C, tValues);
}

SkFindCubicInflections()

int SkFindCubicInflections	(	const SkPoint	src[4],
		SkScalar	tValues[2]
	)

http://www.faculty.idc.ac.il/arik/quality/appendixA.html

Inflection means that curvature is zero. Curvature is [F' x F''] / [F'^3] So we solve F'x X F''y - F'y X F''y == 0 After some canceling of the cubic term, we get A = b - a B = c - 2b + a C = d - 3c + 3b - a (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0

Definition at line 741 of file SkGeometry.cpp.

                                                                      {
    SkScalar    Ax = src[1].fX - src[0].fX;
    SkScalar    Ay = src[1].fY - src[0].fY;
    SkScalar    Bx = src[2].fX - 2 * src[1].fX + src[0].fX;
    SkScalar    By = src[2].fY - 2 * src[1].fY + src[0].fY;
    SkScalar    Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX;
    SkScalar    Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY;
 
    return SkFindUnitQuadRoots(Bx*Cy - By*Cx,
                               Ax*Cy - Ay*Cx,
                               Ax*By - Ay*Bx,
                               tValues);
}

SkFindCubicMaxCurvature()

int SkFindCubicMaxCurvature	(	const SkPoint	src[4],
		SkScalar	tValues[3]
	)

Definition at line 1043 of file SkGeometry.cpp.

                                                                       {
    SkScalar coeffX[4], coeffY[4];
    int      i;
 
    formulate_F1DotF2(&src[0].fX, coeffX);
    formulate_F1DotF2(&src[0].fY, coeffY);
 
    for (i = 0; i < 4; i++) {
        coeffX[i] += coeffY[i];
    }
 
    int numRoots = solve_cubic_poly(coeffX, tValues);
    // now remove extrema where the curvature is zero (mins)
    // !!!! need a test for this !!!!
    return numRoots;
}

SkFindCubicMidTangent()

float SkFindCubicMidTangent

(

const SkPoint

src[4]

)

Given a src cubic bezier, returns the T value whose tangent angle is halfway between the tangents at p0 and p3.

Definition at line 620 of file SkGeometry.cpp.

                                                  {
    // Tangents point in the direction of increasing T, so tan0 and -tan1 both point toward the
    // midtangent. The bisector of tan0 and -tan1 is orthogonal to the midtangent:
    //
    //     bisector dot midtangent == 0
    //
    SkVector tan0 = (src[0] == src[1]) ? src[2] - src[0] : src[1] - src[0];
    SkVector tan1 = (src[2] == src[3]) ? src[3] - src[1] : src[3] - src[2];
    SkVector bisector = SkFindBisector(tan0, -tan1);
 
    // Find the T value at the midtangent. This is a simple quadratic equation:
    //
    //     midtangent dot bisector == 0, or using a tangent matrix C' in power basis form:
    //
    //                   |C'x  C'y|
    //     |T^2  T  1| * |.    .  | * |bisector.x| == 0
    //                   |.    .  |   |bisector.y|
    //
    // The coeffs for the quadratic equation we need to solve are therefore:  C' * bisector
    static const skvx::float4 kM[4] = {skvx::float4(-1,  2, -1,  0),
                                       skvx::float4( 3, -4,  1,  0),
                                       skvx::float4(-3,  2,  0,  0)};
    auto C_x = fma(kM[0], src[0].fX,
               fma(kM[1], src[1].fX,
               fma(kM[2], src[2].fX, skvx::float4(src[3].fX, 0,0,0))));
    auto C_y = fma(kM[0], src[0].fY,
               fma(kM[1], src[1].fY,
               fma(kM[2], src[2].fY, skvx::float4(src[3].fY, 0,0,0))));
    auto coeffs = C_x * bisector.x() + C_y * bisector.y();
 
    // Now solve the quadratic for T.
    float T = 0;
    float a=coeffs[0], b=coeffs[1], c=coeffs[2];
    float discr = b*b - 4*a*c;
    if (discr > 0) {  // This will only be false if the curve is a line.
        return solve_quadratic_equation_for_midtangent(a, b, c, discr);
    } else {
        // This is a 0- or 360-degree flat line. It doesn't have single points of midtangent.
        // (tangent == midtangent at every point on the curve except the cusp points.)
        // Chop in between both cusps instead, if any. There can be up to two cusps on a flat line,
        // both where the tangent is perpendicular to the starting tangent:
        //
        //     tangent dot tan0 == 0
        //
        coeffs = C_x * tan0.x() + C_y * tan0.y();
        a = coeffs[0];
        b = coeffs[1];
        if (a != 0) {
            // We want the point in between both cusps. The midpoint of:
            //
            //     (-b +/- sqrt(b^2 - 4*a*c)) / (2*a)
            //
            // Is equal to:
            //
            //     -b / (2*a)
            T = -b / (2*a);
        }
        if (!(T > 0 && T < 1)) {  // Use "!(positive_logic)" so T=NaN will take this branch.
            // Either the curve is a flat line with no rotation or FP precision failed us. Chop at
            // .5.
            T = .5;
        }
        return T;
    }
}

SkFindQuadExtrema()

int SkFindQuadExtrema	(	SkScalar	a,
		SkScalar	b,
		SkScalar	c,
		SkScalar	tValue[1]
	)

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

Definition at line 265 of file SkGeometry.cpp.

                                                                              {
    /*  At + B == 0
        t = -B / A
    */
    return valid_unit_divide(a - b, a - b - b + c, tValue);
}

SkFindQuadMaxCurvature()

SkScalar SkFindQuadMaxCurvature

(

const SkPoint

src[3]

)

Given 3 points on a quadratic bezier, if the point of maximum curvature exists on the segment, returns the t value for this point along the curve. Otherwise it will return a value of 0.

Definition at line 344 of file SkGeometry.cpp.

                                                      {
    SkScalar    Ax = src[1].fX - src[0].fX;
    SkScalar    Ay = src[1].fY - src[0].fY;
    SkScalar    Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX;
    SkScalar    By = src[0].fY - src[1].fY - src[1].fY + src[2].fY;
 
    SkScalar numer = -(Ax * Bx + Ay * By);
    SkScalar denom = Bx * Bx + By * By;
    if (denom < 0) {
        numer = -numer;
        denom = -denom;
    }
    if (numer <= 0) {
        return 0;
    }
    if (numer >= denom) {  // Also catches denom=0.
        return 1;
    }
    SkScalar t = numer / denom;
    SkASSERT((0 <= t && t < 1) || SkIsNaN(t));
    return t;
}

SkFindQuadMidTangent()

float SkFindQuadMidTangent

(

const SkPoint

src[3]

)

Given a src quadratic bezier, returns the T value whose tangent angle is halfway between the tangents at p0 and p3.

Definition at line 231 of file SkGeometry.cpp.

                                                 {
    // Tangents point in the direction of increasing T, so tan0 and -tan1 both point toward the
    // midtangent. The bisector of tan0 and -tan1 is orthogonal to the midtangent:
    //
    //     n dot midtangent = 0
    //
    SkVector tan0 = src[1] - src[0];
    SkVector tan1 = src[2] - src[1];
    SkVector bisector = SkFindBisector(tan0, -tan1);
 
    // The midtangent can be found where (F' dot bisector) = 0:
    //
    //   0 = (F'(T) dot bisector) = |2*T 1| * |p0 - 2*p1 + p2| * |bisector.x|
    //                                        |-2*p0 + 2*p1  |   |bisector.y|
    //
    //                     = |2*T 1| * |tan1 - tan0| * |nx|
    //                                 |2*tan0     |   |ny|
    //
    //                     = 2*T * ((tan1 - tan0) dot bisector) + (2*tan0 dot bisector)
    //
    //   T = (tan0 dot bisector) / ((tan0 - tan1) dot bisector)
    float T = sk_ieee_float_divide(tan0.dot(bisector), (tan0 - tan1).dot(bisector));
    if (!(T > 0 && T < 1)) {  // Use "!(positive_logic)" so T=nan will take this branch.
        T = .5;  // The quadratic was a line or near-line. Just chop at .5.
    }
 
    return T;
}

SkFindUnitQuadRoots()

int SkFindUnitQuadRoots	(	SkScalar	A,
		SkScalar	B,
		SkScalar	C,
		SkScalar	roots[2]
	)

From Numerical Recipes in C.

Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) x1 = Q / A x2 = C / Q

Definition at line 95 of file SkGeometry.cpp.

                                                                               {
    SkASSERT(roots);
 
    if (A == 0) {
        return return_check_zero(valid_unit_divide(-C, B, roots));
    }
 
    SkScalar* r = roots;
 
    // use doubles so we don't overflow temporarily trying to compute R
    double dr = (double)B * B - 4 * (double)A * C;
    if (dr < 0) {
        return return_check_zero(0);
    }
    dr = sqrt(dr);
    SkScalar R = SkDoubleToScalar(dr);
    if (!SkIsFinite(R)) {
        return return_check_zero(0);
    }
 
    SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2;
    r += valid_unit_divide(Q, A, r);
    r += valid_unit_divide(C, Q, r);
    if (r - roots == 2) {
        if (roots[0] > roots[1]) {
            using std::swap;
            swap(roots[0], roots[1]);
        } else if (roots[0] == roots[1]) { // nearly-equal?
            r -= 1; // skip the double root
        }
    }
    return return_check_zero((int)(r - roots));
}

SkMeasureAngleBetweenVectors()

float SkMeasureAngleBetweenVectors	(	SkVector	a,
		SkVector	b
	)

Measures the angle between two vectors, in the range [0, pi].

Definition at line 197 of file SkGeometry.cpp.

                                                           {
    float cosTheta = sk_ieee_float_divide(a.dot(b), sqrtf(a.dot(a) * b.dot(b)));
    // Pin cosTheta such that if it is NaN (e.g., if a or b was 0), then we return acos(1) = 0.
    cosTheta = std::max(std::min(1.f, cosTheta), -1.f);
    return acosf(cosTheta);
}

SkMeasureNonInflectCubicRotation()

float SkMeasureNonInflectCubicRotation

(

const

SkPoint[4]

)

Given a cubic curve with no inflection points, this method measures the rotation in radians.

Rotation is perhaps easiest described via a driving analogy: If you drive your car along the curve from p0 to p3, then by the time you arrive at p3, how many radians will your car have rotated? This is not quite the same as the vector inside the tangents at the endpoints, even without inflection, because the curve might rotate around the outside of the tangents (>= 180 degrees) or the inside (<= 180 degrees).

Cubics can have rotations in the range [0, 2*pi].

NOTE: The caller must either call SkChopCubicAtInflections or otherwise prove that the provided cubic has no inflection points prior to calling this method.

Definition at line 579 of file SkGeometry.cpp.

                                                             {
    SkVector a = pts[1] - pts[0];
    SkVector b = pts[2] - pts[1];
    SkVector c = pts[3] - pts[2];
    if (a.isZero()) {
        return SkMeasureAngleBetweenVectors(b, c);
    }
    if (b.isZero()) {
        return SkMeasureAngleBetweenVectors(a, c);
    }
    if (c.isZero()) {
        return SkMeasureAngleBetweenVectors(a, b);
    }
    // Postulate: When no points are colocated and there are no inflection points in T=0..1, the
    // rotation is: 360 degrees, minus the angle [p0,p1,p2], minus the angle [p1,p2,p3].
    return 2*SK_ScalarPI - SkMeasureAngleBetweenVectors(a,-b) - SkMeasureAngleBetweenVectors(b,-c);
}

SkScalarCubeRoot()

static SkScalar SkScalarCubeRoot ( SkScalar  x )

static

Definition at line 950 of file SkGeometry.cpp.

                                             {
    return SkScalarPow(x, 0.3333333f);
}

solve_cubic_poly()

static int solve_cubic_poly ( const SkScalar  coeff[4], SkScalar  tValues[3]  )

static

Definition at line 961 of file SkGeometry.cpp.

                                                                          {
    if (SkScalarNearlyZero(coeff[0])) {  // we're just a quadratic
        return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues);
    }
 
    SkScalar a, b, c, Q, R;
 
    {
        SkASSERT(coeff[0] != 0);
 
        SkScalar inva = SkScalarInvert(coeff[0]);
        a = coeff[1] * inva;
        b = coeff[2] * inva;
        c = coeff[3] * inva;
    }
    Q = (a*a - b*3) / 9;
    R = (2*a*a*a - 9*a*b + 27*c) / 54;
 
    SkScalar Q3 = Q * Q * Q;
    SkScalar R2MinusQ3 = R * R - Q3;
    SkScalar adiv3 = a / 3;
 
    if (R2MinusQ3 < 0) { // we have 3 real roots
        // the divide/root can, due to finite precisions, be slightly outside of -1...1
        SkScalar theta = SkScalarACos(SkTPin(R / SkScalarSqrt(Q3), -1.0f, 1.0f));
        SkScalar neg2RootQ = -2 * SkScalarSqrt(Q);
 
        tValues[0] = SkTPin(neg2RootQ * SkScalarCos(theta/3) - adiv3, 0.0f, 1.0f);
        tValues[1] = SkTPin(neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3, 0.0f, 1.0f);
        tValues[2] = SkTPin(neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3, 0.0f, 1.0f);
        SkDEBUGCODE(test_collaps_duplicates();)
 
        // now sort the roots
        bubble_sort(tValues, 3);
        return collaps_duplicates(tValues, 3);
    } else {              // we have 1 real root
        SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3);
        A = SkScalarCubeRoot(A);
        if (R > 0) {
            A = -A;
        }
        if (A != 0) {
            A += Q / A;
        }
        tValues[0] = SkTPin(A - adiv3, 0.0f, 1.0f);
        return 1;
    }
}

solve_quadratic_equation_for_midtangent() [1/2]

static float solve_quadratic_equation_for_midtangent ( float  a, float  b, float  c  )

static

Definition at line 616 of file SkGeometry.cpp.

                                                                                {
    return solve_quadratic_equation_for_midtangent(a, b, c, b*b - 4*a*c);
}

solve_quadratic_equation_for_midtangent() [2/2]

static float solve_quadratic_equation_for_midtangent ( float  a, float  b, float  c, float  discr  )

static

Definition at line 602 of file SkGeometry.cpp.

                                                                                             {
    // Quadratic formula from Numerical Recipes in C:
    float q = -.5f * (b + copysignf(sqrtf(discr), b));
    // The roots are q/a and c/q. Pick the midtangent closer to T=.5.
    float _5qa = -.5f*q*a;
    float T = fabsf(q*q + _5qa) < fabsf(a*c + _5qa) ? sk_ieee_float_divide(q,a)
                                                    : sk_ieee_float_divide(c,q);
    if (!(T > 0 && T < 1)) {  // Use "!(positive_logic)" so T=NaN will take this branch.
        // Either the curve is a flat line with no rotation or FP precision failed us. Chop at .5.
        T = .5;
    }
    return T;
}

subdivide()

static SkPoint * subdivide ( const SkConic &  src, SkPoint  pts[], int  level  )

static

Definition at line 1529 of file SkGeometry.cpp.

                                                                        {
    SkASSERT(level >= 0);
 
    if (0 == level) {
        memcpy(pts, &src.fPts[1], 2 * sizeof(SkPoint));
        return pts + 2;
    } else {
        SkConic dst[2];
        src.chop(dst);
        const SkScalar startY = src.fPts[0].fY;
        SkScalar endY = src.fPts[2].fY;
        if (between(startY, src.fPts[1].fY, endY)) {
            // If the input is monotonic and the output is not, the scan converter hangs.
            // Ensure that the chopped conics maintain their y-order.
            SkScalar midY = dst[0].fPts[2].fY;
            if (!between(startY, midY, endY)) {
                // If the computed midpoint is outside the ends, move it to the closer one.
                SkScalar closerY = SkTAbs(midY - startY) < SkTAbs(midY - endY) ? startY : endY;
                dst[0].fPts[2].fY = dst[1].fPts[0].fY = closerY;
            }
            if (!between(startY, dst[0].fPts[1].fY, dst[0].fPts[2].fY)) {
                // If the 1st control is not between the start and end, put it at the start.
                // This also reduces the quad to a line.
                dst[0].fPts[1].fY = startY;
            }
            if (!between(dst[1].fPts[0].fY, dst[1].fPts[1].fY, endY)) {
                // If the 2nd control is not between the start and end, put it at the end.
                // This also reduces the quad to a line.
                dst[1].fPts[1].fY = endY;
            }
            // Verify that all five points are in order.
            SkASSERT(between(startY, dst[0].fPts[1].fY, dst[0].fPts[2].fY));
            SkASSERT(between(dst[0].fPts[1].fY, dst[0].fPts[2].fY, dst[1].fPts[1].fY));
            SkASSERT(between(dst[0].fPts[2].fY, dst[1].fPts[1].fY, endY));
        }
        --level;
        pts = subdivide(dst[0], pts, level);
        return subdivide(dst[1], pts, level);
    }
}

subdivide_w_value()

static SkScalar subdivide_w_value ( SkScalar  w )

static

Definition at line 1397 of file SkGeometry.cpp.

                                              {
    return SkScalarSqrt(SK_ScalarHalf + w * SK_ScalarHalf);
}

unchecked_mix()

template<int N, typename T >

static skvx::Vec< N, T > unchecked_mix ( const skvx::Vec< N, T > &  a, const skvx::Vec< N, T > &  b, const skvx::Vec< N, T > &  t  )

inlinestatic

Definition at line 468 of file SkGeometry.cpp.

                                                                  {
    return (b - a)*t + a;
}

write_cubic_inflection_roots()

static void write_cubic_inflection_roots ( double  t0, double  s0, double  t1, double  s1, double *  t, double *  s  )

inlinestatic

Definition at line 791 of file SkGeometry.cpp.

                                                                      {
    t[0] = t0;
    s[0] = s0;
 
    // This copysign/abs business orients the implicit function so positive values are always on the
    // "left" side of the curve.
    t[1] = -copysign(t1, t1 * s1);
    s[1] = -fabs(s1);
 
    // Ensure t[0]/s[0] <= t[1]/s[1] (s[1] is negative from above).
    if (copysign(s[1], s[0]) * t[0] > -fabs(s[0]) * t[1]) {
        using std::swap;
        swap(t[0], t[1]);
        swap(s[0], s[1]);
    }
}