2 * Copyright 2012 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, Wojciech Baranowski
23 // Glyphy is written using C style casts
24 #pragma GCC diagnostic push
25 #pragma GCC diagnostic ignored "-Wold-style-cast"
27 #include "glyphy-common.hh"
28 #include "glyphy-geometry.hh"
32 using namespace GLyphy::Geometry;
35 #define UPPER_BITS(v,bits,total_bits) ((v) >> ((total_bits) - (bits)))
36 #define LOWER_BITS(v,bits,total_bits) ((v) & ((1 << (bits)) - 1))
41 static inline glyphy_rgba_t
42 arc_endpoint_encode (unsigned int ix, unsigned int iy, double d)
46 /* 12 bits for each of x and y, 8 bits for d */
53 assert (fabs (d) <= GLYPHY_MAX_D);
54 id = 128 + lround (d * 127 / GLYPHY_MAX_D);
59 v.g = LOWER_BITS (ix, 8, 12);
60 v.b = LOWER_BITS (iy, 8, 12);
61 v.a = ((ix >> 8) << 4) | (iy >> 8);
65 static inline glyphy_rgba_t
66 arc_list_encode (unsigned int offset, unsigned int num_points, int side)
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)
78 static inline glyphy_rgba_t
79 line_encode (const Line &line)
81 Line l = line.normalized ();
82 double angle = l.n.angle ();
83 double distance = l.c;
85 int ia = lround (-angle / M_PI * 0x7FFF);
86 unsigned int ua = ia + 0x8000;
87 assert (0 == (ua & ~0xFFFF));
89 int id = lround (distance * 0x1FFF);
90 unsigned int ud = id + 0x4000;
91 assert (0 == (ud & ~0x7FFF));
93 /* Marker for line-encoded */
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.
109 closest_arcs_to_cell (Point c0, Point c1, /* corners */
111 const glyphy_arc_endpoint_t *endpoints,
112 unsigned int num_endpoints,
113 std::vector<glyphy_arc_endpoint_t> &near_endpoints,
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);
120 *side = min_dist >= 0 ? +1 : -1;
121 min_dist = fabs (min_dist);
122 std::vector<Arc> near_arcs;
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) {
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) {
136 Arc arc (p0, endpoint.p, endpoint.d);
139 if (arc.squared_distance_to_point (c) <= radius_squared)
140 near_arcs.push_back (arc);
144 Point p1 = Point (0, 0);
145 for (unsigned i = 0; i < near_arcs.size (); i++)
147 Arc arc = near_arcs[i];
149 if (i == 0 || p1 != arc.p0) {
150 glyphy_arc_endpoint_t endpoint = {arc.p0, GLYPHY_INFINITY};
151 near_endpoints.push_back (endpoint);
155 glyphy_arc_endpoint_t endpoint = {arc.p1, arc.d};
156 near_endpoints.push_back (endpoint);
163 glyphy_arc_list_encode_blob (const glyphy_arc_endpoint_t *endpoints,
164 unsigned int num_endpoints,
166 unsigned int blob_size,
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)
175 glyphy_extents_t extents;
176 glyphy_extents_clear (&extents);
178 glyphy_arc_list_extents (endpoints, num_endpoints, &extents);
180 if (glyphy_extents_is_empty (&extents)) {
184 *blob = arc_list_encode (0, 0, +1);
185 *avg_fetch_achieved = 1;
187 *nominal_width = *nominal_height = 1;
191 /* Add antialiasing padding */
192 extents.min_x -= faraway;
193 extents.min_y -= faraway;
194 extents.max_x += faraway;
195 extents.max_y += faraway;
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);
201 unsigned int grid_w = GRID_SIZE;
202 unsigned int grid_h = GRID_SIZE;
204 if (glyph_width > glyph_height) {
205 while ((grid_h - 1) * unit / grid_w > glyph_height)
207 glyph_height = grid_h * unit / grid_w;
208 extents.max_y = extents.min_y + glyph_height;
210 while ((grid_w - 1) * unit / grid_h > glyph_width)
212 glyph_width = grid_w * unit / grid_h;
213 extents.max_x = extents.min_x + glyph_width;
216 double cell_unit = unit / std::max (grid_w, grid_h);
218 std::vector<glyphy_rgba_t> tex_data;
219 std::vector<glyphy_arc_endpoint_t> near_endpoints;
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;
227 for (unsigned int row = 0; row < grid_h; row++)
228 for (unsigned int col = 0; col < grid_w; col++)
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 ();
235 closest_arcs_to_cell (cp0, cp1,
237 endpoints, num_endpoints,
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))))
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);
252 tex_data[row * grid_w + col] = line_encode (line);
256 /* If the arclist is two arcs that can be combined in encoding if reordered,
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)
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);
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));
278 unsigned int current_endpoints = tex_data.size () - offset;
280 if (current_endpoints)
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;
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)) {
303 unsigned int new_offset = haystack - &tex_data[0];
304 tex_data.resize (offset);
305 haystack = needle = NULL; /* Invalidated by the resize. */
312 tex_data[row * grid_w + col] = arc_list_encode (offset, current_endpoints, side);
313 offset = tex_data.size ();
315 total_arcs += current_endpoints;
318 if (avg_fetch_achieved)
319 *avg_fetch_achieved = 1 + double (total_arcs) / (grid_w * grid_h);
323 if (tex_data.size () > blob_size)
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;
334 #pragma GCC diagnostic pop