CPU vs GPU. Distance field
Привет всем. Я уже однажды писал про 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. Похоже они используют именно этот алгоритм для данного эффекта.)Сложность для оптимизированного 5×5 = 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.
