NikitaSMorozov Apr 1 2016 at 13:04

Quad-tree визуализация в реальном времени на Shader Model 2.0

6 min

17K

Пролог

Доброго времени суток! Однажды ко мне на работу пришёл друг, и я ему показал свой свеженаписанный шейдер, на тот момент это была первый серьёзный опыт с ними. Данная микропрограмма преобразовывала изображение с камеры в изображение вязаной кофты.

На момент начала разработки изображение бралось с камеры телефона и выводилось в вязанном виде, эффект был необычным. И друг подкинул идею сделать фильтр для камеры в виде квадратичного дерева.

В общем с этого момента я сел за изучения методов быстрого построения квадратичного дерева, и остановился на идеи 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

Tags:

Hubs: