skgpu::tess Namespace Reference

Classes
struct	AddTrianglesWhenChopping
class	AffineMatrix
struct	AttribValue
class	CullTest
struct	DiscardFlatCurves
class	FixedCountCurves
class	FixedCountStrokes
class	FixedCountWedges
class	LinearTolerances
class	MiddleOutPolygonTriangulator
class	MidpointContourParser
struct	NullTriangulator
struct	Optional
struct	PatchStorage
class	PatchWriter
class	PathMiddleOutFanIter
struct	ReplicateLineEndPoints
struct	Required
class	StrokeIterator
struct	StrokeParams
struct	TrackJoinControlPoints

Enumerations
enum class	PatchAttribs {   kNone = 0 , kJoinControlPoint = 1 << 0 , kFanPoint = 1 << 1 , kStrokeParams = 1 << 2 ,   kColor = 1 << 3 , kPaintDepth = 1 << 4 , kExplicitCurveType = 1 << 5 , kSsboIndex = 1 << 7 ,   kWideColorIfEnabled = 1 << 6 }

Functions
template<PatchAttribs A, typename T , bool Required, bool Optional>
VertexWriter &	operator<< (VertexWriter &w, const AttribValue< A, T, Required, Optional > &v)
SkPath	PreChopPathCurves (float tessellationPrecision, const SkPath &path, const SkMatrix &matrix, const SkRect &viewport)
int	FindCubicConvex180Chops (const SkPoint pts[], float T[2], bool *areCusps)
static constexpr int	NumCurveTrianglesAtResolveLevel (int resolveLevel)
constexpr size_t	PatchAttribsStride (PatchAttribs attribs)
constexpr size_t	PatchStride (PatchAttribs attribs)
bool	ConicHasCusp (const SkPoint p[3])
float	GetJoinType (const SkStrokeRec &stroke)
bool	StrokesHaveEqualParams (const SkStrokeRec &a, const SkStrokeRec &b)
constexpr int	NumFixedEdgesInJoin (SkPaint::Join joinType)
constexpr int	NumFixedEdgesInJoin (const StrokeParams &strokeParams)
float	CalcNumRadialSegmentsPerRadian (float approxDevStrokeRadius)
	DEF_TEST (CullTestTest, reporter)
static bool	is_linear (SkPoint p0, SkPoint p1, SkPoint p2)
static bool	is_linear (const SkPoint p[4])
static void	check_cubic_convex_180 (skiatest::Reporter *r, const SkPoint p[4])
	DEF_TEST (FindCubicConvex180Chops, r)
	DEF_TEST (PreChopPathCurves, reporter)
static float	wangs_formula_quadratic_reference_impl (float precision, const SkPoint p[3])
static float	wangs_formula_cubic_reference_impl (float precision, const SkPoint p[4])
static float	wangs_formula_conic_reference_impl (float precision, const SkPoint P[3], const float w)
static void	for_random_matrices (SkRandom *rand, const std::function< void(const SkMatrix &)> &f)
static void	for_random_beziers (int numPoints, SkRandom *rand, const std::function< void(const SkPoint[])> &f, int maxExponent=30)
	DEF_TEST (wangs_formula_log2, r)
	DEF_TEST (wangs_formula_vectorXforms, r)
	DEF_TEST (wangs_formula_worst_case_cubic, r)
	DEF_TEST (wangs_formula_quad_within_tol, r)
	DEF_TEST (wangs_formula_rational_quad_reduces, r)
	DEF_TEST (wangs_formula_conic_within_tol, r)
	DEF_TEST (wangs_formula_conic_matches_reference, r)
	DEF_TEST (wangs_formula_conic_vectorXforms, r)
	DEF_TEST (wangs_formula_nextlog2, r)

Variables
static constexpr float	kPrecision = 4
static constexpr int	kMaxResolveLevel = 5
static constexpr int	kMaxParametricSegments = 1 << kMaxResolveLevel
static constexpr int	kMaxParametricSegments_p2 = kMaxParametricSegments * kMaxParametricSegments
static constexpr int	kMaxParametricSegments_p4
static constexpr float	kMaxSegmentsPerCurve = 1024
static constexpr float	kMaxSegmentsPerCurve_p2 = kMaxSegmentsPerCurve * kMaxSegmentsPerCurve
static constexpr float	kMaxSegmentsPerCurve_p4 = kMaxSegmentsPerCurve_p2 * kMaxSegmentsPerCurve_p2
static constexpr float	kCubicCurveType = 0
static constexpr float	kConicCurveType = 1
static constexpr float	kTriangularConicCurveType = 2
const SkMatrix	gMatrices []
const SkPoint	kSerp [4]
const SkPoint	kLoop [4]
const SkPoint	kQuad [4]

Enumeration Type Documentation

PatchAttribs

enum class skgpu::tess::PatchAttribs

strong

Enumerator
kNone
kJoinControlPoint
kFanPoint
kStrokeParams
kColor
kPaintDepth
kExplicitCurveType
kSsboIndex
kWideColorIfEnabled

Definition at line 77 of file Tessellation.h.

                        {
    // Attribs.
    kNone = 0,
    kJoinControlPoint = 1 << 0, // [float2] Used by strokes. This defines tangent direction.
    kFanPoint = 1 << 1,  // [float2] Used by wedges. This is the center point the wedges fan around.
    kStrokeParams = 1 << 2,  // [float2] Used when strokes have different widths or join types.
    kColor = 1 << 3,  // [ubyte4 or float4] Used when patches have different colors.
    kPaintDepth = 1 << 4, // [float] Used in Graphite to specify depth attachment value for draw.
    kExplicitCurveType = 1 << 5,  // [float] Used when GPU can't infer curve type based on infinity.
    kSsboIndex = 1 << 7,  // [int] Used to index into a shared storage buffer for this patch's
                          //       uniform values.
 
    // Extra flags.
    kWideColorIfEnabled = 1 << 6,  // If kColor is set, specifies it to be float4 wide color.
};

Function Documentation

CalcNumRadialSegmentsPerRadian()

float skgpu::tess::CalcNumRadialSegmentsPerRadian ( float  approxDevStrokeRadius )

inline

Definition at line 210 of file Tessellation.h.

                                                                         {
    float cosTheta = 1.f - (1.f / kPrecision) / approxDevStrokeRadius;
    return .5f / acosf(std::max(cosTheta, -1.f));
}

check_cubic_convex_180()

static void skgpu::tess::check_cubic_convex_180 ( skiatest::Reporter *  r, const SkPoint  p[4]  )

static

