Похоже, что каждый, изучающий создание воксельного движка, впитывает знания исключительно осмосом информации. Давайте изменим эту ситуацию и напишем воксельный движок сами!

Введение

Приготовьтесь, мы совершим путь от единственного кубика до целого воксельного движка! Нам понадобится следующее:

• Язык по вашему выбору! Все примеры написаны на псевдокоде, поэтому если вы не напишете для него компилятор, то просто скопипастить его не сможете, так что выберите язык, который вам нравится.

• API рендеринга! Выбирайте что угодно, эта статья — не туториал по рендерингу.

Если в процессе у вас возникнут вопросы, можете связаться со мной на моём сервере Discord или написать на contact@daymare.net.

Привет, куб

Я не планирую делать остальную часть поста столь же поверхностной, но рендеринг куба — это преимущественно графическая задача, и если вы работаете с OpenGL, то для достижения этого этапа достаточно прочитать шесть страниц на LearnOpenGL. Поэтому я буду предполагать, что вы справились с этим самостоятельно.

В конечном итоге у вас должна получиться функция draw_cube, получающая позицию в Vec3 и рисующая в ней куб. Вот как выглядит мой:

А теперь можно добавить ещё несколько кубов. Достаточно будет простого цикла for

for z in 0..32 {
    for x in 0..32 {
        draw_cube(Vec3::new(x, 0, z));
    }
}

Так мы получим прямоугольник 32x32 высотой в один воксель.

Чтобы каждый раз не выполнять цикл for, поместим воксели в структуру данных и назовём её World. Можно записать в неё HashSet позиций, чтобы знать, в каких координатах мира есть воксель.

В некоторых языках программирования невозможно поместить Vec3 в HashSet. Если даже это возможно, придётся преобразовывать Vec3 с плавающей запятой в целочисленное IVec3, потому что это позволит нам обеспечить выравнивание вокселей по сетке. В дальнейшем нам это очень пригодится.

struct World {
    voxels: HashSet<IVec3>,
}

Дальше нужно заполнить мир в начале программы:

for z in 0..32 {
    for x in 0..32 {
        world.voxels.insert(IVec3::new(x, 0, z))
    }
}

после чего можно будет рендерить мир в каждом кадре:

for voxel_pos in world.voxels {
    draw_cube(voxel_pos);
}

После этого у нас получится... точно такая же сцена! Но теперь можно добавить новые возможности, например, возникновение куба в случайном месте простым добавлением его в World.

world.voxels.insert(IVec3::new(7, 2, 13))

Можно даже добавлять и удалять блоки в среде исполнения. Давайте сделаем так, чтобы при нажатии на пробел в нашей координате добавлялся блок или удалялся, если он уже существует:

if input.is_key_pressed(Key::Space) {
    var position = camera.position.as_ivec3();
    if world.voxels.exists(position) {
        world.voxels.remove(position);
    } else {
        world.voxels.insert(camera.position.as_ivec3())
    }
}

Советую поэкспериментировать немного с этим кодом; например, поменяйте размеры исходной платформы, добавьте странные структуры и так далее.

Меши и чанки

Если вы попробовали увеличить размер платформы, то могли заметить, что производительность сильно снижается. Это связано с тем, что если вы реализовали функцию draw_cube так же наивно, как и я (без инстансинга), то коду придётся в каждом кадре обновлять и отрисовывать 36*voxel_count вершин. Из-за чего в каждом кадре в GPU загружается большой объём данных.

Чтобы решить проблему, можно создать единый меш (Mesh) для нашего мира и обновлять его только в начале. Для этого сначала нужно добавить в мир Mesh

struct World {
    voxels: HashSet<IVec3>,
    mesh: Mesh?,
}

? означает, что Mesh может быть отсутствовать, потому что в начале программы его нет.

затем при рендеринге мы сделаем следующее:

if world.mesh != none {
    draw_mesh(world.mesh);
} else {
    create_mesh(world);
    draw_mesh(world.mesh);
}

а create_mesh будет выглядеть примерно так:

fn create_mesh(world: &World) {
    var vertices = [];

    for voxel_pos in world.voxels {
        draw_cube(vertices, voxel_pos);
    }

    world.mesh = Mesh::from_vertices(vertices);
}

