Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

>> Thanks, too.  What do you think about integrating this into (at
>> least) `ftview`?
> 
> Yes, it can be integrated into the existing demo programs, however I
> think it should have a separate demo program because of the way SDF
> is rendered, it has a raw and reconstruction view as well as various
> properties and bilinear filtering.  Because of that I think
> integrating it completely into the existing programs will clutter
> the programs.

OK, no problem to add another test program :-) Please make it behave
similar to the other ones as much as posible for the sake of
orthogonality.

> On the other hand It makes sense to integrate them into the existing
> programs, so that we can compare them with other renderers and see
> how it looks.  It will require significant changes to the graphics
> subsytem (adding bilinear filtering, render 16 bpp, the
> reconstruction mode etc.).  So, perhaps I should do it after GSoC?

This would be great, of course!  However, if you want to invest some
time in this area please have a look at the `ftinspect` program, which
is intended as a modern replacement and synthesis of all demo
programs.  [There are also some improvements in the
'veeki-gsoc-experimental' branch, which unfortunately don't fly, so to
say.  Maybe some of it is useful.]


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 >> Werner, Are you still interested in adding API to remove overlaps?
>
> Yes, I am.

Alright, I will start reading more about it after GSoC.

>> I have updated the demo to include the new algorithm to handle
>> overlaps.  [...]
>
> Thanks, too.  What do you think about integrating this into (at least)
> `ftview`?

Yes, it can be integrated into the existing demo programs, however I
think it should have a separate demo program because of the way
SDF is rendered, it has a raw and reconstruction view as well as
various properties and bilinear filtering. Because of that I think
integrating it completely into the existing programs will clutter the
programs.
On the other hand It makes sense to integrate them into the
existing programs, so that we can compare them with other
renderers and see how it looks. It will require significant changes
to the graphics subsytem (adding bilinear filtering, render 16 bpp,
the reconstruction mode etc.). So, perhaps I should do it after GSoC?

Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> Werner, Are you still interested in adding API to remove overlaps?

Yes, I am.

> I watched the skia code and the video on how it's done in skia.  I
> think it's doable, the only tricky part that I think is to find the
> intersecting point of contours, because they use a 4th degree
> polynomial to find the intersections.  If you're still interested in
> adding the API, I can start reading more about it after GSoC and
> then add it.

This would be really great.  Thanks for the offer!

> I have updated the demo to include the new algorithm to handle
> overlaps.  [...]

Thanks, too.  What do you think about integrating this into (at least)
`ftview`?

> And then I will write a brief description of how both `sdf' and
> `bsdf' renderers work in the source files.  And finally I will
> create a new branch and add the code there.  If there is anything
> else please do let me know.

Your plan sounds just fine :-)


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei, Werner,

>> I meant it all along but perhaps it is hard to do it on the fly. Ther
>> rules seem to be as follows:
>>
>> 1) Both outside (both positive), choose a smaller value
>> 2) Both inside (both negative), choose a smaller value as in (-5 < -4)
>> not by absolute value
>> 3) one inside one outside, choose a smaller value as in (-3 < 2) not
>> by absolute value
>>
>> I.e. always choose a smaller value combining two contours so it seems
>
> Along with this we probably also need to find the resultant vector in case
> two distances are non infinite at a same point (i.e. the distance values
are
> less than spread), that we can find the distance to the corner even tho
> there is no actual corner in some glyphs.

I've added the overlapping support according to your algorithm, however I
have
modified the rule as follows:

-> Generate SDF for each contour in a separate bitmap.
-> for combining all the SDF to one use the below rule:
  -> for each pixel/grid point:
   c = for all clockwise contours find the largest signed value.
ac = for all counter-clockwise contours find the smallest
signed value.
   final_value = smallest signed value of `c' and `ac'.

It works well for all of the glyphs that I checked apart from glyphs with
self
intersecting contours, because they can't be separated into different
bitmaps. To
handle self intersecting contours I think there is only one way and that is
to remove
the overlaps.

[
Werner,
  Are you still interested in adding API to remove overlaps? I watched the
skia code
  and the video on how it's done in skia. I think it's doable, the only
tricky part that I
  think is to find the intersecting point of contours, because they use a
4th degree
  polynomial to find the intersections.
  If you're still interested in adding the API, I can start reading more
about it after GSoC
  and then add it.
]

I have updated the demo to include the new algorithm to handle overlaps. I
have also
disabled all the optimization modes except the subdivision optimization (it
will be the
default one from now on until I find something even faster). Here is the
link:
https://github.com/preversewharf45/ft2sdf-demo, for help screen press '?'
or F1. There is
a `CascadiaCode.ttf' font which is full of overlaps, so that you can check
how the new
algorithm performs.

And now that GSoC is almost over, I will fix the compiler warnings first.
And then I will
write a brief description of how both `sdf' and `bsdf' renderers work in
the source files.
And finally I will create a new branch and add the code there. If there is
anything else
please do let me know.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > I meant it all along but perhaps it is hard to do it on the fly. Ther
> rules seem to be as follows:
>
> 1) Both outside (both positive), choose a smaller value
> 2) Both inside (both negative), choose a smaller value as in (-5 < -4)
> not by absolute value
> 3) one inside one outside, choose a smaller value as in (-3 < 2) not
> by absolute value
>
> I.e. always choose a smaller value combining two contours so it seems

Along with this we probably also need to find the resultant vector in case
two distances are non infinite at a same point (i.e. the distance values are
less than spread), that we can find the distance to the corner even tho
there is no actual corner in some glyphs.

Also, my progress has been slow lately because my classes have started
and there is the campus placement thing going on. I haven't yet started
doing the overlapping support, I will try to add it by next next week and
see if it works.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

> I.e. always choose a smaller value combining two contours so it seems

This might be oversimplified, but it is clear that the sign is
supposed to agree with the winding number and the priority of
distances should be defined by the fill rule.

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

On Fri, Aug 7, 2020 at 10:58 AM Anuj Verma  wrote:
>
> > Yeah. We should basically think of overlaying or combining two
> > distance fields, generated independently one for each contour.
> > Has this been discussed in the literature?
>
> No, it has not been. That sounds interesting, thanks for the idea.
> I will think about it tomorrow, perhaps it might solve the issue. My
> only concern would be the additional memory usage, because some
> glyphs have many contours. But yeah we can turn it ON only for
> overlapping contours.

I meant it all along but perhaps it is hard to do it on the fly. Ther
rules seem to be as follows:

1) Both outside (both positive), choose a smaller value
2) Both inside (both negative), choose a smaller value as in (-5 < -4)
not by absolute value
3) one inside one outside, choose a smaller value as in (-3 < 2) not
by absolute value

I.e. always choose a smaller value combining two contours so it seems

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > Yeah. We should basically think of overlaying or combining two
> distance fields, generated independently one for each contour.
> Has this been discussed in the literature?

No, it has not been. That sounds interesting, thanks for the idea.
I will think about it tomorrow, perhaps it might solve the issue. My
only concern would be the additional memory usage, because some
glyphs have many contours. But yeah we can turn it ON only for
overlapping contours.

Thanks for the idea,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

On Fri, Aug 7, 2020 at 12:54 AM Anuj Verma  wrote:
>
> Hello Alexei,
>
> > Can you describe discontinuities with the same sign if I overlook them?
>
> So, I found there are two types of discontinuities due to overlapping 
> contours:
>
> A) Discontinuity in sign. (i.e. there is a sudden jump from negative to 
> positive)
> B) Discontinuity in distances. (i.e. the points that should be at 
> infinity/spread have smaller distances)

Yeah. We should basically think of overlaying or combining two
distance fields, generated independently one for each contour.
Has this been discussed in the literature?

> Also, I looked at a library (msdfgen) which handles overlapping contours 
> without
> removing the overlaps. It works well, but it doesn't work for 
> self-intersecting contours,
> that is why I'm not sure whether it's worth implementing.

Self intersecting contours should never and hopefully will never be
allowed in fonts.

> Finally, I can find and fix signs such that all points inside a shape are 
> positive and
> all points outside are negative. But I don't know how I can fix the incorrect 
> distances
> caused by the overlaps. Here is one final example: 
> https://i.imgur.com/jiaqiBS.png
> In this the point `P' has a positive sign and it points to a line inside the 
> shape, which
> is not correct, instead it should point to the corner. Moreover there is no 
> corner in the
> shape because they are two separate contours, so I think removing the 
> overlaps is
> the best way to handle this.

Here I concede we will never find proper distance unless we define the
intersection point.

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

> Can you describe discontinuities with the same sign if I overlook them?

So, I found there are two types of discontinuities due to overlapping
contours:

A) Discontinuity in sign. (i.e. there is a sudden jump from negative to
positive)
B) Discontinuity in distances. (i.e. the points that should be at
infinity/spread have smaller distances)

Here is an example of a SDF generated from glyph with overlaps:
https://i.imgur.com/3pqHZWd.png
In that image the right side is correct (generated from bitmap), and the
left side has both A and B
types of  discontinuities.

What you are saying about detecting sudden jump from large negative to large
positive can work for discontinuities in sign. I tried that and here is an
example: https://i.imgur.com/unRB23Z.png
(ignore the weird lines in the image, that can be fixed). But even after
fixing the
sign there are pixels inside the outline which have shortest distance to
the curves
inside the outline. (basically the pixels around the overlap points to the
overlapping
curve, which causes discontinuous distances). Moreover they interpolate
smoothly
so there is no way to find the actual distance which will be to some curve
at the border
of the outline instead of inside the outline.

Also, I looked at a library (msdfgen) which handles overlapping contours
without
removing the overlaps. It works well, but it doesn't work for
self-intersecting contours,
that is why I'm not sure whether it's worth implementing.

Finally, I can find and fix signs such that all points inside a shape are
positive and
all points outside are negative. But I don't know how I can fix the
incorrect distances
caused by the overlaps. Here is one final example:
https://i.imgur.com/jiaqiBS.png
In this the point `P' has a positive sign and it points to a line inside
the shape, which
is not correct, instead it should point to the corner. Moreover there is no
corner in the
shape because they are two separate contours, so I think removing the
overlaps is
the best way to handle this.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Hi Anuj,

> > If I understand correctly, overlaps cause unexpected discontinuity in
> > SDF, which otherwise should not have any. I doubt that detecting and
> > removing contour overlaps is productive. I would rather deal with the
> > discontinuity directly. Perhaps there is a clever way to ignore
> > smaller distances that unexpectedly have an opposite sign. The
> > distance cannot change by more than the grid size. If it does, ignore
> > the offending value.
>
> Yes, overlaps cause discontinuity in both sign and distances. Detecting
> unexpected opposite sign is possible, but the sign may not be opposite.
> In many cases the sign is not flipped (there is no unexpected change
> in sign) and the distances interpolate smoothly, in those cases it becomes
> hard to find the true distances of the point.

I still think that it should be possible to ignore distances that
result in discontinuities. The distance field has to be continuous
from edge to edge, from clamped "infinity" to clamped "infinity", with
continuity defined as not changing by more than a grid size. The signs
are allowed to flip only then crossing line segments (i.e. scanning
the line neighborhood, rather than overriding a previous value). As
you scan a neighborhood for a line and encounter a previously recorded
(not "infinite") value you should override only if it has the same
sign and smaller magnitude.

Can you describe discontinuities with the same sign if I overlook them?

Thank you
Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

Hello Anuj,


> I have mostly completed the bitmap to SDF renderer (bsdf), there are
> only a few things remaining such as support for all pixel modes
> (currently it only work with FT_PIXEL_MODE_GRAY), and warnings etc.

Excellent, thanks!

> Next, I will be finishing the bsdf renderer and then writing the
> documentation for all the functions (should I write for structs as
> well? i.e. detailed description of all the members).

Yes, please.  The more the merrier :-) To be serious: A few months in
the future even you will start to forget most of the details.  Always
have in mind that people will look at your stuff who have never seen
it before, and who don't have the time to walk through the complete
code to get all the necessary information.

> Also is there any other kind of documentation that I should add?

I don't think so.  Will tell you otherwise :-)

> After that I have not decided what to do.  I have a few things in
> mind (adding floating point support, removing overlaps and a few
> more).  But we can discuss that once I have finished the
> documentation.  (Also, I will keep improving the existing
> algorithms, optimizing and removing any bug that I find along the
> way)

In mid-August I suggest that you start cleaning up your git branch,
this is, you create a new branch and populate it with new commits that
introduce SDF and BSDF in small, incremental, and logical steps.  This
mainly affects the stuff that has to be added to already existing
files.  Code in new files don't have to be handled that way, of
course, if it doesn't make sense.

