Marching Cubes Edge/Triangle LUT Generator

MarchingCubesCaseGen.js

// Marching Cubes Edge/Triangle LUT Generator

// From Transvoxel paper http://transvoxel.org/Lengyel-VoxelTerrain.pdf
// We have ambiguous case when a cube has an ambiguous face
// An ambiguous face has two diagonally opposing corners that are inside and the other two are outside
// This can be tesellated two different ways and when you place this face up against another cube, can introduce holes
// In Lengyel's paper, his ambiguous cases are 2, 6, 7, 8,  9, and 10.
// These map to cases                          3, 7, 8, 12, 10 and 13
// Key observation is that in MC ambiguous cases always arise due to the inclusion of the inverses

const mmc = 1

const EdgeVertexIndexTable = [
    [ 0, 1 ],
    [ 1, 3 ],
    [ 3, 2 ],
    [ 2, 0 ],
    [ 4, 5 ],
    [ 5, 7 ],
    [ 7, 6 ],
    [ 6, 4 ],
    [ 0, 4 ],
    [ 1, 5 ],
    [ 3, 7 ],
    [ 2, 6 ],
];

const Cases = [];

function AddCase(code, triangles, invert)
{
    if (invert)
    {
        code = 255 - code;
        triangles = triangles.map(triangle => triangle.reverse());
    }

    // Prioritise rotations over inversions, which have the potential to introduce ambiguous tesellations
    // Inversions of cases 10, 12 and 13 have potentially ambiguous faces but those can be achieved exclusively through rotation
    // So this check also ignores those cases
    if (!invert || Cases[code] == undefined)
    {
        Cases[code] = triangles;
    }
}

// Compose rotations, not mirrors, so that winding order is retained
const RotateX = [ 4, 5, 0, 1, 6, 7, 2, 3];
const RotateY = [ 4, 0, 6, 2, 5, 1, 7, 3 ];

// Minimal sequence of rotations required to cover all possible units of 90 degree rotations of the cube (24)
// Some of these rotations map to other cubes with their vertex states inverted, so will initially generate more than 128 unique cases
// https://www.euclideanspace.com/maths/discrete/groups/categorise/finite/cube/index.htm
const X = RotateX;
const Y = RotateY;
const RotationPermutations = [
    [ null ],
    [ X ],
    [ Y ],
    [ X, X ],
    [ X, Y ],
    [ Y, X ],
    [ Y, Y ],
    [ X, X, X ],
    [ X, X, Y ],
    [ X, Y, X ],
    [ X, Y, Y ],
    [ Y, X, X ],
    [ Y, Y, X ],
    [ Y, Y, Y ],
    [ X, X, X, Y ],
    [ X, X, Y, X ],
    [ X, X, Y, Y ],
    [ X, Y, X, X ],
    [ X, Y, Y, Y ],
    [ Y, X, X, X ],
    [ Y, Y, Y, X ],
    [ X, X, X, Y, X ],
    [ X, Y, X, X, X ],
    [ X, Y, Y, Y, X ],
];

console.log("---");

function GetPermutedVertexIndices(rotation_index)
{
    let pm_vertex_indices = [ 0, 1, 2, 3, 4, 5, 6, 7 ];
    
    // Execute all rotations in order for this permutation
    const rotations = RotationPermutations[rotation_index % RotationPermutations.length];
    for (let rotation of rotations)
    {
        if (rotation)
        {
            pm_vertex_indices = pm_vertex_indices.map(i => rotation[i]);
        }
    }
    
    return pm_vertex_indices;
}

function GetRemappedVertexMasks(vertex_indices)
{
    // Remap vertices for this permutation and calculate their mask for code construction
    const m0 = 1 << vertex_indices[0];
    const m1 = 1 << vertex_indices[1];
    const m2 = 1 << vertex_indices[2];
    const m3 = 1 << vertex_indices[3];
    const m4 = 1 << vertex_indices[4];
    const m5 = 1 << vertex_indices[5];
    const m6 = 1 << vertex_indices[6];
    const m7 = 1 << vertex_indices[7];
    
    return [m0, m1, m2, m3, m4, m5, m6, m7];
}

function RemapEdge(edge_index, vertex_indices)
{
    // What are the vertices of the old edge?
    const old_edge = EdgeVertexIndexTable[edge_index];
    const old_v0 = old_edge[0];
    const old_v1 = old_edge[1];

    // What are the indices of the new edge?
    const new_v0 = vertex_indices[old_v0];
    const new_v1 = vertex_indices[old_v1];

    // Find an edge defined by these two new indices
    for (let i = 0; i < 12; i++)
    {
        const edge = EdgeVertexIndexTable[i];
        if ((edge[0] == new_v0 && edge[1] == new_v1) || (edge[0] == new_v1 && edge[1] == new_v0))
        {
            return i;
        }
    }

    console.log("FAILED!");
    return edge_index;
}

function GetRemappedEdges(vertex_indices)
{
    // Remap edges for this permutation
    const e0 = RemapEdge(0, vertex_indices);
    const e1 = RemapEdge(1, vertex_indices);
    const e2 = RemapEdge(2, vertex_indices);
    const e3 = RemapEdge(3, vertex_indices);
    const e4 = RemapEdge(4, vertex_indices);
    const e5 = RemapEdge(5, vertex_indices);
    const e6 = RemapEdge(6, vertex_indices);
    const e7 = RemapEdge(7, vertex_indices);
    const e8 = RemapEdge(8, vertex_indices);
    const e9 = RemapEdge(9, vertex_indices);
    const e10 = RemapEdge(10, vertex_indices);
    const e11 = RemapEdge(11, vertex_indices);
    
    return [e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11];
}
    
