Честный 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
    Метки:
    Поделиться публикацией
    Похожие публикации
    Комментарии 25
    • 0
      Всегда думал что «фотошоповское» свечение — лишь гауссовское размытие с выбранным наложением без сохранения информации о цвете.
      • +2
        Там есть 2 режима. Один гаусом, называется soft (мягкий), а второй — точный
        • +1
          Решил проверить.

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

            правая нижняя Н — по гауссу.
            Результаты могут немного отличаться, потому что гауссовское размытие смазало белые пиксели с красными. В случае если мы будем смазывать только красные пикели — такого не будет (может даже нормализация не будет нужна). Так что я думаю мягкий свет — это все таки гауссовское размытие + нормализация.
            • 0
              Есть предположение, что и в мягком используется размытие, только с другим режимом наложения, скорее всего по формуле soft light. Уж больно сильные различия между режимами.
              • 0
                Подскажите, что за программа изображена на скриншоте?
                • 0
                  Это узловой редактор в Blender3D. Но он работает не только с 3D-сценами, но и с обычными изображениями и видео. Кстати, вот пример чуть более сложного свечения через блюр.
      • +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
                        То что вы привели в пример — блюр, а не глоу. Я в статье упоминал об этом

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