[ft-devel] [PATCH resend 2/2] Improve FT_Outline_Embolden for the unintended artifacts problem (#45596).

[Byeongsik Jeon]

FreeType-Bugs: https://savannah.nongnu.org/bugs/?45596
---
src/base/ftoutln.c | 177 ++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 176 insertions(+), 1 deletion(-)

[Byeongsik Jeon]

Hi.

+ det = i.y * o.x - i.x * o.y , det != 0
+ shift.x = strength * ( i.x - o.x ) / det
+ shift.y = strength * ( i.y - o.y ) / det

So your algorithm is exactly the same as the one implemented
currently. The tricky part is how you deal with very short collapsing
segments, the segments of zero length, and your threshold on the
determinant. Can you please elaborate on that and explain why your
algorithm is superior?

https://savannah.nongnu.org/bugs/?45596
https://savannah.nongnu.org/bugs/download.php?file_id=34479
03963_BAUHAUS.ttf is a very bad font for real use. However, it is a suitable
font to test the stability of the Embolden algorithm.

[0]
bauhaus_256px_0_gedit_non_patched.png:
This is a problem that appears in FreeType, which is not patched.

[1]
bauhaus_256px_1_gedit_ftsynth_patched.png:
It's only applied the fetsynth Embolden patch. The overlaped shape was found in
its original shape, and the size of the artifact was reduced. The overall stem
thickness or advance is correctly organized.

[2]
bauhaus_256px_2_gedit_ftsynth+shift_limit_patched.pcrushng:
Additional shift limitation patch have been applied.

shift.x = FT_MAX( FT_MIN( shift.x, strength.x ), -strength.x );
shift.y = FT_MAX( FT_MIN( shift.y, strength.y ), -strength.y );

The sharpen edge of the 'X' has been removed.

[3]
bauhaus_256px_3_gedit_all_patched.png:
The remaining patches were applied. You can see that all the artifacts are
removed. The middle stem of the "$" character is rendered to the right thickness.

It was so difficult to modify the existing code that I rewrite it. But it's
based on the existing code idea.

l_out = (FT_Fixed)FT_Vector_NormLen( &out );

if ( l_out == 0 )
continue;

While the existing code focuses on skipping only the zero-length segment, the
new code skips the zero-determinant segment.

det = FT_MulFix( in.y, out.x ) - FT_MulFix( in.x, out.y );
if ( det == 0 ) continue;

Zero-determinant segments include these things:
- zero-length segment: |in| == 0 or |out| == 0 ( normalized vector in, out )
- plain straight segment: in == out
- forward-backward mixed straight segment: in + out == 0

"( det = in.y * out.x - in.x * out.y ) == 0" checks all of these.

The "forward-backward mixed straight segment" are particularly important.
Because their shift vectors are in the opposite direction, they produce a
prominent artifact.

The good thing about the improved code is that "det" is part of the formula for
obtaining shift vectors. Also, since improved code is not difficult, it is easy
to track even if new problems are found.

Unless "strength" is zero, it is inevitable that shift vectors intersect or
sharpen edge generation. The appropriate values of "strength" and "shift limit
code" complement this deficiencies.

[4]
bauhaus_256px_4_win7ie9_virtualbox.png:
The artifact that appears here is obviously a bug in Windows. Potentially, this
problem can appear on any font.

What we should note is that the rendered letter shape, except for the artifacts,
is almost identical to our results.

Thanks.

FreeType-Bugs: https://savannah.nongnu.org/bugs/?45596
---
   src/base/ftoutln.c | 177 ++++++++++++++++++++++++++++++++++++++++++++-
   1 file changed, 176 insertions(+), 1 deletion(-)
_______________________________________________
Freetype-devel mailing list
https://lists.nongnu.org/mailman/listinfo/freetype-devel

[Alexei Podtelezhnikov]

Post by Byeongsik Jeon
[3]
The remaining patches were applied. You can see that all the artifacts are
removed. The middle stem of the "$" character is rendered to the right thickness.

I can also see that after all set and done the glyph is much less
emboldened. You could have just used less strength with the original
algorithm and achieved similar results. Again it is important to
achieve fewer artifacts with the *same* stem thickness.

[Byeongsik Jeon]

On Thu, 4 Oct 2018 22:34:56 -0400, Alexei Podtelezhnikov <***@gmail.com>
wrote:>>> + /* The large shift value creates a cross point, which appears

+ as one of the artifacts. The shift value limitation inhibits
+ the occurrence of artifacts. */
+ shift.x = FT_MAX( FT_MIN( shift.x, strength.x ), -strength.x );
+ shift.y = FT_MAX( FT_MIN( shift.y, strength.y ), -strength.y );
+

Maybe, it is threshold on the determinant. This inhibits the sarpen corner, and
the cross point artifacts.

Hmm. This is not invariant with respect to rotation. It will work
differently for along the axes and along 45 degree line. It is also
extremely restrictive: the shift magnitude (Euclidean) is always
larger than strength for any (even obtuse) angle. So even obtuse
angles are subject to this restriction sometimes. I wonder if this is
the reason you had to compensate with larger strengths in the second
patch. Have you tried limiting the shift to double or triple the
strength?

The Embolden function of the resended patch has not changed from the original. I
just wanted to start this discussion on the new thread.

I'm aware of the problem you're talking about. It appears in the "/" letter.

bauhaus_256px_1_gedit_ftsynth_patched.png
bauhaus_256px_2_gedit_ftsynth+shift_limit_patched.png

When you compare them, you can see that the diagonal stem thickness changes in
the letters "%" and "4". However, the final result is the same as Windows, so no
further processing was done.

I have the idea of ​​"shift limit code" being separated from artifact like "X"
and normal "/" case. But as I wrote above, I need to investigate MS Windows, so
I want to add it to another patch.

I can also see that after all set and done the glyph is much less
emboldened. You could have just used less strength with the original
algorithm and achieved similar results. Again it is important to
achieve fewer artifacts with the*same* stem thickness.

If you look at the fetsynth patch, you can see that the strength value has been
modified. I have made it an important goal to match with Windows looks. The
original code is divided by 24 so it has a thicker stem. But it doesn't match
Windows looks.

+ /* the value that matches the MS Windows embolden looks.
+ the larger strength value, the more unintended artifacts increase.
+ using the integer pixel strength inhibits the blurred outlines.
+ */
+ ppem = face->size->metrics.y_ppem;
+ ystr = (( ppem - 1 ) / 50 ) << 6;
+ xstr = ystr + 64;


bauhaus_256px_1_gedit_ftsynth_patched.png

This is the result of reducing strength only in the original algorithm. It's
only a reduction in the size of the artifact, but it still occurs. Thickness(
strength) is not the main cause of its occurrence.

Please look at the description of the patch that was resended.

The "forward-backward mixed straight segment" are particularly important.
Because their shift vectors are in the opposite direction, they produce a
prominent artifact.

I've got two goals.
- Match with Windows as much as possible
- Unintended artifact suppression.

The improved code seems to have achieved these two goals, and it's easy to
accept new ideas because the algorithms are easy.

Thanks.

[Byeongsik Jeon]

I'm sorry.
I think I fell into a fixed idea because of my good looking results.

Now, I'm trying to combine the advantages of both codes. I think I will reuse
the idea of ​​a lot of existing code.

If you want to work on your own, please tell me so that I can save my time.

Thanks.

Post by Alexei Podtelezhnikov

Post by Byeongsik Jeon
[3]
The remaining patches were applied. You can see that all the artifacts are
removed. The middle stem of the "$" character is rendered to the right thickness.

I can also see that after all set and done the glyph is much less
emboldened. You could have just used less strength with the original
algorithm and achieved similar results. Again it is important to
achieve fewer artifacts with the *same* stem thickness.

[Alexei Podtelezhnikov]

Post by Byeongsik Jeon
I'm sorry.
I think I fell into a fixed idea because of my good looking results.
Now, I'm trying to combine the advantages of both codes. I think I will reuse
the idea of a lot of existing code.

A few important things to keep in mind before I go into algorithmic
ideas. The strength in the FreeType sense is how many pixels are added
to a stem, half a pixel on each side, measured in 1/64 of a pixel.
This is documented and expected. We cannot change that. You refer to
MS implementation. Is it documented somewhere? Also you should be
careful with modifying metrics. So that you do not surprise people
who use this functionality.

I doubt that there is an easy way to solve artifacts with a simple cap
on shift. This mathematical problem has a proper rigorous solution:

1) Emboldening does not change the orientation of segments, it only
changes their lengths. The "cross" situation is when the length
becomes "negative" or the segment points in the opposite direction.
Such segments should be removed from the *original* outline: two
original adjacent segments should be shortcut at their intersection.
This process might be recursive until all "cross" conditions are
removed.
2) Shift the remaining simplified outline points.
3) Deal with sharp angles: use round or bevel line join.

