How to smooth blocks of the 3D world of voxels?

Question

In my (Minecraft-like) 3D world of voxels, I want to smooth out shapes for more natural visual effects. Let's look at this example in 2D first.

On the left is what the world looks like without smoothing. Terrain data is binary, and each voxel is displayed as a unit size cube.

In the center, you see naive circular smoothing. It takes into account only four directly adjacent blocks. This is still not a very natural look. In addition, I would like to have flat 45-degree slopes.

On the right you can see the smoothing algorithm that I came up with. It takes into account eight straight and diagonal neighbors to come up with a block shape. I have C ++ code online. Here is the code that contains the control points at which the Bezier curve is drawn.

#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?

Answer 1

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

• Imagine that each voxel defines a field with a high density in the center, slowly disappearing to zero when you move away from the center. For example, you can use a function that is inside a voxel and goes into 0 of two voxels. No matter what exact function you choose, make sure that it is not equal to zero within a limited (preferably small) area.
• For each point, sum the densities of all fields.
• Use the marching cubes algorithm for the sum of these fields
• Use high resolution mesh for algorithm

To change the appearance / smoothness, you change the density function and the threshold of the marching cubes algorithm. A possible extension of the marching cubes to create smoother meshes is as follows: imagine that you are facing two points on the edge of the cube, where one point lies inside your volume (above the threshold) and the other outside (below the threshold). In this case, many marching cube algorithms place the border exactly in the middle of the edge. You can calculate the exact boundary point - this eliminates smoothing.

I would also recommend that you then run the mesh simplification algorithm. Using marching cubes results in grids with many unnecessary triangles.

Answer 2

As an alternative to my answer above: you can also use NURBS or any algorithm for the partition surface . In particular, partition surface algorithms are distinguished into smooth meshes. Depending on the algorithm and its configuration, you will get smoother versions of your original grid using

• same volume
• same surface
• the same silhouette

etc.

Answer 3

Using 3D implementations for Biezer curves known as Biezer surfaces, or using B-Spline Surface algorithms:

here

or

here