| Flutter Impeller |

wangs_formula.cc
Go to the documentation of this file.
1 // Copyright 2013 The Flutter Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "impeller/geometry/wangs_formula.h"
6
7 namespace impeller {
8
9 namespace {
10
11 // Don't allow linearized segments to be off by more than 1/4th of a pixel from
12 // the true curve. This value should be scaled by the max basis of the
13 // X and Y directions.
14 constexpr static Scalar kPrecision = 4;
15
16 } // namespace
17
18 Scalar ComputeCubicSubdivisions(Scalar scale_factor,
19 Point p0,
20 Point p1,
21 Point p2,
22 Point p3) {
23 const Scalar k = scale_factor * .75f * kPrecision;
24 const Vector2 a = p0 - p1 * 2 + p2;
25 const Vector2 b = p1 - p2 * 2 + p3;
26 const Scalar max_len_sq =
27 std::max(a.GetLengthSquared(), b.GetLengthSquared());
28 return std::sqrt(k * std::sqrt(max_len_sq));
29 }
30
31 Scalar ComputeQuadradicSubdivisions(Scalar scale_factor,
32 Point p0,
33 Point p1,
34 Point p2) {
35 const Scalar k = scale_factor * .25f * kPrecision;
36 return std::sqrt(k * (p0 - p1 * 2 + p2).GetLength());
37 }
38
39 // Returns Wang's formula specialized for a conic curve.
40 //
41 // This is not actually due to Wang, but is an analogue from:
42 // (Theorem 3, corollary 1):
43 // J. Zheng, T. Sederberg. "Estimating Tessellation Parameter Intervals for
44 // Rational Curves and Surfaces." ACM Transactions on Graphics 19(1). 2000.
45 Scalar ComputeConicSubdivisions(Scalar scale_factor,
46 Point p0,
47 Point p1,
48 Point p2,
49 Scalar w) {
50 // Compute center of bounding box in projected space
51 const Point C = 0.5f * (p0.Min(p1).Min(p2) + p0.Max(p1).Max(p2));
52
53 // Translate by -C. This improves translation-invariance of the formula,
54 // see Sec. 3.3 of cited paper
55 p0 -= C;
56 p1 -= C;
57 p2 -= C;
58
59 // Compute max length
60 const Scalar max_len =
61 std::sqrt(std::max(p0.Dot(p0), std::max(p1.Dot(p1), p2.Dot(p2))));
62
63 // Compute forward differences
64 const Point dp = -2 * w * p1 + p0 + p2;
65 const Scalar dw = std::abs(-2 * w + 2);
66
67 // Compute numerator and denominator for parametric step size of
68 // linearization. Here, the epsilon referenced from the cited paper
69 // is 1/precision.
70 Scalar k = scale_factor * kPrecision;
71 const Scalar rp_minus_1 = std::max(0.0f, max_len * k - 1);
72 const Scalar numer = std::sqrt(dp.Dot(dp)) * k + rp_minus_1 * dw;
73 const Scalar denom = 4 * std::min(w, 1.0f);
74
75 // Number of segments = sqrt(numer / denom).
76 // This assumes parametric interval of curve being linearized is
77 // [t0,t1] = [0, 1].
78 // If not, the number of segments is (tmax - tmin) / sqrt(denom / numer).
79 return std::sqrt(numer / denom);
80 }
81
82 } // namespace impeller
impeller::saturated::b
SI b
Definition: saturated_math.h:87
impeller
Definition: allocation.cc:12
impeller::Scalar
float Scalar
Definition: scalar.h:19
impeller::ComputeConicSubdivisions
Scalar ComputeConicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Scalar w)
Definition: wangs_formula.cc:45
impeller::ComputeQuadradicSubdivisions
Scalar ComputeQuadradicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2)
Definition: wangs_formula.cc:31
impeller::ComputeCubicSubdivisions
Scalar ComputeCubicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Point p3)
Definition: wangs_formula.cc:18
impeller::TPoint< Scalar >
impeller::TPoint::Max
constexpr TPoint Max(const TPoint &p) const
Definition: point.h:190
impeller::TPoint::GetLengthSquared
constexpr Type GetLengthSquared() const
Definition: point.h:204
impeller::TPoint::Min
constexpr TPoint Min(const TPoint &p) const
Definition: point.h:186
impeller::TPoint::Dot
constexpr Type Dot(const TPoint &p) const
Definition: point.h:220
wangs_formula.h