ref: a16d7155ec979ab45eb0d69e6bbf630e2b50151b
dir: /src/autohint/ahoptim.c/
/***************************************************************************/
/* */
/* FreeType Auto-Gridder Outline Optimisation */
/* */
/* 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. */
/* */
/* */
/* Copyright 2000: 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 */
/* */
/***************************************************************************/
#include <freetype/internal/ftobjs.h> /* for ALLOC_ARRAY and FREE */
#ifdef FT_FLAT_COMPILE
#include "ahoptim.h"
#else
#include <autohint/ahoptim.h>
#endif
/* 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 BRUTE_FORCE
#define xxxDEBUG_OPTIM
#undef LOG
#ifdef DEBUG_OPTIM
#define LOG(x) optim_log##x
#else
#define LOG(x)
#endif
#ifdef DEBUG_OPTIM
#include <stdarg.h>
#include <stdlib.h>
#include <string.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 );
}
#endif
#ifdef DEBUG_OPTIM
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
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/**** ****/
/**** 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 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 DEBUG_OPTIM
AH_Dump_Springs(optimizer);
#endif
return error;
}
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/**** ****/
/**** OPTIMISE THROUGH MY STRANGE SIMULATED ANNEALING ALGO ;-) ****/
/**** ****/
/**** ****/
/**** ****/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
#ifndef 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; /* XXXX: Heuristics */
}
/* compute the sum of forces applied on each stem */
optim_compute_tensions( optimizer );
#ifdef DEBUG_OPTIM
AH_Dump_Springs( optimizer );
AH_Dump_Stems2( optimizer );
#endif
/* now, see if 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 /* BRUTE_FORCE */
/* compute current global distortion from springs */
static
FT_Pos optim_compute_distorsion( AH_Optimizer* optimizer )
{
AH_Spring* spring = optimizer->springs;
AH_Spring* limit = spring + optimizer->num_springs;
FT_Pos distorsion = 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;
distorsion += width;
}
return distorsion;
}
/* record stems configuration in "best of" history */
static
void optim_record_configuration( AH_Optimizer* optimizer )
{
FT_Pos distorsion;
AH_Configuration* configs = optimizer->configs;
AH_Configuration* limit = configs + optimizer->num_configs;
AH_Configuration* config;
distorsion = optim_compute_distorsion( optimizer );
LOG(( "config distorsion = %.1f ", FLOAT(distorsion*64) ));
/* check that we really need to add this configuration to our */
/* sorted history.. */
if ( limit > configs && limit[-1].distorsion < distorsion )
{
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->distorsion = distorsion;
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].distorsion < config[-1].distorsion )
{
AH_Configuration temp;
config--;
temp = config[0];
config[0] = config[1];
config[1] = temp;
}
LOG(( "recorded !!\n" ));
}
#ifdef 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
/* 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
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/**** ****/
/**** HIGH-LEVEL OPTIMIZER API ****/
/**** ****/
/**** ****/
/**** ****/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/* releases the optimisation 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 optimisation ------------------------\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 optimisation --------------------------\n" ));
optim_compute( optimizer );
}
}