public/lib/escher/geometry/intersection.cc

// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "lib/escher/geometry/intersection.h"

namespace escher {

bool IntersectRayBox(const escher::ray4& ray, const escher::BoundingBox& box,
                     float* out_distance) {
  // This algorithm is from "An Efficient and Robust Ray–Box Intersection
  // Algorithm" by Amy Williams et al. 2004. Division by zero is handled via
  // IEEE floating-point arithmetic. See paper for details.
  //
  // Fundamentally (leaving aside optimizations), the algorithm projects the box
  // onto each coordinate axis and then computes the min/max parameters for the
  // ray segment that has the same projection onto the same axis. If the
  // intersection of these parameter ranges is empty, then the ray does not
  // intersect the box.  Otherwise, the minimum value of the intersected
  // parameter ranges gives the intersection point.
  const float idx = 1 / ray.direction.x;
  const float idy = 1 / ray.direction.y;
  const float idz = 1 / ray.direction.z;

  float t_min, t_max, ty_min, ty_max, tz_min, tz_max;

  // Bootstrap with x. Any coordinate axis would work just as well.
  t_min = ((idx < 0 ? box.max() : box.min()).x - ray.origin.x) * idx;
  t_max = ((idx < 0 ? box.min() : box.max()).x - ray.origin.x) * idx;

  ty_min = ((idy < 0 ? box.max() : box.min()).y - ray.origin.y) * idy;
  ty_max = ((idy < 0 ? box.min() : box.max()).y - ray.origin.y) * idy;

  if (t_min > ty_max || ty_min > t_max) {
    // The parameter ranges of the "x-axis projection" and "y-axis projection"
    // ray segments are disjoint. Therefore the ray does not intersect the box.
    return false;
  }

  // Compute the intersection of the two parameter ranges.
  if (ty_min > t_min)
    t_min = ty_min;
  if (ty_max < t_max)
    t_max = ty_max;

  tz_min = ((idz < 0 ? box.max() : box.min()).z - ray.origin.z) * idz;
  tz_max = ((idz < 0 ? box.min() : box.max()).z - ray.origin.z) * idz;

  if (t_min > tz_max || tz_min > t_max)
    return false;

  if (tz_min > t_min)
    t_min = tz_min;
  if (tz_max < t_max)
    t_max = tz_max;

  *out_distance = t_min;

  if (*out_distance < 0) {
    *out_distance = t_max;
    if (*out_distance < 0)
      return false;
  }

  return true;
}

}  // namespace escher