Re: [Freetype-devel] Re: GSOC - Distance Fields
I forgot to add the gprof output. This is the final mail for sure. Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds secondscalls us/call us/call name 35.67 1.02 1.02 14600 0.01 0.01 sdf_vector_scale 29.37 1.86 0.84 129379261 0.01 0.01 sdf_vector_add 27.98 2.66 0.80 100 0.80 2.85 get_min_distance 5.25 2.81 0.15 6000 0.00 0.00 sdf_vector_dot 0.70 2.83 0.02 400 0.01 0.01 sdf_vector_sub 0.35 2.84 0.01 2100 0.00 0.00 sdf_vector_length 0.35 2.85 0.01 100 0.01 0.01 sdf_vector_normalize 0.35 2.86 0.01 main 0.00 2.86 0.001 0.00 0.00 _GLOBAL__sub_I_main 0.00 2.86 0.001 0.00 0.00 __static_initialization_and_destruction_0(int, int) % the percentage of the total running time of the time program used by this function. cumulative a running sum of the number of seconds accounted seconds for by this function and those listed above it. self the number of seconds accounted for by this secondsfunction alone. This is the major sort for this listing. calls the number of times this function was invoked, if this function is profiled, else blank. self the average number of milliseconds spent in this ms/callfunction per call, if this function is profiled, else blank. total the average number of milliseconds spent in this ms/callfunction and its descendents per call, if this function is profiled, else blank. name the name of the function. This is the minor sort for this listing. The index shows the location of the function in the gprof listing. If the index is in parenthesis it shows where it would appear in the gprof listing if it were to be printed. Copyright (C) 2012-2020 Free Software Foundation, Inc. Copying and distribution of this file, with or without modification, are permitted in any medium without royalty provided the copyright notice and this notice are preserved. Call graph (explanation follows) granularity: each sample hit covers 2 byte(s) for 0.35% of 2.86 seconds index % timeself childrencalled name [1]100.00.012.85 main [1] 0.802.05 100/100 get_min_distance [2] --- 0.802.05 100/100 main [1] [2] 99.70.802.05 100 get_min_distance [2] 1.020.00 14600/14600 sdf_vector_scale [3] 0.840.00 129379261/129379261 sdf_vector_add [4] 0.150.00 6000/6000 sdf_vector_dot [5] 0.020.00 400/400 sdf_vector_sub [6] 0.010.00 100/100 sdf_vector_normalize [7] 0.010.00 2000/2100 sdf_vector_length [8] --- 1.020.00 14600/14600 get_min_distance [2] [3] 35.71.020.00 14600 sdf_vector_scale [3] --- 0.840.00 129379261/129379261 get_min_distance [2] [4] 29.40.840.00 129379261 sdf_vector_add [4] --- 0.150.00 6000/6000 get_min_distance [2] [5] 5.20.150.00 6000 sdf_vector_dot [5] --- 0.020.00 400/400 get_min_distance [2] [6] 0.70.020.00 400 sdf_vector_sub [6] --- 0.010.00 100/100 get_min_distance [2] [7] 0.40.010.00 100 sdf_vector_normalize [7] 0.000.00 100/2100 sdf_vector_length [8] --- 0.000.00 100/2100 sdf_vector_normalize [7] 0.010.00 2000/2100 get_min_distance [2] [8] 0.30.010.00 2100 sdf_vector_length [8] --- 0.000.00 1/1 __libc_csu_init [315] [310]0.00.000.00 1 _GLOBAL__sub_I_main [310] 0.000.00 1/1 __static_initialization_and_destruction_0(int, int) [311] --- 0.000.00 1/1 _GLOBAL__sub_I_main [310] [311]0.00.000.00 1
Re: [Freetype-devel] Re: GSOC - Distance Fields
Hello Werner, > IMHO, in FreeType, SIMD support is something to be done in addition, > not as a replacement. Since Anuj makes quick progress I suggest that > he first concentrates on the fixed-float route. If there is some time > left we should check how SIMD can be implemented. Just to clarify, ` fixed-float' is the same as `fixed-point' integer? And yeah, I am interested in adding SIMD support as well! [sorry for spamming the list, this is the final mail for now] Thanks, Anuj
Re: [Freetype-devel] Re: GSOC - Distance Fields
Hello Alexei, > Each curved segment has a large number [...] I guess this is similar to the Euclidean distance transform algorithm. http://webstaff.itn.liu.se/~stegu/JFA/Danielsson.pdf As I said before I will not leave out this option, I will try to implement this and then we can compare the performance. > I am deeply sorry if this mathematical fact offends you in any way. > Your code is good but please allow me to suggest an alternative, > perhaps, faster implementation. Please, don't apologize. I don't find anything offending in your suggestions. I realize that we are all in the same boat and we all want to make the algorithm as fast as possible. I think we can't comment on which algorithm is better than the other without checking the performance and other important factors. So, I am open to all of your suggestions and will choose the one that we all can agree on, same for `fixed-point' vs `float', same for subdivision or not. Again Thank you for all of your suggestions,I will require them more in the future. Anuj
Re: [Freetype-devel] Re: GSOC - Distance Fields
> Also I'm surprised that you haven't put the code get_min_distance code for each edge type into a function. > Would you prefer that I comment re these on github? I don't think that will be necessary. I will fix that while adding in FreeType. That repository is just for testing and I might delete it in the future. Anuj
Re: [Freetype-devel] Re: GSOC - Distance Fields
> After you do all this, you will realize that the speed is still a concern. Don't do bounding-box check. > Classic way to do after is to split into a coarse grid and for each cell find all edges that may be relevant. > Then for pixels in each cell only process those edges. This is what GLyphy does and some of the other solutions as well. This sounds interesting, I will definitely try to implement this and see how it performs. Thanks
Re: [Freetype-devel] Re: GSOC - Distance Fields
Hello Behdad, > First, let me congratulate you. This is a very thorough and impressive piece of work for such a short time period. Thank you for that. Viktor's paper did help me a lot while writing the code. I guess you have already read his paper, but in case anyone is interested in reading it check this out: https://github.com/Chlumsky/msdfgen. It contains all the relevant information for generating SDF from outlines. Although I'm not using the full potential of the paper currently. > - I highly suggest you stick to float internally [...] I still think `float' is a better option for generating SDF, especially in lower resolution glyphs where fixed-point produces kind of straight lines instead of smooth curves(which is not noticable if you look at it briefly). But my concern is that FreeType doesn't use floats at the moment and I don't think it will be a good idea to add support for floats just for the sake of this project. It's a tradeoff between one thing or the other and I can't decide which would be the best considering the current state of library. I would say that I'm inclined on using fixed-point integers just because FreeType doesn't use them. Also, why doesn't FreeType use floats? Is it just because of platform which doesn't have floating point type? or are there more reasons? This question has been in my mind for quite some time. > Have you measured performance? I'm fairly sure the float can be made both more robust and faster. I just did, here are the results with compiler optimization turned on using chrono library: A) Line Segment: ~0.026 microseconds B) Conic Bezier: ~0.168 microseconds C) Cubic Bezier: ~0.469 microseconds [I have also attached the gprof output in case you are interested. Note that the gprof output is without any compiler optimization] To compare it to fixed-point check here: https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00095.html > Specially, when and if going for SIMD, you get inverse-sqrt for float but not int and that seems to be the slowest part of your work, which is > normalizing vectors. And I agree, you should do everything in squared-distance, then do a full pass over the results and do the (SIMD if available) > sqrt()ing. I believe you still need normalizing vectors though. SIMD sounds interesting and will definately be a plus point if I can implement it. As for squared-distance, it isn't a problem while using float but in case of fixed-point, I can't store the distance if it is more than ~180 in a 16.16 fixed point without causing overflow. > - Your Newton-Raphson is solid and your performance numbers look amazing. I think you should stick with this approach instead of subdividing. > As was suggested by others, do experiment with Raphson on your quadratic as well. Yes, will try to use Raphson on quadratic, although I don't think it will be better than solving the cubic equation. And I will stick to it until I find something even faster. > * Currently you abandon as soon as factor falls outside of [0,1]. That's wrong. Factor might go out but come back in in the next iteration. I was doing that initially, but I saw that the factor goes `out' and when it come back `in' it has the same value as the previous `in' value. This causes 2 extra passes of a fairly expensive iteration, so I decided to break if it goes outside the range. But, yeah I will see if that is wrong and decide accordingly after further testing. > * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2 is enough for always finding the closest point. > That would speed up significantly. It will certainly speed up the process a lot. But in the current implementation here are the results: A) MAX_DIVISIONS=2 : https://i.imgur.com/B9Q8Kpa.png B) MAX_DIVISIONS=4 : https://i.imgur.com/1sbl9MP.png Maybe if I don't break out when the factor falls outside [0.0, 1.0], MAX_DIVISIONS=2 might work. But currently there are issues when using MAX_DIVISIONS=2. > - Your quadratic code always adds t=0 and t=1 as roots. You don't need to. Only clamp the real roots to [0,1] range and remove duplicates. That is done to also check the endpoints. There are cases where there are: A) no real roots of the cubic equation (coefficient of x^3 = 0) B) all real roots lie within the range [0.0, 1.0] In these cases it becomes necessary to check the endpoints of the bezier curve, hence t = 0 and t = 1. > - Your handling of two edges meeting at a corner is solid. That's exactly what we do in GLyphy. > However, I'm also now convinced that there is no way to produce SDF from contours that might overlap > [...] I did use the winding sum and it works well. But it has issues and as you said it's not possible to find distance around the intersection. I see that FreeType rasterizer also has issues while rendering overlapping contours in Anti-Aliased mode. So, for now I won't add that this and later when FreeType has functionality to resolve overlapping contours I can easily add
Re: Logging Library-GSOC
Hi guys,
(For Armin){
I have looked into log4c, no doubt it is a powerful logging library and we
could use some of it's features to share some logging functionality from
FreeType,
but I am not sure about it on windows as I am having a hard time compiling
it on windows and also I think the pre-built .lib file provided in log4c
release @ here
Re: [Freetype-devel] Re: GSOC - Distance Fields
On Tue, Jun 16, 2020 at 11:02 AM Werner LEMBERG wrote: > > > For SIMD, I studied what's available last year for HarfBuzz. I > > documented what I found here: > > > > https://github.com/harfbuzz/harfbuzz/blob/simd/src/hb-simd.hh > > Thanks for the link, it's an interesting read. > > > If you use floats internally and fill in the distances, then you can > > do SIMD passes at the end to do sqrt, clamping, and other things to > > generate the output. But even solving computing roots or the > > Newton-Raphson can be done in SIMD for up to 8 samples at a time. > > IMHO, in FreeType, SIMD support is something to be done in addition, > not as a replacement. Absolutely. It's implied and I agree that we must support non-SIMD. All projects I know have the same requirements. > Since Anuj makes quick progress I suggest that > he first concentrates on the fixed-float route. If there is some time > left we should check how to SIMD can be implemented. > Agreed. I pointed out in case it can inform how to organize the operations such that SIMD benefit can be achieved later. I think such organization also produces faster code without SIMD. Eg. doing a tight loop of just sqrt()ing every pixel in the end allows the compiler to unroll the loop, which also enables better use of the multiple pipelines in the CPU because there's no data dependency. -- behdad http://behdad.org/
Re: [Freetype-devel] Re: GSOC - Distance Fields
> For SIMD, I studied what's available last year for HarfBuzz. I > documented what I found here: > > https://github.com/harfbuzz/harfbuzz/blob/simd/src/hb-simd.hh Thanks for the link, it's an interesting read. > If you use floats internally and fill in the distances, then you can > do SIMD passes at the end to do sqrt, clamping, and other things to > generate the output. But even solving computing roots or the > Newton-Raphson can be done in SIMD for up to 8 samples at a time. IMHO, in FreeType, SIMD support is something to be done in addition, not as a replacement. Since Anuj makes quick progress I suggest that he first concentrates on the fixed-float route. If there is some time left we should check how to SIMD can be implemented. Werner
Re: [Freetype-devel] Re: GSOC - Distance Fields
For SIMD, I studied what's available last year for HarfBuzz. I documented what I found here: https://github.com/harfbuzz/harfbuzz/blob/simd/src/hb-simd.hh If you use floats internally and fill in the distances, then you can do SIMD passes at the end to do sqrt, clamping, and other things to generate the output. But even solving computing roots or the Newton-Raphson can be done in SIMD for up to 8 samples at a time. On Tue, Jun 16, 2020 at 8:51 AM Behdad Esfahbod wrote: > Hi Anuj, > > First, let me congratulate you. This is a very thorough and impressive > piece of work for such a short time period. I read your code over a week > ago but couldn't sit down and type this. I see there has been lots of > progress since. I'll just summarize: > > - I highly suggest you stick to float internally. Any fixed-point and you > will inevitably hit rasterization issues no matter how hard you try. This > is a tried and tested failure path and I encourage you to stay away from > it. I see you did the fixed already. Have you measured performance? I'm > fairly sure the float can be made both more robust and faster. Specially, > when and if going for SIMD, you get inverse-sqrt for float but not int and > that seems to be the slowest part of your work, which is normalizing > vectors. And I agree, you should do everything in squared-distance, then > do a full pass over the results and do the (SIMD if available) sqrt()ing. > I believe you still need normalizing vectors though. > > - Your Newton-Raphson is solid and your performance numbers look amazing. > I think you should stick with this approach instead of subdividing. As was > suggested by others, do experiment with Raphson on your quadratic as well. > A couple things there: > > * Currently you abandon as soon as factor falls outside of [0,1]. > That's wrong. Factor might go out but come back in in the next iteration. > > * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2 > is enough for always finding the closest point. That would speed up > significantly. > > - Your quadratic code always adds t=0 and t=1 as roots. You don't need to. > Only clamp the real roots to [0,1] range and remove duplicates. > > - Your handling of two edges meeting at a corner is solid. That's exactly > what we do in GLyphy. However, I'm also now convinced that there is no way > to produce SDF from contours that might overlap. Imagine a "+" sign that is > two straight contours. You cannot find the distance around the > intersection. That's really bad news :(. Removing overlaps is extremely > tricky and so far we've stayed away from adding to FreeType. SkiaPathOps > seems to be the most solid Open Source implementation. I don't have any > suggestion as to how to proceed. I can only say do your work without > overlaps and document that as a caveat. I'm sorry I told you you need to do > winding tracking. That would help for other reasons, ie. when you have two > clockwise circles inside each other and a counter-clockwise one inside > those. The middle should be black. To get that black you need to count > winding of a ray from point to infinity. That's not what you are doing. > Again, okay to initially document that shortcoming. > > - I still think an option to get A8 output is desired, since that's enough > for a respectable rendering in most situations and is 50% more efficient > than a 16-bit. Also, most GPU hardware doesn't support 16-bit textures. > > - There was one place when I checked last week, that you were computing > distance then squaring it instead of just getting the squared_distance for > which you already had a function. > > - Your "spread" stuff. Spread is good, and user sets that depends on 1. > the width of filter they gonna use for rasterizing, 2. minimum size they > want to rasterize at. What that means is: > > * x_pad / y_pad should be set equal to spread, > > * The final normalizing you are doing based on max-distance is > nonsensical. Makes the SDF unusable for rasterization. > > Re different filters, I found that they don't really matter. You can see > my results in my slides / video: > > http://behdad.org/glyphy_slides.pdf > https://vimeo.com/83732058 > > That's all I remember. I'll look into your latest code at some point. > > Regards, > behdad > > On Sat, Jun 6, 2020 at 9:51 PM Anuj Verma wrote: > >> Hello All, >> >> >> *> Have you figured out FT_Fixed arithmetic? You still use floats in your >> > code. I think you should convert to FT_Fixed first. * >> >> So, I have been trying to convert my code to FT_Fixed for a few days now >> without any success. >> I did manage to use fixed point for shapes with only line segments, but >> because of small range >> of 16.16 fixed point I have to use 26.6 for intermediate calculations and >> because of that it >> doesn't look good, (https://imgur.com/kUSIj3y) Here is a comparison >> between float on >> the right and 26.6 fixed point representation on the left. >> As for bezier
Re: [Freetype-devel] Re: GSOC - Distance Fields
On Tue, Jun 16, 2020 at 9:49 AM Alexei Podtelezhnikov wrote: > Anuj, > > Each curved segment has a large number of neighboring grid points. > each of which has a unique nearest projection on the curve. The curve > is naturally sampled by this projection points a very large number of > times and quite uniformly. Therefore, why not divide the curve into a > large number of segments to begin with and then just find whatever > point is close to each grid? It could be a lot faster to find the > distance this way. > So... You subdivide the curves into lines. Can you sketch what you do then? I did think about "rasterizing" the outline and mark all pixels that have distance < 1.0 to the outline, and then "propagate" the distance out. But as I've shown in my GLyphy talk, no matter how much I thought about this, I found that there can be points far from the curve such that the closest edge for this point is different from the closest edge for all its neighboring pixels. As such, the only way to use this optimization is if each pixel kept a list of edges that are closest, within a range That then suggests that just using a coarse grid is even better, hence what I suggested. -- behdad http://behdad.org/
Re: [Freetype-devel] Re: GSOC - Distance Fields
On Tue, Jun 16, 2020 at 9:50 AM Werner LEMBERG wrote: > >>> - Your handling of two edges meeting at a corner is solid. That's > >>> exactly what we do in GLyphy. However, I'm also now convinced > >>> that there is no way to produce SDF from contours that might > >>> overlap. Imagine a "+" sign that is two straight contours. You > >>> cannot find the distance around the intersection. That's really > >>> bad news :(. Removing overlaps is extremely tricky and so far > >>> we've stayed away from adding to FreeType. > > This is an interesting idea. I'm very open to add an API for removing > overlaps. > > >>> SkiaPathOps seems to be the most solid Open Source implementation. > > URL, please. A quick search on Google only shows video results. > Watch this video first so you appreciate the level of finesse that has gone into it: https://www.youtube.com/watch?v=OmfliNQsk88 The code is part of Skia. In FontTools we needed that so Cosimo & others wrapped that into Python: https://github.com/fonttools/skia-pathops SkiaPathOps can be compiled separately from the rest of Skia. That was by design. When we started using this for font production, we hit a couple of problems. If I remember correctly, it didn't necessarily retain the direction of contours. Ie. it worked for even-odd only. They were open to addressing those issues so it can be used for font production. And I know fontmake pipeline uses it now. I've CC'ed Cosimo & Ben who can comment. And yes, that library removes overlaps on curves directly. b > >>> I don't have any suggestion as to how to proceed. I can only say > >>> do your work without overlaps and document that as a caveat. > > Sounds like a good suggestion. > > > Werner > -- behdad http://behdad.org/
Re: [Freetype-devel] Re: GSOC - Distance Fields
>>> - Your handling of two edges meeting at a corner is solid. That's >>> exactly what we do in GLyphy. However, I'm also now convinced >>> that there is no way to produce SDF from contours that might >>> overlap. Imagine a "+" sign that is two straight contours. You >>> cannot find the distance around the intersection. That's really >>> bad news :(. Removing overlaps is extremely tricky and so far >>> we've stayed away from adding to FreeType. This is an interesting idea. I'm very open to add an API for removing overlaps. >>> SkiaPathOps seems to be the most solid Open Source implementation. URL, please. A quick search on Google only shows video results. >>> I don't have any suggestion as to how to proceed. I can only say >>> do your work without overlaps and document that as a caveat. Sounds like a good suggestion. Werner
Re: [Freetype-devel] Re: GSOC - Distance Fields
Anuj, Each curved segment has a large number of neighboring grid points. each of which has a unique nearest projection on the curve. The curve is naturally sampled by this projection points a very large number of times and quite uniformly. Therefore, why not divide the curve into a large number of segments to begin with and then just find whatever point is close to each grid? It could be a lot faster to find the distance this way. I am deeply sorry if this mathematical fact offends you in any way. Your code is good but please allow me to suggest an alternative, perhaps, faster implementation. Alexei
Re: [Freetype-devel] Re: GSOC - Distance Fields
Also I'm surprised that you haven't put the code get_min_distance code for each edge type into a function. Would you prefer that I comment re these on github? On Tue, Jun 16, 2020 at 8:53 AM Behdad Esfahbod wrote: > Oh, I forgot: > > After you do all this, you will realize that the speed is still a > concern. Don't do bounding-box check. Classic way to do after is to split > into a coarse grid and for each cell find all edges that may be relevant. > Then for pixels in each cell only process those edges. This is what GLyphy > does and some of the other solutions as well. > > On Tue, Jun 16, 2020 at 8:51 AM Behdad Esfahbod wrote: > >> Hi Anuj, >> >> First, let me congratulate you. This is a very thorough and impressive >> piece of work for such a short time period. I read your code over a week >> ago but couldn't sit down and type this. I see there has been lots of >> progress since. I'll just summarize: >> >> - I highly suggest you stick to float internally. Any fixed-point and >> you will inevitably hit rasterization issues no matter how hard you try. >> This is a tried and tested failure path and I encourage you to stay away >> from it. I see you did the fixed already. Have you measured performance? >> I'm fairly sure the float can be made both more robust and faster. >> Specially, when and if going for SIMD, you get inverse-sqrt for float but >> not int and that seems to be the slowest part of your work, which is >> normalizing vectors. And I agree, you should do everything in >> squared-distance, then do a full pass over the results and do the (SIMD if >> available) sqrt()ing. I believe you still need normalizing vectors though. >> >> - Your Newton-Raphson is solid and your performance numbers look >> amazing. I think you should stick with this approach instead of >> subdividing. As was suggested by others, do experiment with Raphson on >> your quadratic as well. A couple things there: >> >> * Currently you abandon as soon as factor falls outside of [0,1]. >> That's wrong. Factor might go out but come back in in the next iteration. >> >> * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2 >> is enough for always finding the closest point. That would speed up >> significantly. >> >> - Your quadratic code always adds t=0 and t=1 as roots. You don't need >> to. Only clamp the real roots to [0,1] range and remove duplicates. >> >> - Your handling of two edges meeting at a corner is solid. That's exactly >> what we do in GLyphy. However, I'm also now convinced that there is no way >> to produce SDF from contours that might overlap. Imagine a "+" sign that is >> two straight contours. You cannot find the distance around the >> intersection. That's really bad news :(. Removing overlaps is extremely >> tricky and so far we've stayed away from adding to FreeType. SkiaPathOps >> seems to be the most solid Open Source implementation. I don't have any >> suggestion as to how to proceed. I can only say do your work without >> overlaps and document that as a caveat. I'm sorry I told you you need to do >> winding tracking. That would help for other reasons, ie. when you have two >> clockwise circles inside each other and a counter-clockwise one inside >> those. The middle should be black. To get that black you need to count >> winding of a ray from point to infinity. That's not what you are doing. >> Again, okay to initially document that shortcoming. >> >> - I still think an option to get A8 output is desired, since that's >> enough for a respectable rendering in most situations and is 50% more >> efficient than a 16-bit. Also, most GPU hardware doesn't support 16-bit >> textures. >> >> - There was one place when I checked last week, that you were computing >> distance then squaring it instead of just getting the squared_distance for >> which you already had a function. >> >> - Your "spread" stuff. Spread is good, and user sets that depends on 1. >> the width of filter they gonna use for rasterizing, 2. minimum size they >> want to rasterize at. What that means is: >> >> * x_pad / y_pad should be set equal to spread, >> >> * The final normalizing you are doing based on max-distance is >> nonsensical. Makes the SDF unusable for rasterization. >> >> Re different filters, I found that they don't really matter. You can see >> my results in my slides / video: >> >> http://behdad.org/glyphy_slides.pdf >> https://vimeo.com/83732058 >> >> That's all I remember. I'll look into your latest code at some point. >> >> Regards, >> behdad >> >> On Sat, Jun 6, 2020 at 9:51 PM Anuj Verma wrote: >> >>> Hello All, >>> >>> >>> *> Have you figured out FT_Fixed arithmetic? You still use floats in >>> your > code. I think you should convert to FT_Fixed first. * >>> >>> So, I have been trying to convert my code to FT_Fixed for a few days now >>> without any success. >>> I did manage to use fixed point for shapes with only line segments, but >>> because of small range >>> of 16.16 fixed
Re: [Freetype-devel] Re: GSOC - Distance Fields
On Mon, Jun 15, 2020 at 9:47 AM Alexei Podtelezhnikov wrote: > On Mon, Jun 15, 2020 at 11:03 AM Anuj Verma wrote: > >> > > > For linear segments, it will save more than 90% according to your > > > table. Then you will see that splitting Bezier curves is not such a > > > bad option. In general, Bezier curves are used in graphics because it > > > is easy to split and flatten them. I would be very surprised if > > > distance fields were different in this regard? > > > > Well, I'm not much familiar with the rendering part of bezier curve. > > This primer is fun to read with many interactive demos: > https://pomax.github.io/bezierinfo/ > The main thing to recognize is that splitting a Bezier at t=0.5 and > calculating the new set of control points for the halfs is lightning > fast. If you continue doing so, the segments very quickly converge to > almost straight (flat) segments. > Alexei, I find your suggestion deeply offensive. Have you looked at his code? You should. You will learn a few things about writing good code. This is the kind of toxic behavior that has been deeply bothering me on this list but I couldn't fully understand and verbalize. I'm getting closer to that now. I will start a new thread when I can write that down. In the meantime I think you should apologize to Anuj. https://www.businessinsider.com/cond-nast-assistant-quit-ceo-gave-her-elements-of-style-2020-6 > > In distance fields I'm just concerned about finding the shortest > distance as accurate and as fast as possible. > > Each split decreases deviation 4 times for a conic segment so that you > can reach a given accuracy of your distance field and use only > straight segments. The accuracy is defined by the grid resolution: it > won't be visible to a human eye if the approximation deviates from a > true curve by more than ~0.1 of the grid size. > > -- behdad http://behdad.org/
Re: [Freetype-devel] Re: GSOC - Distance Fields
Oh, I forgot: After you do all this, you will realize that the speed is still a concern. Don't do bounding-box check. Classic way to do after is to split into a coarse grid and for each cell find all edges that may be relevant. Then for pixels in each cell only process those edges. This is what GLyphy does and some of the other solutions as well. On Tue, Jun 16, 2020 at 8:51 AM Behdad Esfahbod wrote: > Hi Anuj, > > First, let me congratulate you. This is a very thorough and impressive > piece of work for such a short time period. I read your code over a week > ago but couldn't sit down and type this. I see there has been lots of > progress since. I'll just summarize: > > - I highly suggest you stick to float internally. Any fixed-point and you > will inevitably hit rasterization issues no matter how hard you try. This > is a tried and tested failure path and I encourage you to stay away from > it. I see you did the fixed already. Have you measured performance? I'm > fairly sure the float can be made both more robust and faster. Specially, > when and if going for SIMD, you get inverse-sqrt for float but not int and > that seems to be the slowest part of your work, which is normalizing > vectors. And I agree, you should do everything in squared-distance, then > do a full pass over the results and do the (SIMD if available) sqrt()ing. > I believe you still need normalizing vectors though. > > - Your Newton-Raphson is solid and your performance numbers look amazing. > I think you should stick with this approach instead of subdividing. As was > suggested by others, do experiment with Raphson on your quadratic as well. > A couple things there: > > * Currently you abandon as soon as factor falls outside of [0,1]. > That's wrong. Factor might go out but come back in in the next iteration. > > * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2 > is enough for always finding the closest point. That would speed up > significantly. > > - Your quadratic code always adds t=0 and t=1 as roots. You don't need to. > Only clamp the real roots to [0,1] range and remove duplicates. > > - Your handling of two edges meeting at a corner is solid. That's exactly > what we do in GLyphy. However, I'm also now convinced that there is no way > to produce SDF from contours that might overlap. Imagine a "+" sign that is > two straight contours. You cannot find the distance around the > intersection. That's really bad news :(. Removing overlaps is extremely > tricky and so far we've stayed away from adding to FreeType. SkiaPathOps > seems to be the most solid Open Source implementation. I don't have any > suggestion as to how to proceed. I can only say do your work without > overlaps and document that as a caveat. I'm sorry I told you you need to do > winding tracking. That would help for other reasons, ie. when you have two > clockwise circles inside each other and a counter-clockwise one inside > those. The middle should be black. To get that black you need to count > winding of a ray from point to infinity. That's not what you are doing. > Again, okay to initially document that shortcoming. > > - I still think an option to get A8 output is desired, since that's enough > for a respectable rendering in most situations and is 50% more efficient > than a 16-bit. Also, most GPU hardware doesn't support 16-bit textures. > > - There was one place when I checked last week, that you were computing > distance then squaring it instead of just getting the squared_distance for > which you already had a function. > > - Your "spread" stuff. Spread is good, and user sets that depends on 1. > the width of filter they gonna use for rasterizing, 2. minimum size they > want to rasterize at. What that means is: > > * x_pad / y_pad should be set equal to spread, > > * The final normalizing you are doing based on max-distance is > nonsensical. Makes the SDF unusable for rasterization. > > Re different filters, I found that they don't really matter. You can see > my results in my slides / video: > > http://behdad.org/glyphy_slides.pdf > https://vimeo.com/83732058 > > That's all I remember. I'll look into your latest code at some point. > > Regards, > behdad > > On Sat, Jun 6, 2020 at 9:51 PM Anuj Verma wrote: > >> Hello All, >> >> >> *> Have you figured out FT_Fixed arithmetic? You still use floats in your >> > code. I think you should convert to FT_Fixed first. * >> >> So, I have been trying to convert my code to FT_Fixed for a few days now >> without any success. >> I did manage to use fixed point for shapes with only line segments, but >> because of small range >> of 16.16 fixed point I have to use 26.6 for intermediate calculations and >> because of that it >> doesn't look good, (https://imgur.com/kUSIj3y) Here is a comparison >> between float on >> the right and 26.6 fixed point representation on the left. >> As for bezier curves, there is almost always an overflow because while >> solving
Re: [Freetype-devel] Re: GSOC - Distance Fields
Hi Anuj, First, let me congratulate you. This is a very thorough and impressive piece of work for such a short time period. I read your code over a week ago but couldn't sit down and type this. I see there has been lots of progress since. I'll just summarize: - I highly suggest you stick to float internally. Any fixed-point and you will inevitably hit rasterization issues no matter how hard you try. This is a tried and tested failure path and I encourage you to stay away from it. I see you did the fixed already. Have you measured performance? I'm fairly sure the float can be made both more robust and faster. Specially, when and if going for SIMD, you get inverse-sqrt for float but not int and that seems to be the slowest part of your work, which is normalizing vectors. And I agree, you should do everything in squared-distance, then do a full pass over the results and do the (SIMD if available) sqrt()ing. I believe you still need normalizing vectors though. - Your Newton-Raphson is solid and your performance numbers look amazing. I think you should stick with this approach instead of subdividing. As was suggested by others, do experiment with Raphson on your quadratic as well. A couple things there: * Currently you abandon as soon as factor falls outside of [0,1]. That's wrong. Factor might go out but come back in in the next iteration. * I've convinced myself, but probably can't be proved, that MAX_DIVISIONS=2 is enough for always finding the closest point. That would speed up significantly. - Your quadratic code always adds t=0 and t=1 as roots. You don't need to. Only clamp the real roots to [0,1] range and remove duplicates. - Your handling of two edges meeting at a corner is solid. That's exactly what we do in GLyphy. However, I'm also now convinced that there is no way to produce SDF from contours that might overlap. Imagine a "+" sign that is two straight contours. You cannot find the distance around the intersection. That's really bad news :(. Removing overlaps is extremely tricky and so far we've stayed away from adding to FreeType. SkiaPathOps seems to be the most solid Open Source implementation. I don't have any suggestion as to how to proceed. I can only say do your work without overlaps and document that as a caveat. I'm sorry I told you you need to do winding tracking. That would help for other reasons, ie. when you have two clockwise circles inside each other and a counter-clockwise one inside those. The middle should be black. To get that black you need to count winding of a ray from point to infinity. That's not what you are doing. Again, okay to initially document that shortcoming. - I still think an option to get A8 output is desired, since that's enough for a respectable rendering in most situations and is 50% more efficient than a 16-bit. Also, most GPU hardware doesn't support 16-bit textures. - There was one place when I checked last week, that you were computing distance then squaring it instead of just getting the squared_distance for which you already had a function. - Your "spread" stuff. Spread is good, and user sets that depends on 1. the width of filter they gonna use for rasterizing, 2. minimum size they want to rasterize at. What that means is: * x_pad / y_pad should be set equal to spread, * The final normalizing you are doing based on max-distance is nonsensical. Makes the SDF unusable for rasterization. Re different filters, I found that they don't really matter. You can see my results in my slides / video: http://behdad.org/glyphy_slides.pdf https://vimeo.com/83732058 That's all I remember. I'll look into your latest code at some point. Regards, behdad On Sat, Jun 6, 2020 at 9:51 PM Anuj Verma wrote: > Hello All, > > > *> Have you figured out FT_Fixed arithmetic? You still use floats in your > > code. I think you should convert to FT_Fixed first. * > > So, I have been trying to convert my code to FT_Fixed for a few days now > without any success. > I did manage to use fixed point for shapes with only line segments, but > because of small range > of 16.16 fixed point I have to use 26.6 for intermediate calculations and > because of that it > doesn't look good, (https://imgur.com/kUSIj3y) Here is a comparison > between float on > the right and 26.6 fixed point representation on the left. > As for bezier curves, there is almost always an overflow because while > solving polynomials some > large numbers are involved. I even tried using Newton's approximation, but > it's too slow and still > not as accurate as floating points. I did not try using 64 bit integers > because they are not portable > I guess and because of that I have to create separate implementations for > 32 and 64 bit architecture. > So, after comparing both, I prefer floats over fixed points because they > satisfy both range and precision. > I can try using 64 bit integers but I am not sure whether I will be able > to finish the project on time or > not because of
