The Marching Squares algorithm is a computer graphics technique used to generate contours for a two-dimensional scalar field, which is essentially a grid of numerical values. It’s akin to the 3D Marching Cubes algorithm, but simplified for 2D space. The algorithm is particularly useful in applications like creating topographic maps or weather maps, where contour lines or isobars are needed to represent different data levels.
Here’s a concise explanation of how the Marching Squares algorithm works:
Thresholding: First, a threshold is applied to the 2D field to create a binary image. This image has a value of 1 where the data value is above a certain isovalue (the threshold), and 0 where it’s below.
Grid Formation: The binary image is divided into a grid of 2x2 pixel blocks, each forming a cell for contouring. The grid of cells is one cell smaller in each direction than the original field.
Cell Indexing: For each cell, the four corner values are used to create a 4-bit index. This is done by walking around the cell in a clockwise direction and appending the bit to the index.
Lookup Table: The 4-bit index corresponds to one of 16 possible values and is used to access a pre-built lookup table. This table lists the edges needed to represent the contour for that cell.
Look up the contour lines and put them in the grid
Linear Interpolation: The exact position of the contour line along the edges of the cell is determined by linear interpolation between the original field data values.
Saddle Points: At points where the contour is ambiguous, known as saddle points, the algorithm uses the average data value for the center of the cell to resolve the ambiguity.
Isobands: If filled contour bands are needed, the algorithm can be adjusted to work within upper and lower threshold values to create isobands.
The beauty of the Marching Squares algorithm lies in its simplicity and efficiency. It processes each cell independently, making it highly parallelizable and suitable for real-time applications. The use of a lookup table accelerates the contouring process, as it avoids complex calculations during runtime.
class GRIDCELL {
constructor(field, rez, interpolation = true) {
this.field = field;
this.rez = rez;
this.interpolation = interpolation; // if set to true, interpolate the intersection using the scalar values at vertices, otherwise take mid-point
this.squareIndex = 0;
this.val = new Array(4); // array to hold the scalar values at the 4 corners
this.e = [
new Vector2(),
new Vector2(),
new Vector2(),
new Vector2()
]
}
march(threshold, i,j) {
this.val[0] = this.field[i ][j ];
this.val[1] = this.field[i + 1][j ];
this.val[2] = this.field[i + 1][j + 1];
this.val[3] = this.field[i ][j + 1];
// calculate the square index, used to determine which edg(s) are interescting
this.squareIndex = 0;
if (this.val[0] < threshold) this.squareIndex |= 8;
if (this.val[1] < threshold) this.squareIndex |= 4;
if (this.val[2] < threshold) this.squareIndex |= 2;
if (this.val[3] < threshold) this.squareIndex |= 1;
// now calculate the ends of the intersecting lines
var rez = this.rez;
var x = i * rez, y = j * rez;
if (!this.interpolation) {
this.e[0].set(x + rez * 0.5, y );
this.e[1].set(x + rez, y + rez * 0.5);
this.e[2].set(x + rez * 0.5, y + rez );
this.e[3].set(x, y + rez * 0.5);
}
else
{
var v0 = this.val[0];
var v1 = this.val[1];
var v2 = this.val[2];
var v3 = this.val[3];
this.e[0].set(x + rez * lerp(threshold, v0, v1), y );
this.e[1].set(x + rez, y + rez * lerp(threshold, v1, v2));
this.e[2].set(x + rez * lerp(threshold, v3, v2), y + rez );
this.e[3].set(x, y + rez * lerp(threshold, v0, v3));
}
}
}create the field
field = [];
rez = 10;
cols = 1 + width / rez;
rows = 1 + height / rez;
field = Array.from(Array(cols), ()=> new Array(rows)); // create empty field array[cols][rows]
threshold = 1;
// instantiate the square to be marched!
grid = new GRIDCELL(
field, // this is the array that contains the scalar values at the sampling points
rez, // resolution of sampling
true // interpolate or not?
);March the Square
for (let i = 0; i < cols - 1; i++) {
for (let j = 0; j < rows - 1; j++) {
grid.march(threshold, i,j);
var squareIndex = grid.squareIndex;
// find out which edges the intersecting line(s) connect, by looking up from table, then draw the line
for (let i = 0; table[squareIndex][i] !== -1; i+=2) {
var p1 = grid.e[ table[squareIndex][i] ]
var p2 = grid.e[ table[squareIndex][i+1] ]
drawLine(p1, p2)
}
}
}Table
table = [
[-1,-1], // case 0
[2,3,-1,-1], // case 1: intersection line from edge 2 to edge 3
[1,2,-1,-1],// case 2: intersection line from edge 1 to edge 2
[1,3,-1,-1],// case 3
[0,1,-1,-1],// case 4
[0,3,1,2,-1,-1],// case 5: intersection lines from edge 0 to edge 3 and edge 1 to edge 2
[0,2,-1,-1],// case 6
[0,3,-1,-1],// case 7
[0,3,-1,-1],// case 8
[0,2,-1,-1],// case 9
[0,1,2,3,-1,-1],// case 10
[0,1,-1,-1],// case 11
[1,3,-1,-1],// case 12
[1,2,-1,-1],// case 13
[2,3,-1,-1],// case 14
[-1,-1],// case 15
]
METAL BALLS
Preparation
function create() {
graphics = this.add.graphics();
balls = [];
for (let i = 0; i < 16; i++) {
var radius = random(40, 60);
var b = new Ball(
random(radius, width - radius),
random(radius, height - radius),
radius
)
balls.push(b);
Phaser.Math.RandomXY(b.vel);
}
field = [];
rez = 10;
cols = 1 + width / rez;
rows = 1 + height / rez;
field = Array.from(Array(cols), ()=> new Array(rows)); // create empty field array[cols][rows]
threshold = 1;
// instantiate the square to be marched!
grid = new GRIDCELL(
field, // this is the array that contains the scalar values at the sampling points
rez, // resolution of sampling
true // interpolate or not?
);
}
Main Loop
function update() {
graphics.clear();
// update the scalar values in the field
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
let sum = 0;
let x = i * rez;
let y = j * rez;
for (let b of balls) {
sum += (b.r b.r) / ((x - b.pos.x) (x - b.pos.x) + (y - b.pos.y) * (y - b.pos.y));
}
field[i][j] = sum;
}
}
for (let b of balls) {
b.update();
b.show();
}
for (let i = 0; i < cols - 1; i++) {
for (let j = 0; j < rows - 1; j++) {
grid.march(threshold, i,j);
var squareIndex = grid.squareIndex;
// find out which edges the intersecting line(s) connect, by looking up from table, then draw the line
for (let i = 0; table[squareIndex][i] !== -1; i+=2) {
var p1 = grid.e[ table[squareIndex][i] ]
var p2 = grid.e[ table[squareIndex][i+1] ]
drawLine(p1, p2)
}
}
}
}
CodePen
Useful References
Comments