A Decade of Slug

https://terathon.com/blog/decade-slug.html

by mwkaufma • 4 months ago

760 78 4 months ago

https://web.archive.org/web/20260317185928/https://terathon....

miloignis• 4 months ago

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.

actionfromafar• 4 months ago

Software patents valid for 8 years is actually something I could get behind.

teaearlgraycold• 4 months ago

Copyrights universally dropped to ~20 years as well while we're at it.

olejorgenb• 4 months ago

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.

convexhulled• 4 months ago

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.

moralestapia• 4 months ago

Thank you for your service!

rrauenza• 4 months ago

Here's an alternate if you're also getting connection reset errors:

https://web.archive.org/web/20260317185928/https://terathon....

dang• 4 months ago

We'll put that link in the toptext as well. Thanks!

VikingCoder• 4 months ago

Is it on ShaderToy yet? :D

byearthithatius• 4 months ago

Love it when someone who makes complex, helpful software is rewarded for their efforts. More stories like this!

forrestthewoods• 4 months ago

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

aseipp• 4 months ago

Not quite, just the pixel/vertex shaders and the algorithm is public domain. Slug "the software package" is not open source (you can get a copy of it along with C4 Engine for $100 to take a peek if you want, though).

Vipitis• 4 months ago

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!

cachius• 4 months ago

His latest project is https://radicalpie.com/

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.

amluto2• 4 months ago

25 years ago I would have loved that. But I don't actually know many people still doing any of this sort of work on Windows.

(I get it. It's an awesome replacement for MathType. It uses OLE so that it embeds in Microsoft Word nicely. Still...)

mmooss3• 4 months ago

What stack are those people using?

delta_p_delta_x• 4 months ago

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.

nikanj• 4 months ago

Depressingly I don't actually know many people still doing any of this sort of work, on any platform.

quietbritishjim• 4 months ago

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.

swiftcoder• 4 months ago

Lengyel continues to be standup dude, kudos!

Cthulhu_• 4 months ago

Damn, I worked with the author's game engine (C4) about... 20 years ago now while still in school, didn't know they were still active in that area!

maximilianburke• 4 months ago

Amazing! Thank you, Eric!

leecommamichael• 4 months ago

Thank you!

lacoolj• 4 months ago

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?

elengyel7• 4 months ago

I took care of the whole thing myself without lawyers, so I ended up paying something like $950 in various filing fees.

kzrdude• 4 months ago

How did you get that diploma/plaque, is that something every patent author will have?

astroalex• 4 months ago

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!

adamrezich• 4 months ago

Finally, some good video game development news!

Validark• 4 months ago

Awesome algorithm and thank you for donating it to open source!

amagitakayosi2• 4 months ago

Amazing, Thank you Eric!!

Also, Microsoft's Loop-Blinn patent for cubic curves will expire on March 25. These might change the landscape of text rendering...

cylemons2• 4 months ago

I thought loop-blinn expired a while ago, or is the cubic curves separate from quadratic?

amagitakayosi2• 4 months ago

IIRC their patent is mainly for cubic curve filling. It's still in effect: https://patents.google.com/patent/US7564459B2/en

andai• 4 months ago

This is super cool. A few years ago I was wondering if Ruffle could do something similar, incorporate some kind of GPU accelerated vector graphics.

At the time they were going with, approximating the curves out of triangles. I don't know if they're still doing that though.

tokyovigilante• 4 months ago

Thanks Eric, much appreciated. How would you compare your approach to something like Vello (https://github.com/linebender/vello)?

elengyel7• 4 months ago

Vello is intended more for general vector graphics and would probably perform better with pictures containing lots of large paths. Slug is designed specifically for rendering glyph-like objects and would perform better with lots of text and icons.

Ono-Sendai3• 4 months ago

I was going to ask if Slug can be used as a general vector renderer. Or does it assume limits on e.g. number of curves/paths per area that are typical of fonts?

__tidu• 4 months ago

im not Eric but: having used vello (when it was in its early stages i "transplanted" it into my game engine), it is quite a beast. its got a multistage compute shader pipeline, and over time im kinda soured on the whole idea

vello will probably do great under very heavy loads but for your average UI or text document? i reckon something far simpler (like slug!) will end up being more efficient simply by avoiding all those shader launches

weslleyskah• 4 months ago

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!?

sbinnee• 4 months ago

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.

flohofwoe3• 4 months ago

well-established software like harfbuzz

Harfbuzz is only one piece of the puzzle, it's not a text renderer, only a 'text shaper' (e.g. translating a sequence of UNICODE codepoints into a sequence of glyphs). The actual font handling and text rendering still needs to be done by some other code (e.g. the readme in Mikko Mononen's Skribidi project gives a good overview about what's needed besides the actual rendering engine: https://github.com/memononen/Skribidi/)

nickitolas• 4 months ago

Harfbuzz does shaping, my understanding is slug does rendering. So they do different things

amelius• 4 months ago

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.

Lichtso4• 4 months ago

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

jeremiahkellick3• 4 months ago

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.

Lichtso4• 4 months ago

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.

elengyel7• 4 months ago

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.

Benjamin_Dobell• 4 months ago

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.

elengyel7• 4 months ago

Thanks -- nice to hear from you!

Ono-Sendai3• 4 months ago

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.

A Decade of Slug

Related Stories