1/****************************************************************************
2 *
3 * pshalgo.c
4 *
5 * PostScript hinting algorithm (body).
6 *
7 * Copyright (C) 2001-2019 by
8 * David Turner, Robert Wilhelm, and Werner Lemberg.
9 *
10 * This file is part of the FreeType project, and may only be used
11 * modified and distributed under the terms of the FreeType project
12 * license, LICENSE.TXT. By continuing to use, modify, or distribute
13 * this file you indicate that you have read the license and
14 * understand and accept it fully.
15 *
16 */
17
18
19#include <ft2build.h>
20#include FT_INTERNAL_OBJECTS_H
21#include FT_INTERNAL_DEBUG_H
22#include FT_INTERNAL_CALC_H
23#include "pshalgo.h"
24
25#include "pshnterr.h"
26
27
28#undef FT_COMPONENT
29#define FT_COMPONENT pshalgo
30
31
32#ifdef DEBUG_HINTER
33 PSH_Hint_Table ps_debug_hint_table = NULL;
34 PSH_HintFunc ps_debug_hint_func = NULL;
35 PSH_Glyph ps_debug_glyph = NULL;
36#endif
37
38
39#define COMPUTE_INFLEXS /* compute inflection points to optimize `S' */
40 /* and similar glyphs */
41
42
43 /*************************************************************************/
44 /*************************************************************************/
45 /***** *****/
46 /***** BASIC HINTS RECORDINGS *****/
47 /***** *****/
48 /*************************************************************************/
49 /*************************************************************************/
50
51 /* return true if two stem hints overlap */
52 static FT_Int
53 psh_hint_overlap( PSH_Hint hint1,
54 PSH_Hint hint2 )
55 {
56 return ADD_INT( hint1->org_pos, hint1->org_len ) >= hint2->org_pos &&
57 ADD_INT( hint2->org_pos, hint2->org_len ) >= hint1->org_pos;
58 }
59
60
61 /* destroy hints table */
62 static void
63 psh_hint_table_done( PSH_Hint_Table table,
64 FT_Memory memory )
65 {
66 FT_FREE( table->zones );
67 table->num_zones = 0;
68 table->zone = NULL;
69
70 FT_FREE( table->sort );
71 FT_FREE( table->hints );
72 table->num_hints = 0;
73 table->max_hints = 0;
74 table->sort_global = NULL;
75 }
76
77
78 /* deactivate all hints in a table */
79 static void
80 psh_hint_table_deactivate( PSH_Hint_Table table )
81 {
82 FT_UInt count = table->max_hints;
83 PSH_Hint hint = table->hints;
84
85
86 for ( ; count > 0; count--, hint++ )
87 {
88 psh_hint_deactivate( hint );
89 hint->order = -1;
90 }
91 }
92
93
94 /* internal function to record a new hint */
95 static void
96 psh_hint_table_record( PSH_Hint_Table table,
97 FT_UInt idx )
98 {
99 PSH_Hint hint = table->hints + idx;
100
101
102 if ( idx >= table->max_hints )
103 {
104 FT_TRACE0(( "psh_hint_table_record: invalid hint index %d\n", idx ));
105 return;
106 }
107
108 /* ignore active hints */
109 if ( psh_hint_is_active( hint ) )
110 return;
111
112 psh_hint_activate( hint );
113
114 /* now scan the current active hint set to check */
115 /* whether `hint' overlaps with another hint */
116 {
117 PSH_Hint* sorted = table->sort_global;
118 FT_UInt count = table->num_hints;
119 PSH_Hint hint2;
120
121
122 hint->parent = NULL;
123 for ( ; count > 0; count--, sorted++ )
124 {
125 hint2 = sorted[0];
126
127 if ( psh_hint_overlap( hint, hint2 ) )
128 {
129 hint->parent = hint2;
130 break;
131 }
132 }
133 }
134
135 if ( table->num_hints < table->max_hints )
136 table->sort_global[table->num_hints++] = hint;
137 else
138 FT_TRACE0(( "psh_hint_table_record: too many sorted hints! BUG!\n" ));
139 }
140
141
142 static void
143 psh_hint_table_record_mask( PSH_Hint_Table table,
144 PS_Mask hint_mask )
145 {
146 FT_Int mask = 0, val = 0;
147 FT_Byte* cursor = hint_mask->bytes;
148 FT_UInt idx, limit;
149
150
151 limit = hint_mask->num_bits;
152
153 for ( idx = 0; idx < limit; idx++ )
154 {
155 if ( mask == 0 )
156 {
157 val = *cursor++;
158 mask = 0x80;
159 }
160
161 if ( val & mask )
162 psh_hint_table_record( table, idx );
163
164 mask >>= 1;
165 }
166 }
167
168
169 /* create hints table */
170 static FT_Error
171 psh_hint_table_init( PSH_Hint_Table table,
172 PS_Hint_Table hints,
173 PS_Mask_Table hint_masks,
174 PS_Mask_Table counter_masks,
175 FT_Memory memory )
176 {
177 FT_UInt count;
178 FT_Error error;
179
180 FT_UNUSED( counter_masks );
181
182
183 count = hints->num_hints;
184
185 /* allocate our tables */
186 if ( FT_NEW_ARRAY( table->sort, 2 * count ) ||
187 FT_NEW_ARRAY( table->hints, count ) ||
188 FT_NEW_ARRAY( table->zones, 2 * count + 1 ) )
189 goto Exit;
190
191 table->max_hints = count;
192 table->sort_global = table->sort + count;
193 table->num_hints = 0;
194 table->num_zones = 0;
195 table->zone = NULL;
196
197 /* initialize the `table->hints' array */
198 {
199 PSH_Hint write = table->hints;
200 PS_Hint read = hints->hints;
201
202
203 for ( ; count > 0; count--, write++, read++ )
204 {
205 write->org_pos = read->pos;
206 write->org_len = read->len;
207 write->flags = read->flags;
208 }
209 }
210
211 /* we now need to determine the initial `parent' stems; first */
212 /* activate the hints that are given by the initial hint masks */
213 if ( hint_masks )
214 {
215 PS_Mask mask = hint_masks->masks;
216
217
218 count = hint_masks->num_masks;
219 table->hint_masks = hint_masks;
220
221 for ( ; count > 0; count--, mask++ )
222 psh_hint_table_record_mask( table, mask );
223 }
224
225 /* finally, do a linear parse in case some hints were left alone */
226 if ( table->num_hints != table->max_hints )
227 {
228 FT_UInt idx;
229
230
231 FT_TRACE0(( "psh_hint_table_init: missing/incorrect hint masks\n" ));
232
233 count = table->max_hints;
234 for ( idx = 0; idx < count; idx++ )
235 psh_hint_table_record( table, idx );
236 }
237
238 Exit:
239 return error;
240 }
241
242
243 static void
244 psh_hint_table_activate_mask( PSH_Hint_Table table,
245 PS_Mask hint_mask )
246 {
247 FT_Int mask = 0, val = 0;
248 FT_Byte* cursor = hint_mask->bytes;
249 FT_UInt idx, limit, count;
250
251
252 limit = hint_mask->num_bits;
253 count = 0;
254
255 psh_hint_table_deactivate( table );
256
257 for ( idx = 0; idx < limit; idx++ )
258 {
259 if ( mask == 0 )
260 {
261 val = *cursor++;
262 mask = 0x80;
263 }
264
265 if ( val & mask )
266 {
267 PSH_Hint hint = &table->hints[idx];
268
269
270 if ( !psh_hint_is_active( hint ) )
271 {
272 FT_UInt count2;
273
274#if 0
275 PSH_Hint* sort = table->sort;
276 PSH_Hint hint2;
277
278
279 for ( count2 = count; count2 > 0; count2--, sort++ )
280 {
281 hint2 = sort[0];
282 if ( psh_hint_overlap( hint, hint2 ) )
283 FT_TRACE0(( "psh_hint_table_activate_mask:"
284 " found overlapping hints\n" ))
285 }
286#else
287 count2 = 0;
288#endif
289
290 if ( count2 == 0 )
291 {
292 psh_hint_activate( hint );
293 if ( count < table->max_hints )
294 table->sort[count++] = hint;
295 else
296 FT_TRACE0(( "psh_hint_tableactivate_mask:"
297 " too many active hints\n" ));
298 }
299 }
300 }
301
302 mask >>= 1;
303 }
304 table->num_hints = count;
305
306 /* now, sort the hints; they are guaranteed to not overlap */
307 /* so we can compare their "org_pos" field directly */
308 {
309 FT_Int i1, i2;
310 PSH_Hint hint1, hint2;
311 PSH_Hint* sort = table->sort;
312
313
314 /* a simple bubble sort will do, since in 99% of cases, the hints */
315 /* will be already sorted -- and the sort will be linear */
316 for ( i1 = 1; i1 < (FT_Int)count; i1++ )
317 {
318 hint1 = sort[i1];
319 for ( i2 = i1 - 1; i2 >= 0; i2-- )
320 {
321 hint2 = sort[i2];
322
323 if ( hint2->org_pos < hint1->org_pos )
324 break;
325
326 sort[i2 + 1] = hint2;
327 sort[i2] = hint1;
328 }
329 }
330 }
331 }
332
333
334 /*************************************************************************/
335 /*************************************************************************/
336 /***** *****/
337 /***** HINTS GRID-FITTING AND OPTIMIZATION *****/
338 /***** *****/
339 /*************************************************************************/
340 /*************************************************************************/
341
342#if 1
343 static FT_Pos
344 psh_dimension_quantize_len( PSH_Dimension dim,
345 FT_Pos len,
346 FT_Bool do_snapping )
347 {
348 if ( len <= 64 )
349 len = 64;
350 else
351 {
352 FT_Pos delta = len - dim->stdw.widths[0].cur;
353
354
355 if ( delta < 0 )
356 delta = -delta;
357
358 if ( delta < 40 )
359 {
360 len = dim->stdw.widths[0].cur;
361 if ( len < 48 )
362 len = 48;
363 }
364
365 if ( len < 3 * 64 )
366 {
367 delta = ( len & 63 );
368 len &= -64;
369
370 if ( delta < 10 )
371 len += delta;
372
373 else if ( delta < 32 )
374 len += 10;
375
376 else if ( delta < 54 )
377 len += 54;
378
379 else
380 len += delta;
381 }
382 else
383 len = FT_PIX_ROUND( len );
384 }
385
386 if ( do_snapping )
387 len = FT_PIX_ROUND( len );
388
389 return len;
390 }
391#endif /* 0 */
392
393
394#ifdef DEBUG_HINTER
395
396 static void
397 ps_simple_scale( PSH_Hint_Table table,
398 FT_Fixed scale,
399 FT_Fixed delta,
400 FT_Int dimension )
401 {
402 FT_UInt count;
403
404
405 for ( count = 0; count < table->max_hints; count++ )
406 {
407 PSH_Hint hint = table->hints + count;
408
409
410 hint->cur_pos = FT_MulFix( hint->org_pos, scale ) + delta;
411 hint->cur_len = FT_MulFix( hint->org_len, scale );
412
413 if ( ps_debug_hint_func )
414 ps_debug_hint_func( hint, dimension );
415 }
416 }
417
418#endif /* DEBUG_HINTER */
419
420
421 static FT_Fixed
422 psh_hint_snap_stem_side_delta( FT_Fixed pos,
423 FT_Fixed len )
424 {
425 FT_Fixed delta1 = FT_PIX_ROUND( pos ) - pos;
426 FT_Fixed delta2 = FT_PIX_ROUND( pos + len ) - pos - len;
427
428
429 if ( FT_ABS( delta1 ) <= FT_ABS( delta2 ) )
430 return delta1;
431 else
432 return delta2;
433 }
434
435
436 static void
437 psh_hint_align( PSH_Hint hint,
438 PSH_Globals globals,
439 FT_Int dimension,
440 PSH_Glyph glyph )
441 {
442 PSH_Dimension dim = &globals->dimension[dimension];
443 FT_Fixed scale = dim->scale_mult;
444 FT_Fixed delta = dim->scale_delta;
445
446
447 if ( !psh_hint_is_fitted( hint ) )
448 {
449 FT_Pos pos = FT_MulFix( hint->org_pos, scale ) + delta;
450 FT_Pos len = FT_MulFix( hint->org_len, scale );
451
452 FT_Int do_snapping;
453 FT_Pos fit_len;
454 PSH_AlignmentRec align;
455
456
457 /* ignore stem alignments when requested through the hint flags */
458 if ( ( dimension == 0 && !glyph->do_horz_hints ) ||
459 ( dimension == 1 && !glyph->do_vert_hints ) )
460 {
461 hint->cur_pos = pos;
462 hint->cur_len = len;
463
464 psh_hint_set_fitted( hint );
465 return;
466 }
467
468 /* perform stem snapping when requested - this is necessary
469 * for monochrome and LCD hinting modes only
470 */
471 do_snapping = ( dimension == 0 && glyph->do_horz_snapping ) ||
472 ( dimension == 1 && glyph->do_vert_snapping );
473
474 hint->cur_len = fit_len = len;
475
476 /* check blue zones for horizontal stems */
477 align.align = PSH_BLUE_ALIGN_NONE;
478 align.align_bot = align.align_top = 0;
479
480 if ( dimension == 1 )
481 psh_blues_snap_stem( &globals->blues,
482 ADD_INT( hint->org_pos, hint->org_len ),
483 hint->org_pos,
484 &align );
485
486 switch ( align.align )
487 {
488 case PSH_BLUE_ALIGN_TOP:
489 /* the top of the stem is aligned against a blue zone */
490 hint->cur_pos = align.align_top - fit_len;
491 break;
492
493 case PSH_BLUE_ALIGN_BOT:
494 /* the bottom of the stem is aligned against a blue zone */
495 hint->cur_pos = align.align_bot;
496 break;
497
498 case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT:
499 /* both edges of the stem are aligned against blue zones */
500 hint->cur_pos = align.align_bot;
501 hint->cur_len = align.align_top - align.align_bot;
502 break;
503
504 default:
505 {
506 PSH_Hint parent = hint->parent;
507
508
509 if ( parent )
510 {
511 FT_Pos par_org_center, par_cur_center;
512 FT_Pos cur_org_center, cur_delta;
513
514
515 /* ensure that parent is already fitted */
516 if ( !psh_hint_is_fitted( parent ) )
517 psh_hint_align( parent, globals, dimension, glyph );
518
519 /* keep original relation between hints, this is, use the */
520 /* scaled distance between the centers of the hints to */
521 /* compute the new position */
522 par_org_center = parent->org_pos + ( parent->org_len >> 1 );
523 par_cur_center = parent->cur_pos + ( parent->cur_len >> 1 );
524 cur_org_center = hint->org_pos + ( hint->org_len >> 1 );
525
526 cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );
527 pos = par_cur_center + cur_delta - ( len >> 1 );
528 }
529
530 hint->cur_pos = pos;
531 hint->cur_len = fit_len;
532
533 /* Stem adjustment tries to snap stem widths to standard
534 * ones. This is important to prevent unpleasant rounding
535 * artefacts.
536 */
537 if ( glyph->do_stem_adjust )
538 {
539 if ( len <= 64 )
540 {
541 /* the stem is less than one pixel; we will center it
542 * around the nearest pixel center
543 */
544 if ( len >= 32 )
545 {
546 /* This is a special case where we also widen the stem
547 * and align it to the pixel grid.
548 *
549 * stem_center = pos + (len/2)
550 * nearest_pixel_center = FT_ROUND(stem_center-32)+32
551 * new_pos = nearest_pixel_center-32
552 * = FT_ROUND(stem_center-32)
553 * = FT_FLOOR(stem_center-32+32)
554 * = FT_FLOOR(stem_center)
555 * new_len = 64
556 */
557 pos = FT_PIX_FLOOR( pos + ( len >> 1 ) );
558 len = 64;
559 }
560 else if ( len > 0 )
561 {
562 /* This is a very small stem; we simply align it to the
563 * pixel grid, trying to find the minimum displacement.
564 *
565 * left = pos
566 * right = pos + len
567 * left_nearest_edge = ROUND(pos)
568 * right_nearest_edge = ROUND(right)
569 *
570 * if ( ABS(left_nearest_edge - left) <=
571 * ABS(right_nearest_edge - right) )
572 * new_pos = left
573 * else
574 * new_pos = right
575 */
576 FT_Pos left_nearest = FT_PIX_ROUND( pos );
577 FT_Pos right_nearest = FT_PIX_ROUND( pos + len );
578 FT_Pos left_disp = left_nearest - pos;
579 FT_Pos right_disp = right_nearest - ( pos + len );
580
581
582 if ( left_disp < 0 )
583 left_disp = -left_disp;
584 if ( right_disp < 0 )
585 right_disp = -right_disp;
586 if ( left_disp <= right_disp )
587 pos = left_nearest;
588 else
589 pos = right_nearest;
590 }
591 else
592 {
593 /* this is a ghost stem; we simply round it */
594 pos = FT_PIX_ROUND( pos );
595 }
596 }
597 else
598 {
599 len = psh_dimension_quantize_len( dim, len, 0 );
600 }
601 }
602
603 /* now that we have a good hinted stem width, try to position */
604 /* the stem along a pixel grid integer coordinate */
605 hint->cur_pos = pos + psh_hint_snap_stem_side_delta( pos, len );
606 hint->cur_len = len;
607 }
608 }
609
610 if ( do_snapping )
611 {
612 pos = hint->cur_pos;
613 len = hint->cur_len;
614
615 if ( len < 64 )
616 len = 64;
617 else
618 len = FT_PIX_ROUND( len );
619
620 switch ( align.align )
621 {
622 case PSH_BLUE_ALIGN_TOP:
623 hint->cur_pos = align.align_top - len;
624 hint->cur_len = len;
625 break;
626
627 case PSH_BLUE_ALIGN_BOT:
628 hint->cur_len = len;
629 break;
630
631 case PSH_BLUE_ALIGN_BOT | PSH_BLUE_ALIGN_TOP:
632 /* don't touch */
633 break;
634
635
636 default:
637 hint->cur_len = len;
638 if ( len & 64 )
639 pos = FT_PIX_FLOOR( pos + ( len >> 1 ) ) + 32;
640 else
641 pos = FT_PIX_ROUND( pos + ( len >> 1 ) );
642
643 hint->cur_pos = pos - ( len >> 1 );
644 hint->cur_len = len;
645 }
646 }
647
648 psh_hint_set_fitted( hint );
649
650#ifdef DEBUG_HINTER
651 if ( ps_debug_hint_func )
652 ps_debug_hint_func( hint, dimension );
653#endif
654 }
655 }
656
657
658#if 0 /* not used for now, experimental */
659
660 /*
661 * A variant to perform "light" hinting (i.e. FT_RENDER_MODE_LIGHT)
662 * of stems
663 */
664 static void
665 psh_hint_align_light( PSH_Hint hint,
666 PSH_Globals globals,
667 FT_Int dimension,
668 PSH_Glyph glyph )
669 {
670 PSH_Dimension dim = &globals->dimension[dimension];
671 FT_Fixed scale = dim->scale_mult;
672 FT_Fixed delta = dim->scale_delta;
673
674
675 if ( !psh_hint_is_fitted( hint ) )
676 {
677 FT_Pos pos = FT_MulFix( hint->org_pos, scale ) + delta;
678 FT_Pos len = FT_MulFix( hint->org_len, scale );
679
680 FT_Pos fit_len;
681
682 PSH_AlignmentRec align;
683
684
685 /* ignore stem alignments when requested through the hint flags */
686 if ( ( dimension == 0 && !glyph->do_horz_hints ) ||
687 ( dimension == 1 && !glyph->do_vert_hints ) )
688 {
689 hint->cur_pos = pos;
690 hint->cur_len = len;
691
692 psh_hint_set_fitted( hint );
693 return;
694 }
695
696 fit_len = len;
697
698 hint->cur_len = fit_len;
699
700 /* check blue zones for horizontal stems */
701 align.align = PSH_BLUE_ALIGN_NONE;
702 align.align_bot = align.align_top = 0;
703
704 if ( dimension == 1 )
705 psh_blues_snap_stem( &globals->blues,
706 ADD_INT( hint->org_pos, hint->org_len ),
707 hint->org_pos,
708 &align );
709
710 switch ( align.align )
711 {
712 case PSH_BLUE_ALIGN_TOP:
713 /* the top of the stem is aligned against a blue zone */
714 hint->cur_pos = align.align_top - fit_len;
715 break;
716
717 case PSH_BLUE_ALIGN_BOT:
718 /* the bottom of the stem is aligned against a blue zone */
719 hint->cur_pos = align.align_bot;
720 break;
721
722 case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT:
723 /* both edges of the stem are aligned against blue zones */
724 hint->cur_pos = align.align_bot;
725 hint->cur_len = align.align_top - align.align_bot;
726 break;
727
728 default:
729 {
730 PSH_Hint parent = hint->parent;
731
732
733 if ( parent )
734 {
735 FT_Pos par_org_center, par_cur_center;
736 FT_Pos cur_org_center, cur_delta;
737
738
739 /* ensure that parent is already fitted */
740 if ( !psh_hint_is_fitted( parent ) )
741 psh_hint_align_light( parent, globals, dimension, glyph );
742
743 par_org_center = parent->org_pos + ( parent->org_len / 2 );
744 par_cur_center = parent->cur_pos + ( parent->cur_len / 2 );
745 cur_org_center = hint->org_pos + ( hint->org_len / 2 );
746
747 cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );
748 pos = par_cur_center + cur_delta - ( len >> 1 );
749 }
750
751 /* Stems less than one pixel wide are easy -- we want to
752 * make them as dark as possible, so they must fall within
753 * one pixel. If the stem is split between two pixels
754 * then snap the edge that is nearer to the pixel boundary
755 * to the pixel boundary.
756 */
757 if ( len <= 64 )
758 {
759 if ( ( pos + len + 63 ) / 64 != pos / 64 + 1 )
760 pos += psh_hint_snap_stem_side_delta ( pos, len );
761 }
762
763 /* Position stems other to minimize the amount of mid-grays.
764 * There are, in general, two positions that do this,
765 * illustrated as A) and B) below.
766 *
767 * + + + +
768 *
769 * A) |--------------------------------|
770 * B) |--------------------------------|
771 * C) |--------------------------------|
772 *
773 * Position A) (split the excess stem equally) should be better
774 * for stems of width N + f where f < 0.5.
775 *
776 * Position B) (split the deficiency equally) should be better
777 * for stems of width N + f where f > 0.5.
778 *
779 * It turns out though that minimizing the total number of lit
780 * pixels is also important, so position C), with one edge
781 * aligned with a pixel boundary is actually preferable
782 * to A). There are also more possible positions for C) than
783 * for A) or B), so it involves less distortion of the overall
784 * character shape.
785 */
786 else /* len > 64 */
787 {
788 FT_Fixed frac_len = len & 63;
789 FT_Fixed center = pos + ( len >> 1 );
790 FT_Fixed delta_a, delta_b;
791
792
793 if ( ( len / 64 ) & 1 )
794 {
795 delta_a = FT_PIX_FLOOR( center ) + 32 - center;
796 delta_b = FT_PIX_ROUND( center ) - center;
797 }
798 else
799 {
800 delta_a = FT_PIX_ROUND( center ) - center;
801 delta_b = FT_PIX_FLOOR( center ) + 32 - center;
802 }
803
804 /* We choose between B) and C) above based on the amount
805 * of fractional stem width; for small amounts, choose
806 * C) always, for large amounts, B) always, and inbetween,
807 * pick whichever one involves less stem movement.
808 */
809 if ( frac_len < 32 )
810 {
811 pos += psh_hint_snap_stem_side_delta ( pos, len );
812 }
813 else if ( frac_len < 48 )
814 {
815 FT_Fixed side_delta = psh_hint_snap_stem_side_delta ( pos,
816 len );
817
818 if ( FT_ABS( side_delta ) < FT_ABS( delta_b ) )
819 pos += side_delta;
820 else
821 pos += delta_b;
822 }
823 else
824 {
825 pos += delta_b;
826 }
827 }
828
829 hint->cur_pos = pos;
830 }
831 } /* switch */
832
833 psh_hint_set_fitted( hint );
834
835#ifdef DEBUG_HINTER
836 if ( ps_debug_hint_func )
837 ps_debug_hint_func( hint, dimension );
838#endif
839 }
840 }
841
842#endif /* 0 */
843
844
845 static void
846 psh_hint_table_align_hints( PSH_Hint_Table table,
847 PSH_Globals globals,
848 FT_Int dimension,
849 PSH_Glyph glyph )
850 {
851 PSH_Hint hint;
852 FT_UInt count;
853
854#ifdef DEBUG_HINTER
855
856 PSH_Dimension dim = &globals->dimension[dimension];
857 FT_Fixed scale = dim->scale_mult;
858 FT_Fixed delta = dim->scale_delta;
859
860
861 if ( ps_debug_no_vert_hints && dimension == 0 )
862 {
863 ps_simple_scale( table, scale, delta, dimension );
864 return;
865 }
866
867 if ( ps_debug_no_horz_hints && dimension == 1 )
868 {
869 ps_simple_scale( table, scale, delta, dimension );
870 return;
871 }
872
873#endif /* DEBUG_HINTER*/
874
875 hint = table->hints;
876 count = table->max_hints;
877
878 for ( ; count > 0; count--, hint++ )
879 psh_hint_align( hint, globals, dimension, glyph );
880 }
881
882
883 /*************************************************************************/
884 /*************************************************************************/
885 /***** *****/
886 /***** POINTS INTERPOLATION ROUTINES *****/
887 /***** *****/
888 /*************************************************************************/
889 /*************************************************************************/
890
891#define xxDEBUG_ZONES
892
893
894#ifdef DEBUG_ZONES
895
896#include FT_CONFIG_STANDARD_LIBRARY_H
897
898 static void
899 psh_print_zone( PSH_Zone zone )
900 {
901 printf( "zone [scale,delta,min,max] = [%.5f,%.2f,%d,%d]\n",
902 zone->scale / 65536.0,
903 zone->delta / 64.0,
904 zone->min,
905 zone->max );
906 }
907
908#endif /* DEBUG_ZONES */
909
910
911 /*************************************************************************/
912 /*************************************************************************/
913 /***** *****/
914 /***** HINTER GLYPH MANAGEMENT *****/
915 /***** *****/
916 /*************************************************************************/
917 /*************************************************************************/
918
919#define psh_corner_is_flat ft_corner_is_flat
920#define psh_corner_orientation ft_corner_orientation
921
922
923#ifdef COMPUTE_INFLEXS
924
925 /* compute all inflex points in a given glyph */
926 static void
927 psh_glyph_compute_inflections( PSH_Glyph glyph )
928 {
929 FT_UInt n;
930
931
932 for ( n = 0; n < glyph->num_contours; n++ )
933 {
934 PSH_Point first, start, end, before, after;
935 FT_Pos in_x, in_y, out_x, out_y;
936 FT_Int orient_prev, orient_cur;
937 FT_Int finished = 0;
938
939
940 /* we need at least 4 points to create an inflection point */
941 if ( glyph->contours[n].count < 4 )
942 continue;
943
944 /* compute first segment in contour */
945 first = glyph->contours[n].start;
946
947 start = end = first;
948 do
949 {
950 end = end->next;
951 if ( end == first )
952 goto Skip;
953
954 in_x = end->org_u - start->org_u;
955 in_y = end->org_v - start->org_v;
956
957 } while ( in_x == 0 && in_y == 0 );
958
959 /* extend the segment start whenever possible */
960 before = start;
961 do
962 {
963 do
964 {
965 start = before;
966 before = before->prev;
967 if ( before == first )
968 goto Skip;
969
970 out_x = start->org_u - before->org_u;
971 out_y = start->org_v - before->org_v;
972
973 } while ( out_x == 0 && out_y == 0 );
974
975 orient_prev = psh_corner_orientation( in_x, in_y, out_x, out_y );
976
977 } while ( orient_prev == 0 );
978
979 first = start;
980 in_x = out_x;
981 in_y = out_y;
982
983 /* now, process all segments in the contour */
984 do
985 {
986 /* first, extend current segment's end whenever possible */
987 after = end;
988 do
989 {
990 do
991 {
992 end = after;
993 after = after->next;
994 if ( after == first )
995 finished = 1;
996
997 out_x = after->org_u - end->org_u;
998 out_y = after->org_v - end->org_v;
999
1000 } while ( out_x == 0 && out_y == 0 );
1001
1002 orient_cur = psh_corner_orientation( in_x, in_y, out_x, out_y );
1003
1004 } while ( orient_cur == 0 );
1005
1006 if ( ( orient_cur ^ orient_prev ) < 0 )
1007 {
1008 do
1009 {
1010 psh_point_set_inflex( start );
1011 start = start->next;
1012 }
1013 while ( start != end );
1014
1015 psh_point_set_inflex( start );
1016 }
1017
1018 start = end;
1019 end = after;
1020 orient_prev = orient_cur;
1021 in_x = out_x;
1022 in_y = out_y;
1023
1024 } while ( !finished );
1025
1026 Skip:
1027 ;
1028 }
1029 }
1030
1031#endif /* COMPUTE_INFLEXS */
1032
1033
1034 static void
1035 psh_glyph_done( PSH_Glyph glyph )
1036 {
1037 FT_Memory memory = glyph->memory;
1038
1039
1040 psh_hint_table_done( &glyph->hint_tables[1], memory );
1041 psh_hint_table_done( &glyph->hint_tables[0], memory );
1042
1043 FT_FREE( glyph->points );
1044 FT_FREE( glyph->contours );
1045
1046 glyph->num_points = 0;
1047 glyph->num_contours = 0;
1048
1049 glyph->memory = NULL;
1050 }
1051
1052
1053 static int
1054 psh_compute_dir( FT_Pos dx,
1055 FT_Pos dy )
1056 {
1057 FT_Pos ax, ay;
1058 int result = PSH_DIR_NONE;
1059
1060
1061 ax = FT_ABS( dx );
1062 ay = FT_ABS( dy );
1063
1064 if ( ay * 12 < ax )
1065 {
1066 /* |dy| <<< |dx| means a near-horizontal segment */
1067 result = ( dx >= 0 ) ? PSH_DIR_RIGHT : PSH_DIR_LEFT;
1068 }
1069 else if ( ax * 12 < ay )
1070 {
1071 /* |dx| <<< |dy| means a near-vertical segment */
1072 result = ( dy >= 0 ) ? PSH_DIR_UP : PSH_DIR_DOWN;
1073 }
1074
1075 return result;
1076 }
1077
1078
1079 /* load outline point coordinates into hinter glyph */
1080 static void
1081 psh_glyph_load_points( PSH_Glyph glyph,
1082 FT_Int dimension )
1083 {
1084 FT_Vector* vec = glyph->outline->points;
1085 PSH_Point point = glyph->points;
1086 FT_UInt count = glyph->num_points;
1087
1088
1089 for ( ; count > 0; count--, point++, vec++ )
1090 {
1091 point->flags2 = 0;
1092 point->hint = NULL;
1093 if ( dimension == 0 )
1094 {
1095 point->org_u = vec->x;
1096 point->org_v = vec->y;
1097 }
1098 else
1099 {
1100 point->org_u = vec->y;
1101 point->org_v = vec->x;
1102 }
1103
1104#ifdef DEBUG_HINTER
1105 point->org_x = vec->x;
1106 point->org_y = vec->y;
1107#endif
1108
1109 }
1110 }
1111
1112
1113 /* save hinted point coordinates back to outline */
1114 static void
1115 psh_glyph_save_points( PSH_Glyph glyph,
1116 FT_Int dimension )
1117 {
1118 FT_UInt n;
1119 PSH_Point point = glyph->points;
1120 FT_Vector* vec = glyph->outline->points;
1121 char* tags = glyph->outline->tags;
1122
1123
1124 for ( n = 0; n < glyph->num_points; n++ )
1125 {
1126 if ( dimension == 0 )
1127 vec[n].x = point->cur_u;
1128 else
1129 vec[n].y = point->cur_u;
1130
1131 if ( psh_point_is_strong( point ) )
1132 tags[n] |= (char)( ( dimension == 0 ) ? 32 : 64 );
1133
1134#ifdef DEBUG_HINTER
1135
1136 if ( dimension == 0 )
1137 {
1138 point->cur_x = point->cur_u;
1139 point->flags_x = point->flags2 | point->flags;
1140 }
1141 else
1142 {
1143 point->cur_y = point->cur_u;
1144 point->flags_y = point->flags2 | point->flags;
1145 }
1146
1147#endif
1148
1149 point++;
1150 }
1151 }
1152
1153
1154 static FT_Error
1155 psh_glyph_init( PSH_Glyph glyph,
1156 FT_Outline* outline,
1157 PS_Hints ps_hints,
1158 PSH_Globals globals )
1159 {
1160 FT_Error error;
1161 FT_Memory memory;
1162
1163
1164 /* clear all fields */
1165 FT_ZERO( glyph );
1166
1167 memory = glyph->memory = globals->memory;
1168
1169 /* allocate and setup points + contours arrays */
1170 if ( FT_NEW_ARRAY( glyph->points, outline->n_points ) ||
1171 FT_NEW_ARRAY( glyph->contours, outline->n_contours ) )
1172 goto Exit;
1173
1174 glyph->num_points = (FT_UInt)outline->n_points;
1175 glyph->num_contours = (FT_UInt)outline->n_contours;
1176
1177 {
1178 FT_UInt first = 0, next, n;
1179 PSH_Point points = glyph->points;
1180 PSH_Contour contour = glyph->contours;
1181
1182
1183 for ( n = 0; n < glyph->num_contours; n++ )
1184 {
1185 FT_UInt count;
1186 PSH_Point point;
1187
1188
1189 next = (FT_UInt)outline->contours[n] + 1;
1190 count = next - first;
1191
1192 contour->start = points + first;
1193 contour->count = count;
1194
1195 if ( count > 0 )
1196 {
1197 point = points + first;
1198
1199 point->prev = points + next - 1;
1200 point->contour = contour;
1201
1202 for ( ; count > 1; count-- )
1203 {
1204 point[0].next = point + 1;
1205 point[1].prev = point;
1206 point++;
1207 point->contour = contour;
1208 }
1209 point->next = points + first;
1210 }
1211
1212 contour++;
1213 first = next;
1214 }
1215 }
1216
1217 {
1218 PSH_Point points = glyph->points;
1219 PSH_Point point = points;
1220 FT_Vector* vec = outline->points;
1221 FT_UInt n;
1222
1223
1224 for ( n = 0; n < glyph->num_points; n++, point++ )
1225 {
1226 FT_Int n_prev = (FT_Int)( point->prev - points );
1227 FT_Int n_next = (FT_Int)( point->next - points );
1228 FT_Pos dxi, dyi, dxo, dyo;
1229
1230
1231 if ( !( outline->tags[n] & FT_CURVE_TAG_ON ) )
1232 point->flags = PSH_POINT_OFF;
1233
1234 dxi = vec[n].x - vec[n_prev].x;
1235 dyi = vec[n].y - vec[n_prev].y;
1236
1237 point->dir_in = (FT_Char)psh_compute_dir( dxi, dyi );
1238
1239 dxo = vec[n_next].x - vec[n].x;
1240 dyo = vec[n_next].y - vec[n].y;
1241
1242 point->dir_out = (FT_Char)psh_compute_dir( dxo, dyo );
1243
1244 /* detect smooth points */
1245 if ( point->flags & PSH_POINT_OFF )
1246 point->flags |= PSH_POINT_SMOOTH;
1247
1248 else if ( point->dir_in == point->dir_out )
1249 {
1250 if ( point->dir_out != PSH_DIR_NONE ||
1251 psh_corner_is_flat( dxi, dyi, dxo, dyo ) )
1252 point->flags |= PSH_POINT_SMOOTH;
1253 }
1254 }
1255 }
1256
1257 glyph->outline = outline;
1258 glyph->globals = globals;
1259
1260#ifdef COMPUTE_INFLEXS
1261 psh_glyph_load_points( glyph, 0 );
1262 psh_glyph_compute_inflections( glyph );
1263#endif /* COMPUTE_INFLEXS */
1264
1265 /* now deal with hints tables */
1266 error = psh_hint_table_init( &glyph->hint_tables [0],
1267 &ps_hints->dimension[0].hints,
1268 &ps_hints->dimension[0].masks,
1269 &ps_hints->dimension[0].counters,
1270 memory );
1271 if ( error )
1272 goto Exit;
1273
1274 error = psh_hint_table_init( &glyph->hint_tables [1],
1275 &ps_hints->dimension[1].hints,
1276 &ps_hints->dimension[1].masks,
1277 &ps_hints->dimension[1].counters,
1278 memory );
1279 if ( error )
1280 goto Exit;
1281
1282 Exit:
1283 return error;
1284 }
1285
1286
1287 /* compute all extrema in a glyph for a given dimension */
1288 static void
1289 psh_glyph_compute_extrema( PSH_Glyph glyph )
1290 {
1291 FT_UInt n;
1292
1293
1294 /* first of all, compute all local extrema */
1295 for ( n = 0; n < glyph->num_contours; n++ )
1296 {
1297 PSH_Point first = glyph->contours[n].start;
1298 PSH_Point point, before, after;
1299
1300
1301 if ( glyph->contours[n].count == 0 )
1302 continue;
1303
1304 point = first;
1305 before = point;
1306
1307 do
1308 {
1309 before = before->prev;
1310 if ( before == first )
1311 goto Skip;
1312
1313 } while ( before->org_u == point->org_u );
1314
1315 first = point = before->next;
1316
1317 for (;;)
1318 {
1319 after = point;
1320 do
1321 {
1322 after = after->next;
1323 if ( after == first )
1324 goto Next;
1325
1326 } while ( after->org_u == point->org_u );
1327
1328 if ( before->org_u < point->org_u )
1329 {
1330 if ( after->org_u < point->org_u )
1331 {
1332 /* local maximum */
1333 goto Extremum;
1334 }
1335 }
1336 else /* before->org_u > point->org_u */
1337 {
1338 if ( after->org_u > point->org_u )
1339 {
1340 /* local minimum */
1341 Extremum:
1342 do
1343 {
1344 psh_point_set_extremum( point );
1345 point = point->next;
1346
1347 } while ( point != after );
1348 }
1349 }
1350
1351 before = after->prev;
1352 point = after;
1353
1354 } /* for */
1355
1356 Next:
1357 ;
1358 }
1359
1360 /* for each extremum, determine its direction along the */
1361 /* orthogonal axis */
1362 for ( n = 0; n < glyph->num_points; n++ )
1363 {
1364 PSH_Point point, before, after;
1365
1366
1367 point = &glyph->points[n];
1368 before = point;
1369 after = point;
1370
1371 if ( psh_point_is_extremum( point ) )
1372 {
1373 do
1374 {
1375 before = before->prev;
1376 if ( before == point )
1377 goto Skip;
1378
1379 } while ( before->org_v == point->org_v );
1380
1381 do
1382 {
1383 after = after->next;
1384 if ( after == point )
1385 goto Skip;
1386
1387 } while ( after->org_v == point->org_v );
1388 }
1389
1390 if ( before->org_v < point->org_v &&
1391 after->org_v > point->org_v )
1392 {
1393 psh_point_set_positive( point );
1394 }
1395 else if ( before->org_v > point->org_v &&
1396 after->org_v < point->org_v )
1397 {
1398 psh_point_set_negative( point );
1399 }
1400
1401 Skip:
1402 ;
1403 }
1404 }
1405
1406
1407 /* major_dir is the direction for points on the bottom/left of the stem; */
1408 /* Points on the top/right of the stem will have a direction of */
1409 /* -major_dir. */
1410
1411 static void
1412 psh_hint_table_find_strong_points( PSH_Hint_Table table,
1413 PSH_Point point,
1414 FT_UInt count,
1415 FT_Int threshold,
1416 FT_Int major_dir )
1417 {
1418 PSH_Hint* sort = table->sort;
1419 FT_UInt num_hints = table->num_hints;
1420
1421
1422 for ( ; count > 0; count--, point++ )
1423 {
1424 FT_Int point_dir = 0;
1425 FT_Pos org_u = point->org_u;
1426
1427
1428 if ( psh_point_is_strong( point ) )
1429 continue;
1430
1431 if ( PSH_DIR_COMPARE( point->dir_in, major_dir ) )
1432 point_dir = point->dir_in;
1433
1434 else if ( PSH_DIR_COMPARE( point->dir_out, major_dir ) )
1435 point_dir = point->dir_out;
1436
1437 if ( point_dir )
1438 {
1439 if ( point_dir == major_dir )
1440 {
1441 FT_UInt nn;
1442
1443
1444 for ( nn = 0; nn < num_hints; nn++ )
1445 {
1446 PSH_Hint hint = sort[nn];
1447 FT_Pos d = org_u - hint->org_pos;
1448
1449
1450 if ( d < threshold && -d < threshold )
1451 {
1452 psh_point_set_strong( point );
1453 point->flags2 |= PSH_POINT_EDGE_MIN;
1454 point->hint = hint;
1455 break;
1456 }
1457 }
1458 }
1459 else if ( point_dir == -major_dir )
1460 {
1461 FT_UInt nn;
1462
1463
1464 for ( nn = 0; nn < num_hints; nn++ )
1465 {
1466 PSH_Hint hint = sort[nn];
1467 FT_Pos d = org_u - hint->org_pos - hint->org_len;
1468
1469
1470 if ( d < threshold && -d < threshold )
1471 {
1472 psh_point_set_strong( point );
1473 point->flags2 |= PSH_POINT_EDGE_MAX;
1474 point->hint = hint;
1475 break;
1476 }
1477 }
1478 }
1479 }
1480
1481#if 1
1482 else if ( psh_point_is_extremum( point ) )
1483 {
1484 /* treat extrema as special cases for stem edge alignment */
1485 FT_UInt nn, min_flag, max_flag;
1486
1487
1488 if ( major_dir == PSH_DIR_HORIZONTAL )
1489 {
1490 min_flag = PSH_POINT_POSITIVE;
1491 max_flag = PSH_POINT_NEGATIVE;
1492 }
1493 else
1494 {
1495 min_flag = PSH_POINT_NEGATIVE;
1496 max_flag = PSH_POINT_POSITIVE;
1497 }
1498
1499 if ( point->flags2 & min_flag )
1500 {
1501 for ( nn = 0; nn < num_hints; nn++ )
1502 {
1503 PSH_Hint hint = sort[nn];
1504 FT_Pos d = org_u - hint->org_pos;
1505
1506
1507 if ( d < threshold && -d < threshold )
1508 {
1509 point->flags2 |= PSH_POINT_EDGE_MIN;
1510 point->hint = hint;
1511 psh_point_set_strong( point );
1512 break;
1513 }
1514 }
1515 }
1516 else if ( point->flags2 & max_flag )
1517 {
1518 for ( nn = 0; nn < num_hints; nn++ )
1519 {
1520 PSH_Hint hint = sort[nn];
1521 FT_Pos d = org_u - hint->org_pos - hint->org_len;
1522
1523
1524 if ( d < threshold && -d < threshold )
1525 {
1526 point->flags2 |= PSH_POINT_EDGE_MAX;
1527 point->hint = hint;
1528 psh_point_set_strong( point );
1529 break;
1530 }
1531 }
1532 }
1533
1534 if ( !point->hint )
1535 {
1536 for ( nn = 0; nn < num_hints; nn++ )
1537 {
1538 PSH_Hint hint = sort[nn];
1539
1540
1541 if ( org_u >= hint->org_pos &&
1542 org_u <= ADD_INT( hint->org_pos, hint->org_len ) )
1543 {
1544 point->hint = hint;
1545 break;
1546 }
1547 }
1548 }
1549 }
1550
1551#endif /* 1 */
1552 }
1553 }
1554
1555
1556 /* the accepted shift for strong points in fractional pixels */
1557#define PSH_STRONG_THRESHOLD 32
1558
1559 /* the maximum shift value in font units */
1560#define PSH_STRONG_THRESHOLD_MAXIMUM 30
1561
1562
1563 /* find strong points in a glyph */
1564 static void
1565 psh_glyph_find_strong_points( PSH_Glyph glyph,
1566 FT_Int dimension )
1567 {
1568 /* a point is `strong' if it is located on a stem edge and */
1569 /* has an `in' or `out' tangent parallel to the hint's direction */
1570
1571 PSH_Hint_Table table = &glyph->hint_tables[dimension];
1572 PS_Mask mask = table->hint_masks->masks;
1573 FT_UInt num_masks = table->hint_masks->num_masks;
1574 FT_UInt first = 0;
1575 FT_Int major_dir = ( dimension == 0 ) ? PSH_DIR_VERTICAL
1576 : PSH_DIR_HORIZONTAL;
1577 PSH_Dimension dim = &glyph->globals->dimension[dimension];
1578 FT_Fixed scale = dim->scale_mult;
1579 FT_Int threshold;
1580
1581
1582 threshold = (FT_Int)FT_DivFix( PSH_STRONG_THRESHOLD, scale );
1583 if ( threshold > PSH_STRONG_THRESHOLD_MAXIMUM )
1584 threshold = PSH_STRONG_THRESHOLD_MAXIMUM;
1585
1586 /* process secondary hints to `selected' points */
1587 if ( num_masks > 1 && glyph->num_points > 0 )
1588 {
1589 /* the `endchar' op can reduce the number of points */
1590 first = mask->end_point > glyph->num_points
1591 ? glyph->num_points
1592 : mask->end_point;
1593 mask++;
1594 for ( ; num_masks > 1; num_masks--, mask++ )
1595 {
1596 FT_UInt next = FT_MIN( mask->end_point, glyph->num_points );
1597
1598
1599 if ( next > first )
1600 {
1601 FT_UInt count = next - first;
1602 PSH_Point point = glyph->points + first;
1603
1604
1605 psh_hint_table_activate_mask( table, mask );
1606
1607 psh_hint_table_find_strong_points( table, point, count,
1608 threshold, major_dir );
1609 }
1610 first = next;
1611 }
1612 }
1613
1614 /* process primary hints for all points */
1615 if ( num_masks == 1 )
1616 {
1617 FT_UInt count = glyph->num_points;
1618 PSH_Point point = glyph->points;
1619
1620
1621 psh_hint_table_activate_mask( table, table->hint_masks->masks );
1622
1623 psh_hint_table_find_strong_points( table, point, count,
1624 threshold, major_dir );
1625 }
1626
1627 /* now, certain points may have been attached to a hint and */
1628 /* not marked as strong; update their flags then */
1629 {
1630 FT_UInt count = glyph->num_points;
1631 PSH_Point point = glyph->points;
1632
1633
1634 for ( ; count > 0; count--, point++ )
1635 if ( point->hint && !psh_point_is_strong( point ) )
1636 psh_point_set_strong( point );
1637 }
1638 }
1639
1640
1641 /* find points in a glyph which are in a blue zone and have `in' or */
1642 /* `out' tangents parallel to the horizontal axis */
1643 static void
1644 psh_glyph_find_blue_points( PSH_Blues blues,
1645 PSH_Glyph glyph )
1646 {
1647 PSH_Blue_Table table;
1648 PSH_Blue_Zone zone;
1649 FT_UInt glyph_count = glyph->num_points;
1650 FT_UInt blue_count;
1651 PSH_Point point = glyph->points;
1652
1653
1654 for ( ; glyph_count > 0; glyph_count--, point++ )
1655 {
1656 FT_Pos y;
1657
1658
1659 /* check tangents */
1660 if ( !PSH_DIR_COMPARE( point->dir_in, PSH_DIR_HORIZONTAL ) &&
1661 !PSH_DIR_COMPARE( point->dir_out, PSH_DIR_HORIZONTAL ) )
1662 continue;
1663
1664 /* skip strong points */
1665 if ( psh_point_is_strong( point ) )
1666 continue;
1667
1668 y = point->org_u;
1669
1670 /* look up top zones */
1671 table = &blues->normal_top;
1672 blue_count = table->count;
1673 zone = table->zones;
1674
1675 for ( ; blue_count > 0; blue_count--, zone++ )
1676 {
1677 FT_Pos delta = y - zone->org_bottom;
1678
1679
1680 if ( delta < -blues->blue_fuzz )
1681 break;
1682
1683 if ( y <= zone->org_top + blues->blue_fuzz )
1684 if ( blues->no_overshoots || delta <= blues->blue_threshold )
1685 {
1686 point->cur_u = zone->cur_bottom;
1687 psh_point_set_strong( point );
1688 psh_point_set_fitted( point );
1689 }
1690 }
1691
1692 /* look up bottom zones */
1693 table = &blues->normal_bottom;
1694 blue_count = table->count;
1695 zone = table->zones + blue_count - 1;
1696
1697 for ( ; blue_count > 0; blue_count--, zone-- )
1698 {
1699 FT_Pos delta = zone->org_top - y;
1700
1701
1702 if ( delta < -blues->blue_fuzz )
1703 break;
1704
1705 if ( y >= zone->org_bottom - blues->blue_fuzz )
1706 if ( blues->no_overshoots || delta < blues->blue_threshold )
1707 {
1708 point->cur_u = zone->cur_top;
1709 psh_point_set_strong( point );
1710 psh_point_set_fitted( point );
1711 }
1712 }
1713 }
1714 }
1715
1716
1717 /* interpolate strong points with the help of hinted coordinates */
1718 static void
1719 psh_glyph_interpolate_strong_points( PSH_Glyph glyph,
1720 FT_Int dimension )
1721 {
1722 PSH_Dimension dim = &glyph->globals->dimension[dimension];
1723 FT_Fixed scale = dim->scale_mult;
1724
1725 FT_UInt count = glyph->num_points;
1726 PSH_Point point = glyph->points;
1727
1728
1729 for ( ; count > 0; count--, point++ )
1730 {
1731 PSH_Hint hint = point->hint;
1732
1733
1734 if ( hint )
1735 {
1736 FT_Pos delta;
1737
1738
1739 if ( psh_point_is_edge_min( point ) )
1740 point->cur_u = hint->cur_pos;
1741
1742 else if ( psh_point_is_edge_max( point ) )
1743 point->cur_u = hint->cur_pos + hint->cur_len;
1744
1745 else
1746 {
1747 delta = point->org_u - hint->org_pos;
1748
1749 if ( delta <= 0 )
1750 point->cur_u = hint->cur_pos + FT_MulFix( delta, scale );
1751
1752 else if ( delta >= hint->org_len )
1753 point->cur_u = hint->cur_pos + hint->cur_len +
1754 FT_MulFix( delta - hint->org_len, scale );
1755
1756 else /* hint->org_len > 0 */
1757 point->cur_u = hint->cur_pos +
1758 FT_MulDiv( delta, hint->cur_len,
1759 hint->org_len );
1760 }
1761 psh_point_set_fitted( point );
1762 }
1763 }
1764 }
1765
1766
1767#define PSH_MAX_STRONG_INTERNAL 16
1768
1769 static void
1770 psh_glyph_interpolate_normal_points( PSH_Glyph glyph,
1771 FT_Int dimension )
1772 {
1773
1774#if 1
1775 /* first technique: a point is strong if it is a local extremum */
1776
1777 PSH_Dimension dim = &glyph->globals->dimension[dimension];
1778 FT_Fixed scale = dim->scale_mult;
1779 FT_Memory memory = glyph->memory;
1780
1781 PSH_Point* strongs = NULL;
1782 PSH_Point strongs_0[PSH_MAX_STRONG_INTERNAL];
1783 FT_UInt num_strongs = 0;
1784
1785 PSH_Point points = glyph->points;
1786 PSH_Point points_end = points + glyph->num_points;
1787 PSH_Point point;
1788
1789
1790 /* first count the number of strong points */
1791 for ( point = points; point < points_end; point++ )
1792 {
1793 if ( psh_point_is_strong( point ) )
1794 num_strongs++;
1795 }
1796
1797 if ( num_strongs == 0 ) /* nothing to do here */
1798 return;
1799
1800 /* allocate an array to store a list of points, */
1801 /* stored in increasing org_u order */
1802 if ( num_strongs <= PSH_MAX_STRONG_INTERNAL )
1803 strongs = strongs_0;
1804 else
1805 {
1806 FT_Error error;
1807
1808
1809 if ( FT_NEW_ARRAY( strongs, num_strongs ) )
1810 return;
1811 }
1812
1813 num_strongs = 0;
1814 for ( point = points; point < points_end; point++ )
1815 {
1816 PSH_Point* insert;
1817
1818
1819 if ( !psh_point_is_strong( point ) )
1820 continue;
1821
1822 for ( insert = strongs + num_strongs; insert > strongs; insert-- )
1823 {
1824 if ( insert[-1]->org_u <= point->org_u )
1825 break;
1826
1827 insert[0] = insert[-1];
1828 }
1829 insert[0] = point;
1830 num_strongs++;
1831 }
1832
1833 /* now try to interpolate all normal points */
1834 for ( point = points; point < points_end; point++ )
1835 {
1836 if ( psh_point_is_strong( point ) )
1837 continue;
1838
1839 /* sometimes, some local extrema are smooth points */
1840 if ( psh_point_is_smooth( point ) )
1841 {
1842 if ( point->dir_in == PSH_DIR_NONE ||
1843 point->dir_in != point->dir_out )
1844 continue;
1845
1846 if ( !psh_point_is_extremum( point ) &&
1847 !psh_point_is_inflex( point ) )
1848 continue;
1849
1850 point->flags &= ~PSH_POINT_SMOOTH;
1851 }
1852
1853 /* find best enclosing point coordinates then interpolate */
1854 {
1855 PSH_Point before, after;
1856 FT_UInt nn;
1857
1858
1859 for ( nn = 0; nn < num_strongs; nn++ )
1860 if ( strongs[nn]->org_u > point->org_u )
1861 break;
1862
1863 if ( nn == 0 ) /* point before the first strong point */
1864 {
1865 after = strongs[0];
1866
1867 point->cur_u = after->cur_u +
1868 FT_MulFix( point->org_u - after->org_u,
1869 scale );
1870 }
1871 else
1872 {
1873 before = strongs[nn - 1];
1874
1875 for ( nn = num_strongs; nn > 0; nn-- )
1876 if ( strongs[nn - 1]->org_u < point->org_u )
1877 break;
1878
1879 if ( nn == num_strongs ) /* point is after last strong point */
1880 {
1881 before = strongs[nn - 1];
1882
1883 point->cur_u = before->cur_u +
1884 FT_MulFix( point->org_u - before->org_u,
1885 scale );
1886 }
1887 else
1888 {
1889 FT_Pos u;
1890
1891
1892 after = strongs[nn];
1893
1894 /* now interpolate point between before and after */
1895 u = point->org_u;
1896
1897 if ( u == before->org_u )
1898 point->cur_u = before->cur_u;
1899
1900 else if ( u == after->org_u )
1901 point->cur_u = after->cur_u;
1902
1903 else
1904 point->cur_u = before->cur_u +
1905 FT_MulDiv( u - before->org_u,
1906 after->cur_u - before->cur_u,
1907 after->org_u - before->org_u );
1908 }
1909 }
1910 psh_point_set_fitted( point );
1911 }
1912 }
1913
1914 if ( strongs != strongs_0 )
1915 FT_FREE( strongs );
1916
1917#endif /* 1 */
1918
1919 }
1920
1921
1922 /* interpolate other points */
1923 static void
1924 psh_glyph_interpolate_other_points( PSH_Glyph glyph,
1925 FT_Int dimension )
1926 {
1927 PSH_Dimension dim = &glyph->globals->dimension[dimension];
1928 FT_Fixed scale = dim->scale_mult;
1929 FT_Fixed delta = dim->scale_delta;
1930 PSH_Contour contour = glyph->contours;
1931 FT_UInt num_contours = glyph->num_contours;
1932
1933
1934 for ( ; num_contours > 0; num_contours--, contour++ )
1935 {
1936 PSH_Point start = contour->start;
1937 PSH_Point first, next, point;
1938 FT_UInt fit_count;
1939
1940
1941 /* count the number of strong points in this contour */
1942 next = start + contour->count;
1943 fit_count = 0;
1944 first = NULL;
1945
1946 for ( point = start; point < next; point++ )
1947 if ( psh_point_is_fitted( point ) )
1948 {
1949 if ( !first )
1950 first = point;
1951
1952 fit_count++;
1953 }
1954
1955 /* if there are less than 2 fitted points in the contour, we */
1956 /* simply scale and eventually translate the contour points */
1957 if ( fit_count < 2 )
1958 {
1959 if ( fit_count == 1 )
1960 delta = first->cur_u - FT_MulFix( first->org_u, scale );
1961
1962 for ( point = start; point < next; point++ )
1963 if ( point != first )
1964 point->cur_u = FT_MulFix( point->org_u, scale ) + delta;
1965
1966 goto Next_Contour;
1967 }
1968
1969 /* there are more than 2 strong points in this contour; we */
1970 /* need to interpolate weak points between them */
1971 start = first;
1972 do
1973 {
1974 /* skip consecutive fitted points */
1975 for (;;)
1976 {
1977 next = first->next;
1978 if ( next == start )
1979 goto Next_Contour;
1980
1981 if ( !psh_point_is_fitted( next ) )
1982 break;
1983
1984 first = next;
1985 }
1986
1987 /* find next fitted point after unfitted one */
1988 for (;;)
1989 {
1990 next = next->next;
1991 if ( psh_point_is_fitted( next ) )
1992 break;
1993 }
1994
1995 /* now interpolate between them */
1996 {
1997 FT_Pos org_a, org_ab, cur_a, cur_ab;
1998 FT_Pos org_c, org_ac, cur_c;
1999 FT_Fixed scale_ab;
2000
2001
2002 if ( first->org_u <= next->org_u )
2003 {
2004 org_a = first->org_u;
2005 cur_a = first->cur_u;
2006 org_ab = next->org_u - org_a;
2007 cur_ab = next->cur_u - cur_a;
2008 }
2009 else
2010 {
2011 org_a = next->org_u;
2012 cur_a = next->cur_u;
2013 org_ab = first->org_u - org_a;
2014 cur_ab = first->cur_u - cur_a;
2015 }
2016
2017 scale_ab = 0x10000L;
2018 if ( org_ab > 0 )
2019 scale_ab = FT_DivFix( cur_ab, org_ab );
2020
2021 point = first->next;
2022 do
2023 {
2024 org_c = point->org_u;
2025 org_ac = org_c - org_a;
2026
2027 if ( org_ac <= 0 )
2028 {
2029 /* on the left of the interpolation zone */
2030 cur_c = cur_a + FT_MulFix( org_ac, scale );
2031 }
2032 else if ( org_ac >= org_ab )
2033 {
2034 /* on the right on the interpolation zone */
2035 cur_c = cur_a + cur_ab + FT_MulFix( org_ac - org_ab, scale );
2036 }
2037 else
2038 {
2039 /* within the interpolation zone */
2040 cur_c = cur_a + FT_MulFix( org_ac, scale_ab );
2041 }
2042
2043 point->cur_u = cur_c;
2044
2045 point = point->next;
2046
2047 } while ( point != next );
2048 }
2049
2050 /* keep going until all points in the contours have been processed */
2051 first = next;
2052
2053 } while ( first != start );
2054
2055 Next_Contour:
2056 ;
2057 }
2058 }
2059
2060
2061 /*************************************************************************/
2062 /*************************************************************************/
2063 /***** *****/
2064 /***** HIGH-LEVEL INTERFACE *****/
2065 /***** *****/
2066 /*************************************************************************/
2067 /*************************************************************************/
2068
2069 FT_Error
2070 ps_hints_apply( PS_Hints ps_hints,
2071 FT_Outline* outline,
2072 PSH_Globals globals,
2073 FT_Render_Mode hint_mode )
2074 {
2075 PSH_GlyphRec glyphrec;
2076 PSH_Glyph glyph = &glyphrec;
2077 FT_Error error;
2078#ifdef DEBUG_HINTER
2079 FT_Memory memory;
2080#endif
2081 FT_Int dimension;
2082
2083
2084 /* something to do? */
2085 if ( outline->n_points == 0 || outline->n_contours == 0 )
2086 return FT_Err_Ok;
2087
2088#ifdef DEBUG_HINTER
2089
2090 memory = globals->memory;
2091
2092 if ( ps_debug_glyph )
2093 {
2094 psh_glyph_done( ps_debug_glyph );
2095 FT_FREE( ps_debug_glyph );
2096 }
2097
2098 if ( FT_NEW( glyph ) )
2099 return error;
2100
2101 ps_debug_glyph = glyph;
2102
2103#endif /* DEBUG_HINTER */
2104
2105 error = psh_glyph_init( glyph, outline, ps_hints, globals );
2106 if ( error )
2107 goto Exit;
2108
2109 /* try to optimize the y_scale so that the top of non-capital letters
2110 * is aligned on a pixel boundary whenever possible
2111 */
2112 {
2113 PSH_Dimension dim_x = &glyph->globals->dimension[0];
2114 PSH_Dimension dim_y = &glyph->globals->dimension[1];
2115
2116 FT_Fixed x_scale = dim_x->scale_mult;
2117 FT_Fixed y_scale = dim_y->scale_mult;
2118
2119 FT_Fixed old_x_scale = x_scale;
2120 FT_Fixed old_y_scale = y_scale;
2121
2122 FT_Fixed scaled;
2123 FT_Fixed fitted;
2124
2125 FT_Bool rescale = FALSE;
2126
2127
2128 scaled = FT_MulFix( globals->blues.normal_top.zones->org_ref, y_scale );
2129 fitted = FT_PIX_ROUND( scaled );
2130
2131 if ( fitted != 0 && scaled != fitted )
2132 {
2133 rescale = TRUE;
2134
2135 y_scale = FT_MulDiv( y_scale, fitted, scaled );
2136
2137 if ( fitted < scaled )
2138 x_scale -= x_scale / 50;
2139
2140 psh_globals_set_scale( glyph->globals, x_scale, y_scale, 0, 0 );
2141 }
2142
2143 glyph->do_horz_hints = 1;
2144 glyph->do_vert_hints = 1;
2145
2146 glyph->do_horz_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO ||
2147 hint_mode == FT_RENDER_MODE_LCD );
2148
2149 glyph->do_vert_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO ||
2150 hint_mode == FT_RENDER_MODE_LCD_V );
2151
2152 glyph->do_stem_adjust = FT_BOOL( hint_mode != FT_RENDER_MODE_LIGHT );
2153
2154 for ( dimension = 0; dimension < 2; dimension++ )
2155 {
2156 /* load outline coordinates into glyph */
2157 psh_glyph_load_points( glyph, dimension );
2158
2159 /* compute local extrema */
2160 psh_glyph_compute_extrema( glyph );
2161
2162 /* compute aligned stem/hints positions */
2163 psh_hint_table_align_hints( &glyph->hint_tables[dimension],
2164 glyph->globals,
2165 dimension,
2166 glyph );
2167
2168 /* find strong points, align them, then interpolate others */
2169 psh_glyph_find_strong_points( glyph, dimension );
2170 if ( dimension == 1 )
2171 psh_glyph_find_blue_points( &globals->blues, glyph );
2172 psh_glyph_interpolate_strong_points( glyph, dimension );
2173 psh_glyph_interpolate_normal_points( glyph, dimension );
2174 psh_glyph_interpolate_other_points( glyph, dimension );
2175
2176 /* save hinted coordinates back to outline */
2177 psh_glyph_save_points( glyph, dimension );
2178
2179 if ( rescale )
2180 psh_globals_set_scale( glyph->globals,
2181 old_x_scale, old_y_scale, 0, 0 );
2182 }
2183 }
2184
2185 Exit:
2186
2187#ifndef DEBUG_HINTER
2188 psh_glyph_done( glyph );
2189#endif
2190
2191 return error;
2192 }
2193
2194
2195/* END */
2196