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
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"
30 using namespace GLyphy::Geometry;
34 glyphy_outline_reverse (glyphy_arc_endpoint_t *endpoints,
35 unsigned int num_endpoints)
40 // Shift the d's first
41 double d0 = endpoints[0].d;
42 for (unsigned int i = 0; i < num_endpoints - 1; i++)
43 endpoints[i].d = endpoints[i + 1].d == GLYPHY_INFINITY ? GLYPHY_INFINITY : -endpoints[i + 1].d;
44 endpoints[num_endpoints - 1].d = d0;
47 for (unsigned int i = 0, j = num_endpoints - 1; i < j; i++, j--) {
48 glyphy_arc_endpoint_t t = endpoints[i];
49 endpoints[i] = endpoints[j];
56 winding (const glyphy_arc_endpoint_t *endpoints,
57 unsigned int num_endpoints)
62 * - Find the lowest-x part of the contour,
63 * - If the point is an endpoint:
64 * o compare the angle of the incoming and outgoing edges of that point
65 * to find out whether it's CW or CCW,
66 * - Otherwise, compare the y of the two endpoints of the arc with lowest-x point.
70 * We can use a simpler algorithm here: Act as if arcs are lines, then use the
71 * triangle method to calculate the signed area of the contour and get the sign.
72 * It should work for all cases we care about. The only case failing would be
73 * that of two endpoints and two arcs. But we can even special-case that.
76 unsigned int corner = 1;
77 for (unsigned int i = 2; i < num_endpoints; i++)
78 if (endpoints[i].p.x < endpoints[corner].p.x ||
79 (endpoints[i].p.x == endpoints[corner].p.x &&
80 endpoints[i].p.y < endpoints[corner].p.y))
83 double min_x = endpoints[corner].p.x;
86 for (unsigned int i = 0; i < num_endpoints; i++) {
87 const glyphy_arc_endpoint_t &endpoint = endpoints[i];
88 if (endpoint.d == GLYPHY_INFINITY || endpoint.d == 0 /* arcs only, not lines */) {
92 Arc arc (p0, endpoint.p, endpoint.d);
95 Point c = arc.center ();
96 double r = arc.radius ();
97 if (c.x - r < min_x && arc.wedge_contains_point (c - Vector (r, 0))) {
105 // Corner is lowest-x. Find the tangents of the two arcs connected to the
106 // corner and compare the tangent angles to get contour direction.
107 const glyphy_arc_endpoint_t ethis = endpoints[corner];
108 const glyphy_arc_endpoint_t eprev = endpoints[corner - 1];
109 const glyphy_arc_endpoint_t enext = endpoints[corner < num_endpoints - 1 ? corner + 1 : 1];
110 double in = (-Arc (eprev.p, ethis.p, ethis.d).tangents ().second).angle ();
111 double out = (+Arc (ethis.p, enext.p, enext.d).tangents ().first ).angle ();
117 return endpoints[winner].d < 0;
125 categorize (double v, double ref)
127 return v < ref - GLYPHY_EPSILON ? -1 : v > ref + GLYPHY_EPSILON ? +1 : 0;
133 return fabs (v) < GLYPHY_EPSILON;
137 even_odd (const glyphy_arc_endpoint_t *c_endpoints,
138 unsigned int num_c_endpoints,
139 const glyphy_arc_endpoint_t *endpoints,
140 unsigned int num_endpoints)
145 * - For a point on the contour, draw a halfline in a direction
146 * (eg. decreasing x) to infinity,
147 * - Count how many times it crosses all other contours,
148 * - Pay special attention to points falling exactly on the halfline,
149 * specifically, they count as +.5 or -.5, depending the direction
152 * All this counting is extremely tricky:
154 * - Floating point equality cannot be relied on here,
155 * - Lots of arc analysis needed,
156 * - Without having a point that we know falls /inside/ the contour,
157 * there are legitimate cases that we simply cannot handle using
158 * this algorithm. For example, imagine the following glyph shape:
166 * If the glyph is defined as two outlines, and when analysing the
167 * inner outline we happen to pick the point denoted by 'o' for
168 * analysis, there simply is no way to differentiate this case from
169 * the following case:
180 * However, in one, the triangle should be filled in, and in the other
183 * One way to work around this may be to do the analysis for all endpoints
184 * on the outline and take majority. But even that can fail in more
185 * extreme yet legitimate cases, such as this one:
195 * The only correct algorithm I can think of requires a point that falls
196 * fully inside the outline. While we can try finding such a point (not
197 * dissimilar to the winding algorithm), it's beyond what I'm willing to
198 * implement right now.
201 const Point p = c_endpoints[0].p;
205 for (unsigned int i = 0; i < num_endpoints; i++) {
206 const glyphy_arc_endpoint_t &endpoint = endpoints[i];
207 if (endpoint.d == GLYPHY_INFINITY) {
211 Arc arc (p0, endpoint.p, endpoint.d);
215 * Skip our own contour
217 if (&endpoint >= c_endpoints && &endpoint < c_endpoints + num_c_endpoints)
220 /* End-point y's compared to the ref point; lt, eq, or gt */
221 unsigned s0 = categorize (arc.p0.y, p.y);
222 unsigned s1 = categorize (arc.p1.y, p.y);
231 * Add +.5 / -.5 for each endpoint on the halfline, depending on
232 * crossing direction.
234 Pair<Vector> t = arc.tangents ();
235 if (!s0 && arc.p0.x < p.x + GLYPHY_EPSILON)
236 count += .5 * categorize (t.first.dy, 0);
237 if (!s1 && arc.p1.x < p.x + GLYPHY_EPSILON)
238 count += .5 * categorize (t.second.dy, 0);
243 continue; // Segment fully above or below the halfline
245 // Find x pos that the line segment would intersect the half-line.
246 double x = arc.p0.x + (arc.p1.x - arc.p0.x) * ((p.y - arc.p0.y) / (arc.p1.y - arc.p0.y));
248 if (x >= p.x - GLYPHY_EPSILON)
249 continue; // Does not intersect halfline
251 count++; // Add one for full crossing
261 * Add +.5 / -.5 for each endpoint on the halfline, depending on
262 * crossing direction.
264 Pair<Vector> t = arc.tangents ();
266 /* Arc-specific logic:
267 * If the tangent has dy==0, use the other endpoint's
268 * y value to decide which way the arc will be heading.
270 if (is_zero (t.first.dy))
271 t.first.dy = +categorize (arc.p1.y, p.y);
272 if (is_zero (t.second.dy))
273 t.second.dy = -categorize (arc.p0.y, p.y);
275 if (!s0 && arc.p0.x < p.x + GLYPHY_EPSILON)
276 count += .5 * categorize (t.first.dy, 0);
277 if (!s1 && arc.p1.x < p.x + GLYPHY_EPSILON)
278 count += .5 * categorize (t.second.dy, 0);
281 Point c = arc.center ();
282 double r = arc.radius ();
284 continue; // No chance
285 /* Solve for arc crossing line with y = p.y */
286 double dy = p.y - c.y;
287 double x2 = r * r - dy * dy;
288 if (x2 <= GLYPHY_EPSILON)
289 continue; // Negative delta, no crossing
290 double dx = sqrt (x2);
291 /* There's two candidate points on the arc with the same y as the
293 Point pp[2] = { Point (c.x - dx, p.y),
294 Point (c.x + dx, p.y) };
296 #define POINTS_EQ(a,b) (is_zero (a.x - b.x) && is_zero (a.y - b.y))
297 for (unsigned int i = 0; i < ARRAY_LENGTH (pp); i++)
299 /* Make sure we don't double-count endpoints that fall on the
300 * halfline as we already accounted for those above */
301 if (!POINTS_EQ (pp[i], arc.p0) && !POINTS_EQ (pp[i], arc.p1) &&
302 pp[i].x < p.x - GLYPHY_EPSILON && arc.wedge_contains_point (pp[i]))
303 count++; // Add one for full crossing
309 return !(int (floor (count)) & 1);
313 process_contour (glyphy_arc_endpoint_t *endpoints,
314 unsigned int num_endpoints,
315 const glyphy_arc_endpoint_t *all_endpoints,
316 unsigned int num_all_endpoints,
322 * - Find the winding direction and even-odd number,
323 * - If the two disagree, reverse the contour, inplace.
329 if (num_endpoints < 3) {
330 abort (); // Don't expect this
331 return false; // Need at least two arcs
333 if (Point (endpoints[0].p) != Point (endpoints[num_endpoints-1].p)) {
334 abort (); // Don't expect this
335 return false; // Need a closed contour
339 winding (endpoints, num_endpoints) ^
340 even_odd (endpoints, num_endpoints, all_endpoints, num_all_endpoints))
342 glyphy_outline_reverse (endpoints, num_endpoints);
349 /* Returns true if outline was modified */
351 glyphy_outline_winding_from_even_odd (glyphy_arc_endpoint_t *endpoints,
352 unsigned int num_endpoints,
353 glyphy_bool_t inverse)
358 * - Process one contour at a time.
361 unsigned int start = 0;
363 for (unsigned int i = 1; i < num_endpoints; i++) {
364 const glyphy_arc_endpoint_t &endpoint = endpoints[i];
365 if (endpoint.d == GLYPHY_INFINITY) {
366 ret = ret | process_contour (endpoints + start, i - start, endpoints, num_endpoints, bool (inverse));
370 ret = ret | process_contour (endpoints + start, num_endpoints - start, endpoints, num_endpoints, bool (inverse));
374 #pragma GCC diagnostic pop