From: Roland Hieber Date: Wed, 3 Feb 2010 02:10:25 +0000 (+0100) Subject: box overlapping X-Git-Url: https://git.rohieb.name/MicroTrace.git/commitdiff_plain/ed5c4078fa0e0833b9e43c3a37c041c4c16e8de2 box overlapping --- diff --git a/Box.cxx b/Box.cxx index 70ab618..d421525 100644 --- a/Box.cxx +++ b/Box.cxx @@ -51,10 +51,66 @@ 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 diff --git a/Box.hxx b/Box.hxx index 1d46e03..ce09c2b 100644 --- a/Box.hxx +++ b/Box.hxx @@ -29,6 +29,7 @@ public: const Vec3f& max() const; private: Vec3f m_min, m_max; + bool OverlapsHelper(Box b) const; }; #endif