Definition at line 29 of file FindCubicConvex180ChopsTest.cpp.

                                                                            {
    bool areCusps = false;
    float inflectT[2], convex180T[2];
    if (int inflectN = SkFindCubicInflections(p, inflectT)) {
        // The curve has inflections. FindCubicConvex180Chops should return the inflection
        // points.
        int convex180N = FindCubicConvex180Chops(p, convex180T, &areCusps);
        REPORTER_ASSERT(r, inflectN == convex180N);
        if (!areCusps) {
            REPORTER_ASSERT(r, inflectN == 1 ||
                            fabsf(inflectT[0] - inflectT[1]) >= SK_ScalarNearlyZero);
        }
        for (int i = 0; i < convex180N; ++i) {
            REPORTER_ASSERT(r, SkScalarNearlyEqual(inflectT[i], convex180T[i]));
        }
    } else {
        float totalRotation = SkMeasureNonInflectCubicRotation(p);
        int convex180N = FindCubicConvex180Chops(p, convex180T, &areCusps);
        SkPoint chops[10];
        SkChopCubicAt(p, chops, convex180T, convex180N);
        float radsSum = 0;
        for (int i = 0; i <= convex180N; ++i) {
            float rads = SkMeasureNonInflectCubicRotation(chops + i*3);
            SkASSERT(rads < SK_ScalarPI + SK_ScalarNearlyZero);
            radsSum += rads;
        }
        if (totalRotation < SK_ScalarPI - SK_ScalarNearlyZero) {
            // The curve should never chop if rotation is <180 degrees.
            REPORTER_ASSERT(r, convex180N == 0);
        } else if (!is_linear(p)) {
            REPORTER_ASSERT(r, SkScalarNearlyEqual(radsSum, totalRotation));
            if (totalRotation > SK_ScalarPI + SK_ScalarNearlyZero) {
                REPORTER_ASSERT(r, convex180N == 1);
                // This works because cusps take the "inflection" path above, so we don't get
                // non-lilnear curves that lose rotation when chopped.
                REPORTER_ASSERT(r, SkScalarNearlyEqual(
                    SkMeasureNonInflectCubicRotation(chops), SK_ScalarPI));
                REPORTER_ASSERT(r, SkScalarNearlyEqual(
                    SkMeasureNonInflectCubicRotation(chops + 3), totalRotation - SK_ScalarPI));
            }
            REPORTER_ASSERT(r, !areCusps);
        } else {
            REPORTER_ASSERT(r, areCusps);
        }
    }
}

ConicHasCusp()

bool skgpu::tess::ConicHasCusp ( const SkPoint  p[3] )

inline

Definition at line 131 of file Tessellation.h.

                                             {
    SkVector a = p[1] - p[0];
    SkVector b = p[2] - p[1];
    // A conic of any class can only have a cusp if it is a degenerate flat line with a 180 degree
    // turnarund. To detect this, the beginning and ending tangents must be parallel
    // (a.cross(b) == 0) and pointing in opposite directions (a.dot(b) < 0).
    return a.cross(b) == 0 && a.dot(b) < 0;
}

DEF_TEST() [1/12]

skgpu::tess::DEF_TEST	(	CullTestTest	,
		reporter
	)

Definition at line 35 of file CullTestTest.cpp.

                                 {
    SkRandom rand;
    float l=10, t=2000, r=100, b=2064;
    SkRect viewportRect{l, t, r, b};
    float valuesL[4] = {l-20, l-10, l+10, l+20};
    float valuesT[4] = {t-20, t-10, t+10, t+20};
    float valuesR[4] = {r+20, r+10, r-10, r-20};
    float valuesB[4] = {b+20, b+10, b-10, b-20};
    for (SkMatrix m : gMatrices) {
        CullTest cullTest(viewportRect, m);
        SkMatrix inverse;
        SkAssertResult(m.invert(&inverse));
        for (const float* y : {valuesT, valuesB}) {
        for (const float* x : {valuesL, valuesR}) {
        for (int i = 0; i < 500; ++i) {
            int mask = rand.nextU();
            const SkPoint devPts[4] = {{x[(mask >>  0) & 3], y[(mask >>  2) & 3]},
                                       {x[(mask >>  4) & 3], y[(mask >>  6) & 3]},
                                       {x[(mask >>  8) & 3], y[(mask >> 10) & 3]},
                                       {x[(mask >> 12) & 3], y[(mask >> 14) & 3]}};
 
            SkPoint localPts[4];
            inverse.mapPoints(localPts, devPts, 4);
 
            REPORTER_ASSERT(reporter,
                            cullTest.isVisible(localPts[0]) ==
                            viewportRect.contains(devPts[0].fX, devPts[0].fY));
 
            {
                SkRect devBounds3;
                devBounds3.setBounds(devPts, 3);
                // Outset devBounds because SkRect::intersects returns false on empty, which is NOT
                // the behavior we want.
                devBounds3.outset(1e-3f, 1e-3f);
                REPORTER_ASSERT(reporter,
                        cullTest.areVisible3(localPts) == viewportRect.intersects(devBounds3));
            }
 
            {
                SkRect devBounds4;
                devBounds4.setBounds(devPts, 4);
                // Outset devBounds because SkRect::intersects returns false on empty, which is NOT
                // the behavior we want.
                devBounds4.outset(1e-3f, 1e-3f);
                REPORTER_ASSERT(reporter,
                        cullTest.areVisible4(localPts) == viewportRect.intersects(devBounds4));
            }
        }}}
    }
}

DEF_TEST() [2/12]

skgpu::tess::DEF_TEST	(	FindCubicConvex180Chops	,
		r
	)

Definition at line 76 of file FindCubicConvex180ChopsTest.cpp.

                                     {
    // Test all combinations of corners from the square [0,0,1,1]. This covers every cubic type as
    // well as a wide variety of special cases for cusps, lines, loops, and inflections.
    for (int i = 0; i < (1 << 8); ++i) {
        SkPoint p[4] = {SkPoint::Make((i>>0)&1, (i>>1)&1),
                        SkPoint::Make((i>>2)&1, (i>>3)&1),
                        SkPoint::Make((i>>4)&1, (i>>5)&1),
                        SkPoint::Make((i>>6)&1, (i>>7)&1)};
        check_cubic_convex_180(r, p);
    }
 
    {
        // This cubic has a convex-180 chop at T=1-"epsilon"
        static const uint32_t hexPts[] = {0x3ee0ac74, 0x3f1e061a, 0x3e0fc408, 0x3f457230,
                                          0x3f42ac7c, 0x3f70d76c, 0x3f4e6520, 0x3f6acafa};
        SkPoint p[4];
        memcpy(p, hexPts, sizeof(p));
        check_cubic_convex_180(r, p);
    }
 
    // Now test an exact quadratic.
    SkPoint quad[4] = {{0,0}, {2,2}, {4,2}, {6,0}};
    float T[2];
    bool areCusps;
    REPORTER_ASSERT(r, FindCubicConvex180Chops(quad, T, &areCusps) == 0);
 
    // Now test that cusps and near-cusps get flagged as cusps.
    SkPoint cusp[4] = {{0,0}, {1,1}, {1,0}, {0,1}};
    REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 1);
    REPORTER_ASSERT(r, areCusps == true);
 
    // Find the height of the right side of "cusp" at which the distance between its inflection
    // points is kEpsilon (in parametric space).
    constexpr static double kEpsilon = 1.0 / (1 << 11);
    constexpr static double kEpsilonSquared = kEpsilon * kEpsilon;
    double h = (1 - kEpsilonSquared) / (3 * kEpsilonSquared + 1);
    double dy = (1 - h) / 2;
    cusp[1].fY = (float)(1 - dy);
    cusp[2].fY = (float)(0 + dy);
    REPORTER_ASSERT(r, SkFindCubicInflections(cusp, T) == 2);
    REPORTER_ASSERT(r, SkScalarNearlyEqual(T[1] - T[0], (float)kEpsilon, (float)kEpsilonSquared));
 
    // Ensure two inflection points barely more than kEpsilon apart do not get flagged as cusps.
    cusp[1].fY = (float)(1 - 1.1 * dy);
    cusp[2].fY = (float)(0 + 1.1 * dy);
    REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 2);
    REPORTER_ASSERT(r, areCusps == false);
 
    // Ensure two inflection points barely less than kEpsilon apart do get flagged as cusps.
    cusp[1].fY = (float)(1 - .9 * dy);
    cusp[2].fY = (float)(0 + .9 * dy);
    REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 1);
    REPORTER_ASSERT(r, areCusps == true);
}

DEF_TEST() [3/12]

