Một thập kỷ của Slug

Eric Lengyel      Ngày 17 tháng 3 năm 2026

Cái mà ngày nay được gọi là Thuật toán Slug để hiển thị phông chữ trực tiếp từ đường cong Bézier trên GPU đã được phát triển vào mùa thu năm 2016, vì vậy năm nay đánh dấu tròn một thập kỷ kể từ khi thành lập. Tôi đã xuất bản bài viết trên JCGT về kỹ thuật này vào giữa năm 2017 và công ty của tôi đã bán giấy phép đầu tiên cho phiên bản 1.0 của Thư viện Slug không lâu sau đó. Kể từ đó, Slug đã được cấp phép rộng rãi trong ngành trò chơi điện tử cũng như bởi một loạt công ty chuyên về các lĩnh vực như trực quan hóa khoa học, CAD, chỉnh sửa video, thiết bị y tế và thậm chí cả cung thiên văn. Khách hàng của chúng tôi bao gồm Activision, Blizzard, id Software, 2K Games, Ubisoft, Warner Brothers, Insomniac, Zenimax và Adobe cùng nhiều thứ khác. Slug hóa ra lại là sản phẩm phần mềm thành công nhất mà tôi từng tạo ra.

Ban đầu tôi tạo Slug nhằm mục đích hiển thị văn bản tốt hơn cho C4 Engine, nơi phông chữ cần trông đẹp mắt không chỉ trong GUI mà còn bên trong các cấp độ trò chơi, nơi chúng có thể xuất hiện rất lớn và được nhìn ở các góc xiên. Gần đây nhất, tôi đã sử dụng Slug để xây dựng Trình chỉnh sửa phương trình Radical Pie, tất nhiên, cần khả năng hiển thị phông chữ cũng như đồ họa vector chất lượng cực cao dành cho những thứ như dấu ngoặc, căn thức và các mục thuần túy đồ họa như mũi tên và điểm đánh dấu được gắn vào biểu thức toán học. Slug cũng được sử dụng để kết xuất toàn bộ giao diện người dùng bên trong cửa sổ chỉnh sửa chính và tất cả các hộp thoại.

Bài đăng này nói về những gì đã thay đổi trong phương pháp kết xuất kể từ năm 2017, khi bài báo được xuất bản và Thư viện Slug lần đầu tiên được phát hành. Sau đó, nó kết thúc bằng một thông báo thú vị dành cho những ai muốn triển khai thuật toán Slug cho các dự án của riêng họ.

Kết xuất tiến hóa

Slug hiển thị văn bản và đồ họa vector trên GPU trực tiếp từ dữ liệu đường cong Bézier mà không cần sử dụng bản đồ kết cấu có chứa tính toán trước hoặc được lưu trong bộ nhớ đệm hình ảnh của bất kỳ loại. Thực hiện điều này một cách mạnh mẽ, đồng thời nhanh chóng và tạo ra kết quả chất lượng cao, là một bài toán khó khi chúng ta phải xử lý dấu phẩy động. các lỗi làm tròn. Tính mạnh mẽ đòi hỏi chúng ta không bao giờ nhìn thấy các thành phần giả như điểm ảnh bị rơi, điểm lấp lánh hoặc vệt trong bất kỳ trường hợp nào, có thể chứng minh là như vậy. Nhanh nhẹn có nghĩa là thuật toán có thể hiển thị bất kỳ lượng văn bản hợp lý nào trên bảng điều khiển trò chơi năm 2016 mà không ảnh hưởng đáng kể đến tốc độ khung hình. Sản xuất chất lượng cao kết quả có nghĩa là chúng ta có được văn bản được khử răng cưa độc đáo với những đường cong mượt mà và các góc nhọn khi xem ở mọi tỷ lệ và từ mọi góc độ. Các nguyên tắc của mà thuật toán kết xuất Slug đạt được tất cả những điều này được tóm tắt trong sơ đồ sau. (Nhấp để xem phiên bản PDF.)

Phương pháp xác định tính đủ điều kiện của gốc và tính toán số cuộn dây, chịu trách nhiệm về độ bền, gần như giống hệt như phương pháp hiện nay. là vào năm 2017 khi Slug được phát hành lần đầu tiên. Tuy nhiên, một số phần khác của mã kết xuất được mô tả trong bài báo đã thay đổi qua nhiều năm. Tôi sẽ mô tả ngắn gọn những thay đổi nhỏ hơn ở đây trước khi nói về phần bổ sung lớn có tên là “sự giãn nở động” trong phần riêng bên dưới.

