Crate marching_squares_wgpu 

A GPU Implementation of the Marching Squares algorithm using wgpu.

To use this library, you need to have a working wgpu environment.

First, you need to create a wgpu::Device and a wgpu::Queue to run the compute shaders.

Then, you can create a MarchingSquares instance with the specified surface dimensions width and height, and the surface texture view. You can then call the MarchingSquares::compute_contour method with the desired isovalue to obtain the contour as an IsoContour.

Concept

The Marching Squares algorithm is a method to extract a contour from a 2D scalar field.

In general, a scalar field can be described as a function $f: \mathbb{R}^2 \to \mathbb{R}$. We can define the level set of $f$ at a given value $c \in \mathbb{R}$ as:

$$ \mathcal{S}_c = \{ (x, y) \in \mathbb{R}^2 \mid f(x, y) = c \} $$

If we assume that $f$ is continuous, then this level-set $\mathcal{S}_c$ will be a continuous curve that we call the contour of $f$ at the value $c$. The Marching Squares algorithm approximates this curve by dividing the domain of $f$ into a grid of squares, and then analyzing each square to determine the contour.

Practical uses

Of course, you don’t need to define your data as a mathematical function. If you have any kind of 2D data that can be represented as a grid of values, such as an image, a heightmap, or a temperature map, you can use this algorithm to extract the contours of that data at defined levels. The quality of the calculated contour will, of course, depend on the resolution of the grid and the nature of the data. If, for example, the data is very noisy, the contour will look very jagged.

The main use-case of this library is for real-time visualization of 2D data, such as in scientific simulations or videogames. Therefore, you will probably have an event loop set up in such a way that the contour is calculated on a frame-by-frame basis, and then rendered to the screen.

Example

Let’s consider the following example of a scalar field $f(x, y) = x^2 + y^2$. The contour of this field at the value $c = 1$ is a circle of radius $1$ centered at the origin.

use marching_squares_wgpu::{MarchingSquares, SurfaceDimensions};
use wgpu::{Device, Queue, TextureView};

// Assume we have a `device` and a `queue` already created
async fn calculate_contour(device: &Device, queue: &Queue) {
 // To create a Marching Squares instance with a surface of dimensions 256x256,
 // we first need to create a texture with the scalar field data.
 let width = 256;
 let height = 256;
 let mut data = vec![0.0; (width * height) as usize];
 let f = |x, y| {
     // f(x,y) = x^2 + y^2
     let x = x as f32 / width as f32 - 0.5;
     let y = y as f32 / height as f32 - 0.5;
     x * x + y * y
 }
 for y in 0..height {
     for x in 0..width {
         data[(y * width + x) as usize] = f(x, y);
     }
 }
 // Create the texture with the scalar field data
 let texture = device.create_texture_with_data(
    queue,
    &TextureDescriptor {
        label: Some("2D Surface Texture"),
        size: Extent3d {
            width,
            height,
            depth_or_array_layers: 1,
        },
        mip_level_count: 1,
        sample_count: 1,
        dimension: TextureDimension::D2,
        format: TextureFormat::R32Float,
        usage: TextureUsages::COPY_DST | TextureUsages::TEXTURE_BINDING,
        view_formats: &[TextureFormat::R32Float],
    },
    TextureDataOrder::LayerMajor,
    bytemuck::cast_slice(data),
 );
 let surface_texture_view = texture.create_view(&TextureViewDescriptor::default());
 let surface = SurfaceDimensions::new([width, height]);
 let marching_squares = MarchingSquares::new(device, surface, surface_texture_view);
 let r = 1.0;
 // Compute the contour at the isovalue `r`
 let contour = marching_squares.compute_contour(device, queue, r).await;
 // Remember that this might return `None` if there are no active pixels
 if let Some(contour) = contour {
   // Show vertices
   for vertex in contour.vertices.iter() {
     println!("{:?}", vertex);
   }
   // In practice, you would render these vertices to the screen
 }
}

Structs

IsoContour

Contains the isocontour obtained as a result of the Marching Squares algorithm.

MarchingSquares

The main struct for the Marching Squares algorithm.

SurfaceDimensions

Description of the surface’s dimensions, i.e. its width and height.