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

[Alexei Podtelezhnikov]

H Anuj,

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