third-party/glyphy/glyphy-arc-bezier.hh

   1 /*
   2  * Copyright 2012,2013 Google, Inc. All Rights Reserved.
   3  *
   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
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  *
  16  * Google Author(s): Behdad Esfahbod, Maysum Panju
  17  */
  18
  19 #ifndef GLYPHY_ARC_BEZIER_HH
  20 #define GLYPHY_ARC_BEZIER_HH
  21
  22 #include "glyphy-common.hh"
  23 #include "glyphy-geometry.hh"
  24
  25 namespace GLyphy {
  26 namespace ArcBezier {
  27
  28 using namespace Geometry;
  29
  30
  31 class MaxDeviationApproximatorExact
  32 {
  33   public:
  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)
  36   {
  37     double candidates[4] = {0,1};
  38     unsigned int num_candidates = 2;
  39     if (d0 == d1)
  40       candidates[num_candidates++] = .5;
  41     else {
  42       double delta = d0*d0 - d0*d1 + d1*d1;
  43       double t2 = 1. / (3 * (d0 - d1));
  44       double t0 = (2 * d0 - d1) * t2;
  45       if (delta == 0)
  46         candidates[num_candidates++] = t0;
  47       else if (delta > 0) {
  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
  51          * here.
  52          */
  53         double t1 = sqrt (delta) * t2;
  54         candidates[num_candidates++] = t0 - t1;
  55         candidates[num_candidates++] = t0 + t1;
  56       }
  57     }
  58
  59     double e = 0;
  60     for (unsigned int i = 0; i < num_candidates; i++) {
  61       double t = candidates[i];
  62       double ee;
  63       if (t < 0. || t > 1.)
  64         continue;
  65       ee = fabs (3 * t * (1-t) * (d0 * (1 - t) + d1 * t));
  66       e = std::max (e, ee);
  67     }
  68
  69     return e;
  70   }
  71 };
  72
  73
  74
  75 template <class MaxDeviationApproximator>
  76 class ArcBezierErrorApproximatorBehdad
  77 {
  78   public:
  79   static double approximate_bezier_arc_error (const Bezier &b0, const Arc &a)
  80   {
  81     assert (b0.p0 == a.p0);
  82     assert (b0.p3 == a.p1);
  83
  84     double ea;
  85     Bezier b1 = a.approximate_bezier (&ea);
  86
  87     assert (b0.p0 == b1.p0);
  88     assert (b0.p3 == b1.p3);
  89
  90     Vector v0 = b1.p1 - b0.p1;
  91     Vector v1 = b1.p2 - b0.p2;
  92
  93     Vector b = (b0.p3 - b0.p0).normalized ();
  94     v0 = v0.rebase (b);
  95     v1 = v1.rebase (b);
  96
  97     Vector v (MaxDeviationApproximator::approximate_deviation (v0.dx, v1.dx),
  98               MaxDeviationApproximator::approximate_deviation (v0.dy, v1.dy));
  99
 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 ();
 103
 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 ();
 107
 108     /* If straight line, return the max ortho deviation. */
 109     if (fabs (a.d) < 1e-6)
 110       return ea + v.dy;
 111
 112     /* We made sure that fabs(a.d) < 1 */
 113     double tan_half_alpha = fabs (tan2atan (a.d));
 114
 115     double tan_v = v.dx / v.dy;
 116
 117     double eb;
 118     if (fabs (tan_v) <= tan_half_alpha)
 119       return ea + v.len ();
 120
 121     double c2 = (a.p1 - a.p0).len () * .5;
 122     double r = a.radius ();
 123
 124     eb = Vector (c2 + v.dx, c2 / tan_half_alpha + v.dy).len () - r;
 125     assert (eb >= 0);
 126
 127     return ea + eb;
 128   }
 129 };
 130
 131
 132
 133 template <class ArcBezierErrorApproximator>
 134 class ArcBezierApproximatorMidpointSimple
 135 {
 136   public:
 137   static const Arc approximate_bezier_with_arc (const Bezier &b, double *error)
 138   {
 139     Arc a (b.p0, b.p3, b.midpoint (), false);
 140
 141     *error = ArcBezierErrorApproximator::approximate_bezier_arc_error (b, a);
 142
 143     return a;
 144   }
 145 };
 146
 147 template <class ArcBezierErrorApproximator>
 148 class ArcBezierApproximatorMidpointTwoPart
 149 {
 150   public:
 151   static const Arc approximate_bezier_with_arc (const Bezier &b, double *error, double mid_t = .5)
 152   {
 153     Pair<Bezier > pair = b.split (mid_t);
 154     Point m = pair.second.p0;
 155
 156     Arc a0 (b.p0, m, b.p3, true);
 157     Arc a1 (m, b.p3, b.p0, true);
 158
 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);
 162
 163     return Arc (b.p0, b.p3, m, false);
 164   }
 165 };
 166
 167 template <class ArcBezierErrorApproximator>
 168 class ArcBezierApproximatorQuantized
 169 {
 170   public:
 171   ArcBezierApproximatorQuantized (double _max_d = GLYPHY_INFINITY, unsigned int _d_bits = 0) :
 172     max_d (_max_d), d_bits (_d_bits) {};
 173
 174   protected:
 175   double max_d;
 176   unsigned int d_bits;
 177
 178   public:
 179   const Arc approximate_bezier_with_arc (const Bezier &b, double *error) const
 180   {
 181     double mid_t = .5;
 182     Arc a (b.p0, b.p3, b.point (mid_t), false);
 183     Arc orig_a = a;
 184
 185     if (std::isfinite (max_d)) {
 186       assert (max_d >= 0);
 187       if (fabs (a.d) > max_d)
 188         a.d = a.d < 0 ? -max_d : max_d;
 189     }
 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);
 198     }
 199
 200     /* Error introduced by arc quantization */
 201     double ed = fabs (a.d - orig_a.d) * (a.p1 - a.p0).len () * .5;
 202
 203     ArcBezierApproximatorMidpointTwoPart<ArcBezierErrorApproximator>
 204             ::approximate_bezier_with_arc (b, error, mid_t);
 205
 206     if (ed) {
 207       *error += ed;
 208
 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);
 212       if (e < *error)
 213         *error = e;
 214     }
 215
 216     return a;
 217   }
 218 };
 219
 220 typedef MaxDeviationApproximatorExact MaxDeviationApproximatorDefault;
 221 typedef ArcBezierErrorApproximatorBehdad<MaxDeviationApproximatorDefault> ArcBezierErrorApproximatorDefault;
 222 typedef ArcBezierApproximatorMidpointTwoPart<ArcBezierErrorApproximatorDefault> ArcBezierApproximatorDefault;
 223 typedef ArcBezierApproximatorQuantized<ArcBezierErrorApproximatorDefault> ArcBezierApproximatorQuantizedDefault;
 224
 225 } /* namespace ArcBezier */
 226 } /* namespace GLyphy */
 227
 228 #endif /* GLYPHY_ARC_BEZIER_HH */