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

[Vincent Torri]

On Fri, Jun 26, 2020 at 2:17 PM Anuj Verma <anujv@iitbhilai.ac.in> 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