This is wonderful news, and my sincere thanks to the author.
I remember coming upon this algorithm several years ago, and thinking it was extremely elegant and very appealing, but being disappointed by the patent status making it unusable for FOSS work. I really appreciate the author's choice to dedicate it to the public domain after a reasonable amount of time, and congratulations on the success it had while proprietary!
Now if I ever get around to writing that terminal emulator for fun, I'll be tempted to do it with this algorithm for the code's aesthetic appeal.
> I was granted a patent for the Slug algorithm in 2019, and I legally have exclusive rights to it until the year 2038. But I think that’s too long. The patent has already served its purpose well, and I believe that holding on to it any longer benefits nobody. Therefore, effective today, I am permanently and irrevocably dedicating the Slug patent to the public domain.
Yes, now that SDF font rendering is the industry's preference, he drops the software patent. That is, he is dropping the patent because it isn't a commercially viable piece of software, not because he is ethically opposed to it. Great virtue signaling though.
Seems more like he had the patent long enough to build a sustainable business from his own work, and now he’s been able to earn enough from it that others’ implementations aren’t a risk to him.
Which is kind of the entire point of patents, just that they last way too long relative to the speed of technological progress
He said "holding on to it any longer benefits nobody", implicitly including himself. He may believe that it's to his advantage for the patent to be more widely used.
Which makes sense--I don't doubt that he is a subject matter expert where this patent is concerned. If this algorithm continues to be widely used or its use increases, then that would be likely be good for him.
SDF font rendering was common long before Slug, and Slug is supposed to be the better solution (I haven't used it though, so cannot comment on its pros and cons vs SDF, but one obvious disadvantage of SDF is that you still need a font atlas texture, and that can get very big if you need to render some East Asian character sets).
SDF font rendering has been around 20+ years though? Valve really popularized in their 2007 SIGGRAPH paper and Chlumský developed MSDF font rendering in a 2015 thesis.
SDF font rendering was an industry standard maybe from 2007-2010. and you probably won’t believe what happened to OpenGL since then. Don’t even look into at what people are doing with GPUs these days, you won’t like it one bit!
My feeling is that copyrights should be infinitely renewable, with say a 20 year term, but the renewal fee should double with each term so that Disney can have their infinite copyright on Snow White but at an ever-increasing cost so that they will need to make a decision about whether it makes sense to keep it.
My utopian vision: First registration is free and automatic. Copyright holders get an automated notification of expiring copyright and renewal is, say $1000 for the first term (adjusting for inflation) and doubling thereafter (also adjusting for inflation, so you don’t get a $2000 renewal but more like $4400 with 4% inflation). For corporate-held and posthumous extensions, the term would be 10 years.
The thing here is the exponentially increasing cost of renewing the copyright, with the inflation-adjustment I proposed and the 10-year term for a corporate or posthumous copyright, in 90 years, that $1000 renewal fee goes to $256000 in inflation-adjusted dollars. 110 years it’s a million dollars, 210 years it’s a billion dollars. If a work is worth spending that kind of money on renewing the copyright, why not let them keep it?
I used Slug at a previous job. It is an excellent, artfully crafted library; really the pinnacle of software engineering in my opinion. Thanks to the author for donating the algorithm to the public domain!
> But I don't actually know many people still doing any of this sort of work on Windows.
Most primary, secondary, and pre-university school teachers without an institutional understanding of LaTeX, which admittedly has an extremely high (technical, not financial) barrier to entry compared to Microsoft Word + MathType. This is what my secondary school teachers used, for instance. They're given bog-standard laptops with Windows to work with.
Also exam setters and writers in places like Cambridge University Press and Assessment. If you took a GCSE, O-level, or A-level exam administered by them, it had pretty high quality typesetting for maths, physics diagrams, chemistry skeletal diagrams and reaction pathways... But almost none of it was done with LaTeX, and instead probably all add-ons to Microsoft Word or Adobe InDesign.
I agree that it's a bit late but I don't think the issue is use of Windows (or Word, if that's what you're implying).
> It's an awesome replacement for MathType. It uses OLE so that it embeds in Microsoft Word nicely.
But that's the rub - OLE doesn't embed particularly nicely. I haven't used it in over a decade (maybe two?). It's sort of very softly deprecated.
The new equation editor in Word which isn't based on MathType, and doesn't use OLE, works much more smoothly than the old one, even if it doesn't support everything. ("New"? I just checked and it was introduced in 2007!) I think a typical user would have to be really desperate for extra functionality to abandon that level of integration, at which point you'd probably switch away from Word altogether.
LaTeX or its variants on your favorite OS, which is increasingly not Windows.
Most journals don’t want submissions in Word (there are notable exceptions, e.g. Nature), and conferences without massive editorial budgets want their submissions in a format that makes it easy for them to produce proceedings (again, not Word).
I don’t know to what extent Typst is taking off recently.
I personally wrote my thesis in LuaTeX with figures in TikZ. I have no great love for the TeX language [0] or TikZ, but there are three great properties of this stack that Word lacks:
1. It plays well with version control.
2. The output quality can be very high.
3. You can script the generation of figures, including text and equations that match the formatting of the containing document, in a real programming language, without absurd levels of complexity like scripting Word. So I had little Python programs that printed out TikZ.
No, I do not expect the average high school teacher to do this.
[0] In fact, I think both the language and the tooling are miserable to work with.
There are two ways to get winding numbers and then decide on filled or empty by some rule like non-zero or even-odd:
a) The winding number of a point is the number of intersections of a scanline and a closed path.
b) The winding number around a point is the total angle subtended by the path at that point.
Slug uses approach a) and that comes with a lot of edge cases (see chart in the post) and numerical precision issues. The approach by loop & blinn uses b) and is thus simpler and more robust. Likewise the patent on that one expired too: https://news.ycombinator.com/item?id=47416736#47420450
Loop and blinn does not compute a winding number using the b) method. It avoids the issue of a winding number by assuming there's only 1 bezier curve per triangle, which requires a complicated triangulation step. It can produce some nasty geometry in more complex cases. With Slug, you can use only 1 quad per glyph if you want.
Also just to clarify regarding this statement:
> Slug uses approach a) and that comes with a lot of edge cases (see chart in the post) and numerical precision issues
Slug does not have numerical precision issues. It's the breakdown into different cases that _solves_ those issues, whereas your statement makes it sound like slug has _both_ the case complexity and the precision issues.
> It avoids the issue of a winding number by assuming there's only 1 bezier curve per triangle
The original paper did assume no overlap yes. But that is not how anybody would implement it. For a long time one would use the stencil buffer with different operations depending on the front-face / back-face (this is where the paths rotation around the sample comes in and what makes this an angle based approach).
> which requires a complicated triangulation step. It can produce some nasty geometry in more complex cases.
Again, not how anybody would implement this. You can just stream the quadratic bezier curves unprocessed into the vertex shader, literally the simplest thing conceivable.
> With Slug, you can use only 1 quad per glyph if you want.
Nowadays one would probably implement loop & blinn in a tiled compute shader too (instead of using stencil buffers) to reduce memory bandwidth and over draw. That way you also get one quad per glaph, but without any of the geometry special casing that Slug does.
> It's the breakdown into different cases that _solves_ those issues, whereas your statement makes it sound like slug has _both_ the case complexity and the precision issues.
Correct, might have worded that badly. Still remains a trade off in a) which b) does not have.
[1] and [2] sound similar to what you are describing. They still involve triangulating the shape, but the triangulation process seems much simpler than the loop and blinn paper. However, if you want to do distance based anti-aliasing rather than supersampling, things are going to get complicated again as you have to expand the shape outline to capture more pixel centers.
I don't see a straightforward way to apply this technique in a pixel shader that includes multiple curves per triangle. I feel like any attempt to do that will approach the complexity of Slug, but maybe it's my own shortcoming that I don't see it. I would love to read more detailed information on that if you have it.
> [1] and [2] sound similar to what you are describing. They still involve triangulating the shape, but the triangulation process seems much simpler
Yes, they describe one variation of the angle based method to winding numbers by spanning a triangle fan from an arbitrarily chosen pivot point / vertex.
> if you want to do distance based anti-aliasing rather than supersampling
Particularly when it comes to rendering vector graphics I think of analytic anti-aliasing methods as somewhat cursed and prefer multisampling [0], at least for magnification. For minification mip-mapping remains the go to solution. However, if you only render 2D text on a 2D plane, which is typically overlap free, then these correctness issues don't matter.
> I don't see a straightforward way to apply this technique in a pixel shader that includes multiple curves per triangle
All modern vector renderers I know of avoid triangle rasterization entirely. Like I said, they typically do tiles (screen space partitioned into quads) in a compute shader instead of using the fixed functionality with a fragment / pixel shader. The reason is that nowadays compute is cheap and memory bandwidth is the bottle neck. Thus, it makes sense to load a bunch of overlapping geometry from global memory into workgroup shared memory, render all of it down to pixels in workgroup shared memory, and then only write these pixels back to the framebuffer in global memory.
> I feel like any attempt to do that will approach the complexity of Slug
A highly optimized implementation might very well, yes. Yet, handling the many cases of intersections of the path and the scanline won't be contributing to the complexity, which is what started this discussion.
> I would love to read more detailed information on that if you have it.
I implemented the outdated stencil buffer + triangle fan + implicit curves approach [1] if you want to take a look under the hood. The library is quite complex because it also handles the notoriously hard rational cubic bezier curves analytically, which Slug does not even attempt and just approximates. But the integral quadratic bezier curves are very simple and that is what is comparable to the scope Slug covers. It is just a few lines of code for the vertex shader [2], the fragment shader [3] and the vertex buffer setup [4].
Edit: You can even spin loop & blinn into a scanline method / hybrid: They give you the side of the curve your pixel is on [5], which is typically also the thing scanline methods are interested in. They compute the exact intersection location relative to the pixel, only to throw away most of the information and only keep the sign (side the pixel is on). So, that might be the easiest fragment shader vector renderer possible. Put it together in a shader toy [6] a while back.
You don't seem to have grokked the main feature that makes Slug interesting. The algorithm handles every single possible case uniformly through the use of a very fast classification and root eligibility determination technique. On some GPUs (including all NV from the last 10+ years), handling the full set of cases shown on the poster reduces to a single instruction (LOP3). The algorithm also eliminates all numerical precision issues -- provably -- making it the most robust of all time. There are no valid inputs for which the algorithm fails, so to say Loop-Blinn is somehow more robust is incorrect.
Thanks, Eric; for this, and for my start as a software engineer — my first commercial development work was consulting as an 18 year old building games with C4. I'm really glad Slug was able to find commercial success for you in the way that C4 unfortunately wasn't able to.
For those of you who aren't familiar with Eric's work, he's basically the Fabrice Bellard of computer graphics.
I am sorta in a position where implementing a glyph renderer as a compute shader would be helpful. This is a great opportunity to use this as a reference... exciting weekend project!
So nice to see this here.
The author's books are awesome resources for graphics and C++. It's a shame there seem to be fewer print editions available these days!?
I am not at all familiar with game development. This article reminds me of Casey Muratori mentioning a font issue in game development environment from a random podcast. On web, you can just fetch a google font whatever. No problem. On a local machine, you tend to look a well-established software like harfbuzz. But then harfbuzz could be rather a big dependency. A game is self-contained and you want your font looks cool and unique to your game, like the Diablo font. So it becomes a design issue. It's an awesome approach to let GPU render fonts. I cannot imagine how many game devs had font issues where they realized that they might have to learn how to render fonts as well not just characters and grass.
Oh wow this is crazy. This was a project that was reasonably successful commercially. And now it’s just being given away open source? What an absolutely incredibly gift to the community!!
So now the algorithm is patent-free, and the vertex and fragment shaders are open-sourced with the MIT license, what we presumably need is some open-source code to take Bezier curves from a font file (or from the loaded data from FreeType or whatever), and process them into the data format that Slug expects.
Also thank you to Eric Lengyel, I have had my eye on Slug for a while and wished it was open-source.
80 comments
Now if I ever get around to writing that terminal emulator for fun, I'll be tempted to do it with this algorithm for the code's aesthetic appeal.
> I was granted a patent for the Slug algorithm in 2019, and I legally have exclusive rights to it until the year 2038. But I think that’s too long. The patent has already served its purpose well, and I believe that holding on to it any longer benefits nobody. Therefore, effective today, I am permanently and irrevocably dedicating the Slug patent to the public domain.
Which is kind of the entire point of patents, just that they last way too long relative to the speed of technological progress
Which makes sense--I don't doubt that he is a subject matter expert where this patent is concerned. If this algorithm continues to be widely used or its use increases, then that would be likely be good for him.
My utopian vision: First registration is free and automatic. Copyright holders get an automated notification of expiring copyright and renewal is, say $1000 for the first term (adjusting for inflation) and doubling thereafter (also adjusting for inflation, so you don’t get a $2000 renewal but more like $4400 with 4% inflation). For corporate-held and posthumous extensions, the term would be 10 years.
> so that Disney can have their infinite copyright on Snow White
If copyright was inifinite, then Disney would never have been able to make Snow White in the first place. They didn't invent the story!
Even if they did, it seems like a huge negative to society for copywright not to expire.
A Professional Equation Editor for Windows 10/11 for 60$ that uses Slug for rendering. Presumably he‘s using it to write his great FGED books.
(I get it. It's an awesome replacement for MathType. It uses OLE so that it embeds in Microsoft Word nicely. Still...)
> But I don't actually know many people still doing any of this sort of work on Windows.
Most primary, secondary, and pre-university school teachers without an institutional understanding of LaTeX, which admittedly has an extremely high (technical, not financial) barrier to entry compared to Microsoft Word + MathType. This is what my secondary school teachers used, for instance. They're given bog-standard laptops with Windows to work with.
Also exam setters and writers in places like Cambridge University Press and Assessment. If you took a GCSE, O-level, or A-level exam administered by them, it had pretty high quality typesetting for maths, physics diagrams, chemistry skeletal diagrams and reaction pathways... But almost none of it was done with LaTeX, and instead probably all add-ons to Microsoft Word or Adobe InDesign.
> It's an awesome replacement for MathType. It uses OLE so that it embeds in Microsoft Word nicely.
But that's the rub - OLE doesn't embed particularly nicely. I haven't used it in over a decade (maybe two?). It's sort of very softly deprecated.
The new equation editor in Word which isn't based on MathType, and doesn't use OLE, works much more smoothly than the old one, even if it doesn't support everything. ("New"? I just checked and it was introduced in 2007!) I think a typical user would have to be really desperate for extra functionality to abandon that level of integration, at which point you'd probably switch away from Word altogether.
I'm pretty confident the "stack" is C++ on Win32, with a bunch of hand-rolled libraries and no stdlib.
> I don't actually know many people still doing any of this sort of work on Windows.
Most journals don’t want submissions in Word (there are notable exceptions, e.g. Nature), and conferences without massive editorial budgets want their submissions in a format that makes it easy for them to produce proceedings (again, not Word).
I don’t know to what extent Typst is taking off recently.
I personally wrote my thesis in LuaTeX with figures in TikZ. I have no great love for the TeX language [0] or TikZ, but there are three great properties of this stack that Word lacks:
1. It plays well with version control.
2. The output quality can be very high.
3. You can script the generation of figures, including text and equations that match the formatting of the containing document, in a real programming language, without absurd levels of complexity like scripting Word. So I had little Python programs that printed out TikZ.
No, I do not expect the average high school teacher to do this.
[0] In fact, I think both the language and the tooling are miserable to work with.
Overleaf has done a pretty good job of removing the tooling pain points, but honestly Typst can't take over soon enough.
> The output quality can be very high.
It can also be very low
a) The winding number of a point is the number of intersections of a scanline and a closed path.
b) The winding number around a point is the total angle subtended by the path at that point.
Slug uses approach a) and that comes with a lot of edge cases (see chart in the post) and numerical precision issues. The approach by loop & blinn uses b) and is thus simpler and more robust. Likewise the patent on that one expired too: https://news.ycombinator.com/item?id=47416736#47420450
Also just to clarify regarding this statement:
> Slug uses approach a) and that comes with a lot of edge cases (see chart in the post) and numerical precision issues
Slug does not have numerical precision issues. It's the breakdown into different cases that _solves_ those issues, whereas your statement makes it sound like slug has _both_ the case complexity and the precision issues.
> It avoids the issue of a winding number by assuming there's only 1 bezier curve per triangle
The original paper did assume no overlap yes. But that is not how anybody would implement it. For a long time one would use the stencil buffer with different operations depending on the front-face / back-face (this is where the paths rotation around the sample comes in and what makes this an angle based approach).
> which requires a complicated triangulation step. It can produce some nasty geometry in more complex cases.
Again, not how anybody would implement this. You can just stream the quadratic bezier curves unprocessed into the vertex shader, literally the simplest thing conceivable.
> With Slug, you can use only 1 quad per glyph if you want.
Nowadays one would probably implement loop & blinn in a tiled compute shader too (instead of using stencil buffers) to reduce memory bandwidth and over draw. That way you also get one quad per glaph, but without any of the geometry special casing that Slug does.
> It's the breakdown into different cases that _solves_ those issues, whereas your statement makes it sound like slug has _both_ the case complexity and the precision issues.
Correct, might have worded that badly. Still remains a trade off in a) which b) does not have.
I don't see a straightforward way to apply this technique in a pixel shader that includes multiple curves per triangle. I feel like any attempt to do that will approach the complexity of Slug, but maybe it's my own shortcoming that I don't see it. I would love to read more detailed information on that if you have it.
[1] https://medium.com/@evanwallace/easy-scalable-text-rendering... [2] https://web.archive.org/web/20180905215805/http://www.glprog...
> [1] and [2] sound similar to what you are describing. They still involve triangulating the shape, but the triangulation process seems much simpler
Yes, they describe one variation of the angle based method to winding numbers by spanning a triangle fan from an arbitrarily chosen pivot point / vertex.
> if you want to do distance based anti-aliasing rather than supersampling
Particularly when it comes to rendering vector graphics I think of analytic anti-aliasing methods as somewhat cursed and prefer multisampling [0], at least for magnification. For minification mip-mapping remains the go to solution. However, if you only render 2D text on a 2D plane, which is typically overlap free, then these correctness issues don't matter.
> I don't see a straightforward way to apply this technique in a pixel shader that includes multiple curves per triangle
All modern vector renderers I know of avoid triangle rasterization entirely. Like I said, they typically do tiles (screen space partitioned into quads) in a compute shader instead of using the fixed functionality with a fragment / pixel shader. The reason is that nowadays compute is cheap and memory bandwidth is the bottle neck. Thus, it makes sense to load a bunch of overlapping geometry from global memory into workgroup shared memory, render all of it down to pixels in workgroup shared memory, and then only write these pixels back to the framebuffer in global memory.
> I feel like any attempt to do that will approach the complexity of Slug
A highly optimized implementation might very well, yes. Yet, handling the many cases of intersections of the path and the scanline won't be contributing to the complexity, which is what started this discussion.
> I would love to read more detailed information on that if you have it.
I implemented the outdated stencil buffer + triangle fan + implicit curves approach [1] if you want to take a look under the hood. The library is quite complex because it also handles the notoriously hard rational cubic bezier curves analytically, which Slug does not even attempt and just approximates. But the integral quadratic bezier curves are very simple and that is what is comparable to the scope Slug covers. It is just a few lines of code for the vertex shader [2], the fragment shader [3] and the vertex buffer setup [4].
Edit: You can even spin loop & blinn into a scanline method / hybrid: They give you the side of the curve your pixel is on [5], which is typically also the thing scanline methods are interested in. They compute the exact intersection location relative to the pixel, only to throw away most of the information and only keep the sign (side the pixel is on). So, that might be the easiest fragment shader vector renderer possible. Put it together in a shader toy [6] a while back.
[0]: https://news.ycombinator.com/item?id=46473247#46530503 [1]: https://github.com/Lichtso/contrast_renderer [2]: https://github.com/Lichtso/contrast_renderer/blob/main/src/s... [3]: https://github.com/Lichtso/contrast_renderer/blob/main/src/s... [4]: https://github.com/Lichtso/contrast_renderer/blob/main/src/f... [5]: https://news.ycombinator.com/item?id=45626037#45627274 [6]: https://www.shadertoy.com/view/fsXcDj
For those of you who aren't familiar with Eric's work, he's basically the Fabrice Bellard of computer graphics.
Also, Microsoft's Loop-Blinn patent for cubic curves will expire on March 25. These might change the landscape of text rendering...
At the time they were going with, approximating the curves out of triangles. I don't know if they're still doing that though.
> But I think that’s too long. The patent has already served its purpose well, and I believe that holding on to it any longer benefits nobody.
Damn dude didn't you pay like ... over $10k for that patent?
> I was granted a patent for the Slug algorithm in 2019, and I legally have exclusive rights to it until the year 2038. But I think that’s too long.
This is cool but I did not know software patents were still a thing in the US.
Also thank you to Eric Lengyel, I have had my eye on Slug for a while and wished it was open-source.
https://web.archive.org/web/20260317185928/https://terathon....