projects / reactos.git / blob
? search:


0f7f6e5c419d3c3b123fdff894575efcda06ab81
[reactos.git] / reactos / sdk / lib / 3rdparty / freetype / src / autofit / afhints.c
1 /***************************************************************************/
2 /* */
3 /* afhints.c */
4 /* */
5 /* Auto-fitter hinting routines (body). */
6 /* */
7 /* Copyright 2003-2016 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 #include FT_INTERNAL_DEBUG_H
23
24
25 /*************************************************************************/
26 /* */
27 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
28 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
29 /* messages during execution. */
30 /* */
31 #undef FT_COMPONENT
32 #define FT_COMPONENT trace_afhints
33
34
35 /* Get new segment for given axis. */
36
37 FT_LOCAL_DEF( FT_Error )
38 af_axis_hints_new_segment( AF_AxisHints axis,
39 FT_Memory memory,
40 AF_Segment *asegment )
41 {
42 FT_Error error = FT_Err_Ok;
43 AF_Segment segment = NULL;
44
45
46 if ( axis->num_segments < AF_SEGMENTS_EMBEDDED )
47 {
48 if ( axis->segments == NULL )
49 {
50 axis->segments = axis->embedded.segments;
51 axis->max_segments = AF_SEGMENTS_EMBEDDED;
52 }
53 }
54 else if ( axis->num_segments >= axis->max_segments )
55 {
56 FT_Int old_max = axis->max_segments;
57 FT_Int new_max = old_max;
58 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *segment ) );
59
60
61 if ( old_max >= big_max )
62 {
63 error = FT_THROW( Out_Of_Memory );
64 goto Exit;
65 }
66
67 new_max += ( new_max >> 2 ) + 4;
68 if ( new_max < old_max || new_max > big_max )
69 new_max = big_max;
70
71 if ( axis->segments == axis->embedded.segments )
72 {
73 if ( FT_NEW_ARRAY( axis->segments, new_max ) )
74 goto Exit;
75 ft_memcpy( axis->segments, axis->embedded.segments,
76 sizeof ( axis->embedded.segments ) );
77 }
78 else
79 {
80 if ( FT_RENEW_ARRAY( axis->segments, old_max, new_max ) )
81 goto Exit;
82 }
83
84 axis->max_segments = new_max;
85 }
86
87 segment = axis->segments + axis->num_segments++;
88
89 Exit:
90 *asegment = segment;
91 return error;
92 }
93
94
95 /* Get new edge for given axis, direction, and position, */
96 /* without initializing the edge itself. */
97
98 FT_LOCAL( FT_Error )
99 af_axis_hints_new_edge( AF_AxisHints axis,
100 FT_Int fpos,
101 AF_Direction dir,
102 FT_Bool top_to_bottom_hinting,
103 FT_Memory memory,
104 AF_Edge *anedge )
105 {
106 FT_Error error = FT_Err_Ok;
107 AF_Edge edge = NULL;
108 AF_Edge edges;
109
110
111 if ( axis->num_edges < AF_EDGES_EMBEDDED )
112 {
113 if ( axis->edges == NULL )
114 {
115 axis->edges = axis->embedded.edges;
116 axis->max_edges = AF_EDGES_EMBEDDED;
117 }
118 }
119 else if ( axis->num_edges >= axis->max_edges )
120 {
121 FT_Int old_max = axis->max_edges;
122 FT_Int new_max = old_max;
123 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *edge ) );
124
125
126 if ( old_max >= big_max )
127 {
128 error = FT_THROW( Out_Of_Memory );
129 goto Exit;
130 }
131
132 new_max += ( new_max >> 2 ) + 4;
133 if ( new_max < old_max || new_max > big_max )
134 new_max = big_max;
135
136 if ( axis->edges == axis->embedded.edges )
137 {
138 if ( FT_NEW_ARRAY( axis->edges, new_max ) )
139 goto Exit;
140 ft_memcpy( axis->edges, axis->embedded.edges,
141 sizeof ( axis->embedded.edges ) );
142 }
143 else
144 {
145 if ( FT_RENEW_ARRAY( axis->edges, old_max, new_max ) )
146 goto Exit;
147 }
148
149 axis->max_edges = new_max;
150 }
151
152 edges = axis->edges;
153 edge = edges + axis->num_edges;
154
155 while ( edge > edges )
156 {
157 if ( top_to_bottom_hinting ? ( edge[-1].fpos > fpos )
158 : ( edge[-1].fpos < fpos ) )
159 break;
160
161 /* we want the edge with same position and minor direction */
162 /* to appear before those in the major one in the list */
163 if ( edge[-1].fpos == fpos && dir == axis->major_dir )
164 break;
165
166 edge[0] = edge[-1];
167 edge--;
168 }
169
170 axis->num_edges++;
171
172 Exit:
173 *anedge = edge;
174 return error;
175 }
176
177
178 #ifdef FT_DEBUG_AUTOFIT
179
180 #include FT_CONFIG_STANDARD_LIBRARY_H
181
182 /* The dump functions are used in the `ftgrid' demo program, too. */
183 #define AF_DUMP( varformat ) \
184 do \
185 { \
186 if ( to_stdout ) \
187 printf varformat; \
188 else \
189 FT_TRACE7( varformat ); \
190 } while ( 0 )
191
192
193 static const char*
194 af_dir_str( AF_Direction dir )
195 {
196 const char* result;
197
198
199 switch ( dir )
200 {
201 case AF_DIR_UP:
202 result = "up";
203 break;
204 case AF_DIR_DOWN:
205 result = "down";
206 break;
207 case AF_DIR_LEFT:
208 result = "left";
209 break;
210 case AF_DIR_RIGHT:
211 result = "right";
212 break;
213 default:
214 result = "none";
215 }
216
217 return result;
218 }
219
220
221 #define AF_INDEX_NUM( ptr, base ) (int)( (ptr) ? ( (ptr) - (base) ) : -1 )
222
223
224 static char*
225 af_print_idx( char* p,
226 int idx )
227 {
228 if ( idx == -1 )
229 {
230 p[0] = '-';
231 p[1] = '-';
232 p[2] = '\0';
233 }
234 else
235 ft_sprintf( p, "%d", idx );
236
237 return p;
238 }
239
240
241 static int
242 af_get_segment_index( AF_GlyphHints hints,
243 int point_idx,
244 int dimension )
245 {
246 AF_AxisHints axis = &hints->axis[dimension];
247 AF_Point point = hints->points + point_idx;
248 AF_Segment segments = axis->segments;
249 AF_Segment limit = segments + axis->num_segments;
250 AF_Segment segment;
251
252
253 for ( segment = segments; segment < limit; segment++ )
254 {
255 if ( segment->first <= segment->last )
256 {
257 if ( point >= segment->first && point <= segment->last )
258 break;
259 }
260 else
261 {
262 AF_Point p = segment->first;
263
264
265 for (;;)
266 {
267 if ( point == p )
268 goto Exit;
269
270 if ( p == segment->last )
271 break;
272
273 p = p->next;
274 }
275 }
276 }
277
278 Exit:
279 if ( segment == limit )
280 return -1;
281
282 return (int)( segment - segments );
283 }
284
285
286 static int
287 af_get_edge_index( AF_GlyphHints hints,
288 int segment_idx,
289 int dimension )
290 {
291 AF_AxisHints axis = &hints->axis[dimension];
292 AF_Edge edges = axis->edges;
293 AF_Segment segment = axis->segments + segment_idx;
294
295
296 return segment_idx == -1 ? -1 : AF_INDEX_NUM( segment->edge, edges );
297 }
298
299
300 #ifdef __cplusplus
301 extern "C" {
302 #endif
303 void
304 af_glyph_hints_dump_points( AF_GlyphHints hints,
305 FT_Bool to_stdout )
306 {
307 AF_Point points = hints->points;
308 AF_Point limit = points + hints->num_points;
309 AF_Point* contour = hints->contours;
310 AF_Point* climit = contour + hints->num_contours;
311 AF_Point point;
312
313
314 AF_DUMP(( "Table of points:\n" ));
315
316 if ( hints->num_points )
317 AF_DUMP(( " index hedge hseg vedge vseg flags "
318 " xorg yorg xscale yscale xfit yfit" ));
319 else
320 AF_DUMP(( " (none)\n" ));
321
322 for ( point = points; point < limit; point++ )
323 {
324 int point_idx = AF_INDEX_NUM( point, points );
325 int segment_idx_0 = af_get_segment_index( hints, point_idx, 0 );
326 int segment_idx_1 = af_get_segment_index( hints, point_idx, 1 );
327
328 char buf1[16], buf2[16], buf3[16], buf4[16];
329
330
331 /* insert extra newline at the beginning of a contour */
332 if ( contour < climit && *contour == point )
333 {
334 AF_DUMP(( "\n" ));
335 contour++;
336 }
337
338 AF_DUMP(( " %5d %5s %5s %5s %5s %s"
339 " %5d %5d %7.2f %7.2f %7.2f %7.2f\n",
340 point_idx,
341 af_print_idx( buf1,
342 af_get_edge_index( hints, segment_idx_1, 1 ) ),
343 af_print_idx( buf2, segment_idx_1 ),
344 af_print_idx( buf3,
345 af_get_edge_index( hints, segment_idx_0, 0 ) ),
346 af_print_idx( buf4, segment_idx_0 ),
347 ( point->flags & AF_FLAG_NEAR )
348 ? " near "
349 : ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
350 ? " weak "
351 : "strong",
352
353 point->fx,
354 point->fy,
355 point->ox / 64.0,
356 point->oy / 64.0,
357 point->x / 64.0,
358 point->y / 64.0 ));
359 }
360 AF_DUMP(( "\n" ));
361 }
362 #ifdef __cplusplus
363 }
364 #endif
365
366
367 static const char*
368 af_edge_flags_to_string( FT_UInt flags )
369 {
370 static char temp[32];
371 int pos = 0;
372
373
374 if ( flags & AF_EDGE_ROUND )
375 {
376 ft_memcpy( temp + pos, "round", 5 );
377 pos += 5;
378 }
379 if ( flags & AF_EDGE_SERIF )
380 {
381 if ( pos > 0 )
382 temp[pos++] = ' ';
383 ft_memcpy( temp + pos, "serif", 5 );
384 pos += 5;
385 }
386 if ( pos == 0 )
387 return "normal";
388
389 temp[pos] = '\0';
390
391 return temp;
392 }
393
394
395 /* Dump the array of linked segments. */
396
397 #ifdef __cplusplus
398 extern "C" {
399 #endif
400 void
401 af_glyph_hints_dump_segments( AF_GlyphHints hints,
402 FT_Bool to_stdout )
403 {
404 FT_Int dimension;
405
406
407 for ( dimension = 1; dimension >= 0; dimension-- )
408 {
409 AF_AxisHints axis = &hints->axis[dimension];
410 AF_Point points = hints->points;
411 AF_Edge edges = axis->edges;
412 AF_Segment segments = axis->segments;
413 AF_Segment limit = segments + axis->num_segments;
414 AF_Segment seg;
415
416 char buf1[16], buf2[16], buf3[16];
417
418
419 AF_DUMP(( "Table of %s segments:\n",
420 dimension == AF_DIMENSION_HORZ ? "vertical"
421 : "horizontal" ));
422 if ( axis->num_segments )
423 AF_DUMP(( " index pos delta dir from to "
424 " link serif edge"
425 " height extra flags\n" ));
426 else
427 AF_DUMP(( " (none)\n" ));
428
429 for ( seg = segments; seg < limit; seg++ )
430 AF_DUMP(( " %5d %5d %5d %5s %4d %4d"
431 " %4s %5s %4s"
432 " %6d %5d %11s\n",
433 AF_INDEX_NUM( seg, segments ),
434 seg->pos,
435 seg->delta,
436 af_dir_str( (AF_Direction)seg->dir ),
437 AF_INDEX_NUM( seg->first, points ),
438 AF_INDEX_NUM( seg->last, points ),
439
440 af_print_idx( buf1, AF_INDEX_NUM( seg->link, segments ) ),
441 af_print_idx( buf2, AF_INDEX_NUM( seg->serif, segments ) ),
442 af_print_idx( buf3, AF_INDEX_NUM( seg->edge, edges ) ),
443
444 seg->height,
445 seg->height - ( seg->max_coord - seg->min_coord ),
446 af_edge_flags_to_string( seg->flags ) ));
447 AF_DUMP(( "\n" ));
448 }
449 }
450 #ifdef __cplusplus
451 }
452 #endif
453
454
455 /* Fetch number of segments. */
456
457 #ifdef __cplusplus
458 extern "C" {
459 #endif
460 FT_Error
461 af_glyph_hints_get_num_segments( AF_GlyphHints hints,
462 FT_Int dimension,
463 FT_Int* num_segments )
464 {
465 AF_Dimension dim;
466 AF_AxisHints axis;
467
468
469 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT;
470
471 axis = &hints->axis[dim];
472 *num_segments = axis->num_segments;
473
474 return FT_Err_Ok;
475 }
476 #ifdef __cplusplus
477 }
478 #endif
479
480
481 /* Fetch offset of segments into user supplied offset array. */
482
483 #ifdef __cplusplus
484 extern "C" {
485 #endif
486 FT_Error
487 af_glyph_hints_get_segment_offset( AF_GlyphHints hints,
488 FT_Int dimension,
489 FT_Int idx,
490 FT_Pos *offset,
491 FT_Bool *is_blue,
492 FT_Pos *blue_offset )
493 {
494 AF_Dimension dim;
495 AF_AxisHints axis;
496 AF_Segment seg;
497
498
499 if ( !offset )
500 return FT_THROW( Invalid_Argument );
501
502 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT;
503
504 axis = &hints->axis[dim];
505
506 if ( idx < 0 || idx >= axis->num_segments )
507 return FT_THROW( Invalid_Argument );
508
509 seg = &axis->segments[idx];
510 *offset = ( dim == AF_DIMENSION_HORZ ) ? seg->first->ox
511 : seg->first->oy;
512 if ( seg->edge )
513 *is_blue = (FT_Bool)( seg->edge->blue_edge != 0 );
514 else
515 *is_blue = FALSE;
516
517 if ( *is_blue )
518 *blue_offset = seg->edge->blue_edge->cur;
519 else
520 *blue_offset = 0;
521
522 return FT_Err_Ok;
523 }
524 #ifdef __cplusplus
525 }
526 #endif
527
528
529 /* Dump the array of linked edges. */
530
531 #ifdef __cplusplus
532 extern "C" {
533 #endif
534 void
535 af_glyph_hints_dump_edges( AF_GlyphHints hints,
536 FT_Bool to_stdout )
537 {
538 FT_Int dimension;
539
540
541 for ( dimension = 1; dimension >= 0; dimension-- )
542 {
543 AF_AxisHints axis = &hints->axis[dimension];
544 AF_Edge edges = axis->edges;
545 AF_Edge limit = edges + axis->num_edges;
546 AF_Edge edge;
547
548 char buf1[16], buf2[16];
549
550
551 /*
552 * note: AF_DIMENSION_HORZ corresponds to _vertical_ edges
553 * since they have a constant X coordinate.
554 */
555 if ( dimension == AF_DIMENSION_HORZ )
556 AF_DUMP(( "Table of %s edges (1px=%.2fu, 10u=%.2fpx):\n",
557 "vertical",
558 65536.0 * 64.0 / hints->x_scale,
559 10.0 * hints->x_scale / 65536.0 / 64.0 ));
560 else
561 AF_DUMP(( "Table of %s edges (1px=%.2fu, 10u=%.2fpx):\n",
562 "horizontal",
563 65536.0 * 64.0 / hints->y_scale,
564 10.0 * hints->y_scale / 65536.0 / 64.0 ));
565
566 if ( axis->num_edges )
567 AF_DUMP(( " index pos dir link serif"
568 " blue opos pos flags\n" ));
569 else
570 AF_DUMP(( " (none)\n" ));
571
572 for ( edge = edges; edge < limit; edge++ )
573 AF_DUMP(( " %5d %7.2f %5s %4s %5s"
574 " %c %7.2f %7.2f %11s\n",
575 AF_INDEX_NUM( edge, edges ),
576 (int)edge->opos / 64.0,
577 af_dir_str( (AF_Direction)edge->dir ),
578 af_print_idx( buf1, AF_INDEX_NUM( edge->link, edges ) ),
579 af_print_idx( buf2, AF_INDEX_NUM( edge->serif, edges ) ),
580
581 edge->blue_edge ? 'y' : 'n',
582 edge->opos / 64.0,
583 edge->pos / 64.0,
584 af_edge_flags_to_string( edge->flags ) ));
585 AF_DUMP(( "\n" ));
586 }
587 }
588 #ifdef __cplusplus
589 }
590 #endif
591
592 #undef AF_DUMP
593
594 #endif /* !FT_DEBUG_AUTOFIT */
595
596
597 /* Compute the direction value of a given vector. */
598
599 FT_LOCAL_DEF( AF_Direction )
600 af_direction_compute( FT_Pos dx,
601 FT_Pos dy )
602 {
603 FT_Pos ll, ss; /* long and short arm lengths */
604 AF_Direction dir; /* candidate direction */
605
606
607 if ( dy >= dx )
608 {
609 if ( dy >= -dx )
610 {
611 dir = AF_DIR_UP;
612 ll = dy;
613 ss = dx;
614 }
615 else
616 {
617 dir = AF_DIR_LEFT;
618 ll = -dx;
619 ss = dy;
620 }
621 }
622 else /* dy < dx */
623 {
624 if ( dy >= -dx )
625 {
626 dir = AF_DIR_RIGHT;
627 ll = dx;
628 ss = dy;
629 }
630 else
631 {
632 dir = AF_DIR_DOWN;
633 ll = -dy;
634 ss = dx;
635 }
636 }
637
638 /* return no direction if arm lengths do not differ enough */
639 /* (value 14 is heuristic, corresponding to approx. 4.1 degrees) */
640 /* the long arm is never negative */
641 if ( ll <= 14 * FT_ABS( ss ) )
642 dir = AF_DIR_NONE;
643
644 return dir;
645 }
646
647
648 FT_LOCAL_DEF( void )
649 af_glyph_hints_init( AF_GlyphHints hints,
650 FT_Memory memory )
651 {
652 /* no need to initialize the embedded items */
653 FT_MEM_ZERO( hints, sizeof ( *hints ) - sizeof ( hints->embedded ) );
654 hints->memory = memory;
655 }
656
657
658 FT_LOCAL_DEF( void )
659 af_glyph_hints_done( AF_GlyphHints hints )
660 {
661 FT_Memory memory;
662 int dim;
663
664
665 if ( !( hints && hints->memory ) )
666 return;
667
668 memory = hints->memory;
669
670 /*
671 * note that we don't need to free the segment and edge
672 * buffers since they are really within the hints->points array
673 */
674 for ( dim = 0; dim < AF_DIMENSION_MAX; dim++ )
675 {
676 AF_AxisHints axis = &hints->axis[dim];
677
678
679 axis->num_segments = 0;
680 axis->max_segments = 0;
681 if ( axis->segments != axis->embedded.segments )
682 FT_FREE( axis->segments );
683
684 axis->num_edges = 0;
685 axis->max_edges = 0;
686 if ( axis->edges != axis->embedded.edges )
687 FT_FREE( axis->edges );
688 }
689
690 if ( hints->contours != hints->embedded.contours )
691 FT_FREE( hints->contours );
692 hints->max_contours = 0;
693 hints->num_contours = 0;
694
695 if ( hints->points != hints->embedded.points )
696 FT_FREE( hints->points );
697 hints->max_points = 0;
698 hints->num_points = 0;
699
700 hints->memory = NULL;
701 }
702
703
704 /* Reset metrics. */
705
706 FT_LOCAL_DEF( void )
707 af_glyph_hints_rescale( AF_GlyphHints hints,
708 AF_StyleMetrics metrics )
709 {
710 hints->metrics = metrics;
711 hints->scaler_flags = metrics->scaler.flags;
712 }
713
714
715 /* Recompute all AF_Point in AF_GlyphHints from the definitions */
716 /* in a source outline. */
717
718 FT_LOCAL_DEF( FT_Error )
719 af_glyph_hints_reload( AF_GlyphHints hints,
720 FT_Outline* outline )
721 {
722 FT_Error error = FT_Err_Ok;
723 AF_Point points;
724 FT_UInt old_max, new_max;
725 FT_Fixed x_scale = hints->x_scale;
726 FT_Fixed y_scale = hints->y_scale;
727 FT_Pos x_delta = hints->x_delta;
728 FT_Pos y_delta = hints->y_delta;
729 FT_Memory memory = hints->memory;
730
731
732 hints->num_points = 0;
733 hints->num_contours = 0;
734
735 hints->axis[0].num_segments = 0;
736 hints->axis[0].num_edges = 0;
737 hints->axis[1].num_segments = 0;
738 hints->axis[1].num_edges = 0;
739
740 /* first of all, reallocate the contours array if necessary */
741 new_max = (FT_UInt)outline->n_contours;
742 old_max = (FT_UInt)hints->max_contours;
743
744 if ( new_max <= AF_CONTOURS_EMBEDDED )
745 {
746 if ( hints->contours == NULL )
747 {
748 hints->contours = hints->embedded.contours;
749 hints->max_contours = AF_CONTOURS_EMBEDDED;
750 }
751 }
752 else if ( new_max > old_max )
753 {
754 if ( hints->contours == hints->embedded.contours )
755 hints->contours = NULL;
756
757 new_max = ( new_max + 3 ) & ~3U; /* round up to a multiple of 4 */
758
759 if ( FT_RENEW_ARRAY( hints->contours, old_max, new_max ) )
760 goto Exit;
761
762 hints->max_contours = (FT_Int)new_max;
763 }
764
765 /*
766 * then reallocate the points arrays if necessary --
767 * note that we reserve two additional point positions, used to
768 * hint metrics appropriately
769 */
770 new_max = (FT_UInt)( outline->n_points + 2 );
771 old_max = (FT_UInt)hints->max_points;
772
773 if ( new_max <= AF_POINTS_EMBEDDED )
774 {
775 if ( hints->points == NULL )
776 {
777 hints->points = hints->embedded.points;
778 hints->max_points = AF_POINTS_EMBEDDED;
779 }
780 }
781 else if ( new_max > old_max )
782 {
783 if ( hints->points == hints->embedded.points )
784 hints->points = NULL;
785
786 new_max = ( new_max + 2 + 7 ) & ~7U; /* round up to a multiple of 8 */
787
788 if ( FT_RENEW_ARRAY( hints->points, old_max, new_max ) )
789 goto Exit;
790
791 hints->max_points = (FT_Int)new_max;
792 }
793
794 hints->num_points = outline->n_points;
795 hints->num_contours = outline->n_contours;
796
797 /* We can't rely on the value of `FT_Outline.flags' to know the fill */
798 /* direction used for a glyph, given that some fonts are broken (e.g., */
799 /* the Arphic ones). We thus recompute it each time we need to. */
800 /* */
801 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_UP;
802 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_LEFT;
803
804 if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_POSTSCRIPT )
805 {
806 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_DOWN;
807 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_RIGHT;
808 }
809
810 hints->x_scale = x_scale;
811 hints->y_scale = y_scale;
812 hints->x_delta = x_delta;
813 hints->y_delta = y_delta;
814
815 hints->xmin_delta = 0;
816 hints->xmax_delta = 0;
817
818 points = hints->points;
819 if ( hints->num_points == 0 )
820 goto Exit;
821
822 {
823 AF_Point point;
824 AF_Point point_limit = points + hints->num_points;
825
826 /* value 20 in `near_limit' is heuristic */
827 FT_UInt units_per_em = hints->metrics->scaler.face->units_per_EM;
828 FT_Int near_limit = 20 * units_per_em / 2048;
829
830
831 /* compute coordinates & Bezier flags, next and prev */
832 {
833 FT_Vector* vec = outline->points;
834 char* tag = outline->tags;
835 FT_Short endpoint = outline->contours[0];
836 AF_Point end = points + endpoint;
837 AF_Point prev = end;
838 FT_Int contour_index = 0;
839
840
841 for ( point = points; point < point_limit; point++, vec++, tag++ )
842 {
843 FT_Pos out_x, out_y;
844
845
846 point->in_dir = (FT_Char)AF_DIR_NONE;
847 point->out_dir = (FT_Char)AF_DIR_NONE;
848
849 point->fx = (FT_Short)vec->x;
850 point->fy = (FT_Short)vec->y;
851 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta;
852 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta;
853
854 end->fx = (FT_Short)outline->points[endpoint].x;
855 end->fy = (FT_Short)outline->points[endpoint].y;
856
857 switch ( FT_CURVE_TAG( *tag ) )
858 {
859 case FT_CURVE_TAG_CONIC:
860 point->flags = AF_FLAG_CONIC;
861 break;
862 case FT_CURVE_TAG_CUBIC:
863 point->flags = AF_FLAG_CUBIC;
864 break;
865 default:
866 point->flags = AF_FLAG_NONE;
867 }
868
869 out_x = point->fx - prev->fx;
870 out_y = point->fy - prev->fy;
871
872 if ( FT_ABS( out_x ) + FT_ABS( out_y ) < near_limit )
873 prev->flags |= AF_FLAG_NEAR;
874
875 point->prev = prev;
876 prev->next = point;
877 prev = point;
878
879 if ( point == end )
880 {
881 if ( ++contour_index < outline->n_contours )
882 {
883 endpoint = outline->contours[contour_index];
884 end = points + endpoint;
885 prev = end;
886 }
887 }
888 }
889 }
890
891 /* set up the contours array */
892 {
893 AF_Point* contour = hints->contours;
894 AF_Point* contour_limit = contour + hints->num_contours;
895 short* end = outline->contours;
896 short idx = 0;
897
898
899 for ( ; contour < contour_limit; contour++, end++ )
900 {
901 contour[0] = points + idx;
902 idx = (short)( end[0] + 1 );
903 }
904 }
905
906 {
907 /*
908 * Compute directions of `in' and `out' vectors.
909 *
910 * Note that distances between points that are very near to each
911 * other are accumulated. In other words, the auto-hinter either
912 * prepends the small vectors between near points to the first
913 * non-near vector, or the sum of small vector lengths exceeds a
914 * threshold, thus `grouping' the small vectors. All intermediate
915 * points are tagged as weak; the directions are adjusted also to
916 * be equal to the accumulated one.
917 */
918
919 FT_Int near_limit2 = 2 * near_limit - 1;
920
921 AF_Point* contour;
922 AF_Point* contour_limit = hints->contours + hints->num_contours;
923
924
925 for ( contour = hints->contours; contour < contour_limit; contour++ )
926 {
927 AF_Point first = *contour;
928 AF_Point next, prev, curr;
929
930 FT_Pos out_x, out_y;
931
932
933 /* since the first point of a contour could be part of a */
934 /* series of near points, go backwards to find the first */
935 /* non-near point and adjust `first' */
936
937 point = first;
938 prev = first->prev;
939
940 while ( prev != first )
941 {
942 out_x = point->fx - prev->fx;
943 out_y = point->fy - prev->fy;
944
945 /*
946 * We use Taxicab metrics to measure the vector length.
947 *
948 * Note that the accumulated distances so far could have the
949 * opposite direction of the distance measured here. For this
950 * reason we use `near_limit2' for the comparison to get a
951 * non-near point even in the worst case.
952 */
953 if ( FT_ABS( out_x ) + FT_ABS( out_y ) >= near_limit2 )
954 break;
955
956 point = prev;
957 prev = prev->prev;
958 }
959
960 /* adjust first point */
961 first = point;
962
963 /* now loop over all points of the contour to get */
964 /* `in' and `out' vector directions */
965
966 curr = first;
967
968 /*
969 * We abuse the `u' and `v' fields to store index deltas to the
970 * next and previous non-near point, respectively.
971 *
972 * To avoid problems with not having non-near points, we point to
973 * `first' by default as the next non-near point.
974 *
975 */
976 curr->u = (FT_Pos)( first - curr );
977 first->v = -curr->u;
978
979 out_x = 0;
980 out_y = 0;
981
982 next = first;
983 do
984 {
985 AF_Direction out_dir;
986
987
988 point = next;
989 next = point->next;
990
991 out_x += next->fx - point->fx;
992 out_y += next->fy - point->fy;
993
994 if ( FT_ABS( out_x ) + FT_ABS( out_y ) < near_limit )
995 {
996 next->flags |= AF_FLAG_WEAK_INTERPOLATION;
997 continue;
998 }
999
1000 curr->u = (FT_Pos)( next - curr );
1001 next->v = -curr->u;
1002
1003 out_dir = af_direction_compute( out_x, out_y );
1004
1005 /* adjust directions for all points inbetween; */
1006 /* the loop also updates position of `curr' */
1007 curr->out_dir = (FT_Char)out_dir;
1008 for ( curr = curr->next; curr != next; curr = curr->next )
1009 {
1010 curr->in_dir = (FT_Char)out_dir;
1011 curr->out_dir = (FT_Char)out_dir;
1012 }
1013 next->in_dir = (FT_Char)out_dir;
1014
1015 curr->u = (FT_Pos)( first - curr );
1016 first->v = -curr->u;
1017
1018 out_x = 0;
1019 out_y = 0;
1020
1021 } while ( next != first );
1022 }
1023
1024 /*
1025 * The next step is to `simplify' an outline's topology so that we
1026 * can identify local extrema more reliably: A series of
1027 * non-horizontal or non-vertical vectors pointing into the same
1028 * quadrant are handled as a single, long vector. From a
1029 * topological point of the view, the intermediate points are of no
1030 * interest and thus tagged as weak.
1031 */
1032
1033 for ( point = points; point < point_limit; point++ )
1034 {
1035 if ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
1036 continue;
1037
1038 if ( point->in_dir == AF_DIR_NONE &&
1039 point->out_dir == AF_DIR_NONE )
1040 {
1041 /* check whether both vectors point into the same quadrant */
1042
1043 FT_Pos in_x, in_y;
1044 FT_Pos out_x, out_y;
1045
1046 AF_Point next_u = point + point->u;
1047 AF_Point prev_v = point + point->v;
1048
1049
1050 in_x = point->fx - prev_v->fx;
1051 in_y = point->fy - prev_v->fy;
1052
1053 out_x = next_u->fx - point->fx;
1054 out_y = next_u->fy - point->fy;
1055
1056 if ( ( in_x ^ out_x ) >= 0 && ( in_y ^ out_y ) >= 0 )
1057 {
1058 /* yes, so tag current point as weak */
1059 /* and update index deltas */
1060
1061 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
1062
1063 prev_v->u = (FT_Pos)( next_u - prev_v );
1064 next_u->v = -prev_v->u;
1065 }
1066 }
1067 }
1068
1069 /*
1070 * Finally, check for remaining weak points. Everything else not
1071 * collected in edges so far is then implicitly classified as strong
1072 * points.
1073 */
1074
1075 for ( point = points; point < point_limit; point++ )
1076 {
1077 if ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
1078 continue;
1079
1080 if ( point->flags & AF_FLAG_CONTROL )
1081 {
1082 /* control points are always weak */
1083 Is_Weak_Point:
1084 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
1085 }
1086 else if ( point->out_dir == point->in_dir )
1087 {
1088 if ( point->out_dir != AF_DIR_NONE )
1089 {
1090 /* current point lies on a horizontal or */
1091 /* vertical segment (but doesn't start or end it) */
1092 goto Is_Weak_Point;
1093 }
1094
1095 {
1096 AF_Point next_u = point + point->u;
1097 AF_Point prev_v = point + point->v;
1098
1099
1100 if ( ft_corner_is_flat( point->fx - prev_v->fx,
1101 point->fy - prev_v->fy,
1102 next_u->fx - point->fx,
1103 next_u->fy - point->fy ) )
1104 {
1105 /* either the `in' or the `out' vector is much more */
1106 /* dominant than the other one, so tag current point */
1107 /* as weak and update index deltas */
1108
1109 prev_v->u = (FT_Pos)( next_u - prev_v );
1110 next_u->v = -prev_v->u;
1111
1112 goto Is_Weak_Point;
1113 }
1114 }
1115 }
1116 else if ( point->in_dir == -point->out_dir )
1117 {
1118 /* current point forms a spike */
1119 goto Is_Weak_Point;
1120 }
1121 }
1122 }
1123 }
1124
1125 Exit:
1126 return error;
1127 }
1128
1129
1130 /* Store the hinted outline in an FT_Outline structure. */
1131
1132 FT_LOCAL_DEF( void )
1133 af_glyph_hints_save( AF_GlyphHints hints,
1134 FT_Outline* outline )
1135 {
1136 AF_Point point = hints->points;
1137 AF_Point limit = point + hints->num_points;
1138 FT_Vector* vec = outline->points;
1139 char* tag = outline->tags;
1140
1141
1142 for ( ; point < limit; point++, vec++, tag++ )
1143 {
1144 vec->x = point->x;
1145 vec->y = point->y;
1146
1147 if ( point->flags & AF_FLAG_CONIC )
1148 tag[0] = FT_CURVE_TAG_CONIC;
1149 else if ( point->flags & AF_FLAG_CUBIC )
1150 tag[0] = FT_CURVE_TAG_CUBIC;
1151 else
1152 tag[0] = FT_CURVE_TAG_ON;
1153 }
1154 }
1155
1156
1157 /****************************************************************
1158 *
1159 * EDGE POINT GRID-FITTING
1160 *
1161 ****************************************************************/
1162
1163
1164 /* Align all points of an edge to the same coordinate value, */
1165 /* either horizontally or vertically. */
1166
1167 FT_LOCAL_DEF( void )
1168 af_glyph_hints_align_edge_points( AF_GlyphHints hints,
1169 AF_Dimension dim )
1170 {
1171 AF_AxisHints axis = & hints->axis[dim];
1172 AF_Segment segments = axis->segments;
1173 AF_Segment segment_limit = segments + axis->num_segments;
1174 AF_Segment seg;
1175
1176
1177 if ( dim == AF_DIMENSION_HORZ )
1178 {
1179 for ( seg = segments; seg < segment_limit; seg++ )
1180 {
1181 AF_Edge edge = seg->edge;
1182 AF_Point point, first, last;
1183
1184
1185 if ( edge == NULL )
1186 continue;
1187
1188 first = seg->first;
1189 last = seg->last;
1190 point = first;
1191 for (;;)
1192 {
1193 point->x = edge->pos;
1194 point->flags |= AF_FLAG_TOUCH_X;
1195
1196 if ( point == last )
1197 break;
1198
1199 point = point->next;
1200 }
1201 }
1202 }
1203 else
1204 {
1205 for ( seg = segments; seg < segment_limit; seg++ )
1206 {
1207 AF_Edge edge = seg->edge;
1208 AF_Point point, first, last;
1209
1210
1211 if ( edge == NULL )
1212 continue;
1213
1214 first = seg->first;
1215 last = seg->last;
1216 point = first;
1217 for (;;)
1218 {
1219 point->y = edge->pos;
1220 point->flags |= AF_FLAG_TOUCH_Y;
1221
1222 if ( point == last )
1223 break;
1224
1225 point = point->next;
1226 }
1227 }
1228 }
1229 }
1230
1231
1232 /****************************************************************
1233 *
1234 * STRONG POINT INTERPOLATION
1235 *
1236 ****************************************************************/
1237
1238
1239 /* Hint the strong points -- this is equivalent to the TrueType `IP' */
1240 /* hinting instruction. */
1241
1242 FT_LOCAL_DEF( void )
1243 af_glyph_hints_align_strong_points( AF_GlyphHints hints,
1244 AF_Dimension dim )
1245 {
1246 AF_Point points = hints->points;
1247 AF_Point point_limit = points + hints->num_points;
1248 AF_AxisHints axis = &hints->axis[dim];
1249 AF_Edge edges = axis->edges;
1250 AF_Edge edge_limit = edges + axis->num_edges;
1251 FT_UInt touch_flag;
1252
1253
1254 if ( dim == AF_DIMENSION_HORZ )
1255 touch_flag = AF_FLAG_TOUCH_X;
1256 else
1257 touch_flag = AF_FLAG_TOUCH_Y;
1258
1259 if ( edges < edge_limit )
1260 {
1261 AF_Point point;
1262 AF_Edge edge;
1263
1264
1265 for ( point = points; point < point_limit; point++ )
1266 {
1267 FT_Pos u, ou, fu; /* point position */
1268 FT_Pos delta;
1269
1270
1271 if ( point->flags & touch_flag )
1272 continue;
1273
1274 /* if this point is candidate to weak interpolation, we */
1275 /* interpolate it after all strong points have been processed */
1276
1277 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) )
1278 continue;
1279
1280 if ( dim == AF_DIMENSION_VERT )
1281 {
1282 u = point->fy;
1283 ou = point->oy;
1284 }
1285 else
1286 {
1287 u = point->fx;
1288 ou = point->ox;
1289 }
1290
1291 fu = u;
1292
1293 /* is the point before the first edge? */
1294 edge = edges;
1295 delta = edge->fpos - u;
1296 if ( delta >= 0 )
1297 {
1298 u = edge->pos - ( edge->opos - ou );
1299 goto Store_Point;
1300 }
1301
1302 /* is the point after the last edge? */
1303 edge = edge_limit - 1;
1304 delta = u - edge->fpos;
1305 if ( delta >= 0 )
1306 {
1307 u = edge->pos + ( ou - edge->opos );
1308 goto Store_Point;
1309 }
1310
1311 {
1312 FT_PtrDist min, max, mid;
1313 FT_Pos fpos;
1314
1315
1316 /* find enclosing edges */
1317 min = 0;
1318 max = edge_limit - edges;
1319
1320 #if 1
1321 /* for a small number of edges, a linear search is better */
1322 if ( max <= 8 )
1323 {
1324 FT_PtrDist nn;
1325
1326
1327 for ( nn = 0; nn < max; nn++ )
1328 if ( edges[nn].fpos >= u )
1329 break;
1330
1331 if ( edges[nn].fpos == u )
1332 {
1333 u = edges[nn].pos;
1334 goto Store_Point;
1335 }
1336 min = nn;
1337 }
1338 else
1339 #endif
1340 while ( min < max )
1341 {
1342 mid = ( max + min ) >> 1;
1343 edge = edges + mid;
1344 fpos = edge->fpos;
1345
1346 if ( u < fpos )
1347 max = mid;
1348 else if ( u > fpos )
1349 min = mid + 1;
1350 else
1351 {
1352 /* we are on the edge */
1353 u = edge->pos;
1354 goto Store_Point;
1355 }
1356 }
1357
1358 /* point is not on an edge */
1359 {
1360 AF_Edge before = edges + min - 1;
1361 AF_Edge after = edges + min + 0;
1362
1363
1364 /* assert( before && after && before != after ) */
1365 if ( before->scale == 0 )
1366 before->scale = FT_DivFix( after->pos - before->pos,
1367 after->fpos - before->fpos );
1368
1369 u = before->pos + FT_MulFix( fu - before->fpos,
1370 before->scale );
1371 }
1372 }
1373
1374 Store_Point:
1375 /* save the point position */
1376 if ( dim == AF_DIMENSION_HORZ )
1377 point->x = u;
1378 else
1379 point->y = u;
1380
1381 point->flags |= touch_flag;
1382 }
1383 }
1384 }
1385
1386
1387 /****************************************************************
1388 *
1389 * WEAK POINT INTERPOLATION
1390 *
1391 ****************************************************************/
1392
1393
1394 /* Shift the original coordinates of all points between `p1' and */
1395 /* `p2' to get hinted coordinates, using the same difference as */
1396 /* given by `ref'. */
1397
1398 static void
1399 af_iup_shift( AF_Point p1,
1400 AF_Point p2,
1401 AF_Point ref )
1402 {
1403 AF_Point p;
1404 FT_Pos delta = ref->u - ref->v;
1405
1406
1407 if ( delta == 0 )
1408 return;
1409
1410 for ( p = p1; p < ref; p++ )
1411 p->u = p->v + delta;
1412
1413 for ( p = ref + 1; p <= p2; p++ )
1414 p->u = p->v + delta;
1415 }
1416
1417
1418 /* Interpolate the original coordinates of all points between `p1' and */
1419 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1420 /* reference points. The `u' and `v' members are the current and */
1421 /* original coordinate values, respectively. */
1422 /* */
1423 /* Details can be found in the TrueType bytecode specification. */
1424
1425 static void
1426 af_iup_interp( AF_Point p1,
1427 AF_Point p2,
1428 AF_Point ref1,
1429 AF_Point ref2 )
1430 {
1431 AF_Point p;
1432 FT_Pos u, v1, v2, u1, u2, d1, d2;
1433
1434
1435 if ( p1 > p2 )
1436 return;
1437
1438 if ( ref1->v > ref2->v )
1439 {
1440 p = ref1;
1441 ref1 = ref2;
1442 ref2 = p;
1443 }
1444
1445 v1 = ref1->v;
1446 v2 = ref2->v;
1447 u1 = ref1->u;
1448 u2 = ref2->u;
1449 d1 = u1 - v1;
1450 d2 = u2 - v2;
1451
1452 if ( u1 == u2 || v1 == v2 )
1453 {
1454 for ( p = p1; p <= p2; p++ )
1455 {
1456 u = p->v;
1457
1458 if ( u <= v1 )
1459 u += d1;
1460 else if ( u >= v2 )
1461 u += d2;
1462 else
1463 u = u1;
1464
1465 p->u = u;
1466 }
1467 }
1468 else
1469 {
1470 FT_Fixed scale = FT_DivFix( u2 - u1, v2 - v1 );
1471
1472
1473 for ( p = p1; p <= p2; p++ )
1474 {
1475 u = p->v;
1476
1477 if ( u <= v1 )
1478 u += d1;
1479 else if ( u >= v2 )
1480 u += d2;
1481 else
1482 u = u1 + FT_MulFix( u - v1, scale );
1483
1484 p->u = u;
1485 }
1486 }
1487 }
1488
1489
1490 /* Hint the weak points -- this is equivalent to the TrueType `IUP' */
1491 /* hinting instruction. */
1492
1493 FT_LOCAL_DEF( void )
1494 af_glyph_hints_align_weak_points( AF_GlyphHints hints,
1495 AF_Dimension dim )
1496 {
1497 AF_Point points = hints->points;
1498 AF_Point point_limit = points + hints->num_points;
1499 AF_Point* contour = hints->contours;
1500 AF_Point* contour_limit = contour + hints->num_contours;
1501 FT_UInt touch_flag;
1502 AF_Point point;
1503 AF_Point end_point;
1504 AF_Point first_point;
1505
1506
1507 /* PASS 1: Move segment points to edge positions */
1508
1509 if ( dim == AF_DIMENSION_HORZ )
1510 {
1511 touch_flag = AF_FLAG_TOUCH_X;
1512
1513 for ( point = points; point < point_limit; point++ )
1514 {
1515 point->u = point->x;
1516 point->v = point->ox;
1517 }
1518 }
1519 else
1520 {
1521 touch_flag = AF_FLAG_TOUCH_Y;
1522
1523 for ( point = points; point < point_limit; point++ )
1524 {
1525 point->u = point->y;
1526 point->v = point->oy;
1527 }
1528 }
1529
1530 for ( ; contour < contour_limit; contour++ )
1531 {
1532 AF_Point first_touched, last_touched;
1533
1534
1535 point = *contour;
1536 end_point = point->prev;
1537 first_point = point;
1538
1539 /* find first touched point */
1540 for (;;)
1541 {
1542 if ( point > end_point ) /* no touched point in contour */
1543 goto NextContour;
1544
1545 if ( point->flags & touch_flag )
1546 break;
1547
1548 point++;
1549 }
1550
1551 first_touched = point;
1552
1553 for (;;)
1554 {
1555 FT_ASSERT( point <= end_point &&
1556 ( point->flags & touch_flag ) != 0 );
1557
1558 /* skip any touched neighbours */
1559 while ( point < end_point &&
1560 ( point[1].flags & touch_flag ) != 0 )
1561 point++;
1562
1563 last_touched = point;
1564
1565 /* find the next touched point, if any */
1566 point++;
1567 for (;;)
1568 {
1569 if ( point > end_point )
1570 goto EndContour;
1571
1572 if ( ( point->flags & touch_flag ) != 0 )
1573 break;
1574
1575 point++;
1576 }
1577
1578 /* interpolate between last_touched and point */
1579 af_iup_interp( last_touched + 1, point - 1,
1580 last_touched, point );
1581 }
1582
1583 EndContour:
1584 /* special case: only one point was touched */
1585 if ( last_touched == first_touched )
1586 af_iup_shift( first_point, end_point, first_touched );
1587
1588 else /* interpolate the last part */
1589 {
1590 if ( last_touched < end_point )
1591 af_iup_interp( last_touched + 1, end_point,
1592 last_touched, first_touched );
1593
1594 if ( first_touched > points )
1595 af_iup_interp( first_point, first_touched - 1,
1596 last_touched, first_touched );
1597 }
1598
1599 NextContour:
1600 ;
1601 }
1602
1603 /* now save the interpolated values back to x/y */
1604 if ( dim == AF_DIMENSION_HORZ )
1605 {
1606 for ( point = points; point < point_limit; point++ )
1607 point->x = point->u;
1608 }
1609 else
1610 {
1611 for ( point = points; point < point_limit; point++ )
1612 point->y = point->u;
1613 }
1614 }
1615
1616
1617 #ifdef AF_CONFIG_OPTION_USE_WARPER
1618
1619 /* Apply (small) warp scale and warp delta for given dimension. */
1620
1621 FT_LOCAL_DEF( void )
1622 af_glyph_hints_scale_dim( AF_GlyphHints hints,
1623 AF_Dimension dim,
1624 FT_Fixed scale,
1625 FT_Pos delta )
1626 {
1627 AF_Point points = hints->points;
1628 AF_Point points_limit = points + hints->num_points;
1629 AF_Point point;
1630
1631
1632 if ( dim == AF_DIMENSION_HORZ )
1633 {
1634 for ( point = points; point < points_limit; point++ )
1635 point->x = FT_MulFix( point->fx, scale ) + delta;
1636 }
1637 else
1638 {
1639 for ( point = points; point < points_limit; point++ )
1640 point->y = FT_MulFix( point->fy, scale ) + delta;
1641 }
1642 }
1643
1644 #endif /* AF_CONFIG_OPTION_USE_WARPER */
1645
1646 /* END */
A free Windows-compatible Operating System