Bài viết gốc bao gồm phần mô tả về "tối ưu hóa phân chia băng tần" có thể được bật khi biết rằng glyph sẽ được hiển thị ở kích thước lớn. Nó đã giúp tăng tốc độ cho các glyph lớn, nhưng nó cũng tạo ra một số khác biệt trong trình đổ bóng pixel có thể ảnh hưởng một chút đến hiệu suất cho văn bản được hiển thị ở kích thước nhỏ. Sự tối ưu hóa này cũng yêu cầu danh sách các đường cong giao nhau giữa mỗi dải phải được lưu trữ hai lần, một lần được sắp xếp theo các tia trỏ. theo một hướng và lại sắp xếp theo các tia hướng theo hướng ngược lại. Tốc độ cải thiện còn khiêm tốn và không được áp dụng rộng rãi nên tôi quyết định để loại bỏ nó. Điều này đã loại bỏ một số sự phức tạp trong trình đổ bóng pixel và quan trọng hơn là nó cho phép cắt giảm một nửa dữ liệu băng tần. Kết cấu chứa dữ liệu băng tần hiện sử dụng hai thành phần 16 bit thay vì bốn.

Trong phần Tiện ích mở rộng ở cuối bài viết đã có một số thảo luận về siêu mẫu. Mặc dù không cần thiết để hiển thị văn bản ở kích thước thông thường, siêu mẫu thích ứng đã được triển khai trong các phiên bản đầu tiên của Slug để cải thiện văn bản được vẽ ở kích thước rất nhỏ. Nếu văn bản nhỏ được hiển thị ở xa trong cảnh 3D, sau đó siêu mẫu làm giảm đáng kể lượng răng cưa khi máy ảnh di chuyển và vì nó có tính thích ứng nên số lượng mẫu lấy văn bản lớn hơn vẫn còn chỉ một. Siêu mẫu đã bị loại bỏ vì (a) nó chỉ tạo ra sự khác biệt đối với văn bản quá nhỏ đến mức hầu như không thể đọc được và (b) việc đặt bí danh cho văn bản nhỏ là giảm thiểu ở mức độ cao bằng kỹ thuật giãn nở được mô tả dưới đây. Việc loại bỏ siêu mẫu cũng đơn giản hóa đáng kể trình đổ bóng pixel. (Biên dịch có điều kiện đã loại bỏ mã siêu mẫu khi nó bị tắt, vì vậy việc loại bỏ nó không có nghĩa là trình đổ bóng mẫu đơn thông thường sẽ nhanh hơn chút nào.)

Phần Tiện ích mở rộng cũng đề cập đến việc thêm vòng lặp vào trình đổ bóng pixel để hiển thị biểu tượng cảm xúc nhiều màu, về cơ bản là một chồng các ký tự trong đó mỗi lớp có một màu khác nhau. Điều này tỏ ra không tối ưu vì nhiều lớp thường chỉ bao phủ một phần nhỏ tổng diện tích của vật liệu composite. glyph, nhưng các phép tính hiển thị trên mỗi lớp vẫn đang được thực hiện trên đa giác giới hạn đầy đủ. Hóa ra là tốt hơn khi hiển thị một loạt các dữ liệu độc lập các hình tượng chồng lên nhau, mặc dù nó làm tăng lượng dữ liệu đỉnh, để mỗi lớp có thể có đa giác giới hạn riêng. Điều này nhanh hơn và nó một lần nữa đơn giản hóa mã đổ bóng pixel.

Sự giãn nở động

Đã có một cải tiến lớn đối với thuật toán kết xuất kể từ khi Thư viện Slug ra đời. Nó được gọi là sự giãn nở động, và nó giải quyết được vấn đề được thảo luận trong bài đăng trước đó từ năm 2019 khi nó lần đầu tiên được thêm vào mã. Trước khi giãn nở động, người dùng phải chỉ định thủ công một khoảng cách không đổi mà theo đó mọi đa giác giới hạn của glyph sẽ được mở rộng để đảm bảo rằng tất cả các pixel được che phủ một phần đều được rasterized. Điều này có hai nhược điểm: (a) nếu bạn chọn khoảng cách quá nhỏ thì các hình tượng được hiển thị dưới một kích thước nhất định sẽ bắt đầu có các tạo tác răng cưa dọc theo chúng. ranh giới và (b) bất kỳ khoảng cách nào được chọn sẽ quá lớn đối với các hình tượng trên một mức nhất định kích thước, để lại không gian trống làm giảm hiệu suất mà không có lý do.

