Как сгладить блоки трехмерного воксельного мира?

В моем (похожем на Minecraft) 3D-мире вокселей я хочу сгладить формы для более естественных визуальных эффектов. Давайте сначала посмотрим на этот пример в 2D.

Без сглаживания, круговое сглаживание и сглаживание Безье

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

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

Справа вы видите алгоритм сглаживания, который я придумал. Он принимает во внимание восемь прямых и диагональных соседей, чтобы придумать форму блока. У меня есть код C++ онлайн. Вот код, который выдает контрольные точки, по которым рисуется кривая Безье.

#include <iostream>

using namespace std;
using namespace glm;


list<list<dvec2>> Points::find(ivec2 block)
{
    // Control points
    list<list<ivec2>> lines;
    list<ivec2> *line = nullptr;

    // Fetch blocks, neighbours start top left and count
    // around the center block clock wise
    int center = m_blocks->get(block);
    int neighs[8];
    for (int i = 0; i < 8; i++) {
        auto coord = blockFromIndex(i);
        neighs[i] = m_blocks->get(block + coord);
    }

    // Iterate over neighbour blocks
    for (int i = 0; i < 8; i++) {
        int current = neighs[i];
        int next = neighs[(i + 1) % 8];
        bool is_side   = (((i + 1) % 2) == 0);
        bool is_corner = (((i + 1) % 2) == 1);

        if (line) {
            // Border between air and ground needs a line
            if (current != center) {
                // Sides are cool, but corners get skipped when they don't
                // stop a line
                if (is_side || next == center)
                    line->push_back(blockFromIndex(i));
            } else if (center || is_side || next == center) {
                // Stop line since we found an end of the border. Always
                // stop for ground blocks here, since they connect over
                // corners so there must be open docking sites
                line = nullptr;
            }
        } else {
            // Start a new line for the border between air and ground that
            // just appeared. However, corners get skipped if they don't
            // end a line.
            if (current != center) {
                lines.emplace_back();
                line = &lines.back();
                line->push_back(blockFromIndex(i));
            }
        }
    }

    // Merge last line with first if touching. Only close around a differing corner for air
    // blocks.
    if (neighs[7] != center && (neighs[0] != center || (!center && neighs[1] != center))) {
        // Skip first corner if enclosed
        if (neighs[0] != center && neighs[1] != center)
            lines.front().pop_front();
        if (lines.size() == 1) {
            // Close circle
            auto first_point = lines.front().front();
            lines.front().push_back(first_point);
        } else {
            // Insert last line into first one
            lines.front().insert(lines.front().begin(), line->begin(), line->end());
            lines.pop_back();
        }
    }

    // Discard lines with too few points
    auto i = lines.begin();
    while (i != lines.end()) {
        if (i->size() < 2)
            lines.erase(i++);
        else
            ++i;
    }

    // Convert to concrete points for output
    list<list<dvec2>> points;
    for (auto &line : lines) {
        points.emplace_back();
        for (auto &neighbour : line)
            points.back().push_back(pointTowards(neighbour));
    }
    return points;
}

glm::ivec2 Points::blockFromIndex(int i)
{
    // Returns first positive representant, we need this so that the
    // conditions below "wrap around"
    auto modulo = [](int i, int n) { return (i % n + n) % n; };

    ivec2 block(0, 0);
    // For two indices, zero is right so skip
    if (modulo(i - 1, 4))
        // The others are either 1 or -1
        block.x = modulo(i - 1, 8) / 4 ? -1 : 1;
    // Other axis is same sequence but shifted
    if (modulo(i - 3, 4))
        block.y = modulo(i - 3, 8) / 4 ? -1 : 1;
    return block;
}

dvec2 Points::pointTowards(ivec2 neighbour)
{
    dvec2 point;
    point.x = static_cast<double>(neighbour.x);
    point.y = static_cast<double>(neighbour.y);

    // Convert from neighbour space into
    // drawing space of the block
    point *= 0.5;
    point += dvec2(.5);

    return point;
}

Тем не менее, это все еще в 2D. Как перевести этот алгоритм в трехмерное пространство?


