1 /* Copyright (C) 2001-2006 Artifex Software, Inc.
2 All Rights Reserved.
3
4 This software is provided AS-IS with no warranty, either express or
5 implied.
6
7 This software is distributed under license and may not be copied, modified
8 or distributed except as expressly authorized under the terms of that
9 license. Refer to licensing information at http://www.artifex.com/
10 or contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134,
11 San Rafael, CA 94903, U.S.A., +1(415)492-9861, for further information.
12 */
13
14 /* $Id: gxhintn1.c 8250 2007-09-25 13:31:24Z giles $ */
15 /* A stuff for reconnizing and fixing wrong contour signs. */
16
17 #include "memory_.h"
18 #include "math_.h"
19 #include "gx.h"
20 #include "gxfixed.h"
21 #include "gxarith.h"
22 #include "gstypes.h"
23 #include "gxmatrix.h"
24 #include "gxhintn.h"
25 #include "gzpath.h"
26 #include "vdtrace.h"
27
28 #define CURVE_FLATTENING (fixed_1) /* Design units in 'fixed'. */
29
line_area_2(fixed p0x,fixed p0y,fixed p1x,fixed p1y)30 static double inline line_area_2(fixed p0x, fixed p0y, fixed p1x, fixed p1y)
31 { /* Returns area * 2.*/
32 return ((double)p0x*p1y - (double)p0y*p1x);
33 }
34
bezier_area_2(fixed p0x,fixed p0y,fixed p1x,fixed p1y,fixed p2x,fixed p2y,fixed p3x,fixed p3y)35 static double inline bezier_area_2(fixed p0x, fixed p0y, fixed p1x, fixed p1y,
36 fixed p2x, fixed p2y, fixed p3x, fixed p3y)
37 { /* Returns area * 2.*/
38 return (-(p0y*(6.0*p1x + 3.0*p2x + p3x)) + p0x*(6.0*p1y + 3.0*p2y + p3y) -
39 3*((double)p1y*p2x + (double)p1y*p3x + 2.0*p2y*p3x - 2.0*p2x*p3y - (double)p1x*(p2y + p3y)))/10;
40 }
41
t1_hinter__reverse_contour(t1_hinter * this,int c)42 static void t1_hinter__reverse_contour(t1_hinter * this, int c)
43 {
44 int b = this->contour[c];
45 int e = this->contour[c + 1] - 1; /* Skip 'close'. */
46 int e2 = (b + e + 1) / 2;
47 int i;
48 t1_pole p;
49
50 /* Reverse all except endpoint ('close') : */
51 for (i = b + 1; i < e2; i++) {
52 int j = e - (i - b);
53
54 p = this->pole[i];
55 this->pole[i] = this->pole[j];
56 this->pole[j] = p;
57 }
58 }
59
60 #define CONTACT_SIGNAL -100000.0
61
bar_winding_angle(fixed x0,fixed y0,fixed x1,fixed y1)62 static double inline bar_winding_angle(fixed x0, fixed y0, fixed x1, fixed y1)
63 {
64 double vp = (double)x0 * y1 - (double)y0 * x1;
65 double sp = (double)x0 * x1 + (double)y0 * y1;
66 double A;
67
68 if (sp == 0) {
69 if (vp == 0)
70 return CONTACT_SIGNAL; /* Contours contact. */
71 A = 1.57079632679489661923; /* pi/2. */
72 if (vp < 0)
73 A = -A;
74 } else
75 A = atan2(vp, sp);
76 return A;
77 }
78
79 static double
curve_winding_angle_rec(int k,fixed x0,fixed y0,fixed x1,fixed y1,fixed x2,fixed y2,fixed x3,fixed y3)80 curve_winding_angle_rec(int k, fixed x0, fixed y0, fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3)
81 {
82 if (k <= 1)
83 return bar_winding_angle(x0, y0, x3, y3);
84 else {
85 /* Assuming the trapezoid is not self-intersecting and
86 the curve is inside the trapezoid
87 due to Type 1 constraints. */
88 double a0 = bar_winding_angle(x0, y0, x1, y1);
89 double a1 = bar_winding_angle(x1, y1, x2, y2);
90 double a2 = bar_winding_angle(x2, y2, x3, y3);
91 double a3 = bar_winding_angle(x3, y3, x0, y0);
92 double a = a0 + a1 + a2 + a3;
93
94 if (any_abs(a) < 0.1 && a0 != CONTACT_SIGNAL &&
95 a1 != CONTACT_SIGNAL &&
96 a2 != CONTACT_SIGNAL &&
97 a3 != CONTACT_SIGNAL) {
98 /* The center is outside the trapezoid. */
99 return -a3;
100 } else {
101 fixed x01 = (x0 + x1) / 2, y01 = (y0 + y1) / 2;
102 fixed x12 = (x1 + x2) / 2, y12 = (y1 + y2) / 2;
103 fixed x23 = (x2 + x3) / 2, y23 = (y2 + y3) / 2;
104 fixed x012 = (x01 + x12) / 2, y012 = (y01 + y12) / 2;
105 fixed x123 = (x12 + x23) / 2, y123 = (y12 + y23) / 2;
106 fixed x0123 = (x012 + x123) / 2, y0123 = (y012 + y123) / 2;
107 double A0, A1;
108
109 A0 = curve_winding_angle_rec(k - 1, x0, y0, x01, y01, x012, y012, x0123, y0123);
110 if (A0 == CONTACT_SIGNAL)
111 return CONTACT_SIGNAL;
112 A1 = curve_winding_angle_rec(k - 1, x0123, y0123, x123, y123, x23, y23, x3, y3);
113 if (A1 == CONTACT_SIGNAL)
114 return CONTACT_SIGNAL;
115 return A0 + A1;
116 }
117 }
118 }
119
curve_log2_samples(fixed x0,fixed y0,fixed x1,fixed y1,fixed x2,fixed y2,fixed x3,fixed y3)120 static int curve_log2_samples(fixed x0, fixed y0, fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3)
121 {
122 curve_segment s;
123
124 s.p1.x = x1;
125 s.p1.y = y1;
126 s.p2.x = x2;
127 s.p2.y = y2;
128 s.pt.x = x3;
129 s.pt.y = y3;
130 return gx_curve_log2_samples(x0, y0, &s, (fixed)CURVE_FLATTENING);
131 }
132
curve_winding_angle(fixed x0,fixed y0,fixed x1,fixed y1,fixed x2,fixed y2,fixed x3,fixed y3)133 static double curve_winding_angle(fixed x0, fixed y0, fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3)
134 {
135 int k = curve_log2_samples(x0, y0, x1, y1, x2, y2, x3, y3);
136
137 return curve_winding_angle_rec(k, x0, y0, x1, y1, x2, y2, x3, y3);
138 }
139
t1_hinter__is_inside(t1_hinter * this,t1_glyph_space_coord gx,t1_glyph_space_coord gy,int c)140 static int t1_hinter__is_inside(t1_hinter * this, t1_glyph_space_coord gx, t1_glyph_space_coord gy, int c)
141 {
142 int b = this->contour[c];
143 int e = this->contour[c + 1] - 1;
144 double a = 0, A;
145 int i;
146
147 for (i = b; i < e;) {
148 if (this->pole[i + 1].type != offcurve) { /* line or close. */
149 A = bar_winding_angle(this->pole[i + 0].gx - gx, this->pole[i + 0].gy - gy,
150 this->pole[i + 1].gx - gx, this->pole[i + 1].gy - gy);
151 i++;
152 } else {
153 A = curve_winding_angle(this->pole[i + 0].gx - gx, this->pole[i + 0].gy - gy,
154 this->pole[i + 1].gx - gx, this->pole[i + 1].gy - gy,
155 this->pole[i + 2].gx - gx, this->pole[i + 2].gy - gy,
156 this->pole[i + 3].gx - gx, this->pole[i + 3].gy - gy);
157 i += 3;
158 }
159 if (A == CONTACT_SIGNAL)
160 return -1;
161 a += A;
162 }
163 if (any_abs(a) < 0.1)
164 return 0;
165 return 1;
166 }
167
168 static inline bool
intersect_bar_bar(fixed q0x,fixed q0y,fixed q1x,fixed q1y,fixed q2x,fixed q2y,fixed q3x,fixed q3y)169 intersect_bar_bar(fixed q0x, fixed q0y, fixed q1x, fixed q1y, fixed q2x, fixed q2y, fixed q3x, fixed q3y)
170 {
171 if (q1x == q0x && q1y == q0y)
172 return false;
173 if (q1x == q2x && q1y == q2y)
174 return false;
175 if (q0x == q2x && q0y == q2y)
176 return true;
177 if (q0x == q3x && q0y == q3y)
178 return true;
179 if (q1x == q2x && q1y == q2y)
180 return true;
181 if (q1x == q3x && q1y == q3y)
182 return true;
183 else {
184 fixed dx1 = q1x - q0x;
185 fixed dy1 = q1y - q0y;
186 fixed dx2 = q2x - q0x;
187 fixed dy2 = q2y - q0y;
188 fixed dx3 = q3x - q0x;
189 fixed dy3 = q3y - q0y;
190 fixed dx1a = any_abs(dx1);
191 fixed dy1a = any_abs(dy1);
192 fixed dx2a = any_abs(dx2);
193 fixed dy2a = any_abs(dy2);
194 fixed dx3a = any_abs(dx3);
195 fixed dy3a = any_abs(dy3);
196 fixed d = dx1a | dy1a | dx2a | dy2a | dx3a | dy3a;
197 fixed ry, ey; /* stubs only - don't use them, they are whong here. */
198
199 /* gx_intersect_small_bars needs cubes of distances to fit into 62 bits,
200 Drop extra bits here.
201 We don't need ry, so don't bother with absolute coordinates. */
202 while (d >= (1 << (60 / 3))) {
203 d >>= 1;
204 dx1 = (dx1 + 1) / 2;
205 dy1 = (dy1 + 1) / 2;
206 dx2 = (dy2 + 1) / 2;
207 dy2 = (dy2 + 1) / 2;
208 dx3 = (dy3 + 1) / 2;
209 dy3 = (dy3 + 1) / 2;
210 }
211 /* Well, when we drop bits, the intersection isn't precise.
212 But it happens with big characters only,
213 which unlikely have close oncurve poles
214 which belong to different contours.
215 Due to that we believe the boolean result is precise
216 with a very high probablility. */
217 return gx_intersect_small_bars(0, 0, dx1, dy1, dx2, dy2, dx3, dy3, &ry, &ey);
218 }
219 }
220
221 static inline bool
t1_hinter__intersect_bar_bar(t1_hinter * this,int i,int j)222 t1_hinter__intersect_bar_bar(t1_hinter * this, int i, int j)
223 {
224 fixed q0x = this->pole[i + 0].gx;
225 fixed q0y = this->pole[i + 0].gy;
226 fixed q1x = this->pole[i + 1].gx;
227 fixed q1y = this->pole[i + 1].gy;
228 fixed q2x = this->pole[j + 0].gx;
229 fixed q2y = this->pole[j + 0].gy;
230 fixed q3x = this->pole[j + 1].gx;
231 fixed q3y = this->pole[j + 1].gy;
232
233 return intersect_bar_bar(q0x, q0y, q1x, q1y, q2x, q2y, q3x, q3y);
234 }
235
intersect_curve_bar_rec(int m,int k,fixed X1,fixed Y1,fixed x0,fixed y0,fixed x1,fixed y1,fixed x2,fixed y2,fixed x3,fixed y3)236 static bool intersect_curve_bar_rec(int m, int k, fixed X1, fixed Y1,
237 fixed x0, fixed y0, fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3)
238 {
239 if (m <= 1)
240 return intersect_bar_bar(0, 0, X1, Y1, x0, y0, x3, y3);
241 else {
242 gs_rect box0, box1;
243
244 if (X1 < 0)
245 box0.p.x = X1, box0.q.x = 0;
246 else
247 box0.p.x = 0, box0.q.x = X1;
248 if (Y1 < 0)
249 box0.p.y = Y1, box0.q.y = 0;
250 else
251 box0.p.y = 0, box0.q.y = Y1;
252
253 box1.p.x = box1.q.x = x0;
254 box1.p.y = box1.q.y = y0;
255 if (box1.p.x > x1)
256 box1.p.x = x1;
257 if (box1.q.x < x1)
258 box1.q.x = x1;
259 if (box1.p.y > y1)
260 box1.p.y = y1;
261 if (box1.q.y < y1)
262 box1.q.y = y1;
263 if (box1.p.x > x2)
264 box1.p.x = x2;
265 if (box1.q.x < x2)
266 box1.q.x = x2;
267 if (box1.p.y > y2)
268 box1.p.y = y2;
269 if (box1.q.y < y2)
270 box1.q.y = y2;
271 if (box1.p.x > x3)
272 box1.p.x = x3;
273 if (box1.q.x < x3)
274 box1.q.x = x3;
275 if (box1.p.y > y3)
276 box1.p.y = y3;
277 if (box1.q.y < y3)
278 box1.q.y = y3;
279 if (box0.p.x > box1.q.x)
280 return false;
281 if (box0.q.x < box1.p.x)
282 return false;
283 if (box0.p.y > box1.q.y)
284 return false;
285 if (box0.q.y < box1.p.y)
286 return false;
287 }
288 { fixed x01 = (x0 + x1) / 2, y01 = (y0 + y1) / 2;
289 fixed x12 = (x1 + x2) / 2, y12 = (y1 + y2) / 2;
290 fixed x23 = (x2 + x3) / 2, y23 = (y2 + y3) / 2;
291 fixed x012 = (x01 + x12) / 2, y012 = (y01 + y12) / 2;
292 fixed x123 = (x12 + x23) / 2, y123 = (y12 + y23) / 2;
293 fixed x0123 = (x012 + x123) / 2, y0123 = (y012 + y123) / 2;
294
295 if (k <= 1) {
296 if (intersect_curve_bar_rec(m - 1, k, X1, Y1, x0, y0, x01, y01, x012, y012, x0123, y0123))
297 return true;
298 if (intersect_curve_bar_rec(m - 1, k, X1, Y1, x0123, y0123, x123, y123, x23, y23, x3, y3))
299 return true;
300 } else {
301 fixed X01 = X1 / 2;
302 fixed Y01 = Y1 / 2;
303
304 if (intersect_curve_bar_rec(m - 1, k - 1, X01, Y01, x0, y0, x01, y01, x012, y012, x0123, y0123))
305 return true;
306 if (intersect_curve_bar_rec(m - 1, k - 1, X01, Y01, x0123, y0123, x123, y123, x23, y23, x3, y3))
307 return true;
308 if (intersect_curve_bar_rec(m - 1, k - 1, X1 - X01, Y1 - Y01, x0 - X01, y0 - Y01, x01 - X01, y01 - Y01,
309 x012 - X01, y012 - Y01, x0123 - X01, y0123 - Y01))
310 return true;
311 if (intersect_curve_bar_rec(m - 1, k - 1, X1 - X01, Y1 - Y01, x0123 - X01, y0123 - Y01,
312 x123 - X01, y123 - Y01, x23 - X01, y23 - Y01, x3 - X01, y3 - Y01))
313 return true;
314 }
315 }
316 return false;
317 }
318
bar_samples(fixed dx,fixed dy)319 static int bar_samples(fixed dx, fixed dy)
320 {
321 int l = (any_abs(dx) | any_abs(dy)) / CURVE_FLATTENING, m = 0;
322 while (l) {
323 l >>= 1;
324 m++;
325 }
326 return m;
327 }
328
t1_hinter__intersect_curve_bar(t1_hinter * this,int i,int j)329 static bool t1_hinter__intersect_curve_bar(t1_hinter * this, int i, int j)
330 {
331 fixed X0 = this->pole[j].gx;
332 fixed Y0 = this->pole[j].gy;
333 fixed X1 = this->pole[j + 1].gx - X0;
334 fixed Y1 = this->pole[j + 1].gy - Y0;
335 fixed x0 = this->pole[i].gx - X0;
336 fixed y0 = this->pole[i].gy - Y0;
337 fixed x1 = this->pole[i + 1].gx - X0;
338 fixed y1 = this->pole[i + 1].gy - Y0;
339 fixed x2 = this->pole[i + 2].gx - X0;
340 fixed y2 = this->pole[i + 2].gy - Y0;
341 fixed x3 = this->pole[i + 3].gx - X0;
342 fixed y3 = this->pole[i + 3].gy - Y0;
343 int k = curve_log2_samples(0, 0, x1, y1, x2, y2, x3, y3);
344 int m = bar_samples(X1, Y1);
345
346 return intersect_curve_bar_rec(m, k, X1, Y1, x0, y0, x1, y1, x2, y2, x3, y3);
347 }
348
intersect_curve_curve_rec(int ka,int kb,fixed ax0,fixed ay0,fixed ax1,fixed ay1,fixed ax2,fixed ay2,fixed ax3,fixed ay3,fixed bx0,fixed by0,fixed bx1,fixed by1,fixed bx2,fixed by2,fixed bx3,fixed by3)349 static bool intersect_curve_curve_rec(int ka, int kb,
350 fixed ax0, fixed ay0, fixed ax1, fixed ay1, fixed ax2, fixed ay2, fixed ax3, fixed ay3,
351 fixed bx0, fixed by0, fixed bx1, fixed by1, fixed bx2, fixed by2, fixed bx3, fixed by3)
352 {
353 if (ka <= 1 && kb <= 1)
354 return intersect_bar_bar(ax0, ay0, ax3, ay3, bx0, by0, bx3, by3);
355 else if (ka <= 1) {
356 int m = bar_samples(ax3 - ax0, ay3 - ay0);
357
358 return intersect_curve_bar_rec(m, kb, ax3 - ax0, ay3 - ay0,
359 bx0 - ax0, by0 - ay0, bx1 - ax0, by1 - ay0, bx2 - ax0, by2 - ay0, bx3 - ax0, by3 - ay0);
360 } else if (kb <= 1) {
361 int m = bar_samples(bx3 - bx0, by3 - by0);
362
363 return intersect_curve_bar_rec(m, ka, bx3 - bx0, by3 - by0,
364 ax0 - bx0, ay0 - by0, ax1 - bx0, ay1 - by0, ax2 - bx0, ay2 - by0, ax3 - bx0, ay3 - by0);
365 } else {
366 gs_rect box0, box1;
367
368 box0.p.x = box0.q.x = ax0;
369 box0.p.y = box0.q.y = ay0;
370 if (box0.p.x > ax1)
371 box0.p.x = ax1;
372 if (box0.q.x < ax1)
373 box0.q.x = ax1;
374 if (box0.p.y > ay1)
375 box0.p.y = ay1;
376 if (box0.q.y < ay1)
377 box0.q.y = ay1;
378 if (box0.p.x > ax2)
379 box0.p.x = ax2;
380 if (box0.q.x < ax2)
381 box0.q.x = ax2;
382 if (box0.p.y > ay2)
383 box0.p.y = ay2;
384 if (box0.q.y < ay2)
385 box0.q.y = ay2;
386 if (box0.p.x > ax3)
387 box0.p.x = ax3;
388 if (box0.q.x < ax3)
389 box0.q.x = ax3;
390 if (box0.p.y > ay3)
391 box0.p.y = ay3;
392 if (box0.q.y < ay3)
393 box0.q.y = ay3;
394 box1.p.x = box1.q.x = bx0;
395 box1.p.y = box1.q.y = by0;
396 if (box1.p.x > bx1)
397 box1.p.x = bx1;
398 if (box1.q.x < bx1)
399 box1.q.x = bx1;
400 if (box1.p.y > by1)
401 box1.p.y = by1;
402 if (box1.q.y < by1)
403 box1.q.y = by1;
404 if (box1.p.x > bx2)
405 box1.p.x = bx2;
406 if (box1.q.x < bx2)
407 box1.q.x = bx2;
408 if (box1.p.y > by2)
409 box1.p.y = by2;
410 if (box1.q.y < by2)
411 box1.q.y = by2;
412 if (box1.p.x > bx3)
413 box1.p.x = bx3;
414 if (box1.q.x < bx3)
415 box1.q.x = bx3;
416 if (box1.p.y > by3)
417 box1.p.y = by3;
418 if (box1.q.y < by3)
419 box1.q.y = by3;
420 if (box0.p.x > box1.q.x)
421 return false;
422 if (box0.q.x < box1.p.x)
423 return false;
424 if (box0.p.y > box1.q.y)
425 return false;
426 if (box0.q.y < box1.p.y)
427 return false;
428 }
429 { fixed ax01 = (ax0 + ax1) / 2, ay01 = (ay0 + ay1) / 2;
430 fixed ax12 = (ax1 + ax2) / 2, ay12 = (ay1 + ay2) / 2;
431 fixed ax23 = (ax2 + ax3) / 2, ay23 = (ay2 + ay3) / 2;
432 fixed ax012 = (ax01 + ax12) / 2, ay012 = (ay01 + ay12) / 2;
433 fixed ax123 = (ax12 + ax23) / 2, ay123 = (ay12 + ay23) / 2;
434 fixed ax0123 = (ax012 + ax123) / 2, ay0123 = (ay012 + ay123) / 2;
435 fixed bx01 = (bx0 + bx1) / 2, by01 = (by0 + by1) / 2;
436 fixed bx12 = (bx1 + bx2) / 2, by12 = (by1 + by2) / 2;
437 fixed bx23 = (bx2 + bx3) / 2, by23 = (by2 + by3) / 2;
438 fixed bx012 = (bx01 + bx12) / 2, by012 = (by01 + by12) / 2;
439 fixed bx123 = (bx12 + bx23) / 2, by123 = (by12 + by23) / 2;
440 fixed bx0123 = (bx012 + bx123) / 2, by0123 = (by012 + by123) / 2;
441
442 if (intersect_curve_curve_rec(ka - 1, kb - 1, ax0, ay0, ax01, ay01, ax012, ay012, ax0123, ay0123,
443 bx0, by0, bx01, by01, bx012, by012, bx0123, by0123))
444 return true;
445 if (intersect_curve_curve_rec(ka - 1, kb - 1, ax0, ay0, ax01, ay01, ax012, ay012, ax0123, ay0123,
446 bx0123, by0123, bx123, by123, bx23, by23, bx3, by3))
447 return true;
448 if (intersect_curve_curve_rec(ka - 1, kb - 1, ax0123, ay0123, ax123, ay123, ax23, ay23, ax3, ay3,
449 bx0, by0, bx01, by01, bx012, by012, bx0123, by0123))
450 return true;
451 if (intersect_curve_curve_rec(ka - 1, kb - 1, ax0123, ay0123, ax123, ay123, ax23, ay23, ax3, ay3,
452 bx0123, by0123, bx123, by123, bx23, by23, bx3, by3))
453 return true;
454
455 }
456 return false;
457 }
458
t1_hinter__intersect_curve_curve(t1_hinter * this,int i,int j)459 static bool t1_hinter__intersect_curve_curve(t1_hinter * this, int i, int j)
460 {
461 fixed ax0 = this->pole[i].gx;
462 fixed ay0 = this->pole[i].gy;
463 fixed ax1 = this->pole[i + 1].gx;
464 fixed ay1 = this->pole[i + 1].gy;
465 fixed ax2 = this->pole[i + 2].gx;
466 fixed ay2 = this->pole[i + 2].gy;
467 fixed ax3 = this->pole[i + 3].gx;
468 fixed ay3 = this->pole[i + 3].gy;
469 fixed bx0 = this->pole[j].gx;
470 fixed by0 = this->pole[j].gy;
471 fixed bx1 = this->pole[j + 1].gx;
472 fixed by1 = this->pole[j + 1].gy;
473 fixed bx2 = this->pole[j + 2].gx;
474 fixed by2 = this->pole[j + 2].gy;
475 fixed bx3 = this->pole[j + 3].gx;
476 fixed by3 = this->pole[j + 3].gy;
477 int ka = curve_log2_samples(ax0, ay0, ax1, ay1, ax2, ay2, ax3, ay3);
478 int kb = curve_log2_samples(bx0, by0, bx1, by1, bx2, by2, bx3, by3);
479
480 return intersect_curve_curve_rec(ka, kb,
481 ax0, ay0, ax1, ay1, ax2, ay2, ax3, ay3,
482 bx0, by0, bx1, by1, bx2, by2, bx3, by3);
483 }
484
t1_hinter__contour_intersection(t1_hinter * this,int c0,int c1)485 static bool t1_hinter__contour_intersection(t1_hinter * this, int c0, int c1)
486 {
487 int b0 = this->contour[c0];
488 int e0 = this->contour[c0 + 1] - 1;
489 int b1 = this->contour[c1];
490 int e1 = this->contour[c1 + 1] - 1;
491 int i, j;
492
493 for (i = b0; i < e0;) {
494 if (this->pole[i + 1].type != offcurve) { /* line or close. */
495 for (j = b1; j < e1;) {
496 if (this->pole[j + 1].type != offcurve) { /* line or close. */
497 if (t1_hinter__intersect_bar_bar(this, i, j))
498 return true;
499 j++;
500 } else {
501 if (t1_hinter__intersect_curve_bar(this, j, i))
502 return true;
503 j += 3;
504 }
505 }
506 i++;
507 } else {
508 for (j = b1; j < e1;) {
509 if (this->pole[j + 1].type != offcurve) { /* line or close. */
510 if (t1_hinter__intersect_curve_bar(this, i, j))
511 return true;
512 j++;
513 } else {
514 if (t1_hinter__intersect_curve_curve(this, j, i))
515 return true;
516 j += 3;
517 }
518 }
519 i += 3;
520 }
521 }
522 return false;
523 }
524
525 #define MAX_NORMALIZING_CONTOURS 5
526
t1_hinter__fix_subglyph_contour_signs(t1_hinter * this,int first_contour,int last_contour)527 static void t1_hinter__fix_subglyph_contour_signs(t1_hinter * this, int first_contour, int last_contour)
528 {
529 double area[MAX_NORMALIZING_CONTOURS];
530 int i, j, k, l, m;
531 double a = 0;
532 byte inside[MAX_NORMALIZING_CONTOURS][MAX_NORMALIZING_CONTOURS];
533 int nesting[MAX_NORMALIZING_CONTOURS];
534 gs_rect bbox[MAX_NORMALIZING_CONTOURS];
535 byte isolated[MAX_NORMALIZING_CONTOURS];
536 int nesting_sum;
537
538 if (first_contour == last_contour) {
539 /* Don't fix a single contour. */
540 return;
541 }
542 /* Compute contour bboxes : */
543 k = 0;
544 for(i = first_contour; i <= last_contour; i++) {
545 int b = this->contour[i];
546 int e = this->contour[i + 1] - 1;
547
548 bbox[k].p.x = bbox[k].q.x = this->pole[b].gx;
549 bbox[k].p.y = bbox[k].q.y = this->pole[b].gy;
550 /* 'close' has same coords as the starting point. */
551 for (j = b; j < e; j++) {
552 t1_glyph_space_coord x = this->pole[j].gx;
553 t1_glyph_space_coord y = this->pole[j].gy;
554
555 if (bbox[k].p.x > x)
556 bbox[k].p.x = x;
557 if (bbox[k].q.x < x)
558 bbox[k].q.x = x;
559 if (bbox[k].p.y > y)
560 bbox[k].p.y = y;
561 if (bbox[k].q.y < y)
562 bbox[k].q.y = y;
563 }
564 k++;
565 }
566 /* mark contacting bboxes : */
567 memset(isolated, 0, sizeof(isolated));
568 for (i = 0; i < k; i++) {
569 for (j = i + 1; j < k; j++) {
570 if (bbox[i].p.x > bbox[j].q.x)
571 continue;
572 if (bbox[i].q.x < bbox[j].p.x)
573 continue;
574 if (bbox[i].p.y > bbox[j].q.y)
575 continue;
576 if (bbox[i].q.y < bbox[j].p.y)
577 continue;
578 isolated[i] = isolated[j] = 1; /* mark not isolated. */
579 }
580 }
581 /* Make a list of non-isolated contours : */
582 j = 0;
583 for (i = 0; i < k; i++) {
584 if (isolated[i]) {
585 isolated[j] = first_contour + i;
586 j++;
587 }
588 }
589 k = j;
590 /* So far we skip isolated contours. */
591 if (k <= 1)
592 return; /* Nothing to fix. */
593 /* Compute contour signes : */
594 for(i = 0; i < k; i++) {
595 int c = isolated[i];
596 int b = this->contour[c];
597 int e = this->contour[c + 1] - 1;
598
599 a = 0;
600 /* 'close' has same coords as the starting point. */
601 for (j = b; j < e; ) {
602 if (this->pole[j + 1].type != offcurve) { /* line or close. */
603 a += line_area_2(this->pole[j + 0].gx, this->pole[j + 0].gy,
604 this->pole[j + 1].gx, this->pole[j + 1].gy);
605 j++;
606 } else {
607 a += bezier_area_2(this->pole[j + 0].gx, this->pole[j + 0].gy,
608 this->pole[j + 1].gx, this->pole[j + 1].gy,
609 this->pole[j + 2].gx, this->pole[j + 2].gy,
610 this->pole[j + 3].gx, this->pole[j + 3].gy);
611 j += 3;
612 }
613 }
614 area[i] = a;
615 }
616 /* If contours have different signs, don't adjust. */
617 for (i = 1; i < k; i++) {
618 if (area[0] * area[i] < 0)
619 return;
620 }
621 /* Compute the insideness matrix :
622 For any contoor pair A, B,
623 check if some point of A is inside B. */
624 for (i = 0; i < k; i++) {
625 inside[i][i] = 0;
626 for (j = 0; j < k; j++) {
627 if (i != j) {
628 int b = this->contour[isolated[i]];
629 int code = t1_hinter__is_inside(this, this->pole[b].gx, this->pole[b].gy, isolated[j]);
630
631 if (code < 0) {
632 /* Contours have a common point - don't fix. */
633 return;
634 }
635 inside[i][j] = (byte)code;
636 if (i > j && inside[j][i]) {
637 /* Contours intersect, don't fix. */
638 return;
639 }
640 }
641 }
642 }
643 /* Transitive closure : */
644 do {
645 m = 0;
646 for (i = 0; i < k; i++) {
647 for (j = 0; j < k; j++) {
648 if (i != j) {
649 for (l = 0; l < k; l++) {
650 if (j != l && inside[i][j] && inside[j][l]) {
651 if (inside[l][i]) {
652 /* Cycled - don't fix. */
653 return;
654 }
655 if (!inside[i][l])
656 m = 1;
657 inside[i][l] = 1;
658 }
659 }
660 }
661 }
662 }
663 } while(m);
664 /* Compute nesting numbers : */
665 nesting_sum = 0;
666 memset(nesting, 0, sizeof(nesting));
667 for (i = 0; i < k; i++) {
668 for (j = 0; j < k; j++) {
669 if (inside[i][j]) {
670 nesting[i]++;
671 nesting_sum++;
672 }
673 }
674 }
675 if (nesting_sum == 0) {
676 /* No nesting contours - don't fix.
677 We want to save time from computing contour intersections. */
678 return;
679 }
680 /* Check contour intersections : */
681 for (i = 0; i < k; i++) {
682 for (j = 0; j < k; j++) {
683 if (inside[i][j]) {
684 if (t1_hinter__contour_intersection(this, isolated[i], isolated[j])) {
685 /* Contours intersect - don't fix. */
686 return;
687 }
688 }
689 }
690 }
691 /* Fix signs : */
692 for (i = 0; i < k; i++) {
693 if ((nesting[i] & 1) != (area[i] < 0))
694 t1_hinter__reverse_contour(this, isolated[i]);
695 }
696 /* Note we didn't fix negative isolated contours.
697 We never meet such cases actually. */
698 }
699
t1_hinter__fix_contour_signs(t1_hinter * this)700 void t1_hinter__fix_contour_signs(t1_hinter * this)
701 {
702 int i;
703
704 if (this->subglyph_count >= 3) {
705 /* 3 or more subglyphs.
706 We didn't meet so complex characters with wrong contours signs.
707 Skip it for saving the CPU time. */
708 return;
709 }
710 for (i = 1; i <= this->subglyph_count; i++) {
711 int first_contour = this->subglyph[i - 1];
712 int last_contour = this->subglyph[i] - 1;
713
714 if (last_contour - first_contour >= MAX_NORMALIZING_CONTOURS) {
715 /* 4 or more contours.
716 We didn't meet so complex characters with wrong contours signs.
717 Skip it for saving the CPU time. */
718 continue;
719 }
720 t1_hinter__fix_subglyph_contour_signs(this, first_contour, last_contour);
721 }
722 }
723