Створіть швидкий блок-аут ландшафту і натисніть кнопку "симулювати".
до і після
Вас цікавить процедурне генерування ландшафтів? Або вам подобаються фізичні симуляції? Тоді ця тема може бути саме для вас.
Я Іво ван дер Веен, студент другого курсу в Університеті прикладних наук Бреди і проходжу курс з Креативних медіа та технологій ігор. Це довга назва, коли кажеш її цілу. У будь-якому випадку, для одного з наших семестрів ми отримали можливість виконати незалежний проект на основі досліджень. Я обрав тему гідравлічної ерозії, яка завжди була мені цікава. У своєму проекті я витратив час на створення системи, щоб користувач міг малювати на ландшафті, а потім використовувати систему ерозії для додавання деталей до свого блок-ауту. Частину коду, що відповідає за малювання на ландшафті, я не обговорюватиму в цьому блозі, тому що це вже неодноразово виконувалося, і в загальному це менш цікаво для обговорення.
З цим блогом ви зможете створити таку ж систему, яку створив я, і я дам вам кілька порад і попереджень про підводні камені, з якими я стикався, щоб ви могли створити кращу версію та реалізувати її швидше, ніж я.
Але перед тим, як розпочати все це.
Що таке гідравлічна ерозія?
Гідравлічна ерозія — це ерозія на горах, яка викликається водою. У випадку моєї симуляції це дощ. Існує багато інших видів ерозії, таких як ерозія вітром, термічна ерозія, льодовикові процеси, прибережна ерозія, хімічна ерозія та багато інших. Сьогодні зосередимося на гідравлічній ерозії та врахуємо деякі ерозії, що викликаються силою тяжіння, такі як зсуви осадових порід. Осад — це ще одне слово для матерії в рідині. Він буде відігравати одну з головних ролей у нашій симуляції.
Зображення ефектів гідравлічної ерозії в реальному житті. (джерело)
Як симулювати гідравлічну ерозію
Після того, як я витратив деякий час на дослідження цієї теми, я виявив, що є два основні підходи до симуляції гідравлічної ерозії. Один метод, який я буду називати Симуляція на основі клітин, і другий — це Симуляція на основі часток.
Симуляція на основі клітин
У цьому підході дані про ландшафт і воду зберігаються в клітинах сітки. Це означає, що вода існує тільки на точках сітки і може взаємодіяти з сусідніми клітинами. Ця сітка може бути двовимірною для води, яка завжди знаходиться поверх ландшафту, або тривимірною для симуляцій, де вода знаходиться один на одному.
Під час симуляції кожна клітина обчислює новий стан, використовуючи дані про те, що вода робить в її власній клітині, і скільки води потрапило з сусідніх клітин. Оскільки кожна клітина повинна перевіряти це на кожному кроці, симуляція не масштабується добре на більші карти. Крім того, ця техніка не є дуже інтуїтивною для розуміння. Особливо коли намагаєшся переконатися, що збереження маси є правильним.
Симуляція на основі часток
Інший метод симуляції ерозії — це метод на основі часток. У цій техніці генерується певна кількість часток (зазвичай близько 10 000, залежно від розміру карти). Ці частки мають координати з плаваючою точкою на ландшафті. У нашому випадку сам ландшафт зберігається у вигляді двовимірної сітки з висотною картою. Частка рухається по цьому ландшафту, обчислюючи нахил, на якому вона знаходиться, і слідує шляхом найменшого опору вниз.
Поки частка рухається вниз, вона еродує та відкладає осад по шляху, врешті-решт випаровуючись або спливаючи за межі карти.
Цей метод симуляції означає, що обчислюються тільки ті частини карти, які зазнали змін, що означає, що продуктивність більше не залежить від розміру карти, а скоріше від кількості часток.
Мій обраний підхід
Підхід, який я обрав, — це симуляція на основі часток. Це тому, що він легко масштабується, досить ефективний і тому, що цей метод здавався мені інтуїтивно зрозумілим.
Окрім цих причин, пізніше я знайшов ще кілька переваг, таких як можливість побачити, куди переміщалися частки, що дозволяє побачити, де можна розмістити тріщини, річки та озера.
Ерозія ландшафту — Теплова карта, що показує потік часток
Як працює система детально
Я написав свою реалізацію на C++, що працює на процесорі. Пізніше я наведу деякі дані про продуктивність, щоб ви могли вирішити, чи хочете ви також використовувати процесор чи написати для GPU. Ця система ерозії була значною мірою побудована на основі паперу Ханса Теобальда Бейера.
Система працює наступним чином:
Переміщення частки
Код проходить через цикл усіх існуючих часток. Потім на початку циклу ми отримуємо поточну позицію частки. У випадку симуляції дощу, ми можемо почати з випадкового розташування всіх часток на карті перед початком циклу.
Оскільки поточна позиція є значенням з плаваючою точкою, а наша карта є сіткою з висотною картою, ми повинні використовувати білінійну інтерполяцію для отримання значення градієнта для нашої частки. Для цього ми обчислюємо ваги на основі відстані від частки до кутів.
Білінійна інтерполяція позиції частки
Потім ми використовуємо ці ваги та висоти чотирьох кутів, щоб інтерполювати градієнт для нашої точки. У коді це виглядає ось так:
vec2 gradient = vec2(((height10 - height00) * (1 - Wy) + (height11 - height01) * Wy),
((height01 - height00) * (1 - Wx) + (height11 - height10) * Wx));
Після отримання цього градієнта ми використовуємо його для обчислення нового напрямку для нашої частки.
// inertia = 0 — завжди обирати відкоригований напрямок.
// inertia = 1 — завжди обирати старий напрямок.
vec2 dirNew = dirOld * inertia - gradient * (1 - inertia);
Це використовує постійну змінну під назвою inertia, яку можна налаштовувати під час симуляції, щоб отримати трохи різні результати. Вона відповідає за те, як швидко частка може змінювати напрямок. В деяких випадках, коли градієнт наближається до 0, новий напрямок може також стати 0. Коли це трапляється, частка знаходиться на рівній місцевості, і ми просто даємо їй новий напрямок у випадковому напрямку, щоб компенсувати дрібні деталі в підйомі, які ми пропустили в нашій симуляції. Переконайтеся, що новий вектор напрямку нормалізовано, перш ніж перейти до наступного кроку.
Коли ми маємо новий напрямок, ми обчислюємо нову позицію частки. Тут ми робимо дещо, що може здаватися неприродним. Ми рухаємо частку на одну клітинку сітки в новому напрямку. Це означає, що ми не використовуємо швидкість для переміщення частки. Причина цього полягає в тому, що якщо частка рухалася б швидко, ми могли б пропустити одну клітинку на висотній карті, що призвело б до ефекту «привидів». Та клітинка, де вода точно була, не буде впливати на симуляцію. Тому, щоб запобігти цьому, ми завжди рухаємо частку на одну клітинку сітки. У випадку сітки розміром 1 одиниця, це означає, що ви можете просто додати нормалізований вектор напрямку до старої позиції.
Після обчислення нового вектору позиції, це хороший момент, щоб перевірити, чи не вийшла частка за межі карти.
Якщо частка виходить за межі, ми видаляємо її зі списку часток і жалкуємо про осад, який щойно покинув карту. Це може здатися проблемним, і ми повернемося до цього пізніше.
Ерозія та депонування
Після того, як ми переміщаємо частку, ми тепер отримуємо висоту нашого старого місця та новообчислену позицію. Для того, щоб отримати висоти, ми знову використовуємо білінійну інтерполяцію. Коли ми маємо висоти, ми обчислюємо різницю у висоті, що дозволяє визначити, що наша частка робила під час цього руху на одну клітинку.
Варіанти досить обмежені, на щастя. Коли різниця у висоті від'ємна, це означає, що наша частка рухалася вниз, що ймовірно вказує на ерозію. Однак, якщо частка рухалася вгору, це означає, що вона щойно вийшла з невеликої ямки. Вода не любить рухатися вгору, тому вона залишить стільки осаду, скільки зможе, сподіваючись заповнити ямку та зробити поверхню рівною.
Розглянемо це детальніше. По-перше, що буде, якщо різниця у висоті додатна і частка рухалася вгору? Як сказано, частка абсолютно не любить ям на місцевості, тому вона залишить увесь свій осад на попередньому місці, намагаючись заповнити ямку. Тому кількість осаду, яку вона залишить, завжди буде меншою або рівною різниці у висоті, яку вона щойно подолала.
Але що, якщо частка рухалася вниз, і різниця у висоті від'ємна? Для цього є трохи складніший підхід. Якщо частка рухається вниз, ми хочемо обчислити її поточну ємність. Це робиться за наступною формулою.
capacity = -heightDif * particle.velocity * particle.water * dropCapacity;
У цій формулі ми беремо поточну швидкість частки та кількість води. Що на початку симуляції повинно бути задано і буде зменшуватися з часом, оскільки вода випаровується. Змінна dropCapacity — це ще одна константа, яку можна налаштувати під час симуляції. Вона відповідає за те, скільки осаду може переносити частка.
Коли це обчислено, є два варіанти. Або частка переносить більше осаду, ніж вона здатна вмістити, або у частки є більше ємності, ніж осаду, який вона переносить.
У першому випадку ми повинні залишити частину осаду на старій позиції. Ми робимо це, беручи кількість осаду, яку ми перенесли занадто багато, і множимо її на постійну швидкість осадження. Ця змінна забезпечує, що не весь осад буде скинутий за один раз на одній клітинці. Якщо це сталося, на місцевості з'являться різкі підвищення, що виглядатиме дуже неприродно. Тому ми залишаємо лише певний відсоток осаду кожного разу.
У іншому випадку, коли ми маємо більше ємності, ніж осаду, ми нарешті можемо перейти до частини, на честь якої система і названа — ерозії. Частка буде еродувати місцевість на попередній позиції. Однак і це не буде зроблено одразу, оскільки це може створити великі ями на місцевості. Натомість ми знову використовуємо постійну змінну, щоб розподілити цей процес на кілька місць.
float erodedSediment = min((capacity - particle.sediment) * erosionRate, heightDif);
Знову ж таки, частка не може еродувати більше, ніж різниця у висоті, яку вона щойно подолала.
Після цього ми завершуємо цикл, обчислюючи нову швидкість частки. Це робиться за такою формулою:
float velNew = sqrtf( max(0.0f,particle.velocity * particle.velocity + -heightDif * gravity));
У цій формулі гравітація — це константа, традиційно встановлена на 9.81f.
Зверніть увагу, що я використовую функцію max, щоб переконатися, що ми не намагаємось отримати квадратний корінь з від’ємного числа.
Нарешті, ми випаровуємо частину води, використовуючи фінальну константу: коефіцієнт випаровування (evaporation Rate).
float waterNew = particle.water * (1 - evaporationRate);
Тепер не забувайте застосовувати всі новообчислені змінні часток і збільшувати змінну тривалості життя частки на одиницю.
Детальніше про ерозію та осадження
Можливо, ви помітили, що я пропустив код для осадження і ерозії. Не хвилюйтесь, я розгляну це детальніше зараз.
Для осадження осадів ми просто отримуємо кількість осадів, які потрібно осадити, і позицію, на якій їх треба осадити, та використовуємо білінійну інтерполяцію, щоб отримати ваги для навколишніх точок сітки. Потім ми використовуємо ці ваги, щоб правильно розподілити осади назад на висотну карту.
При ерозії місцевості ви можете зробити це трохи складніше, але й точніше. Як я згадував на початку, ми будемо враховувати ковзання осадів та іншу гравітаційну ерозію. Це тому, що при ерозії частини місцевості часто відбувається так, що навколишня місцевість також еродується трохи, щоб заповнити утворену ямку і створити більшу, більш згладжену вм’ятину в місцевості.
Для цього в коді ми додаємо константу змінної erosionRadius. Використовуючи цю змінну, ми проходимо через квадрат позицій навколо точки падіння, призначаючи ваги для кожної позиції залежно від відстані цієї позиції до точки падіння.
float weight = (max(0.0f, erosionRadius - length(pos - posCurrent)))
Це перетворює квадрат на коло ваг. Ми зберігаємо кожну вагу для кожної позиції в масиві та також тримаємо загальну змінну ваги, додаючи всі ваги. Коли це буде зроблено, ми знову проходимо через той самий квадрат і починаємо еродувати місцевість.
Кількість еродованих осадів залежить від їх призначеної ваги, поділеної на загальну вагу. Це ефективно нормалізує всі ваги, щоб ми дотримувалися закону збереження маси.
float erodedSediment = sediment * (weights[i] / totalWeight);
Краї випадки та підводні камені
Є ще кілька дивних речей, які слід обговорити, перш ніж ми зможемо по-справжньому оголосити нашу систему завершеною. Найбільш очевидне з них — це краї випадки. Перш за все, вам завжди слід переконатися, що поточна частка знаходиться на карті і що ви не намагаєтесь отримати дані поза межами карти.
Коли це буде забезпечено, все одно є деякі моменти, на які слід звернути увагу. Однією з великих проблем є те, що Бейєр називає дренажними долинами (drain valleys). Це ефект, коли частки можуть стікати за межі карти, забираючи з собою осади. Це нормально до того моменту, поки один з осаджених шматків не створить невелику ямку на краю. Це призведе до того, що все більше часток буде стікати по цьому краю та еродувати поверхню разом з ними. Це створює все більшу і більшу канаву. Щоб зупинити це, Бейєр пропонує встановити мінімальне значення для місцевості. Це означає, що місцевість не може бути еродована нижче певної точки, що запобігає утворенню безкінечних канав.
Дренажна долина з роботи Бейєра
Спочатку я думав, що це рішення не є найкращим і це здавалось трохи обманом. Однак, після того, як я реалізував це сам, виявилося, що воно майже не має видимого ефекту на місцевість. Якщо ви хочете альтернативний підхід, є кілька варіантів. Ви можете створити більшу карту і обрізати краї, коли все буде готово. Ви можете встановити значення за межами карти на дуже велике значення, що зупинить частки від ерозії. Однак, це може призвести до того, що частки отримають неправильний напрямок і почнуть рухатися дивно по краях.
Ще одна проблема, яка може виникнути — це дивні горбики, що утворюються на вашій місцевості. Це досить легко може бути спричинено значеннями, які ви вводите. Для кожного розміру карти є значення, які працюють краще і гірше, і знайти правильне може бути іноді складно.
Один із способів полегшити цей процес — зберегти зміни, які ви внесли у висотну карту, окремо, а потім провести операцію згладжування перед тим, як застосувати її до фінальної висотної карти.
Результати
Після того як все це було написано в коді та запущено, а також створено простий візуалізатор, який рендерить місцевість та застосовує базове текстурування, результат виглядає ось так!
Значення, які я використовую в цій симуляції, такі: місцевість розміру 100 x 100 вершин, кількість часток = 5000, інерція = 0.3, місткість краплі = 10, швидкість осадження = 0.08, швидкість ерозії = 0.7, гравітація = 9.81, коефіцієнт випаровування = 0.02, максимальний час життя = 300 та радіус ерозії = 5.
Ще один таймлапс моєї системи ерозії в роботі
Продуктивність
Щоб показати продуктивність коду, а також як він працює на різних масштабах, я провів кілька стрес-тестів зі стандартними значеннями, змінюючи одне з них, щоб показати, який ефект це має. Кожен вимір часу проводився 5 разів, після чого результати були усереднені для більш надійного результату. Стандартні значення:
float inertia = 0.3f;
float minSlope = 0.01f;
float dropCapacity = 10.0f;
float depositionRate = 0.08f;
float erosionRate = 0.7f;
float gravity = 9.81f;
float evaporationRate = 0.02f;
int erosionRadius = 5;
int maxLifeTime = 300;
int particleCount = 5000;
// map size is 100 x 100 vertices
Кількість часток
значення — час — збільшення часу порівняно з попереднім
1000– 17.37 ms
5000– 78.62 ms — x 4.53
10,000– 156.45 ms — x 1.99
50,000– 791.43 ms — x 5.05
100,000– 1774.60 ms — x 2,24
Як видно з цієї таблиці, змінна кількості часток лінійно збільшує час, який потрібен для обчислення симуляції ерозії. Коли кількість часток збільшується в 5 разів, це також збільшує час обчислень приблизно в 5 разів.
Радіус ерозії
Щоб протестувати змінну радіус ерозії, я використовував майже всі раніше згадані базові налаштування. Кількість часток була збільшена до 10000, щоб зробити ефект більш помітним. Під час тестування я збільшував значення змінної радіус ерозії, як зазначено в таблиці.
значення — час
5–176.62
10–240.02
15–336.76
20–470.00
Як і очікувалося, радіус ерозії збільшує час квадратично (O(n²)), оскільки перевіряється область розміру радіус ерозії x радіус ерозії. Однак цей ефект досить малий, оскільки він впливає тільки на функцію ерозії, яка не викликається весь час. Крім того, при виконанні кількох вимірювань я помітив, що часи варіюються в залежності від того, скільки ерозії відбувається в системі і де саме. (Оскільки по краях радіус буде обрізаний.)
Максимальний час життя частки
значення — час
100–36.04 ms
500–139.37 ms
1000–228.54 ms
1500–325.33 ms
2000–417.68 ms
6000–448.52 ms
Як видно з значень і графіка, змінна часу життя частки має великий ефект, коли ми перебуваємо на нижній частині графіка. Однак, чим більша змінна, тим менше часток залишається для оновлення. Це означає, що графік зрештою згладжується, коли часток залишилось 0. В такому разі збільшення часу життя часток не призведе до значного збільшення часу обчислень. Оскільки єдине, що потрібно зробити — це пройти через цикл, поки не досягнеться максимального часу життя, а потім виконати наступний цикл кожного разу.
for (int i = 0; i < particles.size(); i++)
{
…
}
це означає, що система буде перевіряти розмір часток, поки не пройде через встановлену кількість життєвих циклів.
Розмір карти
значення — час
100 x 100 -79.61 ms
200 x 200–93.98 ms
400 x 400–91.79 ms
1000 x 1000–130.20 ms
Зміна розміру карти не має реального ефекту на часи симуляції ерозії, як і очікувалось.
Проте це дійсно має невеликий ефект, який спричинений тим, що операція отримання даних займає більше часу. Наприклад, отримання даних висотної карти з ландшафту. Це займає більше часу на більшій карті, ніж на меншій. Окрім цього, слід врахувати, що для кожного тесту була згенерована нова випадкова карта, що може призвести до дещо більш або менш інтенсивної ерозії в залежності від ухилів місцевості.
Майбутні оптимізації
На даний момент симуляція ерозії працює на CPU (центральний процесор) в серійному режимі з загальною складністю O(n) (де n — це кількість часток). Для покращення продуктивності можна зробити симуляцію багатопотоковою, розподіляючи роботу між n частками, що дозволить подвоїти або навіть зменшити в чотири рази навантаження. Це можливо, оскільки частки не взаємодіють одна з одною. Вони взаємодіють лише з тією самою місцевістю, можливо, в одній і тій же точці в один і той самий час. Тому я рекомендую використовувати атомарні операції (atomics) при редагуванні висотної карти, щоб уникнути втрат чи перезапису змін.
Окрім цього, цілком можливо перемістити всю симуляцію ерозії на GPU (графічний процесор), замість CPU. Це також було рекомендовано в двох з досліджених мною статей. У мене немає результатів, щоб довести, що це справді покращить швидкість. Проте задача є достатньо довгою, щоб виправдати час, витрачений на налаштування, і під час роботи на GPU CPU може продовжувати виконувати іншу логіку. Це, без сумніву, буде великою вигодою в часі, особливо для симуляцій з більшими значеннями.
Нарешті, варто зазначити, що, на жаль, неможливо поділити світ на частини і завантажувати їх одну за одною або використовувати інші оптимізації з розподілом на частки. Це тому, що симуляція ерозії вимагає, щоб вода могла текти з будь-якої точки карти в будь-яку іншу точку. Якщо карту поділити на частини, то краї часток не зійдуться і загальна точність карти знизиться.
Майбутня робота
Розширення системи ерозії має дуже багато потенціалу з безліччю різних цікавих функцій, які ще можна додати. Можна створити окрему карту, яка містить швидкості ерозії для конкретних матеріалів. Так ви могли б поміщати сильніші валуни у вашу місцевість і спостерігати, як вода текатиме навколо них, ерозуючи їх.
Ви могли б використати карту потоку, щоб реально рендерити і малювати річки, струмки та озера на вашій місцевості.
Можна додати дерева в систему і використовувати їх для зміцнення ґрунту. Для прикладу обох цих пропозицій рекомендую цей чудовий блог.
Можна додати ерозію від вітру або інші типи ерозії.
До того ж, дощ можна симулювати за допомогою справжньої системи погоди, замість випадкового рівномірного розподілу по карті.
В загальному, варіанти майже нескінченні, і я з нетерпінням чекаю, куди це все може привести. Я сподіваюся продовжувати роботу над цим проектом в майбутньому та впроваджувати деякі з цих функцій самостійно. Якщо ви вирішите впровадити це або у вас будуть питання, ви можете зв'язатися зі мною за адресою: [email protected]
або переглянути мое портфоліо.
Джерела
- Hans Theobald Beyer. Implementation of a method for hydraulic erosion. TECHNISCHE UNIVERSITÄT MÜNCHEN. 2015.
- B. Beneš, V. Tˇe´sınský, J. Hornyš, and S. K. Bhatia. Hydraulic Erosion. Computer Animation and Virtual Worlds 17(2), 99–108, 2006.
- B. Beneš and R. Forsbach. Layered Data Representation for Visual Simulation of Terrain Erosion. SCCG ’01 Proceedings of the 17th Spring Conference on Computer Graphics Page 80, 2001
- P. Krištof, B. Beneš, J. Kˇrivánek, and O. Št’ava. Hydraulic Erosion Using Smoothed Particle Hydrodynamics. Computer Graphics Forum (Eurographics 2009) vol. 28 №2, 219–228, 2009.
- https://nickmcd.me/2020/04/10/simple-particle-based-hydraulic-erosion/
6.
https://ranmantaru.com/blog/2011/10/08/water-erosion-on-heightmap-terrain/ - https://www.youtube.com/watch?v=eaXk97ujbPQ&ab_channel=SebastianLague
- https://cs418.cs.illinois.edu/website/text/erosion.html
Перекладено з: Improved terrain generation using hydraulic erosion