Ориентированная на данные трассировка лучей на выходных в Rust

Я изучал программирование, ориентированное на данные, и, пытаясь реализовать этот простой Raytracer, я решил сделать это таким образом, используя Rust. Это также относится к курсу оптимизации, где я хотел применить изученные нами принципы (например, избегать промахов кеша).

Мой вопрос в основном о HittableList. (Вы можете увидеть остальную часть кода в репозитории: https://github.com/St0wy/трассировка лучей)

src/ray.rs

use crate::geometry::sphere::Sphere;
use crate::geometry::xy_rectangle::XyRectangle;
use crate::geometry::xz_rectangle::XzRectangle;
use crate::geometry::yz_rectangle::YzRectangle;
use crate::material::Material;
use crate::{math::vec3::*, ray::Ray};
use rand::Rng;
use std::cmp::Ordering;
use tracy::zone;

#[derive(Debug)]
pub struct HitRecord<'a> {
    point: Vec3,
    normal: Vec3,
    t: f32,
    u: f32,
    v: f32,
    front_face: bool,
    material: &'a Material,
}

impl<'a> HitRecord<'a> {
    pub fn new(
        point: Vec3,
        t: f32,
        u: f32,
        v: f32,
        outward_normal: Vec3,
        ray_direction: &Vec3,
        material: &'a Material,
    ) -> Self {
        let front_face = ray_direction.dot(&outward_normal) < 0.0;
        let normal = if front_face {
            outward_normal
        } else {
            -outward_normal
        };

        Self {
            point,
            normal,
            t,
            u,
            v,
            front_face,
            material,
        }
    }

    pub fn normal(&self) -> &Vec3 {
        &self.normal
    }

    pub fn point(&self) -> &Vec3 {
        &self.point
    }

    pub fn material(&self) -> &Material {
        self.material
    }

    pub fn front_face(&self) -> bool {
        self.front_face
    }

    pub fn u(&self) -> f32 {
        self.u
    }

    pub fn v(&self) -> f32 {
        self.v
    }

    pub fn t(&self) -> f32 {
        self.t
    }
}

pub trait Hittable {
    fn hit(&self, ray: &Ray, t_min: f32, t_max: f32) -> Option<HitRecord>;
    fn bounding_box(&self, time0: f32, time1: f32) -> Option<Aabb>;
}

#[derive(Copy, Clone, Debug)]
pub enum HittableObjectType {
    Sphere,
    MovingSphere,
    XyRectangle,
    XzRectangle,
    YzRectangle,
    AabbBox,
    BvhNode,
}

#[derive(Copy, Clone, Debug)]
pub struct HittableObjectIndex {
    pub object_type: HittableObjectType,
    pub index: usize,
}

impl HittableObjectIndex {
    pub fn new(object_type: HittableObjectType, index: usize) -> Self {
        HittableObjectIndex { object_type, index }
    }
}

pub struct HittableList {
    spheres: Vec<Sphere>,
    moving_spheres: Vec<MovingSphere>,
    xy_rectangles: Vec<XyRectangle>,
    xz_rectangles: Vec<XzRectangle>,
    yz_rectangles: Vec<YzRectangle>,
    aabb_boxes: Vec<AabbBox>,
    bvh_nodes: Vec<BvhNode>,
    first_node_index: usize,
}

impl HittableList {
    pub fn new() -> Self {
        Self {
            spheres: Vec::new(),
            moving_spheres: Vec::new(),
            xy_rectangles: Vec::new(),
            xz_rectangles: Vec::new(),
            yz_rectangles: Vec::new(),
            aabb_boxes: Vec::new(),
            bvh_nodes: Vec::new(),
            first_node_index: 0,
        }
    }

    pub fn add_sphere(&mut self, sphere: Sphere) {
        self.spheres.push(sphere);
    }

    pub fn add_moving_sphere(&mut self, moving_sphere: MovingSphere) {
        self.moving_spheres.push(moving_sphere);
    }

    pub fn add_xy_rectangle(&mut self, rectangle: XyRectangle) {
        self.xy_rectangles.push(rectangle);
    }

    pub fn add_xz_rectangle(&mut self, rectangle: XzRectangle) {
        self.xz_rectangles.push(rectangle);
    }

    pub fn add_yz_rectangle(&mut self, rectangle: YzRectangle) {
        self.yz_rectangles.push(rectangle);
    }

    pub fn add_aabb_box(&mut self, aabb_box: AabbBox) {
        self.aabb_boxes.push(aabb_box);
    }

