Board.KolibriOS.org

Foldl, в векторных шрифтах хранятся контуры букв в виде координат линий и кривых Безье. Я пробовал сначала растрировать контур, а затем в растре его и заливать, но этот способ дает отвратительные результаты (независимо от алгоритмов заливки).
Так что да, имеются кривые Безье и отрезки, более того, они образуют замкнутые фигуры, и точка замыкания контура известна (т.е. точка, которая является первой и одновременно последней в контуре). Действительно, самая большая проблема - это определить, лежит ли данная точка внутри контура или нет. Все остальное уже готово и работает - не могу лишь придумать, как быстро определять, какая точка внутри контура, а какая - нет.
Создатели cairo советуют читать книги по вычислительной геометрии, в частности, про алгоритм Бентли-Оттмана.

Spoiler:

По сути, этот алгоритм позволяет определить с наименьшими затратами, какие из прямых пересекают текущую строку (sweeping line) и в каких координатах.

В общем, я мало что пока что понимаю, и потому надеюсь, что много голов лучше, чем одна.

Похоже, тем не менее, что наилучший способ - это тот, что используется во FreeType, и главное - правильно определить, на сколько линий разбивать кривую Безье.

Хорошо. В таком случае мне кажется нужно отталкиваться от алгоритма определения того, лежит ли точка внутри многоугольника (невыпуклого). Только здесь ребром может быть не только отрезок, но и кривая Безье.

Метод трассировки луча в исходном варианте требует процедуры определения пересечения луча и отрезка, возможно он подойдет, если уметь определять пересечение луча и кривой.

Точки пересечения луча и кривой находить не нужно, но в отличие от отрезков придется определять не только пересекает/не пересекает, но и сколько раз (сколько решений имеет система). А дальше, если не ошибаюсь, четность/нечетность и все готово.

Не понял, почему не нужно определять координаты пересечений?

Потому что эти координаты нам не нужны. Необходимо только узнать "пересекает или не пересекает".
Пускаем из точки луч в любую сторону, если число пресечений луча с границей контура нечетное, то точка лежит внутри контура. Эту операцию придется повторить для всех точек, но ведь картинка достаточно маленькая, кроме того, количество ребер не должно быть большим. Дополнительной памяти не требуется.

Понятно!
Хотел сначала возразить, что расчет для каждой точки займет много времени, но сейчас читаю лекции MIT OCW по компьютерной графике, и там черным по белому написано, что "brute force" перебор точек часто работает гораздо быстрее, чем метод scanlines, и в современных графических приложениях используется именно он.

Foldl, спасибо огромное за наведение на нужные мысли! Сейчас почти готова программа для заливки произвольных векторных многоугольников с масштабированием, работает прилично быстро. Я пробовал растрировать с ее помощью несколько глифов из шрифтов, смотрятся приемлемо даже при размерах в 8-14 пикселов, на мой взгляд, не хуже, чем у FreeType с выключенным хинтингом и drop-out контролем. Осталось придумать алгоритм для заливки глифов с отверстиями, и доработать напильничком. После этого я займусь библиотекой для векторных масштабируемых шрифтов. Скорее всего - переведенных в двоичные данные SVG, потому что легче всего. А вообще если разобраться с xml-парсером на fasm (или написать простой свой), то можно будет одним выстрелом сделать и просмотр SVG, и растеризатор SVG-шрифтов.

Тудум! Предлагаю любопытствующим посмотреть на качество растеризатора шрифтов, над которым я работаю.
Пока что поддерживается растеризация без сглаживания (на выходе - массив бит), и растеризация с 4х-полутоновым сглаживанием (на выходе - массив байт 00, 40, 80, FF). В планах - поддержка субпиксельного сглаживания. В мечтах - хинтинг и контроль отсечки (уж очень хитрыми кажутся эти технологии).

Растеризация без сглаживания: DejaVu Sans Mono, высота символов 60px, 30px, 24px, 20px, 12px

Растеризация со сглаживанием: DejaVu Sans Mono, высота символа 12px

Реализация шрифтов через freetype не нравится мне по следующим причинам: библиотека портированная, занимает прилично много места (особенно если считать шрифты), не очень легко линкуется.

