Slug: GPU-Centered Font Rendering and Text Layout Library

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

And there's a paper describing the technique coming soon: https://twitter.com/EricLengyel/status/872362370689097732

He's also the author of "Mathematics for 3D Game Programming and Computer Graphics", which is a nice book that covers a lot of the fundamental topics and is a useful book to have in your library for reference if you do any 3d graphics, game or physics programming. It doesn't go too deep into the subjects, but it's a nice to have anyway.

He has done lots of work on the field, so there are quite a few contributions he has made.

http://mathfor3dgameprogramming.com/

It sounds like loop-blinn font rendering, which is well known. It helps too if you have a lib for getting outlines from a ttf.

Modern accelerated 2D graphics is exactly the same as 3D but with an orthographic projection always looking in the same direction.

Thanks for pointing that out! But please don't flag stories because of titles. Flagging is for things that don't belong on HN in the first place.

When you notice a typo or solecism that wants correcting, email us at hn@ycombinator.com. We don't see all the comments that get posted, but we do see all our emails and will usually fix things right away.