| /* |
| * Copyright 2020 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #ifndef GrWangsFormula_DEFINED |
| #define GrWangsFormula_DEFINED |
| |
| #include "include/core/SkPoint.h" |
| #include "include/private/SkNx.h" |
| #include "src/gpu/tessellate/GrVectorXform.h" |
| |
| // Wang's formulas for cubics and quadratics (1985) give us the minimum number of evenly spaced (in |
| // the parametric sense) line segments that a curve must be chopped into in order to guarantee all |
| // lines stay within a distance of "1/intolerance" pixels from the true curve. |
| namespace GrWangsFormula { |
| |
| SK_ALWAYS_INLINE static float length(const Sk2f& n) { |
| Sk2f nn = n*n; |
| return std::sqrt(nn[0] + nn[1]); |
| } |
| |
| // Constant term for the quatratic formula. |
| constexpr float quadratic_k(float intolerance) { |
| return .25f * intolerance; |
| } |
| |
| // Returns the minimum number of evenly spaced (in the parametric sense) line segments that the |
| // quadratic must be chopped into in order to guarantee all lines stay within a distance of |
| // "1/intolerance" pixels from the true curve. |
| SK_ALWAYS_INLINE static float quadratic(float intolerance, const SkPoint pts[]) { |
| Sk2f p0 = Sk2f::Load(pts); |
| Sk2f p1 = Sk2f::Load(pts + 1); |
| Sk2f p2 = Sk2f::Load(pts + 2); |
| float k = quadratic_k(intolerance); |
| return SkScalarSqrt(k * length(p0 - p1*2 + p2)); |
| } |
| |
| // Constant term for the cubic formula. |
| constexpr float cubic_k(float intolerance) { |
| return .75f * intolerance; |
| } |
| |
| // Returns the minimum number of evenly spaced (in the parametric sense) line segments that the |
| // cubic must be chopped into in order to guarantee all lines stay within a distance of |
| // "1/intolerance" pixels from the true curve. |
| SK_ALWAYS_INLINE static float cubic(float intolerance, const SkPoint pts[]) { |
| Sk2f p0 = Sk2f::Load(pts); |
| Sk2f p1 = Sk2f::Load(pts + 1); |
| Sk2f p2 = Sk2f::Load(pts + 2); |
| Sk2f p3 = Sk2f::Load(pts + 3); |
| float k = cubic_k(intolerance); |
| return SkScalarSqrt(k * length(Sk2f::Max((p0 - p1*2 + p2).abs(), |
| (p1 - p2*2 + p3).abs()))); |
| } |
| |
| // Returns the maximum number of line segments a cubic with the given device-space bounding box size |
| // would ever need to be divided into. This is simply a special case of the cubic formula where we |
| // maximize its value by placing control points on specific corners of the bounding box. |
| SK_ALWAYS_INLINE static float worst_case_cubic(float intolerance, float devWidth, float devHeight) { |
| float k = cubic_k(intolerance); |
| return SkScalarSqrt(2*k * SkVector::Length(devWidth, devHeight)); |
| } |
| |
| // Returns the log2 of the provided value, were that value to be rounded up to the next power of 2. |
| // Returns 0 if value <= 0: |
| // Never returns a negative number, even if value is NaN. |
| // |
| // nextlog2((-inf..1]) -> 0 |
| // nextlog2((1..2]) -> 1 |
| // nextlog2((2..4]) -> 2 |
| // nextlog2((4..8]) -> 3 |
| // ... |
| SK_ALWAYS_INLINE static int nextlog2(float value) { |
| uint32_t bits; |
| memcpy(&bits, &value, 4); |
| bits += (1u << 23) - 1u; // Increment the exponent for non-powers-of-2. |
| int exp = ((int32_t)bits >> 23) - 127; |
| return exp & ~(exp >> 31); // Return 0 for negative or denormalized floats, and exponents < 0. |
| } |
| |
| SK_ALWAYS_INLINE static int ceil_log2_sqrt_sqrt(float f) { |
| return (nextlog2(f) + 3) >> 2; // i.e., "ceil(log2(sqrt(sqrt(f)))) |
| } |
| |
| // Returns the minimum log2 number of evenly spaced (in the parametric sense) line segments that the |
| // transformed quadratic must be chopped into in order to guarantee all lines stay within a distance |
| // of "1/intolerance" pixels from the true curve. |
| SK_ALWAYS_INLINE static int quadratic_log2(float intolerance, const SkPoint pts[], |
| const GrVectorXform& vectorXform = GrVectorXform()) { |
| Sk2f p0 = Sk2f::Load(pts); |
| Sk2f p1 = Sk2f::Load(pts + 1); |
| Sk2f p2 = Sk2f::Load(pts + 2); |
| Sk2f v = p0 + p1*-2 + p2; |
| v = vectorXform(v); |
| Sk2f vv = v*v; |
| float k = quadratic_k(intolerance); |
| float f = k*k * (vv[0] + vv[1]); |
| return ceil_log2_sqrt_sqrt(f); |
| } |
| |
| // Returns the minimum log2 number of evenly spaced (in the parametric sense) line segments that the |
| // transformed cubic must be chopped into in order to guarantee all lines stay within a distance of |
| // "1/intolerance" pixels from the true curve. |
| SK_ALWAYS_INLINE static int cubic_log2(float intolerance, const SkPoint pts[], |
| const GrVectorXform& vectorXform = GrVectorXform()) { |
| Sk4f p01 = Sk4f::Load(pts); |
| Sk4f p12 = Sk4f::Load(pts + 1); |
| Sk4f p23 = Sk4f::Load(pts + 2); |
| Sk4f v = p01 + p12*-2 + p23; |
| v = vectorXform(v); |
| Sk4f vv = v*v; |
| vv = Sk4f::Max(vv, SkNx_shuffle<2,3,0,1>(vv)); |
| float k = cubic_k(intolerance); |
| float f = k*k * (vv[0] + vv[1]); |
| return ceil_log2_sqrt_sqrt(f); |
| } |
| |
| // Returns the maximum log2 number of line segments a cubic with the given device-space bounding box |
| // size would ever need to be divided into. |
| SK_ALWAYS_INLINE static int worst_case_cubic_log2(float intolerance, float devWidth, |
| float devHeight) { |
| float k = cubic_k(intolerance); |
| return ceil_log2_sqrt_sqrt(4*k*k * (devWidth * devWidth + devHeight * devHeight)); |
| } |
| |
| } // namespace |
| |
| #endif |