skgpu::tess::DEF_TEST	(	PreChopPathCurves	,
		reporter
	)

Definition at line 15 of file PreChopPathCurvesTest.cpp.

                                      {
    // These particular test cases can get stuck in infinite recursion due to limited fp32
    // precision. (Although they will not with the provided tessellationPrecision values; we had to
    // lower precision in order to avoid the "viewport size" assert in PreChopPathCurves.) Bump the
    // tessellationPreciion up to 4 and run these tests in order to verify our bail condition for
    // infinite recursion caused by bad fp32 precision. If the test completes, it passed.
    SkPath p = SkPath().moveTo(11.171727877046647f, -11.78621173228717f)
                       .quadTo(11.171727877046647f, -11.78621173228717f,
                               8.33583747124031f, 77.27177002747368f)
                       .cubicTo(8.33583747124031f, 77.27177002747368f,
                                8.33583747124031f, 77.27177002747368f,
                                11.171727877046647f, -11.78621173228717f)
                       .conicTo(11.171727877046647f, -11.78621173228717f,
                                8.33583747124031f, 77.27177002747368f,
                                1e-6f)
                       .conicTo(8.33583747124031f, 77.27177002747368f,
                                11.171727877046647f, -11.78621173228717f,
                                1e6f);
 
    SkMatrix m = SkMatrix::Scale(138.68622826903837f, 74192976757580.44189f);
    PreChopPathCurves(1/16.f, p, m, {1000, -74088852800000.f, 3000, -74088852700000.f});
 
    m = SkMatrix::Scale(138.68622826903837f, 74192976757580.44189f*.3f);
    PreChopPathCurves(.25f, p, m, {1000, -22226658140000.f, 3000, -22226658130000.f});
 
    m = SkMatrix::Scale(138.68622826903837f, 74192976757580.44189f/4);
    PreChopPathCurves(.25f, p, m, {1000, -18522213200000.f, 3000, -18522213100000.f});
}

DEF_TEST() [4/12]

skgpu::tess::DEF_TEST	(	wangs_formula_conic_matches_reference	,
		r
	)

Definition at line 492 of file WangsFormulaTest.cpp.

                                                   {
    SkRandom rand;
    for (int i = -10; i <= 10; ++i) {
        const float w = std::ldexp(1 + rand.nextF(), i);
        for_random_beziers(3, &rand, [&r, w](const SkPoint pts[]) {
            const float ref_nsegs = wangs_formula_conic_reference_impl(kPrecision, pts, w);
            const float nsegs = wangs_formula::conic(kPrecision, pts, w);
 
            // Because the Gr version may implement the math differently for performance,
            // allow different slack in the comparison based on the rough scale of the answer.
            const float cmpThresh = ref_nsegs * (1.f / (1 << 20));
            REPORTER_ASSERT(r, SkScalarNearlyEqual(ref_nsegs, nsegs, cmpThresh));
        });
    }
}

DEF_TEST() [5/12]

skgpu::tess::DEF_TEST	(	wangs_formula_conic_vectorXforms	,
		r
	)

Definition at line 509 of file WangsFormulaTest.cpp.

                                              {
    auto check_conic_with_transform = [&](const SkPoint* pts, float w, const SkMatrix& m) {
        SkPoint ptsXformed[3];
        m.mapPoints(ptsXformed, pts, 3);
        float expected = wangs_formula::conic(kPrecision, ptsXformed, w);
        float actual = wangs_formula::conic(kPrecision, pts, w, wangs_formula::VectorXform(m));
        REPORTER_ASSERT(r, SkScalarNearlyEqual(actual, expected));
    };
 
    SkRandom rand;
    for (int i = -10; i <= 10; ++i) {
        const float w = std::ldexp(1 + rand.nextF(), i);
        for_random_beziers(3, &rand, [&](const SkPoint pts[]) {
            check_conic_with_transform(pts, w, SkMatrix::I());
            check_conic_with_transform(
                    pts, w, SkMatrix::Scale(rand.nextRangeF(-10, 10), rand.nextRangeF(-10, 10)));
 
            // Random 2x2 matrix
            SkMatrix m;
            m.setScaleX(rand.nextRangeF(-10, 10));
            m.setSkewX(rand.nextRangeF(-10, 10));
            m.setSkewY(rand.nextRangeF(-10, 10));
            m.setScaleY(rand.nextRangeF(-10, 10));
            check_conic_with_transform(pts, w, m);
        });
    }
}

DEF_TEST() [6/12]

skgpu::tess::DEF_TEST	(	wangs_formula_conic_within_tol	,
		r
	)

Definition at line 430 of file WangsFormulaTest.cpp.

                                            {
    constexpr int maxExponent = 24;
 
    // Single-precision functions in SkConic/SkGeometry lose too much accuracy with
    // large-magnitude curves and large weights for this test to pass.
    using Sk2d = skvx::Vec<2, double>;
    const auto eval_conic = [](const SkPoint pts[3], float w, float t) -> Sk2d {
        const auto eval = [](Sk2d A, Sk2d B, Sk2d C, float t) -> Sk2d {
            return (A * t + B) * t + C;
        };
 
        const Sk2d p0 = {pts[0].fX, pts[0].fY};
        const Sk2d p1 = {pts[1].fX, pts[1].fY};
        const Sk2d p1w = p1 * w;
        const Sk2d p2 = {pts[2].fX, pts[2].fY};
        Sk2d numer = eval(p2 - p1w * 2 + p0, (p1w - p0) * 2, p0, t);
 
        Sk2d denomC = {1, 1};
        Sk2d denomB = {2 * (w - 1), 2 * (w - 1)};
        Sk2d denomA = {-2 * (w - 1), -2 * (w - 1)};
        Sk2d denom = eval(denomA, denomB, denomC, t);
        return numer / denom;
    };
 
    const auto dot = [](const Sk2d& a, const Sk2d& b) -> double {
        return a[0] * b[0] + a[1] * b[1];
    };
 
    const auto length = [](const Sk2d& p) -> double { return sqrt(p[0] * p[0] + p[1] * p[1]); };
 
    SkRandom rand;
    for (int i = -10; i <= 10; ++i) {
        const float w = std::ldexp(1 + rand.nextF(), i);
        for_random_beziers(
                3, &rand,
                [&](const SkPoint pts[]) {
                    const int nsegs = SkScalarCeilToInt(wangs_formula::conic(kPrecision, pts, w));
 
                    const float tdelta = 1.f / nsegs;
                    for (int j = 0; j < nsegs; ++j) {
                        const float tmin = j * tdelta, tmax = (j + 1) * tdelta,
                                    tmid = 0.5f * (tmin + tmax);
 
                        Sk2d p0, p1, p2;
                        p0 = eval_conic(pts, w, tmin);
                        p1 = eval_conic(pts, w, tmid);
                        p2 = eval_conic(pts, w, tmax);
 
                        // Get distance of p1 to baseline (p0, p2).
                        const Sk2d n = {p2[1] - p0[1], p0[0] - p2[0]};
                        SkASSERT(length(n) != 0);
                        const double d = std::abs(dot(p1 - p0, n)) / length(n);
 
                        // Check distance is within tolerance
                        REPORTER_ASSERT(r, d <= (1.0 / kPrecision) + SK_ScalarNearlyZero);
                    }
                },
                maxExponent);
    }
}

DEF_TEST() [7/12]

skgpu::tess::DEF_TEST	(	wangs_formula_log2	,
		r
	)

