54,1
рейтинг
12 июля 2013 в 17:50

Разработка → Честный glow и скорость

Наверное все, кто хоть чуть-чуть работал с фотошопом — видели эффект outer glow для слоя, и пробовали с ним играться. В фотошопе есть 2 техники этого самого outer glow. Soft и precise. Soft мне был не так интересен, а вот глядя на precise — я задумался.

Выглядит он вот так:

Это однопиксельная линия. А градиент грубо говоря — отражает расстояние до ближайшего пикселя изображения. Это самое расстояние — могло бы быть очень вкусным для построения разнообразных эффектов. Это и всякие контуры, и собственные градиенты, и
даже газоразрядные эффекты вокруг и прочее.
Пример эффекта, который можно получить, если иметь в наличии карту расстояний. Пример использует OpenGL + GLSL, написан на Delphi

Основная проблема такого glow — это сложность вычисления для больших размеров. Если у нас glow на 100 пикселей, то нам надо для каждого пикселя изображения проверить 100*100 соседних пикселей. И для изображения например 800*600 это будет всего 4 800 000 000 проверок.

Однако фотошоп этим не страдает, и прекрасно строит точный glow даже больших (до 250) размеров. Значит решение есть. И мне любопытно было его найти. Нагуглить быстрый алгоритм такого glow у меня не получилось. Большинство алгоритмов использует blur чтобы построить glow, но мы то с вами знаем, что однопиксельная линия не даст нам такого эффекта, как на картинке, она просто сблюрится.

Поэтому я погнал велосипедить.

Что делаем
Давайте прежде чем приступим — определимся с терминами.
Мы будем строить 100 пиксельный glow для png изображения. Вот этого:

оригинал изображения будет в архиве. Так же я для того чтобы выложить его картинкой в топик — залил фон черным. В оригинале — это белое изображение на прозрачном фоне
Я буду называть все пиксели существующими и не существующими. Существующий пиксель — это альфа которого больше 0, и фактически он учавствует и построении glow.

Этап 1
В действительности нет нужды для каждого пикселя искать ближайший существующий пиксель в радиусе 100 пикселей. Каждый существующий пиксель просто отбрасывает на соседние грубо говоря вот такой glow:

На данном glow цвет означает расстояние до пикселя. Таким образом все сводится к «рисованию» glow изображения для каждого существующего пикселя. А чтобы точка результирующего эффекта была ближайшей — мы «рисуем» только минимальное значение.
Отбросив несуществующие пиксели мы в разы сократили время рисования glow, но оно по прежнему огромное. Что же делать дальше?

Этап 2
Если мы внимательно посмотрим то можем заметить, что если точка с 4 сторон окружена существующими пикселями:

то она вообще не будет отбрасывать уникальных пикселей. Все, что мы нарисуем, обрабатывая красную точку, будет перетерто в каждой из пронумерованных зон соседним пикселем. Таким образом, проанализировав соседние точки — мы можем отбросить много существующих точек. Результатом такого анализа является вот это изображение:

Белое — существующие точки, которые были отброшены. Серое — точки которые будут давать реальный glow. Черное — несуществующие точки.
Фактически у нас остался только контур, от которого мы и строим glow.

Итак, наш алгоритм стал на порядки быстрее, но он по прежнему медленный как черепаха, по сравнению с реализацией фотошопа. У меня глоу в 100 пикселей для картинки выше строился 2-3 секунды.

Этап 3
Предыдущие этапы были достаточно тривиальны. Работа алгоритма была значительно ускорена, но у нас по прежнему бешеный overdraw для пикселей на границе.
Давайте внимательно посмотрим на ситуацию, когда 3 пикселя, от которых нам надо отбросить glow идут рядом с друг другом:

В действительности из 3-х (красных) пикселей, ярко красный будет давать всего 1 акуальную линию, вся остальная информация будет перерисована при отрисовке glow для темно красных пикселей. Я не буду приводить геометрическое доказательство этого, для читателя я думаю это достаточно очевидно. Если же мы переместим 1 пиксель в сторону вот так:

то потеряем левый «луч». Останется 1 единственный пиксель, который может быть ближе к яркокрасному. Кроме того, у нас появляется целый новый участок, куда мы должны отбросить glow от ярко красного пикселя:

Сдвинем нижний пиксель в сторону и посмотрим что выйдет:

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

луч влево будет, если нет соседних пикселей с индексами 7, 0, 1
луч влево вверх — если нет соседних пикселей с индексами 0, 1, 2
луч вверх — если нет соседних пикселей 1, 2, 3
и т. д.
Кроме того, между лучами ведь тоже есть пиксели. Так вот, они будут только тогда, когда есть 2 соседних луча. Т.е. по уже упомянутому по рисунку:

У нас есть луч вправо вверх и луч вправо. Между ними надо будет рисовать glow пиксели.

Таким образом мы можем значительно снизить overdraw.

Реализация
Я реализовал данный алгоритм на делфи с использованием библиотеки Vampyre Imaging Library. Сначала я готовлю в памяти уже мелькавшее в статье
glow изображение

затем я подготавливаю
изображение граничащих пикселей
они серенькие, видно если увеличить

glow изображение я бью логически на 16 зон.

Функция в коде DrawGlowPart умеет рисовать только строго определенную зону по её индексу. Пришлось повозиться с циклами для каждой зоны. Кроме того функция DrawGlowPart умеет рисовать зону с индексом 16. Это 1 пиксель вокруг любого существующего пикселя, который отрисовываем. На это рисунке видно, что этот пиксель слева от ярко красного:


Результат возни вот такая зловещая картинка:

И всего за ~150 мс на моей машине. Вот это уже по человечески.
Данный алгоритм хорошо ложится на GPU, что я и попытаюсь когда-нибудь на досуге сделать, чтобы получить еще больший прирост и возможность действительно в реалтайме строить такие glow. Увы 150мс это пока ниразу не реалтайм время, но это уже приемлимое для load time.

В фотошопе
В фотошопе глоу реализован явно не по моему алгоритму, и не удивлюсь если я в своем коде знатно свелосипедил. Если присмотреться в glow от одного пикселя в фотошопе, то на достаточно хорошем мониторе видна его «полигональность»:

Подозреваю что разработчики строят по граничным пикселям контур, далее его сдвигают, и получают полигон. Так же подозреваю что это еще сильнее сократит овердрав. Если у кого есть материалы на эту тему — буду рад почитать.