Если запустить код, снова должна получиться та же сцена. Но! вы заметите, что теперь мир нельзя менять.

Ох уж эти приколы разработки движков. Произошло следующее: в первом кадре мы кэшировали Mesh нашего мира, но пока не можем никак инвалидировать его. То есть после изменения HashSet мы будем отрисовывать кэшированный Mesh из первого кадра.

Звучит пугающе, но чтобы решить проблему, достаточно вернуться к коду изменения мира и присвоить world.mesh значение none

if input.is_key_pressed(Key::Space) {
    world.mesh = none;
    ...
}

Вуаля!

У нас наконец-то снова есть то, что было пять минут назад.

Раньше мы рисовали весь мир блок за блоком, а теперь рисуем весь мир за раз, что само по себе приводит к совершенно новой проблеме — нам нужно перестраивать мир целиком при изменении даже единственного блока.

Это нормально, если мир имеет размер 32x32, но что, если он размером 2048x2048? Из-за одного изменившегося куба придётся перестраивать четыре миллиона.

Это приводит нас к ещё одному понятию: чанкам.

Но прежде, чем мы перейдём к нему, давайте введём функцию flip_voxel, чтобы сделать нашу работу чуть более удобной.

fn flip_voxel(world: &World, position: IVec3) {
    world.mesh = none;
    if world.voxels.contains(position) {
        world.voxels.remove(position);
    } else {
        world.voxels.insert(position.as_ivec3())
    }
}

после чего можно изменить входные данные следующим образом:

if input.is_key_pressed(Key::Space) {
    flip_voxel(world, camera.position);
}

По сути, мы будем не работать с целым миром, как с огромной структурой данных, а разобьём его на меньшие части, называемые чанками. Каждый чанк — это мини-мир, скажем, размером 32x32x32 блока (конкретный размер здесь не особо важен).

Теперь при размещении и удалении блока мы перестраиваем не мир целиком, а только чанк, к которому относится блок.

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

Чтобы реализовать это, н��м достаточно лишь изменить World так, что он будет хранить каждый воксель не в одном большом HashSet, а в чанке. Каждый чанк отслеживает собственные воксели, а мир отслеживает только то, какие чанки существуют. Также мы перенесём поле mesh из мира в чанк.

Ради удобства мы просто переименуем World в Chunk и создадим новый тип World.

struct World {
    chunks: HashMap<IVec3, Chunk>, // !!
}

struct Chunk {
    voxels: HashSet<IVec3>,
    mesh: Mesh?,                   // !!
}

В моей реализации Chunk будет начинаться с (0, 0, 0) и заканчиваться в (32, 32, 32). А World будет хранить Chunk в пространстве чанков.

Это значит, что чанк в точке (1, 5, 3) будет содержать воксели в диапазоне (1x32..2x32, 5x32..6x32, 3x32..4x32).

Чтобы выполнить преобразование из позиции в мире в позицию чанков и локальную позицию, нам нужно выполнить вычисления. Можно разделить позицию в мире на размер чанка (32), чтобы получить позицию чанка в мире. Затем мы берём остаток (или абсолютное значение) позиции в мире от размера чанка, чтобы найти локальную позицию в чанке.

Однако здесь нужно учитывать тонкий момент — существование отрицательных чисел.

Например, возьмём позицию в мире (-7, 0, 0). Мы хотим, чтобы она находилась в чанке (-1, 0, 0) с локальным смещением (7, 0, 0). Но если добавить то, о чём мы говорили, в большинстве языков программирования, то мы получим позицию чанка (0, 0, 0) с локальным смещением (-7, 0, 0). Проблема в том, что чанк в (0, 0, 0) вдвое больше всех остальных чанков.

Это немного неудобно. Чтобы решить эту проблему, можно использовать евклидовы версии этих операций, также известные как деление с округлением вниз/деление с остатком.

Давайте посмотрим, как нужно изменить функцию flip_voxel:

fn flip_voxel(world: &World, position: IVec3) {
    var chunk_position = position.div_euclid(32);
    var local_position = position.rem_euclid(32);

    var chunk = get_or_create_chunk(world, chunk_position);

    chunk.mesh = none;
    if chunk.voxels.contains(local_position) {
        chunk.voxels.remove(local_position);
    } else {
        chunk.voxels.insert(local_position.as_ivec3())
    }
}