> I have updated the demo
> (https://github.com/preversewharf45/ft2sdf-demo) and this time I
> have added the help screen ('?' or F1), I have also included a font
> `CascadiaCode.ttf' which is full of overlaps, so that you can
> compare both the renderers.

Great!  Will test soon.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

> Only FT_PIXEL_MODE_MONO is necessary to add. I do not understand how
> LCD or BGRA can be used for SDF; GRAY2 and GRAY4 are defunct.

It might be possible to convert LCD and BGRA to SDF, either using  a single
channel or by converting them to grayscale, but yeah I don't think that
will be
useful. And I will skip GRAY2 and GRAY4.

> If I understand correctly, overlaps cause unexpected discontinuity in
> SDF, which otherwise should not have any. I doubt that detecting and
> removing contour overlaps is productive. I would rather deal with the
> discontinuity directly. Perhaps there is a clever way to ignore
> smaller distances that unexpectedly have an opposite sign. The
> distance cannot change by more than the grid size. If it does, ignore
> the offending value.

Yes, overlaps cause discontinuity in both sign and distances. Detecting
unexpected opposite sign is possible, but the sign may not be opposite.
In many cases the sign is not flipped (there is no unexpected change
in sign) and the distances interpolate smoothly, in those cases it becomes
hard to find the true distances of the point.
There is a way to do it, which is done in the 'msdfgen' library, but it is
not perfect and I don't know whether it will work with subdivision
optimization
or not.
I will try to think of some other way of handling overlaps without actually
removing overlaps, but I think the most robust way to do it would be to
remove the overlaps.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Hi Anuj,

> I have mostly completed the bitmap to SDF renderer (bsdf), there
> are only a few things remaining such as support for all pixel
> modes (currently it only work with FT_PIXEL_MODE_GRAY),

Only FT_PIXEL_MODE_MONO is necessary to add. I do not understand how
LCD or BGRA can be used for SDF; GRAY2 and GRAY4 are defunct.

> After that I have not decided what to do. I have a few things in mind (adding
> floating point support, removing overlaps [skip]

If I understand correctly, overlaps cause unexpected discontinuity in
SDF, which otherwise should not have any. I doubt that detecting and
removing contour overlaps is productive. I would rather deal with the
discontinuity directly. Perhaps there is a clever way to ignore
smaller distances that unexpectedly have an opposite sign. The
distance cannot change by more than the grid size. If it does, ignore
the offending value.

> CascadiaCode.ttf

Oh those variable fonts with overlaps...  When you read
https://docs.microsoft.com/en-us/typography/opentype/spec/glyf#simpleGlyphFlags
on OVERLAP_SIMPLE, there is a glimmer of hope: "either set this flag
in the derived glyph data, or else should merge contours to remove
overlap". So the flag is basically required in static fonts. I hope it
will be required in variable fonts too in the next version of specs.

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Werner, Alexei,

I have mostly completed the bitmap to SDF renderer (bsdf), there
are only a few things remaining such as support for all pixel
modes (currently it only work with FT_PIXEL_MODE_GRAY),
and warnings etc. I did say before that the bitmap to SDF will require
less memory than the other, but that is not the case, after I read the
algorithm and implemented it, both the renderers have similar memory
requirements. The only advantage of the  bsdf renderer is that it can
handle glyphs with overlaps.

Next, I will be finishing the bsdf renderer and then writing the
documentation
for all the functions (should I write for structs as well? i.e. detailed
description
of all the members). Also is there any other kind of documentation that I
should
add ?
After that I have not decided what to do. I have a few things in mind
(adding
floating point support, removing overlaps and a few more). But we can
discuss
that once I have finished the documentation. (Also, I will keep improving
the
existing algorithms, optimizing and removing any bug that I find along the
way)

I have updated the demo (https://github.com/preversewharf45/ft2sdf-demo)
and this time I have added the help screen ('?' or F1), I have also included
a font `CascadiaCode.ttf' which is full of overlaps, so that you can compare
both the renderers.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> I have my college exams on 23rd and 24th this month, and as I
> haven't prepared for them yet, I would like to give a few days that
> are left and study for my exams.

Of course.  I wish you success!


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei, Werner,

I have my college exams on 23rd and 24th this month,
and as I haven't prepared for them yet, I would like to
give a few days that are left and study for my exams.
My last exam is on the 24th morning and after that I will
start doing the bitmap to SDF renderer which I think
will not take more than 2 weeks.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Hi Anuj

> Which one do you think is better ? I prefer the second one i.e. adding
> another renderer within the `sdf' module. That way I can share some
> of the code, whereas creating another module will require me to
> rewrite everything.

Same module with two renderers as you described makes sense to me too.

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 >> * `FT_Lookup_Renderer' uses renderer format which is currently
>>   `FT_GLYPH_FORMAT_OUTLINE' for the `sdf' module.  How can
>>make it accept both outline and bitmap glyph format ?
>
> Regarding the second issue I think that you probably have to create a
> second renderer that shares most of the code with the original one.

So, I  started adding the new renderer module for the bitmap to sdf
conversion. Is that okay? i.e. adding a new module named `sdfb'.
Or should I just create another renderer in the same module
and add it to the `module.mk' ? something like this:

```
FTMODULE_H_COMMANDS += SDF_RENDERER
FTMODULE_H_COMMANDS += SDF_BITMAP_RENDERER

define SDF_RENDERER
$(OPEN_DRIVER) FT_Renderer_Class, ft_sdf_renderer_class $(CLOSE_DRIVER)
$(ECHO_DRIVER)sdf   $(ECHO_DRIVER_DESC)signed distance field
renderer$(ECHO_DRIVER_DONE)
endef

define SDF_BITMAP_RENDERER
$(OPEN_DRIVER) FT_Renderer_Class, ft_sdf_bitmap_renderer_class
$(CLOSE_DRIVER)
$(ECHO_DRIVER)sdfb  $(ECHO_DRIVER_DESC)bitmap to signed distance field
converter$(ECHO_DRIVER_DONE)
endef

#EOF
```
Which one do you think is better ? I prefer the second one i.e. adding
another renderer within the `sdf' module. That way I can share some
of the code, whereas creating another module will require me to
rewrite everything.

Thanks,
Anuj

On Wed, Jul 15, 2020 at 10:43 AM Werner LEMBERG  wrote:

>
> > I have added all the optimization modes to the module.
>
> Great, thanks!
>
> > By far the fastest method is to subdivide the curve into a number of
> > line segments.  [...]
>
> OK.  I'm glad that you took the time to implement the various
> algorithms so that we have such a comparison.
>
> > The major downside of the BB and subdivision methods is that they
> > require a considerable amount of memory usage (almost 3x of the size
> > of bitmap) because we need to keep a track of the distances and
> > signs of all the grid points.
>
> I don't think this is an issue.  For other rendering modes like LCD
> there are similar requirements, and platforms that are going to use
> SFDs certainly have plenty of memory.  It would be nice, however, if
> you can add this constraint to the documentation, and, if possible,
> also add a logging message that either predicts the necessary
> (approximate) amount of memory before the computation, and/or the
> actual memory use after generating an SFD.
>
> > I have updated the demo, added bilinear filtering, shape
> > reconstruction and has all optimization modes which can be toggled.
> > I have attached the new list of keys.
> > (https://github.com/preversewharf45/ft2sdf-demo)
>
> Thanks, will test soon.
>
> > For now I would like to hold the outline implementation for now and
> > go to the bitmap implementation.  After that the module can be used
> > to generate SDF from bitmaps directly.  It will be pretty fast and
> > will not require any additional memory other than the bitmap itself
> > at a cost of reduced accuracy.
>
> Excellent.
>
> > However there are a few issues.
> >
> > * `FT_Render_Glyph_Internal' break if the glyph format is already
> >a bitmap.
> >```
> > case FT_GLYPH_FORMAT_BITMAP:   /* already a bitmap, don't do
> anything */
> >   break;
> >```
> > * `FT_Lookup_Renderer' uses renderer format which is currently
> >   `FT_GLYPH_FORMAT_OUTLINE' for the `sdf' module.  How can
> >make it accept both outline and bitmap glyph format ?
> >
> > I don't like the idea of changing the internals of freetype so is
> > there any other way in which this can be done ?
>
> Don't worry about changing the internals!  You know best what to do,
> and we can discuss later whether your solution is the right approach.
> Regarding the second issue I think that you probably have to create a
> second renderer that shares most of the code with the original one.
> Alexei?
>
>
> Werner
>

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

> On Jul 16, 2020, at 00:42, Werner LEMBERG  wrote:
> 
> 
>>> I would be less worried about FT_Property_Set if FreeType reserved
>>> the right to remove (ignore) or change properties when it is
>>> reasonable to do so, i.e. properties should not be considered a
>>> part of API.
>> 
>> Does that mean I shouldn't use `FT_Property_Set' ? For some
>> parameters such as `spread' there is no other way to dynamically set
>> it.
> 
> You definitely should use `FT_Property_Set`.  However, as done in
> other modules, we declare (some of) the properties as 'experimental'
> in the documentation so that we can change or remove them if
> necessary.

Yes. For example, the spread probably defines the range of reliable 
interpolations. So this option is solidly user-relevant. The algorithm, on the 
other hand is a developer option to experiment with. A user should not expect 
this option to be perpetually available as new algorithms might be offered and 
the old ones dropped. Perhaps, a development option is a better name.

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

>> I would be less worried about FT_Property_Set if FreeType reserved
>> the right to remove (ignore) or change properties when it is
>> reasonable to do so, i.e. properties should not be considered a
>> part of API.
> 
> Does that mean I shouldn't use `FT_Property_Set' ? For some
> parameters such as `spread' there is no other way to dynamically set
> it.

You definitely should use `FT_Property_Set`.  However, as done in
other modules, we declare (some of) the properties as 'experimental'
in the documentation so that we can change or remove them if
necessary.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

> Ok to remove. This only optimizes mistaken calls to FT_Render_Glyph on
> bitmap fonts. A related question is whether we need FT_LOAD_TARGET_SDF
> for FT_Load_Glyph?

I don't think we need `FT_LOAD_TARGET_SDF', I much prefer loading it with
`FT_LOAD_DEFAULT' and then rendering it separately. However to keep it
consistent with the rest of the renderers we might need to add it.

> I would be less worried about FT_Property_Set if FreeType reserved the
> right to remove (ignore) or change properties when it is reasonable to
> do so, i.e. properties should not be considered a part of API.

Does that mean I shouldn't use `FT_Property_Set' ? For some parameters
such as `spread' there is no other way to dynamically set it.

Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Hi Anuj,

> > Alexei?
>
> Okay, I will probably only need to remove this case statement.
> ```
> case FT_GLYPH_FORMAT_BITMAP:   /* already a bitmap, don't do anything */
>break;
> ```

Ok to remove. This only optimizes mistaken calls to FT_Render_Glyph on
bitmap fonts. A related question is whether we need FT_LOAD_TARGET_SDF
for FT_Load_Glyph?

Indeed, the bitmap-to-sdf renderer should be separate as it hardly
shares anything.

I would be less worried about FT_Property_Set if FreeType reserved the
right to remove (ignore) or change properties when it is reasonable to
do so, i.e. properties should not be considered a part of API.

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > I don't think this is an issue.  For other rendering modes like LCD
> there are similar requirements, and platforms that are going to use
> SFDs certainly have plenty of memory.  It would be nice, however, if
> you can add this constraint to the documentation, and, if possible,
> also add a logging message that either predicts the necessary
> (approximate) amount of memory before the computation, and/or the
> actual memory use after generating an SFD.

Alright, I will add a log message about the exact memory used after
generating the SDF. Is there any profiling tool built into FreeType?
If there is the exact time can be logged as well.

> Don't worry about changing the internals!  You know best what to do,
> and we can discuss later whether your solution is the right approach.
> Regarding the second issue I think that you probably have to create a
> second renderer that shares most of the code with the original one.
> Alexei?

Okay, I will probably only need to remove this case statement.
```
case FT_GLYPH_FORMAT_BITMAP:   /* already a bitmap, don't do anything */
   break;
```
And yeah I like the idea of creating a seperate renderer, since it won't
be used much. The only cases I can think of where SDF from bitmap
will be generated is either for bitmap fonts or for glyphs with overlapping
contours( until I add something to remove the overlapps ). So, if it is a
separate module it can easily be disabled.

>> I have updated the demo, added bilinear filtering, shape
>> reconstruction and has all optimization modes which can be toggled.
>> I have attached the new list of keys.
>> (https://github.com/preversewharf45/ft2sdf-demo)
>
> Looks excellent!  Some items for the wishlist of `ftstd`:
>
> * A help menu showing the list of keys.
>
> * Easy navigation to get to large glyph indices easily.

I will later create the demo from scratch, so will add these.

> * It probably makes sense to not allow 'Width' values in
>   reconstruction mode to be larger than '(Spread - 1)' or something
>   similar, emitting a warning if this threshold is reached.  Otherwise
>   you get white boxes without a warning.

Yeah, I forgot about that. The `Width' shouldn't exceed `(Spread - 1)'
Thanks for pointing that out, I will add this while creating the new demo.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> I have updated the demo, added bilinear filtering, shape
> reconstruction and has all optimization modes which can be toggled.
> I have attached the new list of keys.
> (https://github.com/preversewharf45/ft2sdf-demo)

Looks excellent!  Some items for the wishlist of `ftstd`:

* A help menu showing the list of keys.

* Easy navigation to get to large glyph indices easily.

* It probably makes sense to not allow 'Width' values in
  reconstruction mode to be larger than '(Spread - 1)' or something
  similar, emitting a warning if this threshold is reached.  Otherwise
  you get white boxes without a warning.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > what about adding the other two methods (or one of them) and decide
> which one to choose with an option of the build system ? So one method
> fast build consume more memory than other one which is slower.

Yes, even I thought about that. We can also keep both the methods
and use `FT_Property_Set' to switch between the two, which I am
currently using to compare performance.

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Vincent Torri]

On Wed, Jul 15, 2020 at 7:14 AM Werner LEMBERG  wrote:
>
>
> > I have added all the optimization modes to the module.
>
> Great, thanks!
>
> > By far the fastest method is to subdivide the curve into a number of
> > line segments.  [...]
>
> OK.  I'm glad that you took the time to implement the various
> algorithms so that we have such a comparison.
>
> > The major downside of the BB and subdivision methods is that they
> > require a considerable amount of memory usage (almost 3x of the size
> > of bitmap) because we need to keep a track of the distances and
> > signs of all the grid points.
>
> I don't think this is an issue.  For other rendering modes like LCD
> there are similar requirements, and platforms that are going to use
> SFDs certainly have plenty of memory.  It would be nice, however, if
> you can add this constraint to the documentation, and, if possible,
> also add a logging message that either predicts the necessary
> (approximate) amount of memory before the computation, and/or the
> actual memory use after generating an SFD.

what about adding the other two methods (or one of them) and decide
which one to choose with an option of the build system ? So one method
fast build consume more memory than other one which is slower.

Vincent Torri

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> I have added all the optimization modes to the module.

Great, thanks!

> By far the fastest method is to subdivide the curve into a number of
> line segments.  [...]

OK.  I'm glad that you took the time to implement the various
algorithms so that we have such a comparison.

> The major downside of the BB and subdivision methods is that they
> require a considerable amount of memory usage (almost 3x of the size
> of bitmap) because we need to keep a track of the distances and
> signs of all the grid points.

I don't think this is an issue.  For other rendering modes like LCD
there are similar requirements, and platforms that are going to use
SFDs certainly have plenty of memory.  It would be nice, however, if
you can add this constraint to the documentation, and, if possible,
also add a logging message that either predicts the necessary
(approximate) amount of memory before the computation, and/or the
actual memory use after generating an SFD.

