Re: [Freetype-devel] Re: GSOC - Distance Fields
I assume spread means maximum distance. We use a spread of 4, so 8 would be plenty. We use 4 mainly to keep the glyph sizes under control, because a larger spread means a larger pad of texels around each glyph to make use of that information. Unfortunately we have some pretty severe memory restrictions on low-end devices so that constrains a lot of what we can do. On Fri, Jun 26, 2020 at 8:16 AM Anuj Verma 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). > > 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 > -- Jim Van Verth | Software Engineer | jvanve...@google.com | 919-210-7664
Re: [Freetype-devel] Re: GSOC - Distance Fields
On Fri, Jun 26, 2020 at 3:38 PM Anuj Verma wrote: > > > you also have DrMemory on Windows memory errors and leaks, and the > > Visual Studio tools > > (https://docs.microsoft.com/en-us/visualstudio/profiling/getting-started-with-performance-tools?view=vs-2017) > > That would be much more convenient, I'll check these out. also : http://www.codersnotes.com/sleepy/
Re: [Freetype-devel] Re: GSOC - Distance Fields
> you also have DrMemory on Windows memory errors and leaks, and the > Visual Studio tools > ( https://docs.microsoft.com/en-us/visualstudio/profiling/getting-started-with-performance-tools?view=vs-2017 ) That would be much more convenient, I'll check these out. Thanks, Anuj
Re: [Freetype-devel] Re: GSOC - Distance Fields
On Fri, Jun 26, 2020 at 3:01 PM Anuj Verma wrote: > > > have you tried to use valgrind's callgrind tool + kcachegrind ? It can > > be very helpful > > No, I haven't. The problem is that I use windows for development and > valgrind doesn't work on windows.So, switching back and forth makes > the process a bit tedious. I'll try to use it on WSL2. you also have DrMemory on Windows memory errors and leaks, and the Visual Studio tools (https://docs.microsoft.com/en-us/visualstudio/profiling/getting-started-with-performance-tools?view=vs-2017) Vincent Torri
Re: [Freetype-devel] Re: GSOC - Distance Fields
> have you tried to use valgrind's callgrind tool + kcachegrind ? It can > be very helpful No, I haven't. The problem is that I use windows for development and valgrind doesn't work on windows.So, switching back and forth makes the process a bit tedious. I'll try to use it on WSL2. Thanks for suggestion, Anuj
Re: [Freetype-devel] Re: GSOC - Distance Fields
On Fri, Jun 26, 2020 at 2:17 PM Anuj Verma 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
Re: [Freetype-devel] Re: GSOC - Distance Fields
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
