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