ครบรอบ 10 ปีของอัลกอริทึม Slug

• อัลกอริทึม Slug สำหรับการเรนเดอร์ฟอนต์แบบ อิงเส้นโค้ง Bézier บน GPU ทำการ เรนเดอร์ข้อมูลเวกเตอร์โดยตรงโดยไม่ใช้เท็กซ์เจอร์ และถูกใช้งานในหลากหลายอุตสาหกรรม เช่น เกม, CAD, การตัดต่อวิดีโอ, อุปกรณ์การแพทย์ เป็นต้น
• ได้สละสิทธิ์ผูกขาดตั้งแต่วันที่ 2026/3/17 ทำให้ สิทธิบัตรถูกปล่อยสู่สาธารณสมบัติอย่างสมบูรณ์ และใครก็สามารถใช้งานได้อย่างเสรี
• เวอร์ชันล่าสุดได้ปรับปรุงประสิทธิภาพและประสิทธิผลของโค้ด ด้วย การนำ band split optimization และ supersampling ออก, การทำให้วิธีเรนเดอร์อีโมจิง่ายขึ้น เป็นต้น
• การเปลี่ยนแปลงที่ใหญ่ที่สุดคือฟีเจอร์ dynamic dilation ซึ่งคำนวณการขยายขอบเขตที่เหมาะสมที่สุดโดยอัตโนมัติตามขนาด glyph และมุมมอง
• ใคร ๆ ก็สามารถนำไปใช้งานได้อย่างอิสระผ่าน โค้ด shader อ้างอิงบน GitHub ที่เผยแพร่ภายใต้สัญญาอนุญาต MIT

---

การพัฒนาและการขยายการใช้งานของอัลกอริทึม Slug

• Slug ถูกพัฒนาขึ้นในช่วงฤดูใบไม้ร่วงปี 2016 และเผยแพร่เป็นบทความ JCGT ในปี 2017
  • หลังจากนั้น Slug Library 1.0 ก็ถูกนำออกสู่เชิงพาณิชย์ และให้สิทธิ์ใช้งานแก่บริษัทหลัก ๆ เช่น Activision, Blizzard, Ubisoft, Adobe
  • ถูกใช้งานในหลากหลายสาขา เช่น เกม, การทำภาพวิทยาศาสตร์, CAD, การตัดต่อวิดีโอ, อุปกรณ์การแพทย์, ท้องฟ้าจำลอง
• เดิมทีถูกพัฒนาขึ้นเพื่อการเรนเดอร์ข้อความคุณภาพสูงของ C4 Engine และภายหลังก็นำไปใช้กับ Radical Pie โปรแกรมแก้ไขสมการ ด้วย
  • ใช้แสดงองค์ประกอบกราฟิกเวกเตอร์ เช่น สมการ, วงเล็บ, ลูกศร ให้มีความละเอียดสูง

วิวัฒนาการของวิธีการเรนเดอร์

• Slug ทำการ เรนเดอร์ข้อมูลเส้นโค้ง Bézier บน GPU โดยตรงโดยไม่ต้องใช้เท็กซ์เจอร์ที่คำนวณล่วงหน้า
  • ทนทานต่อความคลาดเคลื่อนของ floating-point และคงไว้ทั้งเส้นโค้งที่เรียบลื่นและมุมที่คมชัด
• band split optimization เคยช่วยเพิ่มความเร็วใน glyph ขนาดใหญ่ แต่ในฟอนต์ขนาดเล็กกลับทำให้ประสิทธิภาพลดลงและเพิ่มความซับซ้อน จึงถูกนำออก
  • ส่งผลให้ pixel shader เรียบง่ายขึ้น และ ขนาดเท็กซ์เจอร์ข้อมูล band ลดลงครึ่งหนึ่ง
• adaptive supersampling เคยถูกใช้เพื่อลด aliasing ในฟอนต์ขนาดเล็ก แต่เนื่องจากผลลัพธ์มีจำกัดและถูกแทนที่ด้วยเทคนิคการขยายแบบใหม่ จึงถูกนำออก
• การเรนเดอร์อีโมจิหลายสี ถูกเปลี่ยนเป็นวิธีที่จัดการแต่ละเลเยอร์เป็น glyph อิสระ ทำให้ประสิทธิภาพดีขึ้นและโค้ดง่ายขึ้น

Dynamic Dilation