Необходимо создать функцию get_or_create_chunk; позже станет понятнее, зачем.

fn get_or_create_chunk(world: &World, chunk_position: IVec3): &Chunk {
    if !world.chunks.contains(chunk_position) {
        world.chunks.insert(chunk_position, Chunk { mesh: none, voxels: HashSet::new() } )
    }

    return world.chunks.get(chunk_position)
}

Разумеется, нам также придётся удалить функцию create_mesh нашего мира и создать её для чанков. (На самом деле, я соврал: достаточно лишь изменить параметр типа с World на Chunk.)

fn create_mesh(chunk: &Chunk) {
    var vertices = [];

    for voxel_pos in chunk.voxels {
        draw_cube(vertices, voxel_pos);
    }

    chunk.mesh = Mesh::from_vertices(vertices);
}

а затем изменить код рендеринга. При рендеринге нужно будет выполнять смещение меша на chunk_pos x chunk_size, потому что мы просто заполняем мир этими чанками.

for chunk_pos, chunk in world.chunks {
    var offset = chunk_pos * 32;
    if chunk.mesh != none {
        draw_mesh(chunk.mesh, offset);
    } else {
        create_mesh(chunk);
        draw_mesh(chunk.mesh, offset);
    }
}

Ой, чуть не забыл! Также нужно изменить способ заполнения мира в начале программы:

for z in 0..32 {
    for x in 0..32 {
        world.flip_voxel(IVec3::new(x, 0, z));
    }
}

world.flip_voxel(IVec3::new(7, 2, 13));

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

Уф, какой большой объём работы для создания не особо красивого результата. Вероятно, следует рассмотреть оптимизацию генерации мешей, но пока давайте поговорим об основах генерации мира.

Генерация мира

Простейшая генерация мира может заключаться в создании плоской платформы на каком-то уровне по оси Y. При такой системе всё будет тривиально!

Первым делом нужно изменить функцию get_or_create_chunk (я же говорил, что позже это окажется важным!)

Пока она отвечала только за создание пустых чанков. Но теперь мы можем начать генерировать с её помощью и заполненных чанков. При генерации чанка мы будем заполнять его каким-то рельефом. В данном случае рельеф просто «плоский». Ничего впечатляющего, но Москва не сразу строилась.

fn get_or_create_chunk(world: &World, chunk_position: IVec3): &Chunk {
    if !world.chunks.contains(chunk_position) {
        
        var voxels = HashSet::new();
        if chunk_position.y == 0 {
            for z in 0..32 {
                for x in 0..32 {
                    voxels.insert(IVec3::new(x, 0, z));
                }
            }
        }

        world.chunks.insert(chunk_position, Chunk { mesh: none, voxels } )
    }

    return world.chunk.get(chunk_position)
}

Если запустить этот код, то можно заметить, что мир выглядит довольно пустым. Причина в том, что мы не генерируем чанки, которые не были изменены, и чтобы исправить это, нужно ввести концепцию расстояния рендеринга.

Принцип прост: выбираем радиус вокруг камеры и отрисовываем все попавшие в него чанки.

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

Давайте вернёмся к циклу рендеринга и изменим его. Нужно сместить радиус так, чтобы центр находился в камере. Для этого нужно сместить его на чанк, в котором находится камера.

var radius = 4;

var camera_chunk = camera.position.div_euclid(32);

for y in -radius..radius {
    for z in -radius..radius {
        for x in -radius..radius {
            var chunk_offset = IVec3(x, y, z);
            var chunk_pos = camera_chunk + chunk_offset;

            var chunk = get_or_create_chunk(world, chunk_pos);
            
            var offset = chunk_pos * 32;
            if chunk.mesh != none {
                draw_mesh(chunk.mesh, offset);
            } else {
                create_mesh(chunk);
                draw_mesh(chunk.mesh, offset);
            }
        }
    }
}

Вот и всё! Мы получили бесконечную плоскость. Пока не особо впечатляет, но это уже хотя бы что-то новое.

Только видите эту огромную дырку? Похоже, наш старый код генерации мира конфликтует с новым. Можно просто удалить эту часть, и всё будет нормально.

Думаю, настало подходящее время сделать небольшое отступление и поговорить о типах вокселей.

Типы вокселей

Пока наш мир состоял из HashSet вокселей, в которых воксель или существовал, или нет. Это довольно скучно, поэтому придадим нашим вокселям немного индивидуальности.

Начнём с создания enum VoxelKind. Очевидно, можно вызывать его в любой нужный момент.

enum VoxelKind {
    Dirt,
    Stone
}

Теперь заменим HashSet на HashMap

struct Chunk {
    voxels: HashMap<IVec3, VoxelKind>, // !!
    mesh: Mesh?,
}

Отсутствие значения мы по-прежнему будем считать воздухом/пустотой. Но да, по сути, это всё, что нужно для поддержки множественных типов вокселей. (Если не считать десятка мест в коде, которые сразу же сломаются).

Давайте начнём с начала моего файла. Во-первых нужно изменить функцию flip_voxel и сменить её название, потому что во что можно инвертировать блок земли? Я переименую её в set_voxel.

fn set_voxel(world: &World, position: IVec3, kind: VoxelKind?) { // !!
    var chunk_position = position.div_euclid(32);
    var local_position = position.rem_euclid(32);

    var chunk = get_or_create_chunk(world, chunk_position);

    chunk.mesh = none;
    if kind == none {                                         // !!
        chunk.voxels.remove(local_position);
    } else {
        chunk.voxels.insert(local_position, kind)    // !!
    }
}

Затем, естественно, перейдём к функции get_or_create_chunk

fn get_or_create_chunk(world: &World, chunk_position: IVec3): &Chunk {
    if !world.chunks.contains(chunk_position) {
        
        var voxels = HashMap::new();                            // !!
        if chunk_position.y == 0 {
            for z in 0..32 {
                for x in 0..32 {
                    voxels.insert(IVec3::new(x, 0, z), VoxelKind::Dirt); // !!
                }
            }
        }

        world.chunks.insert(chunk_position, Chunk { mesh: none, voxels } )
    }

    return world.chunk.get(chunk_position)
}

И к функции create_mesh. Разумеется, при этом также нужно внести изменения в функцию draw_cube, но я пишу не туториал по рендерингу, поэтому просто буду передавать VoxelKind, а отрисовку оставлю вам.

fn create_mesh(chunk: &Chunk) {
    var vertices = [];

    for (voxel_pos, voxel_kind) in chunk.voxels {    // !!
        draw_cube(vertices, voxel_pos, voxel_kind);  // !!
    }

    chunk.mesh = Mesh::from_vertices(vertices);
}

Входные данные нужно тоже изменить:

if input.is_key_pressed(Key::Space) {
    set_voxel(world, camera.position, VoxelKind::Stone);
}

Теперь всё должно работать!

Также можно изменить генерацию мира так, чтобы ниже Y=0 генерировались блоки камней, в Y=1 — блоки земли, а поверх них воздух.

Я немного изменю цикл, чтобы вам было проще менять его и добавлять что-то своё!

fn get_or_create_chunk(world: &World, chunk_position: IVec3): &Chunk {
    if !world.chunks.contains(chunk_position) {
        
        var voxels = HashMap::new();

        for z in 0..32 {
            for y in 0..32 {
                for x in 0..32 {
                    var offset = IVec3::new(x, y, z);
                    var world_voxel_position = chunk_position * 32 + offset;

                    if world_voxel_position.y == 0 {
                        voxels.insert(offset, VoxelKind::Dirt);
                    } else if world_voxel_position.y < 0 {
                        voxels.insert(offset, VoxelKind::Stone);
                    }
                }
            }
        }

        world.chunks.insert(chunk_position, Chunk { mesh: none, voxels } )
    }

    return world.chunk.get(chunk_position)
}

И на этом генерация мира завершена! Художественные украшения я оставлю вам.

Если вы поэкспериментируете с миром, то заметите, что он крайне медленный. Я хотел оставить разговор о производительности на потом, но, похоже, теперь придётся ею заняться.