Я планирую написать библиотеку на ассемблере для работы с векторными шрифтами, и она будет в COFF - формате, с которым большая часть разработчиков для Колибри умеет работать без проблем. Сейчас кроме растеризатора глифов ничего нет, а нужно еще очень многое. Впереди много работы. Однако, растеризатор - это самая важная и сложная часть библиотеки.

: Запланированные функции библиотеки:
СоздатьШрифт(указатель_на_имя_шрифта_в_памяти,указатель_на_имя_файла,размер_шрифта)
СоздатьСглаженныйШрифт(указатель_на_имя_шрифта_в_памяти,указатель_на_имя_файла,размер_шрифта)
ПосчитатьДлину(указатель_на_имя_шрифта_в_памяти,строка)
ОтобразитьСтроку(указатель_на_имя_шрифта_в_памяти,строка,указатель_на_область_памяти_для_изображения)
Предложения принимаются в ЛС.

Прошу прощения за многопостье
Реализовываю субпиксельное сглаживание (у мелкомягких зовется ClearType). Неидеальный (но работающий) пример моего растеризатора: Слева - глиф без хинтинга, контроля отсечки и сглаживания, справа - без хинтинга и контроля отсечки, с примитивным субпиксельным сглаживанием.
UPD: Улучшенная версия Внимание, эффект наблюдается только на LCD-мониторах с последовательностью субпикселов RGB, и только в родном разрешении матрицы!

Полезная работа. Желаю всяческих успехов!

Спасибо!

Сейчас выяснилось, что в qemu производительность значительно ниже, чем в virtualbox. Это вообще нормально?

Sorcerer wrote:Сейчас выяснилось, что в qemu производительность значительно ниже, чем в virtualbox. Это вообще нормально?

А почему это может быть не нормально? Если мне память не изменяет то VirtualBox эмулирует процессор с большей тактовой частотой чем Qemu, а вот звук в Qemu работает нормально в то время как в VirtualBox заикается (это я про Intel AC97 c KolibriOS).

зависит от настроек и от версии.

Оптимизирую растеризатор. Пытался определить, на какое количество отрезков нужно разбивать кривую Безье в зависимости от высоты символа.
И был сильно удивлен: при высоте глифа менее 24 пикселов кривые Безье вообще не нужны, их достаточно преобразовать в два отрезка. Для больших размеров тоже можно обойтись небольшим колчеством отрезков.

Пример:
Слева - буква Q из шрифта Droid Sans высотой 48 пикселов, растеризованная в Колибри моим растеризатором (с преобразованием кривых Безье в два отрезка), без автохинтинга и контроля отсечки, с субпиксельным сглаживанием.
По центру - буква Q из шрифта Droid Sans высотой 48 пикселов, растеризованная с помощью libpango, со включенным автохинтингом, автоинструктированием и максимальным сглаживанием.
Справа - все та же буква Q, растеризованная с помощью freetype2 с контролем отсечки, без хинтинга и сглаживания. Приемлемое качество (учитывая, что хинтинга и контроля отсечки в ближайшее время не будет)?

Такой прием значительно повышает скорость растеризации (количество элментов глифа сокращается в несколько раз).
Библиотека сейчас занимает около 5 килобайт (правда, в ней еще нет кучи нужных функций, и текст с ее помощью пока что не вывести). Шрифт Droid Sans без сжатия и русских букв в SVG занимает 32 килобайта, в SVGZ около 9 килобайт. В двоичном формате должен занимать побольше SVGZ, но поменьше SVG. Русские буквы - это примерно треть всех символов, так что размер одного файла шрифта с цифрами, знаками, русскими и английскими буквами будет примерно 16-20 килобайт.

Что значительно легче FreeType.

Конечно приемлемое, наконец-то у нас будут хорошие шрифты.

Отличная работа! Качество приемлемое. Да и модифицировать по необходимости готовую библиотеку всегда проще, чем писать ее с нуля.

На 48 пикселов, конечно выглядет хорошо. А вот на 12 - то что вверх - не очень хорошо выглядеть, даже сглаженные символы. Сглаживание должно маскировать пиксельных ступенек, а не дефектов растеризации. Например на несглаженные символы (вверх) видны странные пиксельные выступы, которые то появляются, то изчезают в зависимость от высоты.
Я например, всегда выключаю сглаживание, потому что глаза устают. Так что и без сглаживание, символ должен быть вполне читаем и разборчив.