OpenGL patterns with cubes

These are five small OpenGL programs for Windows, written in C++. They share the same window and OpenGL code, and differ only in one file, test.cpp, which decides which cubes to draw and what colour they are.

The idea is the same in all five. Take a box of space and divide it into a grid of cells. Then for every cell, ask a simple question about its position, and if the answer is yes, draw a solid cube there. Change the question, or let it depend on time, and you get a different moving shape.

A grid of cubes

A cube is the simplest thing you can put in a cell: it fills it exactly, so a set of cells drawn as cubes looks like a solid object made of blocks. That's what voxels are, a volume divided up into little boxes, though here there's no stored volume. Nothing is kept from one frame to the next. Every frame, the program goes through the whole grid and works out again which cells are in.

Each cell has whole-number coordinates i, j and k. A test looks at them, and sometimes at a frame counter or the clock, and says whether to draw a cube. The three blobs1 programs use a 40x40x40 grid, which is 64,000 cells, and the two blobs2 programs use a box of 30 or 20 cells along each side:

So between programs it's only the test and the colour that change. We'll go through the code they all share first, then each test in turn.

Setting up

The window and the OpenGL set-up come from a small Windows OpenGL helper library by Mark Lord of Gremlin Interactive, in Winmain.cpp and qe_ogl.cpp. It opens an 800x600 window, picks a double-buffered pixel format with 16-bit colour and a 16-bit depth buffer, and sets up a perspective projection with a 60 degree field of view:

	glMatrixMode (GL_PROJECTION);
	glLoadIdentity ();
	gluPerspective (60.0, (GLfloat)width/(GLfloat)height, 1.0, 30000.0);
	glMatrixMode (GL_MODELVIEW);
	glLoadIdentity ();

	...

	// no blending just yet
	glDisable (GL_BLEND);
  glEnable (GL_DEPTH_TEST);

There's no lighting and no texturing. Back-face culling is configured but left switched off (its glEnable is commented out), so all six faces of every cube are drawn and the depth buffer sorts out which ones are in front.

The main loop doesn't wait for anything. It handles any Windows messages that are waiting, then calls GameMain in test.cpp to draw a frame, as fast as the machine can go:

	g_exitflag = FALSE;
	while (! g_exitflag)
	{
		ProcessMessages ();
		GameMain ();
	}

GameMain clears the screen, moves the scene away from the camera, turns it by however far the mouse has dragged it, draws the cubes and swaps the buffers:

void GameMain()
{
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
	glLoadIdentity();
	glTranslatef(0.f, 0.f, -3.f);

	glRotatef(-r2*0.2, 1.0, 0.0, 0.0);
	glRotatef(-r1*0.2, 0.0, 1.0, 0.0);

	GameDraw();
	SwapBuffers(gl_dc);
}

The grid is centred on the origin, so the camera always looks at the middle of it and the rotations turn it about its centre.

The folders also hold Main.cpp and Pattern.cpp, which are Lewpen's pattern generator, a separate program with its own WinMain. test.cpp still declares the pattern generator's pattern pointers, but never uses them.

Drawing a cube

Every cube is drawn by one function, oglcube, which takes two opposite corners and a colour. It draws the six faces as six triangle fans of four vertices each, two faces for each axis, and changes the colour between the pairs:

  glColor3f(r, g, b);

  glBegin(GL_TRIANGLE_FAN);
    glVertex3f(x1, y1, z1);
    glVertex3f(x1, y1, z2);
    glVertex3f(x2, y1, z2);
    glVertex3f(x2, y1, z1);
  glEnd();

  ...

  glColor3f(r*0.95, g*0.95, b*0.95);

  ...

  glColor3f(r*0.90, g*0.90, b*0.90);

With no lighting, a cube drawn in one colour would be a flat silhouette. You'd see its outline but not its shape, and a wall of cubes would be one solid patch of colour. So oglcube fakes the shading. The two faces at the ends of the y axis get the full colour, the two x faces get 95% of it and the two z faces 90%:

That's enough of a difference to see the edges where two faces meet, and every cube in a wall shows the same pattern of lighter and darker faces, which reads as solid blocks. The shading belongs to the faces rather than to a light, so when you turn the grid with the mouse the shading turns with it, as if the cubes had been painted.