    pub fn len(&self) -> usize {
        self.spheres.len()
            + self.moving_spheres.len()
            + self.xy_rectangles.len()
            + self.xz_rectangles.len()
            + self.yz_rectangles.len()
            + self.aabb_boxes.len()
    }

    pub fn hit_no_limit(&self, ray: &Ray) -> Option<HitRecord> {
        self.hit(ray, 0.001, f32::INFINITY)
    }

    pub fn hit_at(
        &self,
        hittable_object_index: &HittableObjectIndex,
        ray: &Ray,
        t_min: f32,
        t_max: f32,
    ) -> Option<HitRecord> {
        zone!();
        match hittable_object_index.object_type {
            HittableObjectType::BvhNode => self.hit_node(
                &self.bvh_nodes[hittable_object_index.index],
                ray,
                t_min,
                t_max,
            ),
            HittableObjectType::Sphere => {
                self.spheres[hittable_object_index.index].hit(ray, t_min, t_max)
            }
            HittableObjectType::MovingSphere => {
                self.moving_spheres[hittable_object_index.index].hit(ray, t_min, t_max)
            }
            HittableObjectType::XyRectangle => {
                self.xy_rectangles[hittable_object_index.index].hit(ray, t_min, t_max)
            }
            HittableObjectType::XzRectangle => {
                self.xz_rectangles[hittable_object_index.index].hit(ray, t_min, t_max)
            }
            HittableObjectType::YzRectangle => {
                self.yz_rectangles[hittable_object_index.index].hit(ray, t_min, t_max)
            }
            HittableObjectType::AabbBox => {
                self.aabb_boxes[hittable_object_index.index].hit(ray, t_min, t_max)
            }
        }
    }

    pub fn get_aabb(
        &self,
        hittable_object_index: HittableObjectIndex,
        time0: f32,
        time1: f32,
    ) -> Option<Aabb> {
        match hittable_object_index.object_type {
            HittableObjectType::Sphere => {
                self.spheres[hittable_object_index.index].bounding_box(time0, time1)
            }
            HittableObjectType::MovingSphere => {
                self.moving_spheres[hittable_object_index.index].bounding_box(time0, time1)
            }
            HittableObjectType::XyRectangle => {
                self.xy_rectangles[hittable_object_index.index].bounding_box(time0, time1)
            }
            HittableObjectType::XzRectangle => {
                self.xz_rectangles[hittable_object_index.index].bounding_box(time0, time1)
            }
            HittableObjectType::YzRectangle => {
                self.yz_rectangles[hittable_object_index.index].bounding_box(time0, time1)
            }
            HittableObjectType::BvhNode => {
                Some(self.bvh_nodes[hittable_object_index.index].aabb().clone())
            }
            HittableObjectType::AabbBox => {
                self.aabb_boxes[hittable_object_index.index].bounding_box(time0, time1)
            }
        }
    }

    pub fn is_empty(&self) -> bool {
        self.spheres.is_empty()
            && self.moving_spheres.is_empty()
            && self.xy_rectangles.is_empty()
            && self.xz_rectangles.is_empty()
            && self.yz_rectangles.is_empty()
            && self.aabb_boxes.is_empty()
    }

    fn hit_node(&self, node: &BvhNode, ray: &Ray, t_min: f32, t_max: f32) -> Option<HitRecord> {
        zone!();
        if !node.aabb().hit(ray, t_min, t_max) {
            return None;
        }

        let record_left_option = self.hit_at(node.left(), ray, t_min, t_max);
        let mut left_distance = t_max;
        let mut record = None;
        if let Some(record_left) = record_left_option {
            left_distance = record_left.t;
            record = Some(record_left);
        }

        let record_right = self.hit_at(node.right(), ray, t_min, left_distance);
        if let Some(record_right) = record_right {
            if left_distance < record_right.t {
                record
            } else {
                Some(record_right)
            }
        } else {
            record
        }
    }

    fn box_compare(
        &self,
        time0: f32,
        time1: f32,
        axis: usize,
    ) -> impl FnMut(&HittableObjectIndex, &HittableObjectIndex) -> Ordering + '_ {
        move |a, b| {
            let a_bbox = self.get_aabb(*a, time0, time1);
            let b_bbox = self.get_aabb(*b, time0, time1);
            if a_bbox.is_none() || b_bbox.is_none() {
                panic!("no bounding box in bvh node")
            }

            if a_bbox.unwrap().min()[axis] - b_bbox.unwrap().min()[axis] < 0.0 {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        }
    }

    fn create_node(
        &mut self,
        hittables: &mut [HittableObjectIndex],
        time0: f32,
        time1: f32,
    ) -> HittableObjectIndex {
        let axis = rand::thread_rng().gen_range(0..3) as usize;

        let len = hittables.len();
        let (left, right) = match len {
            0 => panic!("0 Hittables provided to node creation"),
            1 => (hittables[0].clone(), hittables[0].clone()),
            2 => (hittables[0].clone(), hittables[1].clone()),
            _ => {
                hittables.sort_unstable_by(self.box_compare(time0, time1, axis));
                let mid = len / 2;
                (
                    self.create_node(&mut hittables[0..mid], time0, time1),
                    self.create_node(&mut hittables[mid..len], time0, time1),
                )
            }
        };

        let left_box = self.get_aabb(left, time0, time1);
        let right_box = self.get_aabb(right, time0, time1);

        if left_box.is_none() || right_box.is_none() {
            panic!("No bounding box in Bvh Node");
        }

        let aabb = Aabb::surrounding_box(left_box.unwrap(), right_box.unwrap());

        let node = BvhNode::new(left, right, aabb);
        self.bvh_nodes.push(node);

        HittableObjectIndex::new(HittableObjectType::BvhNode, self.bvh_nodes.len() - 1)
    }

    pub fn init_bvh_nodes(&mut self) {
        let mut hittables = Vec::new();

        for i in 0..self.spheres.len() {
            hittables.push(HittableObjectIndex::new(HittableObjectType::Sphere, i))
        }

        for i in 0..self.moving_spheres.len() {
            hittables.push(HittableObjectIndex::new(
                HittableObjectType::MovingSphere,
                i,
            ))
        }

        for i in 0..self.xy_rectangles.len() {
            hittables.push(HittableObjectIndex::new(HittableObjectType::XyRectangle, i));
        }

        for i in 0..self.xz_rectangles.len() {
            hittables.push(HittableObjectIndex::new(HittableObjectType::XzRectangle, i));
        }

        for i in 0..self.yz_rectangles.len() {
            hittables.push(HittableObjectIndex::new(HittableObjectType::YzRectangle, i));
        }

        for i in 0..self.aabb_boxes.len() {
            hittables.push(HittableObjectIndex::new(HittableObjectType::AabbBox, i));
        }

        let node = self.create_node(&mut hittables[..], 0.0, 1.0);
        self.first_node_index = node.index;
    }
}

fn get_objects_bounding_box<T: Hittable>(items: &Vec<T>, time0: f32, time1: f32) -> Option<Aabb> {
    if items.is_empty() {
        return None;
    }

    let mut temp_box: Aabb;
    let mut output_box = Aabb::empty();
    let mut first_box = true;

    for object in items.iter() {
        temp_box = object.bounding_box(time0, time1)?;

        output_box = if first_box {
            temp_box
        } else {
            Aabb::surrounding_box(output_box, temp_box)
        };

        first_box = false;
    }

    Some(output_box)
}

impl Hittable for HittableList {
    fn hit(&self, ray: &Ray, t_min: f32, t_max: f32) -> Option<HitRecord> {
        zone!();
        let first = self.bvh_nodes.get(self.first_node_index);

        if first.is_none() {
            panic!("There should be nodes in the hittable list.");
        }

        self.hit_node(&first.unwrap(), ray, t_min, t_max)
    }

    fn bounding_box(&self, time0: f32, time1: f32) -> Option<Aabb> {
        if self.is_empty() {
            return None;
        }

        let spheres_box = get_objects_bounding_box(&self.spheres, time0, time1);
        let moving_spheres_box = get_objects_bounding_box(&self.moving_spheres, time0, time1);
        let xy_rectangles_box = get_objects_bounding_box(&self.xy_rectangles, time0, time1);
        let xz_rectangles_box = get_objects_bounding_box(&self.xz_rectangles, time0, time1);
        let yz_rectangles_box = get_objects_bounding_box(&self.yz_rectangles, time0, time1);
        let aabb_box_box = get_objects_bounding_box(&self.aabb_boxes, time0, time1);

        let a = Aabb::opt_surrounding_box(spheres_box, moving_spheres_box);
        let b = Aabb::opt_surrounding_box(a, xy_rectangles_box);
        let c = Aabb::opt_surrounding_box(b, xz_rectangles_box);
        let d = Aabb::opt_surrounding_box(c, yz_rectangles_box);

        Aabb::opt_surrounding_box(d, aabb_box_box)
    }
}

Как видите, здесь много шаблонов/повторений, потому что я хотел избежать Vec<Box<dyn Hittable>> что сделало бы программу медленнее и менее дружественной к кэшу.