person danijar    schedule 10.09.2012    source источник
comment
Известные алгоритмы, которые могут дать аналогичный результат. Пожалуйста, поищите марширующие кубы. Вы бы не хотели создавать новый алгоритм сортировки, не разобравшись сначала с быстрой сортировкой.   -  person starmole    schedule 14.09.2012
comment
Ваша техника не может справиться с нависающей местностью. Поэтому невозможно использовать ваш алгоритм для обработки нависающих скал. Вам нужен другой алгоритм. Также все алгоритмы, перечисленные в ответах, являются готовыми (?) известными алгоритмами.   -  person Simon    schedule 14.09.2012
comment
Конечно, мой алгоритм не может справиться с нависаниями. Вот почему я хотел бы, чтобы ваша помощь улучшить и обобщить его. К настоящему времени он ориентирован на верхнюю часть моих квадратов. Я считаю, что есть способ довести его до обработки всех сторон кубов одинаково. (Я понимаю марширующие кубы, но это не то, что мне нужно, это другой подход.)   -  person danijar    schedule 14.09.2012
comment
Вы хотите сказать, что марширующие кубики не решают вашу проблему? Почему бы нет? Ответ может позволить мне дать лучший ответ.   -  person Simon    schedule 17.09.2012
comment
у меня та же проблема, но марширующие кубы просто сделали блоки с наклоном до 45 градусов, совсем не очень гладкими ... я не мог понять, как преобразовать воксельные данные в данные плотности любым способом, который марширующие кубы сделают плавными. края.   -  person War    schedule 10.04.2013


Ответы (3)


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

  1. Представьте, что каждый воксель определяет поле с высокой плотностью в центре, которое медленно исчезает до нуля по мере удаления от центра. Например, вы можете использовать функцию, которая равна 1 внутри вокселя и переходит в 0 через два вокселя. Независимо от того, какую именно функцию вы выберете, убедитесь, что она отлична от нуля только в пределах ограниченной (предпочтительно небольшой) области.
  2. Для каждой точки суммируйте плотности всех полей.
  3. Используйте алгоритм марширующих кубов для суммы этих полей.
  4. Используйте сетку высокого разрешения для алгоритма

Чтобы изменить внешний вид/гладкость, вы меняете функцию плотности и порог алгоритма марширующих кубов. Возможным расширением марширующих кубов для создания более гладких сеток является следующая идея: представьте, что вы столкнулись с двумя точками на краю куба, где одна точка находится внутри вашего объема (выше порога), а другая снаружи (ниже порога). В этом случае многие алгоритмы марширующих кубов размещают границу точно посередине ребра. Можно вычислить точную граничную точку - это избавляет от алиасинга.

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

person Simon    schedule 10.09.2012
comment
Я понял, что проведу некоторые исследования своего алгоритма самостоятельно. Однако этот ответ помог мне больше всего, поэтому я принимаю это. Спасибо и за другой ответ. - person danijar; 09.10.2012
comment
эй danijar ты понял это в конце концов? У меня все еще есть проблема с моими марширующими кубами ... кажется, что я делаю очень простое преобразование типа куба в тип наклона 45 градусов ... другие предложили реализовать поверхностные сети на результатах mc, и я еще не понял uv-отображения на новая сетка mc, так как теперь больше нет определяемых граней блока. - person War; 10.04.2013
comment
@Wardy Возможно, вы захотите взглянуть на эту демонстрацию WebGL: * 0fps.net/2012/07/12/smooth-voxel-terrain-part-2 Вот каноническая статья для Marching Cube -- paulbourke.net/geometry/polygonise, также известный как Полигонизация скалярного поля - person Michaelangel007; 01.10.2014

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

  • такой же объем
  • та же поверхность
  • тот самый силуэт

и так далее.

person Simon    schedule 10.09.2012
comment
Также обратите внимание на двойной контур. Вот статья frankpetterson.com/publications/dualcontour/dualcontour.pdf и некоторые связанный вопрос SO stackoverflow.com/questions/6485908/ - person Simon; 12.09.2012

Используйте 3D-реализации для кривых Бизера, известных как поверхности Бизера, или используйте описанные алгоритмы B-Spline Surface:

здесь

or

здесь

person nicholas    schedule 10.09.2012
comment
Хорошо, я упомянул поверхности Безье в своем вопросе. Но как я тогда мог найти контрольные точки? И как заставить его справляться с нависаниями. Вопрос в алгоритме или подходе к нему. - person danijar; 10.09.2012
comment
@danijar Поскольку кривая Безье всегда ограничена выпуклой оболочкой контрольных точек, вы можете просто расширить данные о местности на 1 блок от поверхности и использовать эти в качестве контрольных точек. - person Michaelangel007; 01.10.2014