Les 10 ans de l’algorithme Slug

• L’algorithme Slug, qui effectue un rendu de polices basé sur des courbes de Bézier sur GPU, rend directement les données vectorielles sans texture, et est utilisé dans de nombreux secteurs comme le jeu vidéo, la CAO, le montage vidéo et les équipements médicaux
• Son exclusivité a été abandonnée à compter du 17/03/2026, ce qui signifie que le brevet a été entièrement versé dans le domaine public, et que tout le monde peut désormais l’utiliser librement
• Les versions récentes ont amélioré les performances et l’efficacité du code grâce notamment à l’optimisation band split et à la suppression du supersampling, ainsi qu’à la simplification du mode de rendu des emoji
• Le plus grand changement est la fonction de dilatation dynamique (dynamic dilation), qui calcule automatiquement l’extension optimale des bordures selon la taille du glyphe et le point de vue
• Grâce au code de shaders de référence sur GitHub, publié sous licence MIT, chacun peut librement l’implémenter

---

Développement et diffusion de l’algorithme Slug

• L’algorithme Slug a été développé à l’automne 2016 et présenté en 2017 dans un article du JCGT
  • Par la suite, Slug Library 1.0 a été commercialisée et concédée sous licence à de grandes entreprises comme Activision, Blizzard, Ubisoft et Adobe
  • Il est utilisé dans des domaines variés, notamment le jeu vidéo, la visualisation scientifique, la CAO, le montage vidéo, les équipements médicaux et les planétariums
• À l’origine, il a été conçu pour le rendu de texte haute qualité du C4 Engine, puis a aussi été appliqué à l’éditeur d’équations Radical Pie
  • Il permet de représenter en haute résolution des éléments graphiques vectoriels tels que des formules, parenthèses et flèches

Évolution de la méthode de rendu

• Slug rend directement sur GPU les données de courbes de Bézier sans texture précalculée
  • Il reste robuste face aux erreurs en virgule flottante tout en conservant des courbes lisses et des angles nets
• L’optimisation band split apportait des gains de vitesse sur les grands glyphes, mais a été supprimée en raison de baisses de performances sur les petites polices et d’une complexité accrue
  • Cela a permis de simplifier le pixel shader et de réduire de moitié la taille de la texture des données de bande
• Le supersampling adaptatif était utilisé pour atténuer l’aliasing sur les petites polices, mais son effet était limité et il a été remplacé par la nouvelle technique de dilatation
• Le rendu d’emoji multicolores a été modifié pour traiter chaque couche comme un glyphe indépendant, ce qui a amélioré les performances et simplifié le code

Dilatation dynamique (Dynamic Dilation)

• Auparavant, l’extension des bordures d’un glyphe devait être définie manuellement avec une distance fixe
  • Cela entraînait des pertes de bordure sur les petites polices et un gaspillage d’espace inutile sur les grandes
• La dilatation dynamique est calculée automatiquement dans le vertex shader, ce qui détermine la distance d’extension optimale à chaque rendu de glyphe
  • Elle étend les bordures par demi-pixel à l’aide de la matrice MVP et de la taille du viewport
  • Selon le changement de point de vue, une distance de dilatation différente peut être appliquée à chaque vertex
• Mathématiquement, elle est dérivée comme une équation du second degré permettant de trouver la distance d satisfaisant la condition d’extension d’un demi-pixel dans l’espace du viewport
  • La solution finale prend la forme (d = \frac{s^3t \pm s^2\sqrt{u^2 + v^2}}{u^2 + v^2 - s^2t^2})
  • Le signe positif est choisi pour déplacer le point vers l’extérieur
• Afin de conserver la taille du glyphe, une correction des coordonnées dans l’espace em est également effectuée, avec stockage de la matrice jacobienne inverse pour chaque vertex

Abandon du brevet et annonce de publication

• L’algorithme Slug a obtenu en 2019 le brevet américain (US10373352B1), mais a renoncé à son exclusivité à compter du 17 mars 2026, alors qu’elle devait courir jusqu’en 2038
  • La durée restante du brevet a été officiellement abandonnée auprès de l’USPTO par dépôt du formulaire SB/43 et paiement des frais
