InVoxel() for all Primitives, including fix for Triangle::CalcBounds()

[MicroTrace.git] / Box.cxx

diff --git a/Box.cxx b/Box.cxx
index ef9f750..d421525 100644 (file)
--- a/Box.cxx
+++ b/Box.cxx
@@ -1,6 +1,12 @@
 #include "Box.hxx"
+#include "InfinitePlane.hxx"
 
-Box::Box()
+Box::Box() : m_min(Infinity, Infinity, Infinity),
+  m_max(-Infinity, -Infinity, -Infinity)
+{
+}
+
+Box::Box(Vec3f min, Vec3f max) : m_min(min), m_max(max)
 {
 }
 
@@ -10,11 +16,15 @@ Box::~Box()
 
 Box::Box(const Box& b)
 {
+  m_min = b.m_min;
+  m_max = b.m_max;
 }
 
 Box&
 Box::operator=(const Box& b)
 {
+  m_min = b.m_min;
+  m_max = b.m_max;
   return *this;
 }
 
@@ -26,22 +36,139 @@ Box::Clear()
 void
 Box::Extend(const Vec3f& a)
 {
+  // for all three coordinates, move m_max or m_min to the point
+  for(size_t i = 0; i < 3; i++) {
+    if(a[i] > m_max[i]) {
+      m_max[i] = a[i];
+    } else if(a[i] < m_min[i]) {
+      m_min[i] = a[i];
+    } // else: do nothing, coordinate is inside the box
+  }
 }
 
-void 
+void
 Box::Extend(const Box& box)
 {
 }
 
+bool Box::OverlapsHelper(Box b) const {
+  bool overlaps = true;
+  for(size_t i = 0; i < 3; i++) {
+    overlaps &=
+      (m_min[i] < b.min()[i] && b.min()[i] < m_max[i]) ||
+      (m_min[i] < b.max()[i] && b.min()[i] < m_max[i]) ||
+      (m_min[i] > b.min()[i] && b.min()[i] > m_max[i]) ||
+      (m_min[i] > b.max()[i] && b.min()[i] > m_max[i]);
+  }
+  return overlaps;
+}
+
 bool
 Box::Overlaps(const Box& b) const
 {
-  return false;
+  // Boxes overlap if b.m_min or b.m_max are between our m_max and m_min
+  // for all dimensions
+  bool overlaps = OverlapsHelper(b);
+
+  // if that is not enough, swap y coordinates, we could have the following
+  // (sample for 2-dimensional case):
+  //      o----------
+  //      |         |      + denotes crossing,
+  // -----+----o    |      o denotes min/max point
+  // |    |    |    |
+  // |    -----+----o
+  // |         |
+  // o----------
+  if(!overlaps) {
+    Vec3f min = b.min();
+    Vec3f max = b.max();
+    Vec3f new_min(min[0], max[1], min[2]);
+    Vec3f new_max(max[0], min[1], max[2]);
+    Box new_y_box(new_min, new_max);
+    overlaps = OverlapsHelper(new_y_box);
+
+    // and now for y and z coordinates also
+    if(!overlaps) {
+      min = new_y_box.min();
+      max = new_y_box.max();
+      new_min = Vec3f(min[0], min[1], max[2]);
+      new_max = Vec3f(max[0], max[1], min[2]);
+      Box new_yz_box(new_min, new_max);
+      overlaps = OverlapsHelper(new_yz_box);
+
+      // and now for only z coordinates
+      if(!overlaps) {
+        min = new_y_box.min();
+        max = new_y_box.max();
+        new_min = Vec3f(min[0], max[1], min[2]);
+        new_max = Vec3f(max[0], min[1], max[2]);
+        Box new_z_box(new_min, new_max);
+        overlaps = OverlapsHelper(new_z_box);
+        // at this point, we do not need to swap further, as either m_max or
+        // m_min has been tested inside b.
+      }
+    }
+  }
+
+  return overlaps;
 }
 
 void
 Box::Clip(const Ray& ray, float& tnear, float& tfar) const
 {
+  // Note: equations here are the same as in InfinitePlane::Intersect()
+  // t = ((o-a)*n) / (d*n)
+  // o = ray.origin(), d = ray.direction(),
+  // n = surface normal of plane, a = anchor point of plane
+  Vec3f diff_min = m_min - ray.origin(); // o-a
+  Vec3f diff_max = m_max - ray.origin();
+
+  float cos_theta, temp;
+  float tx_near = -Infinity, tx_far = Infinity,
+    ty_near = -Infinity, ty_far = Infinity,
+    tz_near = -Infinity, tz_far = Infinity;
+
+  // clip along x axis
+  if((cos_theta = ray.direction().dot(Vec3f(1,0,0))) != 0) // if not parallel...
+    tx_near = diff_min.dot(Vec3f(1,0,0)) / cos_theta;
+  if((cos_theta = ray.direction().dot(Vec3f(1,0,0))) != 0)
+    tx_far = diff_max.dot(Vec3f(1,0,0)) / cos_theta;
+
+  // we don't know which is nearer, m_min or m_max, so swap them if neccessary
+  if(tx_near > tx_far) {
+    temp = tx_near;
+    tx_near = tx_far;
+    tx_far = temp;
+  }
+
+  // do the same for y axis
+  if((cos_theta = ray.direction().dot(Vec3f(0,1,0))) != 0)
+    ty_near = diff_min.dot(Vec3f(0,1,0)) / cos_theta;
+  if((cos_theta = ray.direction().dot(Vec3f(0,1,0))) != 0)
+    ty_far = diff_max.dot(Vec3f(0,1,0)) / cos_theta;
+  if(ty_near > ty_far) {
+    temp = ty_near;
+    ty_near = ty_far;
+    ty_far = temp;
+  }
+
+  // ...and for z axis
+  if((cos_theta = ray.direction().dot(Vec3f(0,0,1))) != 0)
+    tz_near = diff_min.dot(Vec3f(0,0,1)) / cos_theta;
+  if((cos_theta = ray.direction().dot(Vec3f(0,0,1))) != 0)
+    tz_far = diff_max.dot(Vec3f(0,0,1)) / cos_theta;
+  if(tz_near > tz_far) {
+    temp = tz_near;
+    tz_near = tz_far;
+    tz_far = temp;
+  }
+
+  // now the maximum of "near"s is the entry point of the ray, the minimum
+  // of "far"s is the ray's exit point. Visually speaking: the ray must cross
+  // all three "near" planes before it can be inside the box.
+  // Note: If t_near_max > t_far_min, the ray does not intersect the box
+  tnear = fmax(fmax(tx_near, ty_near), tz_near);
+  tfar = fmin(fmin(tx_far, ty_far), tz_far);
 }
 
 const Vec3f&