Of course this is easier said than done. I put that on hold a long
time ago. You welcome to work on this. This might be a cool summer
GSoC project.

Regards,
Alexei

[Byeongsik Jeon]

Post by Alexei Podtelezhnikov

Post by Byeongsik Jeon
I'm sorry.
I think I fell into a fixed idea because of my good looking results.
Now, I'm trying to combine the advantages of both codes. I think I will reuse
the idea of a lot of existing code.

A few important things to keep in mind before I go into algorithmic
ideas. The strength in the FreeType sense is how many pixels are added
to a stem, half a pixel on each side, measured in 1/64 of a pixel.
This is documented and expected. We cannot change that. You refer to
MS implementation. Is it documented somewhere? Also you should be
careful with modifying metrics. So that you do not surprise people
who use this functionality.
I doubt that there is an easy way to solve artifacts with a simple cap
1) Emboldening does not change the orientation of segments, it only
changes their lengths. The "cross" situation is when the length
becomes "negative" or the segment points in the opposite direction.
Such segments should be removed from the *original* outline: two
original adjacent segments should be shortcut at their intersection.
This process might be recursive until all "cross" conditions are
removed.
2) Shift the remaining simplified outline points.
3) Deal with sharp angles: use round or bevel line join.
Of course this is easier said than done. I put that on hold a long
time ago. You welcome to work on this. This might be a cool summer
GSoC project.
Regards,
Alexei

