ref: 8a94b1efd6cfe76ffbd66e9315542c9438a34722
parent: 71f53e122b83cbe3033f47a2f283d207492c87b0
author: Werner Lemberg <[email protected]>
date: Sat Apr 12 16:44:33 EDT 2014
[autofit] Redesign the recognition algorithm of strong points.
In particular, local extrema without horizontal or vertical segments
are better recognized:
+ A + D
\ /
\ /
\ /
\ /
\ + C
\ /
B +/
If the distances AB and CD are large, point B wasn't previously
detected as an extremum since the `ft_corner_is_flat' function
`swallowed' BC regardless of its direction, tagging point B as weak.
The next iteration started at B and made `ft_corner_is_flat' swallow
point C, tagging it as weak also, et voilà.
To improve that, another pass gets now performed before calling
`ft_corner_is_flat' to improve the `topology' of an outline: A
sequence of non-horizontal or non-vertical vectors that point into
the same quadrant are handled as a single, large vector.
Additionally, distances of near points are now accumulated, which
makes the auto-hinter handle them as if they were prepended to the
next non-near vector.
This generally improves the auto-hinter's rendering results.
* src/autofit/afhints.c (af_glyph_hints_reload): Implement it.
* src/autofit/afhints.h (AF_FLAGS): Remove no longer used flag
`AF_FLAG_NEAR'.
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,41 @@
+2014-04-12 Werner Lemberg <[email protected]>
+
+ [autofit] Redesign the recognition algorithm of strong points.
+
+ In particular, local extrema without horizontal or vertical segments
+ are better recognized:
+
+ + A + D
+ \ /
+ \ /
+ \ /
+ \ /
+ \ + C
+ \ /
+ B +/
+
+ If the distances AB and CD are large, point B wasn't previously
+ detected as an extremum since the `ft_corner_is_flat' function
+ `swallowed' BC regardless of its direction, tagging point B as weak.
+ The next iteration started at B and made `ft_corner_is_flat' swallow
+ point C, tagging it as weak also, et voilà.
+
+ To improve that, another pass gets now performed before calling
+ `ft_corner_is_flat' to improve the `topology' of an outline: A
+ sequence of non-horizontal or non-vertical vectors that point into
+ the same quadrant are handled as a single, large vector.
+
+ Additionally, distances of near points are now accumulated, which
+ makes the auto-hinter handle them as if they were prepended to the
+ next non-near vector.
+
+ This generally improves the auto-hinter's rendering results.
+
+ * src/autofit/afhints.c (af_glyph_hints_reload): Implement it.
+
+ * src/autofit/afhints.h (AF_FLAGS): Remove no longer used flag
+ `AF_FLAG_NEAR'.
+
2014-04-05 Werner Lemberg <[email protected]>
[autofit] Improve scoring algorithm for identifying stems.
--- a/src/autofit/afhints.c
+++ b/src/autofit/afhints.c
@@ -698,92 +698,166 @@
}
}
- /* compute directions of in & out vectors */
{- AF_Point first = points;
- AF_Point prev = NULL;
- FT_Pos in_x = 0;
- FT_Pos in_y = 0;
- AF_Direction in_dir = AF_DIR_NONE;
+ /*
+ * Compute directions of `in' and `out' vectors.
+ *
+ * Note that distances between points that are very near to each
+ * other are accumulated. In other words, the auto-hinter
+ * prepends the small vectors between near points to the first
+ * non-near vector. All intermediate points are tagged as
+ * weak; the directions are adjusted also to be equal to the
+ * accumulated one.
+ */
- FT_Pos last_good_in_x = 0;
- FT_Pos last_good_in_y = 0;
-
+ /* value 20 in `near_limit' is heuristic */
FT_UInt units_per_em = hints->metrics->scaler.face->units_per_EM;
FT_Int near_limit = 20 * units_per_em / 2048;
+ AF_Point* contour;
+ AF_Point* contour_limit = hints->contours + hints->num_contours;
- for ( point = points; point < point_limit; point++ )
+
+ for ( contour = hints->contours; contour < contour_limit; contour++ )
{- AF_Point next;
- FT_Pos out_x, out_y;
+ AF_Point first = *contour;
+ AF_Point next, prev, curr;
+ FT_Pos out_x, out_y;
- if ( point == first )
+ FT_Bool is_first;
+
+
+ /* since the first point of a contour could be part of a */
+ /* series of near points, go backwards to find the first */
+ /* non-near point and adjust `first' */
+
+ point = first;
+ prev = first->prev;
+
+ while ( prev != first )
{- prev = first->prev;
+ out_x = point->fx - prev->fx;
+ out_y = point->fy - prev->fy;
- in_x = first->fx - prev->fx;
- in_y = first->fy - prev->fy;
+ /* we use Taxicab metrics to measure the vector length */
+ if ( FT_ABS( out_x ) + FT_ABS( out_y ) >= near_limit )
+ break;
- last_good_in_x = in_x;
- last_good_in_y = in_y;
+ point = prev;
+ prev = prev->prev;
+ }
- if ( FT_ABS( in_x ) + FT_ABS( in_y ) < near_limit )
- {- /* search first non-near point to get a good `in_dir' value */
+ /* adjust first point */
+ first = point;
- AF_Point point_ = prev;
+ /* now loop over all points of the contour to get */
+ /* `in' and `out' vector directions */
+ curr = first;
+ out_x = 0;
+ out_y = 0;
- while ( point_ != first )
- {- AF_Point prev_ = point_->prev;
+ is_first = 1;
- FT_Pos in_x_ = point_->fx - prev_->fx;
- FT_Pos in_y_ = point_->fy - prev_->fy;
+ for ( point = first;
+ point != first || is_first;
+ point = point->next )
+ {+ AF_Direction out_dir;
- if ( FT_ABS( in_x_ ) + FT_ABS( in_y_ ) >= near_limit )
- {- last_good_in_x = in_x_;
- last_good_in_y = in_y_;
+ is_first = 0;
- break;
- }
+ next = point->next;
- point_ = prev_;
- }
+ out_x += next->fx - point->fx;
+ out_y += next->fy - point->fy;
+
+ if ( FT_ABS( out_x ) + FT_ABS( out_y ) < near_limit )
+ {+ next->flags |= AF_FLAG_WEAK_INTERPOLATION;
+ continue;
}
- in_dir = af_direction_compute( in_x, in_y );
- first = prev + 1;
+ /* we abuse the `u' and `v' fields to store index deltas */
+ /* to the next and previous non-near point, respectively */
+ curr->u = (FT_Pos)( next - curr );
+ next->v = -curr->u;
+
+ out_dir = af_direction_compute( out_x, out_y );
+
+ /* adjust directions for all points inbetween; */
+ /* the loop also updates position of `curr' */
+ curr->out_dir = (FT_Char)out_dir;
+ for ( curr = curr->next; curr != next; curr = curr->next )
+ {+ curr->in_dir = (FT_Char)out_dir;
+ curr->out_dir = (FT_Char)out_dir;
+ }
+ next->in_dir = (FT_Char)out_dir;
+
+ out_x = 0;
+ out_y = 0;
}
+ }
- point->in_dir = (FT_Char)in_dir;
+ /*
+ * The next step is to `simplify' an outline's topology so that we
+ * can identify local extrema more reliably: A series of
+ * non-horizontal or non-vertical vectors pointing into the same
+ * quadrant are handled as a single, long vector. From a
+ * topological point of the view, the intermediate points are of no
+ * interest and thus tagged as weak.
+ */
- /* check whether the current point is near to the previous one */
- /* (value 20 in `near_limit' is heuristic; we use Taxicab */
- /* metrics for the test) */
+ for ( point = points; point < point_limit; point++ )
+ {+ if ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
+ continue;
- if ( FT_ABS( in_x ) + FT_ABS( in_y ) < near_limit )
- point->flags |= AF_FLAG_NEAR;
- else
+ if ( point->in_dir == AF_DIR_NONE &&
+ point->out_dir == AF_DIR_NONE )
{- last_good_in_x = in_x;
- last_good_in_y = in_y;
- }
+ /* check whether both vectors point into the same quadrant */
- next = point->next;
- out_x = next->fx - point->fx;
- out_y = next->fy - point->fy;
+ FT_Pos in_x, in_y;
+ FT_Pos out_x, out_y;
- in_dir = af_direction_compute( out_x, out_y );
- point->out_dir = (FT_Char)in_dir;
+ AF_Point next_u = point + point->u;
+ AF_Point prev_v = point + point->v;
- /* Check for weak points. The remaining points not collected */
- /* in edges are then implicitly classified as strong points. */
+ in_x = point->fx - prev_v->fx;
+ in_y = point->fy - prev_v->fy;
+
+ out_x = next_u->fx - point->fx;
+ out_y = next_u->fy - point->fy;
+
+ if ( ( in_x ^ out_x ) >= 0 && ( in_y ^ out_y ) >= 0 )
+ {+ /* yes, so tag current point as weak */
+ /* and update index deltas */
+
+ point->flags |= AF_FLAG_WEAK_INTERPOLATION;
+
+ prev_v->u = (FT_Pos)( next_u - prev_v );
+ next_u->v = -prev_v->u;
+ }
+ }
+ }
+
+ /*
+ * Finally, check for remaining weak points. Everything else not
+ * collected in edges so far is then implicitly classified as strong
+ * points.
+ */
+
+ for ( point = points; point < point_limit; point++ )
+ {+ if ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
+ continue;
+
if ( point->flags & AF_FLAG_CONTROL )
{/* control points are always weak */
@@ -799,18 +873,25 @@
goto Is_Weak_Point;
}
- /* test whether `in' and `out' direction is approximately */
- /* the same (and use the last good `in' vector in case */
- /* the current point is near to the previous one) */
- if ( ft_corner_is_flat(
- point->flags & AF_FLAG_NEAR ? last_good_in_x : in_x,
- point->flags & AF_FLAG_NEAR ? last_good_in_y : in_y,
- out_x,
- out_y ) )
{- /* current point lies on a straight, diagonal line */
- /* (more or less) */
- goto Is_Weak_Point;
+ AF_Point next_u = point + point->u;
+ AF_Point prev_v = point + point->v;
+
+
+ if ( ft_corner_is_flat( point->fx - prev_v->fx,
+ point->fy - prev_v->fy,
+ next_u->fx - point->fx,
+ next_u->fy - point->fy ) )
+ {+ /* either the `in' or the `out' vector is much more */
+ /* dominant than the other one, so tag current point */
+ /* as weak and update index deltas */
+
+ prev_v->u = (FT_Pos)( next_u - prev_v );
+ next_u->v = -prev_v->u;
+
+ goto Is_Weak_Point;
+ }
}
}
else if ( point->in_dir == -point->out_dir )
@@ -818,9 +899,6 @@
/* current point forms a spike */
goto Is_Weak_Point;
}
-
- in_x = out_x;
- in_y = out_y;
}
}
}
--- a/src/autofit/afhints.h
+++ b/src/autofit/afhints.h
@@ -4,7 +4,7 @@
/* */
/* Auto-fitter hinting routines (specification). */
/* */
-/* Copyright 2003-2008, 2010-2012 by */
+/* Copyright 2003-2008, 2010-2012, 2014 by */
/* David Turner, Robert Wilhelm, and Werner Lemberg. */
/* */
/* This file is part of the FreeType project, and may only be used, */
@@ -236,10 +236,7 @@
AF_FLAG_WEAK_INTERPOLATION = 1 << 8,
/* all inflection points in the outline have this flag set */
- AF_FLAG_INFLECTION = 1 << 9,
-
- /* the current point is very near to another one */
- AF_FLAG_NEAR = 1 << 10
+ AF_FLAG_INFLECTION = 1 << 9
} AF_Flags;