Definition at line 129 of file WangsFormulaTest.cpp.

                                {
    // Constructs a cubic such that the 'length' term in wang's formula == term.
    //
    //     f = sqrt(k * length(max(abs(p0 - p1*2 + p2),
    //                             abs(p1 - p2*2 + p3))));
    auto setupCubicLengthTerm = [](int seed, SkPoint pts[], float term) {
        memset(pts, 0, sizeof(SkPoint) * 4);
 
        SkPoint term2d = (seed & 1) ?
                SkPoint::Make(term, 0) : SkPoint::Make(.5f, std::sqrt(3)/2) * term;
        seed >>= 1;
 
        if (seed & 1) {
            term2d.fX = -term2d.fX;
        }
        seed >>= 1;
 
        if (seed & 1) {
            std::swap(term2d.fX, term2d.fY);
        }
        seed >>= 1;
 
        switch (seed % 4) {
            case 0:
                pts[0] = term2d;
                pts[3] = term2d * .75f;
                return;
            case 1:
                pts[1] = term2d * -.5f;
                return;
            case 2:
                pts[1] = term2d * -.5f;
                return;
            case 3:
                pts[3] = term2d;
                pts[0] = term2d * .75f;
                return;
        }
    };
 
    // Constructs a quadratic such that the 'length' term in wang's formula == term.
    //
    //     f = sqrt(k * length(p0 - p1*2 + p2));
    auto setupQuadraticLengthTerm = [](int seed, SkPoint pts[], float term) {
        memset(pts, 0, sizeof(SkPoint) * 3);
 
        SkPoint term2d = (seed & 1) ?
                SkPoint::Make(term, 0) : SkPoint::Make(.5f, std::sqrt(3)/2) * term;
        seed >>= 1;
 
        if (seed & 1) {
            term2d.fX = -term2d.fX;
        }
        seed >>= 1;
 
        if (seed & 1) {
            std::swap(term2d.fX, term2d.fY);
        }
        seed >>= 1;
 
        switch (seed % 3) {
            case 0:
                pts[0] = term2d;
                return;
            case 1:
                pts[1] = term2d * -.5f;
                return;
            case 2:
                pts[2] = term2d;
                return;
        }
    };
 
    // wangs_formula_cubic and wangs_formula_quadratic both use rsqrt instead of sqrt for speed.
    // Linearization is all approximate anyway, so as long as we are within ~1/2 tessellation
    // segment of the reference value we are good enough.
    constexpr static float kTessellationTolerance = 1/128.f;
 
    for (int level = 0; level < 30; ++level) {
        float epsilon = std::ldexp(SK_ScalarNearlyZero, level * 2);
        SkPoint pts[4];
 
        {
            // Test cubic boundaries.
            //     f = sqrt(k * length(max(abs(p0 - p1*2 + p2),
            //                             abs(p1 - p2*2 + p3))));
            constexpr static float k = (3 * 2) / (8 * (1.f/kPrecision));
            float x = std::ldexp(1, level * 2) / k;
            setupCubicLengthTerm(level << 1, pts, x - epsilon);
            float referenceValue = wangs_formula_cubic_reference_impl(kPrecision, pts);
            REPORTER_ASSERT(r, std::ceil(std::log2(referenceValue)) == level);
            float c = wangs_formula::cubic(kPrecision, pts);
            REPORTER_ASSERT(r, SkScalarNearlyEqual(c/referenceValue, 1, kTessellationTolerance));
            REPORTER_ASSERT(r, wangs_formula::cubic_log2(kPrecision, pts) == level);
            setupCubicLengthTerm(level << 1, pts, x + epsilon);
            referenceValue = wangs_formula_cubic_reference_impl(kPrecision, pts);
            REPORTER_ASSERT(r, std::ceil(std::log2(referenceValue)) == level + 1);
            c = wangs_formula::cubic(kPrecision, pts);
            REPORTER_ASSERT(r, SkScalarNearlyEqual(c/referenceValue, 1, kTessellationTolerance));
            REPORTER_ASSERT(r, wangs_formula::cubic_log2(kPrecision, pts) == level + 1);
        }
 
        {
            // Test quadratic boundaries.
            //     f = std::sqrt(k * Length(p0 - p1*2 + p2));
            constexpr static float k = 2 / (8 * (1.f/kPrecision));
            float x = std::ldexp(1, level * 2) / k;
            setupQuadraticLengthTerm(level << 1, pts, x - epsilon);
            float referenceValue = wangs_formula_quadratic_reference_impl(kPrecision, pts);
            REPORTER_ASSERT(r, std::ceil(std::log2(referenceValue)) == level);
            float q = wangs_formula::quadratic(kPrecision, pts);
            REPORTER_ASSERT(r, SkScalarNearlyEqual(q/referenceValue, 1, kTessellationTolerance));
            REPORTER_ASSERT(r, wangs_formula::quadratic_log2(kPrecision, pts) == level);
            setupQuadraticLengthTerm(level << 1, pts, x + epsilon);
            referenceValue = wangs_formula_quadratic_reference_impl(kPrecision, pts);
            REPORTER_ASSERT(r, std::ceil(std::log2(referenceValue)) == level+1);
            q = wangs_formula::quadratic(kPrecision, pts);
            REPORTER_ASSERT(r, SkScalarNearlyEqual(q/referenceValue, 1, kTessellationTolerance));
            REPORTER_ASSERT(r, wangs_formula::quadratic_log2(kPrecision, pts) == level + 1);
        }
    }
 
    auto check_cubic_log2 = [&](const SkPoint* pts) {
        float f = std::max(1.f, wangs_formula_cubic_reference_impl(kPrecision, pts));
        int f_log2 = wangs_formula::cubic_log2(kPrecision, pts);
        REPORTER_ASSERT(r, SkScalarCeilToInt(std::log2(f)) == f_log2);
        float c = std::max(1.f, wangs_formula::cubic(kPrecision, pts));
        REPORTER_ASSERT(r, SkScalarNearlyEqual(c/f, 1, kTessellationTolerance));
    };
 
    auto check_quadratic_log2 = [&](const SkPoint* pts) {
        float f = std::max(1.f, wangs_formula_quadratic_reference_impl(kPrecision, pts));
        int f_log2 = wangs_formula::quadratic_log2(kPrecision, pts);
        REPORTER_ASSERT(r, SkScalarCeilToInt(std::log2(f)) == f_log2);
        float q = std::max(1.f, wangs_formula::quadratic(kPrecision, pts));
        REPORTER_ASSERT(r, SkScalarNearlyEqual(q/f, 1, kTessellationTolerance));
    };
 
    SkRandom rand;
 
    for_random_matrices(&rand, [&](const SkMatrix& m) {
        SkPoint pts[4];
        m.mapPoints(pts, kSerp, 4);
        check_cubic_log2(pts);
 
        m.mapPoints(pts, kLoop, 4);
        check_cubic_log2(pts);
 
        m.mapPoints(pts, kQuad, 3);
        check_quadratic_log2(pts);
    });
 
    for_random_beziers(4, &rand, [&](const SkPoint pts[]) {
        check_cubic_log2(pts);
    });
 
    for_random_beziers(3, &rand, [&](const SkPoint pts[]) {
        check_quadratic_log2(pts);
    });
}

DEF_TEST() [8/12]

skgpu::tess::DEF_TEST	(	wangs_formula_nextlog2	,
		r
	)