Thank you.

I have tried to solve this problem in the past few days, but I have not got a
satisfactory solution. In short, it was like playing a mole-catching game.

So I thought in another direction. I tried to find a solution to the problem,
but I was worried about the cause of the problem.

Is it because the shift vector is too big in the sharpen edge?

rot( in + out ) / ( 1 + inner_product( in, out ) )

The sharper the corner, the more this value converges to infinity.
The code below is avoiding this problem.

/* shift only if turn is less than ~160 degrees */
if ( d > -0xF000L )
{
d = d + 0x10000L;
...
}
else
shift.x = shift.y = 0;

However, this code causes another artifact to be created. This is because the
shift value suddenly becomes zero unlike the neighbor points.

I thought about using another equation to get a shift vector. The direction can
be obtained as "normalize( rot( in + out ) ). The length induced an expression
that satisfies certain conditions as follows.

/* deg = in.x * out.x + in.y * out.y = -cos(theta)
* f(deg) = a * deg^2 + b * deg + d
* f(1) = 1 , theta = 180
* f(0) = sqrt(2) , theta = 90, 270
* f(-1) = k , theta = 0, 360
*/

k_plot.png is a graph of the equations with the original expression.

The k value controls the shift value. The actual results are stable because they
maintain the correct value at 90, 180, 270 degrees. Even the results of k = 0.0
are noteworthy.

I want to hear your opinion on this approach.

[Alexei Podtelezhnikov]

Post by Byeongsik Jeon
I want to hear your opinion on this approach.

The original glyph shape is usually smooth: the contours have no
self-intersections. The emboldening might result in self-intersecting
contours. This is the main reason for majority of artifacts. You
already figured out that corners slide along bisectors, assuming
symmetric strength.x == strength.y. It is easy to see that self
intersections happen when a segment flips its orientation under
certain condition. This condition is easy to formulate but it involves
both corners at the segment termini and the length of the segment.
Nothing short of resolving these will work: such segments have to be
removed. To put it differently, the outline has to be simplified by
removing self-intersecting segments and replacing them with a point at
the intersection of the flanking segments. That is it and then you
apply emboldening cleanly.

The other issue is sharp corners that are left. The standard solution
for them is bevel or round join of lines in the emboldened outline.
This is totally separate.

I do not see other reasons for artifacts and very much doubt that any
easier solution exists. By the way, we has glyph stroker
https://www.freetype.org/freetype2/docs/reference/ft2-glyph_stroker.html.
This should be a sister algorithm, but it is implemented separately
with a bunch of trigonometry. I personally would love to have a single
FreeType module handle both, implemented using bisectors. So this is a
big project altogether: I would estimate at least 100 hours of
programing.

[Byeongsik Jeon]

Post by Alexei Podtelezhnikov

Post by Byeongsik Jeon
I want to hear your opinion on this approach.

The original glyph shape is usually smooth: the contours have no
self-intersections. The emboldening might result in self-intersecting
contours. This is the main reason for majority of artifacts. You
already figured out that corners slide along bisectors, assuming
symmetric strength.x == strength.y. It is easy to see that self
intersections happen when a segment flips its orientation under
certain condition. This condition is easy to formulate but it involves
both corners at the segment termini and the length of the segment.
Nothing short of resolving these will work: such segments have to be
removed. To put it differently, the outline has to be simplified by
removing self-intersecting segments and replacing them with a point at
the intersection of the flanking segments. That is it and then you
apply emboldening cleanly.

Yes. I was trying to do a solution this way. The problem is that this method
alone can eliminate the intended design of the font.

So, how about using the newly introduced shifter to implement it? k==2.3 is
almost similar to the existing shifter between 90 and 270 degrees, and I think
it is appropriate for the rest.

Post by Alexei Podtelezhnikov
The other issue is sharp corners that are left. The standard solution
for them is bevel or round join of lines in the emboldened outline.
This is totally separate.
I do not see other reasons for artifacts and very much doubt that any
easier solution exists. By the way, we has glyph stroker
https://www.freetype.org/freetype2/docs/reference/ft2-glyph_stroker.html.
This should be a sister algorithm, but it is implemented separately
with a bunch of trigonometry. I personally would love to have a single
FreeType module handle both, implemented using bisectors. So this is a
big project altogether: I would estimate at least 100 hours of
programing.

[Alexei Podtelezhnikov]

Post by Byeongsik Jeon

Post by Alexei Podtelezhnikov
the outline has to be simplified by
removing self-intersecting segments and replacing them with a point at
the intersection of the flanking segments. That is it and then you
apply emboldening cleanly.

Yes. I was trying to do a solution this way. The problem is that this method
alone can eliminate the intended design of the font.

Emboldening is akin to rolling a ball around the perimeter. A ball
sometimes cannot get into features smaller than its size - those
features are indeed removed. This is unavoidable. A huge ball rolling
around any glyph would produce shapeless blob. The larger the strength
of emboldening, the more features are removed.

[Byeongsik Jeon]

On Tue, 9 Oct 2018 09:51:05 -0400, Alexei Podtelezhnikov

Post by Alexei Podtelezhnikov

Post by Byeongsik Jeon

Post by Alexei Podtelezhnikov
the outline has to be simplified by
removing self-intersecting segments and replacing them with a point at
the intersection of the flanking segments. That is it and then you
apply emboldening cleanly.

Yes. I was trying to do a solution this way. The problem is that this method
alone can eliminate the intended design of the font.

Emboldening is akin to rolling a ball around the perimeter. A ball
sometimes cannot get into features smaller than its size - those
features are indeed removed. This is unavoidable. A huge ball rolling
around any glyph would produce shapeless blob. The larger the strength
of emboldening, the more features are removed.

OK.

What I'm saying is,
the current shifter has too big value as it goes around 0(360) degree,
so it makes up the intersection that should not be made.

However, the shifter replacement is not the priority of the task now.
First, after the intersection removal code is completed, it is a problem
to think about.

I'll do my work as soon as I get time. The exchange of opinions with you
has been a great reference.

Thanks.