marching-squares-wgpu

A simple GPU-parallel implementation of the Marching Squares algorithm in Rust with wgpu.

The main inspiration for this was Will Usher's amazing blog post, GPU Compute in the Browser at the Speed of Native: WebGPU Marching Cubes. The source code here is a direct translation of the code from the blog post, but adapted to work with Marching Squares instead of Marching Cubes. Also, some work was needed to adapt the code to work with Rust and the wgpu crate. His Typescript + WebGPU code is available on his Github repo.

Also, his implementation of the Parallel Prefix Sum (or "Scan") primitive is based on Mark Harris' implementation from the book GPU Gems 3, which originally implements it in CUDA.

Explanation

Imagine you have a 2D scalar function $f: \mathbb{R}^2 \to \mathbb{R}$, and you want to visualize the set of points $\mathcal{S} = { (x, y) \in \mathbb{R}^2 \mid f(x, y) = c }$, where $c \in \mathbb{R}$ is called the "iso-value" or "contour value".

The Marching Squares algorithm is a way to approximate the contour set $\mathcal{S}$ by dividing the 2D plane into a grid of squares, and then approximating the contour set as a line segment within each square.

If $f$ is a continuous function, then the contour set $\mathcal{S}$ is a continuous curve, and the Marching Squares algorithm will approximate this curve reasonably well (the better the resolution of the grid, the better the approximation).

Repo structure

This repo contains a Cargo workspace with two crates:

• marching-squares-wgpu: the main library crate, which contains the implementation of the Marching Squares algorithm.
• rendering-example: a binary crate that uses the marching-squares-wgpu crate to render the contour set of the lemniscate of Bernoulli to the screen as a winit application. This is just a very barebones example to show how to use the library. In practice, you will probably need tessellation to render the lines of the contour set in a more visually appealing way.

References

• Marching Squares - Wikipedia
• Will Usher's blog post
• GPU Gems 3 - Parallel Prefix Sum