Definition at line 537 of file WangsFormulaTest.cpp.

                                    {
    REPORTER_ASSERT(r, 0b0'00000000'111'1111111111'1111111111 == (1u << 23) - 1u);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(-std::numeric_limits<float>::infinity()) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(-std::numeric_limits<float>::max()) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(-1000.0f) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(-0.1f) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(-std::numeric_limits<float>::min()) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(-std::numeric_limits<float>::denorm_min()) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(0.0f) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(std::numeric_limits<float>::denorm_min()) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(std::numeric_limits<float>::min()) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(0.1f) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(1.0f) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(1.1f) == 1);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(2.0f) == 1);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(2.1f) == 2);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(3.0f) == 2);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(3.1f) == 2);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(4.0f) == 2);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(4.1f) == 3);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(5.0f) == 3);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(5.1f) == 3);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(6.0f) == 3);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(6.1f) == 3);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(7.0f) == 3);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(7.1f) == 3);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(8.0f) == 3);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(8.1f) == 4);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(9.0f) == 4);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(9.1f) == 4);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(std::numeric_limits<float>::max()) == 128);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(std::numeric_limits<float>::infinity()) == 128);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(std::numeric_limits<float>::quiet_NaN()) == 0);
    REPORTER_ASSERT(r, wangs_formula::nextlog2(-std::numeric_limits<float>::quiet_NaN()) == 0);
 
    for (int i = 0; i < 100; ++i) {
        float pow2 = std::ldexp(1, i);
        float epsilon = std::ldexp(SK_ScalarNearlyZero, i);
        REPORTER_ASSERT(r, wangs_formula::nextlog2(pow2) == i);
        REPORTER_ASSERT(r, wangs_formula::nextlog2(pow2 + epsilon) == i + 1);
        REPORTER_ASSERT(r, wangs_formula::nextlog2(pow2 - epsilon) == i);
    }
}

DEF_TEST() [9/12]

skgpu::tess::DEF_TEST	(	wangs_formula_quad_within_tol	,
		r
	)

Definition at line 363 of file WangsFormulaTest.cpp.

                                           {
    // Wang's formula and the quad math starts to lose precision with very large
    // coordinate values, so limit the magnitude a bit to prevent test failures
    // due to loss of precision.
    constexpr int maxExponent = 15;
    SkRandom rand;
    for_random_beziers(3, &rand, [&r](const SkPoint pts[]) {
        const int nsegs = static_cast<int>(
                std::ceil(wangs_formula_quadratic_reference_impl(kPrecision, pts)));
 
        const float tdelta = 1.f / nsegs;
        for (int j = 0; j < nsegs; ++j) {
            const float tmin = j * tdelta, tmax = (j + 1) * tdelta;
 
            // Get section of quad in [tmin,tmax]
            const SkPoint* sectionPts;
            SkPoint tmp0[5];
            SkPoint tmp1[5];
            if (tmin == 0) {
                if (tmax == 1) {
                    sectionPts = pts;
                } else {
                    SkChopQuadAt(pts, tmp0, tmax);
                    sectionPts = tmp0;
                }
            } else {
                SkChopQuadAt(pts, tmp0, tmin);
                if (tmax == 1) {
                    sectionPts = tmp0 + 2;
                } else {
                    SkChopQuadAt(tmp0 + 2, tmp1, (tmax - tmin) / (1 - tmin));
                    sectionPts = tmp1;
                }
            }
 
            // For quads, max distance from baseline is always at t=0.5.
            SkPoint p;
            p = SkEvalQuadAt(sectionPts, 0.5f);
 
            // Get distance of p to baseline
            const SkPoint n = {sectionPts[2].fY - sectionPts[0].fY,
                               sectionPts[0].fX - sectionPts[2].fX};
            const float d = std::abs((p - sectionPts[0]).dot(n)) / n.length();
 
            // Check distance is within specified tolerance
            REPORTER_ASSERT(r, d <= (1.f / kPrecision) + SK_ScalarNearlyZero);
        }
    }, maxExponent);
}

DEF_TEST() [10/12]

skgpu::tess::DEF_TEST	(	wangs_formula_rational_quad_reduces	,
		r
	)

Definition at line 415 of file WangsFormulaTest.cpp.

                                                 {
    constexpr static float kTessellationTolerance = 1 / 128.f;
 
    SkRandom rand;
    for (int i = 0; i < 100; ++i) {
        for_random_beziers(3, &rand, [&r](const SkPoint pts[]) {
            const float rational_nsegs = wangs_formula::conic(kPrecision, pts, 1.f);
            const float integral_nsegs = wangs_formula_quadratic_reference_impl(kPrecision, pts);
            REPORTER_ASSERT(
                    r, SkScalarNearlyEqual(rational_nsegs, integral_nsegs, kTessellationTolerance));
        });
    }
}

DEF_TEST() [11/12]

skgpu::tess::DEF_TEST	(	wangs_formula_vectorXforms	,
		r
	)

Definition at line 291 of file WangsFormulaTest.cpp.

                                        {
    auto check_cubic_log2_with_transform = [&](const SkPoint* pts, const SkMatrix& m){
        SkPoint ptsXformed[4];
        m.mapPoints(ptsXformed, pts, 4);
        int expected = wangs_formula::cubic_log2(kPrecision, ptsXformed);
        int actual = wangs_formula::cubic_log2(kPrecision, pts, wangs_formula::VectorXform(m));
        REPORTER_ASSERT(r, actual == expected);
    };
 
    auto check_quadratic_log2_with_transform = [&](const SkPoint* pts, const SkMatrix& m) {
        SkPoint ptsXformed[3];
        m.mapPoints(ptsXformed, pts, 3);
        int expected = wangs_formula::quadratic_log2(kPrecision, ptsXformed);
        int actual = wangs_formula::quadratic_log2(kPrecision, pts, wangs_formula::VectorXform(m));
        REPORTER_ASSERT(r, actual == expected);
    };
 
    SkRandom rand;
 
    for_random_matrices(&rand, [&](const SkMatrix& m) {
        check_cubic_log2_with_transform(kSerp, m);
        check_cubic_log2_with_transform(kLoop, m);
        check_quadratic_log2_with_transform(kQuad, m);
 
        for_random_beziers(4, &rand, [&](const SkPoint pts[]) {
            check_cubic_log2_with_transform(pts, m);
        });
 
        for_random_beziers(3, &rand, [&](const SkPoint pts[]) {
            check_quadratic_log2_with_transform(pts, m);
        });
    });
}

DEF_TEST() [12/12]

skgpu::tess::DEF_TEST	(	wangs_formula_worst_case_cubic	,
		r
	)

Definition at line 325 of file WangsFormulaTest.cpp.

                                            {
    {
        SkPoint worstP[] = {{0,0}, {100,100}, {0,0}, {0,0}};
        REPORTER_ASSERT(r, wangs_formula::worst_case_cubic(kPrecision, 100, 100) ==
                           wangs_formula_cubic_reference_impl(kPrecision, worstP));
        REPORTER_ASSERT(r, wangs_formula::worst_case_cubic_log2(kPrecision, 100, 100) ==
                           wangs_formula::cubic_log2(kPrecision, worstP));
    }
    {
        SkPoint worstP[] = {{100,100}, {100,100}, {200,200}, {100,100}};
        REPORTER_ASSERT(r, wangs_formula::worst_case_cubic(kPrecision, 100, 100) ==
                           wangs_formula_cubic_reference_impl(kPrecision, worstP));
        REPORTER_ASSERT(r, wangs_formula::worst_case_cubic_log2(kPrecision, 100, 100) ==
                           wangs_formula::cubic_log2(kPrecision, worstP));
    }
    auto check_worst_case_cubic = [&](const SkPoint* pts) {
        SkRect bbox;
        bbox.setBoundsNoCheck(pts, 4);
        float worst = wangs_formula::worst_case_cubic(kPrecision, bbox.width(), bbox.height());
        int worst_log2 = wangs_formula::worst_case_cubic_log2(kPrecision, bbox.width(),
                                                               bbox.height());
        float actual = wangs_formula_cubic_reference_impl(kPrecision, pts);
        REPORTER_ASSERT(r, worst >= actual);
        REPORTER_ASSERT(r, std::ceil(std::log2(std::max(1.f, worst))) == worst_log2);
    };
    SkRandom rand;
    for (int i = 0; i < 100; ++i) {
        for_random_beziers(4, &rand, [&](const SkPoint pts[]) {
            check_worst_case_cubic(pts);
        });
    }
    // Make sure overflow saturates at infinity (not NaN).
    constexpr static float inf = std::numeric_limits<float>::infinity();
    REPORTER_ASSERT(r, wangs_formula::worst_case_cubic_p4(kPrecision, inf, inf) == inf);
    REPORTER_ASSERT(r, wangs_formula::worst_case_cubic(kPrecision, inf, inf) == inf);
}

