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

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

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

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

研究背景

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

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

研究内容

框架设计

实现方法与步骤

  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

发表评论