Unityでボクセルデータからメッシュを生成する方法(Marching Cubes)

# はじめに

![img.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2606983/fce41c6a-a1db-09f5-cd85-5f6c640c97a3.jpeg)

[前回の記事](https://qiita.com/GossiperLoturot/items/671ae90dfa0dc8ebacfa)の中でNaiveSurfaceNetsとMarchingCubesとの比較について書きましたが、MarchingCubesの詳細を記述していなかったので、本記事では、前回の記事で使用したMarchingCubesの実装とその説明を書きたいと思います。

# 環境

- OS: Windows11
- CPU: Ryzen 5 3600 3.6GHz 6core
- Unity 2023.1 alpha (.net starndard 2.1)

# 実装

前回に引き続きボクセルデータのポリゴン化を行います。はじめに書いた通りMarchingCubesと呼ばれる手法でUnity上に実装をします。そして様々なボクセルデータに対する処理時間や頂点数を調べたいと思います。

## Marching Cubes

MarchingCubesはボクセルデータをポリゴン化する手法です。Wikipediaでは[マーチングキューブ法](https://ja.wikipedia.org/wiki/マーチングキューブ法)として詳細まで説明されるなど、NaiveSurfaceNetsと比べて有名な手法であることが分かります。本記事では、[Paul Bourke氏によるMarchingCubesのC言語実装](http://paulbourke.net/geometry/polygonise/)をもとに進めていきたいと思います

### ボクセルデータ

ボクセルデータはボクセルの値が実数であるものを使います。負の数が内側、正の数が外側として解釈します。

### 頂点と面の配置

下図のように立方体上の8つのボクセルの状態(全256通り)に対して、それぞれ頂点と面の配置を定義することでポリゴン化を行います。これは点の配置の回転と状態の反転をもとに下図のような15パターンに単純化されます。

![figure1.png](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a7/MarchingCubes.svg/640px-MarchingCubes.svg.png)

By Jmtrivial - Own work, GPL, https://commons.wikimedia.org/w/index.php?curid=1282165

### 頂点の補間

頂点の位置はボクセルの値をもとに表面を滑らかにするよう位置を補間します。上のように頂点の配置を定めると、頂点は異なる側同士のボクセルからなる辺上に存在します。そして下図のように、その辺上で正負が反転する位置を線形補間によって求め、頂点の位置とします。

![figure2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2606983/9018838e-ef22-3ca9-2e1a-db30a49b85c9.jpeg)

## ソースコード

<details>

```cs
// using UnityEngine;
// using Unity.Collections;
// using System.Text;
// using System.Linq;

public void Execute(float[] voxel, int size, out NativeArray<Vector3> vertices, out NativeArray<int> triangles)
{
    // 頂点と三角面の配列 余分に確保
    var vertexBuf = new NativeArray<Vector3>(size * size * size * 12, Allocator.Temp, NativeArrayOptions.UninitializedMemory);
    var triangleBuf = new NativeArray<int>(size * size * size * 18, Allocator.Temp, NativeArrayOptions.UninitializedMemory);
    var vertexCount = 0;
    var triangleCount = 0;

    for (var x = 0; x < size - 1; x++)
    for (var y = 0; y < size - 1; y++)
    for (var z = 0; z < size - 1; z++)
    {
        // 隣接する8つのボクセルの状態(内側か外側)を256通りで記憶
        var kind = 0;
        if (0 > voxel[ToIdx(x, y, z, 0, size)]) kind |= 1 << 0;
        if (0 > voxel[ToIdx(x, y, z, 1, size)]) kind |= 1 << 1;
        if (0 > voxel[ToIdx(x, y, z, 2, size)]) kind |= 1 << 2;
        if (0 > voxel[ToIdx(x, y, z, 3, size)]) kind |= 1 << 3;
        if (0 > voxel[ToIdx(x, y, z, 4, size)]) kind |= 1 << 4;
        if (0 > voxel[ToIdx(x, y, z, 5, size)]) kind |= 1 << 5;
        if (0 > voxel[ToIdx(x, y, z, 6, size)]) kind |= 1 << 6;
        if (0 > voxel[ToIdx(x, y, z, 7, size)]) kind |= 1 << 7;
        
        // 追加される頂点から面を作成
        for (var i = 0; i < triangleTable[kind].Length; i++)
            triangleBuf[triangleCount++] = vertexCount + i;
        
        // 頂点を追加
        foreach (var i in triangleTable[kind])
        {
            var p0 = ToVec(x, y, z, edgeTable[i][0]);
            var p1 = ToVec(x, y, z, edgeTable[i][1]);
            var g0 = voxel[ToIdx(x, y, z, edgeTable[i][0], size)];
            var g1 = voxel[ToIdx(x, y, z, edgeTable[i][1], size)];
            vertexBuf[vertexCount++] = Vector3.Lerp(p0, p1, (0 - g0) / (g1 - g0));
        }
    }
    
    // 必要なサイズを取り出す
    vertices = vertexBuf.GetSubArray(0, vertexCount);
    triangles = triangleBuf.GetSubArray(0, triangleCount);
}

static int ToIdx(int i, int j, int k, int neighbor, int size)
{
    i += neighborTable[neighbor][0];
    j += neighborTable[neighbor][1];
    k += neighborTable[neighbor][2];
    return i + j * size + k * size * size;
}

static Vector3 ToVec(int i, int j, int k, int neighbor)
{
    i += neighborTable[neighbor][0];
    j += neighborTable[neighbor][1];
    k += neighborTable[neighbor][2];
    return new Vector3(i, j, k);
}

static readonly int[][] neighborTable = new int[][]
{
    new int[] { 0, 0, 0 },
    new int[] { 1, 0, 0 },
    new int[] { 1, 0, 1 },
    new int[] { 0, 0, 1 },
    new int[] { 0, 1, 0 },
    new int[] { 1, 1, 0 },
    new int[] { 1, 1, 1 },
    new int[] { 0, 1, 1 },
};

static readonly int[][] edgeTable = new int[][]
{
    new int[] { 0, 1 },
    new int[] { 1, 2 },
    new int[] { 2, 3 },
    new int[] { 3, 0 },
    new int[] { 4, 5 },
    new int[] { 5, 6 },
    new int[] { 6, 7 },
    new int[] { 7, 4 },
    new int[] { 0, 4 },
    new int[] { 1, 5 },
    new int[] { 2, 6 },
    new int[] { 3, 7 },
};

static readonly int[][] triangleTable = new int[][]
{
    new int[] {  },
    new int[] { 0, 8, 3 },
    new int[] { 0, 1, 9 },
    new int[] { 1, 8, 3, 9, 8, 1 },
    new int[] { 1, 2, 10 },
    new int[] { 0, 8, 3, 1, 2, 10 },
    new int[] { 9, 2, 10, 0, 2, 9 },
    new int[] { 2, 8, 3, 2, 10, 8, 10, 9, 8 },
    new int[] { 3, 11, 2 },
    new int[] { 0, 11, 2, 8, 11, 0 },
    new int[] { 1, 9, 0, 2, 3, 11 },
    new int[] { 1, 11, 2, 1, 9, 11, 9, 8, 11 },
    new int[] { 3, 10, 1, 11, 10, 3 },
    new int[] { 0, 10, 1, 0, 8, 10, 8, 11, 10 },
    new int[] { 3, 9, 0, 3, 11, 9, 11, 10, 9 },
    new int[] { 9, 8, 10, 10, 8, 11 },
    new int[] { 4, 7, 8 },
    new int[] { 4, 3, 0, 7, 3, 4 },
    new int[] { 0, 1, 9, 8, 4, 7 },
    new int[] { 4, 1, 9, 4, 7, 1, 7, 3, 1 },
    new int[] { 1, 2, 10, 8, 4, 7 },
    new int[] { 3, 4, 7, 3, 0, 4, 1, 2, 10 },
    new int[] { 9, 2, 10, 9, 0, 2, 8, 4, 7 },
    new int[] { 2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4 },
    new int[] { 8, 4, 7, 3, 11, 2 },
    new int[] { 11, 4, 7, 11, 2, 4, 2, 0, 4 },
    new int[] { 9, 0, 1, 8, 4, 7, 2, 3, 11 },
    new int[] { 4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1 },
    new int[] { 3, 10, 1, 3, 11, 10, 7, 8, 4 },
    new int[] { 1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4 },
    new int[] { 4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3 },
    new int[] { 4, 7, 11, 4, 11, 9, 9, 11, 10 },
    new int[] { 9, 5, 4 },
    new int[] { 9, 5, 4, 0, 8, 3 },
    new int[] { 0, 5, 4, 1, 5, 0 },
    new int[] { 8, 5, 4, 8, 3, 5, 3, 1, 5 },
    new int[] { 1, 2, 10, 9, 5, 4 },
    new int[] { 3, 0, 8, 1, 2, 10, 4, 9, 5 },
    new int[] { 5, 2, 10, 5, 4, 2, 4, 0, 2 },
    new int[] { 2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8 },
    new int[] { 9, 5, 4, 2, 3, 11 },
    new int[] { 0, 11, 2, 0, 8, 11, 4, 9, 5 },
    new int[] { 0, 5, 4, 0, 1, 5, 2, 3, 11 },
    new int[] { 2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5 },
    new int[] { 10, 3, 11, 10, 1, 3, 9, 5, 4 },
    new int[] { 4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10 },
    new int[] { 5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3 },
    new int[] { 5, 4, 8, 5, 8, 10, 10, 8, 11 },
    new int[] { 9, 7, 8, 5, 7, 9 },
    new int[] { 9, 3, 0, 9, 5, 3, 5, 7, 3 },
    new int[] { 0, 7, 8, 0, 1, 7, 1, 5, 7 },
    new int[] { 1, 5, 3, 3, 5, 7 },
    new int[] { 9, 7, 8, 9, 5, 7, 10, 1, 2 },
    new int[] { 10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3 },
    new int[] { 8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2 },
    new int[] { 2, 10, 5, 2, 5, 3, 3, 5, 7 },
    new int[] { 7, 9, 5, 7, 8, 9, 3, 11, 2 },
    new int[] { 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11 },
    new int[] { 2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7 },
    new int[] { 11, 2, 1, 11, 1, 7, 7, 1, 5 },
    new int[] { 9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11 },
    new int[] { 5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0 },
    new int[] { 11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0 },
    new int[] { 11, 10, 5, 7, 11, 5 },
    new int[] { 10, 6, 5 },
    new int[] { 0, 8, 3, 5, 10, 6 },
    new int[] { 9, 0, 1, 5, 10, 6 },
    new int[] { 1, 8, 3, 1, 9, 8, 5, 10, 6 },
    new int[] { 1, 6, 5, 2, 6, 1 },
    new int[] { 1, 6, 5, 1, 2, 6, 3, 0, 8 },
    new int[] { 9, 6, 5, 9, 0, 6, 0, 2, 6 },
    new int[] { 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8 },
    new int[] { 2, 3, 11, 10, 6, 5 },
    new int[] { 11, 0, 8, 11, 2, 0, 10, 6, 5 },
    new int[] { 0, 1, 9, 2, 3, 11, 5, 10, 6 },
    new int[] { 5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11 },
    new int[] { 6, 3, 11, 6, 5, 3, 5, 1, 3 },
    new int[] { 0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6 },
    new int[] { 3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9 },
    new int[] { 6, 5, 9, 6, 9, 11, 11, 9, 8 },
    new int[] { 5, 10, 6, 4, 7, 8 },
    new int[] { 4, 3, 0, 4, 7, 3, 6, 5, 10 },
    new int[] { 1, 9, 0, 5, 10, 6, 8, 4, 7 },
    new int[] { 10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4 },
    new int[] { 6, 1, 2, 6, 5, 1, 4, 7, 8 },
    new int[] { 1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7 },
    new int[] { 8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6 },
    new int[] { 7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9 },
    new int[] { 3, 11, 2, 7, 8, 4, 10, 6, 5 },
    new int[] { 5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11 },
    new int[] { 0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6 },
    new int[] { 9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6 },
    new int[] { 8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6 },
    new int[] { 5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11 },
    new int[] { 0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7 },
    new int[] { 6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9 },
    new int[] { 10, 4, 9, 6, 4, 10 },
    new int[] { 4, 10, 6, 4, 9, 10, 0, 8, 3 },
    new int[] { 10, 0, 1, 10, 6, 0, 6, 4, 0 },
    new int[] { 8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10 },
    new int[] { 1, 4, 9, 1, 2, 4, 2, 6, 4 },
    new int[] { 3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4 },
    new int[] { 0, 2, 4, 4, 2, 6 },
    new int[] { 8, 3, 2, 8, 2, 4, 4, 2, 6 },
    new int[] { 10, 4, 9, 10, 6, 4, 11, 2, 3 },
    new int[] { 0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6 },
    new int[] { 3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10 },
    new int[] { 6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1 },
    new int[] { 9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3 },
    new int[] { 8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1 },
    new int[] { 3, 11, 6, 3, 6, 0, 0, 6, 4 },
    new int[] { 6, 4, 8, 11, 6, 8 },
    new int[] { 7, 10, 6, 7, 8, 10, 8, 9, 10 },
    new int[] { 0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10 },
    new int[] { 10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0 },
    new int[] { 10, 6, 7, 10, 7, 1, 1, 7, 3 },
    new int[] { 1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7 },
    new int[] { 2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9 },
    new int[] { 7, 8, 0, 7, 0, 6, 6, 0, 2 },
    new int[] { 7, 3, 2, 6, 7, 2 },
    new int[] { 2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7 },
    new int[] { 2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7 },
    new int[] { 1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11 },
    new int[] { 11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1 },
    new int[] { 8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6 },
    new int[] { 0, 9, 1, 11, 6, 7 },
    new int[] { 7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0 },
    new int[] { 7, 11, 6 },
    new int[] { 7, 6, 11 },
    new int[] { 3, 0, 8, 11, 7, 6 },
    new int[] { 0, 1, 9, 11, 7, 6 },
    new int[] { 8, 1, 9, 8, 3, 1, 11, 7, 6 },
    new int[] { 10, 1, 2, 6, 11, 7 },
    new int[] { 1, 2, 10, 3, 0, 8, 6, 11, 7 },
    new int[] { 2, 9, 0, 2, 10, 9, 6, 11, 7 },
    new int[] { 6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8 },
    new int[] { 7, 2, 3, 6, 2, 7 },
    new int[] { 7, 0, 8, 7, 6, 0, 6, 2, 0 },
    new int[] { 2, 7, 6, 2, 3, 7, 0, 1, 9 },
    new int[] { 1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6 },
    new int[] { 10, 7, 6, 10, 1, 7, 1, 3, 7 },
    new int[] { 10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8 },
    new int[] { 0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7 },
    new int[] { 7, 6, 10, 7, 10, 8, 8, 10, 9 },
    new int[] { 6, 8, 4, 11, 8, 6 },
    new int[] { 3, 6, 11, 3, 0, 6, 0, 4, 6 },
    new int[] { 8, 6, 11, 8, 4, 6, 9, 0, 1 },
    new int[] { 9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6 },
    new int[] { 6, 8, 4, 6, 11, 8, 2, 10, 1 },
    new int[] { 1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6 },
    new int[] { 4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9 },
    new int[] { 10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3 },
    new int[] { 8, 2, 3, 8, 4, 2, 4, 6, 2 },
    new int[] { 0, 4, 2, 4, 6, 2 },
    new int[] { 1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8 },
    new int[] { 1, 9, 4, 1, 4, 2, 2, 4, 6 },
    new int[] { 8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1 },
    new int[] { 10, 1, 0, 10, 0, 6, 6, 0, 4 },
    new int[] { 4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3 },
    new int[] { 10, 9, 4, 6, 10, 4 },
    new int[] { 4, 9, 5, 7, 6, 11 },
    new int[] { 0, 8, 3, 4, 9, 5, 11, 7, 6 },
    new int[] { 5, 0, 1, 5, 4, 0, 7, 6, 11 },
    new int[] { 11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5 },
    new int[] { 9, 5, 4, 10, 1, 2, 7, 6, 11 },
    new int[] { 6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5 },
    new int[] { 7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2 },
    new int[] { 3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6 },
    new int[] { 7, 2, 3, 7, 6, 2, 5, 4, 9 },
    new int[] { 9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7 },
    new int[] { 3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0 },
    new int[] { 6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8 },
    new int[] { 9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7 },
    new int[] { 1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4 },
    new int[] { 4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10 },
    new int[] { 7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10 },
    new int[] { 6, 9, 5, 6, 11, 9, 11, 8, 9 },
    new int[] { 3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5 },
    new int[] { 0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11 },
    new int[] { 6, 11, 3, 6, 3, 5, 5, 3, 1 },
    new int[] { 1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6 },
    new int[] { 0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10 },
    new int[] { 11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5 },
    new int[] { 6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3 },
    new int[] { 5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2 },
    new int[] { 9, 5, 6, 9, 6, 0, 0, 6, 2 },
    new int[] { 1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8 },
    new int[] { 1, 5, 6, 2, 1, 6 },
    new int[] { 1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6 },
    new int[] { 10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0 },
    new int[] { 0, 3, 8, 5, 6, 10 },
    new int[] { 10, 5, 6 },
    new int[] { 11, 5, 10, 7, 5, 11 },
    new int[] { 11, 5, 10, 11, 7, 5, 8, 3, 0 },
    new int[] { 5, 11, 7, 5, 10, 11, 1, 9, 0 },
    new int[] { 10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1 },
    new int[] { 11, 1, 2, 11, 7, 1, 7, 5, 1 },
    new int[] { 0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11 },
    new int[] { 9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7 },
    new int[] { 7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2 },
    new int[] { 2, 5, 10, 2, 3, 5, 3, 7, 5 },
    new int[] { 8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5 },
    new int[] { 9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2 },
    new int[] { 9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2 },
    new int[] { 1, 3, 5, 3, 7, 5 },
    new int[] { 0, 8, 7, 0, 7, 1, 1, 7, 5 },
    new int[] { 9, 0, 3, 9, 3, 5, 5, 3, 7 },
    new int[] { 9, 8, 7, 5, 9, 7 },
    new int[] { 5, 8, 4, 5, 10, 8, 10, 11, 8 },
    new int[] { 5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0 },
    new int[] { 0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5 },
    new int[] { 10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4 },
    new int[] { 2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8 },
    new int[] { 0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11 },
    new int[] { 0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5 },
    new int[] { 9, 4, 5, 2, 11, 3 },
    new int[] { 2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4 },
    new int[] { 5, 10, 2, 5, 2, 4, 4, 2, 0 },
    new int[] { 3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9 },
    new int[] { 5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2 },
    new int[] { 8, 4, 5, 8, 5, 3, 3, 5, 1 },
    new int[] { 0, 4, 5, 1, 0, 5 },
    new int[] { 8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5 },
    new int[] { 9, 4, 5 },
    new int[] { 4, 11, 7, 4, 9, 11, 9, 10, 11 },
    new int[] { 0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11 },
    new int[] { 1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11 },
    new int[] { 3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4 },
    new int[] { 4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2 },
    new int[] { 9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3 },
    new int[] { 11, 7, 4, 11, 4, 2, 2, 4, 0 },
    new int[] { 11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4 },
    new int[] { 2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9 },
    new int[] { 9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7 },
    new int[] { 3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10 },
    new int[] { 1, 10, 2, 8, 7, 4 },
    new int[] { 4, 9, 1, 4, 1, 7, 7, 1, 3 },
    new int[] { 4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1 },
    new int[] { 4, 0, 3, 7, 4, 3 },
    new int[] { 4, 8, 7 },
    new int[] { 9, 10, 8, 10, 11, 8 },
    new int[] { 3, 0, 9, 3, 9, 11, 11, 9, 10 },
    new int[] { 0, 1, 10, 0, 10, 8, 8, 10, 11 },
    new int[] { 3, 1, 10, 11, 3, 10 },
    new int[] { 1, 2, 11, 1, 11, 9, 9, 11, 8 },
    new int[] { 3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9 },
    new int[] { 0, 2, 11, 8, 0, 11 },
    new int[] { 3, 2, 11 },
    new int[] { 2, 3, 8, 2, 8, 10, 10, 8, 9 },
    new int[] { 9, 10, 2, 0, 9, 2 },
    new int[] { 2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8 },
    new int[] { 1, 10, 2 },
    new int[] { 1, 3, 8, 9, 1, 8 },
    new int[] { 0, 9, 1 },
    new int[] { 0, 3, 8 },
    new int[] { },
};
```

</details>

## 結果

実装したプログラムを処理時間と頂点数、三角面数で比較します。処理時間はUnityEditor上でプログラムを10回実行したときの中央値です。

### ケース1

ボクセルデータのサイズを$32 \times 32 \times 32$、値を$x^2 + y^2 + z^2 − 15^2$としたとき

|処理時間|頂点数|三角面数|
|-|-|-|
|3.2ms|25k|8,360|

### ケース2

ボクセルデータのサイズを$16 \times 16 \times 16$、値を$-1 \le x \le 1$の範囲の乱数としたとき
(サイズ$32 \times 32 \times 32$の場合、頂点数がUInt16の範囲を超えます)

|処理時間|頂点数|三角面数|
|-|-|-|
|2.7ms|31k|10k|

### ケース3

ボクセルデータのサイズを$16 \times 16 \times 16$、値を$x + y + z$が$2$の倍数の場合$1$、そうでない場合$-1$としたとき
(サイズ$32 \times 32 \times 32$の場合、頂点数がUInt16の範囲を超えます)

|処理時間|頂点数|三角面数|
|-|-|-|
|3.3ms|40k|13k|

# 参考

https://ja.wikipedia.org/wiki/マーチングキューブ法

http://paulbourke.net/geometry/polygonise/