third-party/glyphy/glyphy-blob-impl.cc

   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, Wojciech Baranowski
  17  */
  18
  19 #ifdef HAVE_CONFIG_H
  20 #include <config.h>
  21 #endif
  22
  23 // Glyphy is written using C style casts
  24 #pragma GCC diagnostic push
  25 #pragma GCC diagnostic ignored "-Wold-style-cast"
  26
  27 #include "glyphy-common.hh"
  28 #include "glyphy-geometry.hh"
  29
  30 #define GRID_SIZE 24
  31
  32 using namespace GLyphy::Geometry;
  33
  34
  35 #define UPPER_BITS(v,bits,total_bits) ((v) >> ((total_bits) - (bits)))
  36 #define LOWER_BITS(v,bits,total_bits) ((v) & ((1 << (bits)) - 1))
  37
  38 #define MAX_X 4095
  39 #define MAX_Y 4095
  40
  41 static inline glyphy_rgba_t
  42 arc_endpoint_encode (unsigned int ix, unsigned int iy, double d)
  43 {
  44   glyphy_rgba_t v;
  45
  46   /* 12 bits for each of x and y, 8 bits for d */
  47   assert (ix <= MAX_X);
  48   assert (iy <= MAX_Y);
  49   unsigned int id;
  50   if (std::isinf (d))
  51     id = 0;
  52   else {
  53     assert (fabs (d) <= GLYPHY_MAX_D);
  54     id = 128 + lround (d * 127 / GLYPHY_MAX_D);
  55   }
  56   assert (id < 256);
  57
  58   v.r = id;
  59   v.g = LOWER_BITS (ix, 8, 12);
  60   v.b = LOWER_BITS (iy, 8, 12);
  61   v.a = ((ix >> 8) << 4) | (iy >> 8);
  62   return v;
  63 }
  64
  65 static inline glyphy_rgba_t
  66 arc_list_encode (unsigned int offset, unsigned int num_points, int side)
  67 {
  68   glyphy_rgba_t v;
  69   v.r = 0; // unused for arc-list encoding
  70   v.g = UPPER_BITS (offset, 8, 16);
  71   v.b = LOWER_BITS (offset, 8, 16);
  72   v.a = LOWER_BITS (num_points, 8, 8);
  73   if (side < 0 && !num_points)
  74     v.a = 255;
  75   return v;
  76 }
  77
  78 static inline glyphy_rgba_t
  79 line_encode (const Line &line)
  80 {
  81   Line l = line.normalized ();
  82   double angle = l.n.angle ();
  83   double distance = l.c;
  84
  85   int ia = lround (-angle / M_PI * 0x7FFF);
  86   unsigned int ua = ia + 0x8000;
  87   assert (0 == (ua & ~0xFFFF));
  88
  89   int id = lround (distance * 0x1FFF);
  90   unsigned int ud = id + 0x4000;
  91   assert (0 == (ud & ~0x7FFF));
  92
  93   /* Marker for line-encoded */
  94   ud |= 0x8000;
  95
  96   glyphy_rgba_t v;
  97   v.r = ud >> 8;
  98   v.g = ud & 0xFF;
  99   v.b = ua >> 8;
 100   v.a = ua & 0xFF;
 101   return v;
 102 }
 103
 104
 105 /* Given a cell, fills the vector closest_arcs with arcs that may be closest to some point in the cell.
 106  * Uses idea that all close arcs to cell must be ~close to center of cell.
 107  */
 108 static void
 109 closest_arcs_to_cell (Point c0, Point c1, /* corners */
 110                       double faraway,
 111                       const glyphy_arc_endpoint_t *endpoints,
 112                       unsigned int num_endpoints,
 113                       std::vector<glyphy_arc_endpoint_t> &near_endpoints,
 114                       int *side)
 115 {
 116   // Find distance between cell center
 117   Point c = c0.midpoint (c1);
 118   double min_dist = glyphy_sdf_from_arc_list (endpoints, num_endpoints, &c, NULL);
 119
 120   *side = min_dist >= 0 ? +1 : -1;
 121   min_dist = fabs (min_dist);
 122   std::vector<Arc> near_arcs;
 123
 124   // If d is the distance from the center of the square to the nearest arc, then
 125   // all nearest arcs to the square must be at most almost [d + half_diagonal] from the center.
 126   double half_diagonal = (c - c0).len ();
 127   double radius_squared = pow (min_dist + half_diagonal, 2);
 128   if (min_dist - half_diagonal <= faraway) {
 129     Point p0 (0, 0);
 130     for (unsigned int i = 0; i < num_endpoints; i++) {
 131       const glyphy_arc_endpoint_t &endpoint = endpoints[i];
 132       if (endpoint.d == GLYPHY_INFINITY) {
 133         p0 = endpoint.p;
 134         continue;
 135       }
 136       Arc arc (p0, endpoint.p, endpoint.d);
 137       p0 = endpoint.p;
 138
 139       if (arc.squared_distance_to_point (c) <= radius_squared)
 140         near_arcs.push_back (arc);
 141     }
 142   }
 143
 144   Point p1 = Point (0, 0);
 145   for (unsigned i = 0; i < near_arcs.size (); i++)
 146   {
 147     Arc arc = near_arcs[i];
 148
 149     if (i == 0 || p1 != arc.p0) {
 150       glyphy_arc_endpoint_t endpoint = {arc.p0, GLYPHY_INFINITY};
 151       near_endpoints.push_back (endpoint);
 152       p1 = arc.p0;
 153     }
 154
 155     glyphy_arc_endpoint_t endpoint = {arc.p1, arc.d};
 156     near_endpoints.push_back (endpoint);
 157     p1 = arc.p1;
 158   }
 159 }
 160
 161
 162 glyphy_bool_t
 163 glyphy_arc_list_encode_blob (const glyphy_arc_endpoint_t *endpoints,
 164                              unsigned int                 num_endpoints,
 165                              glyphy_rgba_t               *blob,
 166                              unsigned int                 blob_size,
 167                              double                       faraway,
 168                              double                       avg_fetch_desired,
 169                              double                      *avg_fetch_achieved,
 170                              unsigned int                *output_len,
 171                              unsigned int                *nominal_width,  /* 8bit */
 172                              unsigned int                *nominal_height, /* 8bit */
 173                              glyphy_extents_t            *pextents)
 174 {
 175   glyphy_extents_t extents;
 176   glyphy_extents_clear (&extents);
 177
 178   glyphy_arc_list_extents (endpoints, num_endpoints, &extents);
 179
 180   if (glyphy_extents_is_empty (&extents)) {
 181     *pextents = extents;
 182     if (!blob_size)
 183       return false;
 184     *blob = arc_list_encode (0, 0, +1);
 185     *avg_fetch_achieved = 1;
 186     *output_len = 1;
 187     *nominal_width = *nominal_height = 1;
 188     return true;
 189   }
 190
 191   /* Add antialiasing padding */
 192   extents.min_x -= faraway;
 193   extents.min_y -= faraway;
 194   extents.max_x += faraway;
 195   extents.max_y += faraway;
 196
 197   double glyph_width = extents.max_x - extents.min_x;
 198   double glyph_height = extents.max_y - extents.min_y;
 199   double unit = std::max (glyph_width, glyph_height);
 200
 201   unsigned int grid_w = GRID_SIZE;
 202   unsigned int grid_h = GRID_SIZE;
 203
 204   if (glyph_width > glyph_height) {
 205     while ((grid_h - 1) * unit / grid_w > glyph_height)
 206       grid_h--;
 207     glyph_height = grid_h * unit / grid_w;
 208     extents.max_y = extents.min_y + glyph_height;
 209   } else {
 210     while ((grid_w - 1) * unit / grid_h > glyph_width)
 211       grid_w--;
 212     glyph_width = grid_w * unit / grid_h;
 213     extents.max_x = extents.min_x + glyph_width;
 214   }
 215
 216   double cell_unit = unit / std::max (grid_w, grid_h);
 217
 218   std::vector<glyphy_rgba_t> tex_data;
 219   std::vector<glyphy_arc_endpoint_t> near_endpoints;
 220
 221   unsigned int header_length = grid_w * grid_h;
 222   unsigned int offset = header_length;
 223   tex_data.resize (header_length);
 224   Point origin = Point (extents.min_x, extents.min_y);
 225   unsigned int total_arcs = 0;
 226
 227   for (unsigned int row = 0; row < grid_h; row++)
 228     for (unsigned int col = 0; col < grid_w; col++)
 229     {
 230       Point cp0 = origin + Vector ((col + 0) * cell_unit, (row + 0) * cell_unit);
 231       Point cp1 = origin + Vector ((col + 1) * cell_unit, (row + 1) * cell_unit);
 232       near_endpoints.clear ();
 233
 234       int side;
 235       closest_arcs_to_cell (cp0, cp1,
 236                             faraway,
 237                             endpoints, num_endpoints,
 238                             near_endpoints,
 239                             &side);
 240
 241 #define QUANTIZE_X(X) (lround (MAX_X * ((X - extents.min_x) / glyph_width )))
 242 #define QUANTIZE_Y(Y) (lround (MAX_Y * ((Y - extents.min_y) / glyph_height)))
 243 #define DEQUANTIZE_X(X) (double (X) / MAX_X * glyph_width  + extents.min_x)
 244 #define DEQUANTIZE_Y(Y) (double (Y) / MAX_Y * glyph_height + extents.min_y)
 245 #define SNAP(P) (Point (DEQUANTIZE_X (QUANTIZE_X ((P).x)), DEQUANTIZE_Y (QUANTIZE_Y ((P).y))))
 246
 247       if (near_endpoints.size () == 2 && near_endpoints[1].d == 0) {
 248               Point c (extents.min_x + glyph_width * .5, extents.min_y + glyph_height * .5);
 249               Line line (SNAP (near_endpoints[0].p), SNAP (near_endpoints[1].p));
 250               line.c -= line.n * Vector (c);
 251               line.c /= unit;
 252               tex_data[row * grid_w + col] = line_encode (line);
 253               continue;
 254       }
 255
 256       /* If the arclist is two arcs that can be combined in encoding if reordered,
 257        * do that. */
 258       if (near_endpoints.size () == 4 &&
 259           std::isinf (near_endpoints[2].d) &&
 260           near_endpoints[0].p.x == near_endpoints[3].p.x &&
 261           near_endpoints[0].p.y == near_endpoints[3].p.y)
 262       {
 263               glyphy_arc_endpoint_t e0, e1, e2;
 264               e0 = near_endpoints[2];
 265               e1 = near_endpoints[3];
 266               e2 = near_endpoints[1];
 267               near_endpoints.resize (0);
 268               near_endpoints.push_back (e0);
 269               near_endpoints.push_back (e1);
 270               near_endpoints.push_back (e2);
 271       }
 272
 273       for (unsigned i = 0; i < near_endpoints.size (); i++) {
 274         glyphy_arc_endpoint_t &endpoint = near_endpoints[i];
 275         tex_data.push_back (arc_endpoint_encode (QUANTIZE_X(endpoint.p.x), QUANTIZE_Y(endpoint.p.y), endpoint.d));
 276       }
 277
 278       unsigned int current_endpoints = tex_data.size () - offset;
 279
 280       if (current_endpoints)
 281       {
 282         /* See if we can fulfill this cell by using already-encoded arcs */
 283         const glyphy_rgba_t *needle = &tex_data[offset];
 284         unsigned int needle_len = current_endpoints;
 285         const glyphy_rgba_t *haystack = &tex_data[header_length];
 286         unsigned int haystack_len = offset - header_length;
 287
 288         bool found = false;
 289         while (haystack_len >= needle_len) {
 290           /* Trick: we don't care about first endpoint's d value, so skip one
 291            * byte in comparison.  This works because arc_encode() packs the
 292            * d value in the first byte. */
 293           if (0 == memcmp (1 + (const char *) needle,
 294                            1 + (const char *) haystack,
 295                            needle_len * sizeof (*needle) - 1)) {
 296             found = true;
 297             break;
 298           }
 299           haystack++;
 300           haystack_len--;
 301         }
 302         if (found) {
 303           unsigned int new_offset = haystack - &tex_data[0];
 304           tex_data.resize (offset);
 305           haystack = needle = NULL; /* Invalidated by the resize. */
 306           offset = new_offset;
 307         }
 308       }
 309       else
 310         offset = 0;
 311
 312       tex_data[row * grid_w + col] = arc_list_encode (offset, current_endpoints, side);
 313       offset = tex_data.size ();
 314
 315       total_arcs += current_endpoints;
 316     }
 317
 318   if (avg_fetch_achieved)
 319     *avg_fetch_achieved = 1 + double (total_arcs) / (grid_w * grid_h);
 320
 321   *pextents = extents;
 322
 323   if (tex_data.size () > blob_size)
 324     return false;
 325
 326   memcpy (blob, &tex_data[0], tex_data.size () * sizeof(tex_data[0]));
 327   *output_len = tex_data.size ();
 328   *nominal_width = grid_w;
 329   *nominal_height = grid_h;
 330
 331   return true;
 332 }
 333
 334 #pragma GCC diagnostic pop