Colour in rings

In the three blobs1 programs, oglcube does one more thing before it draws. It works out how far the cube's first corner is from the centre of the grid, and uses a sine of that distance to brighten or darken the colour:

  double t = 7 + 2*sin(GetTickCount()*3.14159/16400);

  double dd = sqrt(x1*x1+y1*y1+z1*z1);
  double d = sin(t*dd);
//  if(d < 0) return;

  d += 1.3;

  r *= d; g *= d; b *= d;

Every cube is drawn in the same orange, (0.8, 0.4, 0.0). Adding 1.3 to the sine makes the multiplier d go from 0.3 to 2.3, so the colour goes from (0.24, 0.12, 0), a dark brown, up to (1.84, 0.92, 0). OpenGL clamps each channel to 1.0, so that's (1.0, 0.92, 0), a bright yellow, with orange in between. That's where the bands from yellow to dark brown in the screenshots come from.

The bands are spheres around the centre. The grid goes from −1 to 1 along each axis (40 cells of 0.05), so dd goes up to √3, about 1.73, in the corners. t sets how tightly the rings are packed: one ring, from bright to bright, is 2π/t wide. t itself swings between 5 and 9 every 32.8 seconds, so the rings slowly squeeze in towards the centre and spread back out, between about 14 and 25 cells apart.

The commented-out line is the whole difference in Diagonal with patterns, which we'll come to.

Basic diagonal (blobs1)

The first program fills the grid with diagonal slabs of cubes that slide through it.

Here's its draw function, which goes through the 64,000 cells and tests each one:

void draw()
{
  int i, j, k;

  static int p = 0;
  p++;

  int w = 20;

  for(k = -w; k < w; k++)
    for(j = -w; j < w; j++)
      for(i = -w; i < w; i++)
      {
        if( ((i+j+k+p)&31) < 1 ) cube(i, j, k);
        ...
      }
}

and cube turns a cell into world coordinates, with each cube 0.05 wide:

double scale = 0.05;

void cube(int x, int y, int z)
{
  oglcube(x*scale, y*scale, z*scale, (x+1)*scale, (y+1)*scale, (z+1)*scale, 0.8, 0.4, 0.0);
}

The test ((i+j+k+p)&31) < 1 is a quick way of saying (i + j + k + p) mod 32 = 0. ANDing with 31 keeps the bottom five bits, which is the remainder after dividing by 32, and it works for negative numbers too: in two's complement, −8 & 31 is 24, the same as −8 + 32. So a cell is drawn when i + j + k + p is a multiple of 32.

All the cells with the same i + j + k lie on a plane at right angles to the long diagonal of the grid, the line through (1, 1, 1). So the cubes drawn make a set of parallel planes, 32 cells apart along each axis. i + j + k goes from −60 to 57, so three or four of them cut through the grid at any time, as hexagons through the middle and triangles across the corners.

Here's a slice through the grid at k = 0. In the slice, each plane is a diagonal line of cells:

Each slab is only one cube thick, and its cubes only touch along their edges, like a staircase, since two cells that share a face always have sums that differ by one. That's what gives the slabs their fine stepped texture: each cube shows a little of three of its faces, in the three shades.

Each frame p goes up by one, so the sum that's drawn goes down by one and every slab moves one cell along the diagonal towards the (−20, −20, −20) corner. After 32 frames each slab has moved into the place of the one before it, and the pattern is back where it started.

A slab has up to 1,200 cubes where it passes through the middle of the grid, and across all the slabs it's a 32nd of the grid, about 2,000 cubes or 24,000 triangles a frame.

Diagonal with patterns (blobs1)

This is the same program with one line put back. The commented-out test at the top of oglcube is switched on:

  double dd = sqrt(x1*x1+y1*y1+z1*z1);
  double d = sin(t*dd);
  if(d < 0) return;

Now the rings aren't just colour. Wherever the sine is negative, which is half of every ring, the cube isn't drawn at all. That divides space into a solid ball in the middle and hollow spherical shells around it, and the slabs only show where they pass through the solid parts. In the slice above, the shaded bands are where the sine is negative, and the outlined cells are the ones that go.

A slab through a ball and shells becomes a disc and a set of flat rings: thin, curving bands. Because t changes over time, the rings grow and shrink while the slabs slide through them.

The cubes that are left are the ones where the sine is 0 or more, so after adding 1.3 the multiplier is between 1.3 and 2.3. The dark browns have gone with the cubes that were cut, and what's left is all orange and yellow.

Blob function (blobs1)

The third blobs1 program swaps the diagonal test for a smooth function of position. The diagonal test is commented out, and the block under it, which was commented out in the first program, is switched on:

//        if( ((i+j+k+p)&31) < 1 ) cube(i, j, k);

        double t = sin(i*3.14159/17+p*3.14159/31 + 0.12451) +
                   sin(j*3.14159/16+p*3.14159/54 + 1.89214) +
                   sin(k*3.14159/15+p*3.14159/47 + 1.00298);
        if(t > 0 && t < 0.25) cube(i, j, k);

Each term is a sine wave along one axis. Along i it repeats every 34 cells, along j every 32 and along k every 30, so a bit more than one wave fits across the grid each way. The constants at the end just start the three waves at different points.

The p terms move the waves along, each at its own speed: the i wave moves 17/31 of a cell a frame, the j wave 16/54 and the k wave 15/47. Their cycles are 62, 108 and 94 frames, so the whole shape only comes back to where it started after 157,356 frames.

The sum t goes from −3 to 3. Where it's exactly 0 is a smooth, wavy surface that divides space into two interlocking halves, with t positive on one side and negative on the other. We're only sampling at whole cells, though, so no cell is ever exactly on t = 0. Instead the test picks a thin band on the positive side, 0 < t < 0.25, which gives a skin of cubes over the surface.

The band doesn't leave gaps. Each wave changes by at most π/15, about 0.21, from one cell to the next, which is less than the 0.25 of the band. So along any row of cells that crosses the surface, the first cell past it is still inside the band.

The holes in the screenshot belong to the surface itself. sin x + sin y + sin z = 0 is the same, with the waves shifted, as cos x + cos y + cos z = 0, which is the usual approximation to the Schwarz P surface: a surface that repeats in all three directions, made of tubes that join up in a cubic lattice. Here the waves are slightly different lengths, so it's a stretched one, sliding through the grid.

Expanding & shrinking sphere (blobs2)

The two blobs2 programs use a more general test: an isosurface. You give it a function f(x, y, z) that's negative inside the shape and positive outside, and it finds the cells the surface passes through. It's wrapped up in a class, IsoObject, and the function is a sphere:

  double f(double x, double y, double z)
  {
    return x*x + y*y + z*z - f_size*f_size;
  }

  //---- IsSurface(x, y, z) - returns whether this cube contains a portion of the surface of the object

  bool IsSurface(double x, double y, double z)
  {
    bool p0 = f(x      , y      , z      ) < 0;
    bool p1 = f(x+scale, y      , z      ) < 0;
    ...
    bool p7 = f(x+scale, y+scale, z+scale) < 0;

    return !(p0 == p1 && p0 == p2 && p0 == p3 && p0 == p4 && p0 == p5 && p0 == p6 && p0 == p7);
  }

f is negative inside a sphere of radius f_size and positive outside. IsSurface checks the eight corners of a cell. If they're all inside, the cell is buried in the sphere, and if they're all outside, it's empty space. Either way it isn't drawn. If some are inside and some are outside, the surface must pass through the cell, so it gets a cube. Here's the same test in two dimensions, with four corners to a cell:

This is the same first step as marching cubes, which uses the inside and outside pattern of a cell's eight corners to choose which triangles to draw. Here we simply draw the whole cell. Unlike the band in Blob function, it doesn't depend on how steep the function is, and the cubes always make a closed shell.

Draw goes through the whole box, 30 cells along each side in this program, tests every cell, and colours each cube by where it is in the box:

    f_size = 10.0 + 6.0*sin(GetTickCount()*0.0003);

    ...

    double s = scale * 0.1;

    ...

        for(i=0; i<cx; i++)
        {
          if(IsSurface(x, y, z)) oglcube(x+s, y+s, z+s, x+scale-s, y+scale-s, z+scale-s, (1.0*i)/cx, (1.0*j)/cy, (1.0*k)/cz);
          x += scale;
        }

