16724994103

Committed 04 Aug 2025 01:47PM UTC coverage: 74.615% (+0.02%) from 74.593%

Build # 16724994103

Build Type

push

github

Committed by

Razakhel

Commit Message

[Data/MarchingCubes] Parallelized the marching cubes implementation

- For a 512x512x512 grid created from 3D Perlin noise, this speeds up the marching cubes algorithm by ~20%

Run Details

32 of 33 new or added lines in 1 file covered. (96.97%)

4 existing lines in 2 files now uncovered.

8327 of 11160 relevant lines covered (74.61%)

1750.91 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.56

/src/RaZ/Data/MarchingCubes.cpp

#include "RaZ/Data/Grid3.hpp"
#include "RaZ/Data/MarchingCubes.hpp"
#include "RaZ/Data/Mesh.hpp"
#include "RaZ/Utils/Threading.hpp"

#include "tracy/Tracy.hpp"

#include <numeric>

namespace Raz {

namespace {

// TODO: the middle & back points should have a negative Z coordinate, but follows the configuration used for now
constexpr std::array<Vec3f, 12> edgeVertices = {
  Vec3f(0.5f, 0.f,  0.f),  // Bottom front
  Vec3f(1.f,  0.5f, 0.f),  // Right front
  Vec3f(0.5f, 1.f,  0.f),  // Top front
  Vec3f(0.f,  0.5f, 0.f),  // Left front
  Vec3f(0.f,  0.f,  0.5f), // Bottom left
  Vec3f(1.f,  0.f,  0.5f), // Bottom right
  Vec3f(1.f,  1.f,  0.5f), // Top right
  Vec3f(0.f,  1.f,  0.5f), // Top left
  Vec3f(0.5f, 0.f,  1.f),  // Bottom back
  Vec3f(1.f,  0.5f, 1.f),  // Right back
  Vec3f(0.5f, 1.f,  1.f),  // Top back
  Vec3f(0.f,  0.5f, 1.f)   // Left back
};

enum VertexPosition {
  NONE         = -1,
  BOTTOM_FRONT = 0,
  RIGHT_FRONT  = 1,
  TOP_FRONT    = 2,
  LEFT_FRONT   = 3,
  BOTTOM_LEFT  = 4,
  BOTTOM_RIGHT = 5,
  TOP_RIGHT    = 6,
  TOP_LEFT     = 7,
  BOTTOM_BACK  = 8,
  RIGHT_BACK   = 9,
  TOP_BACK     = 10,
  LEFT_BACK    = 11
};

// Table adapted from https://paulbourke.net/geometry/polygonise/
constexpr std::array<std::array<int8_t, 15>, 256> trianglesIndices = {{
  { NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, LEFT_BACK, BOTTOM_LEFT, RIGHT_BACK, LEFT_BACK, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, BOTTOM_FRONT, RIGHT_FRONT, BOTTOM_BACK, BOTTOM_FRONT, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, LEFT_BACK, BOTTOM_LEFT, BOTTOM_FRONT, RIGHT_FRONT, LEFT_BACK, RIGHT_FRONT, RIGHT_BACK, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, LEFT_FRONT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_FRONT, BOTTOM_FRONT, LEFT_BACK, LEFT_FRONT, BOTTOM_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, RIGHT_BACK, BOTTOM_BACK, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, LEFT_FRONT, BOTTOM_FRONT, BOTTOM_RIGHT, RIGHT_BACK, LEFT_FRONT, RIGHT_BACK, LEFT_BACK, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, RIGHT_FRONT, BOTTOM_RIGHT, LEFT_FRONT, RIGHT_FRONT, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_BACK, LEFT_BACK, RIGHT_FRONT, LEFT_BACK, LEFT_FRONT, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, RIGHT_BACK, BOTTOM_BACK, BOTTOM_LEFT, LEFT_FRONT, RIGHT_BACK, LEFT_FRONT, RIGHT_FRONT, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, LEFT_BACK, RIGHT_FRONT, RIGHT_FRONT, LEFT_BACK, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, TOP_LEFT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, BOTTOM_LEFT, BOTTOM_BACK, TOP_LEFT, BOTTOM_LEFT, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_BACK, LEFT_BACK, TOP_BACK, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, BOTTOM_RIGHT, RIGHT_BACK, TOP_BACK, TOP_LEFT, BOTTOM_RIGHT, TOP_LEFT, BOTTOM_LEFT, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, LEFT_BACK, TOP_BACK, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, TOP_BACK, TOP_LEFT, BOTTOM_LEFT, BOTTOM_BACK, TOP_BACK, BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, BOTTOM_FRONT, RIGHT_FRONT, RIGHT_BACK, BOTTOM_BACK, BOTTOM_FRONT, LEFT_BACK, TOP_BACK, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, RIGHT_FRONT, RIGHT_BACK, BOTTOM_FRONT, RIGHT_BACK, TOP_LEFT, BOTTOM_FRONT, TOP_LEFT, BOTTOM_LEFT, TOP_LEFT, RIGHT_BACK, TOP_BACK, NONE, NONE, NONE },
  { LEFT_BACK, TOP_BACK, TOP_LEFT, BOTTOM_LEFT, LEFT_FRONT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_FRONT, TOP_BACK, TOP_LEFT, LEFT_FRONT, BOTTOM_FRONT, TOP_BACK, BOTTOM_FRONT, BOTTOM_BACK, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, BOTTOM_BACK, BOTTOM_RIGHT, LEFT_BACK, TOP_BACK, TOP_LEFT, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, TOP_LEFT, LEFT_FRONT, RIGHT_BACK, TOP_BACK, LEFT_FRONT, RIGHT_BACK, LEFT_FRONT, BOTTOM_FRONT, RIGHT_BACK, BOTTOM_FRONT, BOTTOM_RIGHT, NONE, NONE, NONE },
  { BOTTOM_LEFT, RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_LEFT, LEFT_FRONT, RIGHT_FRONT, TOP_LEFT, LEFT_BACK, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, LEFT_FRONT, RIGHT_FRONT, BOTTOM_RIGHT, TOP_BACK, LEFT_FRONT, BOTTOM_RIGHT, BOTTOM_BACK, TOP_BACK, TOP_LEFT, LEFT_FRONT, TOP_BACK, NONE, NONE, NONE },
  { TOP_BACK, TOP_LEFT, LEFT_BACK, RIGHT_BACK, BOTTOM_BACK, LEFT_FRONT, RIGHT_BACK, LEFT_FRONT, RIGHT_FRONT, LEFT_FRONT, BOTTOM_BACK, BOTTOM_LEFT, NONE, NONE, NONE },
  { TOP_BACK, TOP_LEFT, LEFT_FRONT, TOP_BACK, LEFT_FRONT, RIGHT_BACK, RIGHT_BACK, LEFT_FRONT, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_RIGHT, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_RIGHT, TOP_BACK, BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, TOP_RIGHT, TOP_BACK, BOTTOM_RIGHT, TOP_RIGHT, BOTTOM_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_BACK, TOP_RIGHT, TOP_BACK, LEFT_BACK, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_RIGHT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, RIGHT_BACK, TOP_RIGHT, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, BOTTOM_BACK, LEFT_BACK, BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, TOP_BACK, RIGHT_BACK, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, TOP_RIGHT, TOP_BACK, BOTTOM_FRONT, TOP_BACK, BOTTOM_BACK, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, RIGHT_FRONT, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_FRONT, TOP_RIGHT, BOTTOM_LEFT, TOP_RIGHT, TOP_BACK, BOTTOM_LEFT, TOP_BACK, LEFT_BACK, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_RIGHT, TOP_BACK, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_FRONT, BOTTOM_FRONT, BOTTOM_BACK, LEFT_BACK, LEFT_FRONT, TOP_BACK, RIGHT_BACK, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, TOP_RIGHT, TOP_BACK, BOTTOM_BACK, BOTTOM_RIGHT, TOP_RIGHT, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, BOTTOM_RIGHT, TOP_RIGHT, BOTTOM_FRONT, TOP_RIGHT, LEFT_BACK, BOTTOM_FRONT, LEFT_BACK, LEFT_FRONT, TOP_BACK, LEFT_BACK, TOP_RIGHT, NONE, NONE, NONE },
  { RIGHT_FRONT, BOTTOM_LEFT, LEFT_FRONT, RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_LEFT, RIGHT_BACK, TOP_RIGHT, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, RIGHT_BACK, TOP_RIGHT, BOTTOM_BACK, LEFT_BACK, BOTTOM_RIGHT, LEFT_BACK, RIGHT_FRONT, BOTTOM_RIGHT, LEFT_BACK, LEFT_FRONT, RIGHT_FRONT, NONE, NONE, NONE },
  { TOP_RIGHT, TOP_BACK, BOTTOM_BACK, TOP_RIGHT, BOTTOM_BACK, LEFT_FRONT, TOP_RIGHT, LEFT_FRONT, RIGHT_FRONT, LEFT_FRONT, BOTTOM_BACK, BOTTOM_LEFT, NONE, NONE, NONE },
  { TOP_RIGHT, TOP_BACK, LEFT_BACK, TOP_RIGHT, LEFT_BACK, RIGHT_FRONT, RIGHT_FRONT, LEFT_BACK, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_LEFT, LEFT_BACK, TOP_RIGHT, TOP_LEFT, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, BOTTOM_LEFT, BOTTOM_BACK, RIGHT_BACK, TOP_RIGHT, BOTTOM_LEFT, TOP_RIGHT, TOP_LEFT, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, TOP_LEFT, LEFT_BACK, BOTTOM_BACK, BOTTOM_RIGHT, TOP_LEFT, BOTTOM_RIGHT, TOP_RIGHT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_LEFT, TOP_RIGHT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_LEFT, LEFT_BACK, RIGHT_BACK, TOP_RIGHT, TOP_LEFT, RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_BACK, TOP_RIGHT, BOTTOM_BACK, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_BACK, TOP_RIGHT, TOP_LEFT, BOTTOM_LEFT, NONE, NONE, NONE },
  { LEFT_BACK, BOTTOM_BACK, BOTTOM_FRONT, LEFT_BACK, BOTTOM_FRONT, TOP_RIGHT, LEFT_BACK, TOP_RIGHT, TOP_LEFT, RIGHT_FRONT, TOP_RIGHT, BOTTOM_FRONT, NONE, NONE, NONE },
  { BOTTOM_FRONT, RIGHT_FRONT, TOP_RIGHT, BOTTOM_FRONT, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_LEFT, TOP_RIGHT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_LEFT, RIGHT_BACK, TOP_RIGHT, TOP_LEFT, LEFT_BACK, RIGHT_BACK, BOTTOM_LEFT, LEFT_FRONT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_RIGHT, TOP_LEFT, RIGHT_BACK, TOP_LEFT, BOTTOM_FRONT, RIGHT_BACK, BOTTOM_FRONT, BOTTOM_BACK, BOTTOM_FRONT, TOP_LEFT, LEFT_FRONT, NONE, NONE, NONE },
  { BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, BOTTOM_BACK, BOTTOM_RIGHT, LEFT_BACK, BOTTOM_RIGHT, TOP_LEFT, LEFT_BACK, BOTTOM_RIGHT, TOP_RIGHT, TOP_LEFT, NONE, NONE, NONE },
  { LEFT_FRONT, BOTTOM_FRONT, BOTTOM_RIGHT, LEFT_FRONT, BOTTOM_RIGHT, TOP_LEFT, TOP_LEFT, BOTTOM_RIGHT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_RIGHT, LEFT_BACK, LEFT_BACK, TOP_RIGHT, TOP_LEFT, RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_LEFT, RIGHT_FRONT, BOTTOM_LEFT, LEFT_FRONT, NONE, NONE, NONE },
  { TOP_RIGHT, TOP_LEFT, BOTTOM_BACK, TOP_RIGHT, BOTTOM_BACK, RIGHT_BACK, TOP_LEFT, LEFT_FRONT, BOTTOM_BACK, BOTTOM_RIGHT, BOTTOM_BACK, RIGHT_FRONT, LEFT_FRONT, RIGHT_FRONT, BOTTOM_BACK },
  { LEFT_FRONT, RIGHT_FRONT, BOTTOM_BACK, LEFT_FRONT, BOTTOM_BACK, BOTTOM_LEFT, RIGHT_FRONT, TOP_RIGHT, BOTTOM_BACK, LEFT_BACK, BOTTOM_BACK, TOP_LEFT, TOP_RIGHT, TOP_LEFT, BOTTOM_BACK },
  { LEFT_FRONT, RIGHT_FRONT, TOP_RIGHT, TOP_LEFT, LEFT_FRONT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_FRONT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, BOTTOM_BACK, BOTTOM_RIGHT, TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, LEFT_BACK, BOTTOM_LEFT, BOTTOM_RIGHT, RIGHT_BACK, LEFT_BACK, TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, TOP_FRONT, TOP_RIGHT, BOTTOM_FRONT, TOP_FRONT, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, TOP_FRONT, TOP_RIGHT, BOTTOM_RIGHT, BOTTOM_FRONT, TOP_FRONT, BOTTOM_LEFT, BOTTOM_BACK, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_FRONT, TOP_RIGHT, RIGHT_BACK, BOTTOM_BACK, TOP_FRONT, BOTTOM_BACK, BOTTOM_FRONT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, RIGHT_BACK, LEFT_BACK, TOP_RIGHT, LEFT_BACK, BOTTOM_FRONT, TOP_RIGHT, BOTTOM_FRONT, TOP_FRONT, BOTTOM_LEFT, BOTTOM_FRONT, LEFT_BACK, NONE, NONE, NONE },
  { BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, RIGHT_FRONT, TOP_FRONT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_FRONT, BOTTOM_BACK, LEFT_BACK, LEFT_FRONT, BOTTOM_FRONT, BOTTOM_BACK, RIGHT_FRONT, TOP_FRONT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_BACK, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, BOTTOM_RIGHT, RIGHT_BACK, BOTTOM_FRONT, RIGHT_BACK, LEFT_FRONT, BOTTOM_FRONT, RIGHT_BACK, LEFT_BACK, LEFT_FRONT, NONE, NONE, NONE },
  { TOP_FRONT, BOTTOM_LEFT, LEFT_FRONT, TOP_FRONT, TOP_RIGHT, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_RIGHT, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, LEFT_FRONT, BOTTOM_BACK, LEFT_FRONT, TOP_RIGHT, BOTTOM_BACK, TOP_RIGHT, BOTTOM_RIGHT, TOP_RIGHT, LEFT_FRONT, TOP_FRONT, NONE, NONE, NONE },
  { BOTTOM_LEFT, LEFT_FRONT, TOP_FRONT, BOTTOM_BACK, BOTTOM_LEFT, TOP_FRONT, BOTTOM_BACK, TOP_FRONT, TOP_RIGHT, BOTTOM_BACK, TOP_RIGHT, RIGHT_BACK, NONE, NONE, NONE },
  { TOP_FRONT, TOP_RIGHT, RIGHT_BACK, TOP_FRONT, RIGHT_BACK, LEFT_FRONT, LEFT_FRONT, RIGHT_BACK, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, TOP_BACK, TOP_LEFT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, BOTTOM_LEFT, BOTTOM_BACK, TOP_BACK, TOP_LEFT, BOTTOM_LEFT, TOP_FRONT, TOP_RIGHT, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, RIGHT_BACK, BOTTOM_BACK, TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, LEFT_BACK, TOP_BACK, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_FRONT, TOP_RIGHT, BOTTOM_RIGHT, RIGHT_BACK, TOP_LEFT, BOTTOM_RIGHT, TOP_LEFT, BOTTOM_LEFT, TOP_LEFT, RIGHT_BACK, TOP_BACK, NONE, NONE, NONE },
  { TOP_FRONT, BOTTOM_RIGHT, BOTTOM_FRONT, TOP_FRONT, TOP_RIGHT, BOTTOM_RIGHT, TOP_BACK, TOP_LEFT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, TOP_RIGHT, TOP_RIGHT, BOTTOM_FRONT, TOP_FRONT, BOTTOM_LEFT, BOTTOM_BACK, TOP_BACK, BOTTOM_LEFT, TOP_BACK, TOP_LEFT, NONE, NONE, NONE },
  { LEFT_BACK, TOP_BACK, TOP_LEFT, RIGHT_BACK, BOTTOM_BACK, TOP_RIGHT, BOTTOM_BACK, TOP_FRONT, TOP_RIGHT, BOTTOM_BACK, BOTTOM_FRONT, TOP_FRONT, NONE, NONE, NONE },
  { TOP_LEFT, BOTTOM_LEFT, RIGHT_BACK, TOP_LEFT, RIGHT_BACK, TOP_BACK, BOTTOM_LEFT, BOTTOM_FRONT, RIGHT_BACK, TOP_RIGHT, RIGHT_BACK, TOP_FRONT, BOTTOM_FRONT, TOP_FRONT, RIGHT_BACK },
  { BOTTOM_LEFT, LEFT_FRONT, BOTTOM_FRONT, TOP_LEFT, LEFT_BACK, TOP_BACK, RIGHT_FRONT, TOP_FRONT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, TOP_BACK, TOP_LEFT, BOTTOM_FRONT, TOP_BACK, BOTTOM_FRONT, BOTTOM_BACK, BOTTOM_FRONT, TOP_LEFT, LEFT_FRONT, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_BACK, TOP_BACK, TOP_LEFT, LEFT_BACK, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, TOP_RIGHT, RIGHT_FRONT, TOP_FRONT, NONE, NONE, NONE },
  { RIGHT_BACK, BOTTOM_FRONT, BOTTOM_RIGHT, RIGHT_BACK, LEFT_FRONT, BOTTOM_FRONT, RIGHT_BACK, TOP_BACK, LEFT_FRONT, TOP_LEFT, LEFT_FRONT, TOP_BACK, TOP_RIGHT, RIGHT_FRONT, TOP_FRONT },
  { LEFT_BACK, TOP_BACK, TOP_LEFT, BOTTOM_LEFT, LEFT_FRONT, TOP_RIGHT, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_RIGHT, TOP_RIGHT, LEFT_FRONT, TOP_FRONT, NONE, NONE, NONE },
  { TOP_RIGHT, BOTTOM_RIGHT, LEFT_FRONT, TOP_RIGHT, LEFT_FRONT, TOP_FRONT, BOTTOM_RIGHT, BOTTOM_BACK, LEFT_FRONT, TOP_LEFT, LEFT_FRONT, TOP_BACK, BOTTOM_BACK, TOP_BACK, LEFT_FRONT },
  { BOTTOM_BACK, TOP_RIGHT, RIGHT_BACK, BOTTOM_BACK, TOP_FRONT, TOP_RIGHT, BOTTOM_BACK, BOTTOM_LEFT, TOP_FRONT, LEFT_FRONT, TOP_FRONT, BOTTOM_LEFT, LEFT_BACK, TOP_BACK, TOP_LEFT },
  { TOP_FRONT, TOP_RIGHT, RIGHT_BACK, TOP_FRONT, RIGHT_BACK, LEFT_FRONT, TOP_BACK, TOP_LEFT, RIGHT_BACK, TOP_LEFT, LEFT_FRONT, RIGHT_BACK, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_BACK, RIGHT_BACK, TOP_FRONT, TOP_BACK, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, RIGHT_FRONT, TOP_FRONT, TOP_BACK, RIGHT_BACK, RIGHT_FRONT, BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_FRONT, TOP_FRONT, BOTTOM_BACK, TOP_FRONT, TOP_BACK, BOTTOM_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_BACK, BOTTOM_LEFT, BOTTOM_RIGHT, LEFT_BACK, BOTTOM_RIGHT, TOP_FRONT, LEFT_BACK, TOP_FRONT, TOP_BACK, TOP_FRONT, BOTTOM_RIGHT, RIGHT_FRONT, NONE, NONE, NONE },
  { BOTTOM_RIGHT, TOP_BACK, RIGHT_BACK, BOTTOM_RIGHT, BOTTOM_FRONT, TOP_BACK, BOTTOM_FRONT, TOP_FRONT, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, BOTTOM_BACK, LEFT_BACK, BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_BACK, BOTTOM_FRONT, TOP_BACK, RIGHT_BACK, BOTTOM_FRONT, TOP_FRONT, TOP_BACK, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_FRONT, TOP_BACK, TOP_BACK, BOTTOM_FRONT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_BACK, BOTTOM_LEFT, BOTTOM_FRONT, LEFT_BACK, BOTTOM_FRONT, TOP_BACK, TOP_BACK, BOTTOM_FRONT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_BACK, RIGHT_BACK, RIGHT_FRONT, TOP_FRONT, TOP_BACK, LEFT_FRONT, BOTTOM_FRONT, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, BOTTOM_FRONT, BOTTOM_FRONT, LEFT_BACK, LEFT_FRONT, TOP_BACK, RIGHT_BACK, RIGHT_FRONT, TOP_BACK, RIGHT_FRONT, TOP_FRONT, NONE, NONE, NONE },
  { BOTTOM_LEFT, LEFT_FRONT, BOTTOM_FRONT, BOTTOM_BACK, BOTTOM_RIGHT, TOP_FRONT, BOTTOM_BACK, TOP_FRONT, TOP_BACK, TOP_FRONT, BOTTOM_RIGHT, RIGHT_FRONT, NONE, NONE, NONE },
  { TOP_FRONT, TOP_BACK, BOTTOM_RIGHT, TOP_FRONT, BOTTOM_RIGHT, RIGHT_FRONT, TOP_BACK, LEFT_BACK, BOTTOM_RIGHT, BOTTOM_FRONT, BOTTOM_RIGHT, LEFT_FRONT, LEFT_BACK, LEFT_FRONT, BOTTOM_RIGHT },
  { RIGHT_BACK, TOP_FRONT, TOP_BACK, RIGHT_BACK, BOTTOM_LEFT, TOP_FRONT, RIGHT_BACK, BOTTOM_RIGHT, BOTTOM_LEFT, LEFT_FRONT, TOP_FRONT, BOTTOM_LEFT, NONE, NONE, NONE },
  { LEFT_BACK, LEFT_FRONT, BOTTOM_RIGHT, LEFT_BACK, BOTTOM_RIGHT, BOTTOM_BACK, LEFT_FRONT, TOP_FRONT, BOTTOM_RIGHT, RIGHT_BACK, BOTTOM_RIGHT, TOP_BACK, TOP_FRONT, TOP_BACK, BOTTOM_RIGHT },
  { BOTTOM_LEFT, LEFT_FRONT, TOP_FRONT, BOTTOM_LEFT, TOP_FRONT, BOTTOM_BACK, BOTTOM_BACK, TOP_FRONT, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_FRONT, TOP_BACK, LEFT_BACK, LEFT_FRONT, TOP_FRONT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_LEFT, RIGHT_FRONT, TOP_FRONT, TOP_LEFT, LEFT_BACK, RIGHT_FRONT, LEFT_BACK, RIGHT_BACK, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, TOP_LEFT, BOTTOM_LEFT, BOTTOM_BACK, RIGHT_FRONT, TOP_LEFT, BOTTOM_BACK, RIGHT_BACK, RIGHT_FRONT, TOP_FRONT, TOP_LEFT, RIGHT_FRONT, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_FRONT, TOP_LEFT, BOTTOM_RIGHT, RIGHT_FRONT, TOP_LEFT, BOTTOM_RIGHT, TOP_LEFT, LEFT_BACK, BOTTOM_RIGHT, LEFT_BACK, BOTTOM_BACK, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_FRONT, TOP_LEFT, RIGHT_FRONT, TOP_LEFT, BOTTOM_RIGHT, BOTTOM_RIGHT, TOP_LEFT, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, TOP_FRONT, BOTTOM_RIGHT, TOP_FRONT, LEFT_BACK, BOTTOM_RIGHT, LEFT_BACK, RIGHT_BACK, LEFT_BACK, TOP_FRONT, TOP_LEFT, NONE, NONE, NONE },
  { BOTTOM_FRONT, TOP_FRONT, RIGHT_BACK, BOTTOM_FRONT, RIGHT_BACK, BOTTOM_RIGHT, TOP_FRONT, TOP_LEFT, RIGHT_BACK, BOTTOM_BACK, RIGHT_BACK, BOTTOM_LEFT, TOP_LEFT, BOTTOM_LEFT, RIGHT_BACK },
  { TOP_LEFT, LEFT_BACK, BOTTOM_BACK, TOP_LEFT, BOTTOM_BACK, TOP_FRONT, TOP_FRONT, BOTTOM_BACK, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_LEFT, BOTTOM_LEFT, BOTTOM_FRONT, TOP_FRONT, TOP_LEFT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT, RIGHT_FRONT, TOP_FRONT, LEFT_BACK, RIGHT_FRONT, LEFT_BACK, RIGHT_BACK, LEFT_BACK, TOP_FRONT, TOP_LEFT, NONE, NONE, NONE },
  { BOTTOM_FRONT, BOTTOM_BACK, TOP_LEFT, BOTTOM_FRONT, TOP_LEFT, LEFT_FRONT, BOTTOM_BACK, RIGHT_BACK, TOP_LEFT, TOP_FRONT, TOP_LEFT, RIGHT_FRONT, RIGHT_BACK, RIGHT_FRONT, TOP_LEFT },
  { BOTTOM_RIGHT, LEFT_BACK, BOTTOM_BACK, BOTTOM_RIGHT, TOP_LEFT, LEFT_BACK, BOTTOM_RIGHT, RIGHT_FRONT, TOP_LEFT, TOP_FRONT, TOP_LEFT, RIGHT_FRONT, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_FRONT },
  { LEFT_FRONT, BOTTOM_FRONT, BOTTOM_RIGHT, LEFT_FRONT, BOTTOM_RIGHT, TOP_LEFT, RIGHT_FRONT, TOP_FRONT, BOTTOM_RIGHT, TOP_FRONT, TOP_LEFT, BOTTOM_RIGHT, NONE, NONE, NONE },
  { LEFT_BACK, RIGHT_BACK, TOP_FRONT, LEFT_BACK, TOP_FRONT, TOP_LEFT, RIGHT_BACK, BOTTOM_RIGHT, TOP_FRONT, LEFT_FRONT, TOP_FRONT, BOTTOM_LEFT, BOTTOM_RIGHT, BOTTOM_LEFT, TOP_FRONT },
  { BOTTOM_BACK, RIGHT_BACK, BOTTOM_RIGHT, LEFT_FRONT, TOP_FRONT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_LEFT, LEFT_BACK, BOTTOM_BACK, TOP_LEFT, BOTTOM_BACK, TOP_FRONT, BOTTOM_LEFT, LEFT_FRONT, BOTTOM_BACK, LEFT_FRONT, TOP_FRONT, BOTTOM_BACK, NONE, NONE, NONE },
  { TOP_LEFT, LEFT_FRONT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_LEFT, TOP_FRONT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, BOTTOM_BACK, LEFT_BACK, LEFT_FRONT, TOP_LEFT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_BACK, LEFT_FRONT, TOP_LEFT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_BACK, BOTTOM_RIGHT, RIGHT_BACK, LEFT_BACK, BOTTOM_LEFT, BOTTOM_RIGHT, LEFT_FRONT, TOP_LEFT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_FRONT, TOP_FRONT, LEFT_FRONT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, BOTTOM_LEFT, BOTTOM_BACK, LEFT_BACK, TOP_FRONT, LEFT_FRONT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, RIGHT_BACK, BOTTOM_BACK, BOTTOM_FRONT, RIGHT_FRONT, RIGHT_BACK, TOP_FRONT, LEFT_FRONT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_FRONT, LEFT_FRONT, TOP_LEFT, BOTTOM_FRONT, RIGHT_FRONT, BOTTOM_LEFT, RIGHT_FRONT, LEFT_BACK, BOTTOM_LEFT, RIGHT_FRONT, RIGHT_BACK, LEFT_BACK, NONE, NONE, NONE },
  { TOP_LEFT, BOTTOM_FRONT, BOTTOM_LEFT, TOP_FRONT, BOTTOM_FRONT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_LEFT, BOTTOM_BACK, LEFT_BACK, TOP_LEFT, TOP_FRONT, BOTTOM_BACK, TOP_FRONT, BOTTOM_FRONT, BOTTOM_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, TOP_LEFT, TOP_FRONT, BOTTOM_FRONT, BOTTOM_LEFT, TOP_LEFT, BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, TOP_FRONT, BOTTOM_FRONT, BOTTOM_RIGHT, LEFT_BACK, TOP_FRONT, BOTTOM_RIGHT, RIGHT_BACK, LEFT_BACK, LEFT_BACK, TOP_LEFT, TOP_FRONT, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_LEFT, TOP_FRONT, RIGHT_FRONT, BOTTOM_RIGHT, TOP_LEFT, BOTTOM_RIGHT, BOTTOM_LEFT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_LEFT, TOP_FRONT, BOTTOM_RIGHT, TOP_LEFT, RIGHT_FRONT, BOTTOM_RIGHT, LEFT_BACK, TOP_LEFT, BOTTOM_RIGHT, BOTTOM_BACK, LEFT_BACK, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_LEFT, TOP_LEFT, BOTTOM_BACK, TOP_LEFT, RIGHT_FRONT, BOTTOM_BACK, RIGHT_FRONT, RIGHT_BACK, TOP_FRONT, RIGHT_FRONT, TOP_LEFT, NONE, NONE, NONE },
  { TOP_LEFT, TOP_FRONT, RIGHT_FRONT, TOP_LEFT, RIGHT_FRONT, LEFT_BACK, LEFT_BACK, RIGHT_FRONT, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_FRONT, LEFT_BACK, TOP_BACK, LEFT_FRONT, LEFT_BACK, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, TOP_FRONT, LEFT_FRONT, BOTTOM_LEFT, BOTTOM_BACK, TOP_FRONT, BOTTOM_BACK, TOP_BACK, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_BACK, TOP_FRONT, LEFT_FRONT, LEFT_BACK, TOP_BACK, TOP_FRONT, RIGHT_BACK, BOTTOM_BACK, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_BACK, TOP_FRONT, RIGHT_BACK, TOP_FRONT, BOTTOM_LEFT, RIGHT_BACK, BOTTOM_LEFT, BOTTOM_RIGHT, LEFT_FRONT, BOTTOM_LEFT, TOP_FRONT, NONE, NONE, NONE },
  { TOP_FRONT, LEFT_BACK, TOP_BACK, TOP_FRONT, LEFT_FRONT, LEFT_BACK, BOTTOM_FRONT, RIGHT_FRONT, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, BOTTOM_LEFT, BOTTOM_BACK, LEFT_FRONT, BOTTOM_BACK, TOP_FRONT, LEFT_FRONT, BOTTOM_BACK, TOP_BACK, TOP_FRONT, NONE, NONE, NONE },
  { TOP_BACK, LEFT_FRONT, LEFT_BACK, TOP_BACK, TOP_FRONT, LEFT_FRONT, BOTTOM_BACK, BOTTOM_FRONT, RIGHT_BACK, BOTTOM_FRONT, RIGHT_FRONT, RIGHT_BACK, NONE, NONE, NONE },
  { RIGHT_FRONT, RIGHT_BACK, BOTTOM_LEFT, RIGHT_FRONT, BOTTOM_LEFT, BOTTOM_FRONT, RIGHT_BACK, TOP_BACK, BOTTOM_LEFT, LEFT_FRONT, BOTTOM_LEFT, TOP_FRONT, TOP_BACK, TOP_FRONT, BOTTOM_LEFT },
  { LEFT_BACK, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_BACK, TOP_BACK, BOTTOM_FRONT, TOP_BACK, TOP_FRONT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, TOP_BACK, BOTTOM_FRONT, TOP_BACK, TOP_FRONT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, RIGHT_BACK, BOTTOM_BACK, BOTTOM_FRONT, BOTTOM_LEFT, TOP_BACK, BOTTOM_FRONT, TOP_BACK, TOP_FRONT, TOP_BACK, BOTTOM_LEFT, LEFT_BACK, NONE, NONE, NONE },
  { BOTTOM_RIGHT, RIGHT_BACK, TOP_BACK, BOTTOM_RIGHT, TOP_BACK, BOTTOM_FRONT, BOTTOM_FRONT, TOP_BACK, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_BACK, BOTTOM_RIGHT, BOTTOM_LEFT, LEFT_BACK, TOP_FRONT, BOTTOM_RIGHT, LEFT_BACK, TOP_BACK, TOP_FRONT, TOP_FRONT, RIGHT_FRONT, BOTTOM_RIGHT, NONE, NONE, NONE },
  { RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_BACK, RIGHT_FRONT, BOTTOM_BACK, TOP_FRONT, TOP_FRONT, BOTTOM_BACK, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, TOP_FRONT, BOTTOM_LEFT, TOP_BACK, BOTTOM_LEFT, LEFT_BACK, TOP_FRONT, RIGHT_FRONT, BOTTOM_LEFT, BOTTOM_BACK, BOTTOM_LEFT, RIGHT_BACK, RIGHT_FRONT, RIGHT_BACK, BOTTOM_LEFT },
  { RIGHT_FRONT, RIGHT_BACK, TOP_BACK, TOP_FRONT, RIGHT_FRONT, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, RIGHT_BACK, TOP_RIGHT, TOP_LEFT, TOP_FRONT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, TOP_BACK, RIGHT_BACK, TOP_RIGHT, LEFT_FRONT, TOP_LEFT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, BOTTOM_BACK, BOTTOM_RIGHT, TOP_RIGHT, TOP_BACK, BOTTOM_BACK, TOP_LEFT, TOP_FRONT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_FRONT, TOP_LEFT, TOP_FRONT, LEFT_BACK, BOTTOM_LEFT, TOP_BACK, BOTTOM_LEFT, TOP_RIGHT, TOP_BACK, BOTTOM_LEFT, BOTTOM_RIGHT, TOP_RIGHT, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_RIGHT, TOP_BACK, RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_FRONT, TOP_LEFT, TOP_FRONT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_FRONT, LEFT_FRONT, TOP_LEFT, BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, TOP_BACK, RIGHT_BACK, TOP_RIGHT, NONE, NONE, NONE },
  { TOP_LEFT, TOP_FRONT, LEFT_FRONT, TOP_RIGHT, TOP_BACK, RIGHT_FRONT, TOP_BACK, BOTTOM_FRONT, RIGHT_FRONT, TOP_BACK, BOTTOM_BACK, BOTTOM_FRONT, NONE, NONE, NONE },
  { BOTTOM_LEFT, TOP_BACK, LEFT_BACK, BOTTOM_LEFT, TOP_RIGHT, TOP_BACK, BOTTOM_LEFT, BOTTOM_FRONT, TOP_RIGHT, RIGHT_FRONT, TOP_RIGHT, BOTTOM_FRONT, LEFT_FRONT, TOP_LEFT, TOP_FRONT },
  { TOP_LEFT, BOTTOM_FRONT, BOTTOM_LEFT, TOP_LEFT, TOP_FRONT, BOTTOM_FRONT, TOP_RIGHT, TOP_BACK, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_RIGHT, TOP_BACK, BOTTOM_BACK, LEFT_BACK, TOP_FRONT, BOTTOM_BACK, TOP_FRONT, BOTTOM_FRONT, TOP_FRONT, LEFT_BACK, TOP_LEFT, NONE, NONE, NONE },
  { BOTTOM_LEFT, TOP_FRONT, BOTTOM_FRONT, BOTTOM_LEFT, TOP_LEFT, TOP_FRONT, BOTTOM_RIGHT, TOP_RIGHT, BOTTOM_BACK, TOP_RIGHT, TOP_BACK, BOTTOM_BACK, NONE, NONE, NONE },
  { TOP_FRONT, BOTTOM_FRONT, LEFT_BACK, TOP_FRONT, LEFT_BACK, TOP_LEFT, BOTTOM_FRONT, BOTTOM_RIGHT, LEFT_BACK, TOP_BACK, LEFT_BACK, TOP_RIGHT, BOTTOM_RIGHT, TOP_RIGHT, LEFT_BACK },
  { RIGHT_BACK, TOP_RIGHT, TOP_BACK, RIGHT_FRONT, BOTTOM_RIGHT, TOP_FRONT, BOTTOM_RIGHT, TOP_LEFT, TOP_FRONT, BOTTOM_RIGHT, BOTTOM_LEFT, TOP_LEFT, NONE, NONE, NONE },
  { BOTTOM_RIGHT, TOP_FRONT, RIGHT_FRONT, BOTTOM_RIGHT, TOP_LEFT, TOP_FRONT, BOTTOM_RIGHT, BOTTOM_BACK, TOP_LEFT, LEFT_BACK, TOP_LEFT, BOTTOM_BACK, RIGHT_BACK, TOP_RIGHT, TOP_BACK },
  { TOP_BACK, BOTTOM_BACK, RIGHT_FRONT, TOP_BACK, RIGHT_FRONT, TOP_RIGHT, BOTTOM_BACK, BOTTOM_LEFT, RIGHT_FRONT, TOP_FRONT, RIGHT_FRONT, TOP_LEFT, BOTTOM_LEFT, TOP_LEFT, RIGHT_FRONT },
  { TOP_LEFT, TOP_FRONT, RIGHT_FRONT, TOP_LEFT, RIGHT_FRONT, LEFT_BACK, TOP_RIGHT, TOP_BACK, RIGHT_FRONT, TOP_BACK, LEFT_BACK, RIGHT_FRONT, NONE, NONE, NONE },
  { TOP_FRONT, RIGHT_BACK, TOP_RIGHT, TOP_FRONT, LEFT_FRONT, RIGHT_BACK, LEFT_FRONT, LEFT_BACK, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, TOP_FRONT, LEFT_FRONT, BOTTOM_BACK, TOP_FRONT, BOTTOM_LEFT, BOTTOM_BACK, TOP_RIGHT, TOP_FRONT, BOTTOM_BACK, RIGHT_BACK, TOP_RIGHT, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_FRONT, LEFT_BACK, BOTTOM_BACK, TOP_RIGHT, LEFT_FRONT, BOTTOM_BACK, BOTTOM_RIGHT, TOP_RIGHT, TOP_RIGHT, TOP_FRONT, LEFT_FRONT, NONE, NONE, NONE },
  { TOP_FRONT, LEFT_FRONT, BOTTOM_LEFT, TOP_FRONT, BOTTOM_LEFT, TOP_RIGHT, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, RIGHT_BACK, TOP_RIGHT, LEFT_FRONT, RIGHT_BACK, LEFT_FRONT, LEFT_BACK, LEFT_FRONT, TOP_RIGHT, TOP_FRONT, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_FRONT, BOTTOM_LEFT, BOTTOM_BACK, TOP_FRONT, LEFT_FRONT, BOTTOM_BACK, RIGHT_BACK, TOP_FRONT, TOP_RIGHT, TOP_FRONT, RIGHT_BACK, BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_FRONT },
  { LEFT_FRONT, LEFT_BACK, TOP_RIGHT, LEFT_FRONT, TOP_RIGHT, TOP_FRONT, LEFT_BACK, BOTTOM_BACK, TOP_RIGHT, RIGHT_FRONT, TOP_RIGHT, BOTTOM_FRONT, BOTTOM_BACK, BOTTOM_FRONT, TOP_RIGHT },
  { TOP_FRONT, LEFT_FRONT, BOTTOM_LEFT, TOP_FRONT, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_FRONT, RIGHT_FRONT, BOTTOM_LEFT, RIGHT_FRONT, TOP_RIGHT, BOTTOM_LEFT, NONE, NONE, NONE },
  { TOP_RIGHT, LEFT_BACK, RIGHT_BACK, TOP_RIGHT, BOTTOM_FRONT, LEFT_BACK, TOP_RIGHT, TOP_FRONT, BOTTOM_FRONT, BOTTOM_LEFT, LEFT_BACK, BOTTOM_FRONT, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_RIGHT, TOP_FRONT, RIGHT_BACK, TOP_FRONT, BOTTOM_BACK, BOTTOM_BACK, TOP_FRONT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, TOP_RIGHT, LEFT_BACK, BOTTOM_RIGHT, LEFT_BACK, BOTTOM_BACK, TOP_RIGHT, TOP_FRONT, LEFT_BACK, BOTTOM_LEFT, LEFT_BACK, BOTTOM_FRONT, TOP_FRONT, BOTTOM_FRONT, LEFT_BACK },
  { BOTTOM_RIGHT, TOP_RIGHT, TOP_FRONT, BOTTOM_FRONT, BOTTOM_RIGHT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_LEFT, TOP_FRONT, BOTTOM_RIGHT, TOP_FRONT, RIGHT_FRONT, BOTTOM_LEFT, LEFT_BACK, TOP_FRONT, TOP_RIGHT, TOP_FRONT, RIGHT_BACK, LEFT_BACK, RIGHT_BACK, TOP_FRONT },
  { RIGHT_FRONT, BOTTOM_RIGHT, BOTTOM_BACK, RIGHT_FRONT, BOTTOM_BACK, TOP_FRONT, RIGHT_BACK, TOP_RIGHT, BOTTOM_BACK, TOP_RIGHT, TOP_FRONT, BOTTOM_BACK, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_LEFT, LEFT_BACK, TOP_RIGHT, TOP_FRONT, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_RIGHT, TOP_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_FRONT, TOP_RIGHT, RIGHT_FRONT, TOP_LEFT, TOP_RIGHT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_FRONT, TOP_RIGHT, RIGHT_FRONT, LEFT_FRONT, TOP_LEFT, TOP_RIGHT, LEFT_BACK, BOTTOM_LEFT, BOTTOM_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, LEFT_FRONT, TOP_LEFT, TOP_RIGHT, RIGHT_FRONT, LEFT_FRONT, BOTTOM_RIGHT, RIGHT_BACK, BOTTOM_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_FRONT, TOP_LEFT, TOP_RIGHT, RIGHT_FRONT, LEFT_FRONT, TOP_LEFT, RIGHT_BACK, LEFT_BACK, BOTTOM_RIGHT, LEFT_BACK, BOTTOM_LEFT, BOTTOM_RIGHT, NONE, NONE, NONE },
  { LEFT_FRONT, BOTTOM_RIGHT, BOTTOM_FRONT, LEFT_FRONT, TOP_LEFT, BOTTOM_RIGHT, TOP_LEFT, TOP_RIGHT, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, BOTTOM_RIGHT, BOTTOM_FRONT, TOP_LEFT, BOTTOM_RIGHT, TOP_LEFT, TOP_RIGHT, TOP_LEFT, BOTTOM_FRONT, LEFT_FRONT, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_LEFT, TOP_RIGHT, RIGHT_BACK, BOTTOM_FRONT, TOP_LEFT, RIGHT_BACK, BOTTOM_BACK, BOTTOM_FRONT, BOTTOM_FRONT, LEFT_FRONT, TOP_LEFT, NONE, NONE, NONE },
  { TOP_LEFT, TOP_RIGHT, BOTTOM_FRONT, TOP_LEFT, BOTTOM_FRONT, LEFT_FRONT, TOP_RIGHT, RIGHT_BACK, BOTTOM_FRONT, BOTTOM_LEFT, BOTTOM_FRONT, LEFT_BACK, RIGHT_BACK, LEFT_BACK, BOTTOM_FRONT },
  { BOTTOM_FRONT, TOP_RIGHT, RIGHT_FRONT, BOTTOM_FRONT, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_LEFT, TOP_LEFT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_BACK, BOTTOM_FRONT, BOTTOM_BACK, LEFT_BACK, TOP_RIGHT, BOTTOM_FRONT, LEFT_BACK, TOP_LEFT, TOP_RIGHT, RIGHT_FRONT, BOTTOM_FRONT, TOP_RIGHT, NONE, NONE, NONE },
  { RIGHT_BACK, BOTTOM_BACK, BOTTOM_RIGHT, TOP_RIGHT, RIGHT_FRONT, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_LEFT, TOP_LEFT, BOTTOM_LEFT, RIGHT_FRONT, BOTTOM_FRONT, NONE, NONE, NONE },
  { RIGHT_BACK, LEFT_BACK, BOTTOM_FRONT, RIGHT_BACK, BOTTOM_FRONT, BOTTOM_RIGHT, LEFT_BACK, TOP_LEFT, BOTTOM_FRONT, RIGHT_FRONT, BOTTOM_FRONT, TOP_RIGHT, TOP_LEFT, TOP_RIGHT, BOTTOM_FRONT },
  { BOTTOM_RIGHT, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_LEFT, TOP_LEFT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, TOP_LEFT, BOTTOM_BACK, TOP_LEFT, BOTTOM_RIGHT, BOTTOM_RIGHT, TOP_LEFT, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, BOTTOM_BACK, BOTTOM_LEFT, RIGHT_BACK, BOTTOM_LEFT, TOP_RIGHT, TOP_RIGHT, BOTTOM_LEFT, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, LEFT_BACK, TOP_LEFT, TOP_RIGHT, RIGHT_BACK, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, LEFT_BACK, TOP_BACK, TOP_RIGHT, RIGHT_FRONT, LEFT_BACK, RIGHT_FRONT, LEFT_FRONT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_RIGHT, BOTTOM_BACK, TOP_BACK, TOP_RIGHT, LEFT_FRONT, BOTTOM_BACK, TOP_RIGHT, RIGHT_FRONT, LEFT_FRONT, LEFT_FRONT, BOTTOM_LEFT, BOTTOM_BACK, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_BACK, LEFT_BACK, TOP_BACK, RIGHT_FRONT, LEFT_BACK, RIGHT_FRONT, LEFT_FRONT, RIGHT_FRONT, TOP_BACK, TOP_RIGHT, NONE, NONE, NONE },
  { RIGHT_FRONT, LEFT_FRONT, TOP_BACK, RIGHT_FRONT, TOP_BACK, TOP_RIGHT, LEFT_FRONT, BOTTOM_LEFT, TOP_BACK, RIGHT_BACK, TOP_BACK, BOTTOM_RIGHT, BOTTOM_LEFT, BOTTOM_RIGHT, TOP_BACK },
  { BOTTOM_FRONT, TOP_RIGHT, BOTTOM_RIGHT, BOTTOM_FRONT, LEFT_BACK, TOP_RIGHT, BOTTOM_FRONT, LEFT_FRONT, LEFT_BACK, TOP_BACK, TOP_RIGHT, LEFT_BACK, NONE, NONE, NONE },
  { BOTTOM_BACK, TOP_BACK, LEFT_FRONT, BOTTOM_BACK, LEFT_FRONT, BOTTOM_LEFT, TOP_BACK, TOP_RIGHT, LEFT_FRONT, BOTTOM_FRONT, LEFT_FRONT, BOTTOM_RIGHT, TOP_RIGHT, BOTTOM_RIGHT, LEFT_FRONT },
  { BOTTOM_BACK, BOTTOM_FRONT, TOP_RIGHT, BOTTOM_BACK, TOP_RIGHT, RIGHT_BACK, BOTTOM_FRONT, LEFT_FRONT, TOP_RIGHT, TOP_BACK, TOP_RIGHT, LEFT_BACK, LEFT_FRONT, LEFT_BACK, TOP_RIGHT },
  { RIGHT_BACK, TOP_BACK, TOP_RIGHT, BOTTOM_FRONT, LEFT_FRONT, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, TOP_RIGHT, RIGHT_FRONT, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_FRONT, BOTTOM_LEFT, TOP_BACK, TOP_RIGHT, BOTTOM_LEFT, LEFT_BACK, TOP_BACK, NONE, NONE, NONE },
  { TOP_RIGHT, RIGHT_FRONT, BOTTOM_FRONT, TOP_RIGHT, BOTTOM_FRONT, TOP_BACK, TOP_BACK, BOTTOM_FRONT, BOTTOM_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, RIGHT_FRONT, BOTTOM_FRONT, BOTTOM_LEFT, TOP_RIGHT, RIGHT_FRONT, BOTTOM_LEFT, LEFT_BACK, TOP_RIGHT, TOP_BACK, TOP_RIGHT, LEFT_BACK, BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_BACK },
  { TOP_RIGHT, RIGHT_FRONT, BOTTOM_FRONT, TOP_RIGHT, BOTTOM_FRONT, TOP_BACK, BOTTOM_RIGHT, RIGHT_BACK, BOTTOM_FRONT, RIGHT_BACK, TOP_BACK, BOTTOM_FRONT, NONE, NONE, NONE },
  { LEFT_BACK, TOP_BACK, TOP_RIGHT, LEFT_BACK, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_LEFT, TOP_RIGHT, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, TOP_BACK, TOP_RIGHT, BOTTOM_RIGHT, BOTTOM_BACK, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_BACK, TOP_BACK, TOP_RIGHT, LEFT_BACK, TOP_RIGHT, BOTTOM_LEFT, RIGHT_BACK, BOTTOM_BACK, TOP_RIGHT, BOTTOM_BACK, BOTTOM_LEFT, TOP_RIGHT, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_BACK, TOP_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, LEFT_FRONT, TOP_LEFT, TOP_BACK, RIGHT_BACK, LEFT_FRONT, RIGHT_BACK, RIGHT_FRONT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT, TOP_BACK, RIGHT_BACK, TOP_LEFT, RIGHT_BACK, LEFT_FRONT, TOP_LEFT, RIGHT_BACK, RIGHT_FRONT, LEFT_FRONT, NONE, NONE, NONE },
  { BOTTOM_RIGHT, RIGHT_FRONT, LEFT_FRONT, BOTTOM_RIGHT, LEFT_FRONT, TOP_BACK, BOTTOM_RIGHT, TOP_BACK, BOTTOM_BACK, TOP_LEFT, TOP_BACK, LEFT_FRONT, NONE, NONE, NONE },
  { BOTTOM_LEFT, BOTTOM_RIGHT, TOP_BACK, BOTTOM_LEFT, TOP_BACK, LEFT_BACK, BOTTOM_RIGHT, RIGHT_FRONT, TOP_BACK, TOP_LEFT, TOP_BACK, LEFT_FRONT, RIGHT_FRONT, LEFT_FRONT, TOP_BACK },
  { TOP_BACK, LEFT_FRONT, TOP_LEFT, RIGHT_BACK, LEFT_FRONT, TOP_BACK, RIGHT_BACK, BOTTOM_FRONT, LEFT_FRONT, RIGHT_BACK, BOTTOM_RIGHT, BOTTOM_FRONT, NONE, NONE, NONE },
  { RIGHT_BACK, TOP_LEFT, TOP_BACK, RIGHT_BACK, LEFT_FRONT, TOP_LEFT, RIGHT_BACK, BOTTOM_RIGHT, LEFT_FRONT, BOTTOM_FRONT, LEFT_FRONT, BOTTOM_RIGHT, BOTTOM_BACK, LEFT_BACK, BOTTOM_LEFT },
  { LEFT_FRONT, TOP_LEFT, TOP_BACK, LEFT_FRONT, TOP_BACK, BOTTOM_FRONT, BOTTOM_FRONT, TOP_BACK, BOTTOM_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { LEFT_FRONT, TOP_LEFT, TOP_BACK, LEFT_FRONT, TOP_BACK, BOTTOM_FRONT, LEFT_BACK, BOTTOM_LEFT, TOP_BACK, BOTTOM_LEFT, BOTTOM_FRONT, TOP_BACK, NONE, NONE, NONE },
  { BOTTOM_FRONT, RIGHT_BACK, RIGHT_FRONT, BOTTOM_FRONT, TOP_LEFT, RIGHT_BACK, BOTTOM_FRONT, BOTTOM_LEFT, TOP_LEFT, TOP_LEFT, TOP_BACK, RIGHT_BACK, NONE, NONE, NONE },
  { RIGHT_BACK, RIGHT_FRONT, TOP_LEFT, RIGHT_BACK, TOP_LEFT, TOP_BACK, RIGHT_FRONT, BOTTOM_FRONT, TOP_LEFT, LEFT_BACK, TOP_LEFT, BOTTOM_BACK, BOTTOM_FRONT, BOTTOM_BACK, TOP_LEFT },
  { BOTTOM_LEFT, TOP_LEFT, RIGHT_FRONT, BOTTOM_LEFT, RIGHT_FRONT, BOTTOM_FRONT, TOP_LEFT, TOP_BACK, RIGHT_FRONT, BOTTOM_RIGHT, RIGHT_FRONT, BOTTOM_BACK, TOP_BACK, BOTTOM_BACK, RIGHT_FRONT },
  { BOTTOM_RIGHT, RIGHT_FRONT, BOTTOM_FRONT, LEFT_BACK, TOP_LEFT, TOP_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, RIGHT_BACK, BOTTOM_RIGHT, TOP_BACK, BOTTOM_RIGHT, TOP_LEFT, TOP_LEFT, BOTTOM_RIGHT, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, RIGHT_BACK, BOTTOM_RIGHT, TOP_BACK, BOTTOM_RIGHT, TOP_LEFT, BOTTOM_BACK, LEFT_BACK, BOTTOM_RIGHT, LEFT_BACK, TOP_LEFT, BOTTOM_RIGHT, NONE, NONE, NONE },
  { TOP_BACK, BOTTOM_BACK, BOTTOM_LEFT, TOP_LEFT, TOP_BACK, BOTTOM_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { TOP_BACK, LEFT_BACK, TOP_LEFT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, RIGHT_FRONT, LEFT_BACK, RIGHT_FRONT, LEFT_FRONT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, BOTTOM_BACK, RIGHT_BACK, BOTTOM_LEFT, RIGHT_BACK, LEFT_FRONT, LEFT_FRONT, RIGHT_BACK, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_RIGHT, RIGHT_FRONT, BOTTOM_BACK, RIGHT_FRONT, LEFT_BACK, LEFT_BACK, RIGHT_FRONT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, BOTTOM_RIGHT, RIGHT_FRONT, LEFT_FRONT, BOTTOM_LEFT, RIGHT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_FRONT, LEFT_FRONT, BOTTOM_RIGHT, LEFT_FRONT, RIGHT_BACK, RIGHT_BACK, LEFT_FRONT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, BOTTOM_BACK, RIGHT_BACK, BOTTOM_LEFT, RIGHT_BACK, LEFT_FRONT, BOTTOM_RIGHT, BOTTOM_FRONT, RIGHT_BACK, BOTTOM_FRONT, LEFT_FRONT, RIGHT_BACK, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_FRONT, LEFT_FRONT, LEFT_BACK, BOTTOM_BACK, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_LEFT, BOTTOM_FRONT, LEFT_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, BOTTOM_LEFT, LEFT_BACK, BOTTOM_FRONT, LEFT_BACK, RIGHT_FRONT, RIGHT_FRONT, LEFT_BACK, RIGHT_BACK, NONE, NONE, NONE, NONE, NONE, NONE },
  { RIGHT_BACK, RIGHT_FRONT, BOTTOM_FRONT, BOTTOM_BACK, RIGHT_BACK, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_FRONT, BOTTOM_LEFT, LEFT_BACK, BOTTOM_FRONT, LEFT_BACK, RIGHT_FRONT, BOTTOM_BACK, BOTTOM_RIGHT, LEFT_BACK, BOTTOM_RIGHT, RIGHT_FRONT, LEFT_BACK, NONE, NONE, NONE },
  { BOTTOM_RIGHT, RIGHT_FRONT, BOTTOM_FRONT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_RIGHT, BOTTOM_LEFT, LEFT_BACK, RIGHT_BACK, BOTTOM_RIGHT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, RIGHT_BACK, BOTTOM_RIGHT, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { BOTTOM_BACK, BOTTOM_LEFT, LEFT_BACK, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE },
  { NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE }
}};

uint8_t computeCellConfiguration(const Grid3b& grid, std::size_t widthIndex, std::size_t heightIndex, std::size_t depthIndex) {
  // TODO: the following configuration feels more logical, matches the marching squares', and should ideally be used in the future

  // Computing a single number according to the corners' values:
  //
  // front      back
  // 8 - 4    128 - 64
  // |   |     |     |
  // 1 - 2    16 -- 32
  //
  // O - O   O - O           O - O   O - X           O - X   X - O           X - X   X - X
  // |   |   |   | -> 0      |   |   |   | -> 65     |   |   |   | -> 165    |   |   |   | -> 255
  // O - O   O - O           X - O   O - O           X - O   O - X           X - X   X - X

  //return static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex,     depthIndex    ))        // Bottom-left front
  //     | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex,     depthIndex    ) << 1u)  // Bottom-right front
  //     | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex + 1, depthIndex    ) << 2u)  // Top-right front
  //     | static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex + 1, depthIndex    ) << 3u)  // Top-left front
  //     | static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex,     depthIndex + 1) << 4u)  // Bottom-left back
  //     | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex,     depthIndex + 1) << 5u)  // Bottom-right back
  //     | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex + 1, depthIndex + 1) << 6u)  // Top-right back
  //     | static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex + 1, depthIndex + 1) << 7u); // Top-left back

  // TODO: using the configuration from https://paulbourke.net/geometry/polygonise/; see other TODO above

  // Computing a single number according to the corners' values:
  //
  //  front       back
  // 128 - 64   16 - 32
  //  |    |     |    |
  //  8 -- 4     1 -- 2
  //
  // O - O   O - O           O - O   O - X           O - X   X - O          X - X   X - X
  // |   |   |   | -> 0      |   |   |   | -> 40     |   |   |   | -> 90    |   |   |   | -> 255
  // O - O   O - O           X - O   O - O           X - O   O - X          X - X   X - X

  return static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex,     depthIndex + 1))        // Bottom-left back
       | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex,     depthIndex + 1) << 1u)  // Bottom-right back
       | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex,     depthIndex    ) << 2u)  // Bottom-right front
       | static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex,     depthIndex    ) << 3u)  // Bottom-left front
       | static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex + 1, depthIndex + 1) << 4u)  // Top-left back
       | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex + 1, depthIndex + 1) << 5u)  // Top-right back
       | static_cast<uint8_t>(grid.getValue(widthIndex + 1, heightIndex + 1, depthIndex    ) << 6u)  // Top-right front
       | static_cast<uint8_t>(grid.getValue(widthIndex,     heightIndex + 1, depthIndex    ) << 7u); // Top-left front
}

} // namespace

