Пользователь
0,0
рейтинг
6 июня 2013 в 12:47

Разработка → Процедурное текстурирование: генерация текстуры булыжника из песочницы



Пишем генератор, который принимает с десяток входных параметров и выдает текстуру булыжника.

Введение


Мое хобби — компьютерная графика и изобретение велосипедов. Поиграв в .kkrieger и прочтя этот и этот посты я загорелся желанием написать свой генератор текстур. Выбрав в качестве темы текстуры — булыжник, начал гуглить. Честно скажу, гуглить генератор текстуры булыжника было сложно, даже с опцией -minecraft. Плюнув на это дело начал думать сам.

С чего начать


Ход моих мыслей был примерно следующим:
— мне нужны камни
— нужно больше камней! Для большой текстуры. А чем больше текстура, тем больше время генерации. Это плохо.
— камни бывают разными (по размеру и цвету)
— камни выпуклые (рельефные)
— текстура камней шершавая
— у разного вида камней разные виды шероховатости
— раз у текстуры есть цвет и рельеф, не плохо бы разделить эти компоненты. Пусть будет чистая цветная текстура и карта нормалей.
В нашем генераторе текстура будет строится поэтапно: сначала создаем одну текстуру, накладываем на нее фильтры, смешиваем с другой текстурой и т. д. Теперь нужно вспомнить или найти известные алгоритмы, которые нам могут помочь. Я просто перечислю и кратко опишу все методы, которые я использовал в своем генераторе, попутно рассказывая об оптимизациях.
Генератор я решил писать на C++ с использованием библиотеки Qt 4.X.Y в QtCreator. Однако сам класс генератора я старался писать без Qt.

Ячеистая текстура

Это основа алгоритма. Именно она создает каркас для камней. Вот здесь подробно описано что из себя представляет ячеистая текстура и как ее создавать.
В моем коде за это отвечает функция generateCelluarTexture:
Спойлер
unsigned char *ProceduralTexture::generateCelluarTexture(int size){
	if (size<2)
		size = 2;
	int cellX = w/size+2;
	int cellY = h/size+2;
	int pointsX[cellX][cellY];
	int pointsY[cellX][cellY];
	srand(seed);
	for (int i=0; i<cellX; i++)
		for (int j=0; j<cellY; j++){
			pointsX[i][j] = i*size+rand()%((int)(size*0.7))+size*0.15-size;
			pointsY[i][j] = j*size+rand()%((int)(size*0.7))+size*0.15-size;
		}

	int distBuff[n];
	int maxDist = INT_MIN;

	for (int i=0; i<n; i++){
		int x = i%w;
		int y = i/w;
		int min = INT_MAX;
		int min2 = INT_MAX;
		int startX = x/size;
		int finishX = startX+3;
		for (int cp=-1, point=0; startX<finishX; startX++){
			int startY = y/size;
			int finishY = startY+3;
			for (; startY<finishY; startY++, point++){
				if (startX<0 || startX>=cellX || startY<0 || startY>=cellY)
					continue;
				int d = distance(x, y, pointsX[startX][startY], pointsY[startX][startY]);
				if (d<min){
					cp = point;
					min2 = min;
					min = d;
				}
				if (d<min2 && cp!=point)
					min2 = d;
			}
		}
		distBuff[i] = min2-min;
		if (maxDist<distBuff[i])
			maxDist = distBuff[i];
	}

	unsigned char *img = new unsigned char[n];

	for (int i=0; i<n; i++)
		img[i] = (distBuff[i]*255)/maxDist;
	return img;
}



Функция принимает размер ячейки, возвращает черно-белое изображение текстуры. Теперь не много об оптимизации.
Во-первых что бы не перебирать все точки, я поделил изображение на прямоугольные области заданного размера (size). Таким образом что бы найти ближайшую точку к текущему пикселю необходимо просмотреть 9 точек из текущей и соседних ячеек. Об этом написано в преведенной выше ссылке.
Во-вторых нам не обязательно искать «честное» расстояние. Я говорю о расстоянии между двумя точками. Вполне сойдет квадрат расстояния (избавляемся от извлечения корня) — картинка в итоге получается более контрастной, но на итоговую текстуру отрицательного эффекта не оказывает.

Яркость и контрастность

Думаю многие применяли этот фильтр в фотошопе или других графических редакторах. Теперь напишем его реализацию сами.
Код
void ProceduralTexture::brightnessContrast(unsigned char *img, float brightness, float contrast, bool onePass){ //параметр onePass - эксперементальная оптимизация
	if (brightness!=0){
		if (brightness>0){
			if (brightness>1)
				brightness = 1;
			brightness = 1.0f-brightness;
			for (int i=0; i<n; i++){
				int r = 255-img[i];
				r *= brightness;
				img[i] = 255-r;
			}
		}
		if (brightness<0){
			if (brightness<-1)
				brightness = -1;
			brightness = 1.0f+brightness;
			for (int i=0; i<n; i++)
				img[i] *= brightness;
		}
	}

	if (contrast!=1){
		if (contrast<0)
			contrast = 0;
		int avbr = 0;
		if (!onePass){
			for (int i=0; i<n; i++)
				avbr += img[i];
			avbr /= n;
		} else
			avbr = 127;
		for (int i=0; i<n; i++){
			int res = contrast*(img[i]-avbr)+avbr;
			if (res<0)
				res = 0;
			if (res>255)
				res = 255;
			img[i] = res;
		}
	}
}


Функция принимает на вход указатель на изображение и коэффициенты яркости и контрастности. Формулы для вычисления описаны тут.

Шум перлина

О шуме перлина написано достаточно много статей (в том числе и на хабре), описывать алгоритм я не буду, расскажу лишь об оптимизациях и приведу пример кода.
Код
//в конструкторе:
interpolateTable = NULL;
powTable = new float[maxOctaves];
for (int i=0; i<maxOctaves; i++)
	powTable[i] = pow(0.5, i);

inline int ProceduralTexture::getRnd(int x, int y){
	return (0x6C078965*(seed^((x*2971902361)^(y*3572953751))))&0x7FFFFFFF;
}

inline int ProceduralTexture::pointOfPerlinNoise(int x, int y, int cellSize){
	int dx = x-(x/cellSize)*cellSize;
	int dy = y-(y/cellSize)*cellSize;
	int z1 = getRnd(x-dx, y-dy);					// z3 --- z4
	int z2 = getRnd(x-dx+cellSize, y-dy);			//  |     |
	int z3 = getRnd(x-dx, y-dy+cellSize);			//  + z   +
	int z4 = getRnd(x-dx+cellSize, y-dy+cellSize);	// z1 --- z2

	int z1z3 = z1*(1.0f-interpolateTable[dy])+z3*interpolateTable[dy];
	int z2z4 = z2*(1.0f-interpolateTable[dy])+z4*interpolateTable[dy];
	return z1z3*(1.0f-interpolateTable[dx])+z2z4*interpolateTable[dx];
}

unsigned char *ProceduralTexture::generatePerlinNoise(int octaves){
	unsigned char *img = new unsigned char[n];
	if (octaves<1)
		octaves = 1;
	if (octaves>maxOctaves)
		octaves = maxOctaves;
	for (int i=0; i<n; i++)
		img[i] = 0;

	float norm = 255.0f/INT_MAX;
	for (int j=1; j<=octaves; j++){
		int f = 1<<(octaves-j);
		delete[] interpolateTable;
		interpolateTable = new float[f];
		for (int i=0; i<f; i++){
			float a = ((float)i/(float)f)*M_PI;
			interpolateTable[i] = (1.0f-cosf(a))*0.5f;
		}
		for (int i=0; i<n; i++)
			img[i] += pointOfPerlinNoise(i%w, i/w, f)*powTable[j]*norm;
	}
	return img;
}



Первая оптимизация: избавляемся от вычисления коэффициента интерполяции (1.0f-cosf(a))*0.5f) — для этого мы просто просчитываем заранее все варианты. А вариантов у нас не так уж и много — максимальное количество окатав. Поэтому перед вычислением каждой октавы просчитываем все коэффициенты и заносим в массив interpolateTable.
Вторая оптимизация похожа на первую — все места где вычисляются квадраты мы заменяем на заранее вычисленные значения (powTable).
Так же я постарался как можно сильнее упростить ГСЧ и максимально избавиться от чисел с плавающей точкой.

Эффект мягкой ступенчатости

Этот эффект я придумал сам (а быть может изобрел велосипед — не знаю). А вот название ему лучше придумать не получилось — извините. Чем то похож на эффект постеризации в фотошопе, только он не просто обрезает палитру, но и сглаживает переходы. Постараюсь изобразить его суть в виде графика:
необходимо преобразовать прямую графика линейного градиента в некое подобие лесенки со сглаженными углами.

