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:
That's all I remember. I'll look into your latest code at some point.
Regards,
behdad