> I have updated the demo, added bilinear filtering, shape
> reconstruction and has all optimization modes which can be toggled.
> I have attached the new list of keys.
> (https://github.com/preversewharf45/ft2sdf-demo)

Thanks, will test soon.

> For now I would like to hold the outline implementation for now and
> go to the bitmap implementation.  After that the module can be used
> to generate SDF from bitmaps directly.  It will be pretty fast and
> will not require any additional memory other than the bitmap itself
> at a cost of reduced accuracy.

Excellent.

> However there are a few issues.
> 
> * `FT_Render_Glyph_Internal' break if the glyph format is already
>a bitmap.
>```
> case FT_GLYPH_FORMAT_BITMAP:   /* already a bitmap, don't do anything */
>   break;
>```
> * `FT_Lookup_Renderer' uses renderer format which is currently
>   `FT_GLYPH_FORMAT_OUTLINE' for the `sdf' module.  How can
>make it accept both outline and bitmap glyph format ?
> 
> I don't like the idea of changing the internals of freetype so is
> there any other way in which this can be done ?

Don't worry about changing the internals!  You know best what to do,
and we can discuss later whether your solution is the right approach.
Regarding the second issue I think that you probably have to create a
second renderer that shares most of the code with the original one.
Alexei?


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello All,

>> The basic sdf module is done, now that is left is to
>> optimize it, fix bugs etc. I will start by optimizing it.
>> I have decided to test three optimization method:
>> * Bounding box (BB)
>> * Subdivisions
>> * And also a coarse grid method that Behdad suggested.

I have added all the optimization modes to the module.
By far the fastest method is to subdivide the curve into
a number of line segments.The coarse grid method is
the slowest unless I am doing something wrong.
[
  Behdad, I divided the grid into 8x8 coarse grid and then
  to find the relevant edges of the coarse grid I am using
  the spread value and the half diagonal of the coarse grid.
  So if any edge's nearest distance to a coarse grid is greater
  then spread + ( coarse grid diagonal length / 2 ) I discard it.
  It works well and for each coarse grid I am getting around
  4 edges, but it's still pretty slower than the bounding box and
  the subdivision method. If you need more details please let
  me know.
]
The major downside of the BB and subdivision methods is
that they require a considerable amount of memory usage
(almost 3x of the size of bitmap) because we need to keep
a track of the distances and signs of all the grid points.

>> The image is upside down in linux maybe because in linux the y = 0
>> is at the the top which is different from windows. I'll fix it soon
>> while adding bilinear filtering.

I have updated the demo, added bilinear filtering, shape
reconstruction and has all optimization modes which can
be toggled. I have attached the new list of keys.
(https://github.com/preversewharf45/ft2sdf-demo)

For now I would like to hold the outline implementation for
now and go to the bitmap implementation. After that the module
can be used to generate SDF from bitmaps directly. It will be
pretty fast and will not require any additional memory other than
the bitmap itself at a cost of reduced accuracy. However there
are a few issues.

* `FT_Render_Glyph_Internal' break if the glyph format is already
   a bitmap.
   ```
case FT_GLYPH_FORMAT_BITMAP:   /* already a bitmap, don't do anything */
  break;
   ```
* `FT_Lookup_Renderer' uses renderer format which is currently
  `FT_GLYPH_FORMAT_OUTLINE' for the `sdf' module. How can
   make it accept both outline and bitmap glyph format ?

I don't like the idea of changing the internals of freetype so is there
any other way in which this can be done ?

Thanks in advance,
Anuj

- KEYS --

Esc / 'q'  : Quit the program.
   
'z': Scale up (This doesn't change point size, it
 just zoom the image.)
'x': Scale Down (same as above)
   
'Up Arrow' : Increase point size by 1.
'Down Arrow'   : Decrease point size by 1.
'Page UP'  : Increase point size by 25.
'Page Down': Decrease point size by 25.

'Left Arrow'   : Previous Glyph
'Right Arrow'  : Next Glyph

'o': Increase 'spread' by 1.
'l': Decrease 'spread' by 1.

'w', 's',  : Move the glyph Up/Down.
'a', 'd'   : Move the glyph Left/Right.

'f': Toggle between Nearest and Bilinear filtering.

-- OPTIMIZATION MODES --

Press the relevant keys to change the optimization mode.

'1': None (All grid points against all contours
 and all edges.)

'2': Bounding Box (Use BB to improve performance
 by only checking the grid points in the 
 bounding box of a edge.)

'3': Subdivision (Subdivide the curve into lines
 then only check the grid points near the
 line segment) [FASTEST]

'4': Coarse Grid (Divide the area into a number of
 coarse grids and then only check the edges
 relevant to the coarse grid.)

-- RECONSTRUCT IMAGE FROM SDF --

'r': Toggle between Reconstruction and Raw view.

** The keys below are only for Reconstruction mode **
-

'i': Increase Width. (Make the text bolder)
'k': Decrease Width. (Make the text thinner)

'u': Increase Edge. (Increase smoothness around
 the edges, similar to anti-aliasing)
'j': Decrease Edge. (Decrease smoothness around
 the edges, makes the text sharper)

- END --

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

>> It's actually `--recurse-submodules`..
> 
> I think they are both the same. They both do exactly the same thing
> for git clone.  The ` --recurse-submodules` was added later to avoid
> confusion or something.

Interesting.  The manpage of git 2.26.2 no longer contains a reference
to `--recursive`.

> The image is upside down in linux maybe because in linux the y = 0
> is at the the top which is different from windows. I'll fix it soon
> while adding bilinear filtering.

Thanks!


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 >> You can check out the demo here:
>> https://github.com/preversewharf45/ft2sdf-demo The build process is
>> the same as ft2-demos. The freetype2 library is added as a submodule
>> so use --recursive.
>
> It's actually `--recurse-submodules`..

I think they are both the same. They both do exactly the same thing
for git clone.
The ` --recurse-submodules` was added later to avoid confusion or
something.
https://www.reddit.com/r/git/comments/f26qmf/difference_between_recursive_and_recursesubmodules/

> On GNU/Linux the image is mirrored vertically – do you mean this with
> 'only works properly on Windows'?

No, I was talking about the weird computation differences in linux and
windows which I fixed in this commit:
https://git.savannah.gnu.org/cgit/freetype/freetype2.git/commit/?h=anuj-distance-field=36e59b55a603c57146ffbf43b4dc93473e3aaa62
The image is upside down in linux maybe because in linux the y = 0
is at the the top which is different from windows. I'll fix it soon while
adding bilinear filtering.

> Besides that: Very nice!

Thank you very much for checking it out.

Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> You can check out the demo here:
> https://github.com/preversewharf45/ft2sdf-demo The build process is
> the same as ft2-demos. The freetype2 library is added as a submodule
> so use --recursive.

It's actually `--recurse-submodules`...

> And it only works properly on windows.

On GNU/Linux the image is mirrored vertically – do you mean this with
'only works properly on Windows'?

Besides that: Very nice!


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > from a mathematical point of view only, you are doing a/64 + b/64
> (this line and also a bit above, which can be factorized like that :
> (a+b)/64. Maybe it is needed to divide first by 64 each term, i don't
> know, i just wanted to point this

I did this to avoid a few divisions and it works fine.

Took me long enough to find out,
The problem was with negating unsigned int.
https://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/sdf/ftsdfrend.c?h=anuj-distance-field#n228
I was subtracting an unsigned int from a signed long
which caused the value to wrap around. It never happened
on windows even with gcc, I'm glad I tested it on linux.

Thanks for your input.

I've updated the demo and it works fine now.

The basic sdf module is done, now that is left is to
optimize it, fix bugs etc. I will start by optimizing it.
I have decided to test three optimization method:
* Bounding box
* Subdivisions
* And also a coarse grid method that Behdad suggested.

Vincent suggested some good tools for profiling. I'm gonna
use linux so if you have any more suggestions please do let
me know, profiling is pretty new to me.
I will also keep updating the demo program.

Thanks for the feedback on the evaluation,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Vincent Torri]

On Sat, Jul 4, 2020 at 11:52 AM Werner LEMBERG  wrote:
>
>
> > I have created the demo program, it can be used to view raw SDF
> > without any bilinear filtering and there is no way to reconstruct
> > fonts from SDF because again it doesn't have bilinear filtering.  I
> > will add that soon.
>
> Thanks, will test soon.
>
> > There is a pretty weird issue that I ran into while testing the demo
> > on linux which doesn't happen on windows whatsoever. On linux
> > various computations give wrong output.  For example, division of
> > -328032 by 64 gives 1811934202, whereas it should be -5125.
> > Moreover FT_Vector_Length returns negative values even for small
> > vectors.  There is no overflow so what am I doing wrong?  (One of
> > the places it happens is:
> > https://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/sdf/ftsdf.c?h=anuj-distance-field#n1129
> > where the `factor' is wrong after division with 64).

from a mathematical point of view only, you are doing a/64 + b/64
(this line and also a bit above, which can be factorized like that :
(a+b)/64. Maybe it is needed to divide first by 64 each term, i don't
know, i just wanted to point this


> I'm not aware of arithmetic computation problems within FreeType.
>
> Maybe you are experiencing a 32bit vs. 64bit issue?

if this is a problem of windows vs linux and 32 bits vs 64 bits, then
it is related to the 'long' type which is always a 32 bits type on
Windows, contrary to unix

>  It might also
> help to compile with UBSan to enable run-time checking of over- and
> underflow.  As an additional step, you could try to compile with clang
> instead of gcc.
>
>
> Werner
>

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> I have created the demo program, it can be used to view raw SDF
> without any bilinear filtering and there is no way to reconstruct
> fonts from SDF because again it doesn't have bilinear filtering.  I
> will add that soon.

Thanks, will test soon.

> There is a pretty weird issue that I ran into while testing the demo
> on linux which doesn't happen on windows whatsoever. On linux
> various computations give wrong output.  For example, division of
> -328032 by 64 gives 1811934202, whereas it should be -5125.
> Moreover FT_Vector_Length returns negative values even for small
> vectors.  There is no overflow so what am I doing wrong?  (One of
> the places it happens is:
> https://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/sdf/ftsdf.c?h=anuj-distance-field#n1129
> where the `factor' is wrong after division with 64).

I'm not aware of arithmetic computation problems within FreeType.

Maybe you are experiencing a 32bit vs. 64bit issue?  It might also
help to compile with UBSan to enable run-time checking of over- and
underflow.  As an additional step, you could try to compile with clang
instead of gcc.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello All,

>> One more thing.  I think the OpenGL demo is not good for everyone to
>> test, so I will working on a demo similar to 'ftview' in my spare
>> time.
>
> Great!

I have created the demo program, it can be used to view raw SDF without
any bilinear filtering and there is no way to reconstruct fonts from SDF
because
again it doesn't have bilinear filtering. I will add that soon.

There is a pretty weird issue that I ran into while testing the demo on
linux
which doesn't happen on windows whatsoever. On linux various computations
give wrong output. For example, division of  -328032 by 64 gives 1811934202,
whereas it should be -5125. Moreover FT_Vector_Length returns negative
values
even for small vectors. There is no overflow so what am I doing wrong?
(One of the places it happens is:
https://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/sdf/ftsdf.c?h=anuj-distance-field#n1129
 where the `factor' is wrong after division with 64).

I am using gcc version 9.3.0 (Ubuntu 9.3.0-10ubuntu2)
and GNU Make 4.2.1 to build.
If you need more details please let me know.

You can check out the demo here:
https://github.com/preversewharf45/ft2sdf-demo
The build process is the same as ft2-demos. The freetype2 library is added
as a submodule
so use --recursive. And it only works properly on windows. There is no
comments of help
screen so I'm attaching a text file for that.

Thanks,
Anuj
Usage: [ptsize] [font file]

Controls:

q/Esc: Exit

z: Increase Scale by 1
x: Decrease Scale by 1

Up Key   : Increase Pt Size by 1
Down Key : Decrease Pt Size by 1
Pg Up Key: Increase Pt Size by 25
Pg Down Key  : Decrease Pt Size by 25

w: Increase Spread by 1
s: Decrease Spread by 1

Left Key : Previous Glyph
Right Key: Next Glyph

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

On Sun, Jun 28, 2020 at 10:18 AM Anuj Verma  wrote:
> Apart from that, I thought about another optimization:
> Smooth rasterizer is ultra fast, it only takes a few nano-
> seconds to render. So we can embolden the outline by
> spread, render it with the smooth or monochrome rasterizer
> and that will give us all the points that we need to check. It
> can pair up well with the bounding box method.

Unfortunately, the emboldening algorithm has flaws... The stroker is
probably a bit more reliable but is much slower too.

The smooth renderer performance is a good benchmark to aspire to and I
think that the SDF renderer can be within reach. The distance to a
line is a cross product divided by the line length ignoring the
distances to the ends for a moment. The division by the length is the
same for all grid points in the neighborhood so it can be reused as
inverse length. The cross products are also interesting: they turn out
to be incremental from grid to grid point. Combining the two facts, it
is super fast to fill the neighborhood of a line using a single
division. Now you just have to deal with the ends trivially. That is
why I think that ultimately dividing the curves will win and the
performance will be comparable to the smooth renderer.

Best,
Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

> Do you know from your floating point version if q3 or r2 is larger
> when this happens? From your description it sounds like q3 is still
> larger than r2.

In this specific case where q3 becomes 0, r2 is always greater than
q3. But generally q3 can be greater than r2 in some cubic equation.

> In this case, if (r2 == 0) is missing here:

I just checked and r2 can also cause underflow, so yeah I should
check r2 == 0. But, this check only reduce the error it does not
eliminate it. I even checked increasing the precision but it still
happens, and increasing precision also creates a risk of overflow.
So, I might have to think of something else.

Apart from that, I thought about another optimization:
Smooth rasterizer is ultra fast, it only takes a few nano-
seconds to render. So we can embolden the outline by
spread, render it with the smooth or monochrome rasterizer
and that will give us all the points that we need to check. It
can pair up well with the bounding box method.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Hi Anuj,

Thanks for the reference:
> This happens because of underflow, if you check the `solve_cubic_equation'
> function 
> (https://github.com/preversewharf45/freetype2-sdf/blob/dcedba69423fc169a9ca95b6391902e1cf27e0b6/src/sdfgen.c#L490)
> there is a term `q3' which is cube of term `q'. So, in cases where is `q' is
> pretty small `q3' becomes zero. And later in the algorithm we have to take
> the `cube_root' of the term (q3 + r2) to find the final roots. Now because of
> underflow the impact of `q' on the final output is zero. That is why the roots
> davaiate and we get a wrong value. In some cases the deviation is quite high.

Do you know from your floating point version if q3 or r2 is larger
when this happens? From your description it sounds like q3 is still
larger than r2.
In this case, if (r2 == 0) is missing here:
https://github.com/preversewharf45/freetype2-sdf/blob/dcedba69423fc169a9ca95b6391902e1cf27e0b6/src/sdfgen.c#L577


Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> One more thing.  I think the OpenGL demo is not good for everyone to
> test, so I will working on a demo similar to 'ftview' in my spare
> time.

Great!


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

One more thing. I think the OpenGL demo is not
good for everyone to test, so I will working on a
demo similar to 'ftview' in my spare time.

On Sat, Jun 27, 2020, 8:21 PM Anuj Verma  wrote:

>
> >> A) Checking all grid points:15.43 seconds (~154ms per glyph average)
> >> B) Bounding Box check: 0.898 seconds (~8.98ms per glyph average)
> >> C) Subdivision method : 0.665 seconds (~6.65ms per glyph average)
> >
> > [for subdivision I equally divided the curve into 16 parts]
> > This is a tie between B and C because you can still find some
> > interesting optimizations
>
> Yes. For now I'll integrate the A method and then start optimizing, and I
> will
> also use some better tools that Vincent suggested for profiling.
>
> > There is another reason why subdividing cound faster: the bounding box
> > of a line is larger than two bounding boxes of its halfs, not
> > considering the padding (spread). However, 16 is too arbitrary. In
> > fact, in our antialiased renderer we divide until the curve deviates
> > from the line no more than 1/8th or a pixel, which could be more or
> > less than 16 depending on the size of the curve and its shape.
>
> I used 16 because It doesn't create jagged edges and looks exactly
> as method A. I believe the smooth renderer uses de Casteljau algorithm
> so I'll use that to subdivide.
>
> >> However, it is not always faster than the bounding box check, If we
> increase the
> >> spread to 16, then it gets a bit slower, because while checking the
> proximity the
> >> number of duplicate checks increases. But I believe that it can be
> avoided by
> >> only checking the grid points that are perpendicular to the line
> segment as you
> >> said in a previous mail.
> >
> > This sort of optimizations can be quite complex to implement though,
> > which might defeat the purpose.
>
> I thought about this, we can align the bounding box in the direction of
> the line,
> that way all the points inside the bounding box will be perpendicular, the
> only
> problem is to actually find the points inside the box, which can be a bit
> tricky.
>
> > Do you understand why the underflow happens? Is it because the curve
> > arches around the point and there exist multiple solutions, perhaps
> > almost an infinite number of solutions? Does the equation with all
> > coefficients substituted become quadratic or linear and you can solve
> > it differently? Your method is still very good.
>
> I explained this to Werner a while ago in this message:
> https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00127.html
> It happens when there is exactly one root of the cubic equiation and
> the curve gets really close so the point. I'm almost sure that It can be
> avoided by increasing the precision, but I haven't tried it yet.
>
> >> Finally, my opinion about subdividing is changed and I say that it's
> definitely worth
> >> subdividing the curve as it increases performance. But, as I said if
> the spread is
> >> more than 8 then it gets slower as of now without any optimizations and
> I still think
> >> we should keep the spread at least 32. So, to clarify weather 8 or 32
> is a good number
> >
> > I wonder if there is a way to test this using some SDF demo tool...
>
> I currently use an OpenGL demo, and in that even a spread of 2
> is enough to draw perfectly, so 8 would be plenty. I just think that
> 32 gives a good range. On the other hand 64 is overkill and it almost
> looks like a circle above 64.
> Either way the subdivision method will work even with 32, so there is
> no problem with the spread now. Moreover what is your opinion about
> implementing both the methods ?
>
> > But for 4 is only 2 bits...I remember you decided to use FT_F2Dot14.
> > What is the correct way of presenting SDF to a client? What is the
> > common practice?
>
> That will have to be changed now, I previously thought of normalizing the
> values, but that is not a good idea. Now, I'm thinking of using something
> like 8.8 and another option of 3.5. That way if the user has low memory
> they can use the 8bit version.
> In skia Jim uses 3.5 so that might be good. I'm still not sure about the
> format
> but that can easily be changed.
>
> Thanks,
> Anuj
>

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

>> A) Checking all grid points:15.43 seconds (~154ms per glyph average)
>> B) Bounding Box check: 0.898 seconds (~8.98ms per glyph average)
>> C) Subdivision method : 0.665 seconds (~6.65ms per glyph average)
>
> [for subdivision I equally divided the curve into 16 parts]
> This is a tie between B and C because you can still find some
> interesting optimizations

Yes. For now I'll integrate the A method and then start optimizing, and I
will
also use some better tools that Vincent suggested for profiling.

> There is another reason why subdividing cound faster: the bounding box
> of a line is larger than two bounding boxes of its halfs, not
> considering the padding (spread). However, 16 is too arbitrary. In
> fact, in our antialiased renderer we divide until the curve deviates
> from the line no more than 1/8th or a pixel, which could be more or
> less than 16 depending on the size of the curve and its shape.

I used 16 because It doesn't create jagged edges and looks exactly
as method A. I believe the smooth renderer uses de Casteljau algorithm
so I'll use that to subdivide.

>> However, it is not always faster than the bounding box check, If we
increase the
>> spread to 16, then it gets a bit slower, because while checking the
proximity the
>> number of duplicate checks increases. But I believe that it can be
avoided by
>> only checking the grid points that are perpendicular to the line segment
as you
>> said in a previous mail.
>
> This sort of optimizations can be quite complex to implement though,
> which might defeat the purpose.

I thought about this, we can align the bounding box in the direction of the
line,
that way all the points inside the bounding box will be perpendicular, the
only
problem is to actually find the points inside the box, which can be a bit
tricky.

> Do you understand why the underflow happens? Is it because the curve
> arches around the point and there exist multiple solutions, perhaps
> almost an infinite number of solutions? Does the equation with all
> coefficients substituted become quadratic or linear and you can solve
> it differently? Your method is still very good.

I explained this to Werner a while ago in this message:
https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00127.html
It happens when there is exactly one root of the cubic equiation and
the curve gets really close so the point. I'm almost sure that It can be
avoided by increasing the precision, but I haven't tried it yet.

>> Finally, my opinion about subdividing is changed and I say that it's
definitely worth
>> subdividing the curve as it increases performance. But, as I said if the
spread is
>> more than 8 then it gets slower as of now without any optimizations and
I still think
>> we should keep the spread at least 32. So, to clarify weather 8 or 32 is
a good number
>
> I wonder if there is a way to test this using some SDF demo tool...

I currently use an OpenGL demo, and in that even a spread of 2
is enough to draw perfectly, so 8 would be plenty. I just think that
32 gives a good range. On the other hand 64 is overkill and it almost
looks like a circle above 64.
Either way the subdivision method will work even with 32, so there is
no problem with the spread now. Moreover what is your opinion about
implementing both the methods ?

> But for 4 is only 2 bits...I remember you decided to use FT_F2Dot14.
> What is the correct way of presenting SDF to a client? What is the
> common practice?

That will have to be changed now, I previously thought of normalizing the
values, but that is not a good idea. Now, I'm thinking of using something
like 8.8 and another option of 3.5. That way if the user has low memory
they can use the 8bit version.
In skia Jim uses 3.5 so that might be good. I'm still not sure about the
format
but that can easily be changed.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

H Anuj,

On Fri, Jun 26, 2020 at 8:16 AM Anuj Verma  wrote:

> A) Checking all grid points:15.43 seconds (~154ms per glyph average)
> B) Bounding Box check: 0.898 seconds (~8.98ms per glyph average)
> C) Subdivision method : 0.665 seconds (~6.65ms per glyph average)
>
> [for subdivision I equally divided the curve into 16 parts]

This is a tie between B and C because you can still find some
interesting optimizations

> Yes, the subdivision method is the fastest, I was not expecting this to happen
> considering it increases the number of duplicate checks and also increases the
> number of lines. Anyway, it is faster because of obvious reasons (we don't 
> have
> to `solve_cubic_equation' which is the slowest part of the entire process).

There is another reason why subdividing cound faster: the bounding box
of a line is larger than two bounding boxes of its halfs, not
considering the padding (spread). However, 16 is too arbitrary. In
fact, in our antialiased renderer we divide until the curve deviates
from the line no more than 1/8th or a pixel, which could be more or
less than 16 depending on the size of the curve and its shape.

> However, it is not always faster than the bounding box check, If we increase 
> the
> spread to 16, then it gets a bit slower, because while checking the proximity 
> the
> number of duplicate checks increases. But I believe that it can be avoided by
> only checking the grid points that are perpendicular to the line segment as 
> you
> said in a previous mail.

This sort of optimizations can be quite complex to implement though,
which might defeat the purpose.

> Moreover the subdivision method gets rid of underflow issues that were caused
> while solving the cubic equation.

Do you understand why the underflow happens? Is it because the curve
arches around the point and there exist multiple solutions, perhaps
almost an infinite number of solutions? Does the equation with all
coefficients substituted become quadratic or linear and you can solve
it differently? Your method is still very good.

> Finally, my opinion about subdividing is changed and I say that it's 
> definitely worth
> subdividing the curve as it increases performance. But, as I said if the 
> spread is
> more than 8 then it gets slower as of now without any optimizations and I 
> still think
> we should keep the spread at least 32. So, to clarify weather 8 or 32 is a 
> good number

I wonder if there is a way to test this using some SDF demo tool...

> I'm CCing Jim, as he uses SDF in skia he will be able to tell whether 8 is 
> enough.

Jim said 4. It is a good idea to have it adjustable. The glyph ppem
size defines the grid resolution and the spread/padding defines the
SDF radius. Both numbers are sufficient to allocate appropriate memory
for each glyph depending on its CBox.

But for 4 is only 2 bits...I remember you decided to use FT_F2Dot14.
What is the correct way of presenting SDF to a client? What is the
common practice?

Regards,
Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

> I assume spread means maximum distance.

Yes.

> We use a spread of 4, so 8 would be plenty. We use 4 mainly to keep the
glyph sizes under control,
> because a larger spread means a larger pad of texels around each glyph to
make use of that information.

So I guess 8 is enough for now. And btw it will be adjustable.

Thanks for the info,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Jim Van Verth]

I assume spread means maximum distance. We use a spread of 4, so 8 would be
plenty. We use 4 mainly to keep the glyph sizes under control, because a
larger spread means a larger pad of texels around each glyph to make use of
that information. Unfortunately we have some pretty severe memory
restrictions on low-end devices so that constrains a lot of what we can do.

On Fri, Jun 26, 2020 at 8:16 AM Anuj Verma  wrote:

> Hello Alexei,
>
> I tried the subdivision method that you suggested. I'll start with the
> performance.
>
> I generated 100 glyphs with a pixel size of 256 and a spread of 8
>
> A) Checking all grid points:15.43 seconds (~154ms per glyph average)
> B) Bounding Box check: 0.898 seconds (~8.98ms per glyph average)
> C) Subdivision method : 0.665 seconds (~6.65ms per glyph average)
>
> [for subdivision I equally divided the curve into 16 parts]
>
> Yes, the subdivision method is the fastest, I was not expecting this to
> happen
> considering it increases the number of duplicate checks and also increases
> the
> number of lines. Anyway, it is faster because of obvious reasons (we don't
> have
> to `solve_cubic_equation' which is the slowest part of the entire process).
>
> However, it is not always faster than the bounding box check, If we
> increase the
> spread to 16, then it gets a bit slower, because while checking the
> proximity the
> number of duplicate checks increases. But I believe that it can be avoided
> by
> only checking the grid points that are perpendicular to the line segment
> as you
> said in a previous mail.
> Moreover the subdivision method gets rid of underflow issues that were
> caused
> while solving the cubic equation.
>
> The only downside that I can think of is that if we increase the pixel
> size ridiculously
> then the number of divisions might have to be increased and that might
> make the
> process slower. But, that is just my intuition and I can't say anything
> for sure.
>
> Here is a screenshot (https://i.imgur.com/CUmGLUM.png) which compares the
> direct
> method to the subdivision method. They look exactly the same. I have also
> marked
> the effect of underflow on the SDF. The image is a bit large so you might
> have to zoom
> in to see the artifact.
>
> Finally, my opinion about subdividing is changed and I say that it's
> definitely worth
> subdividing the curve as it increases performance. But, as I said if the
> spread is
> more than 8 then it gets slower as of now without any optimizations and I
> still think
> we should keep the spread at least 32. So, to clarify weather 8 or 32 is a
> good number
> I'm CCing Jim, as he uses SDF in skia he will be able to tell whether 8 is
> enough.
> [
>   For Jim: Just to make it clear, `spread' is the max distance that will
> be present in the final
>   SDF output. What is the max spread that you use in your SDF and is 8
> enough ?
> ]
>
> I have uploaded the demo directly and not the separate standalone
> implementation
> you can check it out here :
> https://github.com/preversewharf45/freetype2-sdf-demo
> You, can directly go here:
> https://github.com/preversewharf45/freetype2-sdf-demo/blob/master/vendor/freetype2-sdf/src/sdfgen.c#L485
> to see the subdivision code. And yeah currently I'm subdividing equally
> which might
> not be good. So using a more efficient algorithm to subdivide the curve
> will be better.
>
> Sorry for a large mail and Thanks for your time,
> Anuj
>


-- 

Jim Van Verth | Software Engineer | jvanve...@google.com | 919-210-7664

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Vincent Torri]

