Sign in to follow this  
Anfaenger

The most useful enumeration for cube edges

Recommended Posts

All cube-based polygonization algorithms (and octree-related code, e.g. for simplification) need to reason about the geometry and topology of the cube.

For example, given cube corners inside the solid, get the list of active (pierching the isosurface) edges; given two diagonally-adjacent cubes and the active edge on our cube, get the index of the corresponding edge on another cube; given an edge, find the index of its starting vertex and so on.

 

The 'right' way to number a cube's corners, is, of course, to use Morton/Z-order (very elegant to build coordinates of child nodes in an octree, calculate AABBs).

 

But what is the 'canonical', 'correct' way of enumerating cube edges?

 

Right now I'm using the CUBE_EDGE table to find the index of the vertex emanating from the given edge.

Is it possible by some mathematical trickery/bitwise wizardry to avoid using LUTs at all?

Should I pack all small LUTs into uint32_t's for performance?

 

Here's my "cubelib", the best what I've come up so far:

// Cube-related constants.

/*
	   Z
	   |  /Y
	   | /
	   |/_____X
	 (0,0,0)

Face orientation (normal) - apply right-hand rule to the edge loop.

         UP  NORTH
         |  /
         | /
   WEST--O--EAST
        /|
       / |
  SOUTH  DOWN

LABELING OF VERTICES, EDGES AND FACES:

Vertex enumeration:
        6___________7
       /|           /
      / |          /|
     /  |         / |
    4------------5  |
    |   2________|__3
    |   /        |  /
    |  /         | /
    | /          |/
    0/___________1

or using locational (Morton) codes (X - lowest bit, Y - middle, Z - highest):

       110__________111
       /|           /
      / |          /|
     /  |         / |
  100-----------101 |
    |  010_______|__011
    |   /        |  /
    |  /         | /
    | /          |/
  000/___________001

(see Gray code, Hamming distance, De Bruijn sequence)

NOTE: two vertices are connected by an edge, if their indices differ by one and only one bit.

Cube edge enumeration
(edges are split into 3 groups by axes X,Y,Z - this allows: edge_axis = edge_index / 4;
(numbered using right-hand rule):
        ______2______
       /|           /|
      5 |11        6 |
     /  |         /  |10
    |------3-----|   |
    |   |_____1__|___|
    |   /        |   /
   8|  4        9|  7
    | /          | /
    |/___________|/
           0
*/

enum { NUM_CUBE_EDGES = 12 };

// CUBE_EDGE[ cube_edge ] => { start_vertex, end_vertex }
// where cube_edge is [0..11] and (start_vertex, end_vertex is [0..7])
extern const U8 CUBE_EDGE[12][2];

// CUBE_VERTEX[ cube_face ] => { cube vertices [4] }
extern const U8 CUBE_VERTEX[6][4];

// CUBE_FACE_EDGE[ face_edge ] => { cube edges [4] }
// where face_edge is [0..3] and cube_edge is [0..11]
extern const U8 CUBE_FACE_EDGE[6][4];

// NEXT_POSITION[face][edge] gives the connected [face, edge]
// where face is [0..5] and edge is [0..3] (edge relative to face)
extern const U8 NEXT_POSITION[6][4][2];

static const U32 CUBE_EDGES_AXIS_X = (BIT(0) | BIT(1) | BIT(2) | BIT(3));
static const U32 CUBE_EDGES_AXIS_Y = (BIT(4) | BIT(5) | BIT(6) | BIT(7));
static const U32 CUBE_EDGES_AXIS_Z = (BIT(8) | BIT(9) | BIT(10) | BIT(11));

/// maps the given cube edge to the diagonally opposite one, e.g. 0 -> 2, 3 -> 1, 10 -> 8, etc.
static mxFORCEINLINE UINT DiagonallyOppositeEdge( UINT iEdge )
{
	return ((iEdge + 2) % 4) + (iEdge & ~3);
}

