## Tuesday, February 22, 2011

### Iterating Cube Vertices, Edges and Faces

This keeps haunting me. There must be an awesome way to arrange the data so that you can do a simple for loop and iterate over all cube vertices, edges and faces. I'm sort of after something you could use in matching cube like algorithms to fetch data from a sample grid without having to use lookup tables.

Vertices or sample offsets are easy:

``    for (int i = 0; i < 8; ++i)    {        const int dx = i & 1;        const int dy = (i>>1) & 1;        const int dz = (i>>2) & 1;        printf("%d: %d,%d,%d\n", i, dx,dy,dz);    }        ``

Assuming that you have 3 values per sample, one along each axis, the following code can be used to walk through all the valid edges:

``    for (int i = 0; i < 12; ++i)    {        const int ax = (i >> 2) & 3;        const int as = (4-ax) >> 2;        const int bs = (5-ax) >> 2;        const int v = ((i&1) << as) | ((i&2) << bs);        printf("va=%d vb=%d  dir=%c\n", v, v|(1<<ax), "XYZ"[ax]);    }``

But... I'm not satisfied, there must be a cleaner way.

I once figured out how to procedurally draw a cube with just one for loop, but I cannot remember how to do it anymore, IIRC it used rotating sequence of XYZ, ZXY, YZX somehow, much like how you calculate cross products.

1. Your code got pretty horribly eaten so I'm not sure what it was doing.

I can see two approaches for edges. In one, you split the 12 edges into 3 groups of 4 edges, one for each axis. Then you can enumerate a pair of vertices for each one by orthographically traversing the remaining axes.

If you only need one vertex and an axis for each one, you can view it as 4 clusters of 3 edges, all 3 edges meet at a common corner. If I didn't screw up my whiteboard, this is straightforward and produces a simple pattern: you use either corners 0,3,5,6 or corners 1,2,4,7; so now it's just a question of which you can generate more easily in code. I guess 1,2,4,7 is pretty close to 1,2,4,8, although the code will look hacky.

Anyway, the two approaches would both code things so you'd iterate through 12 integers and do 'axis = index >> 2'. For the first approach you would use the remaining two bits *and* the axis to compute the vertices. For the second one, you would have 'axis = index >> 2', and compute the vertices only from 'index&3'. I guess... (1<<(index&3) - ((index&3)==3)), or to keep it comparison free, (1<<(index&3) - ((index>>1)&index&1))

2. Another try... one day someone will make a programmers blogger, which does not mess up source code :) I also changed the code to calculate the opposite edge vertex.

I was not able to get your indexing code to work. I have to try it with more time to see if I can pin point the problem.

The edges what gets printed out with the above code are (va = corner vertex, vb= opposite vertex, dir=sample axis):

va=0 vb=1 dir=X
va=2 vb=3 dir=X
va=4 vb=5 dir=X
va=6 vb=7 dir=X
va=0 vb=2 dir=Y
va=1 vb=3 dir=Y
va=4 vb=6 dir=Y
va=5 vb=7 dir=Y
va=0 vb=4 dir=Z
va=1 vb=5 dir=Z
va=2 vb=6 dir=Z
va=3 vb=7 dir=Z

Or when looked at which sample directions are valid at which sample (Index: sample directions):
0: X Y Z
1: Y Z
2: X Z
3: Z
4: X Y
5: Y
6: X
7:

3. I see a pattern in that second list:
X is a valid direction if (index & 1) == 0
Y is a valid direction if (index & 2) == 0
Z is a valid direction if (index & 4) == 0

4. Ok, yeah, yours was my first variant. Here's my second variant:

axis = i shr 2
temp = i and 3
va = (1 shl temp) - (temp==3)
vb = temp xor (1 shl axis)

Computed by hand:

axis=0 temp=0 va=1 vb=0
axis=0 temp=1 va=2 vb=3
axis=0 temp=2 va=4 vb=5
axis=0 temp=3 va=7 vb=6
axis=1 temp=0 va=1 vb=3
axis=1 temp=1 va=2 vb=0
axis=1 temp=2 va=4 vb=6
axis=1 temp=3 va=7 vb=5
axis=2 temp=0 va=1 va=5
axis=2 temp=1 va=2 va=6
axis=2 temp=2 va=4 va=0
axis=2 temp=3 va=7 va=3

Looks like it's a lightly shuffled version of yours (which is to be expected since 'axis' is encoded identically in both). I think your implementation is simpler, though, so not much point.

5. er, sorry, not 'temp xor (1 shl axis)', it's 'va xor (1 shl axis)'

6. Here's one that's kind of conceptually simple, but unfortunately doesn't seem concisely expressible in actual programming language. Also, i have no explanation for how it works, I just constructed it to generate the right 12 pairs of numbers.

for (i=0; i < 12; ++i)
{
va = i & 7;
offset = i & 8 ? 3 : i_bit_0 ^ i_bit_1 ^ i_bit_2;
vb = va ^ (offset+1);
}
}

7. you can rewrite offset as:

offset = i & 8 ? 3 : popcount(va)&1;

8. I remembered the cube version:

glBegin(GL_LINES);