FindCubicConvex180Chops()

int skgpu::tess::FindCubicConvex180Chops	(	const SkPoint	pts[],
		float	T[2],
		bool *	areCusps
	)

Definition at line 205 of file Tessellation.cpp.

                                                                             {
    SkASSERT(pts);
    SkASSERT(T);
    SkASSERT(areCusps);
 
    // If a chop falls within a distance of "kEpsilon" from 0 or 1, throw it out. Tangents become
    // unstable when we chop too close to the boundary. This works out because the tessellation
    // shaders don't allow more than 2^10 parametric segments, and they snap the beginning and
    // ending edges at 0 and 1. So if we overstep an inflection or point of 180-degree rotation by a
    // fraction of a tessellation segment, it just gets snapped.
    constexpr static float kEpsilon = 1.f / (1 << 11);
    // Floating-point representation of "1 - 2*kEpsilon".
    constexpr static uint32_t kIEEE_one_minus_2_epsilon = (127 << 23) - 2 * (1 << (24 - 11));
    // Unfortunately we don't have a way to static_assert this, but we can runtime assert that the
    // kIEEE_one_minus_2_epsilon bits are correct.
    SkASSERT(sk_bit_cast<float>(kIEEE_one_minus_2_epsilon) == 1 - 2*kEpsilon);
 
    float2 p0 = sk_bit_cast<float2>(pts[0]);
    float2 p1 = sk_bit_cast<float2>(pts[1]);
    float2 p2 = sk_bit_cast<float2>(pts[2]);
    float2 p3 = sk_bit_cast<float2>(pts[3]);
 
    // Find the cubic's power basis coefficients. These define the bezier curve as:
    //
    //                                    |T^3|
    //     Cubic(T) = x,y = |A  3B  3C| * |T^2| + P0
    //                      |.   .   .|   |T  |
    //
    // And the tangent direction (scaled by a uniform 1/3) will be:
    //
    //                                                 |T^2|
    //     Tangent_Direction(T) = dx,dy = |A  2B  C| * |T  |
    //                                    |.   .  .|   |1  |
    //
    float2 C = p1 - p0;
    float2 D = p2 - p1;
    float2 E = p3 - p0;
    float2 B = D - C;
    float2 A = -3*D + E;
 
    // Now find the cubic's inflection function. There are inflections where F' x F'' == 0.
    // We formulate this as a quadratic equation:  F' x F'' == aT^2 + bT + c == 0.
    // See: https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
    // NOTE: We only need the roots, so a uniform scale factor does not affect the solution.
    float a = cross(A,B);
    float b = cross(A,C);
    float c = cross(B,C);
    float b_over_minus_2 = -.5f * b;
    float discr_over_4 = b_over_minus_2*b_over_minus_2 - a*c;
 
    // If -cuspThreshold <= discr_over_4 <= cuspThreshold, it means the two roots are within
    // kEpsilon of one another (in parametric space). This is close enough for our purposes to
    // consider them a single cusp.
    float cuspThreshold = a * (kEpsilon/2);
    cuspThreshold *= cuspThreshold;
 
    if (discr_over_4 < -cuspThreshold) {
        // The curve does not inflect or cusp. This means it might rotate more than 180 degrees
        // instead. Chop were rotation == 180 deg. (This is the 2nd root where the tangent is
        // parallel to tan0.)
        //
        //      Tangent_Direction(T) x tan0 == 0
        //      (AT^2 x tan0) + (2BT x tan0) + (C x tan0) == 0
        //      (A x C)T^2 + (2B x C)T + (C x C) == 0  [[because tan0 == P1 - P0 == C]]
        //      bT^2 + 2cT + 0 == 0  [[because A x C == b, B x C == c]]
        //      T = [0, -2c/b]
        //
        // NOTE: if C == 0, then C != tan0. But this is fine because the curve is definitely
        // convex-180 if any points are colocated, and T[0] will equal NaN which returns 0 chops.
        *areCusps = false;
        float root = sk_ieee_float_divide(c, b_over_minus_2);
        // Is "root" inside the range [kEpsilon, 1 - kEpsilon)?
        if (sk_bit_cast<uint32_t>(root - kEpsilon) < kIEEE_one_minus_2_epsilon) {
            T[0] = root;
            return 1;
        }
        return 0;
    }
 
    *areCusps = (discr_over_4 <= cuspThreshold);
    if (*areCusps) {
        // The two roots are close enough that we can consider them a single cusp.
        if (a != 0 || b_over_minus_2 != 0 || c != 0) {
            // Pick the average of both roots.
            float root = sk_ieee_float_divide(b_over_minus_2, a);
            // Is "root" inside the range [kEpsilon, 1 - kEpsilon)?
            if (sk_bit_cast<uint32_t>(root - kEpsilon) < kIEEE_one_minus_2_epsilon) {
                T[0] = root;
                return 1;
            }
            return 0;
        }
 
        // The curve is a flat line. The standard inflection function doesn't detect cusps from flat
        // lines. Find cusps by searching instead for points where the tangent is perpendicular to
        // tan0. This will find any cusp point.
        //
        //     dot(tan0, Tangent_Direction(T)) == 0
        //
        //                         |T^2|
        //     tan0 * |A  2B  C| * |T  | == 0
        //            |.   .  .|   |1  |
        //
        float2 tan0 = skvx::if_then_else(C != 0, C, p2 - p0);
        a = dot(tan0, A);
        b_over_minus_2 = -dot(tan0, B);
        c = dot(tan0, C);
        discr_over_4 = std::max(b_over_minus_2*b_over_minus_2 - a*c, 0.f);
    }
 
    // Solve our quadratic equation to find where to chop. See the quadratic formula from
    // Numerical Recipes in C.
    float q = sqrtf(discr_over_4);
    q = copysignf(q, b_over_minus_2);
    q = q + b_over_minus_2;
    float2 roots = float2{q,c} / float2{a,q};
 
    auto inside = (roots > kEpsilon) & (roots < (1 - kEpsilon));
    if (inside[0]) {
        if (inside[1] && roots[0] != roots[1]) {
            if (roots[0] > roots[1]) {
                roots = skvx::shuffle<1,0>(roots);  // Sort.
            }
            roots.store(T);
            return 2;
        }
        T[0] = roots[0];
        return 1;
    }
    if (inside[1]) {
        T[0] = roots[1];
        return 1;
    }
    return 0;
}

for_random_beziers()

static void skgpu::tess::for_random_beziers ( int  numPoints, SkRandom *  rand, const std::function< void(const SkPoint[])> &  f, int  maxExponent = 30  )

static