Tính năng giãn nở động giúp tự động đưa ra lựa chọn tối ưu và được tính toán lại trong trình đổ bóng đỉnh mỗi khi một hình tượng được hiển thị. Kỹ thuật này sử dụng mô hình-view-projection hiện tại (MVP) ma trận và kích thước khung nhìn để xác định khoảng cách một đỉnh cần được di chuyển ra ngoài dọc theo hướng bình thường của nó trong không gian đối tượng để mở rộng giới hạn một cách hiệu quả đa giác bằng nửa pixel trong không gian khung nhìn. Điều này đảm bảo rằng tâm của bất kỳ pixel bị che phủ một phần nào đều nằm bên trong đa giác giới hạn nên trình rasterizer sẽ chọn chúng lên. Khi văn bản được xem ở chế độ phối cảnh, khoảng cách giãn nở có thể khác nhau đối với mỗi đỉnh. Mã luôn tạo ra giá trị tối ưu để có không bao giờ có bất kỳ phần đệm không cần thiết nào gây lãng phí tài nguyên GPU.

Tính toán giãn nở động được thực hiện trong trình đổ bóng đỉnh được hiển thị trong sơ đồ ở trên, nhưng tôi chưa cung cấp dẫn xuất của nó ở bất kỳ đâu. Vậy chúng ta đi đây. Mục tiêu là tìm khoảng cách d chúng ta phải di chuyển một vị trí đỉnh không gian đối tượng \(\mathbf p = (p_x, p_y, 0, 1)\) dọc theo vectơ pháp tuyến của nó \(\mathbf n = (n_x, n_y, 0, 0)\) để nó tương ứng với việc mở rộng nửa pixel của đa giác giới hạn trong không gian khung nhìn. Bình thường không có độ dài đơn vị mà thay vào đó được chia tỷ lệ sao cho nó hướng đến vị trí đỉnh mới nếu cả hai cạnh liền kề của đa giác giới hạn bị đẩy ra ngoài một đơn vị khoảng cách, như thể hiện trong sơ đồ. Đầu tiên chúng tôi tính toán khoảng cách d dọc theo hướng pháp tuyến đơn vị \(\hat{\mathbf n} = (\hat n_x, \hat n_y, 0)\) rồi áp dụng điều đó cho vectơ pháp tuyến ban đầu n để thu được vị trí đỉnh mới \(\mathbf p + d\mathbf n\).

Bằng cách áp dụng ma trận MVP m (là \(4 \times 4\)), phép chia phối cảnh và tỷ lệ khung nhìn theo chiều rộng w và chiều cao h của nó cho một vị trí không gian đối tượng p bù lại khoảng cách d theo hướng pháp tuyến đơn vị \(\hat{\mathbf n}\), chúng ta có thể biểu thị sự khác biệt \(\Delta x\) và \(\Delta y\) trong không gian khung nhìn dưới dạng

\(\begin{split}\Delta x &= \dfrac{w}{2}\left[\dfrac{m_{00}(p_x + d\hat n_x) + m_{01}(p_y + d\hat n_y) + m_{03}}{m_{30}(p_x + d\hat n_x) + m_{31}(p_y + d\hat n_y) + m_{33}} - \dfrac{m_{00}p_x + m_{01}p_y + m_{03}}{m_{30}p_x + m_{31}p_y + m_{33}}\right] \\ \Delta y &= \dfrac{h}{2}\left[\dfrac{m_{10}(p_x + d\hat n_x) + m_{11}(p_y + d\hat n_y) + m_{13}}{m_{30}(p_x + d\hat n_x) + m_{31}(p_y + d\hat n_y) + m_{33}} - \dfrac{m_{10}p_x + m_{11}p_y + m_{13}}{m_{30}p_x + m_{31}p_y + m_{33}}\right].\end{split}\)

Nếu chúng ta đặt \((\Delta x)^2 + (\Delta y)^2 = (\frac{1}{2})^2\), thì độ lệch trong không gian khung nhìn là một nửa pixel. Chúng ta chỉ cần giải phương trình này cho d, nhưng nó khá lộn xộn. Khi chúng ta nhân mọi thứ ra, đơn giản hóa hết mức có thể và viết kết quả này dưới dạng phương trình bậc hai trong d, chúng ta nhận được

\(\begin{split}&{\large[}w^2(m_{03} (m_{30}\hat n_x + m_{31}\hat n_y) - m_{33}(m_{00}\hat n_x + m_{01}\hat n_y) + (m_{00}m_{31} - m_{01}m_{30})(p_x \hat n_y - p_y \hat n_x))^2 \\ & + h^2(m_{13} (m_{30}\hat n_x + m_{31}\hat n_y) - m_{33}(m_{10}\hat n_x + m_{11}\hat n_y) + (m_{10}m_{31} - m_{11}m_{30})(p_x \hat n_y - p_y \hat n_x))^2 \\ & - (m_{30}p_x + m_{31}p_y + m_{33})^2(m_{30}\hat n_x + m_{31}\hat n_y)^2{\large]}d^2 - 2{\large[}(m_{30}p_x + m_{31}p_y + m_{33})^3(m_{30}\hat n_x + m_{31}\hat n_y){\large]}d \\ & - (m_{30}p_x + m_{31}p_y + m_{33})^4 = 0.\end{split}\)

