Marching Cubes in Rust
A simple marching cubes implementation
Why?
Volumetric information (e.g. implicit surfaces) -> Surface of triangles
How?
- The algorithm iterates through a uniform 3D grid, sampling 8 points (cube vertices) of f(x, y, z) at once
- There are 256 possible binary (in or out of the isosurface) states of the 8 vertices. Clever lookup tables indexed by from 8 bit lookup indices return vertex configurations to form the corresponding triangles.
Much better explanations can be found here:
Usage:
The main program uses a simple CLI to extract the 0 isosurface from a symbolic expression.
1
2
3
4
5
6
7
8
9
> cargo build --release
> ./target/release/marching-cubes --expr="x^2+y^2+z^2-2500"
Cube count: 1000000
Vertices: 282336
Triangles: 94112
Exported: marched.stl
Time: 0 min 3.10 seconds
Argument | Short | Long | Default |
---|---|---|---|
Expression | -e | –expr | |
.stl path | -e | –export-path | examples/marched.stl |
Grid scale | -s | –scale | 1. |
Domain (centered) | -d | –domain | “[100, 100, 100]” |
Mode | -m | –mode | “evalexpr” |
Variations
The crate provides four versions of marching cubes. Each one of these has an example file that can be run with:
1
cargo run --release --example <example>
1. Symbolic Expression (evalexpr):
Evaluate a symbolic expression at each grid point using the evalexpr crate. Multithreaded with Rayon.
x, y, and z will be updated at each sample point. Operators in the evalexpr crate are supported.
1
2
3
4
5
6
7
8
9
10
11
let expr = &"(.25*x)^2+(.25*y)^2-z-10";
let mesh = marching_cubes_evaluated(
&expr, // expression to evaluate
point![-25., -25., -25.], // minimum bounding box point
100, // x count
100, // y count
100, // z count
0., // isosurface value
1., // scale
);
2. Precompiled:
Evaluate a precompiled function, map()
. Very fast for obvious reasons (also multithreaded with Rayon).
map()
could be anything that returns a value, but some signed distance functions are provided as samples. The code will extract the isosurface where map(Point)
= 0 by default).
1
2
3
4
5
6
7
8
9
let mesh = marching_cubes_compiled(
&thread_safe_map, // function to evaluate
point![-100., -100., -100.], // minimum bounding box point
200, // x count
200, // y count
200, // z count
0., // isosurface value
1., // scale
);
This sample function will make a cube smoothly united with a sphere:
1
2
3
4
5
6
fn map(p: Point) -> f64 {
let s = sdf::sphere(p, point![30., 30., 30.], 65.0);
let b = sdf::rounded_box(p, point![-30., -30., -30.], vector![60., 60., 60.], 10.);
sdf::boolean_union(b, s, 20.)
}
3. Discrete Data:
A 3D buffer of discrete data is sampled for the algorithm. In the example, a map(Point)
function is used to populate the voxels, but any discrete data could be used.
1
2
3
4
let mesh = marching_cubes_buffer(
&buffer, // discrete 3D data
0. // isosurface value
);
4. Symbolic Expression (fidget):
Evaluate a symbolic expression at each grid point using Matt Keeter’s fidget. Multithreaded with Rayon.
x, y, and z will be updated at each sample point. Operators in the rhai crate are supported.
1
2
3
4
5
6
7
8
9
10
11
let expr = "x*x + y*y + z*z - 2500";
let mesh = marching_cubes_fidget(
&expr, // expression to evaluate
point![-100., -100., -100.], // minimum bounding box point
200, // x count
200, // y count
200, // z count
0., // isosurface value
1., // scale
);
Quick & dirty benchmark:
Example | Time(s) | Multithreaded |
---|---|---|
Compiled | 0.04 | yes |
fidget | 0.11 | yes |
evalexpr | 7.24 | yes |
Future improvements
- Optimize to reduce obviously redundant queries (overlapping corners)
- Refactor for less redundancy
- Multithread the discrete data version
- More idiomatic Rust