Definition at line 115 of file WangsFormulaTest.cpp.

                                                     {
    SkASSERT(numPoints <= 4);
    SkPoint pts[4];
    for (int i = -10; i <= maxExponent; ++i) {
        for (int j = 0; j < numPoints; ++j) {
            pts[j].set(std::ldexp(1 + rand->nextF(), i), std::ldexp(1 + rand->nextF(), i));
        }
        f(pts);
    }
}

for_random_matrices()

static void skgpu::tess::for_random_matrices ( SkRandom *  rand, const std::function< void(const SkMatrix &)> &  f  )

static

Definition at line 93 of file WangsFormulaTest.cpp.

                                                                                             {
    SkMatrix m;
    m.setIdentity();
    f(m);
 
    for (int i = -10; i <= 30; ++i) {
        for (int j = -10; j <= 30; ++j) {
            m.setScaleX(std::ldexp(1 + rand->nextF(), i));
            m.setSkewX(0);
            m.setSkewY(0);
            m.setScaleY(std::ldexp(1 + rand->nextF(), j));
            f(m);
 
            m.setScaleX(std::ldexp(1 + rand->nextF(), i));
            m.setSkewX(std::ldexp(1 + rand->nextF(), (j + i) / 2));
            m.setSkewY(std::ldexp(1 + rand->nextF(), (j + i) / 2));
            m.setScaleY(std::ldexp(1 + rand->nextF(), j));
            f(m);
        }
    }
}

GetJoinType()

float skgpu::tess::GetJoinType ( const SkStrokeRec &  stroke )

inline

Definition at line 146 of file Tessellation.h.

                                                    {
    switch (stroke.getJoin()) {
        case SkPaint::kRound_Join: return -1;
        case SkPaint::kBevel_Join: return 0;
        case SkPaint::kMiter_Join: SkASSERT(stroke.getMiter() >= 0); return stroke.getMiter();
    }
    SkUNREACHABLE;
}

is_linear() [1/2]

static bool skgpu::tess::is_linear ( const SkPoint  p[4] )

static

Definition at line 25 of file FindCubicConvex180ChopsTest.cpp.

                                          {
    return is_linear(p[0],p[1],p[2]) && is_linear(p[0],p[2],p[3]) && is_linear(p[1],p[2],p[3]);
}

is_linear() [2/2]

static bool skgpu::tess::is_linear ( SkPoint  p0, SkPoint  p1, SkPoint  p2  )

static

Definition at line 21 of file FindCubicConvex180ChopsTest.cpp.

                                                          {
    return SkScalarNearlyZero((p0 - p1).cross(p2 - p1));
}

NumCurveTrianglesAtResolveLevel()

static constexpr int skgpu::tess::NumCurveTrianglesAtResolveLevel ( int  resolveLevel )

staticconstexpr

Definition at line 66 of file Tessellation.h.

                                                                       {
    // resolveLevel=0 -> 0 line segments -> 0 triangles
    // resolveLevel=1 -> 2 line segments -> 1 triangle
    // resolveLevel=2 -> 4 line segments -> 3 triangles
    // resolveLevel=3 -> 8 line segments -> 7 triangles
    // ...
    return (1 << resolveLevel) - 1;
}

NumFixedEdgesInJoin() [1/2]

constexpr int skgpu::tess::NumFixedEdgesInJoin ( const StrokeParams &  strokeParams )

constexpr

Definition at line 202 of file Tessellation.h.

                                                                    {
    // The caller is responsible for counting the variable number of segments for round joins.
    return strokeParams.fJoinType > 0.f ? /* miter */ 4 : /* round or bevel */ 3;
}

NumFixedEdgesInJoin() [2/2]

constexpr int skgpu::tess::NumFixedEdgesInJoin ( SkPaint::Join  joinType )

constexpr

Definition at line 189 of file Tessellation.h.

                                                        {
    switch (joinType) {
        case SkPaint::kMiter_Join:
            return 4;
        case SkPaint::kRound_Join:
            // The caller is responsible for counting the variable number of middle, radial
            // segments on round joins.
            [[fallthrough]];
        case SkPaint::kBevel_Join:
            return 3;
    }
    SkUNREACHABLE;
}

operator<<()

template<PatchAttribs A, typename T , bool Required, bool Optional>

VertexWriter & skgpu::tess::operator<<	(	VertexWriter &	w,
		const AttribValue< A, T, Required, Optional > &	v
	)

Definition at line 168 of file PatchWriter.h.

                                                                                          {
    if constexpr (Required) {
        w << v.fV; // always write
    } else if constexpr (Optional) {
        if (std::get<1>(v.fV)) {
            w << std::get<0>(v.fV); // write if enabled
        }
    } // else never write
    return w;
}

PatchAttribsStride()

constexpr size_t skgpu::tess::PatchAttribsStride ( PatchAttribs  attribs )

constexpr

Definition at line 103 of file Tessellation.h.

                                                          {
    return (attribs & PatchAttribs::kJoinControlPoint ? sizeof(float) * 2 : 0) +
           (attribs & PatchAttribs::kFanPoint ? sizeof(float) * 2 : 0) +
           (attribs & PatchAttribs::kStrokeParams ? sizeof(float) * 2 : 0) +
           (attribs & PatchAttribs::kColor
                    ? (attribs & PatchAttribs::kWideColorIfEnabled ? sizeof(float)
                                                                   : sizeof(uint8_t)) * 4 : 0) +
           (attribs & PatchAttribs::kPaintDepth ? sizeof(float) : 0) +
           (attribs & PatchAttribs::kExplicitCurveType ? sizeof(float) : 0) +
           (attribs & PatchAttribs::kSsboIndex ? (sizeof(int)) : 0);
}

PatchStride()

constexpr size_t skgpu::tess::PatchStride ( PatchAttribs  attribs )

constexpr

Definition at line 114 of file Tessellation.h.

                                                   {
    return 4*sizeof(SkPoint) + PatchAttribsStride(attribs);
}

PreChopPathCurves()

SkPath skgpu::tess::PreChopPathCurves	(	float	tessellationPrecision,
		const SkPath &	path,
		const SkMatrix &	matrix,
		const SkRect &	viewport
	)

Definition at line 164 of file Tessellation.cpp.

                                                 {
    // If the viewport is exceptionally large, we could end up blowing out memory with an unbounded
    // number of of chops. Therefore, we require that the viewport is manageable enough that a fully
    // contained curve can be tessellated in kMaxTessellationSegmentsPerCurve or fewer. (Any larger
    // and that amount of pixels wouldn't fit in memory anyway.)
    SkASSERT(wangs_formula::worst_case_cubic(
                     tessellationPrecision,
                     viewport.width(),
                     viewport.height()) <= kMaxSegmentsPerCurve);
    PathChopper chopper(tessellationPrecision, matrix, viewport);
    for (auto [verb, p, w] : SkPathPriv::Iterate(path)) {
        switch (verb) {
            case SkPathVerb::kMove:
                chopper.moveTo(p[0]);
                break;
            case SkPathVerb::kLine:
                chopper.lineTo(p);
                break;
            case SkPathVerb::kQuad:
                chopper.quadTo(p);
                break;
            case SkPathVerb::kConic:
                chopper.conicTo(p, *w);
                break;
            case SkPathVerb::kCubic:
                chopper.cubicTo(p);
                break;
            case SkPathVerb::kClose:
                chopper.close();
                break;
        }
    }
    // Must preserve the input path's fill type (see crbug.com/1472747)
    SkPath chopped = chopper.path();
    chopped.setFillType(path.getFillType());
    return chopped;
}

StrokesHaveEqualParams()

bool skgpu::tess::StrokesHaveEqualParams ( const SkStrokeRec &  a, const SkStrokeRec &  b  )

inline

Definition at line 171 of file Tessellation.h.

                                                                               {
    return a.getWidth() == b.getWidth() && a.getJoin() == b.getJoin() &&
            (a.getJoin() != SkPaint::kMiter_Join || a.getMiter() == b.getMiter());
}

wangs_formula_conic_reference_impl()

static float skgpu::tess::wangs_formula_conic_reference_impl ( float  precision, const SkPoint  P[3], const float  w  )

static

Definition at line 56 of file WangsFormulaTest.cpp.

                                                               {
    // Compute center of bounding box in projected space
    float min_x = P[0].fX, max_x = min_x,
          min_y = P[0].fY, max_y = min_y;
    for (int i = 1; i < 3; i++) {
        min_x = std::min(min_x, P[i].fX);
        max_x = std::max(max_x, P[i].fX);
        min_y = std::min(min_y, P[i].fY);
        max_y = std::max(max_y, P[i].fY);
    }
    const SkPoint C = SkPoint::Make(0.5f * (min_x + max_x), 0.5f * (min_y + max_y));
 
    // Translate control points and compute max length
    SkPoint tP[3] = {P[0] - C, P[1] - C, P[2] - C};
    float max_len = 0;
    for (int i = 0; i < 3; i++) {
        max_len = std::max(max_len, tP[i].length());
    }
    SkASSERT(max_len > 0);
 
    // Compute delta = parametric step size of linearization
    const float eps = 1 / precision;
    const float r_minus_eps = std::max(0.f, max_len - eps);
    const float min_w = std::min(w, 1.f);
    const float numer = 4 * min_w * eps;
    const float denom =
            (tP[2] - tP[1] * 2 * w + tP[0]).length() + r_minus_eps * std::abs(1 - 2 * w + 1);
    const float delta = sqrtf(numer / denom);
 
    // Return corresponding num segments in the interval [tmin,tmax]
    constexpr float tmin = 0, tmax = 1;
    SkASSERT(delta > 0);
    return (tmax - tmin) / delta;
}

wangs_formula_cubic_reference_impl()

static float skgpu::tess::wangs_formula_cubic_reference_impl ( float  precision, const SkPoint  p[4]  )

static

Definition at line 42 of file WangsFormulaTest.cpp.

                                                                                     {
    float k = (3 * 2) / 8.f * precision;
    return sqrtf(k * std::max((p[0] - p[1]*2 + p[2]).length(),
                              (p[1] - p[2]*2 + p[3]).length()));
}

wangs_formula_quadratic_reference_impl()

static float skgpu::tess::wangs_formula_quadratic_reference_impl ( float  precision, const SkPoint  p[3]  )

static

Definition at line 37 of file WangsFormulaTest.cpp.

                                                                                         {
    float k = (2 * 1) / 8.f * precision;
    return sqrtf(k * (p[0] - p[1]*2 + p[2]).length());
}

Variable Documentation

gMatrices

const SkMatrix skgpu::tess::gMatrices[]

Initial value:

= {
    SkMatrix::I(),
    SkMatrix::Translate(25, -1000),
    SkMatrix::Scale(.5f, 1000.1f),
    SkMatrix::MakeAll(1000.1f, .0f,  -100,
                         0.0f, .5f, -3000,
                         0.0f, .0f,     1),
    SkMatrix::MakeAll(0, 1, 0,
                      1, 0, 0,
                      0, 0, 1),
    SkMatrix::MakeAll(    2, 7.0f, -100,
                      -8000,  .5f, 2000,
                          0,  .0f,    1),
}

Definition at line 20 of file CullTestTest.cpp.

                             {
    SkMatrix::I(),
    SkMatrix::Translate(25, -1000),
    SkMatrix::Scale(.5f, 1000.1f),
    SkMatrix::MakeAll(1000.1f, .0f,  -100,
                         0.0f, .5f, -3000,
                         0.0f, .0f,     1),
    SkMatrix::MakeAll(0, 1, 0,
                      1, 0, 0,
                      0, 0, 1),
    SkMatrix::MakeAll(    2, 7.0f, -100,
                      -8000,  .5f, 2000,
                          0,  .0f,    1),
};

kConicCurveType

constexpr float skgpu::tess::kConicCurveType = 1

staticconstexpr

Definition at line 98 of file Tessellation.h.

kCubicCurveType

constexpr float skgpu::tess::kCubicCurveType = 0

staticconstexpr

Definition at line 97 of file Tessellation.h.

kLoop

const SkPoint skgpu::tess::kLoop[4]

Initial value:

= {
        {635.625f, 614.687f}, {171.625f, 236.188f}, {1064.62f, 135.688f}, {516.625f, 570.187f}}

Definition at line 31 of file WangsFormulaTest.cpp.

                         {
        {635.625f, 614.687f}, {171.625f, 236.188f}, {1064.62f, 135.688f}, {516.625f, 570.187f}};

kMaxParametricSegments

constexpr int skgpu::tess::kMaxParametricSegments = 1 << kMaxResolveLevel

staticconstexpr

Definition at line 41 of file Tessellation.h.

kMaxParametricSegments_p2

constexpr int skgpu::tess::kMaxParametricSegments_p2 = kMaxParametricSegments * kMaxParametricSegments

staticconstexpr

Definition at line 42 of file Tessellation.h.

kMaxParametricSegments_p4

constexpr int skgpu::tess::kMaxParametricSegments_p4

staticconstexpr

Initial value:

= kMaxParametricSegments_p2 *
                                                 kMaxParametricSegments_p2

Definition at line 43 of file Tessellation.h.

kMaxResolveLevel

constexpr int skgpu::tess::kMaxResolveLevel = 5

staticconstexpr

Definition at line 34 of file Tessellation.h.

kMaxSegmentsPerCurve

constexpr float skgpu::tess::kMaxSegmentsPerCurve = 1024

staticconstexpr

Definition at line 51 of file Tessellation.h.

kMaxSegmentsPerCurve_p2

constexpr float skgpu::tess::kMaxSegmentsPerCurve_p2 = kMaxSegmentsPerCurve * kMaxSegmentsPerCurve

staticconstexpr

Definition at line 52 of file Tessellation.h.

kMaxSegmentsPerCurve_p4

constexpr float skgpu::tess::kMaxSegmentsPerCurve_p4 = kMaxSegmentsPerCurve_p2 * kMaxSegmentsPerCurve_p2

staticconstexpr

Definition at line 53 of file Tessellation.h.

kPrecision

constexpr float skgpu::tess::kPrecision = 4

staticconstexpr

Definition at line 29 of file Tessellation.h.

kQuad

const SkPoint skgpu::tess::kQuad[4]

Initial value:

= {
        {460.625f, 557.187f}, {707.121f, 209.688f}, {779.628f, 577.687f}}

Definition at line 34 of file WangsFormulaTest.cpp.

                         {
        {460.625f, 557.187f}, {707.121f, 209.688f}, {779.628f, 577.687f}};

kSerp

const SkPoint skgpu::tess::kSerp[4]

Initial value:

= {
        {285.625f, 499.687f}, {411.625f, 808.188f}, {1064.62f, 135.688f}, {1042.63f, 585.187f}}

Definition at line 28 of file WangsFormulaTest.cpp.

                         {
        {285.625f, 499.687f}, {411.625f, 808.188f}, {1064.62f, 135.688f}, {1042.63f, 585.187f}};

kTriangularConicCurveType

constexpr float skgpu::tess::kTriangularConicCurveType = 2

staticconstexpr

Definition at line 99 of file Tessellation.h.