Slug: Dynamic GPU Font Rendering and Advanced Text Layout(sluglibrary.com)
sluglibrary.com
Slug: Dynamic GPU Font Rendering and Advanced Text Layout
http://sluglibrary.com/
30 comments
This was posted on the 2017 thread here https://news.ycombinator.com/item?id=14512368:
Pathfinder tessellates edges into microtriangles, computes signed trapezoidal areas in the fragment shader, and then accumulates those areas using a compute shader. I assume that this would make Pathfinder a "tessellating" algorithm in the language of this article as opposed to a "non-tessellating" one.
By contrast, I can't verify from source, but it appears that Slug does all the work in a fragment shader. If so, this would make its closest relative the Will Dobbie vector texture approach [1].
I considered the Dobbie technique but rejected it because it's very slow, asymptotically so even: it's O(height ∗ width ∗ number of curves), with a high constant factor as Newton-Raphson or de Casteljau subdivision (note that the quadratic formula is an alternative if all you care about is TrueType) has to be repeated over and over again for every pixel/subsample in the scene. I don't know how any non-tessellating algorithm can avoid this asymptotic problem, since if you defer all the work to the fragment shader then you have no choice but to run your expensive shader on a conservative cover area instead of only the areas that need to be expensive (i.e. edges, or curves if you're doing Loop Blinn). By contrast, traditional scanline rendering on the CPU is O(height ∗ number of curves), not counting the blitting, and forward differencing can make the work needed to be done for each curve on the scanline extremely cheap. For this reason, every non-tessellating algorithm I've seen is significantly outperformed by typical CPU renderers in practice.
This is not to say that non-tessellating text renderers such as what Slug seems to be are worthless: they may be useful to avoid costly CPU/GPU synchronization if the size of the text to render is not known by the CPU, for example if it depends on the result of vertex shading for a scene.
My further work on Pathfinder, should it pan out, ought to allow for more precise tessellation without significant performance cost, exploiting the fact that the shape of the traditional CPU scanline rendering algorithm can be adapted to generate triangulations on-the-fly through monotone polygon decomposition. My colleague Nical Silva's Lyon [2] shows how this idea can work, though I'm still working on adapting the technique to efficiently handle curves and high quality Levien-style antialiasing. This would eliminate the compute shader step, allowing Pathfinder to easily composite into 2D and 3D scenes as Slug can do without sacrificing performance. Bear in mind that this work is highly experimental and unfinished.
[1]: http://wdobbie.com/post/gpu-text-rendering-with-vector-textu....
[2]: https://github.com/nical/lyon
Pathfinder tessellates edges into microtriangles, computes signed trapezoidal areas in the fragment shader, and then accumulates those areas using a compute shader. I assume that this would make Pathfinder a "tessellating" algorithm in the language of this article as opposed to a "non-tessellating" one.
By contrast, I can't verify from source, but it appears that Slug does all the work in a fragment shader. If so, this would make its closest relative the Will Dobbie vector texture approach [1].
I considered the Dobbie technique but rejected it because it's very slow, asymptotically so even: it's O(height ∗ width ∗ number of curves), with a high constant factor as Newton-Raphson or de Casteljau subdivision (note that the quadratic formula is an alternative if all you care about is TrueType) has to be repeated over and over again for every pixel/subsample in the scene. I don't know how any non-tessellating algorithm can avoid this asymptotic problem, since if you defer all the work to the fragment shader then you have no choice but to run your expensive shader on a conservative cover area instead of only the areas that need to be expensive (i.e. edges, or curves if you're doing Loop Blinn). By contrast, traditional scanline rendering on the CPU is O(height ∗ number of curves), not counting the blitting, and forward differencing can make the work needed to be done for each curve on the scanline extremely cheap. For this reason, every non-tessellating algorithm I've seen is significantly outperformed by typical CPU renderers in practice.
This is not to say that non-tessellating text renderers such as what Slug seems to be are worthless: they may be useful to avoid costly CPU/GPU synchronization if the size of the text to render is not known by the CPU, for example if it depends on the result of vertex shading for a scene.
My further work on Pathfinder, should it pan out, ought to allow for more precise tessellation without significant performance cost, exploiting the fact that the shape of the traditional CPU scanline rendering algorithm can be adapted to generate triangulations on-the-fly through monotone polygon decomposition. My colleague Nical Silva's Lyon [2] shows how this idea can work, though I'm still working on adapting the technique to efficiently handle curves and high quality Levien-style antialiasing. This would eliminate the compute shader step, allowing Pathfinder to easily composite into 2D and 3D scenes as Slug can do without sacrificing performance. Bear in mind that this work is highly experimental and unfinished.
[1]: http://wdobbie.com/post/gpu-text-rendering-with-vector-textu....
[2]: https://github.com/nical/lyon
I'm not a GPU programmer, but I've always been interested in this type of problem from a math/algorithms point of view. Is there any way to help with Pathfinder?
Please feel free to check out the repo, file issues, and submit PRs! https://github.com/servo/pathfinder
Thread from 2017: https://news.ycombinator.com/item?id=14507597
though i think the design of pathfinder has changed at least twice since then. it does 50/50 on gpu/cpu nowadays.
The design of Pathfinder hasn't really changed as far as fonts are concerned. The tiling step is what takes most of the CPU time, but fonts don't benefit from tiling unless they're very large. Most of the changes thus far have been for SVG.
BTW, were you aware that links to your older blog posts (e.g. [1]) were broken? Looks like you just removed "/blog" from the path, but you don't seem to be doing anything else with it.
[1] http://pcwalton.github.io/blog/2017/02/14/pathfinder/
[1] http://pcwalton.github.io/blog/2017/02/14/pathfinder/
ah, thanks for the clarification
The image previews looks like it's very crips, looks great - and the multicolored emoji is a nice touch.
It seems like this would have the same challenges as multi channel signed distance fields [0], where for unicode (e.g. Chinese characters) you need to generate textures on the fly and ship them to the GPU for the fragment shader to work off of.
[0] HN Discussion: https://news.ycombinator.com/item?id=20020664
It seems like this would have the same challenges as multi channel signed distance fields [0], where for unicode (e.g. Chinese characters) you need to generate textures on the fly and ship them to the GPU for the fragment shader to work off of.
[0] HN Discussion: https://news.ycombinator.com/item?id=20020664
I wonder if it would be plausible to use this with webgl via WASM... Or if anyone's working on a javascript implementation of the algorithm.
Good text rendering/layout is about the only thing I feel like I'm missing from being able to pretty simply/rapidly create 3d apps with web tech these days. I still end up typically just overlaying DOM elements over the scene :/
Good text rendering/layout is about the only thing I feel like I'm missing from being able to pretty simply/rapidly create 3d apps with web tech these days. I still end up typically just overlaying DOM elements over the scene :/
> I wonder if it would be plausible to use this with webgl via WASM.
That's precisely what I'm looking at. I'm not as familiar with the front-end space as I used to be. What's the SOTA these days?
That's precisely what I'm looking at. I'm not as familiar with the front-end space as I used to be. What's the SOTA these days?
IMO, unless you're writing a new renderer from scratch or doing something else super custom, three.js is the best way of doing real-time 3d for the web these days.
But, here's their article on text in three.js: https://threejs.org/docs/#manual/en/introduction/Creating-te...
I think the bitmap font stuff can be extended to rendering SDF (signed distance field) fonts, which are nice enough for me--but that is not ready to use out of the box.
But, here's their article on text in three.js: https://threejs.org/docs/#manual/en/introduction/Creating-te...
I think the bitmap font stuff can be extended to rendering SDF (signed distance field) fonts, which are nice enough for me--but that is not ready to use out of the box.
I would just render text to a canvas and use it as a texture in your Three.js scene. That's how I do it in my side project and it works without any extra dependency.
> webgl and WASM
I just found this...
Google's CanvasKit - Skia + WebAssembly
https://skia.org/user/modules/canvaskit
I just found this...
Google's CanvasKit - Skia + WebAssembly
https://skia.org/user/modules/canvaskit
This might work well with Golem (www.golem.network) because they've implemented WASM which opens up many possibilities. I haven't found a cheaper way to render.
Could we get a nice way to mark this as "Not Open Source"?
I spent far too long looking for technical details, a github or similar on that page before I realized that this wasn't open.
I'm not opposed to non-open source software, but it would be nicer if this was a bit more up front.
I spent far too long looking for technical details, a github or similar on that page before I realized that this wasn't open.
I'm not opposed to non-open source software, but it would be nicer if this was a bit more up front.
Also, it is covered by a patent.
I do recall somewhat recently a great improvement was made to SDF using multiple channels of information: https://github.com/Chlumsky/msdfgen
I wonder how they both compare. I am guessing Slug is more accurate but certainly also much more intensive, if its actually rendering outlines.
I wonder how they both compare. I am guessing Slug is more accurate but certainly also much more intensive, if its actually rendering outlines.
As impressive as it is, msdfgen is not actually a vector renderer. It's a technique that allows each texel to encode the distance to two separate edges instead of one. The edges are selected with a bunch of heuristics, but this can fail on complex outlines with fine detail. It's fairly easy to find fonts that msdfgen fails to properly render at certain sizes.
Of course its not a vector renderer, it is using signed distance fields after all. Still, if you want font outlines on GPU, sometimes what you want is probably SDF (like in video games.) MSDF also has some other disadvantages compared to stock SDF since the distance is less accurate outside the actual font boundary.
This kind of reminds me of http://wdobbie.com/ since the only two posts he has are about rendering fonts directly from the bezier curve data of the font.
It looks great!
Too bad the site is very mysterious about licensing and pricing.
Did anybody contact them to request a quote?
Too bad the site is very mysterious about licensing and pricing.
Did anybody contact them to request a quote?
How difficult would it be for this library, or something akin to it, to become the first thing loaded when a PC boots? For several years now I have thought the ancient default of a 'textmode' as the underlying and initial display was destined to only become more and more useless as pixel densities continue to climb. We need the first display mode available to an OS to support vector display. Raster images can come later. I don't know what all is involved in initializing a GPU and handing the display over to it, though, so I'm curious how hard it would be. Would it absolutely require a new BIOS?
You don't need this for that; a 2D CPU-based font renderer would do what you want.
I have several high resolution screens. I can see my BIOS boot text just fine. You're talking about a solution in search of a problem.
Yes, monitors have been forced to include scalers that enable OS to use extremely low resolution modes. The 'problem' is that this mode of display makes the first experience a user sees to betray the extremely high fidelity modern displays are actually capable of. I understand if you personally feel that starting up into 80x25 text mode is still acceptable in 2019 with 4k displays, and that's fine. But if someone wanted to build a brand new OS which was designed from the ground up as if it was built for and with the actual technology we have now, rather than the technology we had 30 years ago, I am just asking how difficult that would be.
Have you ever used a Mac laptop? It boots up with a crisp and clear display of the Apple logo. It's not text mode. It's either actually using the native resolution or using a sufficiently good resolution that I can't tell. This shows that if the manufacturer is willing enough, the first experience a user sees does not have to betray the extremely high fidelity modern displays are actually capable of.
> Have you ever used a Mac laptop? It boots up with a crisp and clear display of the Apple logo. It's not text mode. It's either actually using the native resolution or using a sufficiently good resolution that I can't tell.
So do PC laptops that do UEFI boot since Windows 8.
It's not really problem on laptops, but more on desktops, especially if you have add-on cards that initialize themselves with custom UEFI addon. Or when you need to work in UEFI shell. Or when you use boot manager in text mode, like grub (but grub know how to switch modes, at least). Or miriad of other things, that fall outside of the happy path of bootloader booting the OS on fixed hardware.
So do PC laptops that do UEFI boot since Windows 8.
It's not really problem on laptops, but more on desktops, especially if you have add-on cards that initialize themselves with custom UEFI addon. Or when you need to work in UEFI shell. Or when you use boot manager in text mode, like grub (but grub know how to switch modes, at least). Or miriad of other things, that fall outside of the happy path of bootloader booting the OS on fixed hardware.
It looks like a great piece of code, and I wish I could use it. Maybe the author would consider doing a free-for-open-source type model like many other companies do? It would have the benefit of allowing developers to become familiar with the technology and possibly encourage wider use, too. To be clear, I'm not saying the author needs to open-source it, but he might wish to consider distributing a static lib.
1. https://github.com/servo/pathfinder