Sub-pixel distance transform

https://acko.net/blog/subpixel-distance-transform/

by signa11 • 3 years ago

196 31 3 years ago

AlbertoGP• 3 years ago

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.

flohofwoe• 3 years ago

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)

FrostKiwi• 3 years ago

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

signa11• 3 years ago

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

krona• 3 years ago

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.

WesolyKubeczek• 3 years ago

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?

kevingadd• 3 years ago

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 :)

nyanpasu642• 3 years ago

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

colonwqbang• 3 years ago

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.

nyanpasu642• 3 years ago

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

smrq• 3 years ago

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

jcarrano• 3 years ago

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

contravariant• 3 years ago

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.

mistercow• 3 years ago

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.

dahart3• 3 years ago

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

gsliepen• 3 years ago

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.

amne• 3 years ago

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"

an1sotropy2• 3 years ago

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

JyrkiAlakuijala• 3 years ago

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

dahart3• 3 years ago

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

an1sotropy2• 3 years ago

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

doctorpangloss• 3 years ago

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

endergen• 3 years ago

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

prideout• 3 years ago

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

chasing• 3 years ago

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!

CamperBob2• 3 years ago

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.

theschwa2• 3 years ago

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?

AndrewKemendo• 3 years ago

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.

theschwa2• 3 years ago

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

dahart3• 3 years ago

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.

hulke• 3 years ago

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

Sub-pixel distance transform

Related Stories