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 <behdad@behdad.org> 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 <behdad@behdad.org> 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 <anujv@iitbhilai.ac.in> 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 separate implementation. I have attached the code below, note that this is my first time

dealing with fixed points so there might be something that I am not doing right.

SDF with fixed point: https://github.com/preversewharf45/freetype2-sdf/tree/FT_Fixed

You can directly go here (https://github.com/preversewharf45/freetype2-sdf/blob/FT_Fixed/src/sdfgen.c#L579) to

see the important changes I have made.

To view output: https://github.com/preversewharf45/freetype2-sdf-demo (already has sdf code)

Anuj

On Mon, Jun 1, 2020 at 7:18 PM Alexei Podtelezhnikov <apodtele@gmail.com> wrote:

Hi Anuj,

> I have written the program, you can find it at: https://github.com/preversewharf45/freetype2-sdf
> To view the output I'm currently using a small OpenGL framework: https://github.com/preversewharf45/freetype2-sdf-demo
> this already has the sdf code.

I like the style. Looks good.

> However there is an issue with the program, the glyphs which contain intersecting contours have an issue.
> (example: https://imgur.com/MxJfAwY)

The intersecting contours used to be discouraged and still quite rare.
In general, you should assume that fonts have reasonable shapes
without intersections or wrong contour orientations. It is more
important that your code deals with thin stems and cursive fonts with
tiny details like serifs.

> Currently the sign of the distance is determined by the orientation of the closest edge, so at places where
> one contour intersects another the pixel near that contour can be specified as outside even though it is
> inside the shape.
> To fix this issue I'm thinking of using the winding of the contours, so is there any function in freetype
> to get the winding or something similar?

We only have https://www.freetype.org/freetype2/docs/reference/ft2-outline_processing.html#ft_outline_get_orientation
You can cut the outline into individual contours manually. Keep in
mind that the orientation is different for TrueType and Type1/CFF
fonts.

> Also, should I start integrating this in freetype or first fix the issue?

Have you figured out FT_Fixed arithmetic? You still use floats in your
code. I think you should convert to FT_Fixed first.

Best,
Alexei

--

behdad
http://behdad.org/

--

behdad
http://behdad.org/

--

behdad
http://behdad.org/