Есть ли способ спроектировать мой код таким образом, чтобы упростить работу с новыми объектами?

HittableList identifer хорош, но, похоже, он затрагивает несущественный аспект структуры данных, и, возможно, это не ваш любимый маркетинговый термин для привлечения людей к использованию вашей библиотеки. Подумайте о том, чтобы переосмыслить название. IDK, HittableFinder, может быть?

я нахожу это [benchmark] линия удивительно четкая:

    let mut world = HittableList::new();

Мне бы никогда не пришло в голову написать это, если бы все, что я видел, было определением. Вероятно, я бы пошел с let mut hl = ...
или что-то столь же ужасное.

Это очевидно для специалиста в данной области.

Но когда я подошел к этому, мне было грустно, что я не видел комментарий, в котором упоминалась «иерархия ограничивающих объемов» или «граничная рамка, выровненная по оси».

Тем не менее, не обязательно ничего менять. Внимательный читатель будет в конце концов быть в курсе, я полагаю.

Если вы полагаетесь на какой-то текст для математики, было бы полезно, чтобы код цитировал ссылку.

В len(), по-видимому, узлы bvh как-то особенные, так как они не влияют на длину. Хорошо.

    pub fn hit_no_limit(&self, ray: &Ray) -> Option<HitRecord> {
        self.hit(ray, 0.001, f32::INFINITY)

Угх! Магическое число. Пожалуйста, определите epsilon или что-то.

    pub fn hit_at(
        &self,
        hittable_object_index: &HittableObjectIndex,
        ray: &Ray,
        t_min: f32,
        t_max: f32,
    ) -> Option<HitRecord> {
        zone!();

Читатель должен понимать, что последние два аргумента представляют собой параметризованное расстояние вдоль луча. Обязательны либо комментарий, либо ссылка на литературу. Пока не ясно, как вызывающая сторона будет выбирать разумные значения t. Возможно, исходя из расстояния от глаза до окна просмотра?

Я думаю, Трейси zone!() похож на матлаб tic / toc. Это кажется неуместным в производственной версии. Либо так, либо мы хотели бы увидеть объяснение того, как этот пакет поддерживает желание разработчика приложения понять, куда ушли циклы.

match отправляет на один из семи методов, каждый из которых соответствует одному и тому же интерфейсу. Так что это похоже на хорошее место, чтобы назначить
указатель функцииа затем есть только один сайт вызова, который указывает три аргумента.

Подобный аргумент почти работает в get_aabb, за исключением случая узла bvh. И я признаюсь, что понятия не имею, сколько времени {0,1} примерно.

is_empty определение кажется утомительным, учитывая, что мы могли бы просто сравнить len() == 0.

hit_node выиграет от словесного изображения или URL-адреса диаграммы, объясняющей, как левое/правое вписывается в ориентацию луча.

    fn box_compare(
                ...
                panic!("no bounding box in bvh node")

Это не кажется очень диагностическим. Если бы я был мейнтейнером, гоняющимся за отчетом об ошибке, я, вероятно, хотел бы знать подробности, такие как два раза.

В init_bvh_nodes, аналогичный СУХОМУ аргументу, как указано выше. Кажется, есть возможность перебирать кучу типов объектов, используя только один сайт вызова для push/new.

fn get_objects_bounding_box<T: Hittable>(items: &Vec<T>, time0: f32, time1: f32) -> Option<Aabb> {
    ...
    let mut temp_box: Aabb;

Кажется, мы должны быть в состоянии отсрочить
temp_box декларация до тех пор, пока она не назначена. Вздох.

Может быть, инициализировать output_box быть нулевым элементом и потерять флаг, полагаясь на самосравнение, чтобы быть тождеством?

Время сделать шаг назад.

Прочитав все это, я все еще не вижу мотивации для разделения сферы / движущейся сферы. Просто введите нулевую скорость и покончим с этим, не так ли?

Три ориентации прямоугольника, кажется, играют роль в этом соображении дизайна:

Я хотел избежать использования Vec, который делал бы программу медленнее и менее дружественной к кэшу.

Хорошо, достаточно честно. Но в кодовой базе мне бы очень хотелось видеть эталонные цифры, оправдывающие такие решения, так как действительно есть влияние на код. Например, я представлять себе len() правильно, но это не очевидно для меня, просто прочитав источник. Конечно, для этих оптимизаций есть место, но, судя по тому, что я читал, я еще не уверен, что они нужны здесь. Сравнительные тайминги не помешали бы.

ЛГТМ, отправляй!