>> 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] > This is a tie between B and C because you can still find some > interesting optimizations
Yes. For now I'll integrate the A method and then start optimizing, and I will also use some better tools that Vincent suggested for profiling. > There is another reason why subdividing cound faster: the bounding box > of a line is larger than two bounding boxes of its halfs, not > considering the padding (spread). However, 16 is too arbitrary. In > fact, in our antialiased renderer we divide until the curve deviates > from the line no more than 1/8th or a pixel, which could be more or > less than 16 depending on the size of the curve and its shape. I used 16 because It doesn't create jagged edges and looks exactly as method A. I believe the smooth renderer uses de Casteljau algorithm so I'll use that to subdivide. >> 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. > > This sort of optimizations can be quite complex to implement though, > which might defeat the purpose. I thought about this, we can align the bounding box in the direction of the line, that way all the points inside the bounding box will be perpendicular, the only problem is to actually find the points inside the box, which can be a bit tricky. > Do you understand why the underflow happens? Is it because the curve > arches around the point and there exist multiple solutions, perhaps > almost an infinite number of solutions? Does the equation with all > coefficients substituted become quadratic or linear and you can solve > it differently? Your method is still very good. I explained this to Werner a while ago in this message: https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00127.html It happens when there is exactly one root of the cubic equiation and the curve gets really close so the point. I'm almost sure that It can be avoided by increasing the precision, but I haven't tried it yet. >> 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 wonder if there is a way to test this using some SDF demo tool... I currently use an OpenGL demo, and in that even a spread of 2 is enough to draw perfectly, so 8 would be plenty. I just think that 32 gives a good range. On the other hand 64 is overkill and it almost looks like a circle above 64. Either way the subdivision method will work even with 32, so there is no problem with the spread now. Moreover what is your opinion about implementing both the methods ? > But for 4 is only 2 bits...I remember you decided to use FT_F2Dot14. > What is the correct way of presenting SDF to a client? What is the > common practice? That will have to be changed now, I previously thought of normalizing the values, but that is not a good idea. Now, I'm thinking of using something like 8.8 and another option of 3.5. That way if the user has low memory they can use the 8bit version. In skia Jim uses 3.5 so that might be good. I'm still not sure about the format but that can easily be changed. Thanks, Anuj