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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 separate implementation. I have attached the code below, >>> note that this is my first time >>> dealing with fixed points so there might be something that I am not >>> doing right. >>> >>> SDF with fixed point: >>> https://github.com/preversewharf45/freetype2-sdf/tree/FT_Fixed >>> You can directly go here ( >>> https://github.com/preversewharf45/freetype2-sdf/blob/FT_Fixed/src/sdfgen.c#L579) >>> to >>> see the important changes I have made. >>> >>> To view output: https://github.com/preversewharf45/freetype2-sdf-demo >>> (already has sdf code) >>> >>> Anuj >>> >>> On Mon, Jun 1, 2020 at 7:18 PM Alexei Podtelezhnikov <[email protected]> >>> wrote: >>> >>>> Hi Anuj, >>>> >>>> > I have written the program, you can find it at: >>>> https://github.com/preversewharf45/freetype2-sdf >>>> > To view the output I'm currently using a small OpenGL framework: >>>> https://github.com/preversewharf45/freetype2-sdf-demo >>>> > this already has the sdf code. >>>> >>>> I like the style. Looks good. >>>> >>>> > However there is an issue with the program, the glyphs which contain >>>> intersecting contours have an issue. >>>> > (example: https://imgur.com/MxJfAwY) >>>> >>>> The intersecting contours used to be discouraged and still quite rare. >>>> In general, you should assume that fonts have reasonable shapes >>>> without intersections or wrong contour orientations. It is more >>>> important that your code deals with thin stems and cursive fonts with >>>> tiny details like serifs. >>>> >>>> > Currently the sign of the distance is determined by the orientation >>>> of the closest edge, so at places where >>>> > one contour intersects another the pixel near that contour can be >>>> specified as outside even though it is >>>> > inside the shape. >>>> > To fix this issue I'm thinking of using the winding of the contours, >>>> so is there any function in freetype >>>> > to get the winding or something similar? >>>> >>>> We only have >>>> https://www.freetype.org/freetype2/docs/reference/ft2-outline_processing.html#ft_outline_get_orientation >>>> You can cut the outline into individual contours manually. Keep in >>>> mind that the orientation is different for TrueType and Type1/CFF >>>> fonts. >>>> >>>> > Also, should I start integrating this in freetype or first fix the >>>> issue? >>>> >>>> Have you figured out FT_Fixed arithmetic? You still use floats in your >>>> code. I think you should convert to FT_Fixed first. >>>> >>>> Best, >>>> Alexei >>>> >>> >> >> -- >> behdad >> http://behdad.org/ >> > > > -- > behdad > http://behdad.org/ > -- behdad http://behdad.org/
