SkPath.cpp File Reference

#include "include/core/SkPath.h"
#include "include/core/SkArc.h"
#include "include/core/SkPathBuilder.h"
#include "include/core/SkRRect.h"
#include "include/core/SkStream.h"
#include "include/core/SkString.h"
#include "include/private/SkPathRef.h"
#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkMalloc.h"
#include "include/private/base/SkSpan_impl.h"
#include "include/private/base/SkTArray.h"
#include "include/private/base/SkTDArray.h"
#include "include/private/base/SkTo.h"
#include "src/base/SkFloatBits.h"
#include "src/base/SkTLazy.h"
#include "src/base/SkVx.h"
#include "src/core/SkCubicClipper.h"
#include "src/core/SkEdgeClipper.h"
#include "src/core/SkGeometry.h"
#include "src/core/SkMatrixPriv.h"
#include "src/core/SkPathEnums.h"
#include "src/core/SkPathMakers.h"
#include "src/core/SkPathPriv.h"
#include "src/core/SkPointPriv.h"
#include "src/core/SkStringUtils.h"
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iterator>
#include <limits.h>
#include <utility>

Go to the source code of this file.

Classes
struct	SkPath_Storage_Equivalent
class	SkAutoDisableDirectionCheck
class	SkAutoPathBoundsUpdate
struct	Convexicator
class	ContourIter
struct	SkHalfPlane

Macros
#define	INITIAL_LASTMOVETOINDEX_VALUE   ~0
#define	kValueNeverReturnedBySign   2

Enumerations
enum	DirChange {   kUnknown_DirChange , kLeft_DirChange , kRight_DirChange , kStraight_DirChange ,   kBackwards_DirChange , kInvalid_DirChange }

Functions
static float	poly_eval (float A, float B, float C, float t)
static float	poly_eval (float A, float B, float C, float D, float t)
static void	joinNoEmptyChecks (SkRect *dst, const SkRect &src)
static bool	is_degenerate (const SkPath &path)
bool	operator== (const SkPath &a, const SkPath &b)
static bool	check_edge_against_rect (const SkPoint &p0, const SkPoint &p1, const SkRect &rect, SkPathFirstDirection dir)
static int	rect_make_dir (SkScalar dx, SkScalar dy)
static void	assert_known_direction (SkPathDirection dir)
static bool	arc_is_lone_point (const SkRect &oval, SkScalar startAngle, SkScalar sweepAngle, SkPoint *pt)
static void	angles_to_unit_vectors (SkScalar startAngle, SkScalar sweepAngle, SkVector *startV, SkVector *stopV, SkRotationDirection *dir)
static int	build_arc_conics (const SkRect &oval, const SkVector &start, const SkVector &stop, SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc], SkPoint *singlePt)
static void	subdivide_cubic_to (SkPath *path, const SkPoint pts[4], int level=2)
static void	append_params (SkString *str, const char label[], const SkPoint pts[], int count, SkScalarAsStringType strType, SkScalar conicWeight=-12345)
static int	sign (SkScalar x)
static SkScalar	cross_prod (const SkPoint &p0, const SkPoint &p1, const SkPoint &p2)
static int	find_max_y (const SkPoint pts[], int count)
static int	find_diff_pt (const SkPoint pts[], int index, int n, int inc)
static int	find_min_max_x_at_y (const SkPoint pts[], int index, int n, int *maxIndexPtr)
static SkPathFirstDirection	crossToDir (SkScalar cross)
static bool	between (SkScalar a, SkScalar b, SkScalar c)
static SkScalar	eval_cubic_pts (SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, SkScalar t)
template<size_t N>
static void	find_minmax (const SkPoint pts[], SkScalar *minPtr, SkScalar *maxPtr)
static bool	checkOnCurve (SkScalar x, SkScalar y, const SkPoint &start, const SkPoint &end)
static int	winding_mono_cubic (const SkPoint pts[], SkScalar x, SkScalar y, int *onCurveCount)
static int	winding_cubic (const SkPoint pts[], SkScalar x, SkScalar y, int *onCurveCount)
static double	conic_eval_numerator (const SkScalar src[], SkScalar w, SkScalar t)
static double	conic_eval_denominator (SkScalar w, SkScalar t)
static int	winding_mono_conic (const SkConic &conic, SkScalar x, SkScalar y, int *onCurveCount)
static bool	is_mono_quad (SkScalar y0, SkScalar y1, SkScalar y2)
static int	winding_conic (const SkPoint pts[], SkScalar x, SkScalar y, SkScalar weight, int *onCurveCount)
static int	winding_mono_quad (const SkPoint pts[], SkScalar x, SkScalar y, int *onCurveCount)
static int	winding_quad (const SkPoint pts[], SkScalar x, SkScalar y, int *onCurveCount)
static int	winding_line (const SkPoint pts[], SkScalar x, SkScalar y, int *onCurveCount)
static void	tangent_cubic (const SkPoint pts[], SkScalar x, SkScalar y, SkTDArray< SkVector > *tangents)
static void	tangent_conic (const SkPoint pts[], SkScalar x, SkScalar y, SkScalar w, SkTDArray< SkVector > *tangents)
static void	tangent_quad (const SkPoint pts[], SkScalar x, SkScalar y, SkTDArray< SkVector > *tangents)
static void	tangent_line (const SkPoint pts[], SkScalar x, SkScalar y, SkTDArray< SkVector > *tangents)
static bool	contains_inclusive (const SkRect &r, SkScalar x, SkScalar y)
static int	compute_quad_extremas (const SkPoint src[3], SkPoint extremas[3])
static int	compute_conic_extremas (const SkPoint src[3], SkScalar w, SkPoint extremas[3])
static int	compute_cubic_extremas (const SkPoint src[4], SkPoint extremas[5])
SkPathVerbAnalysis	sk_path_analyze_verbs (const uint8_t vbs[], int verbCount)
static SkPath	clip (const SkPath &path, const SkHalfPlane &plane)

