Пролог
Доброго времени суток! Однажды ко мне на работу пришёл друг, и я ему показал свой свеженаписанный шейдер, на тот момент это была первый серьёзный опыт с ними. Данная микропрограмма преобразовывала изображение с камеры в изображение вязаной кофты.
На момент начала разработки изображение бралось с камеры телефона и выводилось в вязанном виде, эффект был необычным. И друг подкинул идею сделать фильтр для камеры в виде квадратичного дерева.
В общем с этого момента я сел за изучения методов быстрого построения квадратичного дерева, и остановился на идеи HistoPyramid.
Реализация
Изначально нужно подготовить входные параметры для шейдера. Я использовал Unity3D, так что примеры кода на C#.
Процесс работы алгоритма разбит на два этапа:
- Построение дерева
- а. Подготовка параметров шейдера
б. Реализация шейдера - Создание изображения из дерева
Построение дерева
Подготовка параметров шейдера
Все расчёты будут вестись на условиях, что максимальный размер квадрата должен быть равен 256 пикселям.
int quadSize = 256;
Изначально приведу пример построенного дерева:
Количество уровней в дереве высчитывается следующим образом:
float levelsAmount = Mathf.Log(quadSize, 2f);
Каждый следующий уровень в два раза меньше предыдущего. Так как элементы дерева будут расположены справа, то размер изображения дерева будет высчитываться следующим:
Vector2 histoSize = new Vector2((float)quadSize + (float)quadSize / 2f, (float)quadSize);
В параметры шейдера потребуется передать координаты начала блока, координаты конца блока и размер блока. Так же потребуются такие же параметры для родительского блока, т.е. блока большего чем текущий.
float _cellSize = Mathf.Pow (2f, levelsLog - (float)currentLevel);
Vector2 size = new Vector2 (_cellSize / histoSize.x, _cellSize / histoSize.y);
Vector2 start = new Vector2 (0.6666666667f, size.y);
Vector2 end = new Vector2 (0.6666666667f + size.x, 2f *size.y);
builderMaterial [i].SetVector ("_startBlock", start);
builderMaterial [i].SetVector ("_endBlock", end);
builderMaterial [i].SetVector ("_sizeBlock", size);
Указанный кусок кода рассчитывает координаты начала, конца и размер блока, при условии что currentLevel больше 0, т.е. все элементы дерева, которые находится справа от исходного изображения. От этого в координатах начала и конца стоят «магические цифры» 0.6666666667f (2/3 занимает исходное изображение). _cellSize будет хранить размер блока в пикселях, после чего, для начала и конца потребуется перевести в относительные единицы.
if (i == 1) {
parentStart = Vector4.zero;
parentSize = new Vector4 (0.6666666667f, 1f, 0, 0);
}
else {
_cellSize = Mathf.Pow (2f, levelsLog - (float)currentLevel + 1f);
parentSize = new Vector4 (_cellSize / histoSize.x, _cellSize / histoSize.y, 0, 0);
parentStart = new Vector4 (0.6666666667f, parentSize.y, 0, 0);
}
В случае с родительским блоком всё идентично.
Реализация шейдера
Шейдер будет запускаться levelsAmount раз. Для каждого из уровня дерева будут передаваться параметры, соответсвующие текущему уровню.
Параметрами на вход шейдера следующие:
Properties
{
_MainTex ("Base (RGB)", 2D) = "white" {}
_BaseStep ("Pixel size parent block", Vector) = (0, 0, 0, 0)
_Level ("Current level", Float) = 1
_startBlock («Start current block", Vector) = (0, 0, 0, 0)
_endBlock («End current block", Vector) = (0, 0, 0, 0)
_sizeBlock ("Size current block", Vector) = (0, 0, 0, 0)
_parentEndBlock ("Start parent block", Vector) = (0, 0, 0, 0)
_parentSizeBlock ("Size parent block", Vector) = (0, 0, 0, 0)
}
- _MainTex — исходная текстура, в нашем случае размером 256х256 пикселей;
- _BaseStep — относительный размер пикселя (1/histoSize);
- _Level — текущий уровень дерева;
- _startBlock — начало текущего блока;
- _endBlock — конец текущего блока;
- _sizeBlock — размер текущего блока;
- _parentEndBlock — конец родительского блока;
- _parentSizeBlock — размер родительского блока;
Исходное изображение передающееся в _MainTex:
Задачей данного шейдера состоит в следующем:
- Определить, попадают ли координаты обработки изображения в текущий блок
- Найти среднее значение из 4х родительских пикселей и высчитать разницу цвета относительно родительский и нового цвета
- Если мы не попали в текущий блок, возвращаем цвет, который уже есть на текстуре
Для нулевого уровня текстура создастся следующим образом:
if (_Level == 0) {
if (vo.uv.x < _sizeBlock.x) {
float2 uv = float2(vo.uv.x / _sizeBlock.x, vo.uv.y);
return tex2D(_MainTex, uv);
}
else {
return fixed4(0,0,0,1);
}
}
Пропорционально конечному размеру, мы просто вставляем её и остальные пиксели красим в чёрный цвет.
Для остальных уровней необходимо проверить попадание в текущий блок:
if (vo.uv.y >= _startBlock.y && vo.uv.y <= _endBlock.y && vo.uv.x >= _startBlock.x && vo.uv.x <= _endBlock.x) {
Для упрощения вычислений, отличия цвета от исходного будем считать только на первом уровне. Относительные координаты блока рассчитаем следующим образом:
float2 uv = (vo.uv - _startBlock)/_szeBlock;
float2 suv = float2(0.6666666667 * uv.x, uv.y);
Теперь необходимо взять четыре цвета родительского блока и вычислить среднее значение плюс ошибку.
fixed4 col1 = tex2D(_MainTex, suv);
fixed4 col2 = tex2D(_MainTex, float2(min(suv.x + delta.x, _endBlock.x), suv.y));
fixed4 col3 = tex2D(_MainTex, float2(suv.x, min(suv.y - delta.y, _startBlock.y)));
fixed4 col4 = tex2D(_MainTex, float2(suv.x, max(suv.y - delta.y, _startBlock.y)));
col = (col1 + col2 + col3 + col4)/4;
Ошибка вычисляется простым способом: если пиксели отличаются по цвету, то будет добавлять (1/n) к ошибке, где n — количество комбинаций сравнения цветов.
Приведу в пример одну комбинацию:
float rgbError = 0;
if (abs(DecodeFloatRGBA(col2) - DecodeFloatRGBA(col1)) > 0) {
rgbError += 0.1666666667;
}
Результатом функции получается среднее значение цвета пикселя, где альфа-канал — это ошибка. Это главное упрощение в моем алгоритме, так как на расчёт отклонения цвета через гистограмму меня не хватило.
return fixed4(col.rgb, errorColor);
На остальных уровнях принцип схож, только ошибка будет считаться из суммы пикселей родительского блока.
float errorColor = min((col1.a + col2.a + col3.a + col4.a), 1.0);
В итоге, пройдясь по всем уровням, наше дерево будет сформировано. Следующим этапом следует вывод дерева на экран, масштабируя его под размер экрана.
Создание изображение из дерева
Задачей данного шейдера следующая: относительно каждого уровня определить ошибку, и если она не превышает заданный уровень, отрисовать необходимый уровень с цветом пикселя в дереве. Параметрами шейдера:
Properties
{
_MainTex ("Base (RGB)", 2D) = "white" {}
_TileTex ("Tile (RGB)", 2D) = "white" {}
}
- _MainTex — текстура созданного дерева;
- _TileTex — текстура с уровнями дерева, для изменения стилистики визуализации;
От данной текстуры зависит качество конечного изображения, фон прозрачный, а фигура вписанная в квадрат может быть любой.
Основная функция вывода изображения выглядит следующим образом:
fixed4 getLevelColor(float level, float2 uv, float2 cellSize, float outSize) {
float2 suv = float2(0.6666666667 + uv.x*cellSize.x, cellSize.y+uv.y*cellSize.y);
fixed4 color = tex2D(_MainTex, suv);
if (color.a > 0.59-(0.08*(9-level))) {
return fixed4(0,0,0,0);
}
float2 scaledUV = frac(uv/outSize);
float2 patternUV = float2(2*scaledUV.x*outSize, outSize+scaledUV.y*outSize);
fixed4 tileColor = tex2D(_TileTex, patternUV) * fixed4(color.rgb, 1.0);
fixed4 outcolor = lerp(tileColor, fixed4(0,0,0,1), 1 - tileColor.a);
return fixed4(outcolor.rgb, 1);
}
Входные параметры:
- cellSize — относительный размер блока;
- outSize — относительный размер на конечном изображении;
Идея следующая, для каждого пикселя конечного изображения необходимо проходит от самого маленького блока дерева к большому (снизу вверх).
Если ошибка не больше заданного значения (threshold):
if (color.a > 0.59-(0.08*(9-level))) // Прошу прощения за магические наборы цифр.
То выводим нужное изображение с текстуры _TileTex.
В итоге для того чтобы пробежаться по необходимым уровням, мне пришлось жёстко прописать условия без каких-либо циклов.
fixed4 value = float4(0,0,0,0);
value = getLevelColor(7, vo.uv, float2(0.005208333333, 0.0078125), 0.5);
if (value.a > 0) { return value; }
value = getLevelColor(6, vo.uv, float2(0.01041666667, 0.015625), 0.25);
if (value.a > 0) { return value; }
value = getLevelColor(5, vo.uv, float2(0.02083333333, 0.03125), 0.125);
if (value.a > 0) { return value; }
value = getLevelColor(4, vo.uv, float2(0.04166666667, 0.0625), 0.0625);
if (value.a > 0) { return value; }
value = getLevelColor(3, vo.uv, float2(0.08333333333, 0.125), 0.03125);
if (value.a > 0) { return value; }
value = getLevelColor(2, vo.uv, float2(0.1666666667, 0.25), 0.015625);
if (value.a > 0) { return value; }
value = getLevelColor(1, vo.uv, float2(0.3333333333, 0.5), 0.0078125);
if (value.a > 0) { return value; }
return value;
На выходе получим желанный результат:
Эпилог
В итоге мы получили шейдер работающий на слабых мобильных устройствах с частотой кадров 25-30 и больше. В данной статье я затронул обработку изображения с «чистыми» цветами, но можно пойти дальше, и сделать расчёт ошибки отклонения цвета боле сложной, тогда можно использовать данный скрипт в «шумных» изображениях со сложной текстурой.
Пример (с 44 секунды):
Хотел извиниться за множество магических чисел в статье. Спасибо за внимание!
Ссылки на используемые материалы:
- Effcient region segmentation on compressed gray images using quadtree and shading representation. Kuo-Liang Chunga, Hsu-Lien Huanga, Hsueh-I Lu
- RealTime QuadTree Analysis using HistoPyramids. Gernot Ziegler, Rouslan Dimitrovb, Christian Theobalta, Hans-Peter Seidela
a Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, D-66123 Saarbrücken, Germany. bInternational University Bremen GmbH, Postfach 750561, D-28725 Bremen, Germany - HistoPyramid stream compaction and expansion. Christopher Dyken and Gernot Ziegler
- Quadtrees: Implementation. Herman Tulleken
Автор: NikitaSMorozov
