1 /***************************************************************************/
5 /* FreeType auto hinting outline optimization (body). */
7 /* Copyright 2000-2001 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 /*************************************************************************/
35 #include FT_INTERNAL_OBJECTS_H /* for ALLOC_ARRAY() and FREE() */
39 /* define this macro to use brute force optimisation -- this is slow, */
40 /* but a good way to perfect the distortion function `by hand' through */
42 #define AH_BRUTE_FORCE
45 #define xxxAH_DEBUG_OPTIM
51 #define LOG( x ) optim_log ## x
57 #endif /* AH_DEBUG_OPTIM */
66 #define FLOAT( x ) ( (float)( (x) / 64.0 ) )
69 optim_log( const char* fmt, ... )
81 AH_Dump_Stems( AH_Optimizer* optimizer )
87 stem = optimizer->stems;
88 for ( n = 0; n < optimizer->num_stems; n++, stem++ )
90 LOG(( " %c%2d [%.1f:%.1f]={%.1f:%.1f}="
91 "<%1.f..%1.f> force=%.1f speed=%.1f\n",
92 optimizer->vertical ? 'V' : 'H', n,
93 FLOAT( stem->edge1->opos ), FLOAT( stem->edge2->opos ),
94 FLOAT( stem->edge1->pos ), FLOAT( stem->edge2->pos ),
95 FLOAT( stem->min_pos ), FLOAT( stem->max_pos ),
96 FLOAT( stem->force ), FLOAT( stem->velocity ) ));
102 AH_Dump_Stems2( AH_Optimizer* optimizer )
108 stem = optimizer->stems;
109 for ( n = 0; n < optimizer->num_stems; n++, stem++ )
111 LOG(( " %c%2d [%.1f]=<%1.f..%1.f> force=%.1f speed=%.1f\n",
112 optimizer->vertical ? 'V' : 'H', n,
114 FLOAT( stem->min_pos ), FLOAT( stem->max_pos ),
115 FLOAT( stem->force ), FLOAT( stem->velocity ) ));
121 AH_Dump_Springs( AH_Optimizer* optimizer )
128 spring = optimizer->springs;
129 stems = optimizer->stems;
130 LOG(( "%cSprings ", optimizer->vertical ? 'V' : 'H' ));
132 for ( n = 0; n < optimizer->num_springs; n++, spring++ )
134 LOG(( " [%d-%d:%.1f:%1.f:%.1f]",
135 spring->stem1 - stems, spring->stem2 - stems,
136 FLOAT( spring->owidth ),
137 FLOAT( spring->stem2->pos -
138 ( spring->stem1->pos + spring->stem1->width ) ),
139 FLOAT( spring->tension ) ));
145 #endif /* AH_DEBUG_OPTIM */
148 /*************************************************************************/
149 /*************************************************************************/
150 /*************************************************************************/
152 /**** COMPUTE STEMS AND SPRINGS IN AN OUTLINE ****/
154 /*************************************************************************/
155 /*************************************************************************/
156 /*************************************************************************/
160 valid_stem_segments( AH_Segment* seg1,
163 return seg1->serif == 0 &&
165 seg2->link == seg1 &&
166 seg1->pos < seg2->pos &&
167 seg1->min_coord <= seg2->max_coord &&
168 seg2->min_coord <= seg1->max_coord;
172 /* compute all stems in an outline */
174 optim_compute_stems( AH_Optimizer* optimizer )
176 AH_Outline* outline = optimizer->outline;
178 FT_Memory memory = optimizer->memory;
187 edges = outline->horz_edges;
188 edge_limit = edges + outline->num_hedges;
189 scale = outline->y_scale;
191 p_stems = &optimizer->horz_stems;
192 p_num_stems = &optimizer->num_hstems;
194 for ( dimension = 1; dimension >= 0; dimension-- )
197 FT_Int num_stems = 0;
201 /* first of all, count the number of stems in this direction */
202 for ( edge = edges; edge < edge_limit; edge++ )
204 AH_Segment* seg = edge->first;
209 if (valid_stem_segments( seg, seg->link ) )
212 seg = seg->edge_next;
214 } while ( seg != edge->first );
217 /* now allocate the stems and build their table */
223 if ( ALLOC_ARRAY( stems, num_stems, AH_Stem ) )
227 for ( edge = edges; edge < edge_limit; edge++ )
229 AH_Segment* seg = edge->first;
236 if ( valid_stem_segments( seg, seg2 ) )
238 AH_Edge* edge1 = seg->edge;
239 AH_Edge* edge2 = seg2->edge;
244 stem->opos = edge1->opos;
245 stem->pos = edge1->pos;
246 stem->owidth = edge2->opos - edge1->opos;
247 stem->width = edge2->pos - edge1->pos;
249 /* compute min_coord and max_coord */
251 FT_Pos min_coord = seg->min_coord;
252 FT_Pos max_coord = seg->max_coord;
255 if ( seg2->min_coord > min_coord )
256 min_coord = seg2->min_coord;
258 if ( seg2->max_coord < max_coord )
259 max_coord = seg2->max_coord;
261 stem->min_coord = min_coord;
262 stem->max_coord = max_coord;
265 /* compute minimum and maximum positions for stem -- */
266 /* note that the left-most/bottom-most stem has always */
267 /* a fixed position */
268 if ( stem == stems || edge1->blue_edge || edge2->blue_edge )
270 /* this stem cannot move; it is snapped to a blue edge */
271 stem->min_pos = stem->pos;
272 stem->max_pos = stem->pos;
276 /* this edge can move; compute its min and max positions */
277 FT_Pos pos1 = stem->opos;
278 FT_Pos pos2 = pos1 + stem->owidth - stem->width;
279 FT_Pos min1 = pos1 & -64;
280 FT_Pos min2 = pos2 & -64;
283 stem->min_pos = min1;
284 stem->max_pos = min1 + 64;
286 stem->min_pos = min2;
288 stem->max_pos = min2 + 64;
290 /* XXX: just to see what it does */
293 /* just for the case where direct hinting did some */
294 /* incredible things (e.g. blue edge shifts) */
295 if ( stem->min_pos > stem->pos )
296 stem->min_pos = stem->pos;
298 if ( stem->max_pos < stem->pos )
299 stem->max_pos = stem->pos;
307 seg = seg->edge_next;
309 } while ( seg != edge->first );
314 *p_num_stems = num_stems;
316 edges = outline->vert_edges;
317 edge_limit = edges + outline->num_vedges;
318 scale = outline->x_scale;
320 p_stems = &optimizer->vert_stems;
321 p_num_stems = &optimizer->num_vstems;
326 #ifdef AH_DEBUG_OPTIM
327 AH_Dump_Stems( optimizer );
334 /* returns the spring area between two stems, 0 if none */
336 stem_spring_area( AH_Stem* stem1,
339 FT_Pos area1 = stem1->max_coord - stem1->min_coord;
340 FT_Pos area2 = stem2->max_coord - stem2->min_coord;
341 FT_Pos min = stem1->min_coord;
342 FT_Pos max = stem1->max_coord;
347 if ( stem2->opos <= stem1->opos + stem1->owidth )
350 if ( min < stem2->min_coord )
351 min = stem2->min_coord;
353 if ( max < stem2->max_coord )
354 max = stem2->max_coord;
357 if ( 2 * area < area1 && 2 * area < area2 )
364 /* compute all springs in an outline */
366 optim_compute_springs( AH_Optimizer* optimizer )
368 /* basically, a spring exists between two stems if most of their */
369 /* surface is aligned */
370 FT_Memory memory = optimizer->memory;
378 FT_Int* p_num_springs;
379 AH_Spring** p_springs;
382 stems = optimizer->horz_stems;
383 stem_limit = stems + optimizer->num_hstems;
385 p_springs = &optimizer->horz_springs;
386 p_num_springs = &optimizer->num_hsprings;
388 for ( dimension = 1; dimension >= 0; dimension-- )
390 FT_Int num_springs = 0;
391 AH_Spring* springs = 0;
394 /* first of all, count stem springs */
395 for ( stem = stems; stem + 1 < stem_limit; stem++ )
400 for ( stem2 = stem+1; stem2 < stem_limit; stem2++ )
401 if ( stem_spring_area( stem, stem2 ) )
405 /* then allocate and build the springs table */
406 if ( num_springs > 0 )
411 /* allocate table of springs */
412 if ( ALLOC_ARRAY( springs, num_springs, AH_Spring ) )
415 /* fill the springs table */
417 for ( stem = stems; stem+1 < stem_limit; stem++ )
423 for ( stem2 = stem + 1; stem2 < stem_limit; stem2++ )
425 area = stem_spring_area( stem, stem2 );
428 /* add a new spring here */
429 spring->stem1 = stem;
430 spring->stem2 = stem2;
431 spring->owidth = stem2->opos - ( stem->opos + stem->owidth );
439 *p_num_springs = num_springs;
440 *p_springs = springs;
442 stems = optimizer->vert_stems;
443 stem_limit = stems + optimizer->num_vstems;
445 p_springs = &optimizer->vert_springs;
446 p_num_springs = &optimizer->num_vsprings;
451 #ifdef AH_DEBUG_OPTIM
452 AH_Dump_Springs( optimizer );
459 /*************************************************************************/
460 /*************************************************************************/
461 /*************************************************************************/
463 /**** OPTIMIZE THROUGH MY STRANGE SIMULATED ANNEALING ALGO ;-) ****/
465 /*************************************************************************/
466 /*************************************************************************/
467 /*************************************************************************/
469 #ifndef AH_BRUTE_FORCE
471 /* compute all spring tensions */
473 optim_compute_tensions( AH_Optimizer* optimizer )
475 AH_Spring* spring = optimizer->springs;
476 AH_Spring* limit = spring + optimizer->num_springs;
479 for ( ; spring < limit; spring++ )
481 AH_Stem* stem1 = spring->stem1;
482 AH_Stem* stem2 = spring->stem2;
490 /* compute the tension; it simply is -K*(new_width-old_width) */
491 width = stem2->pos - ( stem1->pos + stem1->width );
492 tension = width - spring->owidth;
504 tension = ( tension << 10 ) / width;
506 tension = -sign * FT_MulFix( tension, optimizer->tension_scale );
507 spring->tension = tension;
509 /* now, distribute tension among the englobing stems, if they */
510 /* are able to move */
512 if ( stem1->pos <= stem1->min_pos )
514 if ( stem2->pos >= stem2->max_pos )
520 if ( ( status & 1 ) == 0 )
521 stem1->force -= tension;
523 if ( ( status & 2 ) == 0 )
524 stem2->force += tension;
529 /* compute all stem movements -- returns 0 if nothing moved */
531 optim_compute_stem_movements( AH_Optimizer* optimizer )
533 AH_Stem* stems = optimizer->stems;
534 AH_Stem* limit = stems + optimizer->num_stems;
535 AH_Stem* stem = stems;
539 /* set initial forces to velocity */
540 for ( stem = stems; stem < limit; stem++ )
542 stem->force = stem->velocity;
543 stem->velocity /= 2; /* XXX: Heuristics */
546 /* compute the sum of forces applied on each stem */
547 optim_compute_tensions( optimizer );
549 #ifdef AH_DEBUG_OPTIM
550 AH_Dump_Springs( optimizer );
551 AH_Dump_Stems2( optimizer );
554 /* now, see whether something can move */
555 for ( stem = stems; stem < limit; stem++ )
557 if ( stem->force > optimizer->tension_threshold )
559 /* there is enough tension to move the stem to the right */
560 if ( stem->pos < stem->max_pos )
563 stem->velocity = stem->force / 2;
569 else if ( stem->force < optimizer->tension_threshold )
571 /* there is enough tension to move the stem to the left */
572 if ( stem->pos > stem->min_pos )
575 stem->velocity = stem->force / 2;
583 /* return 0 if nothing moved */
587 #endif /* AH_BRUTE_FORCE */
590 /* compute current global distortion from springs */
592 optim_compute_distortion( AH_Optimizer* optimizer )
594 AH_Spring* spring = optimizer->springs;
595 AH_Spring* limit = spring + optimizer->num_springs;
596 FT_Pos distortion = 0;
599 for ( ; spring < limit; spring++ )
601 AH_Stem* stem1 = spring->stem1;
602 AH_Stem* stem2 = spring->stem2;
605 width = stem2->pos - ( stem1->pos + stem1->width );
606 width -= spring->owidth;
617 /* record stems configuration in `best of' history */
619 optim_record_configuration( AH_Optimizer* optimizer )
622 AH_Configuration* configs = optimizer->configs;
623 AH_Configuration* limit = configs + optimizer->num_configs;
624 AH_Configuration* config;
627 distortion = optim_compute_distortion( optimizer );
628 LOG(( "config distortion = %.1f ", FLOAT( distortion * 64 ) ));
630 /* check that we really need to add this configuration to our */
632 if ( limit > configs && limit[-1].distortion < distortion )
634 LOG(( "ejected\n" ));
638 /* add new configuration at the end of the table */
644 if ( optimizer->num_configs < AH_MAX_CONFIGS )
645 optimizer->num_configs++;
649 config->distortion = distortion;
651 for ( n = 0; n < optimizer->num_stems; n++ )
652 config->positions[n] = optimizer->stems[n].pos;
655 /* move the current configuration towards the front of the list */
656 /* when necessary -- yes this is slow bubble sort ;-) */
657 while ( config > configs && config[0].distortion < config[-1].distortion )
659 AH_Configuration temp;
664 config[0] = config[1];
667 LOG(( "recorded!\n" ));
671 #ifdef AH_BRUTE_FORCE
673 /* optimize outline in a single direction */
675 optim_compute( AH_Optimizer* optimizer )
680 AH_Stem* stem = optimizer->stems;
681 AH_Stem* limit = stem + optimizer->num_stems;
688 optimizer->num_configs = 0;
690 stem = optimizer->stems;
691 for ( ; stem < limit; stem++ )
692 stem->pos = stem->min_pos;
696 /* record current configuration */
697 optim_record_configuration( optimizer );
699 /* now change configuration */
701 for ( stem = optimizer->stems; stem < limit; stem++ )
703 if ( stem->pos < stem->max_pos )
710 stem->pos = stem->min_pos;
714 /* now, set the best stem positions */
715 for ( n = 0; n < optimizer->num_stems; n++ )
717 AH_Stem* stem = optimizer->stems + n;
718 FT_Pos pos = optimizer->configs[0].positions[n];
721 stem->edge1->pos = pos;
722 stem->edge2->pos = pos + stem->width;
724 stem->edge1->flags |= ah_edge_done;
725 stem->edge2->flags |= ah_edge_done;
729 #else /* AH_BRUTE_FORCE */
731 /* optimize outline in a single direction */
733 optim_compute( AH_Optimizer* optimizer )
735 int n, counter, counter2;
738 optimizer->num_configs = 0;
739 optimizer->tension_scale = 0x80000L;
740 optimizer->tension_threshold = 64;
742 /* record initial configuration threshold */
743 optim_record_configuration( optimizer );
746 for ( counter2 = optimizer->num_stems*8; counter2 >= 0; counter2-- )
749 counter = 2 * optimizer->num_stems;
751 if ( !optim_compute_stem_movements( optimizer ) )
754 optim_record_configuration( optimizer );
758 optimizer->tension_scale /= 2;
761 /* now, set the best stem positions */
762 for ( n = 0; n < optimizer->num_stems; n++ )
764 AH_Stem* stem = optimizer->stems + n;
765 FT_Pos pos = optimizer->configs[0].positions[n];
768 stem->edge1->pos = pos;
769 stem->edge2->pos = pos + stem->width;
771 stem->edge1->flags |= ah_edge_done;
772 stem->edge2->flags |= ah_edge_done;
776 #endif /* AH_BRUTE_FORCE */
779 /*************************************************************************/
780 /*************************************************************************/
781 /*************************************************************************/
783 /**** HIGH-LEVEL OPTIMIZER API ****/
785 /*************************************************************************/
786 /*************************************************************************/
787 /*************************************************************************/
790 /* releases the optimization data */
792 AH_Optimizer_Done( AH_Optimizer* optimizer )
796 FT_Memory memory = optimizer->memory;
799 FREE( optimizer->horz_stems );
800 FREE( optimizer->vert_stems );
801 FREE( optimizer->horz_springs );
802 FREE( optimizer->vert_springs );
803 FREE( optimizer->positions );
808 /* loads the outline into the optimizer */
810 AH_Optimizer_Init( AH_Optimizer* optimizer,
817 MEM_Set( optimizer, 0, sizeof ( *optimizer ) );
818 optimizer->outline = outline;
819 optimizer->memory = memory;
821 LOG(( "initializing new optimizer\n" ));
822 /* compute stems and springs */
823 error = optim_compute_stems ( optimizer ) ||
824 optim_compute_springs( optimizer );
828 /* allocate stem positions history and configurations */
833 max_stems = optimizer->num_hstems;
834 if ( max_stems < optimizer->num_vstems )
835 max_stems = optimizer->num_vstems;
837 if ( ALLOC_ARRAY( optimizer->positions,
838 max_stems * AH_MAX_CONFIGS, FT_Pos ) )
841 optimizer->num_configs = 0;
842 for ( n = 0; n < AH_MAX_CONFIGS; n++ )
843 optimizer->configs[n].positions = optimizer->positions +
850 AH_Optimizer_Done( optimizer );
855 /* compute optimal outline */
857 AH_Optimizer_Compute( AH_Optimizer* optimizer )
859 optimizer->num_stems = optimizer->num_hstems;
860 optimizer->stems = optimizer->horz_stems;
861 optimizer->num_springs = optimizer->num_hsprings;
862 optimizer->springs = optimizer->horz_springs;
864 if ( optimizer->num_springs > 0 )
866 LOG(( "horizontal optimization ------------------------\n" ));
867 optim_compute( optimizer );
870 optimizer->num_stems = optimizer->num_vstems;
871 optimizer->stems = optimizer->vert_stems;
872 optimizer->num_springs = optimizer->num_vsprings;
873 optimizer->springs = optimizer->vert_springs;
875 if ( optimizer->num_springs )
877 LOG(( "vertical optimization --------------------------\n" ));
878 optim_compute( optimizer );