Macro Definition Documentation

INITIAL_LASTMOVETOINDEX_VALUE

#define INITIAL_LASTMOVETOINDEX_VALUE   ~0

Definition at line 154 of file SkPath.cpp.

kValueNeverReturnedBySign

#define kValueNeverReturnedBySign   2

Definition at line 2206 of file SkPath.cpp.

Enumeration Type Documentation

DirChange

enum DirChange

Enumerator
kUnknown_DirChange
kLeft_DirChange
kRight_DirChange
kStraight_DirChange
kBackwards_DirChange
kInvalid_DirChange

Definition at line 2208 of file SkPath.cpp.

               {
    kUnknown_DirChange,
    kLeft_DirChange,
    kRight_DirChange,
    kStraight_DirChange,
    kBackwards_DirChange, // if double back, allow simple lines to be convex
    kInvalid_DirChange
};

Function Documentation

angles_to_unit_vectors()

static void angles_to_unit_vectors ( SkScalar  startAngle, SkScalar  sweepAngle, SkVector *  startV, SkVector *  stopV, SkRotationDirection *  dir  )

static

Definition at line 940 of file SkPath.cpp.

                                                                                                {
    SkScalar startRad = SkDegreesToRadians(startAngle),
             stopRad  = SkDegreesToRadians(startAngle + sweepAngle);
 
    startV->fY = SkScalarSinSnapToZero(startRad);
    startV->fX = SkScalarCosSnapToZero(startRad);
    stopV->fY = SkScalarSinSnapToZero(stopRad);
    stopV->fX = SkScalarCosSnapToZero(stopRad);
 
    /*  If the sweep angle is nearly (but less than) 360, then due to precision
     loss in radians-conversion and/or sin/cos, we may end up with coincident
     vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
     of drawing a nearly complete circle (good).
     e.g. canvas.drawArc(0, 359.99, ...)
     -vs- canvas.drawArc(0, 359.9, ...)
     We try to detect this edge case, and tweak the stop vector
     */
    if (*startV == *stopV) {
        SkScalar sw = SkScalarAbs(sweepAngle);
        if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
            // make a guess at a tiny angle (in radians) to tweak by
            SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
            // not sure how much will be enough, so we use a loop
            do {
                stopRad -= deltaRad;
                stopV->fY = SkScalarSinSnapToZero(stopRad);
                stopV->fX = SkScalarCosSnapToZero(stopRad);
            } while (*startV == *stopV);
        }
    }
    *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection;
}

append_params()

static void append_params ( SkString *  str, const char  label[], const SkPoint  pts[], int  count, SkScalarAsStringType  strType, SkScalar  conicWeight = -12345  )

static

Definition at line 2005 of file SkPath.cpp.

                                                                                                  {
    str->append(label);
    str->append("(");
 
    const SkScalar* values = &pts[0].fX;
    count *= 2;
 
    for (int i = 0; i < count; ++i) {
        SkAppendScalar(str, values[i], strType);
        if (i < count - 1) {
            str->append(", ");
        }
    }
    if (conicWeight != -12345) {
        str->append(", ");
        SkAppendScalar(str, conicWeight, strType);
    }
    str->append(");");
    if (kHex_SkScalarAsStringType == strType) {
        str->append("  // ");
        for (int i = 0; i < count; ++i) {
            SkAppendScalarDec(str, values[i]);
            if (i < count - 1) {
                str->append(", ");
            }
        }
        if (conicWeight >= 0) {
            str->append(", ");
            SkAppendScalarDec(str, conicWeight);
        }
    }
    str->append("\n");
}

arc_is_lone_point()

static bool arc_is_lone_point ( const SkRect &  oval, SkScalar  startAngle, SkScalar  sweepAngle, SkPoint *  pt  )

static