Для этого берем значение интенсивности цвета текущего пикселя, делим его на количество итераций (ступенек). Запоминаем целую часть и остаток от деления. От остатка отнимаем половину его максимального диазона и умножаем на коэффициент гладкости. Полученое число обратно прибавляем к целой части. Ох, проще в коде показать:
void ProceduralTexture::postEffect(unsigned char *img, int iterations, float smooth){
	for (int i=0; i<n; i++){
		float s = (float)img[i]/255.0f;
		float ds = s*(float)iterations-(float)((int)(s*iterations));
		ds = smooth*(ds-0.5f)+0.5f;
		if (ds>1)
			ds = 1;
		if (ds<0)
			ds = 0;
		s = ((float)((int)(s*(float)iterations))+ds)/(float)iterations;
		img[i] = s*255;
	}
}

Функция принимает на вход указатель на изображение, кторое нужно преобразовать, количество итераций и степень гладкости. Что бы почувствовать как именно изменяет этот фильтр изображения, приведу пример:
количество итераций везде равно пять. Степень гладкости слева на право: 1, 1.5, 2.5

Кстати этот фильтр используется на второй картинке в заголовке поста.

Смешивание

Фильтр смешивания необходим для совмещения двух изображений. Например ячеистой текстуры и шума перлина. Смешивание можно реализовать множеством различных способов. Я сделал следующим образом:
При смешивании указывается параметр valueTest — это число характеризует интенсивность пикселя выше которой он (пиксель) не обрабатывается. Так же указывается параметр opacity — собственно прозрачность при смешивании.
Код
void ProceduralTexture::mix(unsigned char *img1, unsigned char *img2, int valueTest, float opacity){
	for (int i=0; i<n; i++)
		if (img2[i]<=valueTest){
			int b = img2[i];
			int r = img1[i];
			b = ((float)b/valueTest)*255.0f;
			r = r-(255-b)*opacity;
			if (r<0)
				r = 0;
			img1[i] = r;
		}
}



Цвет

Каждый камушек имеет свой уникальный цвет. Но в целом все эти цвета похожи друг на друга. Например камушки можно назвать зелеными или коричневыми, но среди них будет множество разных оттенков зеленого или коричневого. Палитра RGB для таких целей не очень подходит, так как ей сложно скомандовать «дай все оттенки серо-буро-малинового цвета в диапазоне, скажем, 10%». Поэтому я выбрал палитру HSV. Через нее удобно задавать цвет: яркость камней, насыщенность и оттенок. При этом можно указать диапазон оттенка. Так, например, если мне нужны оттенки желтого цвета, я могу установить компоненту оттенка равной 60 плюс-минус 10. В RGB палитре мне бы пришлось повозиться со всеми каналами.
Однако при использовании HSV модели возникает необходимость в конвертации цвета — ведь в итоговом изображении у нас RGB модель. Взяв с той же вики алгоритм, напишем код:
Спойлер
inline ColorRGB ProceduralTexture::hsvToRgb(ColorHSV &hsv){
	ColorRGB rgb;
	if (hsv.s){
		hsv.h %= 360;
		if (hsv.h<0)
			hsv.h += 360;
		int i = hsv.h/60;
		float f = ((float)hsv.h/60.0f)-(float)i;
		unsigned char c1 = (hsv.v*(100-hsv.s))*0.0255f;
		unsigned char c2 = (hsv.v*(100-hsv.s*f))*0.0255f;
		unsigned char c3 = (hsv.v*(100-hsv.s*(1.0f-f)))*0.0255f;
		hsv.v *= 2.55f;
		switch (i){
			case 0:
				rgb.r = hsv.v;
				rgb.g = c3;
				rgb.b = c1;
				break;
			case 1:
				rgb.r = c2;
				rgb.g = hsv.v;
				rgb.b = c1;
				break;
			case 2:
				rgb.r = c1;
				rgb.g = hsv.v;
				rgb.b = c3;
				break;
			case 3:
				rgb.r = c1;
				rgb.g = c2;
				rgb.b = hsv.v;
				break;
			case 4:
				rgb.r = c3;
				rgb.g = c1;
				rgb.b = hsv.v;
				break;
			case 5:
				rgb.r = hsv.v;
				rgb.g = c1;
				rgb.b = c2;
				break;
		}
	} else
		rgb.r = rgb.g = rgb.b = hsv.v;
	return rgb;
}



