使用行进方块绘制形状

1. Introduction

The Marching Squares algorithm is a computer graphics algorithm introduced in the 1980s that can be used for contouring. We can use the Marching Squares algorithm to draw the lines of constant:

• altitude on a topographical map
• temperature on a temperature heat map
• pressure on a contour map for a pressure field

In this tutorial, we’ll learn how the Marching Squares algorithm determines the contour from a grid of sample points of the image.

2. Contour Curves and Level Curves

Let’s spend a brief moment understanding the mathematically precise definition of contour lines.

2.1. Mathematical Definition

We have been drawing graphs of functions of one-variable such as or implicit functions like for so long, that we give the matter little thought. Plotting functions of two variables is a much more difficult task.

The trick to putting together a reasonable graph of a function of two or more variables is to find a way to cut down on the dimensions involved. One way to achieve this is to draw certain special curves that lie on the surface . These special curves, called contour curves, are obtained by intersecting the surface with horizontal planes for various values of the constant .

These curves in the -plane are called the level curves of the original function .

The level curve at height of any function is the curve in defined by the equation , where is a constant. In mathematical notation,

   

2.2. Examples

Consider the function defined as:

   

By definition, the level curve at height is:

   

Thus, we see that the level curves for are circles centered at the origin of radius . They are summarized in the table below:

The family of level curves, the “topographic map” of the surface is shown in the figure below:

If we stack all level curves together, we can get a feeling for the complete graph of . It’s a surface that looks like an inverted dish and is called a paraboloid:

For our discussion, we require the output contour to possess the following properties:

• It must separate the interior points from the exterior points.
• Thus, it must be an orientable and closed curve.

3. Essentials of the Algorithm

Consider the simplistic image of a cloud given below. We are interested to trace the contours of the cloud:

For simplicity, let’s assume that the image of a cloud is represented by a square matrix of pixels. Each pixel value represents a single sample of light, carrying brightness information. It ranges between and . Black is represented by and white by .

3.1. Sampling the Image

We divide the entire image domain into squares. Each square has dimensions by . We sample the image at each of the grid points:

Next, we iterate through the grid to determine the vertex state in comparison to an iso-value . Each grid vertex is now assigned a binary state ( or ). An iso-value serves as a threshold for determining the vertex state. Suppose we choose as the threshold. The vertex state is determined as follows:

• – Pixel value less than the iso-value
• – Pixel value greater than the iso-value

The resulting binary grid , thus obtained is:

3.2. Configuration of Each Sub-Grid

Next, a subgrid can be associated with a configuration. We iterate through . At each sub-grid, we form a binary code based on the vertex value by iterating clockwise from the top-left corner to the bottom-left corner.

For example, if a given subgrid has four corners:

its binary code is said to be . The equivalent of the binary code in the decimal number system is called the configuration of the sub-grid. In the above example, the sub-grid has the configuration Thus, we have a configuration associated with each sub-grid as follows:

3.3. Lookup Table for the Contours

Imagine a single square with the contours of an object cutting through this square. That is, the square does not lie wholly in the interior or exterior of the object. A square has edges and for each edge, we have possible choices – either the contour(boundary) intersects this edge, or it does not. This results in possible configurations.

The configuration of each sub-grid is matched with one entry in the contours lookup table below:

The contours lookup table is intuitive. As mentioned before, there are possible configurations.

Let’s consider the configuration :

We think of the purple region as the interior of an object, and the blue region as the exterior of the object. We denote the state by a black vertex and the state by a white vertex. We define a bipolar pair to be two vertices in opposite states.

Intuitively, the contour of an object must intersect the edge of a bipolar pair. Thus, the configuration must correspond to an object whose contour intersects the top and left edges of the square. In this fashion, the contours in each sub-grid are approximated, as shown in the figure below:

4. Algorithm

The Marching Squares algorithm can be divided into two steps:

1. Sampling the grid points and converting them to a binary matrix .
2. March the squares in and build a set of edges .

Let’s see the pseudocode:

algorithm MarchingSquares(G, m, n, σ, stepX, stepY):
    // INPUT
    //    G = an m x n matrix of scalar values
    //    stepX = the sampling resolution in the x direction
    //    stepY = the sampling resolution in the y direction
    //    σ = an isovalue
    // OUTPUT
    //    γ = a set of contour lines

    F, coord, p, q <- SampleGrid(G, m, n, σ, stepX, stepY)
    γ <- March(F, coord, p, q)

    return γ

4.1. Sampling the Grid

The input to the Marching Squares algorithm is some sample of the original matrix . The parameters and control the resolution of the sample. For example, if and , we select the sequence of pixel-values:

   

The result of this operation should yield a matrix of size rows and columns.

Each selected pixel value is compared with the iso-value and converted to a bit-value or . is used to hold the bit matrix. The actual -coordinates of each pixel in the sample , concerning the original matrix is stored as a named tuple in a matrix .

For example, if , , we would find , .

Let’s see the pseudocode now:

algorithm SampleGrid(G, m, n, σ, stepX, stepY):
    // INPUT
    //    G = an m x n matrix of scalar values
    //    m = number of rows in the matrix G
    //    n = number of columns in the matrix G
    //    σ = an isovalue
    //    stepX = sampling resolution along the X-axis
    //    stepY = sampling resolution along the Y-axis
    // OUTPUT
    //    F = binary field
    //    coord = named tuple (x, y) indicating each pixel's position in the sample
    //    p = number of rows in the resulting matrix after sampling
    //    q = number of columns in the resulting matrix after sampling

    // Create a zero matrix to hold the binary field and xy-coordinates
    p <- m / stepX
    q <- n / stepY
    F <- zero matrix of size p x q
    coord <- zero matrix of size p x q

    // Sample the grid points
    for i <- 0 to p - 1:
        for j <- 0 to q - 1:
            if G[i * stepY, j * stepX] > σ:
                F[i, j] <- 0
            else:
                F[i, j] <- 1
            // Each entry in coord matrix is a named tuple (x, y)
            coord[i, j] <- (x = j * stepX, y = i * stepY)

    return F, coord, p, q

4.2. Marching the Squares In

Next, we march the squares in the binary grid . Each square in , beginning with its top-left corner, has vertices, in clockwise order : , , and . We compute the reference value of each square. We also compute the mid-points of each square edge: north, east, south, and west. Finally, we determine the contour by searching the reference value in the contours lookup table:

algorithm March(F, Coord, p, q):
    // INPUT
    //    F = the binary field matrix
    //    Coord = the matrix of coordinates
    //    p = the number of rows in F
    //    q = the number of columns in F
    // OUTPUT
    //    γ = a set of contour lines

    γ <- an empty set

    // Compute the reference value for each grid square and lookup in the isocontour table
    for i <- 0 to p - 2:
        for j <- 0 to q - 2:
            a <- Coord[i, j]
            b <- Coord[i, j + 1]
            c <- Coord[i + 1, j + 1]
            d <- Coord[i + 1, j]

            k <- 8 * F[i, j] + 4 * F[i, j + 1] + 2 * F[i + 1, j + 1] + F[i + 1, j]

            // Compute isocontour vertex coordinates
            north <- (a.x + b.x / 2, a.y)
            east <- (b.x, (b.y + c.y) / 2)
            south <- ((d.x + c.x) / 2, d.y)
            west <- (a.x, (a.y + d.y) / 2)

            S <- LUT(k, north, east, south, west)
            γ <- γ + S

    return γ

Here’s a topographical map of the Mont Blanc region in the Swiss Alps. The Marching Squares algorithm when executed on this image produces nice contours around the mountain peaks:

5. Conclusion

In this article, we learned about an interesting Computer Graphics algorithm called the Marching Squares. To summarize, it is based on two core ideas. First, the contours can be constructed piecewise within each grid square, without reference to other squares. Second, each isocontour segment in a grid square can be retrieved from a lookup table.