Re: [Freetype-devel] Re: GSOC - Distance Fields

[Anuj Verma]

Hello Behdad,

> I have.  In 2018 Nicolas Rougier and I presented a mini-course at SIGGRAPH that covered all the SDF-based experiments of the past 10 / 15 years.

> If you haven't reviewed those, I suggest you do.  Unfortunately there's no video and the slides are low resolution:

>

>   https://www.slideshare.net/NicolasRougier1/siggraph-2018-digital-typography

>

> In particular, I advise that you read the 2018-Langyel paper, which is what's in sluglibrary.com:

>

>  http://www.terathon.com/i3d2018_lengyel.pdf

>

> Because if you follow my line of reasoning in my previous messages and the rest of this message, I'm advising that you implement what basically will be Lengyel's algorithm on the CPU.

I looked at the SIGGRAPH slides, it is interesting. Thanks for sharing.

I will read the Lengyel paper and will let you know.

> I thought about that a lot and did some research. This is a good summary:

>

>  https://math.stackexchange.com/questions/2432348/what-is-stopping-criteria-for-newtons-method/2433475#2433475

>

> Basically, if the solution is pulled out of [0,1] range, you can clamp them.  If they keep pulling out again right after clamping, you can discard.

> That post also suggests that what you are seeing was caused by your fixed-point limitations.  Were you testing with float or fixed?:

I was testing it with fixed, I will again test it with floats and let you know. Thanks for sharing the link.

>> * 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.

[note the two images above are constructed using fixed point, I will specify this from now on]

> I take that back.  Moreover, I'm convinced with 4 you still get very noticeable artefacts with correctly-constructed fonts.

> When I was thinking through it last time I was mistakenly thinking that there are three roots, whereas there are five.  Moreover, the positions of the roots

> can be arbitrarily close to each other. Moreover, there's no fast criteria to know the quality of the Raphson output or know when to terminate.  As such, I

> believe the method cannot be made correct (as in not producing artefacts) and fast at the same time.

If you are talking about the artifact at the corners, it is again caused only while using fixed-point. Moreover, it also happens

in simple contours with only line segments (https://i.imgur.com/MZsNeHJ.png - uses fixed). I will try to fix this for fixed-points.

Here is an SDF using floats: https://i.imgur.com/QSGCoIj.png - uses floats and Raphson

> So I go back to my suggestion earlier on: that you convert cubics to a series of quadratics.  Note how that conversion needs to be done once only, not per pixel.

>

> For the conversion I suggest lifting the core ideas from cu2qu:

>

>   https://github.com/googlefonts/cu2qu/issues/10

>

> ideally withe cusp issue handled:

>

>  https://github.com/googlefonts/cu2qu/issues/6

I will try to optimize Newton's method (will also try to remove artifacts) and will also check the performance of converting cubic to quadratic, then we can finally decide what to use.

> I understand why you are doing it.  I believe it's not necessary.  Let me try again.  See if you can prove the following for yourself. 

> I have proved it and can share.  (Only if we had a mathematician around ;)).

>

> Lemma: if the closest point on curve [0,1] is to the endpoint at t=1 and the cubic equation has no real root at t=1, the cubic equation must have at least one real root at some t > 1. 

> Similarly, if the closest point on curve [0,1] is to the endpoint at t=0 and the cubic equation has no real root at t=0, the cubic equation must have at least one real root at some t > 1.

>

> As such, you just need to compute all real roots, clamp them to [0,1] and remove duplicates.

[there is a typo, it should be t < 1 at the last point]

I tried to use this and it works exactly the same as before but faster. Thanks for that.

I can't quite figure out the proof, here is what I think:

The cubic equation here is used to find the perpendicular to the curve.

Now, if we forget about the range [0, 1] the perpendicular can be anywhere.

Moreover, the slope of curve is given by a linear equation ( y = mx + c ),

that means it varies from [-90, 90] (tan(x) varies from [-inf, inf]: this

is also the reason why there has to be at least one real root/perpendicular).

So, if we extend the endpoints we will get a perpendicular somewhere down the

line, but I can't figure out why it is at t > 1 if the nearest point is at t = 1

and vice versa. It will be great if you can share your proof.

Thanks for the comments and your improvements, I will read Lengye's paper and let you know.

Regards,

Anuj