Дело вот в чём: вероятно, вы предположите, что проблема заключается в использовании HashMap для каждого вокселя. Да, частично это так, но более серьёзная проблема в том, что мы генерируем слишком много ненужных граней.

Если вы походите по миру и попробуйте залезть в землю, то заметите, что грани отрисовываются между блоками, где они даже не будут видимы!

Возможно, глядя на землю, вы увидите странные артефакты, тоже частично вызванные этими скрытыми гранями.

Что же нам делать? Для начала нужно преобразовать функцию draw_cube в функцию draw_quad, потому что мы должны будем отрисовывать за раз только одну грань, а не все шесть. После этого изменения станут довольно простыми.

Достаточно изменить функцию create_mesh так, чтобы для каждой проверяемой грани в соответствующем направлении не было вокселя.

fn create_mesh(chunk: &Chunk) {
    var neighbours = [
        (IVec3::new( 1,  0,  0), Direction::Right),
        (IVec3::new(-1,  0,  0), Direction::Left),
        (IVec3::new( 0,  1,  0), Direction::Up),
        (IVec3::new( 0, -1,  0), Direction::Down),
        (IVec3::new( 0,  0,  1), Direction::Forward),
        (IVec3::new( 0,  0, -1), Direction::Back),
    ]
    var vertices = [];

    for (voxel_pos, voxel_kind) in chunk.voxels {
        for (offset, dir) in neighbours {
            if !chunk.voxels.contains(voxel_pos + offset) {
                draw_quad(vertices, voxel_pos, voxel_kind, dir);
            }
        }
    }

    chunk.mesh = Mesh::from_vertices(vertices);
}

Вот и всё! Отрисовывая только видимые грани, мы уже сможем не отрисовывать до 90% вершин!

Можете теперь немного поэкспериментировать. Перемещайтесь по миру, поиграйте с его генерацией (например, попробуйте шум Перлина!), а потом возвращайтесь и мы займёмся физикой.

Физика

Нам остался последний рывок. Давайте начнём с добавления интерактивности при помощи рейкастинга.

Рейкастинг

Наша цель — научиться добавлять и ломать блоки, на которые мы смотрим. Для этого нужно испускать из камеры луч, то есть «стрелять» отрезком из камеры в мир, чтобы проверить, с каким вокселем происходит первое столкновение.

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

Обычно это называется DDA-рейкастинг (Digital Differential Analyzer). Принцип таков:

• Начинаем из позиции камеры

• Выясняем, как далеко нужно двигаться по каждой оси (x, y, z), прежде чем мы наткнёмся на следующий воксель

• На каждом шаге перемещаемся по ближайшей оси

• Повторяем, пока на что-нибудь не наткнёмся

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

Если вы ничего не понимаете, не волнуйтесь, я тоже. Главное, что нам нужен следующий код:

fn raycast_voxel(world: &World, start: Vec3, direction: Vec3, max_dist: float): (IVec3, Vec3)? {
    // воксель, в котором мы находимся
    var pos = start.floor().as_ivec3();
    // направление, в котором мы делаем шаг (+1 или -1 по каждой оси)
    var step_dir = direction.sign()

    // как далеко мы шагаем по каждой оси
    var delta = abs(1 / direction)

    // как далеко от текущей позиции до границы следующего вокселя
    // например, если мы на 0.3 внутри вокселя и идём по X в положительную сторону,
    // то остаётся ещё 0.7 до столкновения со стенкой следующего вокселя.
    var fract = start - pos.as_dvec3();
    var t_max = Vec3::new(
        if dir.x > 0.0 { 1.0 - fract.x } else { fract.x } * delta.x,
        if dir.y > 0.0 { 1.0 - fract.y } else { fract.y } * delta.y,
        if dir.z > 0.0 { 1.0 - fract.z } else { fract.z } * delta.z,
    )

    var dist = 0.0;
    var last_move = Vec3::ZERO;

    while dist < max_dist {
        if get_voxel(world, pos) != none {
            return (pos, -last_move.normalize());
        }

        // куча сложной математики
        // ша г по оси с наименьшим t_max — это граница следующего вокселя
        if t_max.x < t_max.y && t_max.x < t_max.z {
            pos.x += step.x;
            dist = t_max.x;
            t_max.x += delta.x;
            last_move = Vec3::new(step.x, 0.0, 0.0);
        } else if t_max.y < t_max.z {
            pos.y += step.y;
            dist = t_max.y;
            t_max.y += delta.y;
            last_move = Vec3::new(0.0, step.y, 0.0);
        } else {
            pos.z += step.z;
            dist = t_max.z;
            t_max.z += delta.z;
            last_move = Vec3::new(0.0, 0.0, step.z);
        }

    }
    none
}

