如何平滑3D体素世界的障碍？ [英] How to smooth the blocks of a 3D voxel world?

问题描述

在我的类似于Minecraft的3D体素世界中，我希望使形状平滑以提供更自然的视觉效果。首先让我们看一下2D的示例。

In my (Minecraft-like) 3D voxel world, I want to smooth the shapes for more natural visuals. Let's look at this example in 2D first.

左是世界的外观，没有任何平滑。地形数据是二进制的，每个体素都以单位大小的多维数据集呈现。

Left is how the world looks without any smoothing. The terrain data is binary and each voxel is rendered as a unit size cube.

在中心，您可以看到幼稚的圆形平滑。它仅考虑了四个直接相邻的块。它看起来仍然不是很自然。而且，我希望出现45度的平坦坡度。

In the center you can see a naive circular smoothing. It only takes the four directly adjacent blocks into account. It is still not very natural looking. Moreover, I'd like to have flat 45-degree slopes emerge.

在右侧，您可以看到我想出的平滑算法。它考虑了八个直接和对角线邻居，以得出一个块的形状。我在线上有 C ++代码。以下是绘制贝塞尔曲线的控制点所附带的代码。

On the right you can see a smoothing algorithm I came up with. It takes the eight direct and diagonal neighbors into account in order to come up with the shape of a block. I have the C++ code online. Here is the code that comes up with the control points that the bezier curve is drawn along.

#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;
}

但是，这仍然是二维的。如何将该算法转换为三个维度？

However, this is still in 2D. How to translate this algorithm into three dimensions?

推荐答案

您可能应该看看行进立方体算法，然后从那里开始工作。您可以轻松地控制生成的斑点的平滑度：

You should probably have a look at the marching cubes algorithm and work from there. You can easily control the smoothness of the resulting blob:

1. 想象一下，每个体素都定义了一个在其中心处具有高密度的场，缓慢地当您从中心移开时，什么都不会消失。例如，您可以使用在体素内部为1并在两个体素之间相距0的函数。不管您选择什么确切的函数，请确保在有限的（最好是较小的）区域内，它仅是非零的。


2. 对于每个点，求和所有字段的密度。


3. 对这些字段的总和使用行进立方体算法


4. 对算法使用高分辨率网格

1. Imagine that each voxel defines a field, with a high density at it's center, slowly fading to nothing as you move away from the center. For example, you could use a function that is 1 inside a voxel and goes to 0 two voxels away. No matter what exact function you choose, make sure that it's only non-zero inside a limited (preferrably small) area.
2. For each point, sum the densities of all fields.
3. Use the marching cubes algorithm on the sum of those fields
4. Use a high resolution mesh for the algorithm

要更改外观/平滑度，您可以更改密度函数和行进立方体算法的阈值。行进多维数据集以创建更平滑的网格的一种可能扩展是以下构想：想象一下，您在多维数据集的边缘遇到两个点，其中一个点位于体积内（高于阈值），另一点位于体积内（低于阈值）。在这种情况下，许多行进立方体算法将边界恰好放置在边缘的中间。可以计算出确切的边界点-这样就消除了混叠。

In order to change the look/smoothness you change the density function and the threshold of the marching cubes algorithm. A possible extension to marching cubes to create smoother meshes is the following idea: Imagine that you encounter two points on an edge of a cube, where one point lies inside your volume (above a threshold) and the other outside (under the threshold). In this case many marching cubes algorithms place the boundary exactly at the middle of the edge. One can calculate the exact boundary point - this gets rid of aliasing.

此外，我建议您在此之后运行网格简化算法。使用行进立方体会导致网格中包含许多不必要的三角形。

Also I would recommend that you run a mesh simplification algorithm after that. Using marching cubes results in meshes with many unnecessary triangles.

这篇关于如何平滑3D体素世界的障碍？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！