Pull to refresh

CPU vs GPU. Distance field

Reading time 5 min
Views 22K
Привет всем. Я уже однажды писал про Distance Field и приводил реализацию «эвристическим» кодом, дающую неплохую скорость: «Честный glow и скорость».

Зачем он нужен?


DField можно применять:
  • Для значительного повышения качества шрифтов
  • Для эффектов например горения контура. Один из эффектов я приводил в своей предыдущей статье
  • Для эффекта «metaballs» но в 2д и для любых сложных шейпов. (возможно я когда-нибудь приведу пример реализации этого эффекта)
  • А в данный момент DField мне нужен для качественного сглаживания углов и удаления мелких деталей.

И если в первых двух случаях мы можем заранее вычислить DField, то для других эффектов нам нужно просчитывать его в реальном времени.
В статье будет рассмотрен наиболее популярный, я бы сказал классический Chamfer distance (CDA) с кучей картинок, объясняющих принцип его работы, а так же рассмотрен двухпроходный алгоритм на GPU.
Оба алгоритма реализованы в демонстрационных программах на FPC.

Chamfer классика на CPU


Сегодня я хотел бы обратить внимание на классический способ рассчета DField. Поиграться можно тут (исходный код в git-е). У алгоритма есть неустоявшееся название: chamfer distance algoritm. Этот способ уже описывал RPG в своем топике. Однако там нет объяснений почему и как работает этот код. Почему возникают погрешности, какие они, и как их уменьшить.
upd. У RPG модификация CDA алгоритма, которая успешно борется с погрешностями.

Под капотом у 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, если алгоритмы это позволяют.

Ссылки по теме


  1. sourceforge.net/projects/dfsamples — Собственно примеры к статье. Бинарники и исходники.
  2. www.springer.com/cda/content/document/cda_downloaddocument/9780387312019-c1.pdf — отличный разбор как Chamfer алгоритма, так и его модификаций. Сравнение погрешности и времени выполнения.
  3. www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf — Применение DField в рендере шрифтов. Пожалуй самая известная статья.
  4. habrahabr.ru/post/215905 — вышеупомянутая статья от RPG. Хорошо показывает применение DField.
Tags:
Hubs:
+35
Comments 24
Comments Comments 24

Articles