Функция get_voxel теперь будет выглядеть очень похожей на функцию set_voxel, только проще

fn get_voxel(world: &World, position: IVec3): Voxel? {
    var chunk_position = position.div_euclid(32);
    var local_position = position.rem_euclid(32);

    var chunk = get_or_create_chunk(world, chunk_position);
    return chunk.voxels.get(local_position);
}

Вот и всё! Теперь мы можем испускать лучи из камеры и узнавать, на какой воксель мы смотрим, плюс на какую грань. Это пригодится, если мы захотим ломать блоки или создавать их рядом с существующими.

Давайте сделаем это. Можно удалить код, который при помощи пробела размещал или удалял воксель, заменив его следующим

if input.is_mouse_button_pressed(MouseButton::Left) {
    var result = raycast_voxel(world, camera.position, camera.direction, 3)

    if result != none {
        var (target_block, _) = result
        world.set_voxel(target_block, none)
    }
}

Теперь мы можем ломать блоки! Можно сделать что-то подобное и для размещения блоков, и здесь нам пригодится значение last_move.

if input.is_mouse_button_pressed(MouseButton::Right) {
    var result = raycast_voxel(world, camera.position, camera.direction, 3)

    if result != none {
        var (target_block, last_move) = result
        world.set_voxel(target_block + last_move, Voxel::Stone)
    }
}

Как в Minecraft, а все игры пытаются походить на Minecraft.

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

AABB-коллизии

Это тоже потенциально очень сложная тема, как и вся физика, но в нашем случае всё довольно просто, потому что наш мир состоит из вокселей.

Мы будем обрабатывать коллизии AABB (Axis-Aligned Bounding Box, «параллельный осям ограничивающий параллелепипед») с миром. Нам важно только то, пересекается ли этот параллелепипед с миром, и если да, то в этом направлении мы не идём.

Во-первых, нужно добавить камере параллелепипед коллизии. Давайте установим ему размеры (0.8, 1.8, 0.8), потому что нечто подобное используется в Minecraft.

Каким бы ни был ваш код движения камеры, нужно привязать его к переменной new_position перед обновлением истинной позиции камеры, чтобы проверять, не находится ли новая позиция внутри объектов.

После этого можно взглянуть на наш алгоритм.

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

Затем можно применить этот вектор движения для каждой оси, проверить, не находится ли новая позиция внутри вокселя, а затем присвоить её позиции камеры.

Если она внутри вокселя, то можно просто отменить движение в этом направлении.

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

Теперь перейдём к логике AABB. По сути, мы расширим AABB камеры на сетку вокселей.

После этого можно будет просто проверять, только ли воздух находится внутри этого параллелепипеда.

Будем считать, что позиция камеры находится в центре её AABB

Вот алгоритм:

// ..
// new_position должна быть объявлена выше

var aabb_dims = Vec3::new(0.8, 1.8, 0.2);
var aabb_half_dims = aabb_dims / 2;
var delta = new_position - camera.position;

for axis in 0..3 {
    var target_position = new_position;
    target_position[axis] += delta[axis];

    var min = (target_position - aabb_half_dims).floor();
    var max = (target_position + aabb_half_dims).ceil();

    var collided = false;
    for x in min.x..max.x {
        for y in min.y..max.y {
            for z in min.z..max.z {
                var position = IVec3::new(x, y, z);
                if get_voxel(world, position) != none {
                    collided = true;
                    break;
                }
            }

            if collided {
                break;
            }
        }

        if collided {
            break;
        }
    }


    if !collided {
        camera.position[axis] = target_position[axis];
    }

}

Честно говоря, я не лучший преподаватель физики, но мне нужно было добавить этот раздел. В конце концов, кому нужен мир, с которым нельзя взаимодействовать.

И последнее...

Я намеренно оставил это на конец, потому что это всё усложняет, но больше избегать мы этого не можем. Давайте посмотрим на структуру нашего Chunk

struct Chunk {
    voxels: HashMap<IVec3, VoxelKind>,
    mesh: Mesh?,
}

Для хранения вокселей мы используем HashMap, однако это очень плохая идея по множеству причин, самая важная из которых — сильное падение производительности.

Так как наши чанки имеют размер 32x32x32 (то есть IVec3s в HashMap всегда будет находиться в интервале [0, 32)), можно заменить HashMap трёхмерным массивом.

Чтобы сделать это, сначала добавим к VoxelKind тип Air

enum VoxelKind {
    Air,
    Dirt,
    Stone
}

после чего можно изменить Chunk так, чтобы у него был 3D-массив

struct Chunk {
    voxels: [[[VoxelKind; 32]; 32]; 32],
    mesh: Mesh?,
}

Примечание: здесь я индексирую его, как [y][z][x], но если вам привычнее [x][y][z], то можете изменить это.

Очевидно, из-за этого в нашем коде возникнет множество ошибок. Нужно будет заменить все операции доступа к данным voxels на вспомогательные функции set/get.

Впрочем, эти функции тоже нужно будет немного переработать.

Функция set_voxel будет теперь получать не опциональный VoxelKind, а только сам VoxelKind , потому что отсутствие вокселя мы теперь обозначаем, как VoxelKind::Air.

fn set_voxel(world: &World, position: IVec3, kind: VoxelKind) { // !!
    var chunk_position = position.div_euclid(32);
    var local_position = position.rem_euclid(32);

    var chunk = get_or_create_chunk(world, chunk_position);

    chunk.mesh = none;
    
    chunk.voxels[local_position.y][local_position.z][local_position.x] = kind
}

а функция get_voxel станет такой:

fn get_voxel(world: &World, position: IVec3): VoxelKind { // !!
    var chunk_position = position.div_euclid(32);
    var local_position = position.rem_euclid(32);

    var chunk = get_or_create_chunk(world, chunk_position);
    
    chunk.voxels[local_position.y][local_position.z][local_position.x]
}

Дальше вы справитесь сами, я уверен. Со всем, кроме функций get_or_create_chunk и create_mesh.

Давайте посмотрим, как изменится get_or_create_chunk

fn get_or_create_chunk(world: &World, chunk_position: IVec3): &Chunk {
    if !world.chunks.contains(chunk_position) {
        
        var voxels = [[[VoxelKind::Air; 32]; 32]; 32]; // !!
        if chunk_position.y == 0 {
            for z in 0..32 {
                for x in 0..32 {
                    voxels[0][z][x] = VoxelKind::Dirt;
                }
            }
        }

        world.chunks.insert(chunk_position, Chunk { mesh: none, voxels } )
    }

    return world.chunk.get(chunk_position)
}

Да, изменения очевидны, но у нас есть функция create_mesh, где присутствует один тонкий момент, который можно упустить.

В функции create_mesh мы отрисовываем грань только тогда, когда её сосед не существует (теперь это VoxelKind::Air), но поскольку мы использовали HashMap, нам не нужно было беспокоиться, находится ли сосед за пределами чанка.

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

fn create_mesh(chunk: &Chunk) {
    var neighbours = [
        (IVec3::new( 1,  0,  0), Direction::Right),
        (IVec3::new(-1,  0,  0), Direction::Left),
        (IVec3::new( 0,  1,  0), Direction::Up),
        (IVec3::new( 0, -1,  0), Direction::Down),
        (IVec3::new( 0,  0,  1), Direction::Forward),
        (IVec3::new( 0,  0, -1), Direction::Back),
    ]
    var vertices = [];

    for (voxel_pos, voxel_kind) in chunk.voxels {
        for (offset, dir) in neighbours {
            var np = voxel_pos + offset;
            var is_oob = np.any(|axis| axis < 0 || axis >= 32);


            if is_oob || chunk.voxels[np.y][np.z][np.x] == VoxelKind::Air {
                draw_quad(vertices, voxel_pos, voxel_kind, dir);
            }
        }
    }

    chunk.mesh = Mesh::from_vertices(vertices);
}

