Растеризатор на truetype/opentype* шрифтове.
Тъй като сега вече е ясно, че нямам достатъчно време да напиша оригинално планирания си проект (библиотека за gui, все пак ще дам детайли по долу за пълнота) искам да правя за проект една минимална самостоятелно работеща част от него, а именно това което е в заглавието.
Какво точно ще представлява проекта?
Всеки символ в един такъв шрифт се представя, като поредица от насочени и затворени съставни криви на Безие. Посоката им определя дали площтта вътре в тях е "запълнена" или "празна" (Най-вътрешните криви имат финалната дума за това каква да е площта вътре. Ако си представим един голям кръг насочен така, че площтта вътре да е черна и вътре по малък кръг с противоположна посока, ще получим буквата "О").
Целта на библиотеката е да отваря един такъв .ttf файл и по unicode codepoint на някой символ да може да връща растерно (като поредица от пиксели) описание на този символ в избраната от потребителя резолюция (или "височина" на шрифта в пиксели).
Как точно работи проекта?
След като отворим дадения файл и парснем нужните данни според спецификацията е определим, кой пиксел от финалното изображение попада между "запълващ" контур. Най-хамалския начин това да се направи е да се провери всеки пискел със всеки компонент на контура и да се оцвети в съответния цвят, но разбира се това би било потресаващо бавно (и потресаващо грозно) и би създало aliasing (освен ако не използваме supersampling, тоест растеризиране в много висока резолюция и после смаляване, което обаче е прекалено скъпо за беден човек като мен 
).
Има ли не малоумен начин за проверяване на оцветеност на точка и можем ли да намерим по-бюджетно щадящ начин за anti-aliasing от supersampling, като едновременно с това не е толкова сложен, че да не мога или да нямам време да го имплементирам? Ами за сега спекулирам, че следното би свършило работа:
- Взимайки контурите ги превръщаме в поредиа от отсечки (ръбове), разделяйки кривите на Безие, използвайки частен случай на алгоритъма на De Casteljau, докато не надхвърлят някаква локална мярка за плоскост за съответната резолюция (тоест докато станат практически неразличими от прави) и след това заменяйки ги с отсечки.
-
Сега можем да апроксимираме лицето на оцветената площ която се съдържа във всеки пиксел (тук на него гледаме като на малко квадратче). Това може да се прави като съответно прибавяме площа на трапецоидите индуцирани от ръбовете, като спуснем хоризонтални прави от върховете на ръба до върховете на проекцията му по вертикалната координата (ръбовете с една от посоките ще са с положително лице (запълващи) а от другата с отрицателно). Накрая в зависимост от това каква част от лицето на пиксела е запълнено можем да изберем цвят между бялото и черното, по този начин използвайки естествен anti-aliasing по контурите. На пръв поглед пак изглежда, че имаме да вършим работа за всеки ръб и всеки пиксел, но с някой хитрости това може да се избегне:
- Сортираме ръбовете по най-горен връх.
- Итерирайки по редовете на растерната повърхност, пазим един масив от двойки числа (или два масива, но по начина ползваме един масив може да е по приятелски настроен към кеша, защото близките по индекс елементи от двата масива достъпваме в близко време) с големината на реда и масив от "активни" ръбове. Първото число в масива показва закритата площ в съответния пиксел, подмасива индуциран от вторите числа си го представяме като комулативна сума на площи закриващи всеки писек, т.е второто число казва, че всички пиксели нататък им се добавя тази площ, по този начин не трябва да обхождаме целия масив за всеки ръб а го правим само веднъж накрая преди да начертаем съответния ред от картинката. Масива от "активни ръбове" съдържа ръбовете, които имат отношение към съответния ред, т.е които закриват някаква площ в него
-
На всяка итерация премахваме ненужните ръбове от активния масив (тези на които най-долния им връх е над горната граница на текущия ред).
-
На всяка итерация "активираме" последователно ръбовете от нашия сортиран масив с ръбове, чиито най-горен връх започва под горната граница на текущия ред.
- Смятаме лицата за всички активни в конкретната итерация ръбове.
- Оцветяваме съответния ред според нашия масив с лицата.
- Подготвяме оставащите активни ръбове за следващата стъпка. Тук се съдържат детайли свързани с смятането на лицата, което нарочно не илюстрирам защото има много технически детайли. Идеята е, че за да може по тънко да намираме разни пресичания на ръбовете с пиксели ги представяме в slope-intercept форма, но обратната функция (защото се оказва по удобно), като пазим допълнителна информация от къде почват и свършват тъй като са отсечки, а не прави и се оказва одобно да знаем къде всеки път пресичат горната стена на конкретния ред, което трябва да опресняваме.
Какви външни библиотеки ще използвам?
Нищо освен Ръст и стандартната библиотека на езика.
До къде съм стигнал?
Имам сравнително, количество код но тъй като все още има есенциална неимплементирана функционалност на растеризатора, както и разни бъгове не се чувствам самоуверен да покажа код.
(Опционално) История на провалената ми оригинална идея.
Оригиналната ми идея беше да напиша библиотека за графичен интерфейс. Типично тези библиотеки използват два вида API дизайна, immediate mode и retained mode.
Най-общо казано, retained mode библиотеките (такива, като Qt и GTK+), поддържат интерфейс за деклариране на някакви widget-и, заедно с callback - и, които да се ипълняват при настъпването на някакво събитие свързано с дадения widget, след това програмиста дава контрола на програмата (или поне на една нишка от нея) на библиотеката и тя почва да следи за събития, чертае интерфейса и от време на време връща контрола на нишката на нашата програма като викне някой callback. Един чест недостатък на такива библиотеки е, че са оптимизирани за почти статичен интерфейс и не са подходящи за високоскоросни анимации или събития, които драстично променят интерфейса. Също така заради самия им API дизайн, често се пише екстремно количество boilerplate дори за тривиален код, също така не взаимодействат много чисто с други неща които биха искали да вземат контрол над дадена нишка (това обикновенно може да се получи ако искаме да рендърираме нещо по специално освен самия интерфейс, което и то обработва някакви асинхронни събития, прави някакви симулации и се опитва да чертае след това).
За immediate mode библиотеките (такива като nuclear и dear-imgui ) специфичното е, че те не пазят състояние и не взимат постоянен контрол над нишката. Създаването на даден widget в конкретния кадър и проверката дали в текущия момент, в който се чертае кадарът е било настъпило даденото събитие свързано с widget-а обикновенно се извършва с едно извикване (разбира се всъщност повечето такива библиотеки кешират графичната репрезентация на всеки widget за текущия кадър и го изчертават (или дават на потребителя да го изчертае) накрая, но важното е че от гледна точка на създаването на widget-и няма никакво състояние). Тези библиотеки са доста удобни за силно динамичен интерфейс и за някой приложения може да са много приятни за работа но страдат и от сериозни недостатъци. Например тъй като няма никакво състояние и библиотеката предварително не знае какво трябва да изчертае за дадения кадър, не може да се специфицира предварително layout-a чрез някакъв markup language (каквото много от retained mode библиотеките поддържат) и също така не можем да говорим релативно за widget-ите поне в общия случай. Също така тъй като на всеки кадър целия UI се изчертава наново, въпреки че производителността може да е сравнително добра, ако се използва GPU (дори по-добра от някои от по-класическите retained mode библиотеки, тъй като често те могат да използват архаични технологии и да не се възползват от графичния процесор достатъчно) в крайна сметка се върши огромно количество излишна работа (което е излишен разход на енергия при мобилните устройства, за които издръжливостта на батерията е много важна). Също така за да са responsive се изисква да вървят с голям брой кадри в секунда.
И сега в крайна сметка моята идея беше да направя експеримент, комбинирайки аспекти и от двете парадигми. Мислех си за нещо, което по интерфейс доста наподобява immediate mode, но вътрешно е повече като retained и пази сравнително много информация.
Основните проблеми, които са свързани с направата на това нещо са освен, че е трудоемко само по себе си то би зависело от доста други неща. Например една такава библиотека трябва да може да работи с графичната среда на съответната система, както и да прима вход мишка/клавиатура и накрая да има някакъв начин да изобразява нещата (най-добре би било да разчитаме на GPU, вместо на старинни неща като Win32 GDI и примитивите за чертане на X, тоест ни трябва нещо като Vulkan, Direct3D или OpenGL).
Тъй като исках библиотеката да е без външни зависимости, то би трябвало да имам някакъв начин да мога да използвам най-различни системни API-та от ръст. Това обаче не е толкова тривиално по някой причини. Ако исках да ползвам тези апита от C++ да речем, просто бих добавил съответните системни хедъри в сорса за да имам сигнатурите на функциите от апито и след това да свържа с съответната библиотека. Ако искам обаче да направя същото от ръст, чрез FFI, няма как да добавя съответните хедъри и трябва ръчно да наглася сигнатурите, това е свързано с ръчно деклариране на структури понякога имащи стотици полета, т.е имплементация на огромна част от самите хедъри в ръст, което е неприятно.
Един възможен workaround на този проблем е като направя тънък wrapper на съответните библиотеки чрез C++, и опростя интерфейса (като например вместо тези огромни структури, функциите ми приемат void* към съответните структури, които C++ си заделя и трие при съответните извиквания и си ги каства без Ръст да знае кво се случва от вътре) и след това го експортна в ръст с FFI. Това пък изисква писане на много C++ код в Rust проект...
В крайна сметка по едно време през ваканцията реших да потърся някакви компромисни варианти и все пак да пробвам да ползвам някои готови библиотеки.
Например една добра библиотека за линукската част, която ще ми позволи да създавам прозорци и да следя за инпът докато той е фокусиран е x11 , която е гол binding на xlib, всичко е директно експортнато няма никакво рапване. Вътре в ръст човек може да си я рапне както му харесва. Самия xlib е тънка библиотека, която комуникира с X сървъра. Практически всички приложения ползват нея или XCB, никой не говори с X директно.
За бекенда за чертаене смятах да ползвам vulkan (защото не харесвам OpenGL а Direct3D е Windows само). Една библиотека която видях е ash тя е тънък рапър, не е директен байндинг. Има някой ънсейф неща но като цяло са спазвани Ръст конвенциите и апито е попроменено. Например в стандартното C vulkan API, фунцкиите връщат код за грешка а резултата от тях го връщат в някакъв аргумент подаден като пойнтър. Също така много функции поемат като аргумент хендъли към разни неща отговарящи за някакъв контекст в апито. В ash съответно се възползват от методи и от Result, което редуцира броя на аргументите, които се подават на някой функции.
Също така се ползват, конвенциите на именоване на ръст, т.е vkGetPhysicalDeviceQueueFamilyProperties се превръща в метод get_physical_device_queue_family_properties в ash.
Това което не ми харесва обаче е че тази библиотека има много външни зависимости...
Като цяло един проблем (от гледна точка на направата на проект за кратко време) с vulkan е, че не е много абстрактна. Например за създаване на тривиална "hello triangle" чрез vulkan в C++, трябват 1k+ реда код. Отделно за нетривиална програма, човек сам трябва да си имплементира алокатор за паметта на GPU-то, защото броя на алокациите през vulkan са силно лимитирани от драйвера ( нещо от сорта на 1k алокации макс дори на висок клас карти). Това, което човек прави е че обикновенно заделя големи парчета памет през апито и в неговата програма си ги разпределя за съответните буфери, които създава в графичната памет. Общо взето е много занимавка.
През ваканцията пробвах да направя някакви неща в тази насока, но бързо разбрах, че началната ми идея няма как да се реализира, взимайки в предвид други проекти, които трябва да правя през семестъра. За това се надявам да одобрите горния проект, който съм предложил и изглежда по реалистичен.
* Реално това, което формално се специфицира като truetype, opentype е различно от това, което хората имат в предвид под тези термини или това, което се съдържа в .otf .ttf файловете. Всъщност това, което хората най-често имат в предвид под ttf е true-type contained font. Това са различни видове шрифтове с приликата, че контейнера им спазва оригиналната ttf спецификация. Контурите вътре може да са най-различни ttf outlines, cff outlines, postscript outlines etc... (самите контури са математически различни и са пакетирани по заличен начин)... В .otf файловете обикновенно се слагат шрифтове с cff outlines (не винаги по някога са си стандартни ttf), а в .ttf най-често има ttf outlines, но може да има и всичко друго. В крайна сметка моята библиотека за сега работи с ttf outlines само. Tова всъщност покрива може би най-голяма част от често използваните шрифтове за това избрах да поддържам него вместо другите на първо време.
