1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
From d6d6c61c8d0e336c34ba3f5d9adbe923ffa1cbe3 Mon Sep 17 00:00:00 2001
From: Behdad Esfahbod <behdad@behdad.org>
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 <behdad@behdad.org>
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<double> t;
std::vector<double> 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 <behdad@behdad.org>
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 <behdad@behdad.org>
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<double> t;
std::vector<double> e;
--
2.5.0
|