The radius is 10 + 6 sin(0.0003t), with t the clock in milliseconds, so it grows from 4 to 16 and back about every 21 seconds. The box goes from −15 to 15, so only right at its biggest does the sphere push through the sides.

The colour is (i/30, j/30, k/30): red goes up from left to right, green from bottom to top and blue from back to front. It's the RGB colour cube laid over the box, so the sphere is dark towards the (−, −, −) corner and pale towards the (+, +, +) corner, and the side facing you at the start is light blue and purple.

The cubes are 1 unit wide, but each one is shrunk by s = 0.1 on every side, so there's a gap of 0.2 between neighbours and you can see each cube on its own. The sphere is centred on a grid line, so the columns of cubes either side of the middle are mirror images, always at the same depth. Where the shell faces you, the gaps between them run straight through into the dark inside, which shows as a thin dark cross.

The camera is fixed 50 units back, far enough to keep the whole box in view.

Blobs2

Blobs2 uses the same sphere in a smaller box, 20 cells across, with no gap between the cubes (s is 0), so the shell is solid. This is the one the demo starts with.

The radius still goes from 4 to 16, but the box only goes from −10 to 10, so for half of each cycle the sphere is bigger than the box. Where it pushes out through a side, the cells there are completely inside the sphere, so nothing is drawn and a round hole opens in the middle of the face, of radius √(R² − 10²). At R = 16 the holes have a radius of 12.5 and run into each other across the edges of the box, which are only 14.1 from the centre. All that's left is eight curved pieces in the corners, which are √300, about 17.3, away. Through a hole you see the inside of the far side of the shell.

The other change is the camera. GameMain moves it in and out using the same sine as the radius:

  glTranslatef(0.f, 0.f, (-10.0 + 6.0*sin(GetTickCount()*0.0003))*2);

If we call the sine s, the radius is R = 10 + 6s and the distance from the camera to the centre is 20 − 12s, which works out as 40 − 2R:

So the camera moves the opposite way to the sphere: as the sphere grows, the camera comes in to meet it. Once the radius is past 40/3, about 13.3, the camera is inside the sphere, and that's true for about a third of each cycle. At the closest it's inside the box too, looking at the inside of the shell from within. Then it pulls back out as the sphere shrinks to a small ball in the distance.

Timing

There are two clocks in these programs, and they behave differently.

The blobs1 patterns move with the frame counter p, a static variable in draw that goes up by one every time it's called. The main loop draws frames as fast as it can, so how fast the slabs slide and the waves drift depends on the machine: a faster graphics card simply plays the animation faster.

Everything else uses GetTickCount(), the number of milliseconds since Windows started: the colour rings in blobs1, and the sphere and the camera in blobs2. Those run at the same speed on any machine, but each run starts at a different point in the cycle, depending on how long the machine has been on.

Controls

The mouse turns the grid. While the left button is held, every mouse move adds the distance moved to two angles, r1 and r2:

    case WM_LBUTTONDOWN:
      lbutton = TRUE;
      SetCapture(hWnd);
      return 0;

    ...

    case WM_MOUSEMOVE:
      POINT pt;
      GetCursorPos(&pt);

      if(lbutton) {
        r1 += (mx-pt.x);
        r2 += (my-pt.y);
      }

      mx = pt.x;
      my = pt.y;

      return 0;

GameMain turns the scene by −r2 × 0.2 degrees about the x axis and −r1 × 0.2 degrees about the y axis, so a drag of 450 pixels turns it 90 degrees. SetCapture keeps the drag going when the mouse leaves the window.

Stepping cubes

Testing every cell of the box is simple, but most of the cells are nowhere near the surface. The blobs2 source files also have the start of a smarter way, under the heading STEPPING CUBES, which follows the surface instead. GameDraw never calls it, so it isn't part of what you see.

