1 /***************************************************************************/
5 /* FreeType auto hinting outline optimization (body). */
7 /* Copyright 2000 Catharon Productions Inc. */
8 /* Author: David Turner */
10 /* This file is part of the Catharon Typography Project and shall only */
11 /* be used, modified, and distributed under the terms of the Catharon */
12 /* Open Source License that should come with this file under the name */
13 /* `CatharonLicense.txt'. By continuing to use, modify, or distribute */
14 /* this file you indicate that you have read the license and */
15 /* understand and accept it fully. */
17 /* Note that this license is compatible with the FreeType license. */
19 /***************************************************************************/
22 /*************************************************************************/
24 /* This module is in charge of optimising the outlines produced by the */
25 /* auto-hinter in direct mode. This is required at small pixel sizes in */
26 /* order to ensure coherent spacing, among other things.. */
28 /* The technique used in this module is a simplified simulated */
31 /*************************************************************************/
34 #include <freetype/internal/ftobjs.h> /* for ALLOC_ARRAY() and FREE() */
37 #ifdef FT_FLAT_COMPILE
43 #include <freetype/src/autohint/ahoptim.h>
48 /* define this macro to use brute force optimisation -- this is slow, */
49 /* but a good way to perfect the distortion function `by hand' through */
51 #define AH_BRUTE_FORCE
54 #define xxxAH_DEBUG_OPTIM
60 #define LOG( x ) optim_log##x
66 #endif /* AH_DEBUG_OPTIM */
75 #define FLOAT( x ) ( (float)( (x) / 64.0 ) )
78 void optim_log( const char* fmt, ... )
84 /* vprintf( fmt, ap ); FIXME */
90 void AH_Dump_Stems( AH_Optimizer* optimizer )
96 stem = optimizer->stems;
97 for ( n = 0; n < optimizer->num_stems; n++, stem++ )
99 LOG(( " %c%2d [%.1f:%.1f]={%.1f:%.1f}="
100 "<%1.f..%1.f> force=%.1f speed=%.1f\n",
101 optimizer->vertical ? 'V' : 'H', n,
102 FLOAT( stem->edge1->opos ), FLOAT( stem->edge2->opos ),
103 FLOAT( stem->edge1->pos ), FLOAT( stem->edge2->pos ),
104 FLOAT( stem->min_pos ), FLOAT( stem->max_pos ),
105 FLOAT( stem->force ), FLOAT( stem->velocity ) ));
111 void AH_Dump_Stems2( AH_Optimizer* optimizer )
117 stem = optimizer->stems;
118 for ( n = 0; n < optimizer->num_stems; n++, stem++ )
120 LOG(( " %c%2d [%.1f]=<%1.f..%1.f> force=%.1f speed=%.1f\n",
121 optimizer->vertical ? 'V' : 'H', n,
123 FLOAT( stem->min_pos ), FLOAT( stem->max_pos ),
124 FLOAT( stem->force ), FLOAT( stem->velocity ) ));
130 void AH_Dump_Springs( AH_Optimizer* optimizer )
137 spring = optimizer->springs;
138 stems = optimizer->stems;
139 LOG(( "%cSprings ", optimizer->vertical ? 'V' : 'H' ));
141 for ( n = 0; n < optimizer->num_springs; n++, spring++ )
143 LOG(( " [%d-%d:%.1f:%1.f:%.1f]",
144 spring->stem1 - stems, spring->stem2 - stems,
145 FLOAT( spring->owidth ),
146 FLOAT( spring->stem2->pos -
147 ( spring->stem1->pos + spring->stem1->width ) ),
148 FLOAT( spring->tension ) ));
154 #endif /* AH_DEBUG_OPTIM */
157 /*************************************************************************/
158 /*************************************************************************/
159 /*************************************************************************/
161 /**** COMPUTE STEMS AND SPRINGS IN AN OUTLINE ****/
163 /*************************************************************************/
164 /*************************************************************************/
165 /*************************************************************************/
169 int valid_stem_segments( AH_Segment* seg1,
172 return seg1->serif == 0 &&
174 seg2->link == seg1 &&
175 seg1->pos < seg2->pos &&
176 seg1->min_coord <= seg2->max_coord &&
177 seg2->min_coord <= seg1->max_coord;
181 /* compute all stems in an outline */
183 int optim_compute_stems( AH_Optimizer* optimizer )
185 AH_Outline* outline = optimizer->outline;
187 FT_Memory memory = optimizer->memory;
196 edges = outline->horz_edges;
197 edge_limit = edges + outline->num_hedges;
198 scale = outline->y_scale;
200 p_stems = &optimizer->horz_stems;
201 p_num_stems = &optimizer->num_hstems;
203 for ( dimension = 1; dimension >= 0; dimension-- )
206 FT_Int num_stems = 0;
210 /* first of all, count the number of stems in this direction */
211 for ( edge = edges; edge < edge_limit; edge++ )
213 AH_Segment* seg = edge->first;
218 if (valid_stem_segments( seg, seg->link ) )
221 seg = seg->edge_next;
223 } while ( seg != edge->first );
226 /* now allocate the stems and build their table */
232 if ( ALLOC_ARRAY( stems, num_stems, AH_Stem ) )
236 for ( edge = edges; edge < edge_limit; edge++ )
238 AH_Segment* seg = edge->first;
245 if ( valid_stem_segments( seg, seg2 ) )
247 AH_Edge* edge1 = seg->edge;
248 AH_Edge* edge2 = seg2->edge;
253 stem->opos = edge1->opos;
254 stem->pos = edge1->pos;
255 stem->owidth = edge2->opos - edge1->opos;
256 stem->width = edge2->pos - edge1->pos;
258 /* compute min_coord and max_coord */
260 FT_Pos min_coord = seg->min_coord;
261 FT_Pos max_coord = seg->max_coord;
264 if ( seg2->min_coord > min_coord )
265 min_coord = seg2->min_coord;
267 if ( seg2->max_coord < max_coord )
268 max_coord = seg2->max_coord;
270 stem->min_coord = min_coord;
271 stem->max_coord = max_coord;
274 /* compute minimum and maximum positions for stem -- */
275 /* note that the left-most/bottom-most stem has always */
276 /* a fixed position */
277 if ( stem == stems || edge1->blue_edge || edge2->blue_edge )
279 /* this stem cannot move; it is snapped to a blue edge */
280 stem->min_pos = stem->pos;
281 stem->max_pos = stem->pos;
285 /* this edge can move; compute its min and max positions */
286 FT_Pos pos1 = stem->opos;
287 FT_Pos pos2 = pos1 + stem->owidth - stem->width;
288 FT_Pos min1 = pos1 & -64;
289 FT_Pos min2 = pos2 & -64;
292 stem->min_pos = min1;
293 stem->max_pos = min1 + 64;
295 stem->min_pos = min2;
297 stem->max_pos = min2 + 64;
299 /* XXX: just to see what it does */
302 /* just for the case where direct hinting did some */
303 /* incredible things (e.g. blue edge shifts) */
304 if ( stem->min_pos > stem->pos )
305 stem->min_pos = stem->pos;
307 if ( stem->max_pos < stem->pos )
308 stem->max_pos = stem->pos;
316 seg = seg->edge_next;
318 } while ( seg != edge->first );
323 *p_num_stems = num_stems;
325 edges = outline->vert_edges;
326 edge_limit = edges + outline->num_vedges;
327 scale = outline->x_scale;
329 p_stems = &optimizer->vert_stems;
330 p_num_stems = &optimizer->num_vstems;
335 #ifdef AH_DEBUG_OPTIM
336 AH_Dump_Stems( optimizer );
343 /* returns the spring area between two stems, 0 if none */
345 FT_Pos stem_spring_area( AH_Stem* stem1,
348 FT_Pos area1 = stem1->max_coord - stem1->min_coord;
349 FT_Pos area2 = stem2->max_coord - stem2->min_coord;
350 FT_Pos min = stem1->min_coord;
351 FT_Pos max = stem1->max_coord;
356 if ( stem2->opos <= stem1->opos + stem1->owidth )
359 if ( min < stem2->min_coord )
360 min = stem2->min_coord;
362 if ( max < stem2->max_coord )
363 max = stem2->max_coord;
366 if ( 2 * area < area1 && 2 * area < area2 )
373 /* compute all springs in an outline */
375 int optim_compute_springs( AH_Optimizer* optimizer )
377 /* basically, a spring exists between two stems if most of their */
378 /* surface is aligned */
379 FT_Memory memory = optimizer->memory;
387 FT_Int* p_num_springs;
388 AH_Spring** p_springs;
391 stems = optimizer->horz_stems;
392 stem_limit = stems + optimizer->num_hstems;
394 p_springs = &optimizer->horz_springs;
395 p_num_springs = &optimizer->num_hsprings;
397 for ( dimension = 1; dimension >= 0; dimension-- )
399 FT_Int num_springs = 0;
400 AH_Spring* springs = 0;
403 /* first of all, count stem springs */
404 for ( stem = stems; stem + 1 < stem_limit; stem++ )
409 for ( stem2 = stem+1; stem2 < stem_limit; stem2++ )
410 if ( stem_spring_area( stem, stem2 ) )
414 /* then allocate and build the springs table */
415 if ( num_springs > 0 )
420 /* allocate table of springs */
421 if ( ALLOC_ARRAY( springs, num_springs, AH_Spring ) )
424 /* fill the springs table */
426 for ( stem = stems; stem+1 < stem_limit; stem++ )
432 for ( stem2 = stem + 1; stem2 < stem_limit; stem2++ )
434 area = stem_spring_area( stem, stem2 );
437 /* add a new spring here */
438 spring->stem1 = stem;
439 spring->stem2 = stem2;
440 spring->owidth = stem2->opos - ( stem->opos + stem->owidth );
448 *p_num_springs = num_springs;
449 *p_springs = springs;
451 stems = optimizer->vert_stems;
452 stem_limit = stems + optimizer->num_vstems;
454 p_springs = &optimizer->vert_springs;
455 p_num_springs = &optimizer->num_vsprings;
460 #ifdef AH_DEBUG_OPTIM
461 AH_Dump_Springs( optimizer );
468 /*************************************************************************/
469 /*************************************************************************/
470 /*************************************************************************/
472 /**** OPTIMIZE THROUGH MY STRANGE SIMULATED ANNEALING ALGO ;-) ****/
474 /*************************************************************************/
475 /*************************************************************************/
476 /*************************************************************************/
478 #ifndef AH_BRUTE_FORCE
480 /* compute all spring tensions */
482 void optim_compute_tensions( AH_Optimizer* optimizer )
484 AH_Spring* spring = optimizer->springs;
485 AH_Spring* limit = spring + optimizer->num_springs;
488 for ( ; spring < limit; spring++ )
490 AH_Stem* stem1 = spring->stem1;
491 AH_Stem* stem2 = spring->stem2;
499 /* compute the tension; it simply is -K*(new_width-old_width) */
500 width = stem2->pos - ( stem1->pos + stem1->width );
501 tension = width - spring->owidth;
513 tension = ( tension << 10 ) / width;
515 tension = -sign * FT_MulFix( tension, optimizer->tension_scale );
516 spring->tension = tension;
518 /* now, distribute tension among the englobing stems, if they */
519 /* are able to move */
521 if ( stem1->pos <= stem1->min_pos )
523 if ( stem2->pos >= stem2->max_pos )
529 if ( ( status & 1 ) == 0 )
530 stem1->force -= tension;
532 if ( ( status & 2 ) == 0 )
533 stem2->force += tension;
538 /* compute all stem movements -- returns 0 if nothing moved */
540 int optim_compute_stem_movements( AH_Optimizer* optimizer )
542 AH_Stem* stems = optimizer->stems;
543 AH_Stem* limit = stems + optimizer->num_stems;
544 AH_Stem* stem = stems;
548 /* set initial forces to velocity */
549 for ( stem = stems; stem < limit; stem++ )
551 stem->force = stem->velocity;
552 stem->velocity /= 2; /* XXX: Heuristics */
555 /* compute the sum of forces applied on each stem */
556 optim_compute_tensions( optimizer );
558 #ifdef AH_DEBUG_OPTIM
559 AH_Dump_Springs( optimizer );
560 AH_Dump_Stems2( optimizer );
563 /* now, see whether something can move */
564 for ( stem = stems; stem < limit; stem++ )
566 if ( stem->force > optimizer->tension_threshold )
568 /* there is enough tension to move the stem to the right */
569 if ( stem->pos < stem->max_pos )
572 stem->velocity = stem->force / 2;
578 else if ( stem->force < optimizer->tension_threshold )
580 /* there is enough tension to move the stem to the left */
581 if ( stem->pos > stem->min_pos )
584 stem->velocity = stem->force / 2;
592 /* return 0 if nothing moved */
596 #endif /* AH_BRUTE_FORCE */
599 /* compute current global distortion from springs */
601 FT_Pos optim_compute_distortion( AH_Optimizer* optimizer )
603 AH_Spring* spring = optimizer->springs;
604 AH_Spring* limit = spring + optimizer->num_springs;
605 FT_Pos distortion = 0;
608 for ( ; spring < limit; spring++ )
610 AH_Stem* stem1 = spring->stem1;
611 AH_Stem* stem2 = spring->stem2;
614 width = stem2->pos - ( stem1->pos + stem1->width );
615 width -= spring->owidth;
626 /* record stems configuration in `best of' history */
628 void optim_record_configuration( AH_Optimizer* optimizer )
631 AH_Configuration* configs = optimizer->configs;
632 AH_Configuration* limit = configs + optimizer->num_configs;
633 AH_Configuration* config;
636 distortion = optim_compute_distortion( optimizer );
637 LOG(( "config distortion = %.1f ", FLOAT( distortion * 64 ) ));
639 /* check that we really need to add this configuration to our */
641 if ( limit > configs && limit[-1].distortion < distortion )
643 LOG(( "ejected\n" ));
647 /* add new configuration at the end of the table */
653 if ( optimizer->num_configs < AH_MAX_CONFIGS )
654 optimizer->num_configs++;
658 config->distortion = distortion;
660 for ( n = 0; n < optimizer->num_stems; n++ )
661 config->positions[n] = optimizer->stems[n].pos;
664 /* move the current configuration towards the front of the list */
665 /* when necessary -- yes this is slow bubble sort ;-) */
666 while ( config > configs && config[0].distortion < config[-1].distortion )
668 AH_Configuration temp;
673 config[0] = config[1];
676 LOG(( "recorded!\n" ));
680 #ifdef AH_BRUTE_FORCE
682 /* optimize outline in a single direction */
684 void optim_compute( AH_Optimizer* optimizer )
689 AH_Stem* stem = optimizer->stems;
690 AH_Stem* limit = stem + optimizer->num_stems;
697 optimizer->num_configs = 0;
699 stem = optimizer->stems;
700 for ( ; stem < limit; stem++ )
701 stem->pos = stem->min_pos;
705 /* record current configuration */
706 optim_record_configuration( optimizer );
708 /* now change configuration */
710 for ( stem = optimizer->stems; stem < limit; stem++ )
712 if ( stem->pos < stem->max_pos )
719 stem->pos = stem->min_pos;
723 /* now, set the best stem positions */
724 for ( n = 0; n < optimizer->num_stems; n++ )
726 AH_Stem* stem = optimizer->stems + n;
727 FT_Pos pos = optimizer->configs[0].positions[n];
730 stem->edge1->pos = pos;
731 stem->edge2->pos = pos + stem->width;
733 stem->edge1->flags |= ah_edge_done;
734 stem->edge2->flags |= ah_edge_done;
738 #else /* AH_BRUTE_FORCE */
740 /* optimize outline in a single direction */
742 void optim_compute( AH_Optimizer* optimizer )
744 int n, counter, counter2;
747 optimizer->num_configs = 0;
748 optimizer->tension_scale = 0x80000L;
749 optimizer->tension_threshold = 64;
751 /* record initial configuration threshold */
752 optim_record_configuration( optimizer );
755 for ( counter2 = optimizer->num_stems*8; counter2 >= 0; counter2-- )
758 counter = 2 * optimizer->num_stems;
760 if ( !optim_compute_stem_movements( optimizer ) )
763 optim_record_configuration( optimizer );
767 optimizer->tension_scale /= 2;
770 /* now, set the best stem positions */
771 for ( n = 0; n < optimizer->num_stems; n++ )
773 AH_Stem* stem = optimizer->stems + n;
774 FT_Pos pos = optimizer->configs[0].positions[n];
777 stem->edge1->pos = pos;
778 stem->edge2->pos = pos + stem->width;
780 stem->edge1->flags |= ah_edge_done;
781 stem->edge2->flags |= ah_edge_done;
785 #endif /* AH_BRUTE_FORCE */
788 /*************************************************************************/
789 /*************************************************************************/
790 /*************************************************************************/
792 /**** HIGH-LEVEL OPTIMIZER API ****/
794 /*************************************************************************/
795 /*************************************************************************/
796 /*************************************************************************/
799 /* releases the optimization data */
800 void AH_Optimizer_Done( AH_Optimizer* optimizer )
804 FT_Memory memory = optimizer->memory;
807 FREE( optimizer->horz_stems );
808 FREE( optimizer->vert_stems );
809 FREE( optimizer->horz_springs );
810 FREE( optimizer->vert_springs );
811 FREE( optimizer->positions );
816 /* loads the outline into the optimizer */
817 int AH_Optimizer_Init( AH_Optimizer* optimizer,
824 MEM_Set( optimizer, 0, sizeof ( *optimizer ) );
825 optimizer->outline = outline;
826 optimizer->memory = memory;
828 LOG(( "initializing new optimizer\n" ));
829 /* compute stems and springs */
830 error = optim_compute_stems ( optimizer ) ||
831 optim_compute_springs( optimizer );
835 /* allocate stem positions history and configurations */
840 max_stems = optimizer->num_hstems;
841 if ( max_stems < optimizer->num_vstems )
842 max_stems = optimizer->num_vstems;
844 if ( ALLOC_ARRAY( optimizer->positions,
845 max_stems * AH_MAX_CONFIGS, FT_Pos ) )
848 optimizer->num_configs = 0;
849 for ( n = 0; n < AH_MAX_CONFIGS; n++ )
850 optimizer->configs[n].positions = optimizer->positions +
857 AH_Optimizer_Done( optimizer );
862 /* compute optimal outline */
863 void AH_Optimizer_Compute( AH_Optimizer* optimizer )
865 optimizer->num_stems = optimizer->num_hstems;
866 optimizer->stems = optimizer->horz_stems;
867 optimizer->num_springs = optimizer->num_hsprings;
868 optimizer->springs = optimizer->horz_springs;
870 if ( optimizer->num_springs > 0 )
872 LOG(( "horizontal optimization ------------------------\n" ));
873 optim_compute( optimizer );
876 optimizer->num_stems = optimizer->num_vstems;
877 optimizer->stems = optimizer->vert_stems;
878 optimizer->num_springs = optimizer->num_vsprings;
879 optimizer->springs = optimizer->vert_springs;
881 if ( optimizer->num_springs )
883 LOG(( "vertical optimization --------------------------\n" ));
884 optim_compute( optimizer );