X-Git-Url: https://git.octo.it/?p=rrdtool.git;a=blobdiff_plain;f=libraries%2Ffreetype-2.0.5%2Fahoptim.c;fp=libraries%2Ffreetype-2.0.5%2Fahoptim.c;h=0000000000000000000000000000000000000000;hp=87c9ee5e70c00b16ed133e880d7246325c225cc7;hb=bab0189ee9d56aca8bea909275317ab4e0be09ee;hpb=b837c0527f117b54845242ee7626df6d88394444 diff --git a/libraries/freetype-2.0.5/ahoptim.c b/libraries/freetype-2.0.5/ahoptim.c deleted file mode 100644 index 87c9ee5..0000000 --- a/libraries/freetype-2.0.5/ahoptim.c +++ /dev/null @@ -1,883 +0,0 @@ -/***************************************************************************/ -/* */ -/* ahoptim.c */ -/* */ -/* FreeType auto hinting outline optimization (body). */ -/* */ -/* Copyright 2000-2001 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 -#include FT_INTERNAL_OBJECTS_H /* for ALLOC_ARRAY() and FREE() */ -#include "ahoptim.h" - - - /* define this macro to use brute force optimisation -- 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 -#include -#include - -#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 ( ALLOC_ARRAY( stems, num_stems, AH_Stem ) ) - 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 ( ALLOC_ARRAY( springs, num_springs, AH_Spring ) ) - 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; - - - FREE( optimizer->horz_stems ); - FREE( optimizer->vert_stems ); - FREE( optimizer->horz_springs ); - FREE( optimizer->vert_springs ); - 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; - - - MEM_Set( optimizer, 0, 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 ( ALLOC_ARRAY( optimizer->positions, - max_stems * AH_MAX_CONFIGS, FT_Pos ) ) - 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 */