2 * Copyright 2012,2013 Google, Inc. All Rights Reserved.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
16 * Google Author(s): Behdad Esfahbod, Maysum Panju
19 #ifndef GLYPHY_ARC_BEZIER_HH
20 #define GLYPHY_ARC_BEZIER_HH
22 #include "glyphy-common.hh"
23 #include "glyphy-geometry.hh"
28 using namespace Geometry;
31 class MaxDeviationApproximatorExact
34 /* Returns 3 max(abs(d₀ t (1-t)² + d₁ t² (1-t)) for 0≤t≤1. */
35 static double approximate_deviation (double d0, double d1)
37 double candidates[4] = {0,1};
38 unsigned int num_candidates = 2;
40 candidates[num_candidates++] = .5;
42 double delta = d0*d0 - d0*d1 + d1*d1;
43 double t2 = 1. / (3 * (d0 - d1));
44 double t0 = (2 * d0 - d1) * t2;
46 candidates[num_candidates++] = t0;
48 /* This code can be optimized to avoid the sqrt if the solution
49 * is not feasible (ie. lies outside (0,1)). I have implemented
50 * that in cairo-spline.c:_cairo_spline_bound(). Can be reused
53 double t1 = sqrt (delta) * t2;
54 candidates[num_candidates++] = t0 - t1;
55 candidates[num_candidates++] = t0 + t1;
60 for (unsigned int i = 0; i < num_candidates; i++) {
61 double t = candidates[i];
65 ee = fabs (3 * t * (1-t) * (d0 * (1 - t) + d1 * t));
75 template <class MaxDeviationApproximator>
76 class ArcBezierErrorApproximatorBehdad
79 static double approximate_bezier_arc_error (const Bezier &b0, const Arc &a)
81 assert (b0.p0 == a.p0);
82 assert (b0.p3 == a.p1);
85 Bezier b1 = a.approximate_bezier (&ea);
87 assert (b0.p0 == b1.p0);
88 assert (b0.p3 == b1.p3);
90 Vector v0 = b1.p1 - b0.p1;
91 Vector v1 = b1.p2 - b0.p2;
93 Vector b = (b0.p3 - b0.p0).normalized ();
97 Vector v (MaxDeviationApproximator::approximate_deviation (v0.dx, v1.dx),
98 MaxDeviationApproximator::approximate_deviation (v0.dy, v1.dy));
100 /* Edge cases: If d*d is too close too large default to a weak bound. */
101 if (a.d * a.d > 1. - 1e-4)
102 return ea + v.len ();
104 /* If the wedge doesn't contain control points, default to weak bound. */
105 if (!a.wedge_contains_point (b0.p1) || !a.wedge_contains_point (b0.p2))
106 return ea + v.len ();
108 /* If straight line, return the max ortho deviation. */
109 if (fabs (a.d) < 1e-6)
112 /* We made sure that fabs(a.d) < 1 */
113 double tan_half_alpha = fabs (tan2atan (a.d));
115 double tan_v = v.dx / v.dy;
118 if (fabs (tan_v) <= tan_half_alpha)
119 return ea + v.len ();
121 double c2 = (a.p1 - a.p0).len () * .5;
122 double r = a.radius ();
124 eb = Vector (c2 + v.dx, c2 / tan_half_alpha + v.dy).len () - r;
133 template <class ArcBezierErrorApproximator>
134 class ArcBezierApproximatorMidpointSimple
137 static const Arc approximate_bezier_with_arc (const Bezier &b, double *error)
139 Arc a (b.p0, b.p3, b.midpoint (), false);
141 *error = ArcBezierErrorApproximator::approximate_bezier_arc_error (b, a);
147 template <class ArcBezierErrorApproximator>
148 class ArcBezierApproximatorMidpointTwoPart
151 static const Arc approximate_bezier_with_arc (const Bezier &b, double *error, double mid_t = .5)
153 Pair<Bezier > pair = b.split (mid_t);
154 Point m = pair.second.p0;
156 Arc a0 (b.p0, m, b.p3, true);
157 Arc a1 (m, b.p3, b.p0, true);
159 double e0 = ArcBezierErrorApproximator::approximate_bezier_arc_error (pair.first, a0);
160 double e1 = ArcBezierErrorApproximator::approximate_bezier_arc_error (pair.second, a1);
161 *error = std::max (e0, e1);
163 return Arc (b.p0, b.p3, m, false);
167 template <class ArcBezierErrorApproximator>
168 class ArcBezierApproximatorQuantized
171 ArcBezierApproximatorQuantized (double _max_d = GLYPHY_INFINITY, unsigned int _d_bits = 0) :
172 max_d (_max_d), d_bits (_d_bits) {};
179 const Arc approximate_bezier_with_arc (const Bezier &b, double *error) const
182 Arc a (b.p0, b.p3, b.point (mid_t), false);
185 if (std::isfinite (max_d)) {
187 if (fabs (a.d) > max_d)
188 a.d = a.d < 0 ? -max_d : max_d;
190 if (d_bits && max_d != 0) {
191 assert (std::isfinite (max_d));
192 assert (fabs (a.d) <= max_d);
193 int mult = (1 << (d_bits - 1)) - 1;
194 int id = round (a.d / max_d * mult);
195 assert (-mult <= id && id <= mult);
196 a.d = id * max_d / mult;
197 assert (fabs (a.d) <= max_d);
200 /* Error introduced by arc quantization */
201 double ed = fabs (a.d - orig_a.d) * (a.p1 - a.p0).len () * .5;
203 ArcBezierApproximatorMidpointTwoPart<ArcBezierErrorApproximator>
204 ::approximate_bezier_with_arc (b, error, mid_t);
209 /* Try a simple one-arc approx which works with the quantized arc.
210 * May produce smaller error bound. */
211 double e = ArcBezierErrorApproximator::approximate_bezier_arc_error (b, a);
220 typedef MaxDeviationApproximatorExact MaxDeviationApproximatorDefault;
221 typedef ArcBezierErrorApproximatorBehdad<MaxDeviationApproximatorDefault> ArcBezierErrorApproximatorDefault;
222 typedef ArcBezierApproximatorMidpointTwoPart<ArcBezierErrorApproximatorDefault> ArcBezierApproximatorDefault;
223 typedef ArcBezierApproximatorQuantized<ArcBezierErrorApproximatorDefault> ArcBezierApproximatorQuantizedDefault;
225 } /* namespace ArcBezier */
226 } /* namespace GLyphy */
228 #endif /* GLYPHY_ARC_BEZIER_HH */