История бесконечного города. На Three.js
WebGL — одна из самых интересных новых технологий, которая способна удивительным образом преобразовать интернет. На базе этой технологии уже создано несколько движков, которые позволяют без лишних усилий создавать удивительные вещи, и наиболее известный из них Three.js. Познакомится с ним было моим давним желанием, и лучший способ сделать это — создать что-нибудь интересное. Первой идей было набросать «воодушевляющую» сцену на Three.js содержащую как большое количество полигонов, источников освещения и частиц, так и имеющую, при этом, какой-то осмысленный контекст. Вскоре, эта идея превратилась в желание создать бесконечный город в который можно было бы погрузиться сквозь браузер.
Стоит сказать, что статья просвещена не всему построению целиком, а лишь решению наиболее интересных проблем, с которыми пришлось столкнуться по мере создания сцены.
Построение дорог
Окунувшись в работы, найденные в интернете, посвященные процедурному созданию виртуальных городов, я обнаружил, что как правило, для построения дорог используется следующий алгоритм:
1. Строится одна или несколько направляющих дорог из одной или нескольких точек, которые постепенно растут.
2. При росте, с определенной вероятностью, дорога может повернуть на некоторый градус, либо породить другую дорогу растущую ей перпендикулярно с погрешностью в несколько градусов.
3. Как только дорога достигает предельной длины, либо пересекается с другой дорогой, ее рост прекращается.
Выглядит это примерно так:
Результат работы такого алгоритма выглядит весьма естественно, однако имеет несколько серьезных недостатков:
1. Высокая временная сложность: для каждого момента времени построения, нужно пройтись по всем дорогам увеличив их на некую величину. И для каждой отдельной дороги, нужно пройтись по всем недостроенным дорогам, что бы найти возможные пересечения.
2. Невозможно воспроизвести участок дороги, если ключевые точки (из которых начинается построение) оказались за пределами видимости, а значит, необходимо создавать большое количество не нужных в конкретный момент данных.
Эти недостатки не позволяют строить город «на лету». Поэтому нужно было придумать другой алгоритм, который был бы лишен этих недостатков и при этом давал достаточно схожий результат. Идея заключалась в том, чтобы не «выращивать» полотно дорог, а построить массив точек — пересечений дорог и уже после соединить их линиями. Детально алгоритм выглядит следующим образом:
1. Строится полотно равноудаленных (с некоторой случайной погрешностью) точек, которые будут является центрами нашего города. Для каждой точки определяется размеры и форма в пределах которой будет происходить дальнейшее построение.
2. Для каждой точки, в рамках определенной формы, строится свое полотно равноудаленных (на значительно меньшее расстояние и так же имеющие некоторую погрешность) точек, которые будут являться пересечением дорог.
3. Точки которые стоят слишком близко друг к другу удаляются.
4. Ближайшие точки соединяются.
5. Для каждой точки строится некоторое количество «зданий» равное количеству соединений у точки. (Здание занесено в кавычки, так так по идее это не само здание, а форма в пределах которой это здание может быть построено, с уверенностью, что оно не будет пересекаться с другими зданиями)
Таким образом весь город строится без тяжелого поиска пересечений, и может быть воссоздан из любой начальной точки. Однако алгоритм все же имеет недостатки:
1. Пересечения все же иногда происходят, хотя их вероятность достаточно низка.
2. Иногда возникают обособленные участки города не соединенные трассой с остальным городом.
Выглядит работа алгоритма следующим образом: 
Красный — радиус просмотра
Желтый — предельный радиус построения
Построение зданий
Что бы ускорить вывод комплексной геометрии в Three.js существует модуль работы с буферной геометрией, который позволят создавать сцены с невероятным количеством элементов (пример). Однако, что бы все работало быстро, все здания необходимо хранить в одном едином меше, а значит и с единым материалом, которому требовалось передать несколько текстур зданий, чтобы хоть немного их разнообразить. И хотя передать массив текстур в шейдер проблемой не является, для этого в three.js существует специальный тип униформы, проблемой оказалось то, что в GLSL ES 1.0 (который используется для компиляции шейдеров в WebGL) нельзя в качестве индекса массива использовать не константу, а значит и использовать переданный номер текстуры для каждого конкретного здания.
Решение нашлось в том, что в качестве индекса можно использовать итератор цикла. Выглядит это примерно так:
const int max_tex_ind = 3; //Максимальное количество текстур
uniform sampler2D a_texture [max_tex_ind]; //Массив текстур
varying int indx; //Индекс используемой текстуры (индекс передается в вертексный шейдер, как параметр для каждой вершины)
...
void main() {
vec3 tex_color;
for (int i = 0; i < max_tex_ind; i++) {
if (i == indx) {
tex_color = texture2D(a_texture[i],uv).xyz;
}
}
...
}
Конечно, такое решение будет работать хорошо лишь в том случае, если максимальное количество текстур не велико. Альтернативное решение может заключаться в том, чтобы использовать одну большую текстуру, склеенную из необходимых текстур, однако в таком случае придется пожертвовать качеством каждой отдельной текстуры.
Освещение
Для придания городу большей визуальной привлекательности я решил добавить освещение имитирующее свет уличных фонарей. Конечно для решения этой задачи не подходит стандартное освещение используемое в Three.js количество которого значительно ограничено, в то время, как в среднем на сцене присутствует ~8000 источников освещения. Однако все это освещение равноудалено от основания, а значит и обрабатывать каждую точку в отдельности как источник освещения совсем необязательно, вместо этого можно создать текстуру освещенности, еще на стадии генерации города. Так выглядит такая текстура:
Все что остается сделать непосредственно в шейдере, это найти интенсивность отражения света от плоскости и умножить ее на заданную в текстуре освещенность.
Здесь можно пойти чуть дальше. Если источники освещения не пересекаются, можно создать еще одну текстуру, где сохранить высоту на которой находится источник освещения, и благодаря этому, размещать сцену на рельефной поверхности.
Плавное построение
Эта задача оказалась наиболее простой, так как простой была основная идея: необходимо строить город на несколько большее расстояние, чем видит пользователь и пока он передвигается от одной ключевой точки к другой, заново генерировать город исходя уже из следующей ключевой точки. Главное, ограничить скорость передвижения пользователя таким образом, чтобы за время перемещения к следующей точке + время построения, нельзя было достигнуть границы заранее построенной части города.
Что же касается самой генерации, вся она была разделена на множество стадий, при этом для каждой стадии велась статистика (которую можно посмотреть зайдя в консоль браузера) того как много времени процессора занимает та или иная стадия на фрейм, и если это время было больше некоторого значения, стадия делилась на несколько подстадий до тех пор пока это не позволяло достичь стабильно высокого FPS.
Результат
Сама сцена и исходный код: тут
Видео версия:
