Генерация. Воксели

"Весь мир должен генерироваться" - моя первая мысль, когда я только задумывалась об игре)
И прежде чем генерировать всякие красивости и бегающих за игроком лисичек, надо было сгенерировать ландшафт. Самое первое решение, которое у меня получилось, было очень и очень простым: генерируем простенький шум (Perlin например), где значение шума - оффсет для вершин. Дальше двигаем вершины, например в Compute Shaders, и получаем ландшафт. Такой метод используется в Valheim. Выглядит хорошо, если увеличить плотность сетки мешей, работает очень быстро, легко распараллелить. Но есть и один очень большой минус - ландшафт не может иметь сдвиги по горизонтали, а значит никаких пещер, нависающих скал и прочих деталей, которых мне так хотелось.

Поняв, что решение в лоб мне не подходит, я начала искать другие методы генерации. И вскоре пришла к идее вокселей. Самые популярные примеры воксельных миров - Minecraft и No Man's Sky (а сейчас еще и Enshrouded).

Что такое воксель? Его можно описать как куб пространства с каким-либо значением. Прямой сосед вокселю - пиксель, который живет в 2D мире, тогда как воксель - в 3D мире. В моей задаче каждый воксель хранит значение с плавающей запятой со знаком, то есть обычный float. Это значение означает дистанцию до поверхности, где отрицательное значение - мы под поверхностью, а положительное - над ней. Значение 0 же является самой поверхностью. Такое поле дистанций имеет свое название - Signed Distance Field (SDF). Хотя во многих источниках это значение называется плотностью (density), но мне лично помогло осознать алгоритм именно через дистанцию.

Также воксель еще хранит значение градиента SDF. Что такое градиент? Это вектор изменения значений (дистанций) в каждом вокселе. Чтобы его вычислить нам необходимо знать соседние значения SDF (это уже затык для параллелизации в будущем). Но в общем случае вычисление выглядит вот так:

public float3 ComputeGradient(float x, float y, float z, int seed)
{
     var x1 = ComputeDensity(x + 1, y, z, seed);
     var x2 = ComputeDensity(x - 1, y, z, seed);
                
     var y1 = ComputeDensity(x, y + 1, z, seed);
     var y2 = ComputeDensity(x, y - 1, z, seed);
                
     var z1 = ComputeDensity(x, y, z + 1, seed);
     var z2 = ComputeDensity(x, y, z - 1, seed);

     return math.normalize(new float3(x1 - x2, y1 - y2, z1 - z2));
}

На основе градиента вычисляются как позиции вершин, так и их нормали, но об этом расскажу в следующих постах. Также и про генерацию шума расскажу чуть позже)

Генерация. Octree.

После того как я сгенерировала воксели, я обнаружила, что количество вокселей, которые близки к поверхности, на самом деле очень мало. И большая часть вычислений на самом деле идет в пустоту. Ведь нам не нужны воксели, которые под ландшафтом, мы их все равно не увидим. Нам не нужны также воксели, которые в воздухе, мы их фактически тоже не видим.
Решение этой проблемы на самом деле достаточно простое: отсекаем все ненужное пространство и используем только те воксели, которые очень близки к поверхности.

С отсечением пространства хорошо справляются различные иерархические структуры данных. Я взяла для этого Octree, где корень - это чанк, а листья - воксели. А вот как определить, есть ли поверхность? Надо ли делить узел? Тут я пришла к набору эвристик:
- узел уже является вокселем? Тогда не разбиваем, это лист.
- в узле угловые воксели близки к поверхности (значение близко к 0)? Разбиваем узел.
- в узле угловые воксели и те, которые лежат на гранях, меняют свой знак относительно центрального? Значит тут есть поверхность, разбиваем.
- вычисляем ошибку через квадратичную функцию, она больше порога? Значит возможно тут есть поверхность, разбиваем.

С помощью octree получилось сильно оптимизировать вычисления. Отсекается от 70% до 90% пространства, и кол-во вокселей на чанк сильно уменьшается. Жаль, не смогла найти замеры с того времени, но прирост производительности можно примерно прикинуть.

На скриншоте пример результата octree для чанка. Видно, что самих вокселей стало намного меньше.

В предыдущем посте я рассказала про меши, но может встать вопрос, а как работать с мешами в Jobs? Ведь UnityEngine.Mesh - это managed тип, а мы хотим в Jobs, так еще и под Burst!

Для таких задач Unity добавила т.н. Extended Mesh API: они расширили API для Mesh и добавили поддержку Unity.Collections.

