third-party/glyphy/glyphy-outline.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
  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 using namespace GLyphy::Geometry;
  31
  32
  33 void
  34 glyphy_outline_reverse (glyphy_arc_endpoint_t *endpoints,
  35                         unsigned int           num_endpoints)
  36 {
  37   if (!num_endpoints)
  38     return;
  39
  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;
  45
  46   // Reverse
  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];
  50     endpoints[j] = t;
  51   }
  52 }
  53
  54
  55 static bool
  56 winding (const glyphy_arc_endpoint_t *endpoints,
  57          unsigned int                 num_endpoints)
  58 {
  59   /*
  60    * Algorithm:
  61    *
  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.
  67    *
  68    * Note:
  69    *
  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.
  74    */
  75
  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))
  81       corner = i;
  82
  83   double min_x = endpoints[corner].p.x;
  84   int winner = -1;
  85   Point p0 (0, 0);
  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 */) {
  89       p0 = endpoint.p;
  90       continue;
  91     }
  92     Arc arc (p0, endpoint.p, endpoint.d);
  93     p0 = endpoint.p;
  94
  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))) {
  98       min_x = c.x - r;
  99       winner = i;
 100     }
 101   }
 102
 103   if (winner == -1)
 104   {
 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 ();
 112     return out > in;
 113   }
 114   else
 115   {
 116     // Easy.
 117     return endpoints[winner].d < 0;
 118   }
 119
 120   return false;
 121 }
 122
 123
 124 static int
 125 categorize (double v, double ref)
 126 {
 127   return v < ref - GLYPHY_EPSILON ? -1 : v > ref + GLYPHY_EPSILON ? +1 : 0;
 128 }
 129
 130 static bool
 131 is_zero (double v)
 132 {
 133   return fabs (v) < GLYPHY_EPSILON;
 134 }
 135
 136 static bool
 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)
 141 {
 142   /*
 143    * Algorithm:
 144    *
 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
 150    *   of crossing.
 151    *
 152    * All this counting is extremely tricky:
 153    *
 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:
 159    *
 160    *         +---------+
 161    *         | +-----+ |
 162    *         |  \   /  |
 163    *         |   \ /   |
 164    *         +----o----+
 165    *
 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:
 170    *
 171    *         +---------+
 172    *         |         |
 173    *         |         |
 174    *         |         |
 175    *         +----o----+
 176    *             / \
 177    *            /   \
 178    *           +-----+
 179    *
 180    *   However, in one, the triangle should be filled in, and in the other
 181    *   filled out.
 182    *
 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:
 186    *
 187    *           +--+--+
 188    *           | / \ |
 189    *           |/   \|
 190    *           +     +
 191    *           |\   /|
 192    *           | \ / |
 193    *           +--o--+
 194    *
 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.
 199    */
 200
 201   const Point p = c_endpoints[0].p;
 202
 203   double count = 0;
 204   Point p0 (0, 0);
 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) {
 208       p0 = endpoint.p;
 209       continue;
 210     }
 211     Arc arc (p0, endpoint.p, endpoint.d);
 212     p0 = endpoint.p;
 213
 214     /*
 215      * Skip our own contour
 216      */
 217     if (&endpoint >= c_endpoints && &endpoint < c_endpoints + num_c_endpoints)
 218       continue;
 219
 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);
 223
 224     if (is_zero (arc.d))
 225     {
 226       /* Line */
 227
 228       if (!s0 || !s1)
 229       {
 230         /*
 231          * Add +.5 / -.5 for each endpoint on the halfline, depending on
 232          * crossing direction.
 233          */
 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);
 239         continue;
 240       }
 241
 242       if (s0 == s1)
 243         continue; // Segment fully above or below the halfline
 244
 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));
 247
 248       if (x >= p.x - GLYPHY_EPSILON)
 249         continue; // Does not intersect halfline
 250
 251       count++; // Add one for full crossing
 252       continue;
 253     }
 254     else
 255     {
 256       /* Arc */
 257
 258       if (!s0 || !s1)
 259       {
 260         /*
 261          * Add +.5 / -.5 for each endpoint on the halfline, depending on
 262          * crossing direction.
 263          */
 264         Pair<Vector> t = arc.tangents ();
 265
 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.
 269          */
 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);
 274
 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);
 279       }
 280
 281       Point c = arc.center ();
 282       double r = arc.radius ();
 283       if (c.x - r >= p.x)
 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
 292        * ref point. */
 293       Point pp[2] = { Point (c.x - dx, p.y),
 294                       Point (c.x + dx, p.y) };
 295
 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++)
 298       {
 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
 304       }
 305 #undef POINTS_EQ
 306     }
 307   }
 308
 309   return !(int (floor (count)) & 1);
 310 }
 311
 312 static bool
 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,
 317                  bool                         inverse)
 318 {
 319   /*
 320    * Algorithm:
 321    *
 322    * - Find the winding direction and even-odd number,
 323    * - If the two disagree, reverse the contour, inplace.
 324    */
 325
 326   if (!num_endpoints)
 327     return false;
 328
 329   if (num_endpoints < 3) {
 330     abort (); // Don't expect this
 331     return false; // Need at least two arcs
 332   }
 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
 336    }
 337
 338   if (inverse ^
 339       winding (endpoints, num_endpoints) ^
 340       even_odd (endpoints, num_endpoints, all_endpoints, num_all_endpoints))
 341   {
 342     glyphy_outline_reverse (endpoints, num_endpoints);
 343     return true;
 344   }
 345
 346   return false;
 347 }
 348
 349 /* Returns true if outline was modified */
 350 glyphy_bool_t
 351 glyphy_outline_winding_from_even_odd (glyphy_arc_endpoint_t *endpoints,
 352                                       unsigned int           num_endpoints,
 353                                       glyphy_bool_t          inverse)
 354 {
 355   /*
 356    * Algorithm:
 357    *
 358    * - Process one contour at a time.
 359    */
 360
 361   unsigned int start = 0;
 362   bool ret = false;
 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));
 367       start = i;
 368     }
 369   }
 370   ret = ret | process_contour (endpoints + start, num_endpoints - start, endpoints, num_endpoints, bool (inverse));
 371   return ret;
 372 }
 373
 374 #pragma GCC diagnostic pop