Привет всем. Я уже однажды писал про Distance Field, и приводил реализацию «эвристическим» кодом дающую неплохую скорость: habrahabr.ru/post/186482/
Зачем он нужен?
DField можно применять:
- Для значительного повышения качества шрифтов
- Для эффектов например горения контура. Один из эффектов я приводил в своей предыдущей статье
- Для эффекта «metaballs» но в 2д и для любых сложных шейпов. (возможно я когда-нибудь приведу пример реализации этого эффекта)
- А в данный момент DField мне нужен для качественного сглаживания углов и удаления мелких деталей.
И если в первых двух случаях мы можем заранее вычислить DField, то для других эффектов нам нужно просчитывать его в реальном времени.
В статье будет рассмотрен наиболее популярный, я бы сказал классический Chamfer distance (CDA) с кучей картинок, объясняющих принцип его работы, а так же рассмотрен двухпроходный алгоритм на GPU.
Оба алгоритма реализованы в демонстрационных программах на FPC.
Chamfer классика на CPU
Сегодня я хотел бы обратить внимание на классический способ рассчета DField. Поиграться можно тут (исходный код в git-е). У алгоритма есть неустоявшееся название: chamfer distance algoritm. Этот способ уже описывал RPG в своем топике
Однако там нет объяснений почему и как работает этот код. Почему возникают погрешности, какие они, и как их уменьшить.
Под капотом у Chamfer.
Итак, у нас есть монохромное изображение, от которого мы хотим построить Distance Field. Это белая точка на черном фоне:
Начнем строить DField. Для этого сначала заполним наше будущее изображение +бесконечностью для пустот, и нулями для объекта. Как-то так:
Затем начинаем бежать по изображению (слева направо и сверху вниз), и для каждого пикселя проверять его соседей. Возьмем в соседнем пикселе значение, прибавим к этому значение расстояние до соседа. Для пикселей справа и слева это расстояние = 1. Для пикселей по диагонали sqrt(1*1+1*1)=sqrt(2). Запишем в наш пиксель минимальное значение между текущим, и только что вычисленным у соседа. После того как сделаем это для всех соседей — переходим к следующему пикселю. У нас вышла такая картина:
Поскольку мы бежали слева направо и сверху вниз — расстояния накапливались от предыдущих расчетов, и пиксели отмеченные красными стрелками автоматически посчитались «верно». Теперь если мы пробежим в обратном направлении (справа налево, снизу вверх) — то заполнится недостающая часть карты.
Итак, основная идея — использовать уже просчитанное раннее расстояние. Для этого нам не нужно проверять всех соседей. Достаточно проверить пиксели, по которым мы уже пробежали:
Красным — отмечены пиксели соседей для первого прохода (направо, вниз). Синим — для второго (налево, вверх).
Первый проход даст нам красивый шлейф в одну сторону:
Второй даст в другую, а поскольку мы будем записывать только минимальное значение в обоих случаях — то в сумме оно будет выглядеть вот так:
Сложность алгоритма O(2*W*H*5)
Теперь поговорим о точности. На текущем изображении не видно проблем, но если вы попробуете построить контур (как в этой статье) — то результат будет не самым правдоподобным. Посмотрим на distance%16 контур:
Красными стрелками я отметил ярко выраженную октогональность изображения. Почему же так происходит? А все просто, ведь наш результат накапливается, и накапливается он неправильно:
Наше расстояние будет вычислено по красной линии: 1+sqrt(2), в то время как правильно его будет вычислить по синей линии: sqrt(2*2+1*1)=sqrt(3). Если мы будем в расчетах брать не только соседей, но и соседей соседей:
результат конечно будет лучше. Но вычислительные сложности возрастают с O(2*W*H*5) до O(2*W*H*13). Но есть и хорошие новости, мы можем выбросить часть соседей, никак не повлияв на результат:
Дело в том, что выброшенные соседи имеют кратное расстояние и лежат на одном луче. А значит мы их можем выбросить, ибо значение от ближайших будет корректно накапливаться. Матрицу соседей я буду называть ядром. В первом случае у нас было ядро 3х3. Сейчас ядро 5х5. Давайте посмотрим на результат:
Наша октогональность стала заметно «круглее». (К слову, в фотошопе для слоев есть эффект Outer glow с параметром precise. У меня результат в точности совпал после прохода ядром 5х5. Похоже они используют именно этот алгоритм для данного эффекта.)
Сложность для оптимизированного 5x5 = O(2*W*H*9)
Можно дальше продолжать повышать и повышать размер ядра, качество будет расти, но один неприятный эффект мы так и не сможем побороть. Вот изображение для ядра 13*13:
На изображении присутствуют ступенчатые градиенты. Они все так же связаны с пресловутой погрешностью, и чтобы окончательно избавиться от них нам пришлось бы создать ядро размером в две ширины изображения, т.к. диагональ со сторонами (Много;1) может покрыть только ядро размером 2*Много+1. (с этими погрешностями борятся различные модификации CDA, один из вариантов — хранить в пикселе вектор до ближайшего, но я в статье их затрагивать не буду).
Итак суммарно, плюсы алгоритма:
- Неограниченный Distance Field (что это такое мы поймем когда разберемся с алгоритмом на GPU).
- Линейная сложность, и высокая скорость для маленьких ядер.
- Простота реализации.
Минусы:
- Плохая точность (особенно для маленьких ядер)
- Зависимость от предыдущих вычислений (никаких вам SIMD)
GPU в бой.
К сожалению, я не нашел никаких популярных алгоритмов, ложащихся на многопоточную архитектуру GPU. То ли руки у меня не те, то ли гугл зажал. Поэтому я поделюсь с вами своим «велосипедом». Благо он простой. Поиграться можно здесь, исходники лежат в git. Для игры потребуется видеокарточка, поддерживающая OpenGL3 и Rect текстуры.
Итак, допустим нам важно рассчитать Distance Field в радиусе 40 пикселей. Первым проходом мы считаем только вертикальную дистанцию от 40 соседей сверху и от 40 соседей снизу для каждого пикселя. Записываем минимальное значение (если заполненых соседей нет — записываем максимальное значение, 40). Получаем вот такую картину:
После этого делаем второй проход по горизонтали. Точно так же 40 соседей слева, 40 соседей справа. Зная расстояния до соседа, + расстояние по вертикали у соседа — мы легко считаем гипотенузу:
в результат записываем минимальную гипотенузу. После второго прохода нас ждет красивая и правильно построенная картинка:
Сложность алгоритма O(2*W*H*(2*D+1)), где W и H — размеры изображения, а D — расстояние distance field. Distance field у нас получается нормализованным (в изображении не будет значений больше D).
Точность вычислений отличная, т.к. погрешности не накапливаются:
В приложении к статье есть три режима: GL_R8, GL_R16, GL_R32F
Если включить GL_R8 и покрутить дистацию, то можно заметить скачущие погрешности. Дело тут вот в чем. Для промежуточного вертикального DField-а текстура для хранения имеет размер 8бит на пиксель. Поскольку я нормализую дистанцию на диапазон [0;1], то возникают погрешности. Нужно либо хранить не нормализованную дистанцию (но тогда для восьмибитной текстуры она будет ограничена 255 пикселями), либо повышать разрядность текстуры. Для текстуры R16-эти погрешности меньше, а для R32F эти погрешности вообще «отстуствуют», т.к. это float текстура. Учитывайте это, если захотите реализовать подобный distance field.
Итак, плюсы:
- Абсолютная точность
- Отлично ложится на SIMD.
- Простота реализации
- Данные сразу лежат на GPU!
Минусы
- Ограниченная дистанция. Мы должны знать, какая дистанция нам нужна заранее.
- Сложность алгоритма зависит от дистанции
- Данные на GPU (это может потребовать дополнительно время на получение, если мы планируем дальше работать с этими данными на CPU)
Выводы?
У меня в домашнем компьютере стоит GF450. Для изображения Hello world и DField = 500 пикселей мой GPU умудряется делать 20 кадров в секунду, что примерно равно 50мс на кадр. Все это с отличным качеством и простым прозрачным кодом. На CPU ядром 3х3 Distance field рассчитывается около 100мс. 5х5 около 200мс. Даже если ускорить, оптимизируя под CPU в 4 раза (что очень круто), то я получу качество заметно хуже за то же время. Используйте GPU, если алгоритмы это позволяют ;)
Ссылки по теме:
- sourceforge.net/projects/dfsamples/ — Собственно примеры к статье. Бинарники и исходники.
- www.springer.com/cda/content/document/cda_downloaddocument/9780387312019-c1.pdf — отличный разбор как Chamfer алгоритма, так и его модификаций. Сравнение погрешности и времени выполнения.
- www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf — Применение DField в рендере шрифтов. Пожалуй самая известная статья.
- habrahabr.ru/post/215905/ — вышеупомянутая статья от RPG. Хорошо показывает применение DField.
Автор: MrShoor