КОНЕЦ!

Ура!!!

Мы создали воксельный движок! Начали с единственного куба, а теперь у нас есть чанки, рейкастинг, физика и бесконечный мир. Все воксельные движки поначалу выглядят одинаково, так что сделайте свой уникальным.

... или не конец?

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

• Гравитация и прыжки: у нас есть физика, так почему бы не добавить в игру возможностей!

• Смещение AABB камеры: пока мы предполагаем, что камера находится в центре своего AABB; это простое, но не очень правильное решение. Голова выше, чем середина тела, поэтому попробуйте это изменить

• Процедурный рельеф: я не затрагивал это в разделе о генерации мира, потому что это больше относится к художественной части воксельных движков, но определённо стоит рассмотреть эту тему, чтобы придать своему движку индивидуальности. Система, созданная нами в get_or_create_chunk, сильно упростит добавление новых возможностей. Подсказка: в качестве карты высот можно использовать 2D-шум Перлина.

• Сохранение и загрузка: я планировал добавить этот раздел в саму статью, но она и так оказалась достаточно длинной, поэтому оставлю это задание вам. Начните с сохранения данных чанков в двоичный файл и его загрузки в функции get_or_generate_chunk. После этого, если вам любопытно, можете изучить загрузку на основе областей.

• Выгрузка невидимых чанков: чтобы не тратить память впустую, все чанки вне расстояния рендеринга можно выгружать на диск; попробуйте периодически проверять, находится ли чанк в пределах расстояния рендеринга, и если нет, то выгружать его.

• Устранение граней между чанками: возможно, вы заметили, что хоть мы и сильно оптимизировали меш, но между чанками всё равно есть много невидимых граней. Их тоже не так сложно удалить, функция create_mesh должна знать и об окружающих чанках. На этом вполне можно завершить оптимизацию мешей.

• Усечение по пирамиде видимости: сейчас мы отрисовываем каждый чанк в пределах расстояния рендеринга, даже если он находится сзади нас. Попробуйте добавить усечение по пирамиде видимости (frustum culling), чтобы отрисовывались только видимые чанки.

• Ambient Occlusion: есть отличная статья об ambient occlusion для вокселей, она позволит превратить пластмассовый мир в настоящий.

• Текстуры!: я использовал для вокселей сплошные цвета, и могу лишь предположить, что вы поступали так же. Попробуйте добавить текстуры и, может, даже текстурный атлас.

• Жадное создание мешей: итак, вы не вняли моим предупреждениям. Значит, двигайтесь по этому пути.

• Разумеется, освещение: после ambient occlusion логично будет попробовать реализовать освещение. Информацию об освещении в стиле Minecraft можно прочитать в статье. Можно заметить, что чанки в Minecraft имеют размер 16x256x16, а наши чанки — 32x32x32. Но для реализации этой системы освещения необходимо будет определить предел высоты.

• Скорость, скорость, скорость: СКОООРОСТЬ

• Октодеревья: на случай, если HashMap чанков окажутся слишком медленными.

• Многопоточность: сложная тема. Вас ждёт асинхронная генерация чанков, превращение чанков в меши, инвалидация кэшей и многое другое. Но если вы отважитесь на этот квест, то результаты окажутся невероятными.

• Области: это не самая сложная задача, но чтобы решение её оказалось полезным, ваш воксельный движок уже должен быть чрезвычайно быстрым. HashMap очень медленные при большом количестве элементов, поэтому можно попробовать сгруппировать чанки в области 32x32x32.

• Выгрузка чанков v2: тоже непростая тема. Возможно, вы заметите, что при больших расстояниях рендеринга ваш движок потребляет много памяти. Причина в том, что каждый чанк занимает как минимум 32768 байт (если считать, что каждый воксель занимает 1 байт). Раскрою вам тайну: воксельные данные далёких чанков держать в памяти необязательно. Достаточно просто сгенерировать меш и выгрузить его данные. Например, при расстоянии рендеринга 96 потребляемая память снижается с 230 ГБ до 3 ГБ (правдивая история).

• ???: кто сказал, что воксели обязаны обрабатываться CPU?