blob: 7f9b195ef9848f0b624528a5c6d7b9e7ebb5d492 [file] [edit]
/*
* Copyright 2026 Google LLC
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef skgpu_graphite_sparse_strips_FlattenUtils_DEFINED
#define skgpu_graphite_sparse_strips_FlattenUtils_DEFINED
#include "include/core/SkPoint.h"
#include "include/private/SkAttributes.h"
#include "src/core/SkVx.h"
#include "src/gpu/graphite/sparse_strips/Flatten.h"
#include "src/gpu/tessellate/WangsFormula.h"
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <type_traits>
/*
* Curve helpers shared by the flattening passes of sparse strips. They are inline and header-only,
* so that each pass compiles them into its own loops, and they use Flatten's limits (see
* Flatten.h). Error tolerances are parameters, so that each pass can budget its own.
*/
namespace skgpu::graphite::flatten_utils {
/*
* Levien's approximations of the integral that maps a quadratic, projected onto the parabola
* y = x^2, into uniform arc-length space, and of its inverse (see Flatten.h). The scalar versions
* compute in the precision of their argument.
*/
template <typename T, std::enable_if_t<std::is_floating_point_v<T>, bool> = true>
SK_ALWAYS_INLINE T approx_parabola_integral(T x) {
constexpr T kD = static_cast<T>(0.67);
constexpr T kDPow4 = kD * kD * kD * kD;
return x /
(static_cast<T>(1) - kD + std::sqrt(std::sqrt(kDPow4 + static_cast<T>(0.25) * x * x)));
}
template <typename T, std::enable_if_t<std::is_floating_point_v<T>, bool> = true>
SK_ALWAYS_INLINE T approx_parabola_inv_integral(T x) {
constexpr T kB = static_cast<T>(0.39);
return x * (static_cast<T>(1) - kB + std::sqrt(kB * kB + static_cast<T>(0.25) * x * x));
}
template <int N>
SK_ALWAYS_INLINE skvx::Vec<N, float> approx_parabola_integral(skvx::Vec<N, float> x) {
constexpr float kD = 0.67f;
constexpr float kDPow4 = kD * kD * kD * kD;
skvx::Vec<N, float> x2 = x * x;
skvx::Vec<N, float> temp = skvx::sqrt(
skvx::sqrt(skvx::fma(x2, skvx::Vec<N, float>(0.25f), skvx::Vec<N, float>(kDPow4))));
skvx::Vec<N, float> denom = temp + (1.0f - kD);
return x / denom;
}
template <int N>
SK_ALWAYS_INLINE skvx::Vec<N, float> approx_parabola_inv_integral(skvx::Vec<N, float> x) {
constexpr float kB = 0.39f;
constexpr float kOneMinusB = 1.0f - kB;
constexpr float kB2 = kB * kB;
skvx::Vec<N, float> x2 = x * x;
skvx::Vec<N, float> temp =
skvx::sqrt(skvx::fma(x2, skvx::Vec<N, float>(0.25f), skvx::Vec<N, float>(kB2)));
skvx::Vec<N, float> factor = temp + kOneMinusB;
return x * factor;
}
/*
* Determining the number of quads from a cubic:
*
* 1. Error Budgeting:
* Flattening cubics happens in two steps: Cubic -> Quads, then Quads -> Lines. If the first step
* uses the full visual tolerance, the final lines will look jagged (e.g., Flatten's
* kCubicAccuracy allocates only 10% (kCubicErrTolerance) of the total allowed pixel error to the
* Cubic -> Quads step, saving 90% (kQuadToLineTolFromCubic) for the final lines).
*
* 2. Wang's Formula and the Vector Error (errV):
* Wang's formula gives the minimum number of evenly spaced (in parametric space) line segments
* that a bezier curve of degree "n" must be chopped into to guarantee all lines stay within a
* distance of "1/precision" pixels from the true curve:
*
* maxLength = max([length(p[i+2] - 2p[i+1] + p[i]) for (0 <= i <= n-2)])
* numParametricSegments = sqrt(maxLength * precision * n*(n - 1)/8)
*
* (Goldman, Ron. (2003). 5.6.3 Wang's Formula. "Pyramid Algorithms: A Dynamic Programming
* Approach to Curves and Surfaces for Geometric Modeling". Morgan Kaufmann Publishers.)
*
* Since we are flattening a cubic to a *quadratic*, we shift the math up one degree and evaluate
* the third derivative instead: (3*P2 - P3) - (3*P1 - P0). If this evaluates to zero, the second
* derivative is constant, meaning the curve is a perfect parabola. We use this expression 'errV'
* as a measure of how much the cubic "bulges" away from an ideal quadratic shape.
*
* 3. Error Quantization and Lookup Table
* From Wang's formula, the maximum geometric error of the un-chopped cubic is
* ||errV|| / (12*sqrt(3)). By Taylor's theorem, if we chop the curve into n segments, the
* approximation error shrinks cubically (Base Error / n^3). Thus, to satisfy the desired
* tolerance, we must find the minimum n where:
*
* ((||errV|| / (12*sqrt(3)) / n^3) <= errTolerance.
*
* To avoid calling sqrt, we square the equation: (12*sqrt(3))^2 = 432 (see
* inv_cubic_err_threshold()). Correspondingly, (n^3)^2 = n^6, so errDiv scales at n^6. To avoid
* calculating 6th roots, and because we know we can only have an integer number of
* subdivisions, we precompute a lookup table (kPowSixLut) of 6th powers to find the required
* number of subdivisions.
*
* 4. Subdivision limit:
* As a guard against pathological inputs, and to avoid dynamic memory allocation, we bound the
* maximum number of quads that can be produced by a cubic. If errDiv exceeds the table, the
* function returns Flatten::kMaxQuadsFromCubic.
*/
// The 'invErrThreshold' of estimate_num_quads_from_cubic() for an error tolerance in pixels:
// 1 / ((12 * sqrt(3))^2 * errTolerance^2), inverted to avoid division.
template <typename T> constexpr T inv_cubic_err_threshold(T errTolerance) {
return static_cast<T>(1) / (static_cast<T>(432) * errTolerance * errTolerance);
}
template <typename T>
SK_ALWAYS_INLINE uint32_t estimate_num_quads_from_cubic(const SkPoint pts[4], T invErrThreshold) {
// A cubic is a perfect quadratic if (3*P1 - P0) == (3*P2 - P3)
SkPoint leftQuadCtrlX2 = pts[1] * 3.0f - pts[0];
SkPoint rightQuadCtrlX2 = pts[2] * 3.0f - pts[3];
SkPoint errV = rightQuadCtrlX2 - leftQuadCtrlX2;
// Squared error distance
T errSq = SkPoint::DotProduct(errV, errV);
// The relative error mapped into n^6
T errDiv = errSq * invErrThreshold;
constexpr T kPowSixLut[Flatten::kMaxQuadsFromCubic] = {
1.0,
64.0,
729.0,
4096.0,
15625.0,
46656.0,
117649.0,
262144.0,
531441.0,
1000000.0,
1771561.0,
2985984.0,
4826809.0,
7529536.0,
11390625.0,
16777216.0,
};
for (uint32_t i = 0; i < Flatten::kMaxQuadsFromCubic; ++i) {
if (errDiv <= kPowSixLut[i]) {
return i + 1;
}
}
return Flatten::kMaxQuadsFromCubic;
}
/*
* 1. Error Proxy
* The vector `errV = p0 - 2*p1 + p2` is the second difference of the control points. If the
* curve were a standard polynomial quadratic (w = 1), this vector's length would directly bound
* the deviation between the curve and its chord. We use this as our baseline metric for the
* polygon's curvature. Because conics are rational, weights (0 < w < 1) cause the curve to
* parameterize non-uniformly. This significantly increases the worst-case error when
* approximating it with a cubic polynomial. We multiply by `algFactor` (1 / w^2) to
* heuristically overestimate the distortion and force enough subdivisions to hide visual errors.
*
* 2. Midpoint Approximation
* This implementation uses the G1 mid-point approximation from Proposition 5 of Floater, M. S.
* (1996). Floater demonstrates that the error of this approximation is O(h^6), where h is the
* parametric interval. Thus, bisecting the curve at t=0.5 reduces the worst-case error bound
* by a factor of 64 (2^6).
*
* 'invTol' is the inverse of the error tolerance in pixels. Returns the total number of generated
* cubics (1 << bisections).
*/
SK_ALWAYS_INLINE uint32_t
split_conic_to_cubics(const SkPoint pts[3],
float w,
float invTol,
SkPoint outCubics[Flatten::kMaxCubicsFromConic][4]) {
skvx::float2 p0 = skvx::float2::Load(&pts[0]);
skvx::float2 p1 = skvx::float2::Load(&pts[1]);
skvx::float2 p2 = skvx::float2::Load(&pts[2]);
float algFactor = (w < 1.0f && w > 0.0f) ? 1.0f / (w * w) : 1.0f;
skvx::float2 errV = p0 - p1 * 2.0f + p2;
float err = algFactor * skvx::length(errV);
int32_t bisections = std::min(skgpu::wangs_formula::nextlog64(err * invTol),
static_cast<int32_t>(Flatten::kMaxBisections));
struct ConicState {
skvx::float2 p0, p1, p2;
float w;
int32_t level;
};
ConicState stack[Flatten::kMaxBisections + 1];
int32_t stackIdx = 0;
stack[stackIdx++] = {p0, p1, p2, w, bisections};
int32_t cubicIdx = 0;
// Use unrolled recursion with fixed-size array
constexpr int32_t kMaxTreeNodes = (Flatten::kMaxCubicsFromConic * 2) - 1;
for (int32_t i = 0; i < kMaxTreeNodes; ++i) {
if (stackIdx == 0) {
break;
}
ConicState c = stack[--stackIdx];
if (c.level == 0) {
// Approximate conic as cubic
float k = (4.0f / 3.0f) * (c.w / (1.0f + c.w));
skvx::float2 c1 = c.p0 + (c.p1 - c.p0) * k;
skvx::float2 c2 = c.p2 + (c.p1 - c.p2) * k;
c.p0.store(&outCubics[cubicIdx][0]);
c1.store(&outCubics[cubicIdx][1]);
c2.store(&outCubics[cubicIdx][2]);
c.p2.store(&outCubics[cubicIdx][3]);
cubicIdx++;
} else {
// Bisect conic
float inv = 1.0f / (1.0f + c.w);
skvx::float2 p01 = (c.p0 + c.p1 * c.w) * inv;
skvx::float2 p12 = (c.p1 * c.w + c.p2) * inv;
skvx::float2 M = (p01 + p12) * 0.5f;
float newWeight = std::sqrt((1.0f + c.w) * 0.5f);
stack[stackIdx++] = {M, p12, c.p2, newWeight, c.level - 1};
stack[stackIdx++] = {c.p0, p01, M, newWeight, c.level - 1};
}
}
return 1u << bisections;
}
// Whether the points, and so the curve they control, lie entirely above, right of, or below
// 'clip'. Such a curve contributes no winding inside the clip.
template <int N, typename Rect>
SK_ALWAYS_INLINE bool is_completely_culled(const SkPoint pts[N], const Rect& clip) {
bool top = true;
bool right = true;
bool bottom = true;
for (int i = 0; i < N; ++i) {
top &= (pts[i].fY < clip.top());
right &= (pts[i].fX > clip.right());
bottom &= (pts[i].fY > clip.bottom());
}
return top || right || bottom;
}
// Whether the points lie entirely left of 'clip'. Such a curve still contributes winding to the
// rows it spans, so it is simplified rather than culled.
template <int N, typename Rect>
SK_ALWAYS_INLINE bool is_completely_left(const SkPoint pts[N], const Rect& clip) {
bool left = true;
for (int i = 0; i < N; ++i) {
left &= (pts[i].fX < clip.left());
}
return left;
}
} // namespace skgpu::graphite::flatten_utils
#endif // skgpu_graphite_sparse_strips_FlattenUtils_DEFINED