Maybe Optimising Raycasting?

45 Days Until I Can Walk

So, I’ve always been unhappy with how I merged the horizontal and vertial intersections produced by the raycaster. The whole point of performing this merge is to allow me to implement transparency, but the problem was that I was declaring a new vector and performing a rather awkward merge as shown below:

pub fn find_wall_intersections(&self, origin_x: i32, origin_y: i32, direction: i32, scene: &Scene) -> Vec<Intersection> {
  let hintersects = self.find_horizontal_intersect(origin_x, origin_y, direction, scene);
  let vintersects = self.find_vertical_intersect(origin_x, origin_y, direction, scene);

  // =============================
  // begin hideous merge operation
  // =============================
  let mut intersects = Vec::new();
  intersects.reserve(hintersects.len() + vintersects.len());

  let mut i = 0;
  let mut j = 0;

  while i < hintersects.len() && j < vintersects.len() {
    if hintersects[i].dist < vintersects[j].dist {
      intersects.push(hintersects[i]);
      i += 1;
    } else {
      intersects.push(vintersects[j]);
      j += 1;
    }
  }

  while i < hintersects.len() {     
    intersects.push(hintersects[i]);
    i += 1;
  }

  while j < vintersects.len() {
    intersects.push(vintersects[j]);
    j += 1;
  }

  intersects
}

This merge requires a second pass over both vectors of slices, and just generally feels very clunky with the manually updated usize variables and trifecta of while loops. A better solution which I have landed on is to use iterators and to merge the values yielded by these iterators as they are traversed. This tidies up my code beautifully as shown below:

pub fn find_wall_intersections(&self, origin_x: i32, origin_y: i32, direction: i32, scene: &Scene) -> Vec<Intersection> {
  let ray_h = Ray::horizontal(origin_x, origin_y, direction, scene);
  let ray_v = Ray::vertical(origin_x, origin_y, direction, scene);

  if ray_h.is_undefined() { return ray_v.collect(); }
  if ray_v.is_undefined() { return ray_h.collect(); }

  vec![ray_h, ray_v].into_iter().kmerge_by(|a, b| a.dist < b.dist).collect()
}

The logic here is simple. We initialize two iterators—one for a horizontal ray and one for a vertical ray—which will keep track of the state of the ray, and yields the next wall intersection as the ray is cast. There are two if statements for the edge cases where the ray is pointing straight up (vertical intersections cannot be hit in this case) and straight across (horizontal intersections cannot be hit). In either of these events, we simply cast the other ray all the way to completion and return all the intersections encountered.

Otherwise we make use of the IterTools crate which supplies us with a kmerge_by method. By providing an iterator of iterators (achieved using vec![ray_h, ray_v].into_iter()), kmerge_by will traverse both iterators and merge them in sorted order using the closure provided. This assumes that the input iterators are already in sorted order. With this implementation, there is no need to cast, then merge the intersections in a separate loop. Instead the rays are cast in simultaneously, and the one closest to the camera is inserted into the resulting vector.

The definition of struct Ray itself is a little strange, and I’m not quite happy with it. I feel like it could be improved with the use of traits, but I’ll come back to that later. For now, Ray is a container struct which holds all the information necessary to keep track of a ray’s position, and two function pointers which point to appropriate methods depending on whether the ray is being cast horizontally or vertically.

struct Ray<'a> {
  step_x: i32,        // distance to next vertical intersect
  step_y: i32,        // distance to next horizontal intersect
  x: i32,             // x coordinate of current ray intersect
  y: i32,             // y coordinate of current ray intersect
  flipped: bool,      // should the texture of the encountered surface be rendered backwards
  direction: i32,     // direction in which the ray is cast
  scene: &'a Scene,   // the environment in which the ray is being cast
  origin_x: i32,      // x point of origin of the ray in fixed point representation
  origin_y: i32,      // y point of origin of the ray in fixed point representation

  cast_ray: fn(&mut Self) -> Option<Intersection>, // either cast_horizontal or cast_vertical depending on ray type
  check_undefined: fn(&Self) -> bool               // either horizontal_is_undefined or vertical_is_undefined depending on ray type
}

The two function pointers, cast_ray and check_undefined feel like a hack, although overall they seem to work quite well. On initialization, depending on whether we are casting a vertical or horizontal ray, the Ray struct is initialized with these references pointing to the appropriate implementation of cast ray. See below for the initialization of a horizontal ray.

pub fn horizontal(origin_x: i32, origin_y: i32, direction: i32, scene: &Scene) -> Ray {
  let step_x: i32;
  let step_y: i32;
  let x: i32;
  let y: i32;
  let flipped: bool;

  // determine if looking up or down and find horizontal intersection
  if direction > trig::ANGLE_0 && direction < trig::ANGLE_180 { // looking down
    step_x = trig::x_step(direction);
    step_y = consts::FP_TILE_SIZE;

    y = ((origin_y.to_i32() / consts::TILE_SIZE) * consts::TILE_SIZE + consts::TILE_SIZE).to_fp();
    x = fp::add(origin_x, fp::mul(fp::sub(y, origin_y), trig::itan(direction)));
    flipped = true;
  } else {                     // looking up
    step_x = trig::x_step(direction);
    step_y = -consts::FP_TILE_SIZE;

    y = ((origin_y.to_i32() / consts::TILE_SIZE) * consts::TILE_SIZE).to_fp();
    x = fp::add(origin_x, fp::mul(fp::sub(y, origin_y), trig::itan(direction)));
    flipped = false;
  }

  // function pointers hooked up here
  Ray { step_x, step_y, x, y, flipped, direction, scene, origin_x, origin_y, check_undefined: Ray::horizontal_is_undefined, cast_ray: Ray::cast_horizontal }
}

While this does work, it feels like the correct thing to do here would actually be to define a Ray trait, then have two separate Ray structs (RayH and RayV) that would implement both this trait and the Iterator trait. These could then be passed to kmerge_by. So, I will investigate this a little more as it feels like the correct solution.

In Other News

I have accepted a very short-term job with my old university to work on a research project. This will give me a little cash-flow, which is obviously a good thing. I may be working less on Fourteen Screws in the near future as a result.

My intention is for Fourteen Screws to become a teaching resource, and so where possible I plan to write posts here about my academic work too. This site will remain as is until the counter to my walking again hits zero. After that, however, I will be restructuring this site into a more general purpose teaching platform. At least that’s the plan. But please bear with me as I dive into some more research over the next few weeks.