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