School

School – Voxel mesh based on Marching Cubes algorithm

_Redstone_c_

This article is used as a research study report during the summer vacation don't take it seriously

Summary This article gives an implementation of the naive Marching Cubes algorithm voxel mesh in Unreal Engine 4, demonstrating the feasibility of the algorithm by generating a sphere with a "smooth" surface.

Key words MarchingCubes UnrealEngine mesh reconstruction game development

Research Background

"Minecraft" is one of the hottest games at the moment. Its voxel terrain system greatly improves the player's ability to modify the terrain, greatly increasing the degree of freedom. Its voxel representation is based on cubes instead of Mesh, which makes it easier to control curved surfaces. The expression ability is limited. At the same time, with the continuous improvement of computer performance, the Marching Cubes algorithm is gradually applied to games.

The Marching Cubes algorithm is a classic algorithm among isosurface rendering algorithms. It is a voxel-level reconstruction method proposed by W. Lorensen et al. in 1987. The MC algorithm is also known as the "isosurface extraction" algorithm. It is mainly used in visualization scenarios in the medical field, such as 3D reconstruction of CT scans and MRI scans. A small number of games have also applied the MC algorithm.

Research Projects

framework design

classDiagram

UObject <|-- URSMarchingCubesMesher
URSMarchingCubesMesher <|-- URSMarchingCubesDefaultMesher
UMeshComponent <|-- URSMarchingCubesMeshComponent

URSMarchingCubesDefaultMesher -- FRSMarchingCubesTables
URSMarchingCubesMeshComponent -- URSMarchingCubesMesher

Implementation methods and steps

  1. Implement basic rendering functions of primitive components
  2. Implement single voxel isosurface rendering
  3. Achieve voxel rendering of any size volume

Problems and solutions

The problem is that the generated Mesh normals and tangents are calculated incorrectly.
The solution is to synthesize the normal line through the difference of density values ​​of adjacent voxels, and calculate the tangent line through quaternion.

Project innovation points

Apply the Marching Cubes algorithm to the field of game development and combine it with Unreal Engine to achieve high-degree-of-freedom object modification.

Research result

core code

The complete code is located at Gitblit .

void URSMarchingCubesDefaultMesher::ProcessCube(const FIntVector& Coord)
{
    check(VolumeData.IsValidIndex(Coord));

    if (Coord.X == 0) return;
    if (Coord.Y == 0) return;
    if (Coord.Z == 0) return;

    if (Coord.X == VolumeData.Size().X - 1) return;
    if (Coord.Y == VolumeData.Size().Y - 1) return;
    if (Coord.Z == VolumeData.Size().Z - 1) return;

    if (Coord.X == VolumeData.Size().X - 2) return;
    if (Coord.Y == VolumeData.Size().Y - 2) return;
    if (Coord.Z == VolumeData.Size().Z - 2) return;

    FIntVector CornerCoords[8];

    for (int32 Index = 0; Index < 8; ++Index)
    {
        CornerCoords[Index] = Coord + FRSMarchingCubesTables::CornerCoordOffset[Index];
    }

    int32 CubeConfiguration = 0;
    for (int32 Index = 0; Index < 8; ++Index)
    {
        if (SampleDensity(CornerCoords[Index]) < IsoLevel)
        {
            CubeConfiguration |= (1 << Index);
        }
    }

    const auto EdgeIndices = FRSMarchingCubesTables::Triangulation[CubeConfiguration];

    for (int32 TriangleIndex = 0; TriangleIndex < 5; ++TriangleIndex)
    {
        if (EdgeIndices[TriangleIndex][0] == -1) break;

        FTriangle Triangle;

        const auto EdgeIndexA = FRSMarchingCubesTables::CornerIndexFromEdge[EdgeIndices[TriangleIndex][0]];
        const auto EdgeIndexB = FRSMarchingCubesTables::CornerIndexFromEdge[EdgeIndices[TriangleIndex][1]];
        const auto EdgeIndexC = FRSMarchingCubesTables::CornerIndexFromEdge[EdgeIndices[TriangleIndex][2]];

        Triangle.VertexA = CreateVertex(CornerCoords[EdgeIndexA[0]], CornerCoords[EdgeIndexA[1]]);
        Triangle.VertexB = CreateVertex(CornerCoords[EdgeIndexB[0]], CornerCoords[EdgeIndexB[1]]);
        Triangle.VertexC = CreateVertex(CornerCoords[EdgeIndexC[0]], CornerCoords[EdgeIndexC[1]]);

        Triangles.Enqueue(Triangle);
    }
}

Physical display

in conclusion

Through a simple attempt to implement the Marching Cubes algorithm in Unreal Engine, we can understand the feasibility of the algorithm in the engine. The code structure of this attempt is slightly confusing, which is a target that can be improved.

References

[1] Virginia Polytechnic Institute and State University.Voxel-Based Terrain for Real-Time Virtual Simulations． 1994-1996
[2] Sebastian Lague.SebLague/Marching-Cubes． GitHub, 2019
[3] Sebastian Lague.Coding Adventure: Marching Cubes． YouTube, 2019
[4] Eldemarkki.Eldemarkki/Marching-Cubes-Terrain． GitHub, 2021
[5] Eldemarkki.Open Source Marching Cubes in Unity | Triplanar Shader． YouTube, 2019

Post Reply