Mesh MarchingCubes::compute(const Grid3b& grid) {
  ZoneScopedN("MarchingCubes::compute");

  if (grid.getWidth() < 2 || grid.getHeight() < 2 || grid.getDepth() < 2)
    throw std::invalid_argument("[MarchingCubes] The input grid's width, height & depth must be at least 2.");

  Mesh mesh;
  Submesh& submesh = mesh.addSubmesh();

  const Vec3f globalOffset(static_cast<float>(grid.getWidth() - 1) * 0.5f,
                           static_cast<float>(grid.getHeight() - 1) * 0.5f,
                           static_cast<float>(grid.getDepth() - 1) * 0.5f);

  submesh.getVertices() = Threading::parallelizeReduce(0, grid.getDepth() - 1, [&grid, globalOffset] (const auto& range) {
    ZoneScopedN("MarchingCubes::compute");

    std::vector<Vertex> vertices;

    for (std::size_t depthIndex = range.beginIndex; depthIndex < range.endIndex; ++depthIndex) {
      for (std::size_t heightIndex = 0; heightIndex < grid.getHeight() - 1; ++heightIndex) {
        for (std::size_t widthIndex = 0; widthIndex < grid.getWidth() - 1; ++widthIndex) {
          const uint8_t cellConfig = computeCellConfiguration(grid, widthIndex, heightIndex, depthIndex);
          const std::array<int8_t, 15>& edgeIndices = trianglesIndices[cellConfig];
          const Vec3f localOffset(static_cast<float>(widthIndex), static_cast<float>(heightIndex), static_cast<float>(depthIndex));

          for (std::size_t edgeIndex = 0; edgeIndex < edgeIndices.size(); edgeIndex += 3) {
            if (edgeIndices[edgeIndex] == NONE)
              break;

            // TODO: compute texcoords
            // TODO: compute tangent
            const Vec3f firstPoint  = edgeVertices[edgeIndices[edgeIndex    ]] - globalOffset + localOffset;
            const Vec3f secondPoint = edgeVertices[edgeIndices[edgeIndex + 1]] - globalOffset + localOffset;
            const Vec3f thirdPoint  = edgeVertices[edgeIndices[edgeIndex + 2]] - globalOffset + localOffset;
            const Vec3f normal      = (secondPoint - firstPoint).cross(thirdPoint - firstPoint).normalize();
            vertices.emplace_back(Vertex{ firstPoint, Vec2f(), normal });
            vertices.emplace_back(Vertex{ secondPoint, Vec2f(), normal });
            vertices.emplace_back(Vertex{ thirdPoint, Vec2f(), normal });
          }
        }
      }
    }

    return vertices;
  }, [] (std::vector<Vertex>&& result, const std::vector<Vertex>& vertices) {
    ZoneScopedN("Reduce");
    result.insert(result.end(), vertices.begin(), vertices.end());
    return std::move(result);
  });

  std::vector<unsigned int>& indices = submesh.getTriangleIndices();
  indices.resize(submesh.getVertices().size());
  std::iota(indices.begin(), indices.end(), 0);

  return mesh;
}

} // namespace Raz

Razakhel / RaZ / 16724994103

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous