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 to it. > - 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. Sure, it won't be a problem. I can add two output formats. Isn't this `DXGI_FORMAT_R16_SNORM' a 16-bit texture? I don't know about hardware, but in shaders I think you can easily get 16-bit and even 32-bit textures and shaders these days. Please correct me if I'm wrong. ( https://docs.microsoft.com/en-us/windows/win32/api/dxgiformat/ne-dxgiformat-dxgi_format ) > - 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. I do make a lot of stupid mistakes and typo in my code. It was probably while calculating squared_distance for line segments I did fix it recently. > - 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, Thanks for this, I was wondering how to calculate the padding which you just answered. > * The final normalizing you are doing based on max-distance is nonsensical. Makes the SDF unusable for rasterization. When I first heard about distance fields it was this video: https://www.youtube.com/watch?v=d8cfgcJR9Tk In this they use normalized values, but now I realize that the rendering API (OpenGL, DirectX) can automatically normalize the values. So, just to fit in a 2.14 fixed point I am normalizing the values which can very well be changed by a flag or completely removed. > Re different filters, I found that they don't really matter. You can see my results in my slides / video: Will check it out. > That's all I remember. I'll look into your latest code at some point. Thank you very much for reviewing the code and your comments. Also thanks to Werner and Alexei for checking the code out and giving me suggestions. I will keep all of your ideas in mind and decide what will be the best to use in SDF. Best, Anuj
