School

School – 基于 Marching Cubes 算法的体素网格体

_Redstone_c_

本文用来水暑假的研究性学习报告 不要认真

摘要 本文给出了朴素 Marching Cubes 算法体素网格体在 Unreal Engine 4 中的实现方案，通过生成一个具有“光滑”表面的球体来演示算法的可行性。

关键词 MarchingCubes UnrealEngine 网格重建 游戏开发

研究背景

《Minecraft》是当下比较火热的游戏之一，他的体素地形系统大大提高了玩家对地形的修改能力，使得自由度大大提高，其体素表示是基于 立方体 而不是 Mesh ，这使得其对曲面的表达能力受限，同时随着计算机性能的不断提升， Marching Cubes 算法逐渐应用于游戏。

Marching Cubes 算法是等值面绘制算法中的经典算法，它是 W.Lorensen 等人于 1987 年提出来的一种体素级重建方法。 MC 算法也被称为“等值面提取”算法。其主要应用于医学领域的可视化场景，例如 CT 扫描和 MRI 扫描的 3D 重建等。少部分游戏也已经应用了 MC 算法。

研究内容

框架设计

classDiagram

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

URSMarchingCubesDefaultMesher -- FRSMarchingCubesTables
URSMarchingCubesMeshComponent -- URSMarchingCubesMesher

实现方法与步骤

  1. 实现图元组件基本渲染功能
  2. 实现单体素等值面绘制
  3. 实现任意大小体积体素绘制

出现的问题与解决过程

问题是生成的 Mesh 法线与切线计算错误。
解决是通过临近体素的密度值之差合成法线，通过四元数计算切线。

项目创新点

将 Marching Cubes 算法应用到游戏开发领域，与 Unreal Engine 结合，实现高自由度物体修改。

研究结果

核心代码

完整代码位于 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);
    }
}

实物展示

结论

通过对在 Unreal Engine 中实现 Marching Cubes 算法 的简单尝试，可以了解到该算法在引擎中的可行性，本次尝试的代码结构略显混乱，是一个可以改进的目标。

参考文献

[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

发表回复