/// returns the index of the edge on the given edge-adjacent cube,
/// i.e. iNeighborCube is the next [0..2] cube around the edge.
/// E.g. for a cube edge 2 the returned values will be 3, 0, 1;
/// for a cube edge 8 the returned values will be 9, 10, 11;
/// for a cube edge 6 the returned values will be 5, 4, 7.
static mxFORCEINLINE UINT NextAdjacentEdge( UINT iEdge, UINT iNeighborCube )	// iNeighborCube <E [0..2]
{
	const UINT iEdgeOnNeighbor = (iEdge + iNeighborCube + 1) % 4 + (iEdge & ~3);
	return iEdgeOnNeighbor;
}

mxFORCEINLINE U32 ExtractNextEdge( U32 edgeMask, U32 *edgeIndex )
{
	// Search the mask data from least significant bit (LSB) to the most significant bit (MSB) for a set bit (1).
	DWORD iEdge;
	_BitScanForward( &iEdge, edgeMask );
	edgeMask &= ~((1U << (iEdge+1)) - 1);	// zero out all bits below and including the Edge bit
	*edgeIndex = iEdge;
	return edgeMask;
}

/// Edge-table gives all the edges intersected in a given cube configuration:
struct ActiveEdges
{
	U16	edgeMask[256];	//!< set bits correspond to active edges
//	U8	LUT[256][12];
};

/*alignas(128) */mxPREALIGN(128) extern ActiveEdges	CUBE_EDGES_LUT;

// precomputes a set of intersecting edges for each cube/sign configuration
void GenerateActiveCubeEdgesTable( ActiveEdges & LUT );

//*********************************************************************
// in .cpp file
//*********************************************************************

//TODO: pack these integers into one?
// CUBE_EDGE[ cube_edge ] => { start_vertex, end_vertex }
// (edges are split into 3 groups by axes X,Y,Z, numbered using right-hand rule)
const U8 CUBE_EDGE[ 12 ][2] =
{
	{ 0, 1 }, { 2, 3 }, { 6, 7 }, { 4, 5 },	// X-axis
	{ 0, 2 }, { 4, 6 }, { 5, 7 }, { 1, 3 },	// Y-axis
	{ 0, 4 }, { 1, 5 }, { 3, 7 }, { 2, 6 },	// Z-axis
};

// CUBE_VERTEX[ cube_face ] => { cube vertices [4] }
const U8 CUBE_VERTEX[6][4] =
{
	// cube vertices
    {  2,   3,   1,   0 }, // face 0
    {  0,   1,   5,   4 }, // face 1
    {  2,   0,   4,   6 }, // face 2
    {  1,   3,   7,   5 }, // face 3
    {  3,   2,   6,   7 }, // face 4
    {  4,   5,   7,   6 }, // face 5
};

// CUBE_FACE_EDGE[ face_edge ] => { cube edges [4] }
const U8 CUBE_FACE_EDGE[6][4] =
{
	//edge0, edge1, edge2, edge3
    {  1,   7,   0,   4 }, // face 0
    {  0,   9,   3,   8 }, // face 1
    {  4,   8,   5,  11 }, // face 2
    {  7,  10,   6,   9 }, // face 3
    {  1,  11,   2,  10 }, // face 4
    {  3,   6,   2,   5 }, // face 5
};

// Given a face and a face edge, this table returns the next face and face edge,
// which are actually the same edge in the combined cube.
// NEXT_POSITION[face][edge] gives the connected [face, edge]
const U8 NEXT_POSITION[6][4][2] =
{
	// edge0 | edge1 | edge2 | edge3
    {{4, 0}, {3, 0}, {1, 0}, {2, 0}}, // face 0
    {{0, 2}, {3, 3}, {5, 0}, {2, 1}}, // face 1
    {{0, 3}, {1, 3}, {5, 3}, {4, 1}}, // face 2
    {{0, 1}, {4, 3}, {5, 1}, {1, 1}}, // face 3
    {{0, 0}, {2, 3}, {5, 2}, {3, 1}}, // face 4
    {{1, 2}, {3, 2}, {4, 2}, {2, 2}}, // face 5
};

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this