Sync with trunk head
[reactos.git] / lib / 3rdparty / freetype / src / autofit / afhints.c
1 /***************************************************************************/
2 /* */
3 /* afhints.c */
4 /* */
5 /* Auto-fitter hinting routines (body). */
6 /* */
7 /* Copyright 2003, 2004, 2005, 2006, 2007 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 "afhints.h"
20 #include "aferrors.h"
21 #include FT_INTERNAL_CALC_H
22
23
24 FT_LOCAL_DEF( FT_Error )
25 af_axis_hints_new_segment( AF_AxisHints axis,
26 FT_Memory memory,
27 AF_Segment *asegment )
28 {
29 FT_Error error = AF_Err_Ok;
30 AF_Segment segment = NULL;
31
32
33 if ( axis->num_segments >= axis->max_segments )
34 {
35 FT_Int old_max = axis->max_segments;
36 FT_Int new_max = old_max;
37 FT_Int big_max = FT_INT_MAX / sizeof ( *segment );
38
39
40 if ( old_max >= big_max )
41 {
42 error = AF_Err_Out_Of_Memory;
43 goto Exit;
44 }
45
46 new_max += ( new_max >> 2 ) + 4;
47 if ( new_max < old_max || new_max > big_max )
48 new_max = big_max;
49
50 if ( FT_RENEW_ARRAY( axis->segments, old_max, new_max ) )
51 goto Exit;
52
53 axis->max_segments = new_max;
54 }
55
56 segment = axis->segments + axis->num_segments++;
57
58 Exit:
59 *asegment = segment;
60 return error;
61 }
62
63
64 FT_LOCAL( FT_Error )
65 af_axis_hints_new_edge( AF_AxisHints axis,
66 FT_Int fpos,
67 AF_Direction dir,
68 FT_Memory memory,
69 AF_Edge *aedge )
70 {
71 FT_Error error = AF_Err_Ok;
72 AF_Edge edge = NULL;
73 AF_Edge edges;
74
75
76 if ( axis->num_edges >= axis->max_edges )
77 {
78 FT_Int old_max = axis->max_edges;
79 FT_Int new_max = old_max;
80 FT_Int big_max = FT_INT_MAX / sizeof ( *edge );
81
82
83 if ( old_max >= big_max )
84 {
85 error = AF_Err_Out_Of_Memory;
86 goto Exit;
87 }
88
89 new_max += ( new_max >> 2 ) + 4;
90 if ( new_max < old_max || new_max > big_max )
91 new_max = big_max;
92
93 if ( FT_RENEW_ARRAY( axis->edges, old_max, new_max ) )
94 goto Exit;
95
96 axis->max_edges = new_max;
97 }
98
99 edges = axis->edges;
100 edge = edges + axis->num_edges;
101
102 while ( edge > edges )
103 {
104 if ( edge[-1].fpos < fpos )
105 break;
106
107 /* we want the edge with same position and minor direction */
108 /* to appear before those in the major one in the list */
109 if ( edge[-1].fpos == fpos && dir == axis->major_dir )
110 break;
111
112 edge[0] = edge[-1];
113 edge--;
114 }
115
116 axis->num_edges++;
117
118 FT_ZERO( edge );
119 edge->fpos = (FT_Short)fpos;
120 edge->dir = (FT_Char)dir;
121
122 Exit:
123 *aedge = edge;
124 return error;
125 }
126
127
128 #ifdef AF_DEBUG
129
130 #include <stdio.h>
131
132 static const char*
133 af_dir_str( AF_Direction dir )
134 {
135 const char* result;
136
137
138 switch ( dir )
139 {
140 case AF_DIR_UP:
141 result = "up";
142 break;
143 case AF_DIR_DOWN:
144 result = "down";
145 break;
146 case AF_DIR_LEFT:
147 result = "left";
148 break;
149 case AF_DIR_RIGHT:
150 result = "right";
151 break;
152 default:
153 result = "none";
154 }
155
156 return result;
157 }
158
159
160 #define AF_INDEX_NUM( ptr, base ) ( (ptr) ? ( (ptr) - (base) ) : -1 )
161
162
163 void
164 af_glyph_hints_dump_points( AF_GlyphHints hints )
165 {
166 AF_Point points = hints->points;
167 AF_Point limit = points + hints->num_points;
168 AF_Point point;
169
170
171 printf( "Table of points:\n" );
172 printf( " [ index | xorg | yorg | xscale | yscale "
173 "| xfit | yfit | flags ]\n" );
174
175 for ( point = points; point < limit; point++ )
176 {
177 printf( " [ %5d | %5d | %5d | %-5.2f | %-5.2f "
178 "| %-5.2f | %-5.2f | %c%c%c%c%c%c ]\n",
179 point - points,
180 point->fx,
181 point->fy,
182 point->ox/64.0,
183 point->oy/64.0,
184 point->x/64.0,
185 point->y/64.0,
186 ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) ? 'w' : ' ',
187 ( point->flags & AF_FLAG_INFLECTION ) ? 'i' : ' ',
188 ( point->flags & AF_FLAG_EXTREMA_X ) ? '<' : ' ',
189 ( point->flags & AF_FLAG_EXTREMA_Y ) ? 'v' : ' ',
190 ( point->flags & AF_FLAG_ROUND_X ) ? '(' : ' ',
191 ( point->flags & AF_FLAG_ROUND_Y ) ? 'u' : ' ');
192 }
193 printf( "\n" );
194 }
195
196
197 static const char*
198 af_edge_flags_to_string( AF_Edge_Flags flags )
199 {
200 static char temp[32];
201 int pos = 0;
202
203
204 if ( flags & AF_EDGE_ROUND )
205 {
206 memcpy( temp + pos, "round", 5 );
207 pos += 5;
208 }
209 if ( flags & AF_EDGE_SERIF )
210 {
211 if ( pos > 0 )
212 temp[pos++] = ' ';
213 memcpy( temp + pos, "serif", 5 );
214 pos += 5;
215 }
216 if ( pos == 0 )
217 return "normal";
218
219 temp[pos] = 0;
220
221 return temp;
222 }
223
224
225 /* A function to dump the array of linked segments. */
226 void
227 af_glyph_hints_dump_segments( AF_GlyphHints hints )
228 {
229 FT_Int dimension;
230
231
232 for ( dimension = 1; dimension >= 0; dimension-- )
233 {
234 AF_AxisHints axis = &hints->axis[dimension];
235 AF_Segment segments = axis->segments;
236 AF_Segment limit = segments + axis->num_segments;
237 AF_Segment seg;
238
239
240 printf ( "Table of %s segments:\n",
241 dimension == AF_DIMENSION_HORZ ? "vertical" : "horizontal" );
242 printf ( " [ index | pos | dir | link | serif |"
243 " height | extra | flags ]\n" );
244
245 for ( seg = segments; seg < limit; seg++ )
246 {
247 printf ( " [ %5d | %5.2g | %5s | %4d | %5d | %5d | %5d | %s ]\n",
248 seg - segments,
249 dimension == AF_DIMENSION_HORZ ? (int)seg->first->ox / 64.0
250 : (int)seg->first->oy / 64.0,
251 af_dir_str( (AF_Direction)seg->dir ),
252 AF_INDEX_NUM( seg->link, segments ),
253 AF_INDEX_NUM( seg->serif, segments ),
254 seg->height,
255 seg->height - ( seg->max_coord - seg->min_coord ),
256 af_edge_flags_to_string( seg->flags ) );
257 }
258 printf( "\n" );
259 }
260 }
261
262
263 void
264 af_glyph_hints_dump_edges( AF_GlyphHints hints )
265 {
266 FT_Int dimension;
267
268
269 for ( dimension = 1; dimension >= 0; dimension-- )
270 {
271 AF_AxisHints axis = &hints->axis[dimension];
272 AF_Edge edges = axis->edges;
273 AF_Edge limit = edges + axis->num_edges;
274 AF_Edge edge;
275
276
277 /*
278 * note: AF_DIMENSION_HORZ corresponds to _vertical_ edges
279 * since they have constant a X coordinate.
280 */
281 printf ( "Table of %s edges:\n",
282 dimension == AF_DIMENSION_HORZ ? "vertical" : "horizontal" );
283 printf ( " [ index | pos | dir | link |"
284 " serif | blue | opos | pos | flags ]\n" );
285
286 for ( edge = edges; edge < limit; edge++ )
287 {
288 printf ( " [ %5d | %5.2g | %5s | %4d |"
289 " %5d | %c | %5.2f | %5.2f | %s ]\n",
290 edge - edges,
291 (int)edge->opos / 64.0,
292 af_dir_str( (AF_Direction)edge->dir ),
293 AF_INDEX_NUM( edge->link, edges ),
294 AF_INDEX_NUM( edge->serif, edges ),
295 edge->blue_edge ? 'y' : 'n',
296 edge->opos / 64.0,
297 edge->pos / 64.0,
298 af_edge_flags_to_string( edge->flags ) );
299 }
300 printf( "\n" );
301 }
302 }
303
304 #else /* !AF_DEBUG */
305
306 /* these empty stubs are only used to link the `ftgrid' test program */
307 /* when debugging is disabled */
308
309 void
310 af_glyph_hints_dump_points( AF_GlyphHints hints )
311 {
312 FT_UNUSED( hints );
313 }
314
315
316 void
317 af_glyph_hints_dump_segments( AF_GlyphHints hints )
318 {
319 FT_UNUSED( hints );
320 }
321
322
323 void
324 af_glyph_hints_dump_edges( AF_GlyphHints hints )
325 {
326 FT_UNUSED( hints );
327 }
328
329 #endif /* !AF_DEBUG */
330
331
332 /* compute the direction value of a given vector */
333 FT_LOCAL_DEF( AF_Direction )
334 af_direction_compute( FT_Pos dx,
335 FT_Pos dy )
336 {
337 FT_Pos ll, ss; /* long and short arm lengths */
338 AF_Direction dir; /* candidate direction */
339
340
341 if ( dy >= dx )
342 {
343 if ( dy >= -dx )
344 {
345 dir = AF_DIR_UP;
346 ll = dy;
347 ss = dx;
348 }
349 else
350 {
351 dir = AF_DIR_LEFT;
352 ll = -dx;
353 ss = dy;
354 }
355 }
356 else /* dy < dx */
357 {
358 if ( dy >= -dx )
359 {
360 dir = AF_DIR_RIGHT;
361 ll = dx;
362 ss = dy;
363 }
364 else
365 {
366 dir = AF_DIR_DOWN;
367 ll = dy;
368 ss = dx;
369 }
370 }
371
372 ss *= 14;
373 if ( FT_ABS( ll ) <= FT_ABS( ss ) )
374 dir = AF_DIR_NONE;
375
376 return dir;
377 }
378
379
380 /* compute all inflex points in a given glyph */
381
382 static void
383 af_glyph_hints_compute_inflections( AF_GlyphHints hints )
384 {
385 AF_Point* contour = hints->contours;
386 AF_Point* contour_limit = contour + hints->num_contours;
387
388
389 /* do each contour separately */
390 for ( ; contour < contour_limit; contour++ )
391 {
392 AF_Point point = contour[0];
393 AF_Point first = point;
394 AF_Point start = point;
395 AF_Point end = point;
396 AF_Point before;
397 AF_Point after;
398 FT_Pos in_x, in_y, out_x, out_y;
399 AF_Angle orient_prev, orient_cur;
400 FT_Int finished = 0;
401
402
403 /* compute first segment in contour */
404 first = point;
405
406 start = end = first;
407 do
408 {
409 end = end->next;
410 if ( end == first )
411 goto Skip;
412
413 in_x = end->fx - start->fx;
414 in_y = end->fy - start->fy;
415
416 } while ( in_x == 0 && in_y == 0 );
417
418 /* extend the segment start whenever possible */
419 before = start;
420 do
421 {
422 do
423 {
424 start = before;
425 before = before->prev;
426 if ( before == first )
427 goto Skip;
428
429 out_x = start->fx - before->fx;
430 out_y = start->fy - before->fy;
431
432 } while ( out_x == 0 && out_y == 0 );
433
434 orient_prev = ft_corner_orientation( in_x, in_y, out_x, out_y );
435
436 } while ( orient_prev == 0 );
437
438 first = start;
439
440 in_x = out_x;
441 in_y = out_y;
442
443 /* now process all segments in the contour */
444 do
445 {
446 /* first, extend current segment's end whenever possible */
447 after = end;
448 do
449 {
450 do
451 {
452 end = after;
453 after = after->next;
454 if ( after == first )
455 finished = 1;
456
457 out_x = after->fx - end->fx;
458 out_y = after->fy - end->fy;
459
460 } while ( out_x == 0 && out_y == 0 );
461
462 orient_cur = ft_corner_orientation( in_x, in_y, out_x, out_y );
463
464 } while ( orient_cur == 0 );
465
466 if ( ( orient_prev + orient_cur ) == 0 )
467 {
468 /* we have an inflection point here */
469 do
470 {
471 start->flags |= AF_FLAG_INFLECTION;
472 start = start->next;
473
474 } while ( start != end );
475
476 start->flags |= AF_FLAG_INFLECTION;
477 }
478
479 start = end;
480 end = after;
481
482 orient_prev = orient_cur;
483 in_x = out_x;
484 in_y = out_y;
485
486 } while ( !finished );
487
488 Skip:
489 ;
490 }
491 }
492
493
494 FT_LOCAL_DEF( void )
495 af_glyph_hints_init( AF_GlyphHints hints,
496 FT_Memory memory )
497 {
498 FT_ZERO( hints );
499 hints->memory = memory;
500 }
501
502
503 FT_LOCAL_DEF( void )
504 af_glyph_hints_done( AF_GlyphHints hints )
505 {
506 if ( hints && hints->memory )
507 {
508 FT_Memory memory = hints->memory;
509 int dim;
510
511
512 /*
513 * note that we don't need to free the segment and edge
514 * buffers, since they are really within the hints->points array
515 */
516 for ( dim = 0; dim < AF_DIMENSION_MAX; dim++ )
517 {
518 AF_AxisHints axis = &hints->axis[dim];
519
520
521 axis->num_segments = 0;
522 axis->max_segments = 0;
523 FT_FREE( axis->segments );
524
525 axis->num_edges = 0;
526 axis->max_edges = 0;
527 FT_FREE( axis->edges );
528 }
529
530 FT_FREE( hints->contours );
531 hints->max_contours = 0;
532 hints->num_contours = 0;
533
534 FT_FREE( hints->points );
535 hints->num_points = 0;
536 hints->max_points = 0;
537
538 hints->memory = NULL;
539 }
540 }
541
542
543 FT_LOCAL_DEF( void )
544 af_glyph_hints_rescale( AF_GlyphHints hints,
545 AF_ScriptMetrics metrics )
546 {
547 hints->metrics = metrics;
548 hints->scaler_flags = metrics->scaler.flags;
549 }
550
551
552 FT_LOCAL_DEF( FT_Error )
553 af_glyph_hints_reload( AF_GlyphHints hints,
554 FT_Outline* outline,
555 FT_Bool get_inflections )
556 {
557 FT_Error error = AF_Err_Ok;
558 AF_Point points;
559 FT_UInt old_max, new_max;
560 FT_Fixed x_scale = hints->x_scale;
561 FT_Fixed y_scale = hints->y_scale;
562 FT_Pos x_delta = hints->x_delta;
563 FT_Pos y_delta = hints->y_delta;
564 FT_Memory memory = hints->memory;
565
566
567 hints->num_points = 0;
568 hints->num_contours = 0;
569
570 hints->axis[0].num_segments = 0;
571 hints->axis[0].num_edges = 0;
572 hints->axis[1].num_segments = 0;
573 hints->axis[1].num_edges = 0;
574
575 /* first of all, reallocate the contours array when necessary */
576 new_max = (FT_UInt)outline->n_contours;
577 old_max = hints->max_contours;
578 if ( new_max > old_max )
579 {
580 new_max = ( new_max + 3 ) & ~3;
581
582 if ( FT_RENEW_ARRAY( hints->contours, old_max, new_max ) )
583 goto Exit;
584
585 hints->max_contours = new_max;
586 }
587
588 /*
589 * then reallocate the points arrays if necessary --
590 * note that we reserve two additional point positions, used to
591 * hint metrics appropriately
592 */
593 new_max = (FT_UInt)( outline->n_points + 2 );
594 old_max = hints->max_points;
595 if ( new_max > old_max )
596 {
597 new_max = ( new_max + 2 + 7 ) & ~7;
598
599 if ( FT_RENEW_ARRAY( hints->points, old_max, new_max ) )
600 goto Exit;
601
602 hints->max_points = new_max;
603 }
604
605 hints->num_points = outline->n_points;
606 hints->num_contours = outline->n_contours;
607
608 /* We can't rely on the value of `FT_Outline.flags' to know the fill */
609 /* direction used for a glyph, given that some fonts are broken (e.g., */
610 /* the Arphic ones). We thus recompute it each time we need to. */
611 /* */
612 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_UP;
613 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_LEFT;
614
615 if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_POSTSCRIPT )
616 {
617 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_DOWN;
618 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_RIGHT;
619 }
620
621 hints->x_scale = x_scale;
622 hints->y_scale = y_scale;
623 hints->x_delta = x_delta;
624 hints->y_delta = y_delta;
625
626 hints->xmin_delta = 0;
627 hints->xmax_delta = 0;
628
629 points = hints->points;
630 if ( hints->num_points == 0 )
631 goto Exit;
632
633 {
634 AF_Point point;
635 AF_Point point_limit = points + hints->num_points;
636
637
638 /* compute coordinates & Bezier flags, next and prev */
639 {
640 FT_Vector* vec = outline->points;
641 char* tag = outline->tags;
642 AF_Point first = points;
643 AF_Point end = points + outline->contours[0];
644 AF_Point prev = end;
645 FT_Int contour_index = 0;
646
647
648 for ( point = points; point < point_limit; point++, vec++, tag++ )
649 {
650 point->fx = (FT_Short)vec->x;
651 point->fy = (FT_Short)vec->y;
652 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta;
653 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta;
654
655 switch ( FT_CURVE_TAG( *tag ) )
656 {
657 case FT_CURVE_TAG_CONIC:
658 point->flags = AF_FLAG_CONIC;
659 break;
660 case FT_CURVE_TAG_CUBIC:
661 point->flags = AF_FLAG_CUBIC;
662 break;
663 default:
664 point->flags = 0;
665 }
666
667 point->prev = prev;
668 prev->next = point;
669 prev = point;
670
671 if ( point == end )
672 {
673 if ( ++contour_index < outline->n_contours )
674 {
675 first = point + 1;
676 end = points + outline->contours[contour_index];
677 prev = end;
678 }
679 }
680 }
681 }
682
683 /* set-up the contours array */
684 {
685 AF_Point* contour = hints->contours;
686 AF_Point* contour_limit = contour + hints->num_contours;
687 short* end = outline->contours;
688 short idx = 0;
689
690
691 for ( ; contour < contour_limit; contour++, end++ )
692 {
693 contour[0] = points + idx;
694 idx = (short)( end[0] + 1 );
695 }
696 }
697
698 /* compute directions of in & out vectors */
699 {
700 AF_Point first = points;
701 AF_Point prev = NULL;
702 FT_Pos in_x = 0;
703 FT_Pos in_y = 0;
704 AF_Direction in_dir = AF_DIR_NONE;
705
706
707 for ( point = points; point < point_limit; point++ )
708 {
709 AF_Point next;
710 FT_Pos out_x, out_y;
711
712
713 if ( point == first )
714 {
715 prev = first->prev;
716 in_x = first->fx - prev->fx;
717 in_y = first->fy - prev->fy;
718 in_dir = af_direction_compute( in_x, in_y );
719 first = prev + 1;
720 }
721
722 point->in_dir = (FT_Char)in_dir;
723
724 next = point->next;
725 out_x = next->fx - point->fx;
726 out_y = next->fy - point->fy;
727
728 in_dir = af_direction_compute( out_x, out_y );
729 point->out_dir = (FT_Char)in_dir;
730
731 if ( point->flags & ( AF_FLAG_CONIC | AF_FLAG_CUBIC ) )
732 {
733 Is_Weak_Point:
734 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
735 }
736 else if ( point->out_dir == point->in_dir )
737 {
738 if ( point->out_dir != AF_DIR_NONE )
739 goto Is_Weak_Point;
740
741 if ( ft_corner_is_flat( in_x, in_y, out_x, out_y ) )
742 goto Is_Weak_Point;
743 }
744 else if ( point->in_dir == -point->out_dir )
745 goto Is_Weak_Point;
746
747 in_x = out_x;
748 in_y = out_y;
749 prev = point;
750 }
751 }
752 }
753
754 /* compute inflection points -- */
755 /* disabled due to no longer perceived benefits */
756 if ( 0 && get_inflections )
757 af_glyph_hints_compute_inflections( hints );
758
759 Exit:
760 return error;
761 }
762
763
764 FT_LOCAL_DEF( void )
765 af_glyph_hints_save( AF_GlyphHints hints,
766 FT_Outline* outline )
767 {
768 AF_Point point = hints->points;
769 AF_Point limit = point + hints->num_points;
770 FT_Vector* vec = outline->points;
771 char* tag = outline->tags;
772
773
774 for ( ; point < limit; point++, vec++, tag++ )
775 {
776 vec->x = point->x;
777 vec->y = point->y;
778
779 if ( point->flags & AF_FLAG_CONIC )
780 tag[0] = FT_CURVE_TAG_CONIC;
781 else if ( point->flags & AF_FLAG_CUBIC )
782 tag[0] = FT_CURVE_TAG_CUBIC;
783 else
784 tag[0] = FT_CURVE_TAG_ON;
785 }
786 }
787
788
789 /****************************************************************
790 *
791 * EDGE POINT GRID-FITTING
792 *
793 ****************************************************************/
794
795
796 FT_LOCAL_DEF( void )
797 af_glyph_hints_align_edge_points( AF_GlyphHints hints,
798 AF_Dimension dim )
799 {
800 AF_AxisHints axis = & hints->axis[dim];
801 AF_Segment segments = axis->segments;
802 AF_Segment segment_limit = segments + axis->num_segments;
803 AF_Segment seg;
804
805
806 if ( dim == AF_DIMENSION_HORZ )
807 {
808 for ( seg = segments; seg < segment_limit; seg++ )
809 {
810 AF_Edge edge = seg->edge;
811 AF_Point point, first, last;
812
813
814 if ( edge == NULL )
815 continue;
816
817 first = seg->first;
818 last = seg->last;
819 point = first;
820 for (;;)
821 {
822 point->x = edge->pos;
823 point->flags |= AF_FLAG_TOUCH_X;
824
825 if ( point == last )
826 break;
827
828 point = point->next;
829
830 }
831 }
832 }
833 else
834 {
835 for ( seg = segments; seg < segment_limit; seg++ )
836 {
837 AF_Edge edge = seg->edge;
838 AF_Point point, first, last;
839
840
841 if ( edge == NULL )
842 continue;
843
844 first = seg->first;
845 last = seg->last;
846 point = first;
847 for (;;)
848 {
849 point->y = edge->pos;
850 point->flags |= AF_FLAG_TOUCH_Y;
851
852 if ( point == last )
853 break;
854
855 point = point->next;
856 }
857 }
858 }
859 }
860
861
862 /****************************************************************
863 *
864 * STRONG POINT INTERPOLATION
865 *
866 ****************************************************************/
867
868
869 /* hint the strong points -- this is equivalent to the TrueType `IP' */
870 /* hinting instruction */
871
872 FT_LOCAL_DEF( void )
873 af_glyph_hints_align_strong_points( AF_GlyphHints hints,
874 AF_Dimension dim )
875 {
876 AF_Point points = hints->points;
877 AF_Point point_limit = points + hints->num_points;
878 AF_AxisHints axis = &hints->axis[dim];
879 AF_Edge edges = axis->edges;
880 AF_Edge edge_limit = edges + axis->num_edges;
881 AF_Flags touch_flag;
882
883
884 if ( dim == AF_DIMENSION_HORZ )
885 touch_flag = AF_FLAG_TOUCH_X;
886 else
887 touch_flag = AF_FLAG_TOUCH_Y;
888
889 if ( edges < edge_limit )
890 {
891 AF_Point point;
892 AF_Edge edge;
893
894
895 for ( point = points; point < point_limit; point++ )
896 {
897 FT_Pos u, ou, fu; /* point position */
898 FT_Pos delta;
899
900
901 if ( point->flags & touch_flag )
902 continue;
903
904 /* if this point is candidate to weak interpolation, we */
905 /* interpolate it after all strong points have been processed */
906
907 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) &&
908 !( point->flags & AF_FLAG_INFLECTION ) )
909 continue;
910
911 if ( dim == AF_DIMENSION_VERT )
912 {
913 u = point->fy;
914 ou = point->oy;
915 }
916 else
917 {
918 u = point->fx;
919 ou = point->ox;
920 }
921
922 fu = u;
923
924 /* is the point before the first edge? */
925 edge = edges;
926 delta = edge->fpos - u;
927 if ( delta >= 0 )
928 {
929 u = edge->pos - ( edge->opos - ou );
930 goto Store_Point;
931 }
932
933 /* is the point after the last edge? */
934 edge = edge_limit - 1;
935 delta = u - edge->fpos;
936 if ( delta >= 0 )
937 {
938 u = edge->pos + ( ou - edge->opos );
939 goto Store_Point;
940 }
941
942 {
943 FT_UInt min, max, mid;
944 FT_Pos fpos;
945
946
947 /* find enclosing edges */
948 min = 0;
949 max = edge_limit - edges;
950
951 #if 1
952 /* for small edge counts, a linear search is better */
953 if ( max <= 8 )
954 {
955 FT_UInt nn;
956
957 for ( nn = 0; nn < max; nn++ )
958 if ( edges[nn].fpos >= u )
959 break;
960
961 if ( edges[nn].fpos == u )
962 {
963 u = edges[nn].pos;
964 goto Store_Point;
965 }
966 min = nn;
967 }
968 else
969 #endif
970 while ( min < max )
971 {
972 mid = ( max + min ) >> 1;
973 edge = edges + mid;
974 fpos = edge->fpos;
975
976 if ( u < fpos )
977 max = mid;
978 else if ( u > fpos )
979 min = mid + 1;
980 else
981 {
982 /* we are on the edge */
983 u = edge->pos;
984 goto Store_Point;
985 }
986 }
987
988 {
989 AF_Edge before = edges + min - 1;
990 AF_Edge after = edges + min + 0;
991
992
993 /* assert( before && after && before != after ) */
994 if ( before->scale == 0 )
995 before->scale = FT_DivFix( after->pos - before->pos,
996 after->fpos - before->fpos );
997
998 u = before->pos + FT_MulFix( fu - before->fpos,
999 before->scale );
1000 }
1001 }
1002
1003 Store_Point:
1004 /* save the point position */
1005 if ( dim == AF_DIMENSION_HORZ )
1006 point->x = u;
1007 else
1008 point->y = u;
1009
1010 point->flags |= touch_flag;
1011 }
1012 }
1013 }
1014
1015
1016 /****************************************************************
1017 *
1018 * WEAK POINT INTERPOLATION
1019 *
1020 ****************************************************************/
1021
1022
1023 static void
1024 af_iup_shift( AF_Point p1,
1025 AF_Point p2,
1026 AF_Point ref )
1027 {
1028 AF_Point p;
1029 FT_Pos delta = ref->u - ref->v;
1030
1031 if ( delta == 0 )
1032 return;
1033
1034 for ( p = p1; p < ref; p++ )
1035 p->u = p->v + delta;
1036
1037 for ( p = ref + 1; p <= p2; p++ )
1038 p->u = p->v + delta;
1039 }
1040
1041
1042 static void
1043 af_iup_interp( AF_Point p1,
1044 AF_Point p2,
1045 AF_Point ref1,
1046 AF_Point ref2 )
1047 {
1048 AF_Point p;
1049 FT_Pos u;
1050 FT_Pos v1 = ref1->v;
1051 FT_Pos v2 = ref2->v;
1052 FT_Pos d1 = ref1->u - v1;
1053 FT_Pos d2 = ref2->u - v2;
1054
1055
1056 if ( p1 > p2 )
1057 return;
1058
1059 if ( v1 == v2 )
1060 {
1061 for ( p = p1; p <= p2; p++ )
1062 {
1063 u = p->v;
1064
1065 if ( u <= v1 )
1066 u += d1;
1067 else
1068 u += d2;
1069
1070 p->u = u;
1071 }
1072 return;
1073 }
1074
1075 if ( v1 < v2 )
1076 {
1077 for ( p = p1; p <= p2; p++ )
1078 {
1079 u = p->v;
1080
1081 if ( u <= v1 )
1082 u += d1;
1083 else if ( u >= v2 )
1084 u += d2;
1085 else
1086 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 );
1087
1088 p->u = u;
1089 }
1090 }
1091 else
1092 {
1093 for ( p = p1; p <= p2; p++ )
1094 {
1095 u = p->v;
1096
1097 if ( u <= v2 )
1098 u += d2;
1099 else if ( u >= v1 )
1100 u += d1;
1101 else
1102 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 );
1103
1104 p->u = u;
1105 }
1106 }
1107 }
1108
1109
1110 FT_LOCAL_DEF( void )
1111 af_glyph_hints_align_weak_points( AF_GlyphHints hints,
1112 AF_Dimension dim )
1113 {
1114 AF_Point points = hints->points;
1115 AF_Point point_limit = points + hints->num_points;
1116 AF_Point* contour = hints->contours;
1117 AF_Point* contour_limit = contour + hints->num_contours;
1118 AF_Flags touch_flag;
1119 AF_Point point;
1120 AF_Point end_point;
1121 AF_Point first_point;
1122
1123
1124 /* PASS 1: Move segment points to edge positions */
1125
1126 if ( dim == AF_DIMENSION_HORZ )
1127 {
1128 touch_flag = AF_FLAG_TOUCH_X;
1129
1130 for ( point = points; point < point_limit; point++ )
1131 {
1132 point->u = point->x;
1133 point->v = point->ox;
1134 }
1135 }
1136 else
1137 {
1138 touch_flag = AF_FLAG_TOUCH_Y;
1139
1140 for ( point = points; point < point_limit; point++ )
1141 {
1142 point->u = point->y;
1143 point->v = point->oy;
1144 }
1145 }
1146
1147 point = points;
1148
1149 for ( ; contour < contour_limit; contour++ )
1150 {
1151 AF_Point first_touched, last_touched;
1152
1153
1154 point = *contour;
1155 end_point = point->prev;
1156 first_point = point;
1157
1158 /* find first touched point */
1159 for (;;)
1160 {
1161 if ( point > end_point ) /* no touched point in contour */
1162 goto NextContour;
1163
1164 if ( point->flags & touch_flag )
1165 break;
1166
1167 point++;
1168 }
1169
1170 first_touched = point;
1171 last_touched = point;
1172
1173 for (;;)
1174 {
1175 FT_ASSERT( point <= end_point &&
1176 ( point->flags & touch_flag ) != 0 );
1177
1178 /* skip any touched neighbhours */
1179 while ( point < end_point && ( point[1].flags & touch_flag ) != 0 )
1180 point++;
1181
1182 last_touched = point;
1183
1184 /* find the next touched point, if any */
1185 point ++;
1186 for (;;)
1187 {
1188 if ( point > end_point )
1189 goto EndContour;
1190
1191 if ( ( point->flags & touch_flag ) != 0 )
1192 break;
1193
1194 point++;
1195 }
1196
1197 /* interpolate between last_touched and point */
1198 af_iup_interp( last_touched + 1, point - 1,
1199 last_touched, point );
1200 }
1201
1202 EndContour:
1203 /* special case: only one point was touched */
1204 if ( last_touched == first_touched )
1205 {
1206 af_iup_shift( first_point, end_point, first_touched );
1207 }
1208 else /* interpolate the last part */
1209 {
1210 if ( last_touched < end_point )
1211 af_iup_interp( last_touched + 1, end_point,
1212 last_touched, first_touched );
1213
1214 if ( first_touched > points )
1215 af_iup_interp( first_point, first_touched - 1,
1216 last_touched, first_touched );
1217 }
1218
1219 NextContour:
1220 ;
1221 }
1222
1223 /* now save the interpolated values back to x/y */
1224 if ( dim == AF_DIMENSION_HORZ )
1225 {
1226 for ( point = points; point < point_limit; point++ )
1227 point->x = point->u;
1228 }
1229 else
1230 {
1231 for ( point = points; point < point_limit; point++ )
1232 point->y = point->u;
1233 }
1234 }
1235
1236
1237 #ifdef AF_USE_WARPER
1238
1239 FT_LOCAL_DEF( void )
1240 af_glyph_hints_scale_dim( AF_GlyphHints hints,
1241 AF_Dimension dim,
1242 FT_Fixed scale,
1243 FT_Pos delta )
1244 {
1245 AF_Point points = hints->points;
1246 AF_Point points_limit = points + hints->num_points;
1247 AF_Point point;
1248
1249
1250 if ( dim == AF_DIMENSION_HORZ )
1251 {
1252 for ( point = points; point < points_limit; point++ )
1253 point->x = FT_MulFix( point->fx, scale ) + delta;
1254 }
1255 else
1256 {
1257 for ( point = points; point < points_limit; point++ )
1258 point->y = FT_MulFix( point->fy, scale ) + delta;
1259 }
1260 }
1261
1262 #endif /* AF_USE_WARPER */
1263
1264 /* END */