ピクセルを滑らかなカタチに。～marching squares法～

# n: 正方形ピクセル画像の縦横ピクセル数
# p: 各ノードの値(0or1)(ex n=64のときpは1024個のリストデータ)

def convert_to_matrix(n, p):
    matrix = []
    for i in range(n):
        row = p[i*n:(i+1)*n]
        matrix.append(row)
    return matrix

def calculate_p_values_as_int(n, p):
    # 一次元リストを二次元行列に変換
    p_matrix = convert_to_matrix(n, p)

    results = []
    for i in range(n-1):
        for j in range(n-1):
            # 4ビットのバイナリ数値を文字列として取得
            binary_str = f"{p_matrix[i][j]}{p_matrix[i][j+1]}{p_matrix[i+1][j+1]}{p_matrix[i+1][j]}"
            # バイナリ文字列を整数に変換
            int_value = int(binary_str, 2)
            results.append(int_value)
    return results

#各輪郭セルのバイナリ値（0~15）
results = calculate_p_values_as_int(n, p)
print(results)

idea

We are a company that is constantly exploring "shapes". While understanding shapes that already exist in the world, we continue to research how to create shapes that do not yet exist. In the process of investigating computer-based shape generation as a way to create such new shapes, we came across a method called marching cubes.

Marching cubes[1] is a computer graphics algorithm announced by Lorensen and Cline in 1987 that extracts a polygonal mesh of isosurfaces from a three-dimensional discrete scalar field. This algorithm is mainly used for medical visualization such as CT and MRI scan data images.

Although marching cubes is an algorithm intended to be used in 3D, it can also be applied to 2D, in which case it is called marching squares.

A typical example of the use of marching squares is drawing isobars on weather maps and contour lines on maps. Based on discrete information mapped in a grid on a map, it estimates smooth changes in atmospheric pressure and displays them overlaid on the map. Marching squares is a lightweight technology that can instantly convert ever-changing atmospheric pressure measurements and deliver images that are easy for observers to understand.

Marching squares is already a widely used technology, but this time I will implement the process from scratch on Grasshopper in Rhinoceross to understand the algorithm and play around with processing and generating various images.

Research

First, let's start by understanding the algorithm of the marching squares method.
There was a very easy-to-understand explanation on Wikipedia [2], so I will quote it with some additional information.

Steps of the algorithm

① Data binarization
The 2D scalar field values ​​are binarized using a reference value (threshold) to create a black and white pixel image.

• If it is equal to or greater than the reference value, it is set to "1".
• If it is less than the reference value, it is set to "0".

② Creating a contour cell
For each 2x2 block of the binarized image, one "contour cell" is created. This contour cell grid is one cell smaller in each direction than the original 2D scalar field. (In the image below, we originally had a 55 discrete scalar field, but this process changes it to a 44 grid.)

【From here, we process each cell individually】

③ Determining the cell index
Create a cell index by going around the four corners of the contour cell (which hold binary values ​​1 or 0) in a clockwise direction. This index is a 4-bit value that represents one of 16 possible states from 0 to 15.

④ Referencing the lookup table
The generated index is used to refer to a lookup table prepared in advance. The lookup table specifies which side of the cell the contour line should pass through. Only the 16 basic shapes listed in this lookup table are used in marching square.

⑤ Linear Interpolation
On the edge of the cell, the exact position of the contour is corrected by linear interpolation using the original 2D scalar field value. This allows you to deform the 16 basic types and obtain a smoother boundary line.

After executing ① and ②, ③ to ⑤ are processed in order for each cell to draw the boundary line representing the isoline.

The process of processing the 16 shape patterns by making them correspond to 4-bit binary is the cute part.

Build

There is a slight difference between state ④, which expresses the boundary line using 16 basic shapes, and state ⑤, which has linear interpolation applied, as confirmed in the procedure of the marching squares algorithm, so we will divide the execution stage of marching squares into the following three states.

state	name	description
1	marching squares threshold	The state binarized by threshold. The pixel art state.
2	marching squares 16 pattern	The state in which 16 basic shapes corresponding to the cell index are assigned. It is possible to have a 45-degree boundary line relative to the grid, improving expressiveness.
3	marching squares linear interpolation	Linear interpolation is applied using the value of the scalar field before it is decomposed into a threshold value. Smooth boundary lines can be expressed.

16 basic shapes

16 basic shapes were modeled as solid polysurfaces on rhino. Since 2D image processing is assumed, the height is temporarily set to 1. Looking at the diagram below, it looks like there are only 15 types, but the "empty space in the upper left" is also counted as one of the states that represent the shape, so there are a total of 16 types.

In state 2 processing, the shape is reproduced by arranging these 16 blocks like building blocks.

Binary operations

Binary operations on Grasshopper were processed as python code in the Python Script component. The binary values ​​(0 or 1) of the four nodes around the cell are lined up, read as a 4-bit number, and output as a decimal number from 0 to 15. Select the block corresponding to this number from the group of shapes mentioned earlier and place it at the cell position to create a shape with marching squares applied.

Python 3 Script

# n: Number of pixels in the width and height of a square pixel image
# p: Value of each node (0 or 1) (ex. when n=64, p is 1024 list data)

def convert_to_matrix(n, p):
matrix = []
for i in range(n):
row = p[i*n:(i+1)*n]
matrix.append(row)
return matrix

def calculate_p_values_as_int(n, p):
# Convert one-dimensional list to two-dimensional matrix
p_matrix = convert_to_matrix(n, p)

results = []
for i in range(n-1):
for j in range(n-1):
# Get 4-bit binary value as string
binary_str = f"{p_matrix[i][j]}{p_matrix[i][j+1]}{p_matrix[i+1][j+1]}{p_matrix[i+1][j]}"
# Convert binary string to integer
int_value = int(binary_str, 2)
results.append(int_value)
return results
# Binary value of each contour cell (0~15)
results = calculate_p_values_as_int(n, p)
print(results)

Linear Interpolation

By applying linear interpolation in algorithm ⑤, the output image can be made smoother. As an example of linear interpolation, the processing for a certain cell (4-bit binary value "0110") is shown in the figure below.

First, the leftmost shape is the state in which the value of each node has been converted to a binary value of 01 using a threshold value of 0.5 for the scalar field. For this cell, reading the binary value of the nodes clockwise from the top left gives "0110". Since "0110" corresponds to the block "6" when read in decimal, this block is placed. The shape of A in the center of the image represents this, and the execution stage of the algorithm is state 2.

After obtaining the shape of A, for the corners halfway between 0 and 1, the scalar values ​​before classification with the threshold value (here, 0.1, 0.6, 0.9, 0.4) are used to linearly interpolate to infer the coordinates of the threshold value (0.5), and the shape is deformed. The shape of B obtained from this becomes state 3 in the execution stage of the algorithm.

Execution test

By combining the elements constructed above, we created an execution environment for the Marching Squares method on Grasshopper.

Below are examples of using it, including ① an example of Converting the boundaries of a pixel image to smooth and ② an example of visualizing the contours of a randomly generated scalar field.

① Converting the boundaries of a pixel image to smooth

Here, we show the process of applying marching squares to various 64x64 pixel images, in three execution stages. From the left, they are arranged in the order of state1, state2, and state3.

The boundaries of each image become smoother and more beautiful as you go to the right. The pixel art on the far left cannot express shapes thinner than the size of one cell, but the image on the far right expresses even the thin parts properly (the Nemuro Peninsula in Hokkaido is beautifully expressed). Also, the round tire shape of a car or the curved shapes of a penguin may look unnatural when expressed in pixels, but by applying marching squares, you can create a natural smoothness.

Comparison with grayscale image

In the above image processing, when converting from state 2 to state 3, a scalar value between 0 and 1 is given to each node as information on the original image. Let's compare the grayscale image drawn by corresponding this scalar value to the luminosity and the result of extracting the boundary by applying marching squares from it.

The image below is an enlarged view of the penguin's fin. In the grayscale image on the left, the right-angled boundaries of the pixels are noticeable and do not look like a natural fin shape. On the other hand, the image overlaid on the right by marching squares has the same amount of information, but the smooth shape is easier to observe with the human eye.

② Contour visualization of randomly generated scalar fields

Next, we will show an example of constructing a scalar field by giving random values ​​to a 64x64 grid and running marching squares on that scalar field. An averaging filter is applied to the scalar field, and a gif was created to show how the change in random values ​​is smoothed out by gradually increasing the filter strength.

It starts with the finest pattern and gradually changes to a larger, clumpy pattern. This image itself has no physical meaning, but if we give meaning to the scalar field, we can expect it to generate useful shapes.

Next, I used a constant averaging filter to create a gif of the image when the original random seed value was assigned. This gives a variety of images with similar shape granularity.

To me, it looks like it is generating countless maps of continents that don't exist, but what will you create?

Extra

At the beginning, I explained that marching squares is a 2D version of marching cubes. Here, I will briefly summarize the results of my attempt at marching cubes.

In marching cubes, one cell of marching squares is expanded into a cubic lattice and has eight vertices. The basic shapes expressed by the 0s and 1s of these points are 256 shapes obtained by rotating the 30 figures in the figure below on the XYZ axes and removing duplicates. This is equal to the total 256 ways that the 8-bit binary value created by the binary values ​​of the eight vertices can express, from 0 to 255.

Below are some shapes, with the correct data to be expressed, a voxel representation using only cubes, and a representation using 256 basic shape blocks equivalent to state 2 of marching cubes.

Even when using 256 blocks for three-dimensional shapes, it was difficult to achieve a smooth expression. Linear interpolation is possible in three-dimensional space as in two-dimensional space, but the implementation in Grasshopper seems to be quite complicated, so this time we only worked up to state 2, but I think you can get a glimpse of the effect of marching cubes.

Review

This time, I used the marching squares method to create smooth boundaries from pixel images and create new boundaries from randomly generated scalar fields. The marching squares method itself can be said to simply process grayscale images to make boundaries easier to see, but when people see the smooth output shape, their perception and impression changes significantly, so I think there will be differences in the information and ideas that can be obtained from it.

Software used

[1] Rhino 8, Grasshopper

References, sites

[1] https://dl.acm.org/doi/10.1145/37402.37422
[2] https://en.wikipedia.org/wiki/Marching_squares
[3] https://www.youtube.com/watch?v=0ZONMNUKTfU&ab_channel=TheCodingTrain
[4] https://jamie-wong.com/2016/07/06/metaballs-and-webgl/
[5] https://ragingnexus.com/creative-code-lab/experiments/algorithms-marching-squares/
[6] https://www.3dbenchy.com/