Sync with trunk (r48042), except win32k/ntuser/cursoricon.c
[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, 2009 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)( 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)( 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 FT_CONFIG_STANDARD_LIBRARY_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 ft_memcpy( temp + pos, "round", 5 );
207 pos += 5;
208 }
209 if ( flags & AF_EDGE_SERIF )
210 {
211 if ( pos > 0 )
212 temp[pos++] = ' ';
213 ft_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 FT_UNUSED( first );
649 for ( point = points; point < point_limit; point++, vec++, tag++ )
650 {
651 point->fx = (FT_Short)vec->x;
652 point->fy = (FT_Short)vec->y;
653 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta;
654 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta;
655
656 switch ( FT_CURVE_TAG( *tag ) )
657 {
658 case FT_CURVE_TAG_CONIC:
659 point->flags = AF_FLAG_CONIC;
660 break;
661 case FT_CURVE_TAG_CUBIC:
662 point->flags = AF_FLAG_CUBIC;
663 break;
664 default:
665 point->flags = 0;
666 }
667
668 point->prev = prev;
669 prev->next = point;
670 prev = point;
671
672 if ( point == end )
673 {
674 if ( ++contour_index < outline->n_contours )
675 {
676 first = point + 1;
677 end = points + outline->contours[contour_index];
678 prev = end;
679 }
680 }
681 }
682 }
683
684 /* set-up the contours array */
685 {
686 AF_Point* contour = hints->contours;
687 AF_Point* contour_limit = contour + hints->num_contours;
688 short* end = outline->contours;
689 short idx = 0;
690
691
692 for ( ; contour < contour_limit; contour++, end++ )
693 {
694 contour[0] = points + idx;
695 idx = (short)( end[0] + 1 );
696 }
697 }
698
699 /* compute directions of in & out vectors */
700 {
701 AF_Point first = points;
702 AF_Point prev = NULL;
703 FT_Pos in_x = 0;
704 FT_Pos in_y = 0;
705 AF_Direction in_dir = AF_DIR_NONE;
706
707
708 for ( point = points; point < point_limit; point++ )
709 {
710 AF_Point next;
711 FT_Pos out_x, out_y;
712
713
714 if ( point == first )
715 {
716 prev = first->prev;
717 in_x = first->fx - prev->fx;
718 in_y = first->fy - prev->fy;
719 in_dir = af_direction_compute( in_x, in_y );
720 first = prev + 1;
721 }
722
723 point->in_dir = (FT_Char)in_dir;
724
725 next = point->next;
726 out_x = next->fx - point->fx;
727 out_y = next->fy - point->fy;
728
729 in_dir = af_direction_compute( out_x, out_y );
730 point->out_dir = (FT_Char)in_dir;
731
732 if ( point->flags & ( AF_FLAG_CONIC | AF_FLAG_CUBIC ) )
733 {
734 Is_Weak_Point:
735 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
736 }
737 else if ( point->out_dir == point->in_dir )
738 {
739 if ( point->out_dir != AF_DIR_NONE )
740 goto Is_Weak_Point;
741
742 if ( ft_corner_is_flat( in_x, in_y, out_x, out_y ) )
743 goto Is_Weak_Point;
744 }
745 else if ( point->in_dir == -point->out_dir )
746 goto Is_Weak_Point;
747
748 in_x = out_x;
749 in_y = out_y;
750 prev = point;
751 }
752 }
753 }
754
755 /* compute inflection points -- */
756 /* disabled due to no longer perceived benefits */
757 if ( 0 && get_inflections )
758 af_glyph_hints_compute_inflections( hints );
759
760 Exit:
761 return error;
762 }
763
764
765 FT_LOCAL_DEF( void )
766 af_glyph_hints_save( AF_GlyphHints hints,
767 FT_Outline* outline )
768 {
769 AF_Point point = hints->points;
770 AF_Point limit = point + hints->num_points;
771 FT_Vector* vec = outline->points;
772 char* tag = outline->tags;
773
774
775 for ( ; point < limit; point++, vec++, tag++ )
776 {
777 vec->x = point->x;
778 vec->y = point->y;
779
780 if ( point->flags & AF_FLAG_CONIC )
781 tag[0] = FT_CURVE_TAG_CONIC;
782 else if ( point->flags & AF_FLAG_CUBIC )
783 tag[0] = FT_CURVE_TAG_CUBIC;
784 else
785 tag[0] = FT_CURVE_TAG_ON;
786 }
787 }
788
789
790 /****************************************************************
791 *
792 * EDGE POINT GRID-FITTING
793 *
794 ****************************************************************/
795
796
797 FT_LOCAL_DEF( void )
798 af_glyph_hints_align_edge_points( AF_GlyphHints hints,
799 AF_Dimension dim )
800 {
801 AF_AxisHints axis = & hints->axis[dim];
802 AF_Segment segments = axis->segments;
803 AF_Segment segment_limit = segments + axis->num_segments;
804 AF_Segment seg;
805
806
807 if ( dim == AF_DIMENSION_HORZ )
808 {
809 for ( seg = segments; seg < segment_limit; seg++ )
810 {
811 AF_Edge edge = seg->edge;
812 AF_Point point, first, last;
813
814
815 if ( edge == NULL )
816 continue;
817
818 first = seg->first;
819 last = seg->last;
820 point = first;
821 for (;;)
822 {
823 point->x = edge->pos;
824 point->flags |= AF_FLAG_TOUCH_X;
825
826 if ( point == last )
827 break;
828
829 point = point->next;
830
831 }
832 }
833 }
834 else
835 {
836 for ( seg = segments; seg < segment_limit; seg++ )
837 {
838 AF_Edge edge = seg->edge;
839 AF_Point point, first, last;
840
841
842 if ( edge == NULL )
843 continue;
844
845 first = seg->first;
846 last = seg->last;
847 point = first;
848 for (;;)
849 {
850 point->y = edge->pos;
851 point->flags |= AF_FLAG_TOUCH_Y;
852
853 if ( point == last )
854 break;
855
856 point = point->next;
857 }
858 }
859 }
860 }
861
862
863 /****************************************************************
864 *
865 * STRONG POINT INTERPOLATION
866 *
867 ****************************************************************/
868
869
870 /* hint the strong points -- this is equivalent to the TrueType `IP' */
871 /* hinting instruction */
872
873 FT_LOCAL_DEF( void )
874 af_glyph_hints_align_strong_points( AF_GlyphHints hints,
875 AF_Dimension dim )
876 {
877 AF_Point points = hints->points;
878 AF_Point point_limit = points + hints->num_points;
879 AF_AxisHints axis = &hints->axis[dim];
880 AF_Edge edges = axis->edges;
881 AF_Edge edge_limit = edges + axis->num_edges;
882 AF_Flags touch_flag;
883
884
885 if ( dim == AF_DIMENSION_HORZ )
886 touch_flag = AF_FLAG_TOUCH_X;
887 else
888 touch_flag = AF_FLAG_TOUCH_Y;
889
890 if ( edges < edge_limit )
891 {
892 AF_Point point;
893 AF_Edge edge;
894
895
896 for ( point = points; point < point_limit; point++ )
897 {
898 FT_Pos u, ou, fu; /* point position */
899 FT_Pos delta;
900
901
902 if ( point->flags & touch_flag )
903 continue;
904
905 /* if this point is candidate to weak interpolation, we */
906 /* interpolate it after all strong points have been processed */
907
908 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) &&
909 !( point->flags & AF_FLAG_INFLECTION ) )
910 continue;
911
912 if ( dim == AF_DIMENSION_VERT )
913 {
914 u = point->fy;
915 ou = point->oy;
916 }
917 else
918 {
919 u = point->fx;
920 ou = point->ox;
921 }
922
923 fu = u;
924
925 /* is the point before the first edge? */
926 edge = edges;
927 delta = edge->fpos - u;
928 if ( delta >= 0 )
929 {
930 u = edge->pos - ( edge->opos - ou );
931 goto Store_Point;
932 }
933
934 /* is the point after the last edge? */
935 edge = edge_limit - 1;
936 delta = u - edge->fpos;
937 if ( delta >= 0 )
938 {
939 u = edge->pos + ( ou - edge->opos );
940 goto Store_Point;
941 }
942
943 {
944 FT_PtrDist min, max, mid;
945 FT_Pos fpos;
946
947
948 /* find enclosing edges */
949 min = 0;
950 max = edge_limit - edges;
951
952 #if 1
953 /* for small edge counts, a linear search is better */
954 if ( max <= 8 )
955 {
956 FT_PtrDist nn;
957
958 for ( nn = 0; nn < max; nn++ )
959 if ( edges[nn].fpos >= u )
960 break;
961
962 if ( edges[nn].fpos == u )
963 {
964 u = edges[nn].pos;
965 goto Store_Point;
966 }
967 min = nn;
968 }
969 else
970 #endif
971 while ( min < max )
972 {
973 mid = ( max + min ) >> 1;
974 edge = edges + mid;
975 fpos = edge->fpos;
976
977 if ( u < fpos )
978 max = mid;
979 else if ( u > fpos )
980 min = mid + 1;
981 else
982 {
983 /* we are on the edge */
984 u = edge->pos;
985 goto Store_Point;
986 }
987 }
988
989 {
990 AF_Edge before = edges + min - 1;
991 AF_Edge after = edges + min + 0;
992
993
994 /* assert( before && after && before != after ) */
995 if ( before->scale == 0 )
996 before->scale = FT_DivFix( after->pos - before->pos,
997 after->fpos - before->fpos );
998
999 u = before->pos + FT_MulFix( fu - before->fpos,
1000 before->scale );
1001 }
1002 }
1003
1004 Store_Point:
1005 /* save the point position */
1006 if ( dim == AF_DIMENSION_HORZ )
1007 point->x = u;
1008 else
1009 point->y = u;
1010
1011 point->flags |= touch_flag;
1012 }
1013 }
1014 }
1015
1016
1017 /****************************************************************
1018 *
1019 * WEAK POINT INTERPOLATION
1020 *
1021 ****************************************************************/
1022
1023
1024 static void
1025 af_iup_shift( AF_Point p1,
1026 AF_Point p2,
1027 AF_Point ref )
1028 {
1029 AF_Point p;
1030 FT_Pos delta = ref->u - ref->v;
1031
1032 if ( delta == 0 )
1033 return;
1034
1035 for ( p = p1; p < ref; p++ )
1036 p->u = p->v + delta;
1037
1038 for ( p = ref + 1; p <= p2; p++ )
1039 p->u = p->v + delta;
1040 }
1041
1042
1043 static void
1044 af_iup_interp( AF_Point p1,
1045 AF_Point p2,
1046 AF_Point ref1,
1047 AF_Point ref2 )
1048 {
1049 AF_Point p;
1050 FT_Pos u;
1051 FT_Pos v1 = ref1->v;
1052 FT_Pos v2 = ref2->v;
1053 FT_Pos d1 = ref1->u - v1;
1054 FT_Pos d2 = ref2->u - v2;
1055
1056
1057 if ( p1 > p2 )
1058 return;
1059
1060 if ( v1 == v2 )
1061 {
1062 for ( p = p1; p <= p2; p++ )
1063 {
1064 u = p->v;
1065
1066 if ( u <= v1 )
1067 u += d1;
1068 else
1069 u += d2;
1070
1071 p->u = u;
1072 }
1073 return;
1074 }
1075
1076 if ( v1 < v2 )
1077 {
1078 for ( p = p1; p <= p2; p++ )
1079 {
1080 u = p->v;
1081
1082 if ( u <= v1 )
1083 u += d1;
1084 else if ( u >= v2 )
1085 u += d2;
1086 else
1087 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 );
1088
1089 p->u = u;
1090 }
1091 }
1092 else
1093 {
1094 for ( p = p1; p <= p2; p++ )
1095 {
1096 u = p->v;
1097
1098 if ( u <= v2 )
1099 u += d2;
1100 else if ( u >= v1 )
1101 u += d1;
1102 else
1103 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 );
1104
1105 p->u = u;
1106 }
1107 }
1108 }
1109
1110
1111 FT_LOCAL_DEF( void )
1112 af_glyph_hints_align_weak_points( AF_GlyphHints hints,
1113 AF_Dimension dim )
1114 {
1115 AF_Point points = hints->points;
1116 AF_Point point_limit = points + hints->num_points;
1117 AF_Point* contour = hints->contours;
1118 AF_Point* contour_limit = contour + hints->num_contours;
1119 AF_Flags touch_flag;
1120 AF_Point point;
1121 AF_Point end_point;
1122 AF_Point first_point;
1123
1124
1125 /* PASS 1: Move segment points to edge positions */
1126
1127 if ( dim == AF_DIMENSION_HORZ )
1128 {
1129 touch_flag = AF_FLAG_TOUCH_X;
1130
1131 for ( point = points; point < point_limit; point++ )
1132 {
1133 point->u = point->x;
1134 point->v = point->ox;
1135 }
1136 }
1137 else
1138 {
1139 touch_flag = AF_FLAG_TOUCH_Y;
1140
1141 for ( point = points; point < point_limit; point++ )
1142 {
1143 point->u = point->y;
1144 point->v = point->oy;
1145 }
1146 }
1147
1148 point = points;
1149
1150 for ( ; contour < contour_limit; contour++ )
1151 {
1152 AF_Point first_touched, last_touched;
1153
1154
1155 point = *contour;
1156 end_point = point->prev;
1157 first_point = point;
1158
1159 /* find first touched point */
1160 for (;;)
1161 {
1162 if ( point > end_point ) /* no touched point in contour */
1163 goto NextContour;
1164
1165 if ( point->flags & touch_flag )
1166 break;
1167
1168 point++;
1169 }
1170
1171 first_touched = point;
1172 last_touched = point;
1173
1174 for (;;)
1175 {
1176 FT_ASSERT( point <= end_point &&
1177 ( point->flags & touch_flag ) != 0 );
1178
1179 /* skip any touched neighbhours */
1180 while ( point < end_point && ( point[1].flags & touch_flag ) != 0 )
1181 point++;
1182
1183 last_touched = point;
1184
1185 /* find the next touched point, if any */
1186 point ++;
1187 for (;;)
1188 {
1189 if ( point > end_point )
1190 goto EndContour;
1191
1192 if ( ( point->flags & touch_flag ) != 0 )
1193 break;
1194
1195 point++;
1196 }
1197
1198 /* interpolate between last_touched and point */
1199 af_iup_interp( last_touched + 1, point - 1,
1200 last_touched, point );
1201 }
1202
1203 EndContour:
1204 /* special case: only one point was touched */
1205 if ( last_touched == first_touched )
1206 {
1207 af_iup_shift( first_point, end_point, first_touched );
1208 }
1209 else /* interpolate the last part */
1210 {
1211 if ( last_touched < end_point )
1212 af_iup_interp( last_touched + 1, end_point,
1213 last_touched, first_touched );
1214
1215 if ( first_touched > points )
1216 af_iup_interp( first_point, first_touched - 1,
1217 last_touched, first_touched );
1218 }
1219
1220 NextContour:
1221 ;
1222 }
1223
1224 /* now save the interpolated values back to x/y */
1225 if ( dim == AF_DIMENSION_HORZ )
1226 {
1227 for ( point = points; point < point_limit; point++ )
1228 point->x = point->u;
1229 }
1230 else
1231 {
1232 for ( point = points; point < point_limit; point++ )
1233 point->y = point->u;
1234 }
1235 }
1236
1237
1238 #ifdef AF_USE_WARPER
1239
1240 FT_LOCAL_DEF( void )
1241 af_glyph_hints_scale_dim( AF_GlyphHints hints,
1242 AF_Dimension dim,
1243 FT_Fixed scale,
1244 FT_Pos delta )
1245 {
1246 AF_Point points = hints->points;
1247 AF_Point points_limit = points + hints->num_points;
1248 AF_Point point;
1249
1250
1251 if ( dim == AF_DIMENSION_HORZ )
1252 {
1253 for ( point = points; point < points_limit; point++ )
1254 point->x = FT_MulFix( point->fx, scale ) + delta;
1255 }
1256 else
1257 {
1258 for ( point = points; point < points_limit; point++ )
1259 point->y = FT_MulFix( point->fy, scale ) + delta;
1260 }
1261 }
1262
1263 #endif /* AF_USE_WARPER */
1264
1265 /* END */