Ссылки к статье
1. Реализация алгоритма. Бинарный файл + исходные коды. Для компиляции потребуется библиотека Vampyre Imaging Library. 1-ый параметр — входной файл. 2-ой — размер glow в пикселях.
2. Пример эффекта. Не генерирует в реальном времени glow, а использует заранее сгенерированный. Для рендера используется OpenGL + GLSL
Александр Бусаров @MrShoor
карма
129,5
рейтинг 54,1
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (25)

  • 0
    Всегда думал что «фотошоповское» свечение — лишь гауссовское размытие с выбранным наложением без сохранения информации о цвете.
    • +2
      Там есть 2 режима. Один гаусом, называется soft (мягкий), а второй — точный
      • +1
        Решил проверить.

        Причем банальный гаусс на фоне отличается от мягкого свечения, не могли бы вы вкратце описать и принцип «мягкого?» Или это тот же самое, лишь с допущениями?
        • +4
          Поиграл с мягким. Похоже на то, что мягкий свет нужно делать в 2 раза больше чем гаус + потом размытие по гаусу нужно нормализовать уровнями. Во всяком случае у меня получилось очень похоже:

          правая нижняя Н — по гауссу.
          Результаты могут немного отличаться, потому что гауссовское размытие смазало белые пиксели с красными. В случае если мы будем смазывать только красные пикели — такого не будет (может даже нормализация не будет нужна). Так что я думаю мягкий свет — это все таки гауссовское размытие + нормализация.
        • 0
          Есть предположение, что и в мягком используется размытие, только с другим режимом наложения, скорее всего по формуле soft light. Уж больно сильные различия между режимами.
          • 0
            Подскажите, что за программа изображена на скриншоте?
            • 0
              Это узловой редактор в Blender3D. Но он работает не только с 3D-сценами, но и с обычными изображениями и видео. Кстати, вот пример чуть более сложного свечения через блюр.
              • 0
                Спасибо.
  • +3
    А тут не получится применить свёртку через быстрое преобразование фурье?
    • 0
      Буду рад если подскажите как. Я в матане слабоват, в плане применения его как инструмента программирования. Навсякий случай погуглил, но так и не понял как свертка мне поможет.
      • 0
        Проще всего взять фурье от исходной картинки, от размытой (каким угодно образом, хоть вручную, хоть по-вашему, или фотошопом), поделить одно на другое. Получим, не заморачиваясь, фильтр для любой другой картинки
    • 0
      Так же подумал, когда дочитал до микрооптимизаций и эвристик.
    • 0
      Это не операция свёртки, поэтому в частотном домене не получится сделать.
      • 0
        Вся разница только в min вместо sum. Неужели не найдётся какая-то алгебра подходящая?
  • +2
    Поглядите в сторону distance transform и приближенных вычислений. Там все можно очень быстро за один проход реализовать.
    • 0
      Поглядел, Quasi Euclidean похож на то, что я вижу в фотошопе. Пытаюсь понять как оно работает в один проход.
  • 0
    Я может глупость скажу, но может банальный обход в ширину спас бы отца русской демократии?

    Складываем все существующие точки в очередь, достаем по одной, закрашиваем еще не обработанных соседей и кладем их обратно в очередь (тоже только еще не тронутых ранее, конечно).

    Один проход по всем пикселям (ну два, если учесть начальный сбор существующих пикселей), быстрее некуда.
    • 0
      Неверное решение, из-за метрики. Как этот целочисленный алгоритм получит расстояние sqrt(5) для сдвига на 2 пикселя вправо и 1 вниз от границы изображения? А если мы пришли в ту же точку из другой точки границы за 3 хода влево — ходов столько же, а расстояние должно быть другое.

      Это значит, что если мы покрасили пиксель раньше, не факт, что он в евклидовой метрике ближе к изображению. Значит, при заходе на пиксель придётся сравнивать расстояния и иногда перекрашивать уже покрашенный (и добавлять в очередь), т.е. не один проход делать.
      • 0
        Тогда надо брать квадрат расстояния, и обходить по модифицированному алгоритму Дейкстры (т.н. «Дейкстра с хипом»).
        • 0
          UPD:
          Оценка времени — O(|E| log |V|), то есть O(hw (log h + log w)), где h и w — размеры изображения.

          Оценка времени алгоритма автора: O(hw + td (l + d)), где h и w — размеры изображения, d — дистанция glow, t — число изолированных контуров, l — средняя длина контура.

          Алгоритм автора эффективен, когда t << hw/d2, но проигрывает при t >> hw (log h + log w) / d2. Самый страшный случай — решетка из изолированных точек.
  • –6
    <зануда>Ужасный шрифт. Пожалуйста, не используйте его больше.</зануда>
    • +6
      Шрифт был выбран не из-за «красоты». Если бы я взял какой-нибудь arial, то у меня было бы много только вертикальных или только горизонтальных участков.
  • 0
    Преобразованные таким образом картинки используют для рисования типа-векторных картинок в игрушках.

    Вот статья:
    www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf
  • 0
    Если у нас glow на 100 пикселей, то нам надо для каждого пикселя изображения проверить 100*100 соседних пикселей.

    Если реализовать через разделяемый матричный фильтр, то достаточно двух проходов по массиву с общим чтением в 200 пикселей на каждый пиксель, а не 10000.
    www.songho.ca/dsp/convolution/convolution.html#separable_convolution
    • 0
      То что вы привели в пример — блюр, а не глоу. Я в статье упоминал об этом

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.