On Fri, Jun 26, 2020 at 3:38 PM Anuj Verma  wrote:
>
> > you also have DrMemory on Windows memory errors and leaks, and the
> > Visual Studio tools
> > (https://docs.microsoft.com/en-us/visualstudio/profiling/getting-started-with-performance-tools?view=vs-2017)
>
> That would be much more convenient, I'll check these out.

also : http://www.codersnotes.com/sleepy/

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > you also have DrMemory on Windows memory errors and leaks, and the
> Visual Studio tools
> (
https://docs.microsoft.com/en-us/visualstudio/profiling/getting-started-with-performance-tools?view=vs-2017
)

That would be much more convenient, I'll check these out.

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Vincent Torri]

On Fri, Jun 26, 2020 at 3:01 PM Anuj Verma  wrote:
>
> > have you tried to use valgrind's callgrind tool + kcachegrind ? It can
> > be very helpful
>
> No, I haven't. The problem is that I use windows for development and
> valgrind doesn't work on windows.So, switching back and forth makes
> the process a bit tedious. I'll try to use it on WSL2.

you also have DrMemory on Windows memory errors and leaks, and the
Visual Studio tools
(https://docs.microsoft.com/en-us/visualstudio/profiling/getting-started-with-performance-tools?view=vs-2017)

Vincent Torri

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > have you tried to use valgrind's callgrind tool + kcachegrind ? It can
> be very helpful

No, I haven't. The problem is that I use windows for development and
valgrind doesn't work on windows.So, switching back and forth makes
the process a bit tedious. I'll try to use it on WSL2.

Thanks for suggestion,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Vincent Torri]

On Fri, Jun 26, 2020 at 2:17 PM Anuj Verma  wrote:
>
> Hello Alexei,
>
> I tried the subdivision method that you suggested. I'll start with the
> performance.
>
> I generated 100 glyphs with a pixel size of 256 and a spread of 8
>
> A) Checking all grid points:15.43 seconds (~154ms per glyph average)
> B) Bounding Box check: 0.898 seconds (~8.98ms per glyph average)
> C) Subdivision method : 0.665 seconds (~6.65ms per glyph average)
>
> [for subdivision I equally divided the curve into 16 parts]
>
> Yes, the subdivision method is the fastest, I was not expecting this to happen
> considering it increases the number of duplicate checks and also increases the
> number of lines. Anyway, it is faster because of obvious reasons (we don't 
> have
> to `solve_cubic_equation' which is the slowest part of the entire process).

have you tried to use valgrind's callgrind tool + kcachegrind ? It can
be very helpful

Vincent Torri

> However, it is not always faster than the bounding box check, If we increase 
> the
> spread to 16, then it gets a bit slower, because while checking the proximity 
> the
> number of duplicate checks increases. But I believe that it can be avoided by
> only checking the grid points that are perpendicular to the line segment as 
> you
> said in a previous mail.
> Moreover the subdivision method gets rid of underflow issues that were caused
> while solving the cubic equation.
>
> The only downside that I can think of is that if we increase the pixel size 
> ridiculously
> then the number of divisions might have to be increased and that might make 
> the
> process slower. But, that is just my intuition and I can't say anything for 
> sure.
>
> Here is a screenshot (https://i.imgur.com/CUmGLUM.png) which compares the 
> direct
> method to the subdivision method. They look exactly the same. I have also 
> marked
> the effect of underflow on the SDF. The image is a bit large so you might 
> have to zoom
> in to see the artifact.
>
> Finally, my opinion about subdividing is changed and I say that it's 
> definitely worth
> subdividing the curve as it increases performance. But, as I said if the 
> spread is
> more than 8 then it gets slower as of now without any optimizations and I 
> still think
> we should keep the spread at least 32. So, to clarify weather 8 or 32 is a 
> good number
> I'm CCing Jim, as he uses SDF in skia he will be able to tell whether 8 is 
> enough.
> [
>   For Jim: Just to make it clear, `spread' is the max distance that will be 
> present in the final
>   SDF output. What is the max spread that you use in your SDF and is 8 enough 
> ?
> ]
>
> I have uploaded the demo directly and not the separate standalone 
> implementation
> you can check it out here : 
> https://github.com/preversewharf45/freetype2-sdf-demo
> You, can directly go here: 
> https://github.com/preversewharf45/freetype2-sdf-demo/blob/master/vendor/freetype2-sdf/src/sdfgen.c#L485
> to see the subdivision code. And yeah currently I'm subdividing equally which 
> might
> not be good. So using a more efficient algorithm to subdivide the curve will 
> be better.
>
> Sorry for a large mail and Thanks for your time,
> Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

I tried the subdivision method that you suggested. I'll start with the
performance.

I generated 100 glyphs with a pixel size of 256 and a spread of 8

A) Checking all grid points:15.43 seconds (~154ms per glyph average)
B) Bounding Box check: 0.898 seconds (~8.98ms per glyph average)
C) Subdivision method : 0.665 seconds (~6.65ms per glyph average)

[for subdivision I equally divided the curve into 16 parts]

Yes, the subdivision method is the fastest, I was not expecting this to
happen
considering it increases the number of duplicate checks and also increases
the
number of lines. Anyway, it is faster because of obvious reasons (we don't
have
to `solve_cubic_equation' which is the slowest part of the entire process).

However, it is not always faster than the bounding box check, If we
increase the
spread to 16, then it gets a bit slower, because while checking the
proximity the
number of duplicate checks increases. But I believe that it can be avoided
by
only checking the grid points that are perpendicular to the line segment as
you
said in a previous mail.
Moreover the subdivision method gets rid of underflow issues that were
caused
while solving the cubic equation.

The only downside that I can think of is that if we increase the pixel size
ridiculously
then the number of divisions might have to be increased and that might make
the
process slower. But, that is just my intuition and I can't say anything for
sure.

Here is a screenshot (https://i.imgur.com/CUmGLUM.png) which compares the
direct
method to the subdivision method. They look exactly the same. I have also
marked
the effect of underflow on the SDF. The image is a bit large so you might
have to zoom
in to see the artifact.

Finally, my opinion about subdividing is changed and I say that it's
definitely worth
subdividing the curve as it increases performance. But, as I said if the
spread is
more than 8 then it gets slower as of now without any optimizations and I
still think
we should keep the spread at least 32. So, to clarify weather 8 or 32 is a
good number
I'm CCing Jim, as he uses SDF in skia he will be able to tell whether 8 is
enough.
[
  For Jim: Just to make it clear, `spread' is the max distance that will be
present in the final
  SDF output. What is the max spread that you use in your SDF and is 8
enough ?
]

I have uploaded the demo directly and not the separate standalone
implementation
you can check it out here :
https://github.com/preversewharf45/freetype2-sdf-demo
You, can directly go here:
https://github.com/preversewharf45/freetype2-sdf-demo/blob/master/vendor/freetype2-sdf/src/sdfgen.c#L485
to see the subdivision code. And yeah currently I'm subdividing equally
which might
not be good. So using a more efficient algorithm to subdivide the curve
will be better.

Sorry for a large mail and Thanks for your time,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Werner,

> It's not clear to me what you want to achieve.  Please elaborate.

For example If the user wants to enable multi-channel rendering which
gets rid of smooth corners, or to enable SIMD optimization. The simplest
example would be to enable overlapping contour support.

Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> I added functionality to set renderer properties (namely the
> `spread' parameter).  So, there is API for this `FT_Property_Set'
> and `FT_Property_Get'.  Is there any similar API for setting the
> renderer specific modes which is defined by the
> `FT_Renderer_SetModeFunc' function, or do I get the module from
> `FT_Get_Module' (`FT_Get_Renderer' will not return `sdf' renderer
> because it has same glyph format as the `smooth' renderer) and then
> call the function manually?

It's not clear to me what you want to achieve.  Please elaborate.

Up to now, `FT_Render_SetModeFunc` isn't used, so there wasn't any
need for an API.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

> You probably mean the slight "pulsing" inside. You are right, it
> should not happen. It might be the same effect as the one apparent on
> the miter line, or I am just seeing things.

Yes, it's kind of like discontinuities in the distances. I'll share a
screenshot once I subdivide the conic curve.

> The 8x8 neighborhood has larger distances diagonally than vertically
> or horizontally so they (like all distances) have to be clamped
> accordingly. You should probably also preset (memset) the grid to the
> same cutoff value with appropriate sign for the outside. Keep in mind
> that orientations are different for TrueType and Type1/CFF.

Yeah, I was not clamping them before. Now it looks good apart from the
sign.

> Even if you preset the field to an appropriately signed cutoff, there
> might still be unvisited inside regions of opposite signs. Those can
> be found by one pass over looking for large discontinuities, easily
> fixable by flipping the sign.

Yeah, even I was thinking of doing a single pass of all the rows from left
to right, flipping the distances as I go along. So I will try to implement
it
next. The corner checking still stands, it can't be avoided because at
corners
two lines give opposite signs, so to resolve this the corner checking has
to be
done.

>> Lastly, instead of checking the 8x8 neighborhood of the line segments, I
calculated the
>> bounding box of the line, increased it by 8 in the x and y direction and
used that to
>> calculate the distances. It is still very fast and doesn't result in
that hard edge (https://i.imgur.com/24Rz8eV.png).
>> We can even align the bounding box along the line and create a pretty
tight space. I
>> think it is worth giving it a try as well.
>
> Sure, I like it. This is a good test if splitting is worth anything.

Meanwhile here is the performance of using bounding box:
So, I generated 100 glyphs with a pixel size of 256 (which
in my opinion is more than enough for SDF) using a spread of
16:

* the previous method (checking all grid points): took 18.296 seconds for
all glyphs ( ~182 ms average )
* the bounding box method: took 1.487 seconds for all glyphs ( ~14.8 ms
average )

[I did the test on a ttf font so it only contains lines and conic curves]
They look exactly the same. Moreover the bounding box method can be made
even
faster by aligning it properly.

So, the next thing I'll do is the single pass phase to determine the sign of
unchecked grid points, and then I'll try the subdividing. The code is a
little
messed up right now, so I'll probably push it in 2-3 days.

Also, I was working on the integration part today. I added functionality
to set renderer properties (namely the `spread' parameter).  So, there is
API for this `FT_Property_Set' and `FT_Property_Get'. Is there any similar
API for setting the renderer specific modes which is defined by the
`FT_Renderer_SetModeFunc'
function, or do I get the module from `FT_Get_Module' (`FT_Get_Renderer'
will not return `sdf'
renderer because it has same glyph format as the `smooth' renderer) and
then call the
function manually ?

Thanks for your comments

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Hi Anuj,

Good job again!

> > foreach line
> >for proximal gridpoints
> >   do work
> >
> > where proximal is at most 8 grid units away. The rest is truncated
> > (clamped) at 8. I am choosing 8 because this is probably enough (or
> > not).
>
> I tried this method, and yes it is very (probably a lot) faster than checking 
> all the
> grid points. I did not check the performance but now I can generate 512 pixel 
> size
> glyphs within a click. However there are a few issues:
> * First, subdividing creates wrong results. I did not try subdividing bezier 
> curves. For
>   start I simply divided the line segments into 8 segments and I generated 
> SDF in the 8x8
>   neighborhood of those segments, but it results in wrong distances at some 
> points. I don't
>   know the exact reason for this so I will try to find it out.

You probably mean the slight "pulsing" inside. You are right, it
should not happen. It might be the same effect as the one apparent on
the miter line, or I am just seeing things.

> * Second, checking the 8x8 neighborhood causes hard edges. 
> (https://i.imgur.com/SunxGGU.png)

The 8x8 neighborhood has larger distances diagonally than vertically
or horizontally so they (like all distances) have to be clamped
accordingly. You should probably also preset (memset) the grid to the
same cutoff value with appropriate sign for the outside. Keep in mind
that orientations are different for TrueType and Type1/CFF.

>
> > The sign is tentative and flips on
> > updating the grid depending if it is to the right or to the left of
> > the line.
>
> * It is correct to determine the sign this way, but it only determines the 
> sign of the
>   pixels that we are actually checking. There are still points left whose 
> sign is to
>   be determined. We can clamp them to 8, but still the sign has to be 
> determined. I think
>   we can use this for that: 
> https://skia.googlesource.com/skia/+/refs/heads/master/src/gpu/GrDistanceFieldGenFromVector.cpp#23

Even if you preset the field to an appropriately signed cutoff, there
might still be unvisited inside regions of opposite signs. Those can
be found by one pass over looking for large discontinuities, easily
fixable by flipping the sign.

> Lastly, instead of checking the 8x8 neighborhood of the line segments, I 
> calculated the
> bounding box of the line, increased it by 8 in the x and y direction and used 
> that to
> calculate the distances. It is still very fast and doesn't result in that 
> hard edge (https://i.imgur.com/24Rz8eV.png).
> We can even align the bounding box along the line and create a pretty tight 
> space. I
> think it is worth giving it a try as well.

Sure, I like it. This is a good test if splitting is worth anything.

Thank you for your hard work!
Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

> I actually think that it is faster
>
> foreach line
>for proximal gridpoints
>   do work
>
> where proximal is at most 8 grid units away. The rest is truncated
> (clamped) at 8. I am choosing 8 because this is probably enough (or
> not).

I tried this method, and yes it is very (probably a lot) faster than
checking all the
grid points. I did not check the performance but now I can generate 512
pixel size
glyphs within a click. However there are a few issues:
* First, subdividing creates wrong results. I did not try subdividing
bezier curves. For
  start I simply divided the line segments into 8 segments and I generated
SDF in the 8x8
  neighborhood of those segments, but it results in wrong distances at some
points. I don't
  know the exact reason for this so I will try to find it out.
* Second, checking the 8x8 neighborhood causes hard edges. (
https://i.imgur.com/SunxGGU.png)

> The sign is tentative and flips on
> updating the grid depending if it is to the right or to the left of
> the line.

* It is correct to determine the sign this way, but it only determines the
sign of the
  pixels that we are actually checking. There are still points left whose
sign is to
  be determined. We can clamp them to 8, but still the sign has to be
determined. I think
  we can use this for that:
https://skia.googlesource.com/skia/+/refs/heads/master/src/gpu/GrDistanceFieldGenFromVector.cpp#23

Lastly, instead of checking the 8x8 neighborhood of the line segments, I
calculated the
bounding box of the line, increased it by 8 in the x and y direction and
used that to
calculate the distances. It is still very fast and doesn't result in that
hard edge (https://i.imgur.com/24Rz8eV.png).
We can even align the bounding box along the line and create a pretty tight
space. I
think it is worth giving it a try as well.

Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

On Sat, Jun 20, 2020 at 6:32 PM Behdad Esfahbod  wrote:
> Systems without an FPU are vastly less common than they were 20 years ago.  
> They still exist, and is a defendable position to want FreeType to continue 
> to work on those systems, however:
>
>   - Compilers and kernels have stepped up to provide floating-point emulation 
> libraries which work transparently to the client code.  That is, introducing 
> limited use of float in FreeType is by no means an impediment to those 
> building the library for systems without FPU.  Even if that was not true, the 
> SDF module can be easily disabled,

Behdad,

The FT_Fixed underflows and overflows, which are definitely easier to
trigger, makes you think about degenerate cases in your logic and
equations. This is a huge benefit, not an obstacle. In the case of SDF
the distance always exists and is finite. Once the degenerate case is
identified using FT_Fixed, it is better to solve it using an
alternative formula or method, which always exists and is usually
simpler. This will make the code more stable and robust. IMHO, this
discipline makes FreeType indestructible.

I would love to see GPU, FPU, SIMD, compiler features, etc...
Unfortunately, there is maintenance cost associated with it. Just two
days ago 
http://git.savannah.gnu.org/cgit/freetype/freetype2.git/commit/?id=d924c5cf7e5554b22f7edfcb9e98670c4c02c3f0
and that was your contribution but the burden of fixing is on Werner.

It should have been easy to blow FreeType from the face of the Earth
with a faster GPU or SIMD rasterizer or using GPU, but for some reason
for 20 years nobody dared.

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Behdad,

> I have.  In 2018 Nicolas Rougier and I presented a mini-course at
SIGGRAPH that covered all the SDF-based experiments of the past 10 / 15
years.
> If you haven't reviewed those, I suggest you do.  Unfortunately there's
no video and the slides are low resolution:
>
>
https://www.slideshare.net/NicolasRougier1/siggraph-2018-digital-typography
>
> In particular, I advise that you read the 2018-Langyel paper, which is
what's in sluglibrary.com:
>
>  http://www.terathon.com/i3d2018_lengyel.pdf
>
> Because if you follow my line of reasoning in my previous messages and
the rest of this message, I'm advising that you implement what basically
will be Lengyel's algorithm on the CPU.

I looked at the SIGGRAPH slides, it is interesting. Thanks for sharing.
I will read the Lengyel paper and will let you know.

> I thought about that a lot and did some research. This is a good summary:
>
>
https://math.stackexchange.com/questions/2432348/what-is-stopping-criteria-for-newtons-method/2433475#2433475
>
> Basically, if the solution is pulled out of [0,1] range, you can clamp
them.  If they keep pulling out again right after clamping, you can
discard.
> That post also suggests that what you are seeing was caused by your
fixed-point limitations.  Were you testing with float or fixed?:

I was testing it with fixed, I will again test it with floats and let you
know. Thanks for sharing the link.

>> * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2
> is enough for always finding the closest point.
> >> That would speed up significantly.
>
> > It will certainly speed up the process a lot. But in the current
> implementation here are the results:
> > A) MAX_DIVISIONS=2 : https://i.imgur.com/B9Q8Kpa.png
> > B) MAX_DIVISIONS=4 : https://i.imgur.com/1sbl9MP.png
> > Maybe if I don't break out when the factor falls outside [0.0, 1.0],
> MAX_DIVISIONS=2 might work.
> > But currently there are issues when using MAX_DIVISIONS=2.
>

[note the two images above are constructed using fixed point, I will
specify this from now on]

> I take that back.  Moreover, I'm convinced with 4 you still get very
noticeable artefacts with correctly-constructed fonts.

> When I was thinking through it last time I was mistakenly thinking that
there are three roots, whereas there are five.  Moreover, the positions of
the roots
> can be arbitrarily close to each other. Moreover, there's no fast
criteria to know the quality of the Raphson output or know when to
terminate.  As such, I
> believe the method cannot be made correct (as in not producing artefacts)
and fast at the same time.

If you are talking about the artifact at the corners, it is again caused
only while using fixed-point. Moreover, it also happens
in simple contours with only line segments (https://i.imgur.com/MZsNeHJ.png
- uses fixed). I will try to fix this for fixed-points.
Here is an SDF using floats: https://i.imgur.com/QSGCoIj.png - uses floats
and Raphson

> So I go back to my suggestion earlier on: that you convert cubics to a
series of quadratics.  Note how that conversion needs to be done once only,
not per pixel.
>
> For the conversion I suggest lifting the core ideas from cu2qu:
>
>   https://github.com/googlefonts/cu2qu/issues/10
>
> ideally withe cusp issue handled:
>
>  https://github.com/googlefonts/cu2qu/issues/6

I will try to optimize Newton's method (will also try to remove artifacts)
and will also check the performance of converting cubic to quadratic, then
we can finally decide what to use.

> I understand why you are doing it.  I believe it's not necessary.  Let me
try again.  See if you can prove the following for yourself.
> I have proved it and can share.  (Only if we had a mathematician around
;)).
>
> Lemma: if the closest point on curve [0,1] is to the endpoint at t=1 and
the cubic equation has no real root at t=1, the cubic equation must have at
least one real root at some t > 1.
> Similarly, if the closest point on curve [0,1] is to the endpoint at t=0
and the cubic equation has no real root at t=0, the cubic equation must
have at least one real root at some t > 1.
>
> As such, you just need to compute all real roots, clamp them to [0,1] and
remove duplicates.

[there is a typo, it should be t < 1 at the last point]

I tried to use this and it works exactly the same as before but faster.
Thanks for that.
I can't quite figure out the proof, here is what I think:
The cubic equation here is used to find the perpendicular to the curve.
Now, if we forget about the range [0, 1] the perpendicular can be anywhere.
Moreover, the slope of curve is given by a linear equation ( y = mx + c ),
that means it varies from [-90, 90] (tan(x) varies from [-inf, inf]: this
is also the reason why there has to be at least one real
root/perpendicular).
So, if we extend the endpoints we will get a perpendicular somewhere down
the
line, but I can't figure out why it is at t > 1 if the nearest point is at
t = 1
and vice versa. It will be great if 

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> One more thing, shouldn't it be a `minmum level of warnings.' ?
> http://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/smooth/ftgrays.c#n441

No, I don't think so.  I interpret the text as that you can switch on
the maximum number of compiler warnings by suppressing warning 4324.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > *I agree with Behdad.  Using functions, even for stuff that gets called*
> *only once, greatly enhances readability of code, among other things.*
> *So please proceed as you plan :-)*

Yes, I will. Thanks

>> *I strongly advise that you reconsider this.*
>
> *We discussed that already, didn't we?*

Yes, I will summarize. For now I will be using fixed points. And later
I will write code specific to platforms which support floats and SIMD.
I hope that is okay.

> *I beg to differ.  A GSoC project is not only to implement one thing in*
> *one way.  It is an opportunity to learn.  Anuj is now seeing both*
> *sides of the fixed-point mathematics medal, so to say; as soon as he*
> *will have mastered the project he knows *exactly* when to use it and*
>
*when to avoid. *

Before this project I never knew there was something like fixed-point. I
knew that at the end of the day floats are also stored in bit array, but
I didn't know that something like this is used until I started working
on this project.
At first it was a bit frustrating to work with them but I have gotten
used to them now. So yeah it has been a good learning opportunity :)

