Наверное все, кто хоть чуть-чуть работал с фотошопом — видели эффект outer glow для слоя, и пробовали с ним играться. В фотошопе есть 2 техники этого самого outer glow. Soft и precise. Soft мне был не так интересен, а вот глядя на precise — я задумался.
Выглядит он вот так:
Это однопиксельная линия. А градиент грубо говоря — отражает расстояние до ближайшего пикселя изображения. Это самое расстояние — могло бы быть очень вкусным для построения разнообразных эффектов. Это и всякие контуры, и собственные градиенты, и
Основная проблема такого glow — это сложность вычисления для больших размеров. Если у нас glow на 100 пикселей, то нам надо для каждого пикселя изображения проверить 100*100 соседних пикселей. И для изображения например 800*600 это будет всего 4 800 000 000 проверок.
Однако фотошоп этим не страдает, и прекрасно строит точный glow даже больших (до 250) размеров. Значит решение есть. И мне любопытно было его найти. Нагуглить быстрый алгоритм такого glow у меня не получилось. Большинство алгоритмов использует blur чтобы построить glow, но мы то с вами знаем, что однопиксельная линия не даст нам такого эффекта, как на картинке, она просто сблюрится.
Поэтому я погнал велосипедить.
Мы будем строить 100 пиксельный glow для png изображения. Вот этого:
оригинал изображения будет в архиве. Так же я для того чтобы выложить его картинкой в топик — залил фон черным. В оригинале — это белое изображение на прозрачном фоне
Я буду называть все пиксели существующими и не существующими. Существующий пиксель — это альфа которого больше 0, и фактически он учавствует и построении glow.
На данном glow цвет означает расстояние до пикселя. Таким образом все сводится к «рисованию» glow изображения для каждого существующего пикселя. А чтобы точка результирующего эффекта была ближайшей — мы «рисуем» только минимальное значение.
Отбросив несуществующие пиксели мы в разы сократили время рисования glow, но оно по прежнему огромное. Что же делать дальше?
то она вообще не будет отбрасывать уникальных пикселей. Все, что мы нарисуем, обрабатывая красную точку, будет перетерто в каждой из пронумерованных зон соседним пикселем. Таким образом, проанализировав соседние точки — мы можем отбросить много существующих точек. Результатом такого анализа является вот это изображение:
Белое — существующие точки, которые были отброшены. Серое — точки которые будут давать реальный glow. Черное — несуществующие точки.
Фактически у нас остался только контур, от которого мы и строим glow.
Итак, наш алгоритм стал на порядки быстрее, но он по прежнему медленный как черепаха, по сравнению с реализацией фотошопа. У меня глоу в 100 пикселей для картинки выше строился 2-3 секунды.
Давайте внимательно посмотрим на ситуацию, когда 3 пикселя, от которых нам надо отбросить glow идут рядом с друг другом:
В действительности из 3-х (красных) пикселей, ярко красный будет давать всего 1 акуальную линию, вся остальная информация будет перерисована при отрисовке glow для темно красных пикселей. Я не буду приводить геометрическое доказательство этого, для читателя я думаю это достаточно очевидно. Если же мы переместим 1 пиксель в сторону вот так:
то потеряем левый «луч». Останется 1 единственный пиксель, который может быть ближе к яркокрасному. Кроме того, у нас появляется целый новый участок, куда мы должны отбросить glow от ярко красного пикселя:
Сдвинем нижний пиксель в сторону и посмотрим что выйдет:
У нас снова осталось 2 луча.
Покрутив различные ситуации, и внимательно подумав я пришел к выводу. Пиксель будет давать луч в сторону, если трех смежных пикселей нет. Пример для проиндесированных соседних пикселей:
луч влево будет, если нет соседних пикселей с индексами 7, 0, 1
луч влево вверх — если нет соседних пикселей с индексами 0, 1, 2
луч вверх — если нет соседних пикселей 1, 2, 3
и т. д.
Кроме того, между лучами ведь тоже есть пиксели. Так вот, они будут только тогда, когда есть 2 соседних луча. Т.е. по уже упомянутому по рисунку:
У нас есть луч вправо вверх и луч вправо. Между ними надо будет рисовать glow пиксели.
Таким образом мы можем значительно снизить overdraw.
затем я подготавливаю
glow изображение я бью логически на 16 зон.
Функция в коде DrawGlowPart умеет рисовать только строго определенную зону по её индексу. Пришлось повозиться с циклами для каждой зоны. Кроме того функция DrawGlowPart умеет рисовать зону с индексом 16. Это 1 пиксель вокруг любого существующего пикселя, который отрисовываем. На это рисунке видно, что этот пиксель слева от ярко красного:
Результат возни вот такая зловещая картинка:
И всего за ~150 мс на моей машине. Вот это уже по человечески.
Данный алгоритм хорошо ложится на GPU, что я и попытаюсь когда-нибудь на досуге сделать, чтобы получить еще больший прирост и возможность действительно в реалтайме строить такие glow. Увы 150мс это пока ниразу не реалтайм время, но это уже приемлимое для load time.
Подозреваю что разработчики строят по граничным пикселям контур, далее его сдвигают, и получают полигон. Так же подозреваю что это еще сильнее сократит овердрав. Если у кого есть материалы на эту тему — буду рад почитать.
2. Пример эффекта. Не генерирует в реальном времени glow, а использует заранее сгенерированный. Для рендера используется OpenGL + GLSL
Выглядит он вот так:
Это однопиксельная линия. А градиент грубо говоря — отражает расстояние до ближайшего пикселя изображения. Это самое расстояние — могло бы быть очень вкусным для построения разнообразных эффектов. Это и всякие контуры, и собственные градиенты, и
даже газоразрядные эффекты вокруг и прочее.
Пример эффекта, который можно получить, если иметь в наличии карту расстояний. Пример использует 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