Теперь остается написать функцию закраски камушков. Я просто перегрузил функцию генерации ячеистой текстуры. По сути вся закраска сводится к тому, что мы при генерации начального набора случайных точек присваиваем им цвет.
Спойлер
ColorRGB *ProceduralTexture::generateCelluarTexture(int size, ColorHSV color, int hueRange){
	if (size<2)
		size = 2;
	int cellX = w/size+2;
	int cellY = h/size+2;
	int pointsX[cellX][cellY];
	int pointsY[cellX][cellY];
	ColorRGB cellColor[cellX][cellY];
	srand(seed);
	for (int i=0; i<cellX; i++)
		for (int j=0; j<cellY; j++){
			pointsX[i][j] = i*size+rand()%((int)(size*0.7))+size*0.15-size;
			pointsY[i][j] = j*size+rand()%((int)(size*0.7))+size*0.15-size;
		}
	color.h -= (hueRange/2);
	for (int i=0; i<cellX; i++)
		for (int j=0; j<cellY; j++){
			ColorHSV c = color;
			c.h += rand()%hueRange;
			cellColor[i][j] = hsvToRgb(c);
		}

	ColorRGB *img = new ColorRGB[n];
	for (int i=0; i<n; i++){
		int x = i%w;
		int y = i/w;
		int px = 0;
		int py = 0;
		int min = INT_MAX;
		int startX = x/size;
		int finishX = startX+3;
		for (; startX<finishX; startX++){
			int startY = y/size;
			int finishY = startY+3;
			for (; startY<finishY; startY++){
				if (startX<0 || startX>=cellX || startY<0 || startY>=cellY)
					continue;
				int d = distance(x, y, pointsX[startX][startY], pointsY[startX][startY]);
				if (d<min){
					px = startX;
					py = startY;
					min = d;
				}
			}
		}
		img[i] = cellColor[px][py];
	}
	return img;
}



Карта нормалей

Для придания рельефа я написал шейдер, который используя текстуру и карту нормалей создает картинку, которую вы видели в заголовке поста. Карту нормалей можно сгенерировать из исходного изображения. Для этого я вычисляю разницу между соседними пикселями — это и есть угол отклонения нормали. После перебора всех пикселей найдя минимальный и максимальный угол я их (углы) нормализую.
Спойлер
void ProceduralTexture::generateNormalMap(unsigned char *img){
	normalMap = new ColorRG[n];
	int maxR = 0;
	int maxG = 0;

	for (int i=0; i<n; i++){
		int x = i%w;
		int y = i/w;
		if (x>0){
			int dr = (int)img[y*w+x-1]-(int)img[y*w+x];
			if (dr>maxR)
				maxR = dr;
		}
		if (y>0){
			int dg = (int)img[(y-1)*w+x]-(int)img[y*w+x];
			if (dg>maxG)
				maxG = dg;
		}
	}
	maxR *= 2;
	maxG *= 2;
	for (int i=0; i<n; i++){
		int x = i%w;
		int y = i/w;
		if (x>0){
			int r = 127+(((int)img[y*w+x-1]-(int)img[y*w+x])*255)/maxR;
			if (r>255)
				r = 255;
			if (r<0)
				r = 0;
			normalMap[y*w+x].r = r;
		} else {
			int r = 127-(((int)img[y*w+x+1]-(int)img[y*w+x])*255)/maxR;
			if (r>255)
				r = 255;
			if (r<0)
				r = 0;
			normalMap[y*w+x].r = r;
		}
		if (y>0){
			int g = 127+(((int)img[(y-1)*w+x]-img[y*w+x])*255)/maxG;
			if (g>255)
				g = 255;
			if (g<0)
				g = 0;
			normalMap[y*w+x].g = g;
		} else {
			int g = 127-(((int)img[(y+1)*w+x]-img[y*w+x])*255)/maxG;
			if (g>255)
				g = 255;
			if (g<0)
				g = 0;
			normalMap[y*w+x].g = g;
		}
	}
}