Вот небольшой пример как работать с мешами в Jobs:

// meshes - массив или список UnityEngine.Mesh
var meshDataArray = Mesh.AllocateWritableMeshData(meshes);
for (var i = 0; i < meshes.Length; i++)
{
   var meshData = meshDataArray[i];
   meshData.SetVertexBufferParams(vertexCount, Vertex.Layout);
   meshData.SetIndexBufferParams(indexCount, IndexFormat.UInt32);

    var vertexArray = meshData.GetVertexData<Vertex>();
    var indexArray = meshData.GetIndexData<int>();
    // какая-то логика
}
Mesh.ApplyAndDisposeWritableMeshData(meshDataArray, meshes, MeshUpdateFlags.DontRecalculateBounds | MeshUpdateFlags.DontResetBoneBounds);

Vertex - это кастомная структура вершины.

[StructLayout(LayoutKind.Explicit)]
[DebuggerDisplay("Position = {Position}, Normal = {Normal}")]
public readonly struct Vertex : IEquatable<Vertex>
{
   public static readonly VertexAttributeDescriptor[] Layout =
   {
      new(VertexAttribute.Position, VertexAttributeFormat.Float32, 3),
      new(VertexAttribute.Normal, VertexAttributeFormat.Float32, 3)
   };
        
   [FieldOffset(0)]
   public readonly float3 Position;
   [FieldOffset(12)]
   public readonly float3 Normal;
        
   public Vertex(float3 position, float3 normal)
   {
      Position = position;
      Normal = normal;
   }
}

Генерация. LOD и чанки

В прошлый раз я остановилась на мешах. Если генерировать видимый мир (4х4х4 км) сразу весь, то мы получим 82 426 462 208 вокселей! Звучит очень тяжело, а еще сохранение накатывать на этот мир, а еще с сервером синхронизировать, совсем беда.

Поэтому первым делом надо разбить все пространство на чанки - кубики с размером 16х16х16 вокселей. Каждый чанк обрабатывается отдельно и параллельно. Данные также стараюсь сохранять относительно чанков и локальных координат, так легко понять что к чему относится. Но и в таком виде, мы не уменьшаем количество вокселей, а количество чанков равно 16 777 216.

Чтобы решить эту проблему я решила обратиться к LOD (Level of Details). И даже не ради уменьшения нагрузки на GPU при отрисовке (хотя этот эффект есть), а ради уменьшения кол-ва данных, которые надо обработать.

Все чанки я сгруппировала по LOD: вокруг игрока - уровень 0, чуть дальше - 1, потом - 2 и т.д. Каждый чанк все также имеет 16х16х16 вокселей, но их размер увеличивается! Поэтому чанк с LOD 1 в 8 (2^3) раз больше, чем с LOD 0! А значит мне надо меньшее количество чанков и вокселей, чтобы покрыть большее расстояние.

Чтобы "сшить" эти чанки, мне пришлось увеличить число вокселей до 17х17х17 в каждом чанке, чтобы они перекрывали друг друга. Также как и с вокселями, тут применяется Octree, чтобы отсечь те чанки, которые "пустые". Особенно помогает при перестроении мира при движении игрока.

На скриншоте показаны чанки с разным LOD. Игрок находится в центре.

И вот еще видео, на котором видно как меняются LOD чанков в рантайме, когда игрок перемещается.

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

Кстати, пока писала предыдущий пост, заметила, что патч создается через Allocator! Allocator - это enum с перечислением нескольких аллокаторов, но не сами аллокаторы. Есть рекомендация использовать AllocatorManager.AllocatorHandle, и создавать все коллекции и выделять память через него.

Все дело в том, что все больше и больше добавляются новые типы аллокаторов (тот же Rewind Allocator например), которые не представлены в enum. И используя enum мы просто теряем их поддержку. Я вот тоже использую кастомный аллокатор на базе smmalloc.

Единственный, не очень приятный, момент: NativeArray<T> по умолчанию не поддерживает AllocatorManager.AllocatorHandle! Для его создания необходимо использовать API CollectionHelper.
Создание:

var array = CollectionHelper.CreateNativeArray<int>(1000, /*какой-то аллокатор*/);

Dispose:

CollectionHelper.DisposeNativeArray(array, /*какой-то аллокатор*/);

И Dispose в Jobs использовать не получится! По этой причине Unity использует NativeList<T> или UnsafeList<T>, который легко сконвертировать во временный NativeArray<T>.