Definition at line 917 of file SkPath.cpp.

                                           {
    if (0 == sweepAngle && (0 == startAngle || SkIntToScalar(360) == startAngle)) {
        // Chrome uses this path to move into and out of ovals. If not
        // treated as a special case the moves can distort the oval's
        // bounding box (and break the circle special case).
        pt->set(oval.fRight, oval.centerY());
        return true;
    } else if (0 == oval.width() && 0 == oval.height()) {
        // Chrome will sometimes create 0 radius round rects. Having degenerate
        // quad segments in the path prevents the path from being recognized as
        // a rect.
        // TODO: optimizing the case where only one of width or height is zero
        // should also be considered. This case, however, doesn't seem to be
        // as common as the single point case.
        pt->set(oval.fRight, oval.fTop);
        return true;
    }
    return false;
}

assert_known_direction()

static void assert_known_direction ( SkPathDirection  dir )

static

Definition at line 860 of file SkPath.cpp.

                                                        {
    SkASSERT(SkPathDirection::kCW == dir || SkPathDirection::kCCW == dir);
}

between()

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

static

Definition at line 2716 of file SkPath.cpp.

                                                        {
    SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
            || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c)));
    return (a - b) * (c - b) <= 0;
}

build_arc_conics()

static int build_arc_conics ( const SkRect &  oval, const SkVector &  start, const SkVector &  stop, SkRotationDirection  dir, SkConic  conics[SkConic::kMaxConicsForArc], SkPoint *  singlePt  )

static

If this returns 0, then the caller should just line-to the singlePt, else it should ignore singlePt and append the specified number of conics.

Definition at line 978 of file SkPath.cpp.

                                               {
    SkMatrix    matrix;
 
    matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
    matrix.postTranslate(oval.centerX(), oval.centerY());
 
    int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics);
    if (0 == count) {
        matrix.mapXY(stop.x(), stop.y(), singlePt);
    }
    return count;
}

check_edge_against_rect()

static bool check_edge_against_rect ( const SkPoint &  p0, const SkPoint &  p1, const SkRect &  rect, SkPathFirstDirection  dir  )

inlinestatic

Definition at line 265 of file SkPath.cpp.

                                                                     {
    const SkPoint* edgeBegin;
    SkVector v;
    if (SkPathFirstDirection::kCW == dir) {
        v = p1 - p0;
        edgeBegin = &p0;
    } else {
        v = p0 - p1;
        edgeBegin = &p1;
    }
    if (v.fX || v.fY) {
        // check the cross product of v with the vec from edgeBegin to each rect corner
        SkScalar yL = v.fY * (rect.fLeft - edgeBegin->fX);
        SkScalar xT = v.fX * (rect.fTop - edgeBegin->fY);
        SkScalar yR = v.fY * (rect.fRight - edgeBegin->fX);
        SkScalar xB = v.fX * (rect.fBottom - edgeBegin->fY);
        if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
            return false;
        }
    }
    return true;
}

checkOnCurve()

static bool checkOnCurve ( SkScalar  x, SkScalar  y, const SkPoint &  start, const SkPoint &  end  )

static

Definition at line 2743 of file SkPath.cpp.

                                                                                           {
    if (start.fY == end.fY) {
        return between(start.fX, x, end.fX) && x != end.fX;
    } else {
        return x == start.fX && y == start.fY;
    }
}

clip()

static SkPath clip ( const SkPath &  path, const SkHalfPlane &  plane  )

static

Definition at line 3892 of file SkPath.cpp.

                                                                 {
    SkMatrix mx, inv;
    SkPoint p0 = { -plane.fA*plane.fC, -plane.fB*plane.fC };
    mx.setAll( plane.fB, plane.fA, p0.fX,
              -plane.fA, plane.fB, p0.fY,
                      0,        0,     1);
    if (!mx.invert(&inv)) {
        return SkPath();
    }
 
    SkPath rotated;
    path.transform(inv, &rotated);
    if (!rotated.isFinite()) {
        return SkPath();
    }
 
    SkScalar big = SK_ScalarMax;
    SkRect clip = {-big, 0, big, big };
 
    struct Rec {
        SkPathBuilder fResult;
        SkPoint       fPrev = {0,0};
    } rec;
 
    SkEdgeClipper::ClipPath(rotated, clip, false,
                            [](SkEdgeClipper* clipper, bool newCtr, void* ctx) {
        Rec* rec = (Rec*)ctx;
 
        bool addLineTo = false;
        SkPoint      pts[4];
        SkPath::Verb verb;
        while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
            if (newCtr) {
                rec->fResult.moveTo(pts[0]);
                rec->fPrev = pts[0];
                newCtr = false;
            }
 
            if (addLineTo || pts[0] != rec->fPrev) {
                rec->fResult.lineTo(pts[0]);
            }
 
            switch (verb) {
                case SkPath::kLine_Verb:
                    rec->fResult.lineTo(pts[1]);
                    rec->fPrev = pts[1];
                    break;
                case SkPath::kQuad_Verb:
                    rec->fResult.quadTo(pts[1], pts[2]);
                    rec->fPrev = pts[2];
                    break;
                case SkPath::kCubic_Verb:
                    rec->fResult.cubicTo(pts[1], pts[2], pts[3]);
                    rec->fPrev = pts[3];
                    break;
                default: break;
            }
            addLineTo = true;
        }
    }, &rec);
 
    rec.fResult.setFillType(path.getFillType());
    SkPath result = rec.fResult.detach().makeTransform(mx);
    if (!result.isFinite()) {
        result = SkPath();
    }
    return result;
}

compute_conic_extremas()

static int compute_conic_extremas ( const SkPoint  src[3], SkScalar  w, SkPoint  extremas[3]  )

static

Definition at line 3421 of file SkPath.cpp.

                                                                                         {
    SkConic conic(src[0], src[1], src[2], w);
    SkScalar ts[2];
    int n  = conic.findXExtrema(ts);
        n += conic.findYExtrema(&ts[n]);
    SkASSERT(n >= 0 && n <= 2);
    for (int i = 0; i < n; ++i) {
        extremas[i] = conic.evalAt(ts[i]);
    }
    extremas[n] = src[2];
    return n + 1;
}

compute_cubic_extremas()

static int compute_cubic_extremas ( const SkPoint  src[4], SkPoint  extremas[5]  )

static

Definition at line 3434 of file SkPath.cpp.

                                                                             {
    SkScalar ts[4];
    int n  = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, src[3].fX, ts);
        n += SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, src[3].fY, &ts[n]);
    SkASSERT(n >= 0 && n <= 4);
    for (int i = 0; i < n; ++i) {
        SkEvalCubicAt(src, ts[i], &extremas[i], nullptr, nullptr);
    }
    extremas[n] = src[3];
    return n + 1;
}

compute_quad_extremas()

static int compute_quad_extremas ( const SkPoint  src[3], SkPoint  extremas[3]  )

static

Definition at line 3409 of file SkPath.cpp.

                                                                            {
    SkScalar ts[2];
    int n  = SkFindQuadExtrema(src[0].fX, src[1].fX, src[2].fX, ts);
        n += SkFindQuadExtrema(src[0].fY, src[1].fY, src[2].fY, &ts[n]);
    SkASSERT(n >= 0 && n <= 2);
    for (int i = 0; i < n; ++i) {
        extremas[i] = SkEvalQuadAt(src, ts[i]);
    }
    extremas[n] = src[2];
    return n + 1;
}

conic_eval_denominator()

static double conic_eval_denominator ( SkScalar  w, SkScalar  t  )

static

Definition at line 2818 of file SkPath.cpp.

                                                             {
    SkScalar B = 2 * (w - 1);
    SkScalar C = 1;
    SkScalar A = -B;
    return poly_eval(A, B, C, t);
}

conic_eval_numerator()

static double conic_eval_numerator ( const SkScalar  src[], SkScalar  w, SkScalar  t  )

static

Definition at line 2807 of file SkPath.cpp.

                                                                                 {
    SkASSERT(src);
    SkASSERT(t >= 0 && t <= 1);
    SkScalar src2w = src[2] * w;
    SkScalar C = src[0];
    SkScalar A = src[4] - 2 * src2w + C;
    SkScalar B = 2 * (src2w - C);
    return poly_eval(A, B, C, t);
}

contains_inclusive()

static bool contains_inclusive ( const SkRect &  r, SkScalar  x, SkScalar  y  )

static

Definition at line 3114 of file SkPath.cpp.

                                                                        {
    return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
}

cross_prod()

static SkScalar cross_prod ( const SkPoint &  p0, const SkPoint &  p1, const SkPoint &  p2  )

static

Definition at line 2537 of file SkPath.cpp.

                                                                                    {
    SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
    // We may get 0 when the above subtracts underflow. We expect this to be
    // very rare and lazily promote to double.
    if (0 == cross) {
        double p0x = SkScalarToDouble(p0.fX);
        double p0y = SkScalarToDouble(p0.fY);
 
        double p1x = SkScalarToDouble(p1.fX);
        double p1y = SkScalarToDouble(p1.fY);
 
        double p2x = SkScalarToDouble(p2.fX);
        double p2y = SkScalarToDouble(p2.fY);
 
        cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
                                 (p1y - p0y) * (p2x - p0x));
 
    }
    return cross;
}

crossToDir()

static SkPathFirstDirection crossToDir ( SkScalar  cross )

static

Definition at line 2615 of file SkPath.cpp.

                                                       {
    return cross > 0 ? SkPathFirstDirection::kCW : SkPathFirstDirection::kCCW;
}

eval_cubic_pts()

static SkScalar eval_cubic_pts ( SkScalar  c0, SkScalar  c1, SkScalar  c2, SkScalar  c3, SkScalar  t  )