for (int i = 0; i < 6; ++i)
{
int s = i&1;
int x = i>>1;
int y = (x+1)%3;
int z = (y+1)%3;

float p = {0,0,0};
p[x] = s ? 0.2f : -0.2f;

float ax = {0,0,0};
ax[y] = s ? 0.3f : -0.3f;

float ay = {0,0,0};
ay[z] = s ? 0.3f : -0.3f;

glColor4ub(255,255,255,255);
glVertex3f(0,0,0);
glVertex3f(p,p,p);

float p2 = {p-ax/2-ay/2, p-ax/2-ay/2, p-ax/2-ay/2};

glColor4ub(255,0,0,255);
glVertex3f(p2,p2,p2);
glVertex3f(p2+ax,p2+ax,p2+ax);

glColor4ub(0,255,0,255);
glVertex3f(p2,p2,p2);
glVertex3f(p2+ay,p2+ay,p2+ay);
}

glEnd();

There should be a way to change those floating point offsets to sample offsets, and those mod3s can be done using the shift & and trick.

Also with some fiddling it should be possible to rotate the face axii so that the iteration only visits a single edge once.

9. Wait, but that's drawing 18 lines? Hmm, I was picturing you meant more something that kept some variables defined outside the loop and shuffled them inside the loop.

If you're willing to draw three line segments on every iteration of the loop, you could probably use my 1,2,4,7 sequence to do it with only 4 iterations. In fact, looking at my whiteboard again, I see that you can in fact generate the 1,2,4,7 sequence pretty trivially if it's expanded into a vector.

// this is verbose what with comments
// explaining what's going on, if you
// strip those out it should be reasonable
int width = 1; // any integer
int p = { 0,0,0 };
for (i=0; i < 4)
{
// generate the sequence:
// (0,0,0)
// 1,0,1
// 1,1,0
// 0,1,1
// 0,0,0
// x and y make a rotation, and z toggles.
p = p ^ width;
// compute the rotation
p = p;
p = i & 2 ? 0 : width; // cheat to avoid temp

glColor3ub(255,0,0);
glVertex3f(p,p,p);
glVertex3f(p^width,p,p);

glColor3ub(0,255,0);
glVertex3f(p,p,p);
glVertex3f(p,p^width,p);

glColor3ub(0,0,255);
glVertex3f(p,p,p);
glVertex3f(p,p,p^width);
}

// You can allow arbitrary cube positions by
// making 'width' be 1 and using the integers
// to lerp/select between two floats.

10. Oh wait, I see, you're actually drawing 6 lines from the *center*? I'm not sure what those would be, I guess to the centers of faces? I can't guess what the red vs. blue color distinguishes, though.

11. I should have been more clear with that code, I wrote it whilst waiting a meeting to start :) It is meant to iterate all cube faces. It's the last case I mentioned in the blog post.

The vectors ax/ay (with proper scaling) can be used to draw a face of a cube, and I think it should be possible to turn then into indices to the 8 vertices too. And a bit of rotation magic, it should be possible to arrange the axii so that each edge is visited once (current each edge is visited twice). I remember doing that too once to draw beveled cubes.

Yeah, that white line is just direction to the center of the cube face. Probably should have omitted it.

12. glColor3f(1, 1, 1);
glBegin(GL_LINES);

for (int i = 0; i < 8; i++)
for (int j = 0; j < i; j++) {
int x = i ^ j;

if (x == 1 || x == 2 || x == 4) {
glVertex3f(v[!(i & 1)].x(), v[!(i & 2)].y(), v[!(i & 4)].z());
glVertex3f(v[!(j & 1)].x(), v[!(j & 2)].y(), v[!(j & 4)].z());
}
}

glEnd();

This assumes v is an array of two vectors containing opposing any two opposing corners of the cube. This did the trick for me.

This just observes the fact that the vertices of all valid edges must share exactly two of the x, y and z values. Or in other words only one of the three can be from a different opposing corner. If you take these as bits they must therefore only differ in one bit.

The '!(i & 1)' parts are just extracting the bits from i and j and using them to choose which vector to take the x, y or z coordinate from.

13. The cheapest way to iterate edges I can think of is this:

for (int i = 0x2ef0298; i > 0x2ef0; i >>= 1)
{
int va = i & 7;
int vb = (i >> 14) & 7;

printf("va=%d vb=%d dir=%c\n", va, vb, ".XY.Z"[va ^ vb]);
}

The edges you get with this code are:

va=0 vb=4 dir=Z
va=4 vb=6 dir=Y
va=6 vb=7 dir=X
va=3 vb=7 dir=Z
va=1 vb=3 dir=Y
va=4 vb=5 dir=X
va=2 vb=6 dir=Z
va=5 vb=7 dir=Y
va=2 vb=3 dir=X
va=1 vb=5 dir=Z
va=0 vb=2 dir=Y
va=0 vb=1 dir=X

It is not particulary elegant in the sense that it does not exploit the layout of the data nor does it iterate the edges in a meaningful geometric order. The value 0x2ef0298 is a very small (28 bits; 14 bits per vertex) lookup table.

I use a vertex order that can be iterated by shifting in a single bit per step. The lower 14 bits are for vertex A and the upper 14 are for vertex B.

The value used here is not unique. I have found 1280 possible values that iterate over all cube edges. Half of these values simply swap vertex a and b. Like Mikko's code this code walks all edges in the positive direction albeit in a different order. I don't know if the edge direction is an important property.