А вот и сам шейдер. Для наглядности я сделал точечное освещение в положении курсора мыши (на картинках в заголовке курсор мыши находился в верхнем левом углу
Спойлер
//вершинный
varying vec4 texCoord;

void main(){
    gl_Position = gl_ModelViewProjectionMatrix*gl_Vertex;
    texCoord = gl_MultiTexCoord0;
}

//фрагментный
uniform sampler2D colorMap;
uniform sampler2D normalMap;
varying vec4 texCoord;
uniform vec2 light;
uniform vec2 screen;
uniform float dist;

void main() {
    vec3 normal = texture2D(normalMap, texCoord.st).rgb;
    normal = 2.0*normal-1.0;
    vec3 n = normalize(normal);
    vec3 l = normalize(vec3((gl_FragCoord.xy-light.xy)/screen, dist));
    float a = dot(n, l);
    gl_FragColor = a*texture2D(colorMap, texCoord.st);
}



Склеиваем все вместе


Я применял вышеописанные функции в следующем порядке:
— создание ячеистой текстуры
— применение фильтра яркости/контрастности
— создание текстуры с шумом перлина
— применение эффекта ступенчатости к шуму перлина
— применение фильтра яркости/контрастности к шуму перлина
— смешивание ячеистой текстуры и шума перлина
— создание карты нормалей
— раскраска
В каждом из описанных шагов есть свои входные параметры. Изменяя их можно получить огромное количество уникальных текстур.

А как же бесшовная текстура?


Честно я хотел сделать возможность создания бесшовной текстуры. Но почему то было лень. Рецепт прост: при генерации ячеистой текстуры при поиске расстояний на границах нужно использовать точки с противоположно стороны текстуры. А при генерации шума перлина… если честно даже не думал. Наверное что то похожее.

Мало оптимизаций. Оно того стоило?


На самом деле первоначальная реализация кода работала довольно медленно, было много чисел с плавающей точкой, лишних переборов и вычислений. Все что я сделал — это по возможности выносил вычисления и переводил на числа с фиксированной точкой. В итоге производительность между первоначальной версией и текущей выросла примерно 10 раз. Была идея распараллелить алгоритм, однако из-за подозрения что все упирается в работу с памятью я откинул эту мысль.

Исходный код


Основной класс для генерации называется ProceduralTexture. Старался писать более или менее красиво, на сколько это может сделать студент 5 курса. Все остальное — это обвес, интерфейсная часть нужна лишь для демонстрации. Красиво я там не особо старался писать.
исходники

Еще немного примеров



Руслан @Torvald3d
карма
89,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (19)

  • +6
    Хорошо бы исходники на гитхабе, было бы гораздо удобнее.
    • +5
      Или на битбакете.
    • +4
      Готово, залил на гитхаб
  • +2
    Почему не используете libnoise или Accidental Noise Library?
    • +14
      Потому что люблю изобретать велосипеды. Интересно самому все написать, изучить, а вызов готовых функций мало чему учит.
  • 0
    Не плохо было бы реализовать всё тоже самое, но на GPU.
    Скорость должна увеличиться на порядок, а то и два.
    • 0
      А я и хотел сначала сделать это на гпу. Но после того как увидел на сколько сильно может отличаться результат на разных гпу, передумал.
      • 0
        Для данной задачи результат на разных гпу должен быть едва ли не bit-perfect одинаковый.
        Разное получается, если выпендриваться.
      • +2
        Не на гпу такие штуки делать просто бессмысленно. Это дороже-дольше и в прототипировании, и в исполнении.
        Современные гпушечи трассируют лучи через синтезируемого в реальном же времени Вороного в 3D на пофиг, если говорить про производительность.
  • +1
    А не пробовали для создания ячеек использовать диаграмму Вороного?
    • 0
      Я рассматривал такой вариант. Диаграмма Вороного хорошо бы подошла для раскраски, но ячеистая текстура больше подходит для создание рельефности и теней между камнями.
    • 0
      Используемая в статье ячеистая текстура (одна из вариаций Cellular или Worley noise) получает интенсивность как разницу расстояний между второй и первой ближайшей контрольной точкой. В результате 0 (чёрный цвет) получается как раз на границе ячеек диаграммы Вороного. Но кроме границ, получаются еще и холмы в центре ячейки. К тому же алгоритм идеально ложится на GPU.
  • 0
    Крутяк!
    Однако, отмечу, что то, что вы называете шумом Перлина, таковым не является. На самом деле у вас фрактальный value noise, а оригинальный шум Перлина несколько сложнее.

    Кроме того, у вас довольно странные места в коде, много их.
    Например, вот это
    delete[] interpolateTable;
    interpolateTable = new float[f];
    

    значительно и непредсказуемо дороже, чем просто при надобности делать
    (1.0f-cosf(a))*0.5f
    
    • +2
      Почему дороже? Доступ к переменной дешевле чем вычисление. Я тестировал оба варианта и брать готовое значение оказалось дешевле. Если вы про дорогое выделение памяти, то оно происходит всего несколько раз по сравнению с многими тысячами вычисления значений.
      • –1
        Потому что это потенциальное прерывание и уход в ядро на неизвестно сколько миллисекунд. Высвобождение памяти тоже может быть очень не бесплатным.
        Если и предрассчитывать таблицы, то где-то заранее и (квази-)статичного размера. При этом надо иметь в виду размер кэшей, промах по которым может нарушать «Доступ к переменной дешевле чем вычисление».
        • 0
          … только в том случае, если не используешь свой аллокатор.
          В противном случае, у меня выделение/освобождение памяти занимает 5 тактов. Плюс поток контроллера ОЗУ, он же пишет на HDD.
  • +2
    Вспомнил про шикарный генератор рельефа в Space Engine:

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