• เดิมทีการขยายขอบเขตของ glyph ต้อง กำหนดระยะคงที่ด้วยตนเอง
  • ในฟอนต์ขนาดเล็กจะเกิดการสูญเสียขอบเขต ส่วนในฟอนต์ขนาดใหญ่จะสิ้นเปลืองพื้นที่โดยไม่จำเป็น
• dynamic dilation จะถูก คำนวณอัตโนมัติใน vertex shader เพื่อกำหนดระยะขยายที่เหมาะสมที่สุดทุกครั้งที่เรนเดอร์ glyph
  • ใช้ เมทริกซ์ MVP และขนาด viewport เพื่อขยายขอบเขตในระดับครึ่งพิกเซล
  • สามารถใช้ระยะ dilation ที่ต่างกันในแต่ละ vertex ตามการเปลี่ยนแปลงของมุมมอง
• ในเชิงคณิตศาสตร์ จะได้มาจากสมการกำลังสองที่ใช้หาระยะ d ซึ่งทำให้ ตรงตามเงื่อนไขการขยายครึ่งพิกเซลใน viewport space
  • คำตอบสุดท้ายอยู่ในรูป (d = \frac{s^3t \pm s^2\sqrt{u^2 + v^2}}{u^2 + v^2 - s^2t^2})
  • เลือกเครื่องหมายบวกเพื่อให้เคลื่อนที่ไปทางด้านนอก
• เพื่อคงขนาดของ glyph เอาไว้ ยังมีการ ปรับแก้พิกัด em-space ด้วย และเก็บเมทริกซ์ Jacobian ผกผันไว้ในแต่ละ vertex

การยกเลิกสิทธิบัตรและการประกาศเปิดให้ใช้

• อัลกอริทึม Slug ได้รับ สิทธิบัตรสหรัฐฯ (US10373352B1) ในปี 2019 แต่ได้ สละสิทธิ์ผูกขาดที่เดิมมีถึงปี 2038 ตั้งแต่วันที่ 17 มีนาคม 2026
  • ดำเนินการสละระยะเวลาคุ้มครองที่เหลือของสิทธิบัตรอย่างเป็นทางการผ่าน การยื่นแบบฟอร์ม SB/43 ต่อ USPTO และชำระค่าธรรมเนียม
• ด้วยเหตุนี้ ทุกคนจึงสามารถ นำอัลกอริทึม Slug ไปพัฒนาและใช้งานได้อย่างเสรี
  • อนุญาตทั้งเพื่อวัตถุประสงค์เชิงพาณิชย์และไม่เชิงพาณิชย์ โดยไม่ต้องกังวลเรื่องการละเมิดทรัพย์สินทางปัญญา
• มีการเผยแพร่ GitHub repository (https://github.com/EricLengyel/Slug) เพื่อใช้อ้างอิงการพัฒนาจริง
  • ให้ใช้งานภายใต้ สัญญาอนุญาต MIT และมีทั้ง pixel shader ที่ปรับปรุงจากบทความ JCGT รวมถึง vertex shader ที่มี dynamic dilation

ความสำคัญของ Slug

• Slug ได้กลายเป็น หนึ่งในตัวอย่างสำคัญของการเรนเดอร์ฟอนต์เวกเตอร์บน GPU
• ตลอด 10 ปีที่ผ่านมา มีการพัฒนาให้ดีขึ้นทั้งในด้าน ประสิทธิภาพ, ความเรียบง่าย, และคุณภาพ
• การปลดสิทธิบัตรทำให้เกิด โอกาสในการนำไปใช้และต่อยอดได้อย่างเสรีในอุตสาหกรรมโดยรวม

[dalinaum]

เป็นข่าวที่ยอดเยี่ยมมากครับ

[GN⁺]

ความเห็นจาก Hacker News

• เป็นข่าวที่ยอดเยี่ยมมาก เคยทึ่งกับ ความงดงามของอัลกอริทึมนี้ มาก่อน แต่ก็น่าเสียดายที่ใช้กับ FOSS ไม่ได้เพราะติดสิทธิบัตร
  ตอนนี้เขานำมันไป อุทิศให้เป็นสมบัติสาธารณะ หลังผ่านไประยะหนึ่งแล้ว ถือเป็นเรื่องที่น่าขอบคุณมาก ถ้าวันหนึ่งได้ทำเทอร์มินัลอีมูเลเตอร์ขึ้นมา ก็อยากลองใช้อัลกอริทึมนี้เพราะเสน่ห์เชิงสุนทรียะของโค้ด
  • ผู้เขียนอธิบายด้วยตัวเองว่า เขาได้รับสิทธิบัตรอัลกอริทึม Slug ในปี 2019 แต่รู้สึกว่าการผูกขาดสิทธิ์ไปจนถึงปี 2038 นั้นนานเกินไป ดังนั้นนับจากวันนี้ สิทธิบัตร Slug จึงถูกอุทิศให้เป็นสมบัติสาธารณะอย่างถาวร
  • คิดว่าถ้าสิทธิบัตรซอฟต์แวร์ มีผลแค่ราว 8 ปี ก็น่าจะพอเห็นด้วยได้
• โปรเจ็กต์ล่าสุดของเขาคือ RadicalPie
  เป็น โปรแกรมแก้ไขสมการแบบมืออาชีพ สำหรับ Windows 10/11 ใช้ Slug เป็นเอนจินเรนเดอร์ และมีราคา 60 ดอลลาร์ น่าจะเป็นสิ่งที่เขาใช้ตอนเขียนหนังสือ FGED
  • ถ้าเป็นเมื่อ 25 ปีก่อนคงดีใจมาก แต่ทุกวันนี้แทบไม่เห็นใครทำงานแบบนี้บน Windows แล้ว
    ถึงอย่างนั้นก็เป็นทางเลือกแทน MathType ที่ยอดเยี่ยม และก็น่าประทับใจที่ รองรับการทำงานร่วมกับ OLE จึงแทรกลง Word ได้ดี
• ที่ทำงานเก่าเคยใช้ Slug และมันเป็น ไลบรารีที่ออกแบบได้อย่างมีศิลปะ จริงๆ
  คิดว่าเป็นจุดสูงสุดของวิศวกรรมซอฟต์แวร์เลย ขอบคุณผู้เขียนที่บริจาคสิ่งนี้ให้เป็นสมบัติสาธารณะ
• ขอบคุณ Eric อยากรู้จริงๆ ว่าแนวทางของเขาจะแตกต่างจากโปรเจ็กต์อย่าง Vello อย่างไร
• ชอบมากที่ได้เห็นเรื่องราวของคนที่สร้างซอฟต์แวร์ซับซ้อนแต่มีประโยชน์ แล้วได้รับ ผลตอบแทนที่เป็นธรรม
  อยากให้มีกรณีแบบนี้มากขึ้น
• เป็นข่าวที่น่าทึ่งมาก ขอบคุณ Eric
  อีกอย่าง สิทธิบัตร Loop-Blinn ของ Microsoft (สำหรับเส้นโค้งกำลังสาม) ก็กำลังจะหมดอายุในไม่ช้า ซึ่งอาจทำให้วงการการเรนเดอร์ข้อความเปลี่ยนไปมาก
• ยอดเยี่ยมจริงๆ ก่อนหน้านี้เคยสงสัยว่า Ruffle จะทำกราฟิกเวกเตอร์เร่งด้วย GPU แบบคล้ายๆ กันได้ไหม
  ตอนนั้นใช้วิธีประมาณเส้นโค้งด้วยสามเหลี่ยม แต่ไม่รู้ว่าตอนนี้ยังเป็นแบบนั้นอยู่หรือเปล่า
• เป็นข่าวที่ดีมาก เมื่อดูจากความเร็วของฮาร์ดแวร์ทุกวันนี้ ก็ไม่มีเหตุผลอะไรที่เราจะ เรนเดอร์ glyph จากเส้นโค้ง Bezier โดยตรง ไม่ได้
  วิธีแบบ texture atlas หรือ SDF ในอดีตดูเหมือนเป็นเพียงทางออกชั่วคราว และคุณภาพก็ลดลงเมื่อสเกลเปลี่ยน
  พอ Slug ถูกเปิดให้ใช้งานแล้ว ก็หวังว่าไลบรารีหลักๆ หรือเกมเอนจินต่างๆ จะหันมาใช้ วิธีเรนเดอร์คุณภาพสูง กันมากขึ้น
• เมื่อก่อนเคยทำงานกับเกมเอนจิน C4 ของผู้เขียน นี่ก็ผ่านมา 20 ปีแล้ว
  ไม่รู้มาก่อนเลยว่าเขายังทำงานในสายนี้อย่างแข็งขันอยู่
• สงสัยว่ามีคนเอาไปลง ShaderToy แล้วหรือยัง 😄