feat: parallelize ray marching

8 files changed, 247 insertions, 93 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 6c192ef..184ee5f 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -34,6 +34,37 @@ dependencies = [
 ]
 
 [[package]]
+name = "crossbeam-deque"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "613f8cc01fe9cf1a3eb3d7f488fd2fa8388403e97039e2f73692932e291a770d"
+dependencies = [
+ "crossbeam-epoch",
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "crossbeam-epoch"
+version = "0.9.18"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b82ac4a3c2ca9c3460964f020e1402edd5753411d7737aa39c3714ad1b5420e"
+dependencies = [
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "crossbeam-utils"
+version = "0.8.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "248e3bacc7dc6baa3b21e405ee045c3047101a49145e7e9eca583ab4c2ca5345"
+
+[[package]]
+name = "either"
+version = "1.12.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3dca9240753cf90908d7e4aac30f630662b02aebaa1b58a3cadabdb23385b58b"
+
+[[package]]
 name = "libc"
 version = "0.2.105"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -65,6 +96,7 @@ version = "0.1.0"
 dependencies = [
  "cgmath",
  "ncurses",
+ "rayon",
 ]
 
 [[package]]
@@ -72,3 +104,23 @@ name = "pkg-config"
 version = "0.3.22"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "12295df4f294471248581bc09bef3c38a5e46f1e36d6a37353621a0c6c357e1f"
+
+[[package]]
+name = "rayon"
+version = "1.10.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b418a60154510ca1a002a752ca9714984e21e4241e804d32555251faf8b78ffa"
+dependencies = [
+ "either",
+ "rayon-core",
+]
+
+[[package]]
+name = "rayon-core"
+version = "1.12.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1465873a3dfdaa8ae7cb14b4383657caab0b3e8a0aa9ae8e04b044854c8dfce2"
+dependencies = [
+ "crossbeam-deque",
+ "crossbeam-utils",
+]
diff --git a/Cargo.toml b/Cargo.toml
index d9612b6..27ad75f 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,3 +8,4 @@ edition = "2018"
 [dependencies]
 cgmath = "0.18.0"
 ncurses = "5.101.0"
+rayon = "1.10.0"
diff --git a/src/buffer.rs b/src/buffer.rs
index a2c5708..61b3374 100644
--- a/src/buffer.rs
+++ b/src/buffer.rs
@@ -10,7 +10,9 @@ impl Buffer {
         Self {
             height,
             width: height * aspect_ratio,
-            palette: "$@B%8&WM#oahkbdpqwmZO0QLCJUYXzcvunxrjft/\\|()1{}[]?-_+~<>i!lI;:,\"^`'. ".chars().collect(),
+            palette: "$@B%8&WM#oahkbdpqwmZO0QLCJUYXzcvunxrjft/\\|()1{}[]?-_+~<>i!lI;:,\"^`'. "
+                .chars()
+                .collect(),
         }
     }
 }
diff --git a/src/camera.rs b/src/camera.rs
index 84d8446..7682553 100644
--- a/src/camera.rs
+++ b/src/camera.rs
@@ -1,12 +1,14 @@
-use cgmath::{Vector3, Matrix3};
 use cgmath::prelude::*;
+use cgmath::{Matrix3, Vector3};
+
+use crate::screen::ScreenIterator;
 type Vector = Vector3<f32>;
 
 // The physical screen that camera projects onto
 #[derive(Debug, Copy, Clone)]
 pub struct Screen {
     pub width: f32,
-    pub height: f32
+    pub height: f32,
 }
 
 #[derive(Debug, Copy, Clone)]
@@ -34,10 +36,10 @@ impl Camera {
             distance,
             screen: Screen { width, height },
             speed: 0.5,
-            turn_rate: 60.0
+            turn_rate: 60.0,
         }
     }
-    pub fn get_screen_iterator(self) -> (Vector, Vector, Vector) {
+    pub fn get_screen_iterator(self) -> ScreenIterator {
         // Linear transormation operator for calculating screen position
         // Assumes "initial" screen is perpendicular to OX
         // and it's bottom edge is parallel to OY
@@ -47,12 +49,10 @@ impl Camera {
             -self.up * self.screen.height,
         );
 
-        let corner_dir = operator * Vector::new(1.0, -0.5, -0.5); // Corner
-        let step_v = operator * Vector::unit_z();
-        let step_h = operator * Vector::unit_y();
-
-        // TODO: return an actual iterator
-        return (corner_dir, step_h, step_v)
+        ScreenIterator::from_screen_position(
+            operator * Vector::new(1.0, -0.5, -0.5),
+            operator * Vector::unit_z(),
+            operator * Vector::unit_y(),
+        )
     }
 }
