1 /* 2 * Copyright 2012 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_ARCS_BEZIER_HH 20 #define GLYPHY_ARCS_BEZIER_HH 21 22 #include "glyphy-common.hh" 23 #include "glyphy-geometry.hh" 24 #include "glyphy-arc-bezier.hh" 25 26 namespace GLyphy { 27 namespace ArcsBezier { 28 29 using namespace Geometry; 30 using namespace ArcBezier; 31 32 template <class ArcBezierApproximator> 33 class ArcsBezierApproximatorSpringSystem 34 { calc_arcs(const Bezier & b,const std::vector<double> & t,const ArcBezierApproximator & appx,std::vector<double> & e,std::vector<Arc> & arcs,double & max_e,double & min_e)35 static inline void calc_arcs (const Bezier &b, 36 const std::vector<double> &t, 37 const ArcBezierApproximator &appx, 38 std::vector<double> &e, 39 std::vector<Arc > &arcs, 40 double &max_e, double &min_e) 41 { 42 unsigned int n = t.size () - 1; 43 e.resize (n); 44 arcs.clear (); 45 max_e = 0; 46 min_e = GLYPHY_INFINITY; 47 for (unsigned int i = 0; i < n; i++) 48 { 49 Bezier segment = b.segment (t[i], t[i + 1]); 50 arcs.push_back (appx.approximate_bezier_with_arc (segment, &e[i])); 51 52 max_e = std::max (max_e, e[i]); 53 min_e = std::min (min_e, e[i]); 54 } 55 } 56 jiggle(const Bezier & b,const ArcBezierApproximator & appx,std::vector<double> & t,std::vector<double> & e,std::vector<Arc> & arcs,double & max_e,double & min_e,double tolerance,unsigned int & n_jiggle)57 static inline void jiggle (const Bezier &b, 58 const ArcBezierApproximator &appx, 59 std::vector<double> &t, 60 std::vector<double> &e, 61 std::vector<Arc > &arcs, 62 double &max_e, double &min_e, 63 double tolerance, 64 unsigned int &n_jiggle) 65 { 66 unsigned int n = t.size () - 1; 67 //fprintf (stderr, "candidate n %d max_e %g min_e %g\n", n, max_e, min_e); 68 unsigned int max_jiggle = log2 (n) + 1; 69 unsigned int s; 70 for (s = 0; s < max_jiggle; s++) 71 { 72 double total = 0; 73 for (unsigned int i = 0; i < n; i++) { 74 double l = t[i + 1] - t[i]; 75 double k_inv = l * pow (e[i], -.3); 76 total += k_inv; 77 e[i] = k_inv; 78 } 79 for (unsigned int i = 0; i < n; i++) { 80 double k_inv = e[i]; 81 double l = k_inv / total; 82 t[i + 1] = t[i] + l; 83 } 84 t[n] = 1.0; // Do this to get real 1.0, not .9999999999999998! 85 86 calc_arcs (b, t, appx, e, arcs, max_e, min_e); 87 88 //fprintf (stderr, "n %d jiggle %d max_e %g min_e %g\n", n, s, max_e, min_e); 89 90 n_jiggle++; 91 if (max_e < tolerance || (2 * min_e - max_e > tolerance)) 92 break; 93 } 94 //if (s == max_jiggle) fprintf (stderr, "JIGGLE OVERFLOW n %d s %d\n", n, s); 95 } 96 97 public: approximate_bezier_with_arcs(const Bezier & b,double tolerance,const ArcBezierApproximator & appx,std::vector<Arc> & arcs,double * perror,unsigned int max_segments=100)98 static void approximate_bezier_with_arcs (const Bezier &b, 99 double tolerance, 100 const ArcBezierApproximator &appx, 101 std::vector<Arc> &arcs, 102 double *perror, 103 unsigned int max_segments = 100) 104 { 105 std::vector<double> t; 106 std::vector<double> e; 107 double max_e, min_e; 108 unsigned int n_jiggle = 0; 109 110 /* Technically speaking we can bsearch for n. */ 111 for (unsigned int n = 1; n <= max_segments; n++) 112 { 113 t.resize (n + 1); 114 for (unsigned int i = 0; i < n; i++) 115 t[i] = double (i) / n; 116 t[n] = 1.0; // Do this out of the loop to get real 1.0, not .9999999999999998! 117 118 calc_arcs (b, t, appx, e, arcs, max_e, min_e); 119 120 for (unsigned int i = 0; i < n; i++) 121 if (e[i] <= tolerance) { 122 jiggle (b, appx, t, e, arcs, max_e, min_e, tolerance, n_jiggle); 123 break; 124 } 125 126 if (max_e <= tolerance) 127 break; 128 } 129 if (perror) 130 *perror = max_e; 131 //fprintf (stderr, "n_jiggle %d\n", n_jiggle); 132 } 133 }; 134 135 } /* namespace ArcsBezier */ 136 } /* namespace GLyphy */ 137 138 #endif /* GLYPHY_ARCS_BEZIER_HH */ 139