It starts at the centre and steps up the y axis until it finds a surface cell. Then it spreads out from there a layer at a time. For each cube found in the last step it checks the cells around it, and any that are on the surface and haven't been seen yet are queued for the next step:

    while(q[0]->Next(&x, &y, &z))
    {
      //  Check all the cubes around this one
      int i, j, k;
      for(i=-1; i<=1; i++) for(j=-1; j<=1; j++) for(k=-1; k<=1; k++) if(i+j+k == 1 || i+j+k == -1)
        queuecube(x+i, y+j, z+k);
    }

    //  Shuffle queues so that q[0] is the neighbour

    Queue *qq = q[0];
    q[0] = q[1];
    q[1] = q[2];
    q[2] = qq;

The condition i+j+k == 1 || i+j+k == -1 picks 12 of the 26 neighbours: the 6 that share a face, and 6 of the 8 that only share a corner. The three queues hold the previous step, the current one and the next, and a new cell is only checked against those, rather than against every cube found so far. That works because the front only ever moves outwards across the surface.

The surface it follows is a different function from the sphere, in the same file: ten metaballs, each adding 1/d for the distance d to its centre, with the surface where the total is 0.65. The values are kept in a small hash table, since every corner is shared by eight cells, and the number of cubes is capped by maxcubes, set to 55. The blobs1 files have a first version of the queue and a single 1/d function, which aren't used for drawing either.

The WebGL version

The demo at the top runs all five programs in the browser, with a button for each. It's a straight port of test.cpp and the framework into JavaScript and WebGL, doing the same steps in the same order.

WebGL has no glBegin and glEnd, so the port keeps one vertex buffer and its oglcube writes into that instead. Each four-vertex fan becomes two triangles, and each vertex gets its position and the current colour:

  function fan( ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz )
  {
    vertex( ax, ay, az ); vertex( bx, by, bz ); vertex( cx, cy, cz );
    vertex( ax, ay, az ); vertex( cx, cy, cz ); vertex( dx, dy, dz );
  }

A vertex is three floats and four colour bytes, 16 bytes, and a cube is 36 vertices, so the 2,000 or so cubes of a diagonal frame come to about 1.1MB. The whole frame is built into one buffer, in the same order the original drew the cubes, then sent to the graphics card and drawn in one go:

      gl.bufferSubData( gl.ARRAY_BUFFER, 0, bytes.subarray( 0, used ) );
      gl.drawArrays( gl.TRIANGLES, 0, count );

Turning a colour into a byte clamps it to 0 to 255, which does what the fixed pipeline did with the colours over 1.0 from the rings. The shaders hardly do anything, since there's no lighting: the vertex shader applies the matrix and the fragment shader outputs the vertex's colour:

attribute vec3 aPos;
attribute vec4 aCol;
uniform mat4 uMVP;
varying vec4 vCol;
void main() { vCol = aCol; gl_Position = uMVP * vec4( aPos, 1.0 ); }

precision mediump float;
varying vec4 vCol;
void main() { gl_FragColor = vCol; }

The matrix is built the same way as in GameMain: gluPerspective(60, ...) with the near plane at 1 and the far plane at 30000, then the translate and the two rotations. The canvas keeps the shape of the original window's 792x573 client area, and drags are measured in that window's pixels, so a drag across the canvas turns the grid as far as a drag across the original window did, whatever size it's shown at.

The port takes two short cuts that give exactly the same cubes. Blob function's sines each depend on only one coordinate, so it works out the 40 values for each axis once a frame rather than three sines for each of the 64,000 cells. The sphere programs work out f once for each corner of the grid and count the inside corners of each cell, where the original worked out all eight corners again for every cell.

A few things can't be quite the same:

• The frame counter. The originals stepped p once a frame, as fast as the machine could go. The port steps it 60 times a second, so the slabs and waves move at a steady speed.
• The clock. GetTickCount() started at however long the machine had been on, so each run began somewhere different in its cycle. The port starts the clock at 0 when you pick a program, except for Blobs2, which starts 10.3 seconds in, with the sphere just poking out of the box and the camera pulling back, so you see its near side first.
• Colour depth. The originals asked for a 16-bit colour buffer and a 16-bit depth buffer. The browser draws with 8 bits per channel, so the shades are a little smoother.
• Escape. It closed the original window, but a web page can't close its own tab, so here it does nothing.