-
diff --git a/src/main.rs b/src/main.rs
index 5873996..d733fb3 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,30 +1,26 @@
 extern crate ncurses;
 
-mod camera;
 mod buffer;
+mod camera;
 mod renderer;
+mod screen;
 mod sdf;
 
-use std::{f32::consts::PI, time::Instant};
 use cgmath::{Angle, Array, Matrix3, Rad, Vector3, Zero};
 use ncurses::*;
+use std::{f32::consts::PI, time::Instant};
 
-use camera::Camera;
 use buffer::Buffer;
+use camera::Camera;
 use renderer::Renderer;
-use sdf::{Sphere, Gear, Object, SDBox};
+use sdf::{Gear, Object, SDBox, Sphere};
 
 fn main() {
     // This vector will later be built
     // by parsing a JSON scene
     let mut renderer = Renderer::new(
-        Box::new(Buffer::from_height(50.0, 3.0)),
-        Box::new(Camera::new(
-            Vector3::new(-4.0, 0.0, 0.0),
-            Vector3::zero(),
-            PI / 2.0,
-            1.0
-        )),
+        Buffer::from_height(50.0, 3.0),
+        Camera::new(Vector3::new(-4.0, 0.0, 0.0), Vector3::zero(), PI / 2.0, 1.0),
         vec![
             Box::new(Sphere {
                 center: Vector3::zero(),
@@ -40,7 +36,7 @@ fn main() {
                 center: Vector3::new(2.0, 2.0, 0.0),
                 size: Vector3::from_value(1.0),
             }),
-        ]
+        ],
     );
 
     initscr();
@@ -56,9 +52,16 @@ fn main() {
         // Render
         let timestamp = Instant::now();
         renderer.render(time);
-        addstr(&format!("\nRendered in {:?} ({:.1} FPS)\n", timestamp.elapsed(), 1.0 / timestamp.elapsed().as_secs_f64()));
+        addstr(&format!(
+            "\nRendered in {:?} ({:.1} FPS)\n",
+            timestamp.elapsed(),
+            1.0 / timestamp.elapsed().as_secs_f64()
+        ));
         addstr(&format!("Camera: {:?}\n", renderer.camera.position));
-        addstr(&format!("Facing: {:?}, Up: {:?}\n", renderer.camera.direction, renderer.camera.up));
+        addstr(&format!(
+            "Facing: {:?}, Up: {:?}\n",
+            renderer.camera.direction, renderer.camera.up
+        ));
 
         refresh();
 
@@ -68,39 +71,56 @@ fn main() {
         addstr(&format!("\nPressed: {:?}\n", char));
         refresh();
 
-        if char == 107 { // k to move forward
+        if char == 107 {
+            // k to move forward
             renderer.camera.position += renderer.camera.direction * renderer.camera.speed;
-        } else if char == 106 { // j to move backward
+        } else if char == 106 {
+            // j to move backward
             renderer.camera.position -= renderer.camera.direction * renderer.camera.speed;
-        } else if char == 72 { // H to move left
-            renderer.camera.position += Matrix3::from_axis_angle(renderer.camera.up, Rad::turn_div_4()) * renderer.camera.direction * renderer.camera.speed;
-        } else if char == 76 { // L to move right
-            renderer.camera.position -= Matrix3::from_axis_angle(renderer.camera.up, Rad::turn_div_4()) * renderer.camera.direction * renderer.camera.speed;
-        } else if char == 104 { // h to rotate left
+        } else if char == 72 {
+            // H to move left
+            renderer.camera.position +=
+                Matrix3::from_axis_angle(renderer.camera.up, Rad::turn_div_4())
+                    * renderer.camera.direction
+                    * renderer.camera.speed;
+        } else if char == 76 {
+            // L to move right
+            renderer.camera.position -=
+                Matrix3::from_axis_angle(renderer.camera.up, Rad::turn_div_4())
+                    * renderer.camera.direction
+                    * renderer.camera.speed;
+        } else if char == 104 {
+            // h to rotate left
             let rotation = Matrix3::from_angle_z(Rad::full_turn() / renderer.camera.turn_rate);
             renderer.camera.direction = rotation * renderer.camera.direction;
             renderer.camera.up = rotation * renderer.camera.up;
-        } else if char == 108 { // l to rotate right
+        } else if char == 108 {
+            // l to rotate right
             let rotation = Matrix3::from_angle_z(-Rad::full_turn() / renderer.camera.turn_rate);
             renderer.camera.direction = rotation * renderer.camera.direction;
             renderer.camera.up = rotation * renderer.camera.up;
-        } else if char == 75 { // K to rotate up
+        } else if char == 75 {
+            // K to rotate up
             let axis = renderer.camera.up.cross(renderer.camera.direction);
             let angle = -Rad::full_turn() / renderer.camera.turn_rate;
             let rotation = Matrix3::from_axis_angle(axis, angle);
             renderer.camera.up = rotation * renderer.camera.up;
             renderer.camera.direction = rotation * renderer.camera.direction;
-        } else if char == 74 { // J to rotate down
+        } else if char == 74 {
+            // J to rotate down
             let axis = renderer.camera.up.cross(renderer.camera.direction);
             let angle = Rad::full_turn() / renderer.camera.turn_rate;
             let rotation = Matrix3::from_axis_angle(axis, angle);
             renderer.camera.up = rotation * renderer.camera.up;
             renderer.camera.direction = rotation * renderer.camera.direction;
-        } else if char == 117 { // u to move up along Z
+        } else if char == 117 {
+            // u to move up along Z
             renderer.camera.position += Vector3::unit_z() * renderer.camera.speed;
-        } else if char == 100 { // d to move down along Z
+        } else if char == 100 {
+            // d to move down along Z
             renderer.camera.position -= Vector3::unit_z() * renderer.camera.speed;
-        } else if char == 70 { // F to reverse camera direction
+        } else if char == 70 {
+            // F to reverse camera direction
             renderer.camera.direction = -renderer.camera.direction;
         }
     }
diff --git a/src/renderer.rs b/src/renderer.rs
index 0c6c8d2..6db67e2 100644
--- a/src/renderer.rs
+++ b/src/renderer.rs
@@ -1,7 +1,9 @@
-use cgmath::Vector3;
 use cgmath::prelude::*;
+use cgmath::Vector3;
 use ncurses::addstr;
+use rayon::prelude::*;
 use std::f32;
+use std::sync::Arc;
 
 use crate::Buffer;
 use crate::Camera;
@@ -9,17 +11,16 @@ use crate::Object;
 
 type Vector = Vector3<f32>;
 
-pub struct Renderer<'a> {
-    pub camera: Box<Camera>,
-    pub buffer: Box<Buffer>,
-    pub sdf: Box<dyn Fn(Vector, f32) -> f32 + 'a>,
+pub struct Renderer {
+    pub camera: Camera,
+    pub buffer: Buffer,
+    pub sdf: Arc<dyn Fn(Vector3<f32>, f32) -> f32 + Send + Sync>,
 }
 
-impl Renderer<'_> {
-    // TODO: figure out how the fuck it actually works
-    pub fn new(buffer: Box<Buffer>, camera: Box<Camera>, objects: Vec<Box<dyn Object>>) -> Self {
+impl Renderer {
+    pub fn new(buffer: Buffer, camera: Camera, objects: Vec<Box<dyn Object>>) -> Self {
         let sdf = move |point: Vector3<f32>, time: f32| -> f32 {
-            let mut dist: f32 = 100000.0;
+            let mut dist = f32::MAX;
             for object in objects.iter() {
                 dist = dist.min(object.sdf(point, time));
             }
@@ -29,41 +30,49 @@ impl Renderer<'_> {
         Self {
             buffer,
             camera,
-            sdf: Box::new(sdf)
+            sdf: Arc::new(sdf),
         }
     }
 
     pub fn render(&self, time: f32) {
-        let (mut ray_dir, mut step_h, mut step_v) = self.camera.get_screen_iterator();
+        let mut iterator = self.camera.get_screen_iterator();
+        iterator.set_buffer_size(&self.buffer);
 
-        let sdf = |point: Vector3<f32>| -> f32 {
-            (self.sdf)(point, time)
-        };
+        let sdf = |point: Vector3<f32>| -> f32 { (self.sdf)(point, time) };
 
-        step_v /= self.buffer.height;
-        step_h /= self.buffer.width;
+        let ray_dirs: Vec<Vector3<f32>> = iterator.collect();
+
+        // Ray march in parallel
+        let chars: Vec<char> = ray_dirs
+            .par_iter()
+            .map(|ray_dir| {
+                let collision = Self::ray_march(self.camera.position, *ray_dir, &sdf);
+                match collision {
+                    Some(point) => Self::light_point(point, &sdf),
+                    None => 0.0,
+                }
+            })
+            .map(|brightness| {
+                self.buffer.palette
+                    [((1.0 - brightness) * (self.buffer.palette.len() - 1) as f32) as usize]
+            })
+            .collect();
 
         for _i in 0..self.buffer.height as usize {
-            ray_dir += step_v;
             let mut row = "\n".to_string();
             for _j in 0..self.buffer.width as usize {
-                ray_dir += step_h;
-
-                let collision = Self::ray_march(self.camera.position, ray_dir, &sdf);
-
-                let brightness = match collision {
-                    Some(point) => Self::light_point(point, &sdf),
-                    None => 0.0
-                };
-
-                row.push(self.buffer.palette[((1.0 - brightness) * (self.buffer.palette.len() - 1) as f32) as usize]);
+                let character = chars[_i * self.buffer.width as usize + _j];
+                row.push(character);
             }
-            ray_dir -= step_h * self.buffer.width;
             addstr(&row);
         }
     }
 
-    pub fn ray_march(origin: Vector, direction: Vector, sdf: &dyn Fn(Vector) -> f32) -> Option<Vector> {
+    pub fn ray_march(
+        origin: Vector,
+        direction: Vector,
+        sdf: &dyn Fn(Vector) -> f32,
+    ) -> Option<Vector> {
         let threshold = 0.1;
 
         let ray = direction.normalize();
@@ -80,16 +89,16 @@ impl Renderer<'_> {
             point += ray * dist;
         }
 
-        return None
+        None
     }
 
     pub fn light_point(point: Vector, sdf: &dyn Fn(Vector) -> f32) -> f32 {
         let light = Vector::new(1.0, 1.0, -1.0);
         let ambient = 0.1;
-        return ambient + (1.0 - ambient) * (
-            Self::diffuse_lighting(point, light, sdf) * 0.7 +
-            Self::specular_lighting(point, light, sdf) * 0.3
-        )
+        ambient
+            + (1.0 - ambient)
+                * (Self::diffuse_lighting(point, light, sdf) * 0.7
+                    + Self::specular_lighting(point, light, sdf) * 0.3)
     }
 
     pub fn diffuse_lighting(point: Vector, light: Vector, sdf: &dyn Fn(Vector) -> f32) -> f32 {
@@ -100,22 +109,22 @@ impl Renderer<'_> {
         while t < 1.0 {
             let h = sdf(point - light * t);
             if h < 0.001 {
-                return 0.00
+                return 0.00;
             }
             res = res.min(k * h / t);
             t += h;
         }
 
-        return res
+        res
     }
 
     pub fn specular_lighting(point: Vector, light: Vector, sdf: &dyn Fn(Vector) -> f32) -> f32 {
         let normal = Self::normal(point, sdf);
         let dot = -(normal.dot(light));
-        return dot.min(1.0).max(0.0)
-     }
+        dot.min(1.0).max(0.0)
+    }
 
-     pub fn normal(point: Vector, sdf: &dyn Fn(Vector) -> f32) -> Vector {
+    pub fn normal(point: Vector, sdf: &dyn Fn(Vector) -> f32) -> Vector {
         let d = 0.001;
 
         let dx = Vector::unit_x() * d;
@@ -124,10 +133,11 @@ impl Renderer<'_> {
 
         let dist = sdf(point);
 
-        return (Vector {
+        (Vector {
             x: (sdf(point + dx) - dist),
             y: (sdf(point + dy) - dist),
             z: (sdf(point + dz) - dist),
-        } / d).normalize()
+        } / d)
+            .normalize()
     }
 }
diff --git a/src/screen.rs b/src/screen.rs
new file mode 100644
index 0000000..739d6f8
--- /dev/null
+++ b/src/screen.rs
@@ -0,0 +1,61 @@
+use cgmath::{Vector3, Zero};
+
+use crate::buffer::Buffer;
+type Vector = Vector3<f32>;
+
+#[derive(Debug)]
+pub struct ScreenIterator {
+    pub corner_position: Vector,
+    pub vertical_edge: Vector,
+    pub horizontal_edge: Vector,
+    pub horizontal_step: Vector,
+    pub vertical_step: Vector,
+    buffer_width: usize,
+    buffer_height: usize,
+    current_index: usize,
+}
+
+impl ScreenIterator {
+    pub fn from_screen_position(
+        corner_position: Vector,
+        vertical_edge: Vector,
+        horizontal_edge: Vector,
+    ) -> Self {
+        Self {
+            corner_position,
+            vertical_edge,
+            horizontal_edge,
+            vertical_step: Vector::zero(),
+            horizontal_step: Vector::zero(),
+            current_index: 0,
+            buffer_width: 0,
+            buffer_height: 0,
+        }
+    }
+    pub fn set_buffer_size(&mut self, buffer: &Buffer) {
+        self.buffer_width = buffer.width as usize;
+        self.buffer_height = buffer.height as usize;
+
+        self.horizontal_step = self.horizontal_edge / buffer.width;
+        self.vertical_step = self.vertical_edge / buffer.height;
+    }
+}
+
+impl Iterator for ScreenIterator {
+    type Item = Vector;
+    fn next(&mut self) -> Option<Self::Item> {
+        let pixel_x = self.current_index % self.buffer_width;
+        let pixel_y = self.current_index / self.buffer_width;
+
+        if self.current_index < self.buffer_width * self.buffer_height {
+            self.current_index += 1;
+            Some(
+                self.corner_position
+                    + self.horizontal_step * pixel_x as f32
+                    + self.vertical_step * pixel_y as f32,
+            )
+        } else {
+            None
+        }
+    }
+}
diff --git a/src/sdf.rs b/src/sdf.rs
index c46deab..d940f39 100644
--- a/src/sdf.rs
+++ b/src/sdf.rs
@@ -1,10 +1,10 @@
-use std::f32::consts::PI;
-use cgmath::Vector3;
 use cgmath::prelude::*;
+use cgmath::Vector3;
+use std::f32::consts::PI;
 
 type Vector = Vector3<f32>;
 
-pub trait Object {
+pub trait Object: Send + Sync {
     fn sdf(&self, point: Vector, time: f32) -> f32;
 }
 
@@ -28,7 +28,7 @@ impl Object for SDBox {
     fn sdf(&self, point: Vector, _time: f32) -> f32 {
         let diff = self.center - point;
         let q = diff.map(|n| n.abs()) - self.size / 2.0;
-        return q.map(|n| n.max(0.0)).magnitude() + (q.y.max(q.z).max(q.x)).min(0.0)
+        q.map(|n| n.max(0.0)).magnitude() + (q.y.max(q.z).max(q.x)).min(0.0)
     }
 }
 
@@ -48,7 +48,8 @@ impl Object for Gear {
 
         // Ring
         {
-            let cylinder_dist = (Vector::new(0.0, point.y, point.z) - self.center).magnitude() - (self.radius - thickness_over_4);
+            let cylinder_dist = (Vector::new(0.0, point.y, point.z) - self.center).magnitude()
+                - (self.radius - thickness_over_4);
             dist = cylinder_dist.abs() - thickness_over_2; // Make cylinder hollow
         }
         // Teeth
@@ -60,7 +61,7 @@ impl Object for Gear {
             let rotated_point = Vector::new(
                 point.x,
                 point.y * angle.cos() - point.z * angle.sin(),
-                point.y * angle.sin() + point.z * angle.cos()
+                point.y * angle.sin() + point.z * angle.cos(),
             );
 
             // Map all space to the first sector
@@ -70,20 +71,27 @@ impl Object for Gear {
             let mapped_point = Vector::new(
                 rotated_point.x,
                 (rotated_point.y * angle2.cos() - rotated_point.z * angle2.sin()).abs(),
-                rotated_point.y * angle2.sin() + rotated_point.z * angle2.cos()
+                rotated_point.y * angle2.sin() + rotated_point.z * angle2.cos(),
             );
 
             // Make teeth smooth by subtracting some amount
-            dist = dist.min(SDBox {
-                center: Vector { x: 0.0, y: self.radius + thickness_over_2, z: 0.0 },
-                size: Vector::new(self.thickness, self.thickness * 2.0, self.thickness),
-            }.sdf(mapped_point, time) - thickness_over_4);
+            dist = dist.min(
+                SDBox {
+                    center: Vector {
+                        x: 0.0,
+                        y: self.radius + thickness_over_2,
+                        z: 0.0,
+                    },
+                    size: Vector::new(self.thickness, self.thickness * 2.0, self.thickness),
+                }
+                .sdf(mapped_point, time)
+                    - thickness_over_4,
+            );
         }
 
         // Take a slice
         dist = dist.max(point.x.abs() - thickness_over_2);
 
-        return dist;
+        dist
     }
 }
-