• En conséquence, tout le monde peut désormais implémenter et utiliser librement l’algorithme Slug
  • Les usages commerciaux comme non commerciaux sont autorisés, sans risque de violation de propriété intellectuelle
• Un dépôt GitHub a été publié comme référence d’implémentation : https://github.com/EricLengyel/Slug
  • Il est fourni sous licence MIT et comprend un pixel shader amélioré par rapport à l’article du JCGT, ainsi qu’un vertex shader intégrant la dilatation dynamique

Importance de Slug

• Slug s’est imposé comme une implémentation emblématique du rendu de polices vectorielles sur GPU
• Dix ans d’évolution ont permis d’améliorer à la fois les performances, la simplicité et la qualité
• La levée du brevet ouvre la voie à une adoption et une extension libres à l’échelle de l’industrie

[dalinaum]

C'est une excellente nouvelle.

[GN⁺]

Avis sur Hacker News

• C’est une très bonne nouvelle. J’avais déjà admiré l’élégance de cet algorithme, mais c’était frustrant de ne pas pouvoir l’utiliser dans le FOSS à cause du brevet
  Maintenant qu’il a été versé au domaine public après un certain temps, c’est vraiment appréciable. Si je me retrouve un jour à créer un émulateur de terminal, j’aimerais essayer cet algorithme rien que pour la beauté du code
  • L’auteur a lui-même expliqué qu’il avait obtenu le brevet de l’algorithme Slug en 2019, mais qu’il trouvait excessif d’en conserver l’exclusivité jusqu’en 2038. À partir d’aujourd’hui, il verse donc définitivement le brevet de Slug dans le domaine public
  • Je pense que je serais favorable aux brevets logiciels s’ils n’étaient valables que huit ans environ
• Son projet le plus récent est RadicalPie
  C’est un éditeur professionnel de formules pour Windows 10/11, qui utilise Slug comme moteur de rendu, et coûte 60 dollars. Il s’en sert probablement pour écrire le livre FGED
  • Il y a 25 ans, j’aurais trouvé ça vraiment formidable. Mais aujourd’hui, on voit rarement des gens faire ce genre de travail sur Windows
    Cela dit, c’est une excellente alternative à MathType, et le fait que l’intégration OLE permette une bonne insertion dans Word est impressionnant
• J’ai utilisé Slug dans un ancien travail, et c’était vraiment une bibliothèque conçue comme une œuvre d’art
  Je pense que c’est le sommet de l’ingénierie logicielle. Merci à l’auteur de l’avoir offert au domaine public
• Merci Eric. Je me demande quelles seraient les différences entre son approche et des projets comme Vello
• J’aime beaucoup voir des histoires où quelqu’un qui a créé un logiciel complexe et utile reçoit une juste rémunération
  J’aimerais qu’il y ait davantage d’exemples de ce genre
• Nouvelle étonnante. Merci à Eric
  À noter aussi que le brevet Loop-Blinn de Microsoft (pour les courbes cubiques) va bientôt expirer, ce qui pourrait beaucoup changer le paysage du rendu de texte
• Vraiment génial. Je m’étais déjà demandé si Ruffle pourrait implémenter quelque chose de similaire pour le graphisme vectoriel accéléré par GPU
  À l’époque, ils utilisaient une méthode qui approchait les courbes avec des triangles, mais je ne sais pas si c’est toujours le cas
• Excellente nouvelle. Vu la vitesse du matériel actuel, il n’y a aucune raison de ne pas rendre directement les glyphes à partir des courbes de Bézier
  Les anciennes approches par atlas de textures ou SDF m’ont toujours semblé être des expédients, avec une qualité qui se dégradait quand l’échelle changeait
  Maintenant que Slug est disponible, j’espère que les grandes bibliothèques et les moteurs de jeu adopteront davantage de méthodes de rendu de meilleure qualité
• J’avais travaillé autrefois avec le moteur de jeu C4 de l’auteur, et c’était déjà il y a 20 ans
  Je ne savais pas qu’il était encore aussi actif dans ce domaine
• Je me demande si quelqu’un l’a mis sur ShaderToy 😄