Sub-pixel distance transform | Hacker News Reader

Sub-pixel distance transform

acko.net

196 pointssigna1131 comments

Content aside, I've got to give Mr. acko.net credit for that header. It's been there for, what, almost twenty years now? And yet it somehow still feels really fun and cool and not particularly dated, which is something that cannot be said for more mid-00s web art kinds of stuff!

It's a very nicely-done blog, having looked at some of the other articles in more detail. But I wish I'd stuck to the technical entries and steered clear of the political ones. "Who doesn't go Nazi?" turns a pleasant rabbit hole into an intellectual Superfund site.

It wasn't obvious to me what this was about from the title but it's very relevant to my interests:

> In this post I will describe Use.GPU's text rendering, which uses a bespoke approach to Signed Distance Fields (SDFs). This was borne out of necessity: while SDF text is pretty common on GPUs, some of the established practice on generating SDFs from masks is incorrect, and some libraries get it right only by accident. So this will be a deep dive from first principles, about the nuances of subpixels.

Me too, wouldn't have thought it's about SDF font rendering. The blog posts subtitle would make more sense as HN title:

High quality font rendering for WebGPU

(but then it's not really about WebGPU either but about solving general problems with SDF font generation and rendering)

U+1FAD5 FONDUE

Amazing that we have a unicode code point for this, but we still need to use vegetables as proxies for our reproductive organs.

𓂸... huh, how about 𓂺... Wonder if anyone can read these.

We've been able to misuse glyphs as pictographs as long as computers could render 8, =, and D.

Super big fan of SDF text rendering and their ability to get effects like soft-shadows and hard bevels, essentially for free by baking Multi Channel and Single SDFs into one RGBA texture.[1] was surprised to see emojis work without being decomposed into separate parts, albeit the colors losing their sharpness above the texture's 1:1 resolution.

[1] https://github.com/Chlumsky/msdfgen

Impressive. Very nice. Let’s see Text Mesh Pro’s SDF rendering.

Look at that subtle off-white coloring. The tasteful thickness of it. Oh my God, it even has a novel distance transform...

Are you saying Text Mesh Pro is better or using a similar improvement over SDFs?

Maybe if GTK4 is so bent on GPU rendering and all about edge cases like slightly rotated text, it should be using this technique so that fonts are not blurry shite by default?

Using SDFs to render text is a recipe for blurry text unless you get all the details right, which is part of why the post is so long :)

Having worked with GTK4's renderer and glyph cache a bit, the reason that GTK4 has blurry text is that some text is positioned at non-integer Y coordinates (unsure if a bug or not), and text isn't grid-snapped vertically while rendering (even when hinting is on, which is useless unless grid-snapping is enabled). For some reason they're considering disabling subpixel horizontal positioning as well as vertical on non-HiDPI displays (https://gitlab.gnome.org/GNOME/gtk/-/merge_requests/6190).

Can someone help me understand why a CPU based method like EDT would be used instead of a more GPU friendly method like jump fill?

It seems like you could use the sun pixel distances like he did, but then use them with jump fill, but maybe I'm missing something?

Most likely compatibility is more stable across clients

GPUs aren't universally supported by browsers or available on client devices, and implementing a user-agent/telemetry based response adds overhead.

But,I believe this is being used for his Use.GPU project, which requires not just GPU support, but the latest WebGPU support.

Jump flood is multi-pass and approximate not exact. I wouldn’t assume it’s faster for small input images, which is what the article is aiming for.

Also the distance transform algorithm in the article could be implemented on a GPU using a thread per row & column rather than per pixel. (At least in CUDA - I’m not immediately certain how to do it in GLSL but I guess someone could do it.) This is not optimal, of course, but parallelizing rows is perhaps a lot better than a single-threaded loop over the image.

It is trivially done with compute shaders in two passes, one vertical, one horizontal.

I'm sure the animated rendered background is there to drive the following point home: "if you're reading this on a device that can't keep up then this is not for you"

This is a neat tool for making SDF's: https://jobtalle.com/SDFMaker/

I believe that Daniel Huttenlocher and Pedro Felzenszwalb should be credited for the multi-pass (first X, then Y) transform based on quadratic distance:

https://ecommons.cornell.edu/handle/1813/5663

I had "invented" that independently for shape based interpolation needs I had in early 2000.

I like that paper, but I don’t think it was the first to suggest separating x and y and using multi-pass for distance transforms.

Here are a few that predate and I think make the same observation:

https://dl.acm.org/doi/10.1016/j.ipl.2006.12.005

https://www.sciencedirect.com/science/article/abs/pii/002001...

That second paper from 1996 references an even older paper from 94, saying “Dividing rows and columns alternately, Chen and Chuang reduced the time complexity to O(N^2) which is optimal.”

https://www.sciencedirect.com/science/article/abs/pii/002001...

Interesting - thanks dahart (hi again!) for pointing out these references. They do seem to be missing in the Cornell report.

Is there a library that can generate SDFs directly from the font's Bezier curves?

Distance to a Bezier curve is an interesting one. For an n-degree Bezier it's easy to turn it into a problem to find a root for a 2n-1 degree polynomial, but that means anything for n>2 is going to be tricky to do in closed form. A few iterations of Newton's method with a good initial guess could go quite far though.

I did some experiments with shaders to stroke bezier curves many years ago, and iirc, the easiest (reasonably efficient) route I found if you have a cubic spline is to fit a quadratic spline to it first, then just transform and solve it as distance to a parabola.

Yes, tricky, a.k.a. impossible. ;) There is a neat closed-form solution for the n=2 quadratic Bezier floating around on ShaderToy, based on the trig solution of the cubic equation [1] and I’m fascinated by the link between cubics and circles [2]

[1] https://en.wikipedia.org/wiki/Cubic_equation#Trigonometric_s...

[2] https://en.wikipedia.org/wiki/Cubic_equation#Geometric_inter...

The FreeType library can generate SDFs from TrueType fonts. I am not sure whether it uses the Bezier curves directly though, or first renders to a bitmap.

another entry into this field is via the slug library: http://sluglibrary.com/

I've only glanced at slug but it looks far too heavyweight for the 'just render this bitmap of a glyph but with sharp edges' use case that SDF attempts to fulfil; especially since browsers are already excellent text rendering engines.

Reply on news.ycombinator.com