Introduction
In order to practice Rust more effectively, I have decided to rewrite some some interesting projects in Rust. The first project has been finished, it is a CPU Path Tracing tiny project, you can find the code at Github and find the article at Here.
It’s now time to release the second one, a tiny Ray Marching Engine. With this, you can import SDF shapes from Shadertoy and render a scene, here is an example:
There are four types of primitives in the scene above, they are:
- Cube: Forming the ground
- Sphere: Forming the purple model
- Torus: The metallic torus to the left of the spheres
- Helix: THe metallic helix is at the back
These primitives are imported from Shadertoy, you can import them by add Shape trait implements in sdf/mod.rs.
Implementation
The SDF (Signed Distance Field) is the key for ray marching, If you are interested in the implementation details, you can refer to An Introduction to Raymarching by typhomnt. This project was developed based on the priciples outlined in that article.
Each primitive (such as Cube, Sphere, Plane, etc.) has its own SDF, and we can combine these SDFs to construct complex shapes. SDF supports a variety of set operators, in this project, we have implemented the following ones:
pub enum ShapeOpType {
Nop,
Union,
Subtraction,
Intersection,
SmoothUnion,
}
To combine SDFs together, we need to create some LinkedList, for the scene above, there are three shapes:
- Helix: a leaf node
- Torus: a leaf node
- Spheres: composed of three sphere: Right Sphere ∪ Left Sphere − Top Sphere
For the spheres, we must link the right one, left one and top one together like this:
// Sphere
let sub_sphere = scene.add_leaf_node(
Box::new(Sphere {
center: Vector3f::new(0.0, 2.0, -5.6),
radius: 0.5,
}),
Rc::clone(&purper_material),
);
let sphere = scene.add_node(
Box::new(Sphere {
center: Vector3f::new(0.0, 1.65, -5.6),
radius: 0.8,
}),
Rc::clone(&purper_material),
sdf::ShapeOpType::Subtraction,
Some(sub_sphere),
);
let bottom_sphere = scene.add_node(
Box::new(Sphere {
center: Vector3f::new(0.85, 1.85, -6.6),
radius: 0.5,
}),
Rc::clone(&purper_material),
sdf::ShapeOpType::SmoothUnion,
Some(sphere),
);
scene.add_root_node(bottom_sphere);
// Sphere(c=(0.85, 1.85, -6.6), o=0.5)
// ==> Sphere(c=(0, 1.65, -5.6), o=0.8)
// ==> Sphere(c=(0, 2, -5.6), o=0.5)
To achieve this, we must create a scene struct contains nodes, and allowing nodes to reference to each other, below is the first try:
pub struct Shape {}
pub struct Node<'a> {
data: Shape,
next: Option<&'a Node<'a>>,
}
pub struct Scene<'a> {
nodes: Vec<Node<'a>>,
}
The code does not work, if we try to create a scene with the code above, we have two approaches:
- create leaf nodes first, and create node references to the leafs
- create all nodes as leaves, and mutate some node to reference to others
For the first approach, imagine we have two nodes: leaf and root. The root.next points to the leaf, we can create the two nodes without any error, but when we try to add the leaf node to the scene, it will be moved, and the reference of root.next will be invalid.
fn create_scene() {
let leaf = Node {
data: Shape {},
next: None,
};
let root = Node {
data: Shape {},
next: Some(&leaf),
};
let mut nodes = vec![];
// after the line below, the leaf will be moved, and the root.next is invalid
nodes.push(leaf);
}
How about push the leaf to the vector first and reference from it? It does not work either because when we reference from the vector, there will be a immutable reference to the vector, then we cannot push the root node to the vector because of the borrow check rule:
fn create_scene() {
let leaf = Node {
data: Shape {},
next: None,
};
let mut nodes = vec![];
nodes.push(leaf);
let root = Node {
data: Shape {},
next: Some(&nodes[0]),
};
// cannot borrow `nodes` as mutable because it is also borrowed as immutable
nodes.push(root);
}
For the second approach, when we borrow the root node from vector as mutable reference, we cannot borrow any other node references, so we cannot borrow a reference of leaf for root.
fn create_scene() {
let mut nodes = vec![];
let leaf = Node {
data: Shape {},
next: None,
};
nodes.push(leaf);
let root = Node {
data: Shape {},
next: None,
};
nodes.push(root);
let root = &mut nodes[1];
// cannot borrow `nodes` as immutable because it is also borrowed as mutable
root.next = Some(&nodes[0]);
}
These restrictions are designed to prevent issues with invalid references that can occur when a vector is resized. To create this kind of self-referential structure, we can employ the arena pattern.
For our current scenario, we can utilize the elsa::FrozenVec which is an append-only Vec-like abstraction that allows you to call .push() without requiring a mutable reference:
fn create_scene() {
let scene = Scene {
nodes: FrozenVec::new(),
};
let leaf = Box::new(Node {
data: Shape {},
next: None,
});
scene.nodes.push(leaf);
let leaf = &scene.nodes[0];
let root = Box::new(Node {
data: Shape {},
next: Some(leaf),
});
scene.nodes.push(root);
}
Because we can push to the vector-like abstraction FrozenVec without a mutable reference to it, we can reference from nodes, assign it to the root.next and add root to scene.
The FrozenVec is the key to implementing the SDF LinkedList, here is the atual code:
pub struct ShapeOp<'a> {
pub shape: Box<dyn Shape>,
pub op: ShapeOpType,
pub material: Rc<PBRMaterial>,
pub next: Option<&'a ShapeOp<'a>>,
}
pub struct Scene<'a> {
pub nodes: FrozenVec<Box<ShapeOp<'a>>>,
pub root_nodes: FrozenVec<&'a ShapeOp<'a>>,
// ...
}
impl<'a> Scene<'a> {
// ...
pub fn add_leaf_node(
&'a self,
shape: Box<dyn Shape>,
material: Rc<PBRMaterial>,
) -> &'a ShapeOp<'a> {
let idx = self.nodes.len();
self.nodes.push(Box::new(ShapeOp {
shape,
op: ShapeOpType::Nop,
next: None,
material,
}));
&self.nodes[idx]
}
pub fn add_node(
&'a self,
shape: Box<dyn Shape>,
material: Rc<PBRMaterial>,
op: ShapeOpType,
next: Option<&'a ShapeOp<'a>>,
) -> &'a ShapeOp<'a> {
let idx = self.nodes.len();
self.nodes.push(Box::new(ShapeOp {
shape,
material,
op,
next,
}));
&self.nodes[idx]
}
// ...
}
References
- Arenas in Rust (from manishearth)
- An Introduction to Raymarching (from typhomnt)
- Raymarching Primitives (from shadertoy)
- 3D SDF Primitives (from shadertoy)
- An Introduction to Physically Based Rendering (from typhomnt)