Наверное все, кто хоть чуть-чуть работал с фотошопом — видели эффект 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.
Этап 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 изображение я бью логически на 16 зон.
Функция в коде DrawGlowPart умеет рисовать только строго определенную зону по её индексу. Пришлось повозиться с циклами для каждой зоны. Кроме того функция DrawGlowPart умеет рисовать зону с индексом 16. Это 1 пиксель вокруг любого существующего пикселя, который отрисовываем. На это рисунке видно, что этот пиксель слева от ярко красного:
Результат возни вот такая зловещая картинка:
И всего за ~150 мс на моей машине. Вот это уже по человечески.
Данный алгоритм хорошо ложится на GPU, что я и попытаюсь когда-нибудь на досуге сделать, чтобы получить еще больший прирост и возможность действительно в реалтайме строить такие glow. Увы 150мс это пока ниразу не реалтайм время, но это уже приемлимое для load time.
В фотошопе
В фотошопе глоу реализован явно не по моему алгоритму, и не удивлюсь если я в своем коде знатно свелосипедил. Если присмотреться в glow от одного пикселя в фотошопе, то на достаточно хорошем мониторе видна его «полигональность»:
Подозреваю что разработчики строят по граничным пикселям контур, далее его сдвигают, и получают полигон. Так же подозреваю что это еще сильнее сократит овердрав. Если у кого есть материалы на эту тему — буду рад почитать.
Ссылки к статье
1. Реализация алгоритма. Бинарный файл + исходные коды. Для компиляции потребуется библиотека Vampyre Imaging Library. 1-ый параметр — входной файл. 2-ой — размер glow в пикселях.
2. Пример эффекта. Не генерирует в реальном времени glow, а использует заранее сгенерированный. Для рендера используется OpenGL + GLSL
Автор: MrShoor