static

Definition at line 2722 of file SkPath.cpp.

                                           {
    SkScalar A = c3 + 3*(c1 - c2) - c0;
    SkScalar B = 3*(c2 - c1 - c1 + c0);
    SkScalar C = 3*(c1 - c0);
    SkScalar D = c0;
    return poly_eval(A, B, C, D, t);
}

find_diff_pt()

static int find_diff_pt ( const SkPoint  pts[], int  index, int  n, int  inc  )

static

Definition at line 2573 of file SkPath.cpp.

                                                                        {
    int i = index;
    for (;;) {
        i = (i + inc) % n;
        if (i == index) {   // we wrapped around, so abort
            break;
        }
        if (pts[index] != pts[i]) { // found a different point, success!
            break;
        }
    }
    return i;
}

find_max_y()

static int find_max_y ( const SkPoint  pts[], int  count  )

static

Definition at line 2559 of file SkPath.cpp.

                                                      {
    SkASSERT(count > 0);
    SkScalar max = pts[0].fY;
    int firstIndex = 0;
    for (int i = 1; i < count; ++i) {
        SkScalar y = pts[i].fY;
        if (y > max) {
            max = y;
            firstIndex = i;
        }
    }
    return firstIndex;
}

find_min_max_x_at_y()

static int find_min_max_x_at_y ( const SkPoint  pts[], int  index, int  n, int *  maxIndexPtr  )

static

Starting at index, and moving forward (incrementing), find the xmin and xmax of the contiguous points that have the same Y.

Definition at line 2591 of file SkPath.cpp.

                                                 {
    const SkScalar y = pts[index].fY;
    SkScalar min = pts[index].fX;
    SkScalar max = min;
    int minIndex = index;
    int maxIndex = index;
    for (int i = index + 1; i < n; ++i) {
        if (pts[i].fY != y) {
            break;
        }
        SkScalar x = pts[i].fX;
        if (x < min) {
            min = x;
            minIndex = i;
        } else if (x > max) {
            max = x;
            maxIndex = i;
        }
    }
    *maxIndexPtr = maxIndex;
    return minIndex;
}

find_minmax()

template<size_t N>

static void find_minmax ( const SkPoint  pts[], SkScalar *  minPtr, SkScalar *  maxPtr  )

static

Definition at line 2731 of file SkPath.cpp.

                                                                                {
    SkScalar min, max;
    min = max = pts[0].fX;
    for (size_t i = 1; i < N; ++i) {
        min = std::min(min, pts[i].fX);
        max = std::max(max, pts[i].fX);
    }
    *minPtr = min;
    *maxPtr = max;
}

is_degenerate()

static bool is_degenerate ( const SkPath &  path )

static

Definition at line 73 of file SkPath.cpp.

                                              {
    return (path.countVerbs() - SkPathPriv::LeadingMoveToCount(path)) == 0;
}

is_mono_quad()

static bool is_mono_quad ( SkScalar  y0, SkScalar  y1, SkScalar  y2  )

static

Definition at line 2875 of file SkPath.cpp.

                                                                {
    //    return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
    if (y0 == y1) {
        return true;
    }
    if (y0 < y1) {
        return y1 <= y2;
    } else {
        return y1 >= y2;
    }
}

joinNoEmptyChecks()

static void joinNoEmptyChecks ( SkRect *  dst, const SkRect &  src  )

static

Path.bounds is defined to be the bounds of all the control points. If we called bounds.join(r) we would skip r if r was empty, which breaks our promise. Hence we have a custom joiner that doesn't look at emptiness

Definition at line 66 of file SkPath.cpp.

                                                              {
    dst->fLeft = std::min(dst->fLeft, src.fLeft);
    dst->fTop = std::min(dst->fTop, src.fTop);
    dst->fRight = std::max(dst->fRight, src.fRight);
    dst->fBottom = std::max(dst->fBottom, src.fBottom);
}

operator==()

bool operator==	(	const SkPath &	a,
		const SkPath &	b
	)

Compares a and b; returns true if SkPath::FillType, verb array, SkPoint array, and weights are equivalent.

Parameters

a	SkPath to compare
b	SkPath to compare

Returns

true if SkPath pair are equivalent

Definition at line 212 of file SkPath.cpp.

                                                  {
    // note: don't need to look at isConvex or bounds, since just comparing the
    // raw data is sufficient.
    return &a == &b ||
        (a.fFillType == b.fFillType && *a.fPathRef == *b.fPathRef);
}

poly_eval() [1/2]

static float poly_eval ( float  A, float  B, float  C, float  D, float  t  )

static

Definition at line 55 of file SkPath.cpp.

                                                                    {
    return ((A * t + B) * t + C) * t + D;
}

poly_eval() [2/2]

static float poly_eval ( float  A, float  B, float  C, float  t  )

static

Definition at line 51 of file SkPath.cpp.

                                                           {
    return (A * t + B) * t + C;
}

rect_make_dir()

static int rect_make_dir ( SkScalar  dx, SkScalar  dy  )

static

Definition at line 512 of file SkPath.cpp.

                                                   {
    return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
}

sign()

static int sign ( SkScalar  x )

static

Definition at line 2205 of file SkPath.cpp.

{ return x < 0; }

sk_path_analyze_verbs()

SkPathVerbAnalysis sk_path_analyze_verbs	(	const uint8_t	vbs[],
		int	verbCount
	)

Definition at line 3515 of file SkPath.cpp.

                                                                             {
    SkPathVerbAnalysis info = {false, 0, 0, 0};
    bool needMove = true;
    bool invalid = false;
 
    if (verbCount >= (INT_MAX / 3)) SK_UNLIKELY {
        // A path with an extremely high number of quad, conic or cubic verbs could cause
        // `info.points` to overflow. To prevent against this, we reject extremely large paths. This
        // check is conservative and assumes the worst case (in particular, it assumes that every
        // verb consumes 3 points, which would only happen for a path composed entirely of cubics).
        // This limits us to 700 million verbs, which is large enough for any reasonable use case.
        invalid = true;
    } else {
        for (int i = 0; i < verbCount; ++i) {
            switch ((SkPathVerb)vbs[i]) {
                case SkPathVerb::kMove:
                    needMove = false;
                    info.points += 1;
                    break;
                case SkPathVerb::kLine:
                    invalid |= needMove;
                    info.segmentMask |= kLine_SkPathSegmentMask;
                    info.points += 1;
                    break;
                case SkPathVerb::kQuad:
                    invalid |= needMove;
                    info.segmentMask |= kQuad_SkPathSegmentMask;
                    info.points += 2;
                    break;
                case SkPathVerb::kConic:
                    invalid |= needMove;
                    info.segmentMask |= kConic_SkPathSegmentMask;
                    info.points += 2;
                    info.weights += 1;
                    break;
                case SkPathVerb::kCubic:
                    invalid |= needMove;
                    info.segmentMask |= kCubic_SkPathSegmentMask;
                    info.points += 3;
                    break;
                case SkPathVerb::kClose:
                    invalid |= needMove;
                    needMove = true;
                    break;
                default:
                    invalid = true;
                    break;
            }
        }
    }
    info.valid = !invalid;
    return info;
}

subdivide_cubic_to()

static void subdivide_cubic_to ( SkPath *  path, const SkPoint  pts[4], int  level = 2  )

static

Definition at line 1698 of file SkPath.cpp.

                                              {
    if (--level >= 0) {
        SkPoint tmp[7];
 
        SkChopCubicAtHalf(pts, tmp);
        subdivide_cubic_to(path, &tmp[0], level);
        subdivide_cubic_to(path, &tmp[3], level);
    } else {
        path->cubicTo(pts[1], pts[2], pts[3]);
    }
}

tangent_conic()

static void tangent_conic ( const SkPoint  pts[], SkScalar  x, SkScalar  y, SkScalar  w, SkTDArray< SkVector > *  tangents  )

static

Definition at line 3039 of file SkPath.cpp.

                                           {
    if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
        return;
    }
    if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
        return;
    }
    SkScalar roots[2];
    SkScalar A = pts[2].fY;
    SkScalar B = pts[1].fY * w - y * w + y;
    SkScalar C = pts[0].fY;
    A += C - 2 * B;  // A = a + c - 2*(b*w - yCept*w + yCept)
    B -= C;  // B = b*w - w * yCept + yCept - a
    C -= y;
    int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
    for (int index = 0; index < n; ++index) {
        SkScalar t = roots[index];
        SkScalar xt = conic_eval_numerator(&pts[0].fX, w, t) / conic_eval_denominator(w, t);
        if (!SkScalarNearlyEqual(x, xt)) {
            continue;
        }
        SkConic conic(pts, w);
        tangents->push_back(conic.evalTangentAt(t));
    }
}

tangent_cubic()

static void tangent_cubic ( const SkPoint  pts[], SkScalar  x, SkScalar  y, SkTDArray< SkVector > *  tangents  )

static

Definition at line 3011 of file SkPath.cpp.

                                       {
    if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)
             && !between(pts[2].fY, y, pts[3].fY)) {
        return;
    }
    if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)
             && !between(pts[2].fX, x, pts[3].fX)) {
        return;
    }
    SkPoint dst[10];
    int n = SkChopCubicAtYExtrema(pts, dst);
    for (int i = 0; i <= n; ++i) {
        SkPoint* c = &dst[i * 3];
        SkScalar t;
        if (!SkCubicClipper::ChopMonoAtY(c, y, &t)) {
            continue;
        }
        SkScalar xt = eval_cubic_pts(c[0].fX, c[1].fX, c[2].fX, c[3].fX, t);
        if (!SkScalarNearlyEqual(x, xt)) {
            continue;
        }
        SkVector tangent;
        SkEvalCubicAt(c, t, nullptr, &tangent, nullptr);
        tangents->push_back(tangent);
    }
}

tangent_line()

static void tangent_line ( const SkPoint  pts[], SkScalar  x, SkScalar  y, SkTDArray< SkVector > *  tangents  )

static

Definition at line 3092 of file SkPath.cpp.

                                       {
    SkScalar y0 = pts[0].fY;
    SkScalar y1 = pts[1].fY;
    if (!between(y0, y, y1)) {
        return;
    }
    SkScalar x0 = pts[0].fX;
    SkScalar x1 = pts[1].fX;
    if (!between(x0, x, x1)) {
        return;
    }
    SkScalar dx = x1 - x0;
    SkScalar dy = y1 - y0;
    if (!SkScalarNearlyEqual((x - x0) * dy, dx * (y - y0))) {
        return;
    }
    SkVector v;
    v.set(dx, dy);
    tangents->push_back(v);
}

tangent_quad()

static void tangent_quad ( const SkPoint  pts[], SkScalar  x, SkScalar  y, SkTDArray< SkVector > *  tangents  )

static

Definition at line 3066 of file SkPath.cpp.

                                       {
    if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
        return;
    }
    if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
        return;
    }
    SkScalar roots[2];
    int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
                                2 * (pts[1].fY - pts[0].fY),
                                pts[0].fY - y,
                                roots);
    for (int index = 0; index < n; ++index) {
        SkScalar t = roots[index];
        SkScalar C = pts[0].fX;
        SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
        SkScalar B = 2 * (pts[1].fX - C);
        SkScalar xt = poly_eval(A, B, C, t);
        if (!SkScalarNearlyEqual(x, xt)) {
            continue;
        }
        tangents->push_back(SkEvalQuadTangentAt(pts, t));
    }
}

winding_conic()

static int winding_conic ( const SkPoint  pts[], SkScalar  x, SkScalar  y, SkScalar  weight, int *  onCurveCount  )

static

Definition at line 2887 of file SkPath.cpp.

                                            {
    SkConic conic(pts, weight);
    SkConic chopped[2];
    // If the data points are very large, the conic may not be monotonic but may also
    // fail to chop. Then, the chopper does not split the original conic in two.
    bool isMono = is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY) || !conic.chopAtYExtrema(chopped);
    int w = winding_mono_conic(isMono ? conic : chopped[0], x, y, onCurveCount);
    if (!isMono) {
        w += winding_mono_conic(chopped[1], x, y, onCurveCount);
    }
    return w;
}

winding_cubic()

static int winding_cubic ( const SkPoint  pts[], SkScalar  x, SkScalar  y, int *  onCurveCount  )

static

Definition at line 2797 of file SkPath.cpp.

                                                                                         {
    SkPoint dst[10];
    int n = SkChopCubicAtYExtrema(pts, dst);
    int w = 0;
    for (int i = 0; i <= n; ++i) {
        w += winding_mono_cubic(&dst[i * 3], x, y, onCurveCount);
    }
    return w;
}

winding_line()

static int winding_line ( const SkPoint  pts[], SkScalar  x, SkScalar  y, int *  onCurveCount  )

static

Definition at line 2971 of file SkPath.cpp.

                                                                                        {
    SkScalar x0 = pts[0].fX;
    SkScalar y0 = pts[0].fY;
    SkScalar x1 = pts[1].fX;
    SkScalar y1 = pts[1].fY;
 
    SkScalar dy = y1 - y0;
 
    int dir = 1;
    if (y0 > y1) {
        using std::swap;
        swap(y0, y1);
        dir = -1;
    }
    if (y < y0 || y > y1) {
        return 0;
    }
    if (checkOnCurve(x, y, pts[0], pts[1])) {
        *onCurveCount += 1;
        return 0;
    }
    if (y == y1) {
        return 0;
    }
    SkScalar cross = (x1 - x0) * (y - pts[0].fY) - dy * (x - x0);
 
    if (!cross) {
        // zero cross means the point is on the line, and since the case where
        // y of the query point is at the end point is handled above, we can be
        // sure that we're on the line (excluding the end point) here
        if (x != x1 || y != pts[1].fY) {
            *onCurveCount += 1;
        }
        dir = 0;
    } else if (SkScalarSignAsInt(cross) == dir) {
        dir = 0;
    }
    return dir;
}

winding_mono_conic()

static int winding_mono_conic ( const SkConic &  conic, SkScalar  x, SkScalar  y, int *  onCurveCount  )

static

