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 
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 inline Scalar length(Point n) {
17  Point nn = n * n;
18  return std::sqrt(nn.x + nn.y);
19 }
20 
21 } // namespace
22 
24  Point p0,
25  Point p1,
26  Point p2,
27  Point p3) {
28  Scalar k = scale_factor * .75f * kPrecision;
29  Point a = (p0 - p1 * 2 + p2).Abs();
30  Point b = (p1 - p2 * 2 + p3).Abs();
31  return std::sqrt(k * length(a.Max(b)));
32 }
33 
35  Point p0,
36  Point p1,
37  Point p2) {
38  Scalar k = scale_factor * .25f * kPrecision;
39  return std::sqrt(k * length(p0 - p1 * 2 + p2));
40 }
41 
42 // Returns Wang's formula specialized for a conic curve.
43 //
44 // This is not actually due to Wang, but is an analogue from:
45 // (Theorem 3, corollary 1):
46 // J. Zheng, T. Sederberg. "Estimating Tessellation Parameter Intervals for
47 // Rational Curves and Surfaces." ACM Transactions on Graphics 19(1). 2000.
49  Point p0,
50  Point p1,
51  Point p2,
52  Scalar w) {
53  // Compute center of bounding box in projected space
54  const Point C = 0.5f * (p0.Min(p1).Min(p2) + p0.Max(p1).Max(p2));
55 
56  // Translate by -C. This improves translation-invariance of the formula,
57  // see Sec. 3.3 of cited paper
58  p0 -= C;
59  p1 -= C;
60  p2 -= C;
61 
62  // Compute max length
63  const Scalar max_len =
64  std::sqrt(std::max(p0.Dot(p0), std::max(p1.Dot(p1), p2.Dot(p2))));
65 
66  // Compute forward differences
67  const Point dp = -2 * w * p1 + p0 + p2;
68  const Scalar dw = std::abs(-2 * w + 2);
69 
70  // Compute numerator and denominator for parametric step size of
71  // linearization. Here, the epsilon referenced from the cited paper
72  // is 1/precision.
73  Scalar k = scale_factor * kPrecision;
74  const Scalar rp_minus_1 = std::max(0.0f, max_len * k - 1);
75  const Scalar numer = std::sqrt(dp.Dot(dp)) * k + rp_minus_1 * dw;
76  const Scalar denom = 4 * std::min(w, 1.0f);
77 
78  // Number of segments = sqrt(numer / denom).
79  // This assumes parametric interval of curve being linearized is
80  // [t0,t1] = [0, 1].
81  // If not, the number of segments is (tmax - tmin) / sqrt(denom / numer).
82  return std::sqrt(numer / denom);
83 }
84 
85 } // namespace impeller
float Scalar
Definition: scalar.h:19
TPoint< Scalar > Point
Definition: point.h:327
Scalar ComputeConicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Scalar w)
Scalar ComputeQuadradicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2)
Scalar ComputeCubicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Point p3)
constexpr TPoint Max(const TPoint &p) const
Definition: point.h:190
constexpr TPoint Min(const TPoint &p) const
Definition: point.h:186
constexpr Type Dot(const TPoint &p) const
Definition: point.h:220