Comments 24
А как оба алгоритма учитывают полупрозрачные пиксели? На первый взгляд кажется, что не существует общего вида distance field для полупрозрачного изображения. И результат будет зависеть от некоторого коэффициента затухания.
Т.е. когда изображение монохромное, расстояние измеряется от 0 до +∞ в любой шкале — всю карту можно делить и умножать на любой коэффициент. Как только появляются полутона, нужно понимать — «расстояние в один пиксель это потеря интенсивности на сколько?» Меняем коэффициент — нелинейно меняется вся карта. Я прав?
Т.е. когда изображение монохромное, расстояние измеряется от 0 до +∞ в любой шкале — всю карту можно делить и умножать на любой коэффициент. Как только появляются полутона, нужно понимать — «расстояние в один пиксель это потеря интенсивности на сколько?» Меняем коэффициент — нелинейно меняется вся карта. Я прав?
Не учитывают никак. Однако если у нас изображение с антиалиасингом, мы можем вычислять по прозрачности пикселя приблизительную дистанцию, и изначально заполнять карту не только 0 и +∞. Для второго алгоритма — аналогично прибавлять эту самую небольшую дистанцию.
В целом же для полупрозрачного изображения построить карту расстояний нельзя. DFiled — кратчайшее расстояние до контура, а без выявления контура оно бессмысленно.
В целом же для полупрозрачного изображения построить карту расстояний нельзя. DFiled — кратчайшее расстояние до контура, а без выявления контура оно бессмысленно.
Столкнулся с этой же проблемой, когда добавлял поддержку DF для рендеринга шрифтов (глифы кэшируются в текстуру в рантайме с помощью freetype2). Чаще всего используют посчитанную заранее текстуру, при этом можно брать глиф изначально увеличенный раз в 16, считать distance field, потом уменьшать — сглаживаются все артефакты.
Но мне хотелось генерить глифы в рантайме, да еще и на мобильных устройствах, а вариант с суперсэмплингом для этого слишком медленный. Если не использовать суперсэмплинг, то даже улучшенный CDA в результате выглядит ступеньками (алгоритм dead reckoning, при окне 3х3 дает почти идеальный результат — статья).
Поскольку freetype рендерит глифы с антиалиасингом, глупо выкидывать эту информацию из обработки. Сейчас использую алгоритм с поддержкой АА — edtaa3. Результат вполне годный, буковку первоначально отрендеренную размером в 48px можно увеличивать раз в 10 без особых потерь.
Хотя более правильно глиф сразу рендерить в distance field, но freetype так не умеет. Как-нибудь бы вытащить векторные контура и из них уже генерировать sdf, есть у кого опыт?
Но мне хотелось генерить глифы в рантайме, да еще и на мобильных устройствах, а вариант с суперсэмплингом для этого слишком медленный. Если не использовать суперсэмплинг, то даже улучшенный CDA в результате выглядит ступеньками (алгоритм dead reckoning, при окне 3х3 дает почти идеальный результат — статья).
Поскольку freetype рендерит глифы с антиалиасингом, глупо выкидывать эту информацию из обработки. Сейчас использую алгоритм с поддержкой АА — edtaa3. Результат вполне годный, буковку первоначально отрендеренную размером в 48px можно увеличивать раз в 10 без особых потерь.
Хотя более правильно глиф сразу рендерить в distance field, но freetype так не умеет. Как-нибудь бы вытащить векторные контура и из них уже генерировать sdf, есть у кого опыт?
Для контура distance field — это Straight skeleton
Строить такую штуку очень затратно, а в случае с кривыми безье второго порядка (которые как раз содержатся в глифах) — это еще затратнее. По растру проще, имхо.
Строить такую штуку очень затратно, а в случае с кривыми безье второго порядка (которые как раз содержатся в глифах) — это еще затратнее. По растру проще, имхо.
В растре уже потеряно очень много информации. С вектором можно использовать меньший размер глифа, поэтому по быстродействию все не так однозначно. Freetype сначала аппроксимирует кривые дугами и прямыми, а потом уже растеризует, по идее по ним же можно попробовать строить скелет.
В Qt5 вроде используется этот способ рендеринга шрифтов.
В Qt5 вроде используется этот способ рендеринга шрифтов.
Qt5 опенсорсный — надо просто посмотреть как там рендерится шрифт. Впрочем, даже если вы построите SDF по вектору напрямую, это не избавит вас от артефактов, свойственных для SDF, так как в конечном итоге всё равно придётся хранить растр. Можно увеличить битность карты (16 бит на канал), качество должно стать получше, хотя и за счёт потери совместимости.
AMD APU решит проблему общих данных
Хоть вы и ссылаетесь на мою реализацию, у меня не получается такая ярко выраженная «звезда»:
Принцип такой же (окно 3х3), но возможно алгоритм модифицированный. Ещё на картинки видны какие-то артефакты на удалении, но это похоже на ошибку в реализации.
Принцип такой же (окно 3х3), но возможно алгоритм модифицированный. Ещё на картинки видны какие-то артефакты на удалении, но это похоже на ошибку в реализации.
Интересно. Вроде принцип абсолютно такой же, однако «ступеньки» на градиентах остались, и в глаза бросаются некоторые артефакты (ну и у вас SDF, т.е. еще один проход). Посмотрю ваш код на досуге.
У меня алгоритм 8SSEDT, только что выяснил. Дело давно было, а ступеньки и прочее — ошибки реализации. Я когда искал хоть какой-то алгоритм, было днём с огнём не сыскать. Сейчас если чуть-чуть копнуть — оказывается существует десяток методов.
Вот оригинальная реализация: www.codersnotes.com/algorithms/signed-distance-fields (ступеньки прилагаются).
Потом я похоже что-то нахимичил когда переделывал, но у меня ощущение, что в оригинале тоже есть ошибки.
Вот оригинальная реализация: www.codersnotes.com/algorithms/signed-distance-fields (ступеньки прилагаются).
Потом я похоже что-то нахимичил когда переделывал, но у меня ощущение, что в оригинале тоже есть ошибки.
Для сравнения, картинка, которую я получил методом брутфорса. Прямолинейный простейший алгоритм. И тут тоже лесенка:
Так что это либо повод задуматься, либо я где-то ошибся… Но рискну предположить, что ваш метод на GPU ещё как-то учитывает антиалиасинг и сглаживает переходы в ущерб точности, но в пользу красоты результата.
Далее по производительности (Core 2 quad):
брутфорс — 462 сек
8SSEDT — 0.046 сек (46 мс)
Как видно, практически также быстро как GPU. У меня правда он ещё два прохода считает (знаковая карта расстояний), эти два прохода можно запустить на двух процессорах без особых проблем. SIMD там прикрутить тоже можно, но лениво.
Так что это либо повод задуматься, либо я где-то ошибся… Но рискну предположить, что ваш метод на GPU ещё как-то учитывает антиалиасинг и сглаживает переходы в ущерб точности, но в пользу красоты результата.
Далее по производительности (Core 2 quad):
брутфорс — 462 сек
8SSEDT — 0.046 сек (46 мс)
Как видно, практически также быстро как GPU. У меня правда он ещё два прохода считает (знаковая карта расстояний), эти два прохода можно запустить на двух процессорах без особых проблем. SIMD там прикрутить тоже можно, но лениво.
Данная лесенка — прямое следствие негладкости изначального контура. Если не мухлевать с сглаживанием и/или аппроксимацией, от нее никуда не деться. Для подтверждения достаточно в 4х увеличении рассмотреть приведённое изображение.
Да не должно быть там лесенки. lim(sqrt(N*N+1*1)-sqrt((N+1)*(N+1)+2*2)) = 0 при N -> +∞
RPG, а можно код брутфорса в студию?
RPG, а можно код брутфорса в студию?
Забрутфорсил, получил лесенку, начал копать и нашел откуда эта лесенка берется. Это из-за округления при построении градиента. У вас и у меня одна и та же ошибка. Мы делаем (trunc(distance)%16) * (255/16)
Вот собственно на trunc(distance) мы создаем эту лесенку. GPU же делает все по честному через frac. Так что градиент нужно считать как trunc(frac(distance/16)*255).
Тогда CDA для ядра 3x3 выглядит вот так:
лесенка все еще есть, но уже не такая резкая. Для ядра 13х13 она уже абсолютно не заметна глазу:
Ну и если забрутфорсить — то должны получить абсолютно такую же картинку, как на GPU.
p.s. А то я уж думал что я с ума сошел, ибо математически её там не должно быть :) Приду домой, запушу изменения в git, поправлю семпл и статью. Спасибо.
Вот собственно на trunc(distance) мы создаем эту лесенку. GPU же делает все по честному через frac. Так что градиент нужно считать как trunc(frac(distance/16)*255).
Тогда CDA для ядра 3x3 выглядит вот так:
лесенка все еще есть, но уже не такая резкая. Для ядра 13х13 она уже абсолютно не заметна глазу:
Ну и если забрутфорсить — то должны получить абсолютно такую же картинку, как на GPU.
p.s. А то я уж думал что я с ума сошел, ибо математически её там не должно быть :) Приду домой, запушу изменения в git, поправлю семпл и статью. Спасибо.
Ну отлично, а я свой алгоритм переделал — результат за 5 мс и никакой лесенки. Вот соотношение сигнал/шум в сравнении 8SED с брутом: 91.58 dB. Ошибки всего в паре пикселей. 90 децибелл это отличный результат, при сжатии изображений нормальным отклонением является где-то 50 dB.
Я вспомнил как я делал. Сначала нашёл алгоритм 8SSEDT, он в общем работал, но очень медленно. Затем нашёл статью, где предполагался более быстрый метод и реализовал его. Но математики тоже шутят и в статье оказались баги (на глаз не отличить, но благодаря вашему посту я заметил разницу). Переделаю обратно на улучшенный 8SED.
На очереди попробовать алгоритм с антиалиасингом.
Я вспомнил как я делал. Сначала нашёл алгоритм 8SSEDT, он в общем работал, но очень медленно. Затем нашёл статью, где предполагался более быстрый метод и реализовал его. Но математики тоже шутят и в статье оказались баги (на глаз не отличить, но благодаря вашему посту я заметил разницу). Переделаю обратно на улучшенный 8SED.
На очереди попробовать алгоритм с антиалиасингом.
А если предварительно составить список пикселей, являющихся границей? (т.е. пиксель черный, а рядом есть хотя бы один белый пиксель), а потом вычислять дистанции от каждого пикселя картинки до каждого пикселя границы, это ускорит брутфорс, я думаю (может кто-то до меня это придумал?)
может кто-то до меня это придумал?Да, придумал: https://habrahabr.ru/post/186482/
Но идея так себе. По крайней мере я эту «эвристику» сейчас нигде не использую.
Воспользовался вашим методом для вычисления SDF на GPU https://github.com/1vanK/Urho3DBitmapFontGenerator/blob/master/Bin/MyData/Shaders/GLSL/SdfCalculator.glsl
Спасибо большое!
Возможно, Вам следует обратить внимание на работу господина Арнольда Мейстера, который предложил алгоритм точного (если мне, конечно, память не изменяет) расчета подобных полей за линейное время. Причем там неважно, какое преобразование Вы хотите сделать — Евклидово, или какое поинтересней. Расчет выполняется, как и у Вас, в два прохода, причем выполняется построчно, что в целом предполагает прекрасный потенциал для распараллеливания.
Почитать можно вот тут.
Почитать можно вот тут.
Я не знаю, почему ни в одном источнике он не используется, но это прекрасно работает — я лично использовал этот метод для генерации атласов с SDF-шрифтами, и результат был отличный.
Это здорово, спасибо! Это фактически симбиоз тех алгоритмов, что описаны в этой статье. Он разбивает скан на вертикальный и горизонтальный как у меня для GPU, но при этом сами колонки и строки проходит один раз накапливая данные. Распараллеливается уже не так хорошо (по колонкам/строкам), но алгоритм очень годный. Я сейчас в большинстве случаев использую jump flooding, т.к. он оказался эффективнее, чем описанные в статье (хотел про него тоже статью написать, но руки пока не дошли). Он параллелится идеально, у него логарифмическое время, но у алгоритма Арнольда Мейстера есть все шансы обскакать его даже на GPU. Надо будет будет устроить битву этих алгоритмов.
Буду рад, если поделитесь результатами. :)
Совсем забыл, кстати докладываю. Алгоритм Мейстера я реализовал на CPU, и на CPU он показал лучшие результаты среди всех алгоритмов. Так что на CPU он мастхев. А вот на GPU эффективно положить этот алгоритм у меня пока не вышло (из-за особенности устройства GPU), и пока Jump Flooding опрежает его. Но у меня есть идея что можно еще попробовать, чтобы ускорить его. Может быть когда-нибудь я это попробую.
Sign up to leave a comment.
CPU vs GPU. Distance field