Non-Marching Squares

I has looking into Marching cube algorithms for extracting meshes from volume data yesterday, and thought, as a little test, I’d try making a very simple 2D edge-detection type setup, using some of the same principles. There’s lots of stuff on the web about marching cubes, and the 2D version, marching squares, so I’m not going to go into a detailed explanation here, but to summarise my setup:

• divide the image into tiles
• for each tile, test to see if the colour/luminosity value pixel at each corner is above or below a given threshold value.
• use the results of these tests to lookup into a table.
In my case, this table is an image strip something like this (I’ve added the numbers for debugging purposes)

In the original Marching Cubes code, the logic for choosing the correct cell from the table is quite elegant. You basically create a binary number, where each digit is either a 0 or a 1, according to whether the corresponding grid-point value is above or below the threshold. Decoding the binary into an integer gives you the index into the table. Unfortunately, because GLSL doesn’t have support for binary numbers, I’ve had to kludge that a bit, but it works fine.
• draw the selected table cell into the working tile of the input image

Here’s some results.

It’s a bit glitchy around the edges of the tiles, but I’m quite pleased with it. I’ve added some controls to recolour the tiles in various ways, and to deliberately scan the corners in the wrong order, for a more abstract look.

I call this ‘non-marching cubes’ because I’m not really doing the marching bit. Variations on this technique are often used iteratively to detect, and then follow edges in an image. Tools like the Magic Wand in Photoshop use similar techniques to create selections based on colour values, for example.

Vertex Shader code for the simple black-and-white version:

uniform float CellCount;
varying vec2 cellCoords;

void main()
{
	//Transform vertex by modelview and projection matrices
	gl_Position = gl_ModelViewProjectionMatrix * gl_Vertex;
	
	//Forward current color and texture coordinates after applying texture matrix
	gl_FrontColor = gl_Color;
	gl_TexCoord[0] = gl_TextureMatrix[0] * gl_MultiTexCoord0;
	cellCoords = gl_TexCoord[0].xy * CellCount;
}

..and the Fragment Shader:

uniform sampler2D Texture, EdgeTable;
uniform vec2 CellSize;
uniform float Threshold;
uniform int Scramble;
uniform vec2 ClampAmt;  // Values for clamping edges
varying vec2 cellCoords;
const float eTableCellWidth = 1.0 / 16.0;

void main()
{
	// Cell corners (putting in vec4 allows swizzling for different tile patterns)
	vec4 corners;
	corners[0] = max(floor(cellCoords.x) * CellSize.x, ClampAmt[0]);       // Left
	corners[1] = min(ceil(cellCoords.x) *CellSize.x, 1.0 - ClampAmt[0]);   // Right
	corners[2] = max(floor(cellCoords.y) * CellSize.y, ClampAmt[0]);       // Top
	corners[3] = min(ceil(cellCoords.y) * CellSize.y, 1.0 - ClampAmt[0]);  // Bottom
	
	// Swizzle corners for different effects
	corners = (Scramble == 1) ? corners.xywz : (Scramble == 2) ? corners.yxzw : (Scramble == 3) ? corners.zwyx : corners;

	// Sample corners	
	float c0	= texture2D(Texture, vec2(corners[0], corners[2])).r;
	float c1 	= texture2D(Texture, vec2(corners[1], corners[2])).r;
	float c2 	= texture2D(Texture, vec2(corners[0], corners[3])).r;
	float c3 	= texture2D(Texture, vec2(corners[1], corners[3])).r;
	
	// Clamp coords for edge-table
	vec2 cellCoordsClamp = fract(cellCoords);
	cellCoordsClamp.x = clamp(cellCoordsClamp.x, ClampAmt[1], 1.0 - ClampAmt[1]); 
	cellCoordsClamp.y = clamp(cellCoordsClamp.y,ClampAmt[1], 1.0 - ClampAmt[1]);
	
	// Calculate index for edge-table
	// Returns 0.0 > 15.0 to index into edge-table strip
	float index = 0.0;
	index += step(Threshold, c0);
	index += step(Threshold, c1) * 2.0;
	index += step(Threshold, c2) * 4.0;
	index += step(Threshold, c3) * 8.0;
	
	// Sample edge-table and return
	vec2 ttcoords	= vec2(cellCoordsClamp.x * eTableCellWidth + (eTableCellWidth * index), cellCoordsClamp.y);
	gl_FragColor = texture2D(EdgeTable, ttcoords);
}