One more thing, shouldn't it be a `minmum level of warnings.' ?
http://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/smooth/ftgrays.c#n441

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> Systems without an FPU are vastly less common than they were 20
> years ago.  They still exist, and is a defendable position to want
> FreeType to continue to work on those systems, [...]

Honestly, I think this an issue even today – just think of the
Internet of Things stuff, which demands that even the sheets of my
toilet paper can communicate somehow...

>   - I have a *very* hard time imagining any system that has a
> programmable GPU, but no FPU.  As such, I find it completely
> nonsensical to ban using float for the SDF generation.

Here you definitely have a point.

> I strongly advise that you reconsider this.

We discussed that already, didn't we?

> And many other decisions that seem to be stuck in 20 years ago.  I'm
> working on writing a full assessment of FreeType as a project and
> will share in a new thread when that is ready.

Thanks for that.  I fully agree that a modern redesign of FreeType
would be a good thing.

> In the meantime, I like to see Anuj's time be spent in producing a
> **solid** SDF implementation, instead of fighting barriers that are
> not technically justified.

I beg to differ.  A GSoC project is not only to implement one thing in
one way.  It is an opportunity to learn.  Anuj is now seeing both
sides of the fixed-point mathematics medal, so to say; as soon as he
will have mastered the project he knows *exactly* when to use it and
when to avoid.

Deriving an alternative implementation using standard floating point
mathematics will be an easy exercise then, AFAICS.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

>>> Also I'm surprised that you haven't put the code get_min_distance
>>> code for each edge type into a function.  Would you prefer that I
>>> comment re these on github?
>>
>> I don't think that will be necessary.  I will fix that while adding
>> in FreeType.  That repository is just for testing and I might
>> delete it in the future.
> 
> I understand.  I find it using functions generously makes one's code
> develop and flow better.

I agree with Behdad.  Using functions, even for stuff that gets called
only once, greatly enhances readability of code, among other things.
So please proceed as you plan :-)


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

Hi Anuj,

On Tue, Jun 16, 2020 at 9:43 PM Anuj Verma  wrote:

> Hello Behdad,
>
> > First, let me congratulate you.  This is a very thorough and impressive
> piece of work for such a short time period.
>
> Thank you for that. Viktor's paper did help me a lot while writing the
> code. I guess you have already read his paper,
> but in case anyone is interested in reading it check this out:
> https://github.com/Chlumsky/msdfgen. It contains all
> the relevant information for generating SDF from outlines. Although I'm
> not using the full potential of the paper currently.
>

I have.  In 2018 Nicolas Rougier and I presented a mini-course at SIGGRAPH
that covered all the SDF-based experiments of the past 10 / 15 years.  If
you haven't reviewed those, I suggest you do.  Unfortunately there's no
video and the slides are low resolution:


https://www.slideshare.net/NicolasRougier1/siggraph-2018-digital-typography

In particular, I advise that you read the 2018-Langyel paper, which is
what's in sluglibrary.com:

  http://www.terathon.com/i3d2018_lengyel.pdf

Because if you follow my line of reasoning in my previous messages and the
rest of this message, I'm advising that you implement what basically will
be Lengyel's algorithm on the CPU.


> - I highly suggest you stick to float internally [...]
>
> I still think `float' is a better option for generating SDF, especially in
> lower resolution glyphs where fixed-point produces
> kind of straight lines instead of smooth curves(which is not noticable if
> you look at it briefly). But my concern is that
> FreeType doesn't use floats at the moment and I don't think it will be a
> good idea to add support for floats just for the
> sake of this project.
> It's a tradeoff between one thing or the other and I can't decide which
> would be the best considering the current state of
> library. I would say that I'm inclined on using fixed-point integers just
> because FreeType doesn't use them.
> Also, why doesn't FreeType use floats? Is it just because of platform
> which doesn't have floating point type? or are there
> more reasons? This question has been in my mind for quite some time.
>

I addressed that in my reply to Werner a few minutes ago.



> > Have you measured performance?  I'm fairly sure the float can be made
> both more robust and faster.
>
> I just did, here are the results with compiler optimization turned on
> using chrono library:
>
> A) Line Segment: ~0.026 microseconds
> B) Conic Bezier: ~0.168 microseconds
> C) Cubic Bezier: ~0.469 microseconds
>
> [I have also attached the gprof output in case you are interested. Note
> that the gprof output is without any compiler optimization]
> To compare it to fixed-point check here:
> https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00095.html
>

So basically you already showed that using fixed is slower and introduces
artifacts.  To me that was unnecessary as both were very well-understood to
anyone who has worked in this field.  But now that you have, I strongly
advise you stick to float.


> - Your Newton-Raphson is solid and your performance numbers look
> amazing.  I think you should stick with this approach instead of
> subdividing.
> > As was suggested by others, do experiment with Raphson on your quadratic
> as well.
>
> Yes, will try to use Raphson on quadratic, although I don't think it will
> be better than solving the cubic equation. And I will stick to it
> until I find something even faster.
>

I take that back for now.  It might be workable, but stick with what you
have.  We can find other ways to make your cubic-solving faster.  More
about my position-reversal on Raphson below.



> > * Currently you abandon as soon as factor falls outside of [0,1].
> That's wrong.  Factor might go out but come back in in the next iteration.
>
> I was doing that initially, but I saw that the factor goes `out' and when
> it come back `in' it has the same value as the previous `in' value.
> This causes 2 extra passes of a fairly expensive iteration, so I decided
> to break if it goes outside the range. But, yeah I will see if
> that is wrong and decide accordingly after further testing.
>

I thought about that a lot and did some research.  This is a good summary:


https://math.stackexchange.com/questions/2432348/what-is-stopping-criteria-for-newtons-method/2433475#2433475

Basically, if the solution is pulled out of [0,1] range, you can clamp
them.  If they keep pulling out again right after clamping, you can
discard.  That post also suggests that what you are seeing was caused by
your fixed-point limitations.  Were you testing with float or fixed?  This
is the part I'm referring to:
  "Occasionally, it is helpful to remember that Newton's method exhibits
one sided convergence in the limit, i.e. if the root is a simple, then the
residuals 푓(푥푛)f(xn) eventually have the same sign. Deviation from this
behavior indicates that you are pushing against the limitations imposed by
floating point arithmetic."

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

Werner!

On Wed, Jun 17, 2020 at 12:23 AM Werner LEMBERG  wrote:

> > Also, why doesn't FreeType use floats?  Is it just because of
> > platform which doesn't have floating point type?
>
> Yes.  The original intention of FreeType was to provide support for
> embedded devices, which usually are systems that have CPUs with very
> limited capabilities and a tiny amount of memory.  This goal hasn't
>

Reminds me of Colbert on Bush: "The greatest thing about this man is that
he’s steady. You know where he stands,” Colbert said about Bush. “He
believes the same thing Wednesday that he believed on Monday — no matter
what happened Tuesday.  Events can change; this man’s beliefs never will."

FreeType was designed in the 90s.  Back then there were embedded systems
that did not have an FPU.  There also existed embedded systems that did not
allow a library to have static writable data segment.  Both of those
limitations were ingrained into FreeType design.  Both are *still* actively
defended.  In the meantime the world has changed...

Systems without an FPU are vastly less common than they were 20 years ago.
They still exist, and is a defendable position to want FreeType to continue
to work on those systems, however:

  - Compilers and kernels have stepped up to provide floating-point
emulation libraries which work transparently to the client code.  That is,
introducing limited use of float in FreeType is by no means an impediment
to those building the library for systems without FPU.  Even if that was
not true, the SDF module can be easily disabled,

  - I have a *very* hard time imagining any system that has a programmable
GPU, but no FPU.  As such, I find it completely nonsensical to ban using
float for the SDF generation.

In HarfBuzz we started from the same position, exactly because of precedent
in FreeType.  But when we got to variable fonts, we acknowledged the shift
in the scene and just used float internally.  Broke nothing... And sure
there are users of FreeType who won't ever want HarfBuzz.  I'm not ruling
those use-cases out categorically.  But my arguments above address those
situations as well.

I strongly advise that you reconsider this.  And many other decisions that
seem to be stuck in 20 years ago.  I'm working on writing a full assessment
of FreeType as a project and will share in a new thread when that is
ready.  In the meantime, I like to see Anuj's time be spent in producing a
**solid** SDF implementation, instead of fighting barriers that are not
technically justified.

b



-- 
behdad
http://behdad.org/

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

On Tue, Jun 16, 2020 at 9:54 PM Anuj Verma  wrote:

>
> > Also I'm surprised that you haven't put the code get_min_distance code
> for each edge type into a function.
> > Would you prefer that I comment re these on github?
>
> I don't think that will be necessary. I will fix that while adding in
> FreeType. That repository is just for
> testing and I might delete it in the future.
>

I understand.  I find it using functions generously makes one's code
develop and flow better.  In this case I wanted to quickly test your
Newton-Raphson in isolation.  Sure, I know how to isolate it. :)

-- 
behdad
http://behdad.org/

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

On Wed, Jun 17, 2020 at 7:22 PM Alexei Podtelezhnikov 
wrote:

> Hi Anuj,
>
> Please let me finish my thoughts below...
>
> >> Each curved segment has a large number of neighboring grid points.
> >> each of which has a unique nearest projection on the curve. The curve
> >> is naturally sampled by these projection points a very large number of
> >> times and quite uniformly. Therefore, why not divide the curve into a
> >> large number of  segments to begin with and then just find whatever
> >> point is close to each grid? It could be a lot faster to find the
> >> distance this way.
>
> ...
> It is at this point I am asking why not just split the curve using De
> Casteljau's algorithm recursively a large number of times and
> calculate the distance field for a slightly jagged line to begin with.
>

Because then instead of one curve you have tens of tiny lines to walk
over.  The speed doesn't work.


> The distance field will do the magic regardless and thread the
> boundary smoothly through the grid...
>
> On Wed, Jun 17, 2020 at 1:08 AM Anuj Verma  wrote:
> > I guess this is similar to the Euclidean distance transform algorithm.
> > http://webstaff.itn.liu.se/~stegu/JFA/Danielsson.pdf
>
> No, I do not think this is it.
>
> > As I said before I will not leave out this option, I will try to
> implement this
> > and then we can compare the performance.
> [skip]
> > I don't find anything offending in your suggestions.
>
> ;)
>
>

-- 
behdad
http://behdad.org/

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

On Sat, Jun 20, 2020 at 7:38 AM Anuj Verma  wrote:
> Secondly, I did try subdividing the conic curves, for start I simply divided
> them into equal parts and used that to generate SDF. I saw that it require
> at least 32 divisions to produce a decent SDF, which in itself is quite slower
> than simply solving the cubic equation (and there can be many curves in the
> glyph).
> Moreover, I overlooked the fact that around the corners there is a corner 
> check
> involved, which is done to determine the sign correctly around corners. So,
> subdividing the curve also increases that which is around ~0.13 microseconds
> for each pixel around the corner.
>
> Looking at this I now think that it's not worth splitting the curve into 
> lines for
> generating the SDF.

Hi Anuj,

Thank you for the analysis. What you describe make sense if you:

foreach gridpoint
   foreach curve or line
  do work

Then, of course, you increase the inner loop by subdividing. I
actually think that it is faster

foreach line
   for proximal gridpoints
  do work

where proximal is at most 8 grid units away. The rest is truncated
(clamped) at 8. I am choosing 8 because this is probably enough (or
not).

As you walk along the (subdivided) path, you can optimize and update
distance for the points ahead (along the line) only, without looking
behind as those distances increase. The sign is tentative and flips on
updating the grid depending if it is to the right or to the left of
the line. You sort of sweep the grid proximal to the path. There is
another optimization possible, as you move along the subdivided curve,
you can only update grid points in a "orthogonal/normal" sector
roughly the size of the small turn corner, which is rather small.

Does it make sense?

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

First thing, here is the result of all the curves after using square
distances:

A) Line Segment: ~0.10 microseconds
B) Conic Curves: ~0.75 microseconds
C) Cubic Curves: ~0.71 microseconds

For comparison, the previous result with `FT_Vector_Length':

A) Line Segment: ~0.32 microseconds
B) Conic Bezier: ~1.08 microseconds
C) Cubic Bezier: ~1.25 microseconds

Secondly, I did try subdividing the conic curves, for start I simply divided
them into equal parts and used that to generate SDF. I saw that it require
at least 32 divisions to produce a decent SDF, which in itself is quite
slower
than simply solving the cubic equation (and there can be many curves in the
glyph).
Moreover, I overlooked the fact that around the corners there is a corner
check
involved, which is done to determine the sign correctly around corners. So,
subdividing the curve also increases that which is around ~0.13
microseconds
for each pixel around the corner.

Looking at this I now think that it's not worth splitting the curve into
lines for
generating the SDF. But I think for optimization it can be used, we can use
a coarse grid and subdivided curves to quickly check which line is closer
to the coarse grid, and then for the pixels in the coarse grid we only check
those curves. This will also not require the corver check since we are only
interested in absolute values. I think this can be faster but can't say
anything
for sure without profiling.

One more thing, shouldn't it be `minmum level of warnings.' ?
http://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/smooth/ftgrays.c#n441

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > *Ok. This means that square-distance might need [...]*

I agree that 181 is enough in a typical SDF grid, and anyway
if we generate a 8bit SDF bitmap it won't be able to represent
more than 127 signed values.
And I also agree that closer distances are more important than
distant distances if the user is simple using the SDF from simple
reconstruction. But, if we want to generate something like this:
( https://www.ronja-tutorials.com/2018/11/17/2d-sdf-combination.html )
then I think both types of distances are equally important.
By truncating do you mean normalizing in a range of [0, 181] or clamping
the values? In both cases I don't see any problem.

> *As I said above, the distant grid points contain [...]*

So, basically we subdivide the curve into small lines and use them to
generate the SDF, so as to make the process faster.
I will try to implement this tomorrow and see how it looks. And if it
works here is what I propose:

First for the squared distances. While generating SDF, I am using a `spread'
parameter which defines the max distance which will be present in the final
output (basically the output will have a range [-spread, spread]). So, In
case
the spread is small (< 181), we can use the squared distance to generate
the SDF.
And in case it is greater than 181 we simply use `FT_Vector_Length'.

Second if the subdivision method works and is both faster and doesn't
differ much from
the method I am currently using, then we will use it to generate SDF if the
glyph size
is small, because I think if the glyph size is large then there might be
too many
subdivisions and it will make the whole process slow. And if the glyph if
large then
we will use the current method. (of course this will depend if the
subdivision method
doesn't differ much from the actual SDF)

So we use separate implementations depending on the spread and the size of
the glyph.
How does it sound?

>
*Looks alright, including modules.mk . Have you checked
if it compiles? *

Thanks for checking it out. Yes, it does compile,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

On Thu, Jun 18, 2020 at 8:01 AM Anuj Verma  wrote:
>
> Hello Alexei,
>
> First, about using squared distances instead of `FT_Vector_Length', it
> is much faster to use squared distance. I tested it with a linear case and
> it comes around 0.114 microseconds, which is almost 65% faster than the
> original time of ~0.32 microsecond. It isn't 90% faster because there is
> one vector normalization which can't be avoided.
> Moving on, I think it's not possible to store squared distance  using 16.16
> fixed point because it can store a maximum of 32668 which is a square of ~181,
> so if the glyph is more than that, then there is a problem of overflow. If I
> am allowed to use decimal representation instead of binary fixed-point for
> internal computation then It might be possible.

Ok. This means that square-distance might need to be represented as
26.6, for example, but this also means that short distances will lose
accuracy. Hence the question, which distances contain more important
information? I would argue that it is the short distances to proximal
grid points because those contain the information on how to thread the
boundary through the grid. The distant grid points contain very little
additional information as they might even be closer to a different
segment. So, 16.16 is still better and truncating at 181 should not be
a problem. Also 181 is far considering a typical distance field grid
size. Is there a way you can test if truncated distance fields work
(TSDF)?

>
> > So each curve is sampled a large number of times [...]
>
> I'm not sure I understand it correctly, here is what I understood:
> You want to divide the curve in a large number of flat segments. Then
> calculate the distance of the pixels very near to the curve (the pixels
> will have a unique projection on the flat segments and no two will be
> the same). Now using these pixels (which have a unique projection),
> calculate the distances of the rest of the pixels/grid. Is that correct?

As I said above, the distant grid points contain very little
additional information or even "belong" to a different segment. All
grid points should be calculated and truncated alike. The idea is to
use a coarse *slightly* jagged representation of all curves and grid
points. FreeType smooth renderer walks along the outline (using
FT_Outline_Decompose) and generates small linear segments along the
curves.

>
> And finally I have a small request, I have added a new `sdf' module in
> my branch 
> (https://git.savannah.gnu.org/cgit/freetype/freetype2.git/log/?h=anuj-distance-field)
> Can you verify if everything is correct?

Looks alright, including modules.mk. Have you checked if it compiles?

Best,
Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

First, about using squared distances instead of `FT_Vector_Length', it
is much faster to use squared distance. I tested it with linear case and
it comes around 0.114 microseconds, which is almost 65% faster than the
original time of ~0.32 microsecond. It isn't 90% faster because there is
one vector normalization which can't be avoided.
Moving on, I think it's not possible to store squared distance  using 16.16
fixed point because it can store a maximum of 32668 which is a square of
~181,
so if the glyph is more than that, then there is a problem of overflow. If I
am allowed to use decimal representation instead of binary fixed-point for
internal computation then It might be possible.

> *So each curve is sampled a large number of times [...]*

I'm not sure I understand it correctly, here is what I understood:
You want to divide the curve in a large number of flat segments. Then
calculate the distance of the pixels very near to the curve (the pixels
will have a unique projection on the flat segments and no two will be
the same). Now using these pixels (which have a unique projection),
calculate the distances of the rest of the pixels/grid. Is that correct?

And finally I have a small request, I have added a new `sdf' module in
my branch (
https://git.savannah.gnu.org/cgit/freetype/freetype2.git/log/?h=anuj-distance-field
)
Can you verify if everything is correct?

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Hi Anuj,

Please let me finish my thoughts below...

>> Each curved segment has a large number of neighboring grid points.
>> each of which has a unique nearest projection on the curve. The curve
>> is naturally sampled by these projection points a very large number of
>> times and quite uniformly. Therefore, why not divide the curve into a
>> large number of  segments to begin with and then just find whatever
>> point is close to each grid? It could be a lot faster to find the
>> distance this way.

So each curve is sampled a large number of times and the distances are
recorded at the grid points. This distance information is about those
projection points, not the entire curve. Indeed, should we simply
connect those projection points with straight segments, we would get
exactly the same distance field. Ultimately, distance fields produce
smooth borders because they contain information on how to thread a
line between the grid points. It will be very close to the original
Bezier curve, but not exactly the same. It will also be close enough
to the jagged line though the projection points.

It is at this point I am asking why not just split the curve using De
Casteljau's algorithm recursively a large number of times and
calculate the distance field for a slightly jagged line to begin with.
The distance field will do the magic regardless and thread the
boundary smoothly through the grid...

On Wed, Jun 17, 2020 at 1:08 AM Anuj Verma  wrote:
> I guess this is similar to the Euclidean distance transform algorithm.
> http://webstaff.itn.liu.se/~stegu/JFA/Danielsson.pdf

No, I do not think this is it.

> As I said before I will not leave out this option, I will try to implement 
> this
> and then we can compare the performance.
[skip]
> I don't find anything offending in your suggestions.

;)

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

>> Please elaborate.  It's not clear to me what you are referring to,
>> and what the problem is about.
> 
> If you checkout this (https://i.imgur.com/hw4vrZL.png) which is an
> ascii character `0' at pixel size 31, you can see that fixed point
> deviates from the actual path slightly, which does not happen in
> case of float.  [...]

OK, thanks.

>> And if there is still some time left for GSoC I suggest that you
>> explore how to implement overlapping removal in FreeType, based on
>> the Skia code as Behdad suggested.
> 
> I would certainly love to do that even after GSoC.

Excellent :-)


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > *Please elaborate.  It's not clear to me what you are referring to, and*
> *what the problem is about.*

If you checkout this (https://i.imgur.com/hw4vrZL.png) which is an ascii
character `0' at pixel size 31, you can see that fixed point deviates from
the actual path slightly, which does not happen in case of float.
Moreover in some glyph (eg: https://i.imgur.com/aLmMPld.png) you can see
that
there are jagged edges.
This happens because of underflow, if you check the `solve_cubic_equation'
function (
https://github.com/preversewharf45/freetype2-sdf/blob/dcedba69423fc169a9ca95b6391902e1cf27e0b6/src/sdfgen.c#L490
)
there is a term `q3' which is cube of term `q'. So, in cases where is `q' is
pretty small `q3' becomes zero. And later in the algorithm we have to take
the `cube_root' of the term (q3 + r2) to find the final roots. Now because
of
underflow the impact of `q' on the final output is zero. That is why the
roots
davaiate and we get a wrong value. In some cases the deviation is quite
high.
I can perhaps increase the precision in case `q' is pretty small, or simply
use
Newton-Raphson similar to the cubic curve case.

> *And if there is still some time left for GSoC I suggest that you*
> *explore how to implement overlapping removal in FreeType, based on the*
> *Skia code as Behdad suggested.*

I would certainly love to do that even after GSoC.

Thanks for your explanation of the motive behind using fixed-point and
the summarization. Most of the things are clear to me now, I will start
writing the code as soon as I figure out how to add a new module.

Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

>> - I highly suggest you stick to float internally [...]
> 
> I still think `float' is a better option for generating SDF,
> especially in lower resolution glyphs where fixed-point produces
> kind of straight lines instead of smooth curves (which is not
> noticable if you look at it briefly).

Please elaborate.  It's not clear to me what you are referring to, and
what the problem is about.

> Also, why doesn't FreeType use floats?  Is it just because of
> platform which doesn't have floating point type?

Yes.  The original intention of FreeType was to provide support for
embedded devices, which usually are systems that have CPUs with very
limited capabilities and a tiny amount of memory.  This goal hasn't
changed.

However, looking at Behdad's SIMD code in HarfBuzz it is clear that
you have to implement this at a very low level, which is basically
assembler, to get the most profit.

To summarize: I want a good solution that fits into FreeType's general
philosophy first, this is, using fixed-point calculations only.  After
that, a special solution that encapsulates the critical hotspots with
specific code for specific CPUs (in particular the SSE instruction set
for x86 processors or its ARM equivalent) to accellerate them as much
as possible would be great.

And if there is still some time left for GSoC I suggest that you
explore how to implement overlapping removal in FreeType, based on the
Skia code as Behdad suggested.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

>> IMHO, in FreeType, SIMD support is something to be done in
>> addition, not as a replacement.  Since Anuj makes quick progress I
>> suggest that he first concentrates on the fixed-float route.  If
>> there is some time left we should check how SIMD can be
>> implemented.
> 
> Just to clarify, ` fixed-float' is the same as `fixed-point'
> integer?

Yes, sorry for the confusion.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

I forgot to add the gprof output. This is the final mail for sure.
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self  self total   
 time   seconds   secondscalls  us/call  us/call  name
 35.67  1.02 1.02 14600 0.01 0.01  sdf_vector_scale
 29.37  1.86 0.84 129379261 0.01 0.01  sdf_vector_add
 27.98  2.66 0.80  100 0.80 2.85  get_min_distance
  5.25  2.81 0.15 6000 0.00 0.00  sdf_vector_dot
  0.70  2.83 0.02  400 0.01 0.01  sdf_vector_sub
  0.35  2.84 0.01 2100 0.00 0.00  sdf_vector_length
  0.35  2.85 0.01  100 0.01 0.01  sdf_vector_normalize
  0.35  2.86 0.01 main
  0.00  2.86 0.001 0.00 0.00  _GLOBAL__sub_I_main
  0.00  2.86 0.001 0.00 0.00  
__static_initialization_and_destruction_0(int, int)

 % the percentage of the total running time of the
time   program used by this function.

cumulative a running sum of the number of seconds accounted
 seconds   for by this function and those listed above it.

 self  the number of seconds accounted for by this
secondsfunction alone.  This is the major sort for this
   listing.

calls  the number of times this function was invoked, if
   this function is profiled, else blank.

 self  the average number of milliseconds spent in this
ms/callfunction per call, if this function is profiled,
   else blank.

 total the average number of milliseconds spent in this
ms/callfunction and its descendents per call, if this
   function is profiled, else blank.

name   the name of the function.  This is the minor sort
   for this listing. The index shows the location of
   the function in the gprof listing. If the index is
   in parenthesis it shows where it would appear in
   the gprof listing if it were to be printed.

Copyright (C) 2012-2020 Free Software Foundation, Inc.

Copying and distribution of this file, with or without modification,
are permitted in any medium without royalty provided the copyright
notice and this notice are preserved.

 Call graph (explanation follows)


granularity: each sample hit covers 2 byte(s) for 0.35% of 2.86 seconds

index % timeself  childrencalled name
 
[1]100.00.012.85 main [1]
0.802.05 100/100 get_min_distance [2]
---
0.802.05 100/100 main [1]
[2] 99.70.802.05 100 get_min_distance [2]
1.020.00 14600/14600 sdf_vector_scale [3]
0.840.00 129379261/129379261 sdf_vector_add [4]
0.150.00 6000/6000 sdf_vector_dot [5]
0.020.00 400/400 sdf_vector_sub [6]
0.010.00 100/100 sdf_vector_normalize [7]
0.010.00 2000/2100 sdf_vector_length [8]
---
1.020.00 14600/14600 get_min_distance [2]
[3] 35.71.020.00 14600 sdf_vector_scale [3]
---
0.840.00 129379261/129379261 get_min_distance [2]
[4] 29.40.840.00 129379261 sdf_vector_add [4]
---
0.150.00 6000/6000 get_min_distance [2]
[5]  5.20.150.00 6000 sdf_vector_dot [5]
---
0.020.00 400/400 get_min_distance [2]
[6]  0.70.020.00 400 sdf_vector_sub [6]
---
0.010.00 100/100 get_min_distance [2]
[7]  0.40.010.00 100 sdf_vector_normalize [7]
0.000.00 100/2100 sdf_vector_length [8]
---
0.000.00 100/2100 sdf_vector_normalize [7]
0.010.00 2000/2100 get_min_distance [2]
[8]  0.30.010.00 2100 sdf_vector_length [8]
---
0.000.00   1/1   __libc_csu_init [315]
[310]0.00.000.00   1 _GLOBAL__sub_I_main [310]
0.000.00   1/1   
__static_initialization_and_destruction_0(int, int) [311]
---
0.000.00   1/1   _GLOBAL__sub_I_main [310]
[311]0.00.000.00   1 

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Werner,

> IMHO, in FreeType, SIMD support is something to be done in addition,
> not as a replacement.  Since Anuj makes quick progress I suggest that
> he first concentrates on the fixed-float route.  If there is some time
> left we should check how SIMD can be implemented.

Just to clarify, ` fixed-float' is the same as `fixed-point' integer?
And yeah, I am interested in adding SIMD support as well!

[sorry for spamming the list, this is the final mail for now]

Thanks,
Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Alexei,

> Each curved segment has a large number [...]

I guess this is similar to the Euclidean distance transform algorithm.
http://webstaff.itn.liu.se/~stegu/JFA/Danielsson.pdf

As I said before I will not leave out this option, I will try to implement
this
and then we can compare the performance.

> I am deeply sorry if this mathematical fact offends you in any way.
> Your code is good but please allow me to suggest an alternative,
> perhaps, faster implementation.

Please, don't apologize. I don't find anything offending in your
suggestions.
I realize that we are all in the same boat and we all want to make the
algorithm
as fast as possible. I think we can't comment on which algorithm is better
than the
other without checking the performance and other important factors. So, I
am open to
all of your suggestions and will choose the one that we all can agree on,
same for
`fixed-point' vs `float', same for subdivision or not.

Again Thank you for all of your suggestions,I will require them more in the
future.

Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

> Also I'm surprised that you haven't put the code get_min_distance code
for each edge type into a function.
> Would you prefer that I comment re these on github?

I don't think that will be necessary. I will fix that while adding in
FreeType. That repository is just for
testing and I might delete it in the future.

Anuj

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

 > After you do all this, you will realize that the speed is still a
concern.  Don't do bounding-box check.
> Classic way to do after is to split into a coarse grid and for each cell
find all edges that may be relevant.
> Then for pixels in each cell only process those edges.  This is what
GLyphy does and some of the other solutions as well.

This sounds interesting, I will definitely try to implement this and see
how it performs.

Thanks

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Behdad,

> First, let me congratulate you.  This is a very thorough and impressive
piece of work for such a short time period.

Thank you for that. Viktor's paper did help me a lot while writing the
code. I guess you have already read his paper,
but in case anyone is interested in reading it check this out:
https://github.com/Chlumsky/msdfgen. It contains all
the relevant information for generating SDF from outlines. Although I'm not
using the full potential of the paper currently.

> - I highly suggest you stick to float internally [...]

I still think `float' is a better option for generating SDF, especially in
lower resolution glyphs where fixed-point produces
kind of straight lines instead of smooth curves(which is not noticable if
you look at it briefly). But my concern is that
FreeType doesn't use floats at the moment and I don't think it will be a
good idea to add support for floats just for the
sake of this project.
It's a tradeoff between one thing or the other and I can't decide which
would be the best considering the current state of
library. I would say that I'm inclined on using fixed-point integers just
because FreeType doesn't use them.
Also, why doesn't FreeType use floats? Is it just because of platform which
doesn't have floating point type? or are there
more reasons? This question has been in my mind for quite some time.

> Have you measured performance?  I'm fairly sure the float can be made
both more robust and faster.

I just did, here are the results with compiler optimization turned on using
chrono library:

A) Line Segment: ~0.026 microseconds
B) Conic Bezier: ~0.168 microseconds
C) Cubic Bezier: ~0.469 microseconds

[I have also attached the gprof output in case you are interested. Note
that the gprof output is without any compiler optimization]
To compare it to fixed-point check here:
https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00095.html

> Specially, when and if going for SIMD, you get inverse-sqrt for float but
not int and that seems to be the slowest part of your work, which is
> normalizing vectors. And I agree, you should do everything in
squared-distance, then do a full pass over the results and do the (SIMD if
available)
> sqrt()ing.  I believe you still need normalizing vectors though.

SIMD sounds interesting and will definately be a plus point if I can
implement it. As for squared-distance, it isn't a problem while using float
but in case of fixed-point, I can't store the distance if it is more than
~180 in a 16.16 fixed point without causing overflow.

> - Your Newton-Raphson is solid and your performance numbers look
amazing.  I think you should stick with this approach instead of
subdividing.
> As was suggested by others, do experiment with Raphson on your quadratic
as well.

Yes, will try to use Raphson on quadratic, although I don't think it will
be better than solving the cubic equation. And I will stick to it
until I find something even faster.

> * Currently you abandon as soon as factor falls outside of [0,1].  That's
wrong.  Factor might go out but come back in in the next iteration.

I was doing that initially, but I saw that the factor goes `out' and when
it come back `in' it has the same value as the previous `in' value.
This causes 2 extra passes of a fairly expensive iteration, so I decided to
break if it goes outside the range. But, yeah I will see if
that is wrong and decide accordingly after further testing.

> * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2
is enough for always finding the closest point.
> That would speed up significantly.

It will certainly speed up the process a lot. But in the current
implementation here are the results:
A) MAX_DIVISIONS=2 : https://i.imgur.com/B9Q8Kpa.png
B) MAX_DIVISIONS=4 : https://i.imgur.com/1sbl9MP.png
Maybe if I don't break out when the factor falls outside [0.0, 1.0],
MAX_DIVISIONS=2 might work.
But currently there are issues when using MAX_DIVISIONS=2.

> - Your quadratic code always adds t=0 and t=1 as roots. You don't need
to. Only clamp the real roots to [0,1] range and remove duplicates.

That is done to also check the endpoints. There are cases where there are:
A) no real roots of the cubic equation (coefficient of x^3 = 0)
B) all real roots lie within the range [0.0, 1.0]

