diff options
Diffstat (limited to 'libfreetype/ahoptim.c')
| -rw-r--r-- | libfreetype/ahoptim.c | 882 |
1 files changed, 882 insertions, 0 deletions
diff --git a/libfreetype/ahoptim.c b/libfreetype/ahoptim.c new file mode 100644 index 00000000..8d10f4a4 --- /dev/null +++ b/libfreetype/ahoptim.c @@ -0,0 +1,882 @@ +/***************************************************************************/ +/* */ +/* ahoptim.c */ +/* */ +/* FreeType auto hinting outline optimization (body). */ +/* */ +/* Copyright 2000-2001, 2002 Catharon Productions Inc. */ +/* Author: David Turner */ +/* */ +/* This file is part of the Catharon Typography Project and shall only */ +/* be used, modified, and distributed under the terms of the Catharon */ +/* Open Source License that should come with this file under the name */ +/* `CatharonLicense.txt'. By continuing to use, modify, or distribute */ +/* this file you indicate that you have read the license and */ +/* understand and accept it fully. */ +/* */ +/* Note that this license is compatible with the FreeType license. */ +/* */ +/***************************************************************************/ + + + /*************************************************************************/ + /* */ + /* This module is in charge of optimising the outlines produced by the */ + /* auto-hinter in direct mode. This is required at small pixel sizes in */ + /* order to ensure coherent spacing, among other things.. */ + /* */ + /* The technique used in this module is a simplified simulated */ + /* annealing. */ + /* */ + /*************************************************************************/ + + +#include <ft2build.h> +#include FT_INTERNAL_OBJECTS_H /* for FT_ALLOC_ARRAY() and FT_FREE() */ +#include "ahoptim.h" + + + /* define this macro to use brute force optimization -- this is slow, */ + /* but a good way to perfect the distortion function `by hand' through */ + /* tweaking */ +#define AH_BRUTE_FORCE + + +#define xxxAH_DEBUG_OPTIM + + +#undef LOG +#ifdef AH_DEBUG_OPTIM + +#define LOG( x ) optim_log ## x + +#else + +#define LOG( x ) + +#endif /* AH_DEBUG_OPTIM */ + + +#ifdef AH_DEBUG_OPTIM + +#include <stdarg.h> +#include <stdlib.h> + +#define FLOAT( x ) ( (float)( (x) / 64.0 ) ) + + + static void + optim_log( const char* fmt, ... ) + { + va_list ap; + + + va_start( ap, fmt ); + vprintf( fmt, ap ); + va_end( ap ); + } + + + static void + AH_Dump_Stems( AH_Optimizer* optimizer ) + { + int n; + AH_Stem* stem; + + + stem = optimizer->stems; + for ( n = 0; n < optimizer->num_stems; n++, stem++ ) + { + LOG(( " %c%2d [%.1f:%.1f]={%.1f:%.1f}=" + "<%1.f..%1.f> force=%.1f speed=%.1f\n", + optimizer->vertical ? 'V' : 'H', n, + FLOAT( stem->edge1->opos ), FLOAT( stem->edge2->opos ), + FLOAT( stem->edge1->pos ), FLOAT( stem->edge2->pos ), + FLOAT( stem->min_pos ), FLOAT( stem->max_pos ), + FLOAT( stem->force ), FLOAT( stem->velocity ) )); + } + } + + + static void + AH_Dump_Stems2( AH_Optimizer* optimizer ) + { + int n; + AH_Stem* stem; + + + stem = optimizer->stems; + for ( n = 0; n < optimizer->num_stems; n++, stem++ ) + { + LOG(( " %c%2d [%.1f]=<%1.f..%1.f> force=%.1f speed=%.1f\n", + optimizer->vertical ? 'V' : 'H', n, + FLOAT( stem->pos ), + FLOAT( stem->min_pos ), FLOAT( stem->max_pos ), + FLOAT( stem->force ), FLOAT( stem->velocity ) )); + } + } + + + static void + AH_Dump_Springs( AH_Optimizer* optimizer ) + { + int n; + AH_Spring* spring; + AH_Stem* stems; + + + spring = optimizer->springs; + stems = optimizer->stems; + LOG(( "%cSprings ", optimizer->vertical ? 'V' : 'H' )); + + for ( n = 0; n < optimizer->num_springs; n++, spring++ ) + { + LOG(( " [%d-%d:%.1f:%1.f:%.1f]", + spring->stem1 - stems, spring->stem2 - stems, + FLOAT( spring->owidth ), + FLOAT( spring->stem2->pos - + ( spring->stem1->pos + spring->stem1->width ) ), + FLOAT( spring->tension ) )); + } + + LOG(( "\n" )); + } + +#endif /* AH_DEBUG_OPTIM */ + + + /*************************************************************************/ + /*************************************************************************/ + /*************************************************************************/ + /**** ****/ + /**** COMPUTE STEMS AND SPRINGS IN AN OUTLINE ****/ + /**** ****/ + /*************************************************************************/ + /*************************************************************************/ + /*************************************************************************/ + + + static int + valid_stem_segments( AH_Segment seg1, + AH_Segment seg2 ) + { + return seg1->serif == 0 && + seg2 && + seg2->link == seg1 && + seg1->pos < seg2->pos && + seg1->min_coord <= seg2->max_coord && + seg2->min_coord <= seg1->max_coord; + } + + + /* compute all stems in an outline */ + static int + optim_compute_stems( AH_Optimizer* optimizer ) + { + AH_Outline outline = optimizer->outline; + FT_Fixed scale; + FT_Memory memory = optimizer->memory; + FT_Error error = 0; + FT_Int dimension; + AH_Edge edges; + AH_Edge edge_limit; + AH_Stem** p_stems; + FT_Int* p_num_stems; + + + edges = outline->horz_edges; + edge_limit = edges + outline->num_hedges; + scale = outline->y_scale; + + p_stems = &optimizer->horz_stems; + p_num_stems = &optimizer->num_hstems; + + for ( dimension = 1; dimension >= 0; dimension-- ) + { + AH_Stem* stems = 0; + FT_Int num_stems = 0; + AH_Edge edge; + + + /* first of all, count the number of stems in this direction */ + for ( edge = edges; edge < edge_limit; edge++ ) + { + AH_Segment seg = edge->first; + + + do + { + if (valid_stem_segments( seg, seg->link ) ) + num_stems++; + + seg = seg->edge_next; + + } while ( seg != edge->first ); + } + + /* now allocate the stems and build their table */ + if ( num_stems > 0 ) + { + AH_Stem* stem; + + + if ( FT_NEW_ARRAY( stems, num_stems ) ) + goto Exit; + + stem = stems; + for ( edge = edges; edge < edge_limit; edge++ ) + { + AH_Segment seg = edge->first; + AH_Segment seg2; + + + do + { + seg2 = seg->link; + if ( valid_stem_segments( seg, seg2 ) ) + { + AH_Edge edge1 = seg->edge; + AH_Edge edge2 = seg2->edge; + + + stem->edge1 = edge1; + stem->edge2 = edge2; + stem->opos = edge1->opos; + stem->pos = edge1->pos; + stem->owidth = edge2->opos - edge1->opos; + stem->width = edge2->pos - edge1->pos; + + /* compute min_coord and max_coord */ + { + FT_Pos min_coord = seg->min_coord; + FT_Pos max_coord = seg->max_coord; + + + if ( seg2->min_coord > min_coord ) + min_coord = seg2->min_coord; + + if ( seg2->max_coord < max_coord ) + max_coord = seg2->max_coord; + + stem->min_coord = min_coord; + stem->max_coord = max_coord; + } + + /* compute minimum and maximum positions for stem -- */ + /* note that the left-most/bottom-most stem has always */ + /* a fixed position */ + if ( stem == stems || edge1->blue_edge || edge2->blue_edge ) + { + /* this stem cannot move; it is snapped to a blue edge */ + stem->min_pos = stem->pos; + stem->max_pos = stem->pos; + } + else + { + /* this edge can move; compute its min and max positions */ + FT_Pos pos1 = stem->opos; + FT_Pos pos2 = pos1 + stem->owidth - stem->width; + FT_Pos min1 = pos1 & -64; + FT_Pos min2 = pos2 & -64; + + + stem->min_pos = min1; + stem->max_pos = min1 + 64; + if ( min2 < min1 ) + stem->min_pos = min2; + else + stem->max_pos = min2 + 64; + + /* XXX: just to see what it does */ + stem->max_pos += 64; + + /* just for the case where direct hinting did some */ + /* incredible things (e.g. blue edge shifts) */ + if ( stem->min_pos > stem->pos ) + stem->min_pos = stem->pos; + + if ( stem->max_pos < stem->pos ) + stem->max_pos = stem->pos; + } + + stem->velocity = 0; + stem->force = 0; + + stem++; + } + seg = seg->edge_next; + + } while ( seg != edge->first ); + } + } + + *p_stems = stems; + *p_num_stems = num_stems; + + edges = outline->vert_edges; + edge_limit = edges + outline->num_vedges; + scale = outline->x_scale; + + p_stems = &optimizer->vert_stems; + p_num_stems = &optimizer->num_vstems; + } + + Exit: + +#ifdef AH_DEBUG_OPTIM + AH_Dump_Stems( optimizer ); +#endif + + return error; + } + + + /* returns the spring area between two stems, 0 if none */ + static FT_Pos + stem_spring_area( AH_Stem* stem1, + AH_Stem* stem2 ) + { + FT_Pos area1 = stem1->max_coord - stem1->min_coord; + FT_Pos area2 = stem2->max_coord - stem2->min_coord; + FT_Pos min = stem1->min_coord; + FT_Pos max = stem1->max_coord; + FT_Pos area; + + + /* order stems */ + if ( stem2->opos <= stem1->opos + stem1->owidth ) + return 0; + + if ( min < stem2->min_coord ) + min = stem2->min_coord; + + if ( max < stem2->max_coord ) + max = stem2->max_coord; + + area = ( max-min ); + if ( 2 * area < area1 && 2 * area < area2 ) + area = 0; + + return area; + } + + + /* compute all springs in an outline */ + static int + optim_compute_springs( AH_Optimizer* optimizer ) + { + /* basically, a spring exists between two stems if most of their */ + /* surface is aligned */ + FT_Memory memory = optimizer->memory; + + AH_Stem* stems; + AH_Stem* stem_limit; + AH_Stem* stem; + int dimension; + int error = 0; + + FT_Int* p_num_springs; + AH_Spring** p_springs; + + + stems = optimizer->horz_stems; + stem_limit = stems + optimizer->num_hstems; + + p_springs = &optimizer->horz_springs; + p_num_springs = &optimizer->num_hsprings; + + for ( dimension = 1; dimension >= 0; dimension-- ) + { + FT_Int num_springs = 0; + AH_Spring* springs = 0; + + + /* first of all, count stem springs */ + for ( stem = stems; stem + 1 < stem_limit; stem++ ) + { + AH_Stem* stem2; + + + for ( stem2 = stem+1; stem2 < stem_limit; stem2++ ) + if ( stem_spring_area( stem, stem2 ) ) + num_springs++; + } + + /* then allocate and build the springs table */ + if ( num_springs > 0 ) + { + AH_Spring* spring; + + + /* allocate table of springs */ + if ( FT_NEW_ARRAY( springs, num_springs ) ) + goto Exit; + + /* fill the springs table */ + spring = springs; + for ( stem = stems; stem+1 < stem_limit; stem++ ) + { + AH_Stem* stem2; + FT_Pos area; + + + for ( stem2 = stem + 1; stem2 < stem_limit; stem2++ ) + { + area = stem_spring_area( stem, stem2 ); + if ( area ) + { + /* add a new spring here */ + spring->stem1 = stem; + spring->stem2 = stem2; + spring->owidth = stem2->opos - ( stem->opos + stem->owidth ); + spring->tension = 0; + + spring++; + } + } + } + } + *p_num_springs = num_springs; + *p_springs = springs; + + stems = optimizer->vert_stems; + stem_limit = stems + optimizer->num_vstems; + + p_springs = &optimizer->vert_springs; + p_num_springs = &optimizer->num_vsprings; + } + + Exit: + +#ifdef AH_DEBUG_OPTIM + AH_Dump_Springs( optimizer ); +#endif + + return error; + } + + + /*************************************************************************/ + /*************************************************************************/ + /*************************************************************************/ + /**** ****/ + /**** OPTIMIZE THROUGH MY STRANGE SIMULATED ANNEALING ALGO ;-) ****/ + /**** ****/ + /*************************************************************************/ + /*************************************************************************/ + /*************************************************************************/ + +#ifndef AH_BRUTE_FORCE + + /* compute all spring tensions */ + static void + optim_compute_tensions( AH_Optimizer* optimizer ) + { + AH_Spring* spring = optimizer->springs; + AH_Spring* limit = spring + optimizer->num_springs; + + + for ( ; spring < limit; spring++ ) + { + AH_Stem* stem1 = spring->stem1; + AH_Stem* stem2 = spring->stem2; + FT_Int status; + + FT_Pos width; + FT_Pos tension; + FT_Pos sign; + + + /* compute the tension; it simply is -K*(new_width-old_width) */ + width = stem2->pos - ( stem1->pos + stem1->width ); + tension = width - spring->owidth; + + sign = 1; + if ( tension < 0 ) + { + sign = -1; + tension = -tension; + } + + if ( width <= 0 ) + tension = 32000; + else + tension = ( tension << 10 ) / width; + + tension = -sign * FT_MulFix( tension, optimizer->tension_scale ); + spring->tension = tension; + + /* now, distribute tension among the englobing stems, if they */ + /* are able to move */ + status = 0; + if ( stem1->pos <= stem1->min_pos ) + status |= 1; + if ( stem2->pos >= stem2->max_pos ) + status |= 2; + + if ( !status ) + tension /= 2; + + if ( ( status & 1 ) == 0 ) + stem1->force -= tension; + + if ( ( status & 2 ) == 0 ) + stem2->force += tension; + } + } + + + /* compute all stem movements -- returns 0 if nothing moved */ + static int + optim_compute_stem_movements( AH_Optimizer* optimizer ) + { + AH_Stem* stems = optimizer->stems; + AH_Stem* limit = stems + optimizer->num_stems; + AH_Stem* stem = stems; + int moved = 0; + + + /* set initial forces to velocity */ + for ( stem = stems; stem < limit; stem++ ) + { + stem->force = stem->velocity; + stem->velocity /= 2; /* XXX: Heuristics */ + } + + /* compute the sum of forces applied on each stem */ + optim_compute_tensions( optimizer ); + +#ifdef AH_DEBUG_OPTIM + AH_Dump_Springs( optimizer ); + AH_Dump_Stems2( optimizer ); +#endif + + /* now, see whether something can move */ + for ( stem = stems; stem < limit; stem++ ) + { + if ( stem->force > optimizer->tension_threshold ) + { + /* there is enough tension to move the stem to the right */ + if ( stem->pos < stem->max_pos ) + { + stem->pos += 64; + stem->velocity = stem->force / 2; + moved = 1; + } + else + stem->velocity = 0; + } + else if ( stem->force < optimizer->tension_threshold ) + { + /* there is enough tension to move the stem to the left */ + if ( stem->pos > stem->min_pos ) + { + stem->pos -= 64; + stem->velocity = stem->force / 2; + moved = 1; + } + else + stem->velocity = 0; + } + } + + /* return 0 if nothing moved */ + return moved; + } + +#endif /* AH_BRUTE_FORCE */ + + + /* compute current global distortion from springs */ + static FT_Pos + optim_compute_distortion( AH_Optimizer* optimizer ) + { + AH_Spring* spring = optimizer->springs; + AH_Spring* limit = spring + optimizer->num_springs; + FT_Pos distortion = 0; + + + for ( ; spring < limit; spring++ ) + { + AH_Stem* stem1 = spring->stem1; + AH_Stem* stem2 = spring->stem2; + FT_Pos width; + + width = stem2->pos - ( stem1->pos + stem1->width ); + width -= spring->owidth; + if ( width < 0 ) + width = -width; + + distortion += width; + } + + return distortion; + } + + + /* record stems configuration in `best of' history */ + static void + optim_record_configuration( AH_Optimizer* optimizer ) + { + FT_Pos distortion; + AH_Configuration* configs = optimizer->configs; + AH_Configuration* limit = configs + optimizer->num_configs; + AH_Configuration* config; + + + distortion = optim_compute_distortion( optimizer ); + LOG(( "config distortion = %.1f ", FLOAT( distortion * 64 ) )); + + /* check that we really need to add this configuration to our */ + /* sorted history */ + if ( limit > configs && limit[-1].distortion < distortion ) + { + LOG(( "ejected\n" )); + return; + } + + /* add new configuration at the end of the table */ + { + int n; + + + config = limit; + if ( optimizer->num_configs < AH_MAX_CONFIGS ) + optimizer->num_configs++; + else + config--; + + config->distortion = distortion; + + for ( n = 0; n < optimizer->num_stems; n++ ) + config->positions[n] = optimizer->stems[n].pos; + } + + /* move the current configuration towards the front of the list */ + /* when necessary -- yes this is slow bubble sort ;-) */ + while ( config > configs && config[0].distortion < config[-1].distortion ) + { + AH_Configuration temp; + + + config--; + temp = config[0]; + config[0] = config[1]; + config[1] = temp; + } + LOG(( "recorded!\n" )); + } + + +#ifdef AH_BRUTE_FORCE + + /* optimize outline in a single direction */ + static void + optim_compute( AH_Optimizer* optimizer ) + { + int n; + FT_Bool moved; + + AH_Stem* stem = optimizer->stems; + AH_Stem* limit = stem + optimizer->num_stems; + + + /* empty, exit */ + if ( stem >= limit ) + return; + + optimizer->num_configs = 0; + + stem = optimizer->stems; + for ( ; stem < limit; stem++ ) + stem->pos = stem->min_pos; + + do + { + /* record current configuration */ + optim_record_configuration( optimizer ); + + /* now change configuration */ + moved = 0; + for ( stem = optimizer->stems; stem < limit; stem++ ) + { + if ( stem->pos < stem->max_pos ) + { + stem->pos += 64; + moved = 1; + break; + } + + stem->pos = stem->min_pos; + } + } while ( moved ); + + /* now, set the best stem positions */ + for ( n = 0; n < optimizer->num_stems; n++ ) + { + AH_Stem* stem = optimizer->stems + n; + FT_Pos pos = optimizer->configs[0].positions[n]; + + + stem->edge1->pos = pos; + stem->edge2->pos = pos + stem->width; + + stem->edge1->flags |= AH_EDGE_DONE; + stem->edge2->flags |= AH_EDGE_DONE; + } + } + +#else /* AH_BRUTE_FORCE */ + + /* optimize outline in a single direction */ + static void + optim_compute( AH_Optimizer* optimizer ) + { + int n, counter, counter2; + + + optimizer->num_configs = 0; + optimizer->tension_scale = 0x80000L; + optimizer->tension_threshold = 64; + + /* record initial configuration threshold */ + optim_record_configuration( optimizer ); + + counter = 0; + for ( counter2 = optimizer->num_stems*8; counter2 >= 0; counter2-- ) + { + if ( counter == 0 ) + counter = 2 * optimizer->num_stems; + + if ( !optim_compute_stem_movements( optimizer ) ) + break; + + optim_record_configuration( optimizer ); + + counter--; + if ( counter == 0 ) + optimizer->tension_scale /= 2; + } + + /* now, set the best stem positions */ + for ( n = 0; n < optimizer->num_stems; n++ ) + { + AH_Stem* stem = optimizer->stems + n; + FT_Pos pos = optimizer->configs[0].positions[n]; + + + stem->edge1->pos = pos; + stem->edge2->pos = pos + stem->width; + + stem->edge1->flags |= AH_EDGE_DONE; + stem->edge2->flags |= AH_EDGE_DONE; + } + } + +#endif /* AH_BRUTE_FORCE */ + + + /*************************************************************************/ + /*************************************************************************/ + /*************************************************************************/ + /**** ****/ + /**** HIGH-LEVEL OPTIMIZER API ****/ + /**** ****/ + /*************************************************************************/ + /*************************************************************************/ + /*************************************************************************/ + + + /* releases the optimization data */ + void + AH_Optimizer_Done( AH_Optimizer* optimizer ) + { + if ( optimizer ) + { + FT_Memory memory = optimizer->memory; + + + FT_FREE( optimizer->horz_stems ); + FT_FREE( optimizer->vert_stems ); + FT_FREE( optimizer->horz_springs ); + FT_FREE( optimizer->vert_springs ); + FT_FREE( optimizer->positions ); + } + } + + + /* loads the outline into the optimizer */ + int + AH_Optimizer_Init( AH_Optimizer* optimizer, + AH_Outline outline, + FT_Memory memory ) + { + FT_Error error; + + + FT_MEM_ZERO( optimizer, sizeof ( *optimizer ) ); + optimizer->outline = outline; + optimizer->memory = memory; + + LOG(( "initializing new optimizer\n" )); + /* compute stems and springs */ + error = optim_compute_stems ( optimizer ) || + optim_compute_springs( optimizer ); + if ( error ) + goto Fail; + + /* allocate stem positions history and configurations */ + { + int n, max_stems; + + + max_stems = optimizer->num_hstems; + if ( max_stems < optimizer->num_vstems ) + max_stems = optimizer->num_vstems; + + if ( FT_NEW_ARRAY( optimizer->positions, max_stems * AH_MAX_CONFIGS ) ) + goto Fail; + + optimizer->num_configs = 0; + for ( n = 0; n < AH_MAX_CONFIGS; n++ ) + optimizer->configs[n].positions = optimizer->positions + + n * max_stems; + } + + return error; + + Fail: + AH_Optimizer_Done( optimizer ); + return error; + } + + + /* compute optimal outline */ + void + AH_Optimizer_Compute( AH_Optimizer* optimizer ) + { + optimizer->num_stems = optimizer->num_hstems; + optimizer->stems = optimizer->horz_stems; + optimizer->num_springs = optimizer->num_hsprings; + optimizer->springs = optimizer->horz_springs; + + if ( optimizer->num_springs > 0 ) + { + LOG(( "horizontal optimization ------------------------\n" )); + optim_compute( optimizer ); + } + + optimizer->num_stems = optimizer->num_vstems; + optimizer->stems = optimizer->vert_stems; + optimizer->num_springs = optimizer->num_vsprings; + optimizer->springs = optimizer->vert_springs; + + if ( optimizer->num_springs ) + { + LOG(( "vertical optimization --------------------------\n" )); + optim_compute( optimizer ); + } + } + + +/* END */ |
