ref: 89d4e4bd9a4fccd6a40373727ef1f667a3bd8cb2
dir: /src/autohint/ahglyph.c/
/***************************************************************************/ /* */ /* ahglyph.c */ /* */ /* Routines used to load and analyze a given glyph before hinting */ /* (body). */ /* */ /* Copyright 2000-2001, 2002, 2003, 2004 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 <ft2build.h> #include "ahglyph.h" #include "ahangles.h" #include "ahglobal.h" #include "aherrors.h" #ifdef AH_DEBUG #include <stdio.h> void ah_dump_edges( AH_Outline outline ) { AH_Edge edges; AH_Edge edge_limit; AH_Segment segments; FT_Int dimension; edges = outline->horz_edges; edge_limit = edges + outline->num_hedges; segments = outline->horz_segments; for ( dimension = 1; dimension >= 0; dimension-- ) { AH_Edge edge; printf ( "Table of %s edges:\n", !dimension ? "vertical" : "horizontal" ); printf ( " [ index | pos | dir | link |" " serif | blue | opos | pos ]\n" ); for ( edge = edges; edge < edge_limit; edge++ ) { printf ( " [ %5d | %4d | %5s | %4d | %5d | %c | %5.2f | %5.2f ]\n", edge - edges, (int)edge->fpos, edge->dir == AH_DIR_UP ? "up" : ( edge->dir == AH_DIR_DOWN ? "down" : ( edge->dir == AH_DIR_LEFT ? "left" : ( edge->dir == AH_DIR_RIGHT ? "right" : "none" ) ) ), edge->link ? ( edge->link - edges ) : -1, edge->serif ? ( edge->serif - edges ) : -1, edge->blue_edge ? 'y' : 'n', edge->opos / 64.0, edge->pos / 64.0 ); } edges = outline->vert_edges; edge_limit = edges + outline->num_vedges; segments = outline->vert_segments; } } /* A function used to dump the array of linked segments */ void ah_dump_segments( AH_Outline outline ) { AH_Segment segments; AH_Segment segment_limit; AH_Point points; FT_Int dimension; points = outline->points; segments = outline->horz_segments; segment_limit = segments + outline->num_hsegments; for ( dimension = 1; dimension >= 0; dimension-- ) { AH_Segment seg; printf ( "Table of %s segments:\n", !dimension ? "vertical" : "horizontal" ); printf ( " [ index | pos | dir | link | serif |" " numl | first | start ]\n" ); for ( seg = segments; seg < segment_limit; seg++ ) { printf ( " [ %5d | %4d | %5s | %4d | %5d | %4d | %5d | %5d ]\n", seg - segments, (int)seg->pos, seg->dir == AH_DIR_UP ? "up" : ( seg->dir == AH_DIR_DOWN ? "down" : ( seg->dir == AH_DIR_LEFT ? "left" : ( seg->dir == AH_DIR_RIGHT ? "right" : "none" ) ) ), seg->link ? ( seg->link - segments ) : -1, seg->serif ? ( seg->serif - segments ) : -1, (int)seg->num_linked, seg->first - points, seg->last - points ); } segments = outline->vert_segments; segment_limit = segments + outline->num_vsegments; } } #endif /* AH_DEBUG */ /* compute the direction value of a given vector */ static AH_Direction ah_compute_direction( FT_Pos dx, FT_Pos dy ) { AH_Direction dir; FT_Pos ax = FT_ABS( dx ); FT_Pos ay = FT_ABS( dy ); dir = AH_DIR_NONE; /* atan(1/12) == 4.7 degrees */ /* test for vertical direction */ if ( ax * 12 < ay ) { dir = dy > 0 ? AH_DIR_UP : AH_DIR_DOWN; } /* test for horizontal direction */ else if ( ay * 12 < ax ) { dir = dx > 0 ? AH_DIR_RIGHT : AH_DIR_LEFT; } return dir; } /* this function is used by ah_get_orientation (see below) to test */ /* the fill direction of given bbox extremum */ static FT_Int ah_test_extremum( FT_Outline* outline, FT_Int n ) { FT_Vector *prev, *cur, *next; FT_Pos product; FT_Int first, last, c; FT_Int retval; /* we need to compute the `previous' and `next' point */ /* for this extremum; we check whether the extremum */ /* is start or end of a contour and providing */ /* appropriate values if so */ cur = outline->points + n; prev = cur - 1; next = cur + 1; first = 0; for ( c = 0; c < outline->n_contours; c++ ) { last = outline->contours[c]; if ( n == first ) prev = outline->points + last; if ( n == last ) next = outline->points + first; first = last + 1; } /* compute the vectorial product -- since we know that the angle */ /* is <= 180 degrees (otherwise it wouldn't be an extremum) we */ /* can determine the filling orientation if the product is */ /* either positive or negative */ product = FT_MulDiv( cur->x - prev->x, /* in.x */ next->y - cur->y, /* out.y */ 0x40 ) - FT_MulDiv( cur->y - prev->y, /* in.y */ next->x - cur->x, /* out.x */ 0x40 ); retval = 0; if ( product ) retval = product > 0 ? 2 : 1; return retval; } /* Compute the orientation of path filling. It differs between TrueType */ /* and Type1 formats. We could use the `FT_OUTLINE_REVERSE_FILL' flag, */ /* but it is better to re-compute it directly (it seems that this flag */ /* isn't correctly set for some weird composite glyphs currently). */ /* */ /* We do this by computing bounding box points, and computing their */ /* curvature. */ /* */ /* The function returns either 1 or 2. */ /* */ static FT_Int ah_get_orientation( FT_Outline* outline ) { FT_BBox box; FT_Int indices_xMin, indices_yMin, indices_xMax, indices_yMax; FT_Int n, last; indices_xMin = -1; indices_yMin = -1; indices_xMax = -1; indices_yMax = -1; box.xMin = box.yMin = 32767L; box.xMax = box.yMax = -32768L; /* is it empty? */ if ( outline->n_contours < 1 ) return 1; last = outline->contours[outline->n_contours - 1]; for ( n = 0; n <= last; n++ ) { FT_Pos x, y; x = outline->points[n].x; if ( x < box.xMin ) { box.xMin = x; indices_xMin = n; } if ( x > box.xMax ) { box.xMax = x; indices_xMax = n; } y = outline->points[n].y; if ( y < box.yMin ) { box.yMin = y; indices_yMin = n; } if ( y > box.yMax ) { box.yMax = y; indices_yMax = n; } } /* test orientation of the extrema */ n = ah_test_extremum( outline, indices_xMin ); if ( n ) goto Exit; n = ah_test_extremum( outline, indices_yMin ); if ( n ) goto Exit; n = ah_test_extremum( outline, indices_xMax ); if ( n ) goto Exit; n = ah_test_extremum( outline, indices_yMax ); if ( !n ) n = 1; Exit: return n; } /*************************************************************************/ /* */ /* <Function> */ /* ah_outline_new */ /* */ /* <Description> */ /* Creates a new and empty AH_OutlineRec object. */ /* */ FT_LOCAL_DEF( FT_Error ) ah_outline_new( FT_Memory memory, AH_Outline* aoutline ) { FT_Error error; AH_Outline outline; if ( !FT_NEW( outline ) ) { outline->memory = memory; *aoutline = outline; } return error; } /*************************************************************************/ /* */ /* <Function> */ /* ah_outline_done */ /* */ /* <Description> */ /* Destroys a given AH_OutlineRec object. */ /* */ FT_LOCAL_DEF( void ) ah_outline_done( AH_Outline outline ) { FT_Memory memory = outline->memory; FT_FREE( outline->horz_edges ); FT_FREE( outline->horz_segments ); FT_FREE( outline->contours ); FT_FREE( outline->points ); FT_FREE( outline ); } /*************************************************************************/ /* */ /* <Function> */ /* ah_outline_save */ /* */ /* <Description> */ /* Saves the contents of a given AH_OutlineRec object into a face's */ /* glyph slot. */ /* */ FT_LOCAL_DEF( void ) ah_outline_save( AH_Outline outline, AH_Loader gloader ) { AH_Point point = outline->points; AH_Point point_limit = point + outline->num_points; FT_Vector* vec = gloader->current.outline.points; char* tag = gloader->current.outline.tags; /* we assume that the glyph loader has already been checked for storage */ for ( ; point < point_limit; point++, vec++, tag++ ) { vec->x = point->x; vec->y = point->y; if ( point->flags & AH_FLAG_CONIC ) tag[0] = FT_CURVE_TAG_CONIC; else if ( point->flags & AH_FLAG_CUBIC ) tag[0] = FT_CURVE_TAG_CUBIC; else tag[0] = FT_CURVE_TAG_ON; } } /*************************************************************************/ /* */ /* <Function> */ /* ah_outline_load */ /* */ /* <Description> */ /* Loads an unscaled outline from a glyph slot into an AH_OutlineRec */ /* object. */ /* */ FT_LOCAL_DEF( FT_Error ) ah_outline_load( AH_Outline outline, FT_Fixed x_scale, FT_Fixed y_scale, FT_Face face ) { FT_Memory memory = outline->memory; FT_Error error = AH_Err_Ok; FT_Outline* source = &face->glyph->outline; FT_Int num_points = source->n_points; FT_Int num_contours = source->n_contours; AH_Point points; /* check arguments */ if ( !face || !face->size || face->glyph->format != FT_GLYPH_FORMAT_OUTLINE ) return AH_Err_Invalid_Argument; /* first of all, reallocate the contours array if necessary */ if ( num_contours > outline->max_contours ) { FT_Int new_contours = FT_PAD_CEIL( num_contours, 4 ); if ( FT_RENEW_ARRAY( outline->contours, outline->max_contours, new_contours ) ) goto Exit; outline->max_contours = new_contours; } /* then, reallocate the points, segments & edges arrays if needed -- */ /* note that we reserved two additional point positions, used to */ /* hint metrics appropriately */ /* */ if ( num_points + 2 > outline->max_points ) { FT_Int news = FT_PAD_CEIL( num_points + 2, 8 ); FT_Int max = outline->max_points; if ( FT_RENEW_ARRAY( outline->points, max, news ) || FT_RENEW_ARRAY( outline->horz_edges, max * 2, news * 2 ) || FT_RENEW_ARRAY( outline->horz_segments, max * 2, news * 2 ) ) goto Exit; /* readjust some pointers */ outline->vert_edges = outline->horz_edges + news; outline->vert_segments = outline->horz_segments + news; outline->max_points = news; } outline->num_points = num_points; outline->num_contours = num_contours; outline->num_hedges = 0; outline->num_vedges = 0; outline->num_hsegments = 0; outline->num_vsegments = 0; /* We can't rely on the value of `FT_Outline.flags' to know the fill */ /* direction used for a glyph, given that some fonts are broken (e.g. */ /* the Arphic ones). We thus recompute it each time we need to. */ /* */ outline->vert_major_dir = AH_DIR_UP; outline->horz_major_dir = AH_DIR_LEFT; if ( ah_get_orientation( source ) > 1 ) { outline->vert_major_dir = AH_DIR_DOWN; outline->horz_major_dir = AH_DIR_RIGHT; } outline->x_scale = x_scale; outline->y_scale = y_scale; points = outline->points; if ( outline->num_points == 0 ) goto Exit; { /* do one thing at a time -- it is easier to understand, and */ /* the code is clearer */ AH_Point point; AH_Point point_limit = points + outline->num_points; /* compute coordinates */ { FT_Vector* vec = source->points; for ( point = points; point < point_limit; vec++, point++ ) { point->fx = vec->x; point->fy = vec->y; point->ox = point->x = FT_MulFix( vec->x, x_scale ); point->oy = point->y = FT_MulFix( vec->y, y_scale ); point->flags = 0; } } /* compute Bezier flags */ { char* tag = source->tags; for ( point = points; point < point_limit; point++, tag++ ) { switch ( FT_CURVE_TAG( *tag ) ) { case FT_CURVE_TAG_CONIC: point->flags = AH_FLAG_CONIC; break; case FT_CURVE_TAG_CUBIC: point->flags = AH_FLAG_CUBIC; break; default: ; } } } /* compute `next' and `prev' */ { FT_Int contour_index; AH_Point prev; AH_Point first; AH_Point end; contour_index = 0; first = points; end = points + source->contours[0]; prev = end; for ( point = points; point < point_limit; point++ ) { point->prev = prev; if ( point < end ) { point->next = point + 1; prev = point; } else { point->next = first; contour_index++; if ( point + 1 < point_limit ) { end = points + source->contours[contour_index]; first = point + 1; prev = end; } } } } /* set-up the contours array */ { AH_Point* contour = outline->contours; AH_Point* contour_limit = contour + outline->num_contours; short* end = source->contours; short idx = 0; for ( ; contour < contour_limit; contour++, end++ ) { contour[0] = points + idx; idx = (short)( end[0] + 1 ); } } /* compute directions of in & out vectors */ { for ( point = points; point < point_limit; point++ ) { AH_Point prev; AH_Point next; FT_Vector ivec, ovec; prev = point->prev; ivec.x = point->fx - prev->fx; ivec.y = point->fy - prev->fy; point->in_dir = ah_compute_direction( ivec.x, ivec.y ); next = point->next; ovec.x = next->fx - point->fx; ovec.y = next->fy - point->fy; point->out_dir = ah_compute_direction( ovec.x, ovec.y ); #ifndef AH_OPTION_NO_WEAK_INTERPOLATION if ( point->flags & ( AH_FLAG_CONIC | AH_FLAG_CUBIC ) ) { Is_Weak_Point: point->flags |= AH_FLAG_WEAK_INTERPOLATION; } else if ( point->out_dir == point->in_dir ) { AH_Angle angle_in, angle_out, delta; if ( point->out_dir != AH_DIR_NONE ) goto Is_Weak_Point; angle_in = ah_angle( &ivec ); angle_out = ah_angle( &ovec ); delta = angle_in - angle_out; if ( delta > AH_PI ) delta = AH_2PI - delta; if ( delta < 0 ) delta = -delta; if ( delta < 2 ) goto Is_Weak_Point; } else if ( point->in_dir == -point->out_dir ) goto Is_Weak_Point; #endif } } } Exit: return error; } FT_LOCAL_DEF( void ) ah_setup_uv( AH_Outline outline, AH_UV source ) { AH_Point point = outline->points; AH_Point point_limit = point + outline->num_points; switch ( source ) { case AH_UV_FXY: for ( ; point < point_limit; point++ ) { point->u = point->fx; point->v = point->fy; } break; case AH_UV_FYX: for ( ; point < point_limit; point++ ) { point->u = point->fy; point->v = point->fx; } break; case AH_UV_OXY: for ( ; point < point_limit; point++ ) { point->u = point->ox; point->v = point->oy; } break; case AH_UV_OYX: for ( ; point < point_limit; point++ ) { point->u = point->oy; point->v = point->ox; } break; case AH_UV_YX: for ( ; point < point_limit; point++ ) { point->u = point->y; point->v = point->x; } break; case AH_UV_OX: for ( ; point < point_limit; point++ ) { point->u = point->x; point->v = point->ox; } break; case AH_UV_OY: for ( ; point < point_limit; point++ ) { point->u = point->y; point->v = point->oy; } break; default: for ( ; point < point_limit; point++ ) { point->u = point->x; point->v = point->y; } } } /* compute all inflex points in a given glyph */ static void ah_outline_compute_inflections( AH_Outline outline ) { AH_Point* contour = outline->contours; AH_Point* contour_limit = contour + outline->num_contours; /* load original coordinates in (u,v) */ ah_setup_uv( outline, AH_UV_FXY ); /* do each contour separately */ for ( ; contour < contour_limit; contour++ ) { FT_Vector vec; AH_Point point = contour[0]; AH_Point first = point; AH_Point start = point; AH_Point end = point; AH_Point before; AH_Point after; AH_Angle angle_in, angle_seg, angle_out; AH_Angle diff_in, diff_out; FT_Int finished = 0; /* compute first segment in contour */ first = point; start = end = first; do { end = end->next; if ( end == first ) goto Skip; } while ( end->u == first->u && end->v == first->v ); vec.x = end->u - start->u; vec.y = end->v - start->v; angle_seg = ah_angle( &vec ); /* extend the segment start whenever possible */ before = start; do { do { start = before; before = before->prev; if ( before == first ) goto Skip; } while ( before->u == start->u && before->v == start->v ); vec.x = start->u - before->u; vec.y = start->v - before->v; angle_in = ah_angle( &vec ); } while ( angle_in == angle_seg ); first = start; diff_in = ah_angle_diff( angle_in, angle_seg ); /* now, process all segments in the contour */ do { /* first, extend current segment's end whenever possible */ after = end; do { do { end = after; after = after->next; if ( after == first ) finished = 1; } while ( end->u == after->u && end->v == after->v ); vec.x = after->u - end->u; vec.y = after->v - end->v; angle_out = ah_angle( &vec ); } while ( angle_out == angle_seg ); diff_out = ah_angle_diff( angle_seg, angle_out ); if ( ( diff_in ^ diff_out ) < 0 ) { /* diff_in and diff_out have different signs, we have */ /* inflection points here... */ do { start->flags |= AH_FLAG_INFLECTION; start = start->next; } while ( start != end ); start->flags |= AH_FLAG_INFLECTION; } start = end; end = after; angle_seg = angle_out; diff_in = diff_out; } while ( !finished ); Skip: ; } } FT_LOCAL_DEF( void ) ah_outline_compute_segments( AH_Outline outline ) { int dimension; AH_Segment segments; FT_Int* p_num_segments; AH_Direction segment_dir; AH_Direction major_dir; segments = outline->horz_segments; p_num_segments = &outline->num_hsegments; major_dir = AH_DIR_RIGHT; /* This value must be positive! */ segment_dir = major_dir; /* set up (u,v) in each point */ ah_setup_uv( outline, AH_UV_FYX ); for ( dimension = 1; dimension >= 0; dimension-- ) { AH_Point* contour = outline->contours; AH_Point* contour_limit = contour + outline->num_contours; AH_Segment segment = segments; FT_Int num_segments = 0; #ifdef AH_HINT_METRICS AH_Point min_point = 0; AH_Point max_point = 0; FT_Pos min_coord = 32000; FT_Pos max_coord = -32000; #endif /* do each contour separately */ for ( ; contour < contour_limit; contour++ ) { AH_Point point = contour[0]; AH_Point last = point->prev; int on_edge = 0; FT_Pos min_pos = 32000; /* minimum segment pos != min_coord */ FT_Pos max_pos = -32000; /* maximum segment pos != max_coord */ FT_Bool passed; #ifdef AH_HINT_METRICS if ( point->u < min_coord ) { min_coord = point->u; min_point = point; } if ( point->u > max_coord ) { max_coord = point->u; max_point = point; } #endif if ( point == last ) /* skip singletons -- just in case */ continue; if ( FT_ABS( last->out_dir ) == major_dir && FT_ABS( point->out_dir ) == major_dir ) { /* we are already on an edge, try to locate its start */ last = point; for (;;) { point = point->prev; if ( FT_ABS( point->out_dir ) != major_dir ) { point = point->next; break; } if ( point == last ) break; } } last = point; passed = 0; for (;;) { FT_Pos u, v; if ( on_edge ) { u = point->u; if ( u < min_pos ) min_pos = u; if ( u > max_pos ) max_pos = u; if ( point->out_dir != segment_dir || point == last ) { /* we are just leaving an edge; record a new segment! */ segment->last = point; segment->pos = ( min_pos + max_pos ) >> 1; /* a segment is round if either its first or last point */ /* is a control point */ if ( ( segment->first->flags | point->flags ) & AH_FLAG_CONTROL ) segment->flags |= AH_EDGE_ROUND; /* compute segment size */ min_pos = max_pos = point->v; v = segment->first->v; if ( v < min_pos ) min_pos = v; if ( v > max_pos ) max_pos = v; segment->min_coord = min_pos; segment->max_coord = max_pos; on_edge = 0; num_segments++; segment++; /* fallthrough */ } } /* now exit if we are at the start/end point */ if ( point == last ) { if ( passed ) break; passed = 1; } if ( !on_edge && FT_ABS( point->out_dir ) == major_dir ) { /* this is the start of a new segment! */ segment_dir = point->out_dir; /* clear all segment fields */ FT_ZERO( segment ); segment->dir = segment_dir; segment->flags = AH_EDGE_NORMAL; min_pos = max_pos = point->u; segment->first = point; segment->last = point; segment->contour = contour; segment->score = 32000; segment->link = NULL; on_edge = 1; #ifdef AH_HINT_METRICS if ( point == max_point ) max_point = 0; if ( point == min_point ) min_point = 0; #endif } point = point->next; } } /* contours */ #ifdef AH_HINT_METRICS /* we need to ensure that there are edges on the left-most and */ /* right-most points of the glyph in order to hint the metrics; */ /* we do this by inserting fake segments when needed */ if ( dimension == 0 ) { AH_Point point = outline->points; AH_Point point_limit = point + outline->num_points; FT_Pos min_pos = 32000; FT_Pos max_pos = -32000; min_point = 0; max_point = 0; /* compute minimum and maximum points */ for ( ; point < point_limit; point++ ) { FT_Pos x = point->fx; if ( x < min_pos ) { min_pos = x; min_point = point; } if ( x > max_pos ) { max_pos = x; max_point = point; } } /* insert minimum segment */ if ( min_point ) { /* clear all segment fields */ FT_ZERO( segment ); segment->dir = segment_dir; segment->flags = AH_EDGE_NORMAL; segment->first = min_point; segment->last = min_point; segment->pos = min_pos; segment->score = 32000; segment->link = NULL; num_segments++; segment++; } /* insert maximum segment */ if ( max_point ) { /* clear all segment fields */ FT_ZERO( segment ); segment->dir = segment_dir; segment->flags = AH_EDGE_NORMAL; segment->first = max_point; segment->last = max_point; segment->pos = max_pos; segment->score = 32000; segment->link = NULL; num_segments++; segment++; } } #endif /* AH_HINT_METRICS */ *p_num_segments = num_segments; segments = outline->vert_segments; major_dir = AH_DIR_UP; p_num_segments = &outline->num_vsegments; ah_setup_uv( outline, AH_UV_FXY ); } } FT_LOCAL_DEF( void ) ah_outline_link_segments( AH_Outline outline ) { AH_Segment segments; AH_Segment segment_limit; AH_Direction major_dir; int dimension; segments = outline->horz_segments; segment_limit = segments + outline->num_hsegments; major_dir = outline->horz_major_dir; for ( dimension = 1; dimension >= 0; dimension-- ) { AH_Segment seg1; AH_Segment seg2; #if 0 /* now compare each segment to the others */ for ( seg1 = segments; seg1 < segment_limit; seg1++ ) { FT_Pos best_score; AH_Segment best_segment; /* the fake segments are introduced to hint the metrics -- */ /* we must never link them to anything */ if ( seg1->first == seg1->last ) continue; best_segment = seg1->link; if ( best_segment ) best_score = seg1->score; else best_score = +32000; for ( seg2 = segments; seg2 < segment_limit; seg2++ ) if ( seg1 != seg2 && seg1->dir + seg2->dir == 0 ) { FT_Pos pos1 = seg1->pos; FT_Pos pos2 = seg2->pos; FT_Bool is_dir; FT_Bool is_pos; /* check that the segments are correctly oriented and */ /* positioned to form a black distance */ is_dir = (FT_Bool)( seg1->dir == outline->horz_major_dir || seg1->dir == outline->vert_major_dir ); is_pos = (FT_Bool)( pos1 > pos2 ); if ( pos1 == pos2 || !(is_dir ^ is_pos) ) continue; { FT_Pos min = seg1->min_coord; FT_Pos max = seg1->max_coord; FT_Pos len, dist, score; if ( min < seg2->min_coord ) min = seg2->min_coord; if ( max > seg2->max_coord ) max = seg2->max_coord; len = max - min; if ( len >= 8 ) { dist = seg2->pos - seg1->pos; if ( dist < 0 ) dist = -dist; score = dist + 3000 / len; if ( score < best_score ) { best_score = score; best_segment = seg2; } } } } if ( best_segment ) { seg1->link = best_segment; seg1->score = best_score; best_segment->num_linked++; } } #endif /* 0 */ #if 1 /* the following code does the same, but much faster! */ /* now compare each segment to the others */ for ( seg1 = segments; seg1 < segment_limit; seg1++ ) { /* the fake segments are introduced to hint the metrics -- */ /* we must never link them to anything */ if ( seg1->first == seg1->last || seg1->dir != major_dir ) continue; for ( seg2 = segments; seg2 < segment_limit; seg2++ ) if ( seg2 != seg1 && seg1->dir + seg2->dir == 0 ) { FT_Pos pos1 = seg1->pos; FT_Pos pos2 = seg2->pos; FT_Pos dist = pos2 - pos1; if ( dist < 0 ) continue; { FT_Pos min = seg1->min_coord; FT_Pos max = seg1->max_coord; FT_Pos len, score; if ( min < seg2->min_coord ) min = seg2->min_coord; if ( max > seg2->max_coord ) max = seg2->max_coord; len = max - min; if ( len >= 8 ) { score = dist + 3000 / len; if ( score < seg1->score ) { seg1->score = score; seg1->link = seg2; } if ( score < seg2->score ) { seg2->score = score; seg2->link = seg1; } } } } } #endif /* 1 */ /* now, compute the `serif' segments */ for ( seg1 = segments; seg1 < segment_limit; seg1++ ) { seg2 = seg1->link; if ( seg2 ) { seg2->num_linked++; if ( seg2->link != seg1 ) { seg1->link = 0; seg1->serif = seg2->link; } } } segments = outline->vert_segments; segment_limit = segments + outline->num_vsegments; major_dir = outline->vert_major_dir; } } static void ah_outline_compute_edges( AH_Outline outline ) { AH_Edge edges; AH_Segment segments; AH_Segment segment_limit; AH_Direction up_dir; FT_Int* p_num_edges; FT_Int dimension; FT_Fixed scale; FT_Pos edge_distance_threshold; edges = outline->horz_edges; segments = outline->horz_segments; segment_limit = segments + outline->num_hsegments; p_num_edges = &outline->num_hedges; up_dir = AH_DIR_RIGHT; scale = outline->y_scale; for ( dimension = 1; dimension >= 0; dimension-- ) { AH_Edge edge; AH_Edge edge_limit; /* really == edge + num_edges */ AH_Segment seg; /*********************************************************************/ /* */ /* We will begin by generating a sorted table of edges for the */ /* current direction. To do so, we simply scan each segment and try */ /* to find an edge in our table that corresponds to its position. */ /* */ /* If no edge is found, we create and insert a new edge in the */ /* sorted table. Otherwise, we simply add the segment to the edge's */ /* list which will be processed in the second step to compute the */ /* edge's properties. */ /* */ /* Note that the edges table is sorted along the segment/edge */ /* position. */ /* */ /*********************************************************************/ edge_distance_threshold = FT_MulFix( outline->edge_distance_threshold, scale ); if ( edge_distance_threshold > 64 / 4 ) edge_distance_threshold = 64 / 4; edge_distance_threshold = FT_DivFix( edge_distance_threshold, scale ); edge_limit = edges; for ( seg = segments; seg < segment_limit; seg++ ) { AH_Edge found = 0; /* look for an edge corresponding to the segment */ for ( edge = edges; edge < edge_limit; edge++ ) { FT_Pos dist; dist = seg->pos - edge->fpos; if ( dist < 0 ) dist = -dist; if ( dist < edge_distance_threshold ) { found = edge; break; } } if ( !found ) { /* insert a new edge in the list and */ /* sort according to the position */ while ( edge > edges && edge[-1].fpos > seg->pos ) { edge[0] = edge[-1]; edge--; } edge_limit++; /* clear all edge fields */ FT_MEM_ZERO( edge, sizeof ( *edge ) ); /* add the segment to the new edge's list */ edge->first = seg; edge->last = seg; edge->fpos = seg->pos; edge->opos = edge->pos = FT_MulFix( seg->pos, scale ); seg->edge_next = seg; } else { /* if an edge was found, simply add the segment to the edge's */ /* list */ seg->edge_next = edge->first; edge->last->edge_next = seg; edge->last = seg; } } *p_num_edges = (FT_Int)( edge_limit - edges ); /*********************************************************************/ /* */ /* Good, we will now compute each edge's properties according to */ /* segments found on its position. Basically, these are: */ /* */ /* - edge's main direction */ /* - stem edge, serif edge or both (which defaults to stem then) */ /* - rounded edge, straight or both (which defaults to straight) */ /* - link for edge */ /* */ /*********************************************************************/ /* first of all, set the `edge' field in each segment -- this is */ /* required in order to compute edge links */ /* Note that I've tried to remove this loop, setting * the "edge" field of each segment directly in the * code above. For some reason, it slows down execution * speed -- on a Sun. */ for ( edge = edges; edge < edge_limit; edge++ ) { seg = edge->first; if ( seg ) do { seg->edge = edge; seg = seg->edge_next; } while ( seg != edge->first ); } /* now, compute each edge properties */ for ( edge = edges; edge < edge_limit; edge++ ) { FT_Int is_round = 0; /* does it contain round segments? */ FT_Int is_straight = 0; /* does it contain straight segments? */ FT_Pos ups = 0; /* number of upwards segments */ FT_Pos downs = 0; /* number of downwards segments */ seg = edge->first; do { FT_Bool is_serif; /* check for roundness of segment */ if ( seg->flags & AH_EDGE_ROUND ) is_round++; else is_straight++; /* check for segment direction */ if ( seg->dir == up_dir ) ups += seg->max_coord-seg->min_coord; else downs += seg->max_coord-seg->min_coord; /* check for links -- if seg->serif is set, then seg->link must */ /* be ignored */ is_serif = (FT_Bool)( seg->serif && seg->serif->edge != edge ); if ( seg->link || is_serif ) { AH_Edge edge2; AH_Segment seg2; edge2 = edge->link; seg2 = seg->link; if ( is_serif ) { seg2 = seg->serif; edge2 = edge->serif; } if ( edge2 ) { FT_Pos edge_delta; FT_Pos seg_delta; edge_delta = edge->fpos - edge2->fpos; if ( edge_delta < 0 ) edge_delta = -edge_delta; seg_delta = seg->pos - seg2->pos; if ( seg_delta < 0 ) seg_delta = -seg_delta; if ( seg_delta < edge_delta ) edge2 = seg2->edge; } else edge2 = seg2->edge; #ifdef FT_CONFIG_CHESTER_SERIF if ( is_serif ) { edge->serif = edge2; edge2->flags |= AH_EDGE_SERIF; } else edge->link = edge2; #else /* !FT_CONFIG_CHESTER_SERIF */ if ( is_serif ) edge->serif = edge2; else edge->link = edge2; #endif /* !FT_CONFIG_CHESTER_SERIF */ } seg = seg->edge_next; } while ( seg != edge->first ); /* set the round/straight flags */ edge->flags = AH_EDGE_NORMAL; if ( is_round > 0 && is_round >= is_straight ) edge->flags |= AH_EDGE_ROUND; /* set the edge's main direction */ edge->dir = AH_DIR_NONE; if ( ups > downs ) edge->dir = up_dir; else if ( ups < downs ) edge->dir = -up_dir; else if ( ups == downs ) edge->dir = 0; /* both up and down! */ /* gets rid of serifs if link is set */ /* XXX: This gets rid of many unpleasant artefacts! */ /* Example: the `c' in cour.pfa at size 13 */ if ( edge->serif && edge->link ) edge->serif = 0; } edges = outline->vert_edges; segments = outline->vert_segments; segment_limit = segments + outline->num_vsegments; p_num_edges = &outline->num_vedges; up_dir = AH_DIR_UP; scale = outline->x_scale; } } /*************************************************************************/ /* */ /* <Function> */ /* ah_outline_detect_features */ /* */ /* <Description> */ /* Performs feature detection on a given AH_OutlineRec object. */ /* */ FT_LOCAL_DEF( void ) ah_outline_detect_features( AH_Outline outline ) { ah_outline_compute_segments ( outline ); ah_outline_link_segments ( outline ); ah_outline_compute_edges ( outline ); ah_outline_compute_inflections( outline ); } /*************************************************************************/ /* */ /* <Function> */ /* ah_outline_compute_blue_edges */ /* */ /* <Description> */ /* Computes the `blue edges' in a given outline (i.e. those that must */ /* be snapped to a blue zone edge (top or bottom). */ /* */ FT_LOCAL_DEF( void ) ah_outline_compute_blue_edges( AH_Outline outline, AH_Face_Globals face_globals ) { AH_Edge edge = outline->horz_edges; AH_Edge edge_limit = edge + outline->num_hedges; AH_Globals globals = &face_globals->design; FT_Fixed y_scale = outline->y_scale; FT_Bool blue_active[AH_BLUE_MAX]; /* compute which blue zones are active, i.e. have their scaled */ /* size < 3/4 pixels */ { AH_Blue blue; FT_Bool check = 0; for ( blue = AH_BLUE_CAPITAL_TOP; blue < AH_BLUE_MAX; blue++ ) { FT_Pos ref, shoot, dist; ref = globals->blue_refs[blue]; shoot = globals->blue_shoots[blue]; dist = ref - shoot; if ( dist < 0 ) dist = -dist; blue_active[blue] = 0; if ( FT_MulFix( dist, y_scale ) < 48 ) { blue_active[blue] = 1; check = 1; } } /* return immediately if no blue zone is active */ if ( !check ) return; } /* for each horizontal edge search the blue zone which is closest */ for ( ; edge < edge_limit; edge++ ) { AH_Blue blue; FT_Pos* best_blue = 0; FT_Pos best_dist; /* initial threshold */ /* compute the initial threshold as a fraction of the EM size */ best_dist = FT_MulFix( face_globals->face->units_per_EM / 40, y_scale ); #ifdef FT_CONFIG_CHESTER_SMALL_F if ( best_dist > 64 / 2 ) best_dist = 64 / 2; #else if ( best_dist > 64 / 4 ) best_dist = 64 / 4; #endif for ( blue = AH_BLUE_CAPITAL_TOP; blue < AH_BLUE_MAX; blue++ ) { /* if it is a top zone, check for right edges -- if it is a bottom */ /* zone, check for left edges */ /* */ /* of course, that's for TrueType XXX */ FT_Bool is_top_blue = FT_BOOL( AH_IS_TOP_BLUE( blue ) ); FT_Bool is_major_dir = FT_BOOL( edge->dir == outline->horz_major_dir ); if ( !blue_active[blue] ) continue; /* if it is a top zone, the edge must be against the major */ /* direction; if it is a bottom zone, it must be in the major */ /* direction */ if ( is_top_blue ^ is_major_dir ) { FT_Pos dist; FT_Pos* blue_pos = globals->blue_refs + blue; /* first of all, compare it to the reference position */ dist = edge->fpos - *blue_pos; if ( dist < 0 ) dist = -dist; dist = FT_MulFix( dist, y_scale ); if ( dist < best_dist ) { best_dist = dist; best_blue = blue_pos; } /* now, compare it to the overshoot position if the edge is */ /* rounded, and if the edge is over the reference position of a */ /* top zone, or under the reference position of a bottom zone */ if ( edge->flags & AH_EDGE_ROUND && dist != 0 ) { FT_Bool is_under_ref = FT_BOOL( edge->fpos < *blue_pos ); if ( is_top_blue ^ is_under_ref ) { blue_pos = globals->blue_shoots + blue; dist = edge->fpos - *blue_pos; if ( dist < 0 ) dist = -dist; dist = FT_MulFix( dist, y_scale ); if ( dist < best_dist ) { best_dist = dist; best_blue = blue_pos; } } } } } if ( best_blue ) edge->blue_edge = best_blue; } } /*************************************************************************/ /* */ /* <Function> */ /* ah_outline_scale_blue_edges */ /* */ /* <Description> */ /* This function must be called before hinting in order to re-adjust */ /* the contents of the detected edges (basically change the `blue */ /* edge' pointer from `design units' to `scaled ones'). */ /* */ FT_LOCAL_DEF( void ) ah_outline_scale_blue_edges( AH_Outline outline, AH_Face_Globals globals ) { AH_Edge edge = outline->horz_edges; AH_Edge edge_limit = edge + outline->num_hedges; FT_Pos delta; delta = globals->scaled.blue_refs - globals->design.blue_refs; for ( ; edge < edge_limit; edge++ ) { if ( edge->blue_edge ) edge->blue_edge += delta; } } /* END */