1/*
2 * Copyright 2020 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef GrWangsFormula_DEFINED
9#define GrWangsFormula_DEFINED
10
11#include "include/core/SkPoint.h"
12#include "include/private/SkNx.h"
13#include "src/gpu/tessellate/GrVectorXform.h"
14
15// Wang's formulas for cubics and quadratics (1985) give us the minimum number of evenly spaced (in
16// the parametric sense) line segments that a curve must be chopped into in order to guarantee all
17// lines stay within a distance of "1/intolerance" pixels from the true curve.
18namespace GrWangsFormula {
19
20SK_ALWAYS_INLINE static float length(const Sk2f& n) {
21 Sk2f nn = n*n;
22 return std::sqrt(nn[0] + nn[1]);
23}
24
25// Constant term for the quatratic formula.
26constexpr float quadratic_k(float intolerance) {
27 return .25f * intolerance;
28}
29
30// Returns the minimum number of evenly spaced (in the parametric sense) line segments that the
31// quadratic must be chopped into in order to guarantee all lines stay within a distance of
32// "1/intolerance" pixels from the true curve.
33SK_ALWAYS_INLINE static float quadratic(float intolerance, const SkPoint pts[]) {
34 Sk2f p0 = Sk2f::Load(pts);
35 Sk2f p1 = Sk2f::Load(pts + 1);
36 Sk2f p2 = Sk2f::Load(pts + 2);
37 float k = quadratic_k(intolerance);
38 return SkScalarSqrt(k * length(p0 - p1*2 + p2));
39}
40
41// Constant term for the cubic formula.
42constexpr float cubic_k(float intolerance) {
43 return .75f * intolerance;
44}
45
46// Returns the minimum number of evenly spaced (in the parametric sense) line segments that the
47// cubic must be chopped into in order to guarantee all lines stay within a distance of
48// "1/intolerance" pixels from the true curve.
49SK_ALWAYS_INLINE static float cubic(float intolerance, const SkPoint pts[]) {
50 Sk2f p0 = Sk2f::Load(pts);
51 Sk2f p1 = Sk2f::Load(pts + 1);
52 Sk2f p2 = Sk2f::Load(pts + 2);
53 Sk2f p3 = Sk2f::Load(pts + 3);
54 float k = cubic_k(intolerance);
55 return SkScalarSqrt(k * length(Sk2f::Max((p0 - p1*2 + p2).abs(),
56 (p1 - p2*2 + p3).abs())));
57}
58
59// Returns the maximum number of line segments a cubic with the given device-space bounding box size
60// would ever need to be divided into. This is simply a special case of the cubic formula where we
61// maximize its value by placing control points on specific corners of the bounding box.
62SK_ALWAYS_INLINE static float worst_case_cubic(float intolerance, float devWidth, float devHeight) {
63 float k = cubic_k(intolerance);
64 return SkScalarSqrt(2*k * SkVector::Length(devWidth, devHeight));
65}
66
67// Returns the log2 of the provided value, were that value to be rounded up to the next power of 2.
68// Returns 0 if value <= 0:
69// Never returns a negative number, even if value is NaN.
70//
71// nextlog2((-inf..1]) -> 0
72// nextlog2((1..2]) -> 1
73// nextlog2((2..4]) -> 2
74// nextlog2((4..8]) -> 3
75// ...
76SK_ALWAYS_INLINE static int nextlog2(float value) {
77 uint32_t bits;
78 memcpy(&bits, &value, 4);
79 bits += (1u << 23) - 1u; // Increment the exponent for non-powers-of-2.
80 int exp = ((int32_t)bits >> 23) - 127;
81 return exp & ~(exp >> 31); // Return 0 for negative or denormalized floats, and exponents < 0.
82}
83
84SK_ALWAYS_INLINE static int ceil_log2_sqrt_sqrt(float f) {
85 return (nextlog2(f) + 3) >> 2; // i.e., "ceil(log2(sqrt(sqrt(f))))
86}
87
88// Returns the minimum log2 number of evenly spaced (in the parametric sense) line segments that the
89// transformed quadratic must be chopped into in order to guarantee all lines stay within a distance
90// of "1/intolerance" pixels from the true curve.
91SK_ALWAYS_INLINE static int quadratic_log2(float intolerance, const SkPoint pts[],
92 const GrVectorXform& vectorXform = GrVectorXform()) {
93 Sk2f p0 = Sk2f::Load(pts);
94 Sk2f p1 = Sk2f::Load(pts + 1);
95 Sk2f p2 = Sk2f::Load(pts + 2);
96 Sk2f v = p0 + p1*-2 + p2;
97 v = vectorXform(v);
98 Sk2f vv = v*v;
99 float k = quadratic_k(intolerance);
100 float f = k*k * (vv[0] + vv[1]);
101 return ceil_log2_sqrt_sqrt(f);
102}
103
104// Returns the minimum log2 number of evenly spaced (in the parametric sense) line segments that the
105// transformed cubic must be chopped into in order to guarantee all lines stay within a distance of
106// "1/intolerance" pixels from the true curve.
107SK_ALWAYS_INLINE static int cubic_log2(float intolerance, const SkPoint pts[],
108 const GrVectorXform& vectorXform = GrVectorXform()) {
109 Sk4f p01 = Sk4f::Load(pts);
110 Sk4f p12 = Sk4f::Load(pts + 1);
111 Sk4f p23 = Sk4f::Load(pts + 2);
112 Sk4f v = p01 + p12*-2 + p23;
113 v = vectorXform(v);
114 Sk4f vv = v*v;
115 vv = Sk4f::Max(vv, SkNx_shuffle<2,3,0,1>(vv));
116 float k = cubic_k(intolerance);
117 float f = k*k * (vv[0] + vv[1]);
118 return ceil_log2_sqrt_sqrt(f);
119}
120
121// Returns the maximum log2 number of line segments a cubic with the given device-space bounding box
122// size would ever need to be divided into.
123SK_ALWAYS_INLINE static int worst_case_cubic_log2(float intolerance, float devWidth,
124 float devHeight) {
125 float k = cubic_k(intolerance);
126 return ceil_log2_sqrt_sqrt(4*k*k * (devWidth * devWidth + devHeight * devHeight));
127}
128
129} // namespace GrWangsFormula
130
131#endif
132