// Do two passes through the rotation permutations, where the last pass inverts in/out state of vertices
for (let i = 0; i < RotationPermutations.length * 2; i++)
{
    const pm_vertex_indices = GetPermutedVertexIndices(i);
    const [m0, m1, m2, m3, m4, m5, m6, m7] = GetRemappedVertexMasks(pm_vertex_indices);
    const [e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11] = GetRemappedEdges(pm_vertex_indices);
    
    const invert = i >= RotationPermutations.length;
    AddCase(0, [], invert);
    AddCase(m0, [ [ e0, e3, e8 ] ], invert);
    AddCase(m0 | m1, [ [ e3, e8, e1 ], [ e1, e8, e9] ], invert);
    AddCase(m0 | m3, [ [ e0, e3, e8 ], [ e2, e1, e10 ] ], invert);
    AddCase(m0 | m7, [ [ e0, e3, e8 ], [ e6, e10, e5 ] ], invert);
    AddCase(m1 | m4 | m5, [ [ e7, e0, e8 ], [ e7, e1, e0 ], [ e7, e5, e1 ] ], invert);
    AddCase(m0 | m1 | m7, [ [ e3, e8, e1 ], [ e1, e8, e9 ], [ e6, e10, e5 ] ], invert);
    AddCase(m1 | m2 | m7, [ [ e1, e0, e9 ], [ e2, e11, e3 ], [ e6, e10, e5 ] ], invert);
    AddCase(m0 | m1 | m4 | m5, [ [ e7, e5, e3 ], [ e3, e5, e1 ] ], invert);
    AddCase(m0 | m4 | m5 | m6, [ [ e11, e6, e3 ], [ e3, e6, e0 ], [ e0, e6, e5], [ e0, e5, e9 ] ], invert);
    AddCase(m0 | m2 | m5 | m7, [ [ e2, e11, e8 ], [ e2, e8, e0 ], [ e6, e10, e4 ], [ e10, e9, e4 ] ], invert);
    AddCase(m0 | m4 | m5 | m7, [ [ e3, e7, e0 ], [ e7, e6, e10 ], [ e0, e7, e10 ], [ e0, e10, e9 ] ], invert);
    AddCase(m1 | m2 | m4 | m5, [ [ e2, e11, e3 ], [ e7, e0, e8 ], [ e7, e1, e0 ], [ e7, e5, e1 ] ], invert);
    AddCase(m0 | m3 | m5 | m6, [ [ e0, e3, e8 ], [ e4, e5, e9 ], [ e11, e6, e7 ], [ e10, e2, e1 ] ], invert);
    AddCase(m1 | m4 | m5 | m6, [ [ e11, e6, e5 ], [ e11, e5, e0 ], [ e5, e1, e0 ], [ e8, e11, e0 ] ], invert);	
}

if (mmc)
{
    // Only process the rotation permutations
    for (let i = 0; i < RotationPermutations.length; i++)
    {
        const pm_vertex_indices = GetPermutedVertexIndices(i);
        const [m0, m1, m2, m3, m4, m5, m6, m7] = GetRemappedVertexMasks(pm_vertex_indices);
        const [e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11] = GetRemappedEdges(pm_vertex_indices);
        
        AddCase(m0 | m2 | m3 | m4 | m5 | m6, [ [ e1, e10, e0 ], [ e0, e10, e6 ], [ e0, e6, e5 ], [ e0, e5, e9 ] ], false);
        AddCase(m0 | m2 | m3 | m4 | m5, [ [ e1, e10, e0 ], [ e0, e10, e11 ], [ e0, e11, e7 ], [ e0, e7, e5 ], [ e0, e5, e9 ] ], false);
        AddCase(m0 | m3 | m4 | m5 | m6, [ [ e10, e2, e1 ], [ e0, e3, e11 ], [ e0, e11, e6 ], [ e0, e6, e9 ], [ e9, e6, e5 ] ], false);
    }
}

let count = Cases.reduce(x => x + 1, 0);;
console.log("Case Count:", count);
console.log(Cases);

const print = true;
if (print)
{
    let edge_mask_str = "const EdgeMasks = [\n";
    for (let i = 0; i < count / 8; i++)
    {
        edge_mask_str += "\t";

        for (let j = 0; j < 8; j++)
        {
            const triangles = Cases[i * 8 + j];

            // Construct mask from all edges of all triangles in this case
            let edge_mask = 0;
            for (let triangle of triangles)
            {
                edge_mask |= (1 << triangle[0]);
                edge_mask |= (1 << triangle[1]);
                edge_mask |= (1 << triangle[2]);
            }

            edge_mask_str += "0x" + edge_mask.toString(16) + ", ";
        }

        edge_mask_str += "\n";
    }
    edge_mask_str += "];\n";
    console.log(edge_mask_str);

    let triangle_list_str = "const TriangleLists = [\n";
    for (let i = 0; i < count; i++)
    {
        triangle_list_str += "\t[ ";

        const triangles = Cases[i];

        for (let j = 0; j < triangles.length; j++)
        {
            const triangle = triangles[j];
            triangle_list_str += triangle[0] + ", "  + triangle[1] + ", " + triangle[2] + ", ";
        }

        triangle_list_str += "-1 ],\n";
    }
    triangle_list_str += "];\n";
    console.log(triangle_list_str);
}