>> 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.
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