Bug 158573

Created attachment 73283 [details]
Message11

Created attachment 73284 [details]
Message13

<the Problem for " ? ">

Created attachment 73306 [details]
Message9

<the Problem for " ? ">

Seems that it's a bug of freetype embolden function. I can reproduce this issue with FZSongTi as well.

Created attachment 73444 [details]
FZSongTi without embolden.

Created attachment 73445 [details]
FZSongTi with embolden.

Comparing to the previous screenshot, you may see that there are two chars have similiar issue.
The font is not changed.

The issue is not always reproduceable, even for the same font size.

Ok. I found the issue.

See the source code of FT_Outline_Embolden():

  FT_EXPORT_DEF( FT_Error )
  FT_Outline_Embolden( FT_Outline*  outline,
                       FT_Pos       strength )
  {
    FT_Vector*  points;
    FT_Vector   v_prev, v_first, v_next, v_cur;
    FT_Angle    rotate, angle_in, angle_out;
    FT_Int      c, n, first;


    if ( !outline )
      return FT_Err_Invalid_Argument;

    if ( strength == 0 )
      return FT_Err_Ok;

    if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_TRUETYPE )
      rotate = -FT_ANGLE_PI2;
    else
      rotate = FT_ANGLE_PI2;

    points = outline->points;

    first = 0;
    for ( c = 0; c < outline->n_contours; c++ )
    {
      int  last = outline->contours[c];


It calls FT_Outline_Get_Orientation() to get correct rotation angle of embolden vector. But sometimes, FT_Outline_Get_Orientation() returns FT_ORIENTATION_POSTSCRIPT instead of FT_ORIENTATION_TRUETYPE, it's of course wrong for TrueType font.

I'll investigate FT_Outline_Get_Orientation() to see what's wrong in it.

Created attachment 73674 [details]
sazanami-mincho.png

It is also reproducible with "Sazanami Mincho" (??????).

Created attachment 73726 [details]
The patch to fix (hopefully) this issue.

This patch should fix the most cases of this issue. Please try, if it's ok, then please apply.

You can find the testing package with this patch in /work/built/mbuild/magellan-zsu-46/i386/

patch for bug #159166 is also included.

Please try the package, if it's ok then I'll commit the package.

Apparently it doesn't fix the issue for "Sazanami Gothic", I can
still reproduce the problem seen in the screen shot in comment #9.

It's so strange that I can't reproduce this issue with ftview, though it's visible in gucharmap and other gtk applications.

Ok. I know the reason.
The issue shows in comment #9 is caused by hinting. The patch in #10 is correct. But because embolden is down after hinting, after applying hinting, the micro orientation (near the most left points) of some glyphs will be inverted strangely. Because FT_Outline_Get_Orientation() determines the orientation by comparing the angles between the most left point and its previous and next points, when there are two or more points with same minimum x coordinator, and their y coordinators are swapped strangely by hinting, wrong result will be returned.

I just submit the patch with this patch, because it fixes most of the issues.
I'll continue to investigate this strange issue to find out a way.

OK, thank you for your great investigation.

It's a bad idea IMHO to hint glyphs before emboldening.  It should be done
afterwards (using the autohinter) -- something to discuss on the freetype-devel
mailing list...

For the moment I suggest to disable hinting while embolding.

Werner> For the moment I suggest to disable hinting while embolding.

How can this be done?

Hehe, it can't :-)  As I've said, this is something to discuss on
freetype-devel...

I've applied the suggested patch, thanks.

A new fontconfig package has been submitted into STABLE, which turns off hinting when do embolden. It should workaround all rest issues.

Closing this bug as fixed.

Good idea to do that in the fontconfig setup. Thank you!

I have just verified that the problem doesn't occur anymore with the
unpatched freetype 2.2.1, i.e. this bug fix has been properly included
upstream. Thank you!

In

  http://lists.nongnu.org/archive/html/freetype/2006-10/msg00000.html

we got a report that the patch fails if a contour consists of only
off-line points.  The mentioned font (VL-Gothic-Regular) contains a couple
of such glyphs, most notably `zero', `sigma', and `omega'.  The latter
two have weird overlapping contours so it's probably not important to fix.
Anyway, the `zero' shape is a full valid glyph shape, so we have to fix
it...

I improved the algorithm to take into account implicit on-curve points. The  VL-Gothic-Regular font issue should be fixed by this enhancement. However I found that it still can't solve all the issues, for example glyph uni4e31, uni4e38 in font sazanami-mincho.ttf.

It seems that we need a totally different algorithm to solve this issue completely.

Created attachment 101395 [details]
Patch against freetype 2.2.1

It's a patch against freetype 2.2.1, which improves the orientation detection algorithm to take into account implicit on-curve points.

Created attachment 101396 [details]
glyph uni4E31 of font sazanami-mincho.ttf

This glyph can't be handle by the new algorithm. There are many similar glyphs in this font which have similar issues.

Created attachment 101397 [details]
Zoom in view of the most left points.

You can see that, because the new algorithm will only take on-curve (both explicit and implicit) points into account, the most left (xmin) point is 26, the previous point is 24, the next point is 28. But the angle 24-26-28 is inverted comparing to the contour orientation, then we will get wrong result.

If we take off-curve points into account, this issue will be avoided, but we will get wrong result on many other glyphs.

Regarding a new algorithm, perhaps the method I've implemented in
mf2pt1 might help (you can get version 2.2 from CTAN; have a look
at function `is_clockwise' in file mf2pt1.mp).  It was necessary
to add it because the built-in code of MetaPost was faulty then.

Here a description:

. Find a point P on the path which has a non-zero direction.

. Construct a ray of ``infinite'' length, starting in the
  vicinity of P which intersects the path at this point.

. Use the MetaPost function `intersectiontimes' to find the
  intersection.  If the direction of the path at this point
  is (near) zero, or if we have a grazing intersection,
  get a new ray.

. Shorten the ray so that it starts right after the
  intersection.  Repeat the previous step until no
  intersection is found.  Then go back to the last
  intersection and compare the path's direction with the
  direction of the ray.  According to the `nonzero winding
  number' rule we have found a clockwise oriented path it
  it crosses the ray from left to right.

This method completely avoids any problems with the geometry of
Bézier curves.  If problems arise, a different ray is tried.
Since it isn't necessary to analyze the whole path it runs quite fast
in spite of using `intersectiontimes' which is a quite slow.

Sorry that I can't fully understand this algorithm and the is_clockwise code. Is there any article and diagram describing this algorithm?

According to my understanding, I have a question regarding this algorithm. Is it required to calculate the intersection points between the ray and contour? Because the contour contains not only straight lines but also Bezier curves, is it simple enough to calculate the intersection between ray and Bezier curves?

The current algorithm is correct for polygons with only straight lines.

I have new question: For truetype fonts, is it possible that the outer contour of a glyph has POSTSCRIPT orientation instead of TRUETYPE orientation? Why do we need to check the orientation of the contour instead of just assume that it's always TRUETYPE orientation?

Hmm, very interesting that sazanami-mincho.ttf is a font with POSTSCRIPT orientation instead of TRUETYPE orientation.

For an explanation of the nonzero winding rule, see for example

  http://www.asppdf.com/manual_04.html

(or look up something similar in the PS Reference Manual).

The above mentioned algorithm can be enormously simplified because font
contours are much more well-behaved than arbitrary Bézier curves; most
notably, they don't contain self-intersections or cusps.  Under these
assumptions it is sufficient to determine the orientation of the
`envelope' determined by the Bézier control points, this is, to find
the orientation of the polygon spanned up by the on and off line
points.  For simplicity, only consider horizontal rays -- the above
algorithm then gets reduced to comparing x and y values (probably
adding a vertical offset to avoid rays which pass through one of the
points).

A remark: Cusps and self-intersections (`loops') can only happen
for third-order curves.  It is also possible to construct third-order
Bézier curves which looks quite normal, but where the connection lines
between the control points do cross. I suggest that we ignore such
cases also.

Now I understand the algorithm. But I found that some fonts (especially CJK fonts) do have quite a few glyphs with self-intersections. It's possible to get false detection if the ray is inappropriate.

Created attachment 101492 [details]
A glyph with self-intersection contour in FZSongTi.ttf

A sample glyph with self-intersection.

Created attachment 101493 [details]
Zoom in view of the self-intersection area.

The self-intersection is obvious.

Well, the self-intersection in this glyph is clearly a bug in the font.
On the other hand, it's quite unlikely that a ray hits this small part
of the outline.  We might implement an additional `paranoid' mode which
uses two rays: If the results differ, a third ray finally decides the
orientation.

Hello everyone,

I'm pretty new here, but I'd like to make a few statements.

First of all, the TrueType specification clearly wasn't designed with easy emboldening in mind, since it explicitely allows:

- two contours to intersect (note: this is note the same than a single self-intersecting contour). See 

  http://developer.apple.com/textfonts/TTRefMan/RM01/Chap1.html#intersecting

- contours in arbitrary drawing directions, see the graphics in:

  http://developer.apple.com/textfonts/TTRefMan/RM02/Chap2.html#distinguishing

  note that even if all contours are oriented uniformly, you could have a reversal of the drawing direction in a composite glyph using, for example a mirroring transform (i've seen this implemented in a font to generate the reversed cyrillic R, for example)


this is a lot less strict than the Postscript font design rules, which allow the emboldening algorithm to work flawlessly for any compliant font.

Generally speaking, the current algorithm tries to do its job very quickly by simply "displacing" the glyph outline towards the "exterior" direction. It is quick because it doesn't try to compute new points in the outline, or see if there are intersections. And it works well in a *lot* of cases :-)

it simply assumes that the glyph is wel-formed, computes its orientation, then apply the relevant displacements to all points.

A general-purpose emboldening algorithm is something *very* different that must be capable of computing all intersections in the glyph (not only in each contour), and tesselate the result appropriately when these are found. This involves a lot of complex mathematics, with very subtle and hard-to-fix rounding issues; while it is possible to implement something like this, its performance will most certainly suck (witness the performance of the Cairo tesselators, where the original one is a drag and the new "optimized" one only provides massive speed-ups in complex/theorical cases, while being slower in practical ones at the moment; all this means is that writing an efficient tesselator is *hard* stuff). And consider that what we need here is considerably more difficult than what is used in Cairo, since we need to deal with Bezier arcs, not only line segments.

in an ideal world, we should be able to quickly determine if a glyph is well-formed, and use the short-cut when this is the case. When note, we should be able to use the slow algorithm (when and if it exists).

however, I'm for a more practical approach at the moment. I'll try to submit a patch that will do the following:

- to compute the global orientation, try to compute the orientation of all 4 borders of the glyph (top/bottom/left/right)

- if they all match, return the corresponding value

- if only 3 of them match, return their value since it probably means a self-intersecting gizmo like the one in the FZSongTi.ttf

- the only alternative is where we have 2 opposite values in equal numbers (2+2), in this case, we have a problem, and do *nothing*, at least we'll have something nicer to display.

what do you think about it ? It's only a slightly refined heuristic that doesn't force us to actually compute overlaps/intersections, but I hope it should be enough for the curious cases we're seeing.

I'm implementing the algorithm that Werner mentioned. I'll give you result asap.

I had tried to improve the patch posted in Comment #25 to test four borders, but it seems that it still can't handle some glyphs in FZSongTi.ttf and sazanami-mincho.ttf.

However, I'm willing to test your patch to see whether it's better or not.

I just found that some fonts really have many contours in arbitrary drawing directions, such as UnBatang.ttf, FZKaiTi.ttf.
I believe that many other fonts may have the same issue.
So I think, besides FT_Outline_Get_Orientation, we need fix FT_Outline_Embolden as well. One possible solution is to check each contour's orientation separately in FT_Outline_Embolden, instead of checking the whole glyph's orientation. However I don't know how much performance impact will be introduced by it.

I'll try this approach and give you feedback asap.

Created attachment 101863 [details]
A glyph in FZKaiTi.ttf with contours in arbitrary orientations.

The left part of this glyph is clockwise while the right part is counter-clockwise.

Created attachment 101864 [details]
A glyph in UnBatang.ttf with contours in arbitrary orientations.

Oh my god, these fonts are so wicked !! the control polygon is even self-intersection in patch 101863, while the outline isn't. there are local extrema on bezier curves everywhere; there is no way we're going to correctly embolden them with our "quick" algorithm, even if we improve the heuristics.

besides, checking the orientation of each contour is not going to help a lot, because you'll still need to decide wether the contour is an interior or exterior one, which quickly becomes non trivial if you're not on the glyph's bounding box.

we're either going to some *serious* code to deal with these or think differently about the problem (e.g. embolden the bitmaps, instead of the vectors)

Created attachment 102025 [details]
A patch to implement a new algorithm using nonzero winding rule.

It's a patch to implement the algorithm mentioned in comment #28, #32 and #36.

Most of those weird glyphs can be handled correctly, except those with arbitrary contour orientations.

Please have a try.

This looks good IMHO -- definitely better than the current code.
Have you done some timings?  And can you write a ChangeLog entry so that
I can easily add it to the FreeType CVS?

I don't know how to do benchmark easily, do you have any suggestion? Is there any existing benchmark code that I can use?

The ChangeLog entry can be:

* Algorithm used by FT_Outline_Get_Orientation() was improved by using "Nonzero winding rule", so that most weird glyphs can be handled correctly, except those with arbitrary contour orientation. Correctness of outline embolden can be improved a lot by this improvement.

It seems that the performance of the new algorithm is almost same as the old one.

I patched ftbench to do the benchmark. The benchmark result of the new algorithm of FZSongTi.ttf is around 175 us/op. While the result of old algorithm around 170 us/op.

Please help test it again.

Created attachment 102295 [details]
Patch to add Embolden benchmark into ftbench.

Please try this patch. It's correct and helpful, please merge it into ft2demos.

Both patches are now in the FreeType CVS, thanks a lot !

- David

Thanks a lot.

Mike, could you please upgrade our freetype2 and ft2demos packages to the latest cvs version? Or apply these two patches?

I think the package of SLE10 should be fixed as well.

freetype2 and ft2demos updated to 2.2.1.20061027 submitted to STABLE.

FIXED.