Алгоритмы заливки

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

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

    Точки пересечения луча и кривой находить не нужно, но в отличие от отрезков придется определять не только пересекает/не пересекает, но и сколько раз (сколько решений имеет система). А дальше, если не ошибаюсь, четность/нечетность и все готово.
  • Не понял, почему не нужно определять координаты пересечений?
  • Потому что эти координаты нам не нужны. Необходимо только узнать "пересекает или не пересекает".
    Пускаем из точки луч в любую сторону, если число пресечений луча с границей контура нечетное, то точка лежит внутри контура. Эту операцию придется повторить для всех точек, но ведь картинка достаточно маленькая, кроме того, количество ребер не должно быть большим. Дополнительной памяти не требуется.
  • Понятно!
    Хотел сначала возразить, что расчет для каждой точки займет много времени, но сейчас читаю лекции MIT OCW по компьютерной графике, и там черным по белому написано, что "brute force" перебор точек часто работает гораздо быстрее, чем метод scanlines, и в современных графических приложениях используется именно он.

    Foldl, спасибо огромное за наведение на нужные мысли! Сейчас почти готова программа для заливки произвольных векторных многоугольников с масштабированием, работает прилично быстро. Я пробовал растрировать с ее помощью несколько глифов из шрифтов, смотрятся приемлемо даже при размерах в 8-14 пикселов, на мой взгляд, не хуже, чем у FreeType с выключенным хинтингом и drop-out контролем. Осталось придумать алгоритм для заливки глифов с отверстиями, и доработать напильничком. После этого я займусь библиотекой для векторных масштабируемых шрифтов. Скорее всего - переведенных в двоичные данные SVG, потому что легче всего. А вообще если разобраться с xml-парсером на fasm (или написать простой свой), то можно будет одним выстрелом сделать и просмотр SVG, и растеризатор SVG-шрифтов.
    Last edited by SoUrcerer on Mon Apr 11, 2011 1:10 pm, edited 1 time in total.
  • Тудум! Предлагаю любопытствующим посмотреть на качество растеризатора шрифтов, над которым я работаю.
    Пока что поддерживается растеризация без сглаживания (на выходе - массив бит), и растеризация с 4х-полутоновым сглаживанием (на выходе - массив байт 00, 40, 80, FF). В планах - поддержка субпиксельного сглаживания. В мечтах - хинтинг и контроль отсечки (уж очень хитрыми кажутся эти технологии).

    Растеризация без сглаживания:
    raster.png
    raster.png (805 Bytes)
    Viewed 6352 times
    DejaVu Sans Mono, высота символов 60px, 30px, 24px, 20px, 12px

    Растеризация со сглаживанием:
    aa-raster.png
    aa-raster.png (347 Bytes)
    Viewed 6352 times
    DejaVu Sans Mono, высота символа 12px

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

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

    : Запланированные функции библиотеки:
    СоздатьШрифт(указатель_на_имя_шрифта_в_памяти,указатель_на_имя_файла,размер_шрифта)
    СоздатьСглаженныйШрифт(указатель_на_имя_шрифта_в_памяти,указатель_на_имя_файла,размер_шрифта)
    ПосчитатьДлину(указатель_на_имя_шрифта_в_памяти,строка)
    ОтобразитьСтроку(указатель_на_имя_шрифта_в_памяти,строка,указатель_на_область_памяти_для_изображения)
    Предложения принимаются в ЛС.
  • Прошу прощения за многопостье :)
    Реализовываю субпиксельное сглаживание (у мелкомягких зовется ClearType). Неидеальный (но работающий) пример моего растеризатора:
    subpixel.png
    subpixel.png (322 Bytes)
    Viewed 6344 times
    Слева - глиф без хинтинга, контроля отсечки и сглаживания, справа - без хинтинга и контроля отсечки, с примитивным субпиксельным сглаживанием.
    UPD: Улучшенная версия
    subpixel_plus.png
    subpixel_plus.png (406 Bytes)
    Viewed 6340 times
    Внимание, эффект наблюдается только на 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 с контролем отсечки, без хинтинга и сглаживания.
    render-nobezier.png
    render-nobezier.png (1.94 KiB)
    Viewed 6283 times
    Приемлемое качество (учитывая, что хинтинга и контроля отсечки в ближайшее время не будет)?

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

    Что значительно легче FreeType.
  • Конечно приемлемое, наконец-то у нас будут хорошие шрифты.
  • Отличная работа! Качество приемлемое. Да и модифицировать по необходимости готовую библиотеку всегда проще, чем писать ее с нуля.
  • На 48 пикселов, конечно выглядет хорошо. А вот на 12 - то что вверх - не очень хорошо выглядеть, даже сглаженные символы. Сглаживание должно маскировать пиксельных ступенек, а не дефектов растеризации. Например на несглаженные символы (вверх) видны странные пиксельные выступы, которые то появляются, то изчезают в зависимость от высоты.
    Я например, всегда выключаю сглаживание, потому что глаза устают. Так что и без сглаживание, символ должен быть вполне читаем и разборчив.
  • Who is online

    Users browsing this forum: No registered users and 10 guests