From 2afd347f508a3e30dd7065061c48f4f738e17934 Mon Sep 17 00:00:00 2001 From: Tor Lillqvist Date: Wed, 18 Nov 2015 15:12:30 +0200 Subject: Update GLyphy to match upstream Change-Id: Ia1fe3f5d44e2194f87f1b7655ee28148fb614e81 --- external/glyphy/UnpackedTarball_glyphy.mk | 1 + external/glyphy/glyphy-upstream.patch.1 | 211 ++++++++++++++++++++++++++++++ 2 files changed, 212 insertions(+) create mode 100644 external/glyphy/glyphy-upstream.patch.1 (limited to 'external') diff --git a/external/glyphy/UnpackedTarball_glyphy.mk b/external/glyphy/UnpackedTarball_glyphy.mk index 43a603df8ed2..08512b9a761f 100644 --- a/external/glyphy/UnpackedTarball_glyphy.mk +++ b/external/glyphy/UnpackedTarball_glyphy.mk @@ -14,6 +14,7 @@ $(eval $(call gb_UnpackedTarball_set_tarball,glyphy,$(GLYPHY_TARBALL))) $(eval $(call gb_UnpackedTarball_set_patchlevel,glyphy,1)) $(eval $(call gb_UnpackedTarball_add_patches,glyphy,\ + external/glyphy/glyphy-upstream.patch.1 \ external/glyphy/glyphy-windows.patch.1 \ )) diff --git a/external/glyphy/glyphy-upstream.patch.1 b/external/glyphy/glyphy-upstream.patch.1 new file mode 100644 index 000000000000..f898918f4c8f --- /dev/null +++ b/external/glyphy/glyphy-upstream.patch.1 @@ -0,0 +1,211 @@ +From d6d6c61c8d0e336c34ba3f5d9adbe923ffa1cbe3 Mon Sep 17 00:00:00 2001 +From: Behdad Esfahbod +Date: Thu, 6 Aug 2015 15:34:38 +0100 +Subject: [PATCH 2/6] Implement more robust winding-direction algorithm + +Fixes 'p' in Comic Sans Bold for example. That font has many +self-intersecting contours. The one in 'p' was causing complete +winding direction reversal using old algorithm. Implement area-based +algorithm. +--- + src/glyphy-outline.cc | 67 ++++++++++----------------------------------------- + 1 file changed, 13 insertions(+), 54 deletions(-) + +diff --git a/src/glyphy-outline.cc b/src/glyphy-outline.cc +index 3543f3b..ef71247 100644 +--- a/src/glyphy-outline.cc ++++ b/src/glyphy-outline.cc +@@ -55,65 +55,24 @@ winding (const glyphy_arc_endpoint_t *endpoints, + /* + * Algorithm: + * +- * - Find the lowest-x part of the contour, +- * - If the point is an endpoint: +- * o compare the angle of the incoming and outgoing edges of that point +- * to find out whether it's CW or CCW, +- * - Otherwise, compare the y of the two endpoints of the arc with lowest-x point. +- * +- * Note: +- * +- * We can use a simpler algorithm here: Act as if arcs are lines, then use the +- * triangle method to calculate the signed area of the contour and get the sign. +- * It should work for all cases we care about. The only case failing would be +- * that of two endpoints and two arcs. But we can even special-case that. ++ * - Approximate arcs with triangles passing through the mid- and end-points, ++ * - Calculate the area of the contour, ++ * - Return sign. + */ + +- unsigned int corner = 1; +- for (unsigned int i = 2; i < num_endpoints; i++) +- if (endpoints[i].p.x < endpoints[corner].p.x || +- (endpoints[i].p.x == endpoints[corner].p.x && +- endpoints[i].p.y < endpoints[corner].p.y)) +- corner = i; +- +- double min_x = endpoints[corner].p.x; +- int winner = -1; +- Point p0 (0, 0); +- for (unsigned int i = 0; i < num_endpoints; i++) { +- const glyphy_arc_endpoint_t &endpoint = endpoints[i]; +- if (endpoint.d == GLYPHY_INFINITY || endpoint.d == 0 /* arcs only, not lines */) { +- p0 = endpoint.p; +- continue; +- } +- Arc arc (p0, endpoint.p, endpoint.d); +- p0 = endpoint.p; ++ double area = 0; ++ for (unsigned int i = 1; i < num_endpoints; i++) ++ { ++ const glyphy_point_t &p0 = endpoints[i - 1].p; ++ const glyphy_point_t &p1 = endpoints[i].p; ++ double d = endpoints[i].d; + +- Point c = arc.center (); +- double r = arc.radius (); +- if (c.x - r < min_x && arc.wedge_contains_point (c - Vector (r, 0))) { +- min_x = c.x - r; +- winner = i; +- } +- } ++ assert (d != GLYPHY_INFINITY); + +- if (winner == -1) +- { +- // Corner is lowest-x. Find the tangents of the two arcs connected to the +- // corner and compare the tangent angles to get contour direction. +- const glyphy_arc_endpoint_t ethis = endpoints[corner]; +- const glyphy_arc_endpoint_t eprev = endpoints[corner - 1]; +- const glyphy_arc_endpoint_t enext = endpoints[corner < num_endpoints - 1 ? corner + 1 : 1]; +- double in = (-Arc (eprev.p, ethis.p, ethis.d).tangents ().second).angle (); +- double out = (+Arc (ethis.p, enext.p, enext.d).tangents ().first ).angle (); +- return out > in; ++ area += p0.x*p1.y - p0.y*p1.x; ++ area -= .5 * d * ((p1.x-p0.x)*(p1.x-p0.x) + (p1.y-p0.y)*(p1.y-p0.y)); + } +- else +- { +- // Easy. +- return endpoints[winner].d < 0; +- } +- +- return false; ++ return area < 0; + } + + +-- +2.5.0 + +From 644c5bab6e7f0e5af8f42fa7a8075372716c66d3 Mon Sep 17 00:00:00 2001 +From: Behdad Esfahbod +Date: Thu, 6 Aug 2015 15:49:37 +0100 +Subject: [PATCH 3/6] Start handling fully-degenerate curves + +--- + src/glyphy-arcs-bezier.hh | 7 +++++++ + src/glyphy-geometry.hh | 4 ++++ + 2 files changed, 11 insertions(+) + +diff --git a/src/glyphy-arcs-bezier.hh b/src/glyphy-arcs-bezier.hh +index ab729cb..32b7c8c 100644 +--- a/src/glyphy-arcs-bezier.hh ++++ b/src/glyphy-arcs-bezier.hh +@@ -103,6 +103,13 @@ class ArcsBezierApproximatorSpringSystem + double *perror, + unsigned int max_segments = 100) + { ++ /* Handle fully-degenerate cases. */ ++ Vector v1 (b.p1 - b.p0); ++ Vector v2 (b.p2 - b.p0); ++ Vector v3 (b.p3 - b.p0); ++ if (fabs (v1.cross(v2)) < GLYPHY_EPSILON && fabs (v2.cross(v3)) < GLYPHY_EPSILON) ++ ;//TODO ++ + std::vector t; + std::vector e; + double max_e, min_e; +diff --git a/src/glyphy-geometry.hh b/src/glyphy-geometry.hh +index f5f6003..3c60856 100644 +--- a/src/glyphy-geometry.hh ++++ b/src/glyphy-geometry.hh +@@ -99,6 +99,7 @@ struct Vector { + inline const Vector normal (void) const; /* ortho().normalized() */ + inline double angle (void) const; + ++ inline double cross (const Vector &other) const; + inline const Vector rebase (const Vector &bx, const Vector &by) const; + inline const Vector rebase (const Vector &bx) const; + +@@ -345,6 +346,9 @@ inline double Vector::angle (void) const { + return atan2 (dy, dx); + } + ++inline double Vector::cross (const Vector &other) const { ++ return dx * other.dy - dy * other.dx; ++} + inline const Vector Vector::rebase (const Vector &bx, + const Vector &by) const { + return Vector (*this * bx, *this * by); +-- +2.5.0 + +From 5667ab11a3d5f57bb89c4e8970d26b940d36964a Mon Sep 17 00:00:00 2001 +From: Behdad Esfahbod +Date: Thu, 6 Aug 2015 15:51:15 +0100 +Subject: [PATCH 4/6] Simplify winding() + +--- + src/glyphy-outline.cc | 4 ++-- + 1 file changed, 2 insertions(+), 2 deletions(-) + +diff --git a/src/glyphy-outline.cc b/src/glyphy-outline.cc +index ef71247..7fded28 100644 +--- a/src/glyphy-outline.cc ++++ b/src/glyphy-outline.cc +@@ -69,8 +69,8 @@ winding (const glyphy_arc_endpoint_t *endpoints, + + assert (d != GLYPHY_INFINITY); + +- area += p0.x*p1.y - p0.y*p1.x; +- area -= .5 * d * ((p1.x-p0.x)*(p1.x-p0.x) + (p1.y-p0.y)*(p1.y-p0.y)); ++ area += Vector(p0).cross (Vector(p1)); ++ area -= .5 * d * (Point(p1) - Point(p0)).len2 (); + } + return area < 0; + } +-- +2.5.0 + +From 16fa0a713295a76f3075e6732007dca2dd38d11e Mon Sep 17 00:00:00 2001 +From: Behdad Esfahbod +Date: Thu, 6 Aug 2015 16:00:19 +0100 +Subject: [PATCH 5/6] Better handle fully-degenerate curves + +--- + src/glyphy-arcs-bezier.hh | 9 ++++++++- + 1 file changed, 8 insertions(+), 1 deletion(-) + +diff --git a/src/glyphy-arcs-bezier.hh b/src/glyphy-arcs-bezier.hh +index 32b7c8c..ac210c0 100644 +--- a/src/glyphy-arcs-bezier.hh ++++ b/src/glyphy-arcs-bezier.hh +@@ -108,7 +108,14 @@ class ArcsBezierApproximatorSpringSystem + Vector v2 (b.p2 - b.p0); + Vector v3 (b.p3 - b.p0); + if (fabs (v1.cross(v2)) < GLYPHY_EPSILON && fabs (v2.cross(v3)) < GLYPHY_EPSILON) +- ;//TODO ++ { ++ /* Curve has no area. If endpoints are NOT the same, replace with single ++ * line segment. Otherwise fully skip. */ ++ arcs.clear (); ++ if (b.p0 != b.p1) ++ arcs.push_back (Arc (b.p0, b.p1, 0)); ++ return; ++ } + + std::vector t; + std::vector e; +-- +2.5.0 + -- cgit