Thật thuận tiện khi thực hiện các phép gán \(s = m_{30}p_x + m_{31}p_y + m_{33}\) và \(t = m_{30}\hat n_x + m_{31}\hat n_y\), chúng ta hãy viết

\(\begin{split}&{\large[}w^2(s(m_{00}\hat n_x + m_{01}\hat n_y) - t(m_{00}p_x + m_{01}p_y + m_{03}))^2 \\ & + h^2(s(m_{10}\hat n_x + m_{11}\hat n_y) - t(m_{10}p_x + m_{11}p_y + m_{13}))^2 - s^2 t^2{\large]}d^2 \\ & - 2s^3td -s^4 = 0.\end{split}\)

Chỉ định thêm

\(\begin{split}u &= w(s(m_{00}\hat n_x + m_{01}\hat n_y) - t (m_{00}p_x + m_{01}p_y + m_{03})) \\ v &= h(s(m_{10}\hat n_x + m_{11}\hat n_y) - t(m_{10}p_x + m_{11}p_y + m_{13}))\end{split}\)

cuối cùng cho chúng ta phương trình bậc hai đơn giản hóa

\((u^2 + v^2 - s^2t^2)d^2 - 2s^3td -s^4 = 0,\)

có giải pháp

\(d = \dfrac{s^3t \pm s^2\sqrt{u^2 + v^2}}{u^2 + v^2 - s^2t^2}.\)

Việc chọn dấu cộng sẽ thu được khoảng cách hướng ra ngoài dọc theo vectơ pháp tuyến đơn vị mà đỉnh cần được di chuyển để giãn nở nửa pixel. Để đảm bảo glyph vẫn được hiển thị ở kích thước ban đầu, tọa độ lấy mẫu không gian em cũng cần được bù. Một ma trận Jacobian nghịch đảo \(2 \times 2\) được lưu trữ với mỗi đỉnh, và nó cung cấp cho chúng ta thông tin chúng ta cần để chuyển đổi sự dịch chuyển không gian đối tượng thành một vectơ bù không gian em. Ma trận Jacobian, trước khi đảo ngược, là ma trận phía trên bên trái \(2 \times 2\) phần của ma trận biến đổi chuyển đổi tọa độ không gian em thành tọa độ không gian đối tượng, tính tỷ lệ, độ giãn, độ lệch và có thể sự đảo của trục tọa độ.

Công bố bằng sáng chế

Tôi đã được cấp bằng sáng chế cho thuật toán Slug vào năm 2019 và về mặt pháp lý, tôi có độc quyền đối với thuật toán đó cho đến khi năm 2038. Nhưng tôi nghĩ thế là quá dài. Bằng sáng chế đã phục vụ tốt mục đích của nó và tôi tin rằng việc giữ nó nữa sẽ không mang lại lợi ích gì cho ai cả. Do đó, có hiệu lực từ hôm nay, tôi vĩnh viễn cống hiến bằng sáng chế Slug cho phạm vi công cộng. Điều đó có nghĩa là bất kỳ ai cũng có thể tự do thực hiện thuật toán Slug kể từ ngày này trở đi mà không có giấy phép cho bất kỳ mục đích nào họ muốn và họ không cần lo lắng về việc vi phạm bất kỳ quyền sở hữu trí tuệ nào. (Đối với bất kỳ chuyên gia pháp lý nào đọc nội dung này, công ty của tôi đã nộp mẫu SB/43 cho USPTO và trả phí để từ chối phần cuối của điều khoản đối với bằng sáng chế số 10,373,352, có hiệu lực từ ngày 17 tháng 3 năm 2026.)

Để hỗ trợ triển khai thuật toán Slug, các trình đổ bóng pixel và đỉnh tham chiếu dựa trên mã thực tế được sử dụng trong Thư viện Slug đã được đăng trong một bài viết mới. Kho lưu trữ GitHub và được cung cấp theo giấy phép MIT. Pixel shader là một bản nâng cấp đáng kể so với mã đi kèm với giấy JCGT và trình đổ bóng đỉnh bao gồm độ giãn nở động, chưa được thực hiện khi bài báo được xuất bản.

Xem thêm

• Kết xuất phông chữ tập trung vào GPU trực tiếp từ Glyph Outlines, Tạp chí kỹ thuật đồ họa máy tính, 2017.
• Trình đổ bóng tham chiếu thuật toán sên trên GitHub.
Bài đăng trên blog
• Sự giãn nở Glyph động, năm 2019.
• Trang web Thư viện Slug.