| 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 constexpr Scalar length(Point n) {
17 Point nn = n * n;
18 return std::sqrt(nn.x + nn.y);
19 }
20
21 } // namespace
22
23 Scalar ComputeCubicSubdivisions(Scalar scale_factor,
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
34 Scalar ComputeQuadradicSubdivisions(Scalar scale_factor,
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.
48 Scalar ComputeConicSubdivisions(Scalar scale_factor,
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 Scalar ComputeQuadradicSubdivisions(Scalar scale_factor,
86 const QuadraticPathComponent& quad) {
87 return ComputeQuadradicSubdivisions(scale_factor, quad.p1, quad.cp, quad.p2);
88 }
89
90 Scalar ComputeCubicSubdivisions(float scale_factor,
91 const CubicPathComponent& cub) {
92 return ComputeCubicSubdivisions(scale_factor, cub.p1, cub.cp1, cub.cp2,
93 cub.p2);
94 }
95
96 Scalar ComputeConicSubdivisions(float scale_factor,
97 const ConicPathComponent& conic) {
98 return ComputeConicSubdivisions(scale_factor, conic.p1, conic.cp, conic.p2,
99 conic.weight.x);
100 }
101
102 } // namespace impeller
impeller::saturated::b
SI b
Definition: saturated_math.h:87
impeller
Definition: allocation.cc:12
impeller::Scalar
float Scalar
Definition: scalar.h:18
impeller::Point
TPoint< Scalar > Point
Definition: point.h:327
impeller::ComputeConicSubdivisions
Scalar ComputeConicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Scalar w)
Definition: wangs_formula.cc:48
impeller::ComputeQuadradicSubdivisions
Scalar ComputeQuadradicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2)
Definition: wangs_formula.cc:34
impeller::ComputeCubicSubdivisions
Scalar ComputeCubicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Point p3)
Definition: wangs_formula.cc:23
impeller::ConicPathComponent
Definition: path_component.h:226
impeller::ConicPathComponent::cp
Point cp
Definition: path_component.h:230
impeller::ConicPathComponent::weight
Point weight
Definition: path_component.h:243
impeller::ConicPathComponent::p1
Point p1
Definition: path_component.h:228
impeller::ConicPathComponent::p2
Point p2
Definition: path_component.h:232
impeller::CubicPathComponent
Definition: path_component.h:280
impeller::CubicPathComponent::p1
Point p1
Definition: path_component.h:282
impeller::CubicPathComponent::cp1
Point cp1
Definition: path_component.h:284
impeller::CubicPathComponent::cp2
Point cp2
Definition: path_component.h:286
impeller::CubicPathComponent::p2
Point p2
Definition: path_component.h:288
impeller::QuadraticPathComponent
Definition: path_component.h:135
impeller::QuadraticPathComponent::p2
Point p2
Definition: path_component.h:141
impeller::QuadraticPathComponent::cp
Point cp
Definition: path_component.h:139
impeller::QuadraticPathComponent::p1
Point p1
Definition: path_component.h:137
impeller::TPoint< Scalar >
impeller::TPoint::Max
constexpr TPoint Max(const TPoint &p) const
Definition: point.h:190
impeller::TPoint::x
Type x
Definition: point.h:30
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