Definition at line 2825 of file SkPath.cpp.

                                                                                               {
    const SkPoint* pts = conic.fPts;
    SkScalar y0 = pts[0].fY;
    SkScalar y2 = pts[2].fY;
 
    int dir = 1;
    if (y0 > y2) {
        using std::swap;
        swap(y0, y2);
        dir = -1;
    }
    if (y < y0 || y > y2) {
        return 0;
    }
    if (checkOnCurve(x, y, pts[0], pts[2])) {
        *onCurveCount += 1;
        return 0;
    }
    if (y == y2) {
        return 0;
    }
 
    SkScalar roots[2];
    SkScalar A = pts[2].fY;
    SkScalar B = pts[1].fY * conic.fW - y * conic.fW + y;
    SkScalar C = pts[0].fY;
    A += C - 2 * B;  // A = a + c - 2*(b*w - yCept*w + yCept)
    B -= C;  // B = b*w - w * yCept + yCept - a
    C -= y;
    int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
    SkASSERT(n <= 1);
    SkScalar xt;
    if (0 == n) {
        // zero roots are returned only when y0 == y
        // Need [0] if dir == 1
        // and  [2] if dir == -1
        xt = pts[1 - dir].fX;
    } else {
        SkScalar t = roots[0];
        xt = conic_eval_numerator(&pts[0].fX, conic.fW, t) / conic_eval_denominator(conic.fW, t);
    }
    if (SkScalarNearlyEqual(xt, x)) {
        if (x != pts[2].fX || y != pts[2].fY) {  // don't test end points; they're start points
            *onCurveCount += 1;
            return 0;
        }
    }
    return xt < x ? dir : 0;
}

winding_mono_cubic()

static int winding_mono_cubic ( const SkPoint  pts[], SkScalar  x, SkScalar  y, int *  onCurveCount  )

static

Definition at line 2751 of file SkPath.cpp.

                                                                                              {
    SkScalar y0 = pts[0].fY;
    SkScalar y3 = pts[3].fY;
 
    int dir = 1;
    if (y0 > y3) {
        using std::swap;
        swap(y0, y3);
        dir = -1;
    }
    if (y < y0 || y > y3) {
        return 0;
    }
    if (checkOnCurve(x, y, pts[0], pts[3])) {
        *onCurveCount += 1;
        return 0;
    }
    if (y == y3) {
        return 0;
    }
 
    // quickreject or quickaccept
    SkScalar min, max;
    find_minmax<4>(pts, &min, &max);
    if (x < min) {
        return 0;
    }
    if (x > max) {
        return dir;
    }
 
    // compute the actual x(t) value
    SkScalar t;
    if (!SkCubicClipper::ChopMonoAtY(pts, y, &t)) {
        return 0;
    }
    SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
    if (SkScalarNearlyEqual(xt, x)) {
        if (x != pts[3].fX || y != pts[3].fY) {  // don't test end points; they're start points
            *onCurveCount += 1;
            return 0;
        }
    }
    return xt < x ? dir : 0;
}

winding_mono_quad()

static int winding_mono_quad ( const SkPoint  pts[], SkScalar  x, SkScalar  y, int *  onCurveCount  )

static

Definition at line 2901 of file SkPath.cpp.

                                                                                             {
    SkScalar y0 = pts[0].fY;
    SkScalar y2 = pts[2].fY;
 
    int dir = 1;
    if (y0 > y2) {
        using std::swap;
        swap(y0, y2);
        dir = -1;
    }
    if (y < y0 || y > y2) {
        return 0;
    }
    if (checkOnCurve(x, y, pts[0], pts[2])) {
        *onCurveCount += 1;
        return 0;
    }
    if (y == y2) {
        return 0;
    }
    // bounds check on X (not required. is it faster?)
#if 0
    if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
        return 0;
    }
#endif
 
    SkScalar roots[2];
    int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
                                2 * (pts[1].fY - pts[0].fY),
                                pts[0].fY - y,
                                roots);
    SkASSERT(n <= 1);
    SkScalar xt;
    if (0 == n) {
        // zero roots are returned only when y0 == y
        // Need [0] if dir == 1
        // and  [2] if dir == -1
        xt = pts[1 - dir].fX;
    } else {
        SkScalar t = roots[0];
        SkScalar C = pts[0].fX;
        SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
        SkScalar B = 2 * (pts[1].fX - C);
        xt = poly_eval(A, B, C, t);
    }
    if (SkScalarNearlyEqual(xt, x)) {
        if (x != pts[2].fX || y != pts[2].fY) {  // don't test end points; they're start points
            *onCurveCount += 1;
            return 0;
        }
    }
    return xt < x ? dir : 0;
}

winding_quad()

static int winding_quad ( const SkPoint  pts[], SkScalar  x, SkScalar  y, int *  onCurveCount  )

static

Definition at line 2956 of file SkPath.cpp.

                                                                                        {
    SkPoint dst[5];
    int     n = 0;
 
    if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
        n = SkChopQuadAtYExtrema(pts, dst);
        pts = dst;
    }
    int w = winding_mono_quad(pts, x, y, onCurveCount);
    if (n > 0) {
        w += winding_mono_quad(&pts[2], x, y, onCurveCount);
    }
    return w;
}