In these cases it becomes necessary to check the endpoints of the bezier
curve, hence t = 0 and  t = 1.

> - Your handling of two edges meeting at a corner is solid. That's exactly
what we do in GLyphy.
> However, I'm also now convinced that there is no way to produce SDF from
contours that might overlap
> [...]

I did use the winding sum and it works well. But it has issues and as you
said it's not possible to find
distance around the intersection. I see that FreeType rasterizer also has
issues while rendering overlapping
contours in Anti-Aliased mode. So, for now I won't add that this and later
when FreeType has functionality to
resolve overlapping contours I can easily add 

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

On Tue, Jun 16, 2020 at 11:02 AM Werner LEMBERG  wrote:

>
> > For SIMD, I studied what's available last year for HarfBuzz.  I
> > documented what I found here:
> >
> >   https://github.com/harfbuzz/harfbuzz/blob/simd/src/hb-simd.hh
>
> Thanks for the link, it's an interesting read.
>
> > If you use floats internally and fill in the distances, then you can
> > do SIMD passes at the end to do sqrt, clamping, and other things to
> > generate the output.  But even solving computing roots or the
> > Newton-Raphson can be done in SIMD for up to 8 samples at a time.
>
> IMHO, in FreeType, SIMD support is something to be done in addition,
> not as a replacement.


Absolutely.  It's implied and I agree that we must support non-SIMD.  All
projects I know have the same requirements.


>   Since Anuj makes quick progress I suggest that
> he first concentrates on the fixed-float route.  If there is some time
> left we should check how to SIMD can be implemented.
>

Agreed.  I pointed out in case it can inform how to organize the operations
such that SIMD benefit can be achieved later.  I think such organization
also produces faster code without SIMD.  Eg. doing a tight loop of just
sqrt()ing every pixel in the end allows the compiler to unroll the loop,
which also enables better use of the multiple pipelines in the CPU because
there's no data dependency.

-- 
behdad
http://behdad.org/

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> For SIMD, I studied what's available last year for HarfBuzz.  I
> documented what I found here:
> 
>   https://github.com/harfbuzz/harfbuzz/blob/simd/src/hb-simd.hh

Thanks for the link, it's an interesting read.

> If you use floats internally and fill in the distances, then you can
> do SIMD passes at the end to do sqrt, clamping, and other things to
> generate the output.  But even solving computing roots or the
> Newton-Raphson can be done in SIMD for up to 8 samples at a time.

IMHO, in FreeType, SIMD support is something to be done in addition,
not as a replacement.  Since Anuj makes quick progress I suggest that
he first concentrates on the fixed-float route.  If there is some time
left we should check how to SIMD can be implemented.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

For SIMD, I studied what's available last year for HarfBuzz.  I documented
what I found here:

  https://github.com/harfbuzz/harfbuzz/blob/simd/src/hb-simd.hh

If you use floats internally and fill in the distances, then you can do
SIMD passes at the end to do sqrt, clamping, and other things to generate
the output.  But even solving computing roots or the Newton-Raphson can be
done in SIMD for up to 8 samples at a time.

On Tue, Jun 16, 2020 at 8:51 AM Behdad Esfahbod  wrote:

> Hi Anuj,
>
> First, let me congratulate you.  This is a very thorough and impressive
> piece of work for such a short time period.  I read your code over a week
> ago but couldn't sit down and type this.  I see there has been lots of
> progress since.  I'll just summarize:
>
> - I highly suggest you stick to float internally.  Any fixed-point and you
> will inevitably hit rasterization issues no matter how hard you try.  This
> is a tried and tested failure path and I encourage you to stay away from
> it.  I see you did the fixed already.  Have you measured performance?  I'm
> fairly sure the float can be made both more robust and faster.  Specially,
> when and if going for SIMD, you get inverse-sqrt for float but not int and
> that seems to be the slowest part of your work, which is normalizing
> vectors.  And I agree, you should do everything in squared-distance, then
> do a full pass over the results and do the (SIMD if available) sqrt()ing.
> I believe you still need normalizing vectors though.
>
> - Your Newton-Raphson is solid and your performance numbers look amazing.
> I think you should stick with this approach instead of subdividing.  As was
> suggested by others, do experiment with Raphson on your quadratic as well.
> A couple things there:
>
>   * Currently you abandon as soon as factor falls outside of [0,1].
> That's wrong.  Factor might go out but come back in in the next iteration.
>
>   * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2
> is enough for always finding the closest point. That would speed up
> significantly.
>
> - Your quadratic code always adds t=0 and t=1 as roots. You don't need to.
> Only clamp the real roots to [0,1] range and remove duplicates.
>
> - Your handling of two edges meeting at a corner is solid. That's exactly
> what we do in GLyphy. However, I'm also now convinced that there is no way
> to produce SDF from contours that might overlap. Imagine a "+" sign that is
> two straight contours. You cannot find the distance around the
> intersection. That's really bad news :(. Removing overlaps is extremely
> tricky and so far we've stayed away from adding to FreeType. SkiaPathOps
> seems to be the most solid Open Source implementation. I don't have any
> suggestion as to how to proceed. I can only say do your work without
> overlaps and document that as a caveat. I'm sorry I told you you need to do
> winding tracking. That would help for other reasons, ie. when you have two
> clockwise circles inside each other and a counter-clockwise one inside
> those. The middle should be black. To get that black you need to count
> winding of a ray from point to infinity. That's not what you are doing.
> Again, okay to initially document that shortcoming.
>
> - I still think an option to get A8 output is desired, since that's enough
> for a respectable rendering in most situations and is 50% more efficient
> than a 16-bit. Also, most GPU hardware doesn't support 16-bit textures.
>
> - There was one place when I checked last week, that you were computing
> distance then squaring it instead of just getting the squared_distance for
> which you already had a function.
>
> - Your "spread" stuff. Spread is good, and user sets that depends on 1.
> the width of filter they gonna use for rasterizing, 2. minimum size they
> want to rasterize at. What that means is:
>
> * x_pad / y_pad should be set equal to spread,
>
> * The final normalizing you are doing based on max-distance is
> nonsensical. Makes the SDF unusable for rasterization.
>
> Re different filters, I found that they don't really matter. You can see
> my results in my slides / video:
>
> http://behdad.org/glyphy_slides.pdf
> https://vimeo.com/83732058
>
> That's all I remember.  I'll look into your latest code at some point.
>
> Regards,
> behdad
>
> On Sat, Jun 6, 2020 at 9:51 PM Anuj Verma  wrote:
>
>> Hello All,
>>
>>
>> *> Have you figured out FT_Fixed arithmetic? You still use floats in your
>> > code. I think you should convert to FT_Fixed first. *
>>
>> So, I have been trying to convert my code to FT_Fixed for a few days now
>> without any success.
>> I did manage to use fixed point for shapes with only line segments, but
>> because of small range
>> of 16.16 fixed point I have to use 26.6 for intermediate calculations and
>> because of that it
>> doesn't look good, (https://imgur.com/kUSIj3y) Here is a comparison
>> between float on
>> the right and 26.6 fixed point representation on the left.
>> As for bezier 

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

On Tue, Jun 16, 2020 at 9:49 AM Alexei Podtelezhnikov 
wrote:

> Anuj,
>
> Each curved segment has a large number of neighboring grid points.
> each of which has a unique nearest projection on the curve. The curve
> is naturally sampled by this projection points a very large number of
> times and quite uniformly. Therefore, why not divide the curve into a
> large number of  segments to begin with and then just find whatever
> point is close to each grid? It could be a lot faster to find the
> distance this way.
>

So... You subdivide the curves into lines.  Can you sketch what you do then?

I did think about "rasterizing" the outline and mark all pixels that have
distance < 1.0 to the outline, and then "propagate" the distance out.  But
as I've shown in my GLyphy talk, no matter how much I thought about this, I
found that there can be points far from the curve such that the closest
edge for this point is different from the closest edge for all its
neighboring pixels.  As such, the only way to use this optimization is if
each pixel kept a list of edges that are closest, within a range  That
then suggests that just using a coarse grid is even better, hence what I
suggested.

-- 
behdad
http://behdad.org/

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

On Tue, Jun 16, 2020 at 9:50 AM Werner LEMBERG  wrote:

> >>> - Your handling of two edges meeting at a corner is solid.  That's
> >>>   exactly what we do in GLyphy.  However, I'm also now convinced
> >>>   that there is no way to produce SDF from contours that might
> >>>   overlap.  Imagine a "+" sign that is two straight contours.  You
> >>>   cannot find the distance around the intersection.  That's really
> >>>   bad news :(.  Removing overlaps is extremely tricky and so far
> >>>   we've stayed away from adding to FreeType.
>
> This is an interesting idea.  I'm very open to add an API for removing
> overlaps.
>
> >>> SkiaPathOps seems to be the most solid Open Source implementation.
>
> URL, please.  A quick search on Google only shows video results.
>

Watch this video first so you appreciate the level of finesse that has gone
into it:

  https://www.youtube.com/watch?v=OmfliNQsk88

The code is part of Skia.  In FontTools we needed that so Cosimo & others
wrapped that into Python:

  https://github.com/fonttools/skia-pathops

SkiaPathOps can be compiled separately from the rest of Skia.  That was by
design.  When we started using this for font production, we hit a couple of
problems. If I remember correctly, it didn't necessarily retain the
direction of contours.  Ie. it worked for even-odd only.  They were open to
addressing those issues so it can be used for font production.  And I know
fontmake pipeline uses it now.  I've CC'ed Cosimo & Ben who can comment.

And yes, that library removes overlaps on curves directly.

b


> >>> I don't have any suggestion as to how to proceed.  I can only say
> >>> do your work without overlaps and document that as a caveat.
>
> Sounds like a good suggestion.
>
>
> Werner
>


-- 
behdad
http://behdad.org/

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

>>> - Your handling of two edges meeting at a corner is solid.  That's
>>>   exactly what we do in GLyphy.  However, I'm also now convinced
>>>   that there is no way to produce SDF from contours that might
>>>   overlap.  Imagine a "+" sign that is two straight contours.  You
>>>   cannot find the distance around the intersection.  That's really
>>>   bad news :(.  Removing overlaps is extremely tricky and so far
>>>   we've stayed away from adding to FreeType.

This is an interesting idea.  I'm very open to add an API for removing
overlaps.

>>> SkiaPathOps seems to be the most solid Open Source implementation.

URL, please.  A quick search on Google only shows video results.

>>> I don't have any suggestion as to how to proceed.  I can only say
>>> do your work without overlaps and document that as a caveat.

Sounds like a good suggestion.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Anuj,

Each curved segment has a large number of neighboring grid points.
each of which has a unique nearest projection on the curve. The curve
is naturally sampled by this projection points a very large number of
times and quite uniformly. Therefore, why not divide the curve into a
large number of  segments to begin with and then just find whatever
point is close to each grid? It could be a lot faster to find the
distance this way.

I am deeply sorry if this mathematical fact offends you in any way.
Your code is good but please allow me to suggest an alternative,
perhaps, faster implementation.

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

Also I'm surprised that you haven't put the code get_min_distance code for
each edge type into a function.  Would you prefer that I comment re these
on github?

On Tue, Jun 16, 2020 at 8:53 AM Behdad Esfahbod  wrote:

> Oh, I forgot:
>
> After you do all this, you will realize that the speed is still a
> concern.  Don't do bounding-box check.  Classic way to do after is to split
> into a coarse grid and for each cell find all edges that may be relevant.
> Then for pixels in each cell only process those edges.  This is what GLyphy
> does and some of the other solutions as well.
>
> On Tue, Jun 16, 2020 at 8:51 AM Behdad Esfahbod  wrote:
>
>> Hi Anuj,
>>
>> First, let me congratulate you.  This is a very thorough and impressive
>> piece of work for such a short time period.  I read your code over a week
>> ago but couldn't sit down and type this.  I see there has been lots of
>> progress since.  I'll just summarize:
>>
>> - I highly suggest you stick to float internally.  Any fixed-point and
>> you will inevitably hit rasterization issues no matter how hard you try.
>> This is a tried and tested failure path and I encourage you to stay away
>> from it.  I see you did the fixed already.  Have you measured performance?
>> I'm fairly sure the float can be made both more robust and faster.
>> Specially, when and if going for SIMD, you get inverse-sqrt for float but
>> not int and that seems to be the slowest part of your work, which is
>> normalizing vectors.  And I agree, you should do everything in
>> squared-distance, then do a full pass over the results and do the (SIMD if
>> available) sqrt()ing.  I believe you still need normalizing vectors though.
>>
>> - Your Newton-Raphson is solid and your performance numbers look
>> amazing.  I think you should stick with this approach instead of
>> subdividing.  As was suggested by others, do experiment with Raphson on
>> your quadratic as well. A couple things there:
>>
>>   * Currently you abandon as soon as factor falls outside of [0,1].
>> That's wrong.  Factor might go out but come back in in the next iteration.
>>
>>   * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2
>> is enough for always finding the closest point. That would speed up
>> significantly.
>>
>> - Your quadratic code always adds t=0 and t=1 as roots. You don't need
>> to. Only clamp the real roots to [0,1] range and remove duplicates.
>>
>> - Your handling of two edges meeting at a corner is solid. That's exactly
>> what we do in GLyphy. However, I'm also now convinced that there is no way
>> to produce SDF from contours that might overlap. Imagine a "+" sign that is
>> two straight contours. You cannot find the distance around the
>> intersection. That's really bad news :(. Removing overlaps is extremely
>> tricky and so far we've stayed away from adding to FreeType. SkiaPathOps
>> seems to be the most solid Open Source implementation. I don't have any
>> suggestion as to how to proceed. I can only say do your work without
>> overlaps and document that as a caveat. I'm sorry I told you you need to do
>> winding tracking. That would help for other reasons, ie. when you have two
>> clockwise circles inside each other and a counter-clockwise one inside
>> those. The middle should be black. To get that black you need to count
>> winding of a ray from point to infinity. That's not what you are doing.
>> Again, okay to initially document that shortcoming.
>>
>> - I still think an option to get A8 output is desired, since that's
>> enough for a respectable rendering in most situations and is 50% more
>> efficient than a 16-bit. Also, most GPU hardware doesn't support 16-bit
>> textures.
>>
>> - There was one place when I checked last week, that you were computing
>> distance then squaring it instead of just getting the squared_distance for
>> which you already had a function.
>>
>> - Your "spread" stuff. Spread is good, and user sets that depends on 1.
>> the width of filter they gonna use for rasterizing, 2. minimum size they
>> want to rasterize at. What that means is:
>>
>> * x_pad / y_pad should be set equal to spread,
>>
>> * The final normalizing you are doing based on max-distance is
>> nonsensical. Makes the SDF unusable for rasterization.
>>
>> Re different filters, I found that they don't really matter. You can see
>> my results in my slides / video:
>>
>> http://behdad.org/glyphy_slides.pdf
>> https://vimeo.com/83732058
>>
>> That's all I remember.  I'll look into your latest code at some point.
>>
>> Regards,
>> behdad
>>
>> On Sat, Jun 6, 2020 at 9:51 PM Anuj Verma  wrote:
>>
>>> Hello All,
>>>
>>>
>>> *> Have you figured out FT_Fixed arithmetic? You still use floats in
>>> your > code. I think you should convert to FT_Fixed first. *
>>>
>>> So, I have been trying to convert my code to FT_Fixed for a few days now
>>> without any success.
>>> I did manage to use fixed point for shapes with only line segments, but
>>> because of small range
>>> of 16.16 fixed 

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

On Mon, Jun 15, 2020 at 9:47 AM Alexei Podtelezhnikov 
wrote:

> On Mon, Jun 15, 2020 at 11:03 AM Anuj Verma  wrote:
> >>
> > > For linear segments, it will save more than 90% according to your
> > > table. Then you will see that splitting Bezier curves is not such a
> > > bad option. In general, Bezier curves are used in graphics because it
> > > is easy to split and flatten them. I would be very surprised if
> > > distance fields were different in this regard?
> >
> > Well, I'm not much familiar with the rendering part of bezier curve.
>
> This primer is fun to read with many interactive demos:
> https://pomax.github.io/bezierinfo/
> The main thing to recognize is that splitting a Bezier at t=0.5 and
> calculating the new set of control points for the halfs is lightning
> fast. If you continue doing so, the segments very quickly converge to
> almost straight (flat) segments.
>

Alexei,

I find your suggestion deeply offensive.  Have you looked at his code?  You
should.  You will learn a few things about writing good code.  This is the
kind of toxic behavior that has been deeply bothering me on this list but I
couldn't fully understand and verbalize.  I'm getting closer to that now.
I will start a new thread when I can write that down.  In the meantime I
think you should apologize to Anuj.


https://www.businessinsider.com/cond-nast-assistant-quit-ceo-gave-her-elements-of-style-2020-6





> > In distance fields I'm just concerned about finding the shortest
> distance as accurate and as fast as possible.
>
> Each split decreases deviation 4 times for a conic segment so that you
> can reach a given accuracy of your distance field and use only
> straight segments. The accuracy is defined by the grid resolution: it
> won't be visible to a human eye if the approximation deviates from a
> true curve by more than ~0.1 of the grid size.
>
>

-- 
behdad
http://behdad.org/

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

Oh, I forgot:

After you do all this, you will realize that the speed is still a concern.
Don't do bounding-box check.  Classic way to do after is to split into a
coarse grid and for each cell find all edges that may be relevant.  Then
for pixels in each cell only process those edges.  This is what GLyphy does
and some of the other solutions as well.

On Tue, Jun 16, 2020 at 8:51 AM Behdad Esfahbod  wrote:

> Hi Anuj,
>
> First, let me congratulate you.  This is a very thorough and impressive
> piece of work for such a short time period.  I read your code over a week
> ago but couldn't sit down and type this.  I see there has been lots of
> progress since.  I'll just summarize:
>
> - I highly suggest you stick to float internally.  Any fixed-point and you
> will inevitably hit rasterization issues no matter how hard you try.  This
> is a tried and tested failure path and I encourage you to stay away from
> it.  I see you did the fixed already.  Have you measured performance?  I'm
> fairly sure the float can be made both more robust and faster.  Specially,
> when and if going for SIMD, you get inverse-sqrt for float but not int and
> that seems to be the slowest part of your work, which is normalizing
> vectors.  And I agree, you should do everything in squared-distance, then
> do a full pass over the results and do the (SIMD if available) sqrt()ing.
> I believe you still need normalizing vectors though.
>
> - Your Newton-Raphson is solid and your performance numbers look amazing.
> I think you should stick with this approach instead of subdividing.  As was
> suggested by others, do experiment with Raphson on your quadratic as well.
> A couple things there:
>
>   * Currently you abandon as soon as factor falls outside of [0,1].
> That's wrong.  Factor might go out but come back in in the next iteration.
>
>   * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2
> is enough for always finding the closest point. That would speed up
> significantly.
>
> - Your quadratic code always adds t=0 and t=1 as roots. You don't need to.
> Only clamp the real roots to [0,1] range and remove duplicates.
>
> - Your handling of two edges meeting at a corner is solid. That's exactly
> what we do in GLyphy. However, I'm also now convinced that there is no way
> to produce SDF from contours that might overlap. Imagine a "+" sign that is
> two straight contours. You cannot find the distance around the
> intersection. That's really bad news :(. Removing overlaps is extremely
> tricky and so far we've stayed away from adding to FreeType. SkiaPathOps
> seems to be the most solid Open Source implementation. I don't have any
> suggestion as to how to proceed. I can only say do your work without
> overlaps and document that as a caveat. I'm sorry I told you you need to do
> winding tracking. That would help for other reasons, ie. when you have two
> clockwise circles inside each other and a counter-clockwise one inside
> those. The middle should be black. To get that black you need to count
> winding of a ray from point to infinity. That's not what you are doing.
> Again, okay to initially document that shortcoming.
>
> - I still think an option to get A8 output is desired, since that's enough
> for a respectable rendering in most situations and is 50% more efficient
> than a 16-bit. Also, most GPU hardware doesn't support 16-bit textures.
>
> - There was one place when I checked last week, that you were computing
> distance then squaring it instead of just getting the squared_distance for
> which you already had a function.
>
> - Your "spread" stuff. Spread is good, and user sets that depends on 1.
> the width of filter they gonna use for rasterizing, 2. minimum size they
> want to rasterize at. What that means is:
>
> * x_pad / y_pad should be set equal to spread,
>
> * The final normalizing you are doing based on max-distance is
> nonsensical. Makes the SDF unusable for rasterization.
>
> Re different filters, I found that they don't really matter. You can see
> my results in my slides / video:
>
> http://behdad.org/glyphy_slides.pdf
> https://vimeo.com/83732058
>
> That's all I remember.  I'll look into your latest code at some point.
>
> Regards,
> behdad
>
> On Sat, Jun 6, 2020 at 9:51 PM Anuj Verma  wrote:
>
>> Hello All,
>>
>>
>> *> Have you figured out FT_Fixed arithmetic? You still use floats in your
>> > code. I think you should convert to FT_Fixed first. *
>>
>> So, I have been trying to convert my code to FT_Fixed for a few days now
>> without any success.
>> I did manage to use fixed point for shapes with only line segments, but
>> because of small range
>> of 16.16 fixed point I have to use 26.6 for intermediate calculations and
>> because of that it
>> doesn't look good, (https://imgur.com/kUSIj3y) Here is a comparison
>> between float on
>> the right and 26.6 fixed point representation on the left.
>> As for bezier curves, there is almost always an overflow because while
>> solving 

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Behdad Esfahbod]

Hi Anuj,

First, let me congratulate you.  This is a very thorough and impressive
piece of work for such a short time period.  I read your code over a week
ago but couldn't sit down and type this.  I see there has been lots of
progress since.  I'll just summarize:

- I highly suggest you stick to float internally.  Any fixed-point and you
will inevitably hit rasterization issues no matter how hard you try.  This
is a tried and tested failure path and I encourage you to stay away from
it.  I see you did the fixed already.  Have you measured performance?  I'm
fairly sure the float can be made both more robust and faster.  Specially,
when and if going for SIMD, you get inverse-sqrt for float but not int and
that seems to be the slowest part of your work, which is normalizing
vectors.  And I agree, you should do everything in squared-distance, then
do a full pass over the results and do the (SIMD if available) sqrt()ing.
I believe you still need normalizing vectors though.

- Your Newton-Raphson is solid and your performance numbers look amazing.
I think you should stick with this approach instead of subdividing.  As was
suggested by others, do experiment with Raphson on your quadratic as well.
A couple things there:

  * Currently you abandon as soon as factor falls outside of [0,1].  That's
wrong.  Factor might go out but come back in in the next iteration.

  * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2
is enough for always finding the closest point. That would speed up
significantly.

- Your quadratic code always adds t=0 and t=1 as roots. You don't need to.
Only clamp the real roots to [0,1] range and remove duplicates.

- Your handling of two edges meeting at a corner is solid. That's exactly
what we do in GLyphy. However, I'm also now convinced that there is no way
to produce SDF from contours that might overlap. Imagine a "+" sign that is
two straight contours. You cannot find the distance around the
intersection. That's really bad news :(. Removing overlaps is extremely
tricky and so far we've stayed away from adding to FreeType. SkiaPathOps
seems to be the most solid Open Source implementation. I don't have any
suggestion as to how to proceed. I can only say do your work without
overlaps and document that as a caveat. I'm sorry I told you you need to do
winding tracking. That would help for other reasons, ie. when you have two
clockwise circles inside each other and a counter-clockwise one inside
those. The middle should be black. To get that black you need to count
winding of a ray from point to infinity. That's not what you are doing.
Again, okay to initially document that shortcoming.

- I still think an option to get A8 output is desired, since that's enough
for a respectable rendering in most situations and is 50% more efficient
than a 16-bit. Also, most GPU hardware doesn't support 16-bit textures.

- There was one place when I checked last week, that you were computing
distance then squaring it instead of just getting the squared_distance for
which you already had a function.

- Your "spread" stuff. Spread is good, and user sets that depends on 1. the
width of filter they gonna use for rasterizing, 2. minimum size they want
to rasterize at. What that means is:

* x_pad / y_pad should be set equal to spread,

* The final normalizing you are doing based on max-distance is nonsensical.
Makes the SDF unusable for rasterization.

Re different filters, I found that they don't really matter. You can see my
results in my slides / video:

http://behdad.org/glyphy_slides.pdf
https://vimeo.com/83732058

That's all I remember.  I'll look into your latest code at some point.

Regards,
behdad

On Sat, Jun 6, 2020 at 9:51 PM Anuj Verma  wrote:

> Hello All,
>
>
> *> Have you figured out FT_Fixed arithmetic? You still use floats in your
> > code. I think you should convert to FT_Fixed first. *
>
> So, I have been trying to convert my code to FT_Fixed for a few days now
> without any success.
> I did manage to use fixed point for shapes with only line segments, but
> because of small range
> of 16.16 fixed point I have to use 26.6 for intermediate calculations and
> because of that it
> doesn't look good, (https://imgur.com/kUSIj3y) Here is a comparison
> between float on
> the right and 26.6 fixed point representation on the left.
> As for bezier curves, there is almost always an overflow because while
> solving polynomials some
> large numbers are involved. I even tried using Newton's approximation, but
> it's too slow and still
> not as accurate as floating points. I did not try using 64 bit integers
> because they are not portable
> I guess and because of that I have to create separate implementations for
> 32 and 64 bit architecture.
> So, after comparing both, I prefer floats over fixed points because they
> satisfy both range and precision.
> I can try using 64 bit integers but I am not sure whether I will be able
> to finish the project on time or
> not because of 

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

On Mon, Jun 15, 2020 at 11:03 AM Anuj Verma  wrote:
>
>
> > For linear segments, it will save more than 90% according to your
> > table. Then you will see that splitting Bezier curves is not such a
> > bad option. In general, Bezier curves are used in graphics because it
> > is easy to split and flatten them. I would be very surprised if
> > distance fields were different in this regard?
>
> Well, I'm not much familiar with the rendering part of bezier curve.

This primer is fun to read with many interactive demos:
https://pomax.github.io/bezierinfo/
The main thing to recognize is that splitting a Bezier at t=0.5 and
calculating the new set of control points for the halfs is lightning
fast. If you continue doing so, the segments very quickly converge to
almost straight (flat) segments.

> In distance fields I'm just concerned about finding the shortest distance as 
> accurate and as fast as possible.

Each split decreases deviation 4 times for a conic segment so that you
can reach a given accuracy of your distance field and use only
straight segments. The accuracy is defined by the grid resolution: it
won't be visible to a human eye if the approximation deviates from a
true curve by more than ~0.1 of the grid size.

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Werner LEMBERG]

> Did you miss the last two mails from Alexei and me?  I missed a few
> mails a few days ago for no reason and even got a few duplicate
> mails.

I think I received everything.  It's only that sometimes I start
writing an e-mail and finish it hours later – in this case, Alexei has
answered meanwhile.


Werner

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

> For linear segments, it will save more than 90% according to your
> table. Then you will see that splitting Bezier curves is not such a
> bad option. In general, Bezier curves are used in graphics because it
> is easy to split and flatten them. I would be very surprised if
> distance fields were different in this regard?

Well, I'm not much familiar with the rendering part of bezier curve. In 
distance fields I'm just concerned about finding the shortest distance as 
accurate and as fast as possible.
So I won't leave out your option, in the next few days I'll try to optimize the 
code and then again we can compare the results. I think it will be a good 
option.

Anuj

Sent from Outlook Mobile

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

On Mon, Jun 15, 2020 at 9:06 AM Anuj Verma  wrote:
>
> > Your profiling results indicate that a lot of time is spent
> > calculating distances. Perhaps, you can work with much faster
> > square-distances (they can be signed or signs stored separately) and
> > apply square root as a final processing step. Or, would signed
> > square-distance field work as well (SSDF so to speak)? Please spend
> > some time thinking about optimizations and bottlenecks.
>
> Yes, even I was thinking of reducing the number of calls to 
> `ft_trig_pseudo_polarize'
> which I believe is called through `FT_Vector_Length'. Working with squared 
> distances
> can definitely be a good option, it will cut the total time by almost 50%.

For linear segments, it will save more than 90% according to your
table. Then you will see that splitting Bezier curves is not such a
bad option. In general, Bezier curves are used in graphics because it
is easy to split and flatten them. I would be very surprised if
distance fields were different in this regard?

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Replying to myself...

On Mon, Jun 15, 2020 at 8:11 AM Alexei Podtelezhnikov
 wrote:
>
> Hi Anuj,
>
> > A) Line Segment: ~0.32 microseconds
> > B) Conic Bezier: ~1.08 microseconds
> > C) Cubic Bezier: ~1.25 microseconds
> >
>
> I am very surprised indeed. In the linear case, it is a trivial
> cross-product divided by the length of a segment, or the smaller of
> two distances to the ends. There are no equations to solve. What is
> your explanation for such close numbers?

Your profiling results indicate that a lot of time is spent
calculating distances. Perhaps, you can work with much faster
square-distances (they can be signed or signs stored separately) and
apply square root as a final processing step. Or, would signed
square-distance field work as well (SSDF so to speak)? Please spend
some time thinking about optimizations and bottlenecks.

Alexei

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Alexei Podtelezhnikov]

Hi Anuj,

> A) Line Segment: ~0.32 microseconds
> B) Conic Bezier: ~1.08 microseconds
> C) Cubic Bezier: ~1.25 microseconds
>

I am very surprised indeed. In the linear case, it is a trivial
cross-product divided by the length of a segment, or the smaller of
two distances to the ends. There are no equations to solve. What is
your explanation for such close numbers?

Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Werner,

Thanks for checking the code and for your comments.

Did you miss the last two mails from Alexei and me?
I missed a few mails a few days ago for no reason and
even got a few duplicate mails.

> *I think he means that the code must be optimized as much as possible*
> *to get fast rendering. In particular, it is important to find and*
> *eliminate hotspots.*

Yes, he wanted to check if it's worth splitting the curves into line
segments to get better performance without losing much details. I did
a performance analysis and have attached it in the previous mail.

> *Some comments to your code.*
> ** What does line 38 do?*

There is no use for that. It was just me checking the accuracy of the
output. I forgot to remove that before committing.

> ** Function `get_min_conour` should probably be called*
>   *`get_min_contour`.  Otherwise please explain in a comment what*
>   *'conour' means.*

Another typo, I did fix it in the header file but forgot in the
source file. Thanks for pointing that out.

> ** Have you thought about iterative solutions to get the cubic roots*
>
*necessary for the quadratic case?  Maybe this would be faster. *

This can be faster because we only need to find the roots within
the range [0.0, 1.0]. So, I will implement an iterative solution
and see how it goes.





* > * Maybe there is a mathematical approximation to solving the >
fifth-grade polynomial.  I don't mean a better root-finding >   algorithm
but a simpler representation of the curves so that we can >   avoid a
fifth-grade polynomial altogether.  The same holds for the >   third-grade
equation, of course. *

I am definitely avoiding the fifth-degree polynomial. If you look the commit
(
https://github.com/preversewharf45/freetype2-sdf/blob/5322b28305b3b1a2d45ef68a057fe97efe113cbb/src/sdfgen.c#L523
)
I was actually solving the fifth-degree polynomial, later I decided to
remove
because it was huge and slow. Now I bisect the curve in four parts and
use newton's iteration to find the closest point on the curve.
So to avoid the third-degree polynomial I can use the exact same method
that I use for cubic-curves, but I checked the performance and it's actually
faster to simply solve the polynomial in case of conic-curves. (in case you
missed the mail:
https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00095.html)

> *PS: Did you have a look at Behdad's `GLyphy` implementation? *

Yes, I did check out `GLyphy'. He converts bezier curves to arcs, but I'm
not sure how he does it. Perhaps he is using this algorithm.
(
https://github.com/preversewharf45/papers/blob/master/Cubic%20curves%20to%20Circular%20arcs.pdf
)

Behdad, It would be great if you tell me more about your algorithm and if
it is faster to convert bezier to arcs and find the signed distance.

Thanks,
Anuj