Історія нескінченного міста. На Three.js

WebGL — одна з найбільш цікавих нових технологій, яка здатна дивним чином перетворити інтернет. На базі цієї технології вже створено кілька движків, які дозволяють без зайвих зусиль створювати дивовижні речі, і найбільш відомий з них Three.js. Познайомиться з ним було моїм давнім бажанням, і кращий спосіб зробити це — створити що-небудь цікаве. Першою ідей було накидати «творчі» на сцену Three.js містить велику кількість полігонів, джерел освітлення і частинок, так і має, при цьому, якийсь осмислений контекст. Незабаром, ця ідея перетворилася в бажання створити нескінченний місто в який можна було б зануритися крізь браузер.

Варто сказати, що стаття не просвічена всьому побудови цілком, а лише вирішення найбільш цікавих проблем, з якими довелося зіткнутися в міру створення сцени.

image


Побудова доріг

Занурившись в роботи, знайдені в інтернеті, присвячені процедурному створення віртуальних міст, я виявив, що як правило, для побудови доріг використовується наступний алгоритм:

1. Будується одна або кілька направляючих доріг з однієї або декількох точок, які поступово зростають.
2. При зростанні, з певною ймовірністю, дорога може повернути на певний градус, або породити іншу дорогу зростаючу перпендикулярно їй з похибкою у декілька градусів.
3. Як тільки дорога досягає граничної довжини, або перетинається з іншою дорогою, її ріст припиняється.

Виглядає це приблизно так:


Результат роботи такого алгоритму виглядає досить природно, проте має декілька серйозних недоліків:

1. Висока часова складність: для кожного моменту часу побудови, потрібно пройтися по всіх дорогах збільшивши їх на якусь величину. І для кожної окремої дороги, потрібно пройтися по всіх недобудованим дорогах, що б знайти можливі перетину.
2. Неможливо відтворити ділянку дороги, якщо ключові точки (з яких починається побудова) опинилися за межами видимості, а значить, необхідно створювати велику кількість не потрібних в конкретний момент.

Ці недоліки не дозволяють будувати місто «на льоту». Тому потрібно було придумати інший алгоритм, який був би позбавлений цих недоліків і при цьому давав досить схожий результат. Ідея полягала в тому, щоб не «вирощувати» полотно доріг, а побудувати масив точок перетинань доріг і вже після з'єднати їх лініями. Детально алгоритм виглядає наступним чином:

1. Будується полотно рівновіддалених (з деякою випадковою похибкою) точок, які є центрами нашого міста. Для кожної точки визначається розміри і форма в межах якої відбуватиметься подальше побудова.
2. Для кожної точки, в рамках певної форми, будується своє полотно рівновіддалених (на значно меншу відстань і так само мають деяку похибка) точок, які будуть перетином доріг.
3. Точки які стоять дуже близько один до одного видаляються.
4. Найближчі точки з'єднуються.
5. Для кожної точки будується деяка кількість «будівель» рівне кількості сполук у точки. (Будівля занесена в лапки, бо так по ідеї це не сама будівля, а форма в межах якої цей будинок може бути побудовано, з упевненістю, що воно не буде перетинатися з іншими будівлями)

Таким чином весь місто будується без важкого пошуку перетинів, і може бути відтворений з будь-якої початкової точки. Однак алгоритм все ж має недоліки:

1. Перетину все ж іноді відбуваються, хоча їх ймовірність досить низька.
2. Іноді виникають відокремлені ділянки міста не сполучені трасою з іншим містом.

Виглядає робота алгоритму наступним чином:
image
Червоний — радіус перегляду
Жовтий — граничний радіус побудови


Побудова будівель

Що б прискорити висновок комплексної геометрії в 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 джерел освітлення. Однак все це освітлення рівновіддаленим від основи, а значить і обробляти кожну точку окремо як джерело освітлення зовсім необов'язково, замість цього можна створити текстуру освітленості, ще на стадії генерації міста. Так виглядає така текстура:

image

Все, що залишається зробити безпосередньо в шейдере, це знайти інтенсивність відбиття світла від плоских і помножити її на задану в текстурі освітленість.

Тут можна піти трохи далі. Якщо джерела освітлення не перетинаються, можна створити ще одну структуру, де зберегти висоту на якій знаходиться джерело світла, і завдяки цьому, розміщувати сцену на рельєфній поверхні.

Плавне побудова

Ця задача виявилася найбільш простий, так як простий була основна ідея: необхідно будувати місто на кілька більшу відстань, ніж бачить користувач і поки він пересувається від однієї ключової точки до іншої, заново генерувати місто виходячи вже з наступної ключової точки. Головне, обмежити швидкість пересування користувача таким чином, щоб за час переміщення до наступної точки + час побудови, не можна було досягти межі заздалегідь побудованої частини міста.

Що ж стосується самої генерації, вся вона була розділена на безліч стадій, при цьому для кожної стадії велася статистика (яку можна подивитися зайшовши в консоль браузера) того, як багато часу процесора займає та чи інша стадія на кадр, і якщо цей час було більше деякого значення, стадія ділилася на кілька подстадий до тих пір поки це не дозволяло досягти стабільно високого FPS.

Результат

Сама сцена і вихідний код: тут
Відео версія:


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.