Changeset 971

Timestamp:

04/02/07 17:27:28 (3 years ago)

Author:

jakraft

Message:

o Add test for overlap between a box and a plane
o Add test for overlap between a box and a triangle
o Add unit tests for above methods

GeomUtilTests?.cpp | 328 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
MBGeomUtil.cpp | 139 ++++++++++++++++++++++
MBGeomUtil.hpp | 69 +++++++++++
3 files changed, 536 insertions(+)

Location:

MOAB/trunk

Files:

• GeomUtilTests.cpp (modified) (2 diffs)
• MBGeomUtil.cpp (modified) (2 diffs)
• MBGeomUtil.hpp (modified) (1 diff)

MOAB/trunk/GeomUtilTests.cpp

@@ -48 +48 @@
 
 
+void test_box_plane_norm( MBCartVect norm, 
+                          MBCartVect min,
+                          MBCartVect max )
+{
+  MBCartVect c_lower = min;
+  MBCartVect c_upper = max;
+  for (int i = 0; i < 3; ++i)
+    if (norm[i] < 0.0)
+      std::swap(c_lower[i],c_upper[i]);
+  
+  MBCartVect p_below = c_lower - norm;
+  MBCartVect p_lower = c_lower + norm;
+  MBCartVect p_upper = c_upper - norm;
+  MBCartVect p_above = c_upper + norm;
+  
+  double below = -(p_below % norm);
+  double lower = -(p_lower % norm);
+  double upper = -(p_upper % norm);
+  double above = -(p_above % norm);
+  
+  ASSERT( !box_plane_overlap( norm, below, min, max ) );
+  ASSERT(  box_plane_overlap( norm, lower, min, max ) );
+  ASSERT(  box_plane_overlap( norm, upper, min, max ) );
+  ASSERT( !box_plane_overlap( norm, above, min, max ) );
+}
+
+void test_box_plane_axis( int axis, double ns, 
+                          const MBCartVect& min, 
+                          const MBCartVect& max )
+{
+  MBCartVect norm(0.0);
+  norm[axis] = ns;
+  test_box_plane_norm( norm, min, max );
+}
+
+void test_box_plane_edge( int axis1, int axis2, bool flip_axis2,
+                          MBCartVect min, MBCartVect max )
+{
+  MBCartVect norm(0.0);
+  norm[axis1] = max[axis1] - min[axis1];
+  if (flip_axis2)
+    norm[axis2] = min[axis2] - max[axis2];
+  else
+    norm[axis2] = max[axis2] - min[axis2];
+  norm.normalize();
+  
+  test_box_plane_norm( norm, min, max );
+}
+
+void test_box_plane_corner( int xdir, int ydir, int zdir, 
+                            MBCartVect min, MBCartVect max )
+{
+  MBCartVect norm(max - min);
+  norm[0] *= xdir;
+  norm[1] *= ydir;
+  norm[2] *= zdir;
+  test_box_plane_norm( norm, min, max );
+}
+
+void test_box_plane_overlap()
+{
+  const MBCartVect min( -1, -2, -3 );
+  const MBCartVect max(  6,  4,  2 );
+  
+    // test with planes orthogonal to Z axis
+  test_box_plane_axis( 2, 2.0, min, max );
+    // test with planes orthogonal to X axis
+  test_box_plane_axis( 1,-2.0, min, max );
+    // test with planes orthogonal to Y axis
+  test_box_plane_axis( 1, 1.0, min, max );
+
+    // test with plane orthogonal to face diagonals
+  test_box_plane_edge( 0, 1, true,  min, max );
+  test_box_plane_edge( 0, 1, false, min, max );
+  test_box_plane_edge( 0, 2, true,  min, max );
+  test_box_plane_edge( 0, 2, false, min, max );
+  test_box_plane_edge( 2, 1, true,  min, max );
+  test_box_plane_edge( 2, 1, false, min, max );
+  
+    // test with plane orthogonal to box diagonals
+  test_box_plane_corner( 1, 1, 1, min, max );
+  test_box_plane_corner( 1, 1,-1, min, max );
+  test_box_plane_corner( 1,-1,-1, min, max );
+  test_box_plane_corner( 1,-1, 1, min, max );
+}     
+
+void test_box_tri_overlap()
+{
+  MBCartVect coords[3];
+  MBCartVect center, dims;
+  
+    // test box projection within triangle, z-plane
+  coords[0] = MBCartVect( 0, 0, 0 );
+  coords[1] = MBCartVect( 0, 4, 0 );
+  coords[2] = MBCartVect(-4, 0, 0 );
+  center = MBCartVect( -2, 1, 0 );
+  dims = MBCartVect( 1, 0.5, 3 );
+  ASSERT(  box_tri_overlap( coords, center, dims ) );
+    // move box below plane of triangle
+  center[2] = -4;
+  ASSERT( !box_tri_overlap( coords, center, dims ) );
+    // move box above plane of triangle
+  center[2] =  4;
+  ASSERT( !box_tri_overlap( coords, center, dims ) );
+  
+    // test box projection within triangle, x-plane
+  coords[0] = MBCartVect( 3, 3, 0 );
+  coords[1] = MBCartVect( 3, 3, 1 );
+  coords[2] = MBCartVect( 3, 0, 0 );
+  center = MBCartVect( 3, 2.5, .25 );
+  dims = MBCartVect( 0.001, 0.4, .2 );
+  ASSERT(  box_tri_overlap( coords, center, dims ) );
+    // move box below plane of triangle
+  center[0] = 2;
+  ASSERT( !box_tri_overlap( coords, center, dims ) );
+    // move box above plane of triangle
+  center[0] = 4;
+  ASSERT( !box_tri_overlap( coords, center, dims ) );
+  
+    // test tri slices corner at +x,+y,+z
+  coords[0] = MBCartVect(3,1,1);
+  coords[1] = MBCartVect(1,3,1);
+  coords[2] = MBCartVect(1,1,3);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri above the corner
+  ASSERT( !box_tri_overlap( coords, MBCartVect(0,0,0), MBCartVect(1,1,1) ) );
+    // test tri slices corner at -x,-y,-z
+  coords[0] = MBCartVect(-1,1,1);
+  coords[1] = MBCartVect(1,-1,1);
+  coords[2] = MBCartVect(1,1,-1);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri below the corner
+  ASSERT( !box_tri_overlap( coords, MBCartVect(2,2,2),MBCartVect(1,1,1) ) );
+  
+    // test tri slices corner at -x,+y,+z
+  coords[0] = MBCartVect( 0.5, 0.0, 2.5);
+  coords[1] = MBCartVect( 0.5, 2.5, 0.0);
+  coords[2] = MBCartVect(-0.5, 0.0, 0.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri above the corner
+  ASSERT( !box_tri_overlap( coords, MBCartVect(2,1,1), MBCartVect(1,1,1) ) );
+  
+    // test tri slices corner at +x,-y,-z
+  coords[0] = MBCartVect( 0.5, 0.0,-1.5);
+  coords[1] = MBCartVect( 0.5,-1.5, 0.0);
+  coords[2] = MBCartVect( 1.5, 0.0, 0.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri above the corner
+  ASSERT( !box_tri_overlap( coords, MBCartVect(0,1,1), MBCartVect(1,1,1) ) );
+
+    // test tri slices corner at +x,-y,+z
+  coords[0] = MBCartVect( 1.0, 1.0, 2.5 );
+  coords[1] = MBCartVect( 2.5, 1.0, 1.0 );
+  coords[2] = MBCartVect( 1.0,-0.5, 1.0 );
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri above the corner
+  ASSERT( !box_tri_overlap( coords, MBCartVect(-1,1,1), MBCartVect(1,1,1) ) );
+
+    // test tri slices corner at -x,+y,-z  
+  coords[0] = MBCartVect( 1.0,  1.0,-0.5 );
+  coords[1] = MBCartVect(-0.5,  1.0, 1.0 );
+  coords[2] = MBCartVect( 1.0,  2.5, 1.0 );
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri above the corner
+  ASSERT( !box_tri_overlap( coords, MBCartVect(3,1,1), MBCartVect(1,1,1) ) );
+
+    // test tri slices corner at +x,+y,-z
+  coords[0] = MBCartVect(-0.1, 1.0, 1.0);
+  coords[1] = MBCartVect( 1.0,-0.1, 1.0);
+  coords[2] = MBCartVect( 1.0, 1.0,-0.1);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,3), MBCartVect(1,1,1) ) );
+  
+    // test tri slices corner at -x,-y,+z
+  coords[0] = MBCartVect( 2.1, 1.0, 1.0);
+  coords[1] = MBCartVect( 1.0, 2.1, 1.0);
+  coords[2] = MBCartVect( 1.0, 1.0, 2.1);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,-1), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to x at +y,+z passes through triangle
+  coords[0] = MBCartVect( 1.0, 1.0, 3.0);
+  coords[1] = MBCartVect( 1.0, 3.0, 3.0);
+  coords[2] = MBCartVect( 1.0, 3.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,0.3), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to x at +y,-z passes through triangle
+  coords[0] = MBCartVect( 1.0, 3.0, 1.0);
+  coords[1] = MBCartVect( 1.0, 3.0,-1.0);
+  coords[2] = MBCartVect( 1.0, 1.0,-1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,1.7), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to x at -y,-z passes through triangle
+  coords[0] = MBCartVect( 1.0,-1.0, 1.0);
+  coords[1] = MBCartVect( 1.0,-1.0,-1.0);
+  coords[2] = MBCartVect( 1.0, 1.0,-1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,1.7), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to x at -y,+z passes through triangle
+  coords[0] = MBCartVect( 1.0,-1.0, 1.0);
+  coords[1] = MBCartVect( 1.0,-1.0, 3.0);
+  coords[2] = MBCartVect( 1.0, 1.0, 3.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,0.3), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to y at +x,+z passes through triangle
+  coords[0] = MBCartVect( 1.0, 1.0, 3.0);
+  coords[1] = MBCartVect( 3.0, 1.0, 3.0);
+  coords[2] = MBCartVect( 3.0, 1.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,0.3), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to y at -x,+z passes through triangle
+  coords[0] = MBCartVect( 1.0, 1.0, 3.0);
+  coords[1] = MBCartVect(-1.0, 1.0, 3.0);
+  coords[2] = MBCartVect(-1.0, 1.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,0.3), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to y at +x,-z passes through triangle
+  coords[0] = MBCartVect( 1.0, 1.0,-1.0);
+  coords[1] = MBCartVect( 3.0, 1.0,-1.0);
+  coords[2] = MBCartVect( 3.0, 1.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,1.7), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to y at -x,-z passes through triangle
+  coords[0] = MBCartVect( 1.0, 1.0,-1.0);
+  coords[1] = MBCartVect(-1.0, 1.0,-1.0);
+  coords[2] = MBCartVect(-1.0, 1.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1,1,1.7), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to z at +x,+y passes through triangle
+  coords[0] = MBCartVect( 1.0, 3.0, 1.0);
+  coords[1] = MBCartVect( 3.0, 3.0, 1.0);
+  coords[2] = MBCartVect( 3.0, 1.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(0.3,1,1), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to z at +x,-y passes through triangle
+  coords[0] = MBCartVect( 1.0,-1.0, 1.0);
+  coords[1] = MBCartVect( 3.0,-1.0, 1.0);
+  coords[2] = MBCartVect( 3.0, 1.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(0.3,1,1), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to z at -x,+y passes through triangle
+  coords[0] = MBCartVect( 1.0, 3.0, 1.0);
+  coords[1] = MBCartVect(-1.0, 3.0, 1.0);
+  coords[2] = MBCartVect(-1.0, 1.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1.7,1,1), MBCartVect(1,1,1) ) );
+  
+    // box edge parallel to z at -x,-y passes through triangle
+  coords[0] = MBCartVect( 1.0,-1.0, 1.0);
+  coords[1] = MBCartVect(-1.0,-1.0, 1.0);
+  coords[2] = MBCartVect(-1.0, 1.0, 1.0);
+  ASSERT(  box_tri_overlap( coords, MBCartVect(1,1,1), MBCartVect(1,1,1) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(1.7,1,1), MBCartVect(1,1,1) ) );
+  
+    // triangle penetrates +x face
+  coords[0] = MBCartVect( 2.0, 2.0, 2.0 );
+  coords[1] = MBCartVect( 5.0, 3.0, 2.0 );
+  coords[2] = MBCartVect( 5.0, 1.0, 2.0 );
+  ASSERT(  box_tri_overlap( coords, MBCartVect(2,2,2), MBCartVect(2,2,2) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(-1,2,2), MBCartVect(2,2,2) ) );
+  
+    // triangle penetrates -x face
+  coords[0] = MBCartVect( 2.0, 2.0, 2.0 );
+  coords[1] = MBCartVect(-1.0, 3.0, 2.0 );
+  coords[2] = MBCartVect(-1.0, 1.0, 2.0 );
+  ASSERT(  box_tri_overlap( coords, MBCartVect(2,2,2), MBCartVect(2,2,2) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(5,2,2), MBCartVect(2,2,2) ) );
+  
+    // triangle penetrates +y face
+  coords[0] = MBCartVect( 2.0, 2.0, 2.0 );
+  coords[1] = MBCartVect( 3.0, 5.0, 2.0 );
+  coords[2] = MBCartVect( 1.0, 5.0, 2.0 );
+  ASSERT(  box_tri_overlap( coords, MBCartVect(2,2,2), MBCartVect(2,2,2) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(2,-1,2), MBCartVect(2,2,2) ) );
+  
+    // triangle penetrates -y face
+  coords[0] = MBCartVect( 2.0, 2.0, 2.0 );
+  coords[1] = MBCartVect( 3.0,-1.0, 2.0 );
+  coords[2] = MBCartVect( 1.0,-1.0, 2.0 );
+  ASSERT(  box_tri_overlap( coords, MBCartVect(2,2,2), MBCartVect(2,2,2) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(2,5,2), MBCartVect(2,2,2) ) );
+  
+    // triangle penetrates +z face
+  coords[0] = MBCartVect( 2.0, 2.0, 2.0 );
+  coords[1] = MBCartVect( 2.0, 3.0, 5.0 );
+  coords[2] = MBCartVect( 2.0, 1.0, 5.0 );
+  ASSERT(  box_tri_overlap( coords, MBCartVect(2,2,2), MBCartVect(2,2,2) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(2,2,-1), MBCartVect(2,2,2) ) );
+  
+    // triangle penetrates -z face
+  coords[0] = MBCartVect( 2.0, 2.0, 2.0 );
+  coords[1] = MBCartVect( 2.0, 3.0,-1.0 );
+  coords[2] = MBCartVect( 2.0, 1.0,-1.0 );
+  ASSERT(  box_tri_overlap( coords, MBCartVect(2,2,2), MBCartVect(2,2,2) ) );
+    // test with tri outside box
+  ASSERT( !box_tri_overlap( coords, MBCartVect(2,2,5), MBCartVect(2,2,2) ) );
+}
 
 void test_ray_tri_intersect()
@@ -272 +598 @@
 int main()
 {
+  test_box_plane_overlap();
+  test_box_tri_overlap();
   test_ray_tri_intersect();
   test_closest_location_on_tri();

MOAB/trunk/MBGeomUtil.cpp

@@ -21 +21 @@
 #include "MBCartVect.hpp"
 #include <cmath>
+#include <algorithm>
 
 namespace MBGeomUtil {
@@ -76 +77 @@
   return true;
 }
+
+bool box_plane_overlap( const MBCartVect& normal,
+                        double d,
+                        MBCartVect min,
+                        MBCartVect max )
+{
+  if (normal[0] < 0.0)
+    std::swap( min[0], max[0] );
+  if (normal[1] < 0.0)
+    std::swap( min[1], max[1] );
+  if (normal[2] < 0.0)
+    std::swap( min[2], max[2] );
+  
+  return (normal % min <= -d) && (normal % max >= -d);
+}
+
+
+#define CHECK_RANGE( A, B, R ) \
+  if ((A) < (B)) { \
+    if ((A) > (R) || (B) < -(R)) \
+      return false; \
+  } \
+  else if ((B) > (R) || (A) < -(R)) \
+    return false
+
+/* Adapted from: http://jgt.akpeters.com/papers/AkenineMoller01/tribox.html
+ * Use separating axis theorem to test for overlap between triangle
+ * and axis-aligned box.
+ *
+ * Test for overlap in these directions:
+ * 1) {x,y,z}-directions 
+ * 2) normal of triangle
+ * 3) crossprod of triangle edge with {x,y,z}-direction
+ */
+bool box_tri_overlap( const MBCartVect vertices[3],
+                      const MBCartVect& box_center,
+                      const MBCartVect& box_dims )
+{
+    // translate everthing such that box is centered at origin
+  const MBCartVect v0( vertices[0] - box_center );
+  const MBCartVect v1( vertices[1] - box_center );
+  const MBCartVect v2( vertices[2] - box_center );
+
+  // do case 1) tests
+  if (v0[0] > box_dims[0] && v1[0] > box_dims[0] && v2[0] > box_dims[0])
+    return false;
+  if (v0[1] > box_dims[1] && v1[1] > box_dims[1] && v2[1] > box_dims[1])
+    return false;
+  if (v0[2] > box_dims[2] && v1[2] > box_dims[2] && v2[2] > box_dims[2])
+    return false;
+  if (v0[0] < -box_dims[0] && v1[0] < -box_dims[0] && v2[0] < -box_dims[0])
+    return false;
+  if (v0[1] < -box_dims[1] && v1[1] < -box_dims[1] && v2[1] < -box_dims[1])
+    return false;
+  if (v0[2] < -box_dims[2] && v1[2] < -box_dims[2] && v2[2] < -box_dims[2])
+    return false;
+  
+    // compute triangle edge vectors
+  const MBCartVect e0( vertices[1] - vertices[0] );
+  const MBCartVect e1( vertices[2] - vertices[1] );
+  const MBCartVect e2( vertices[0] - vertices[2] );
+  
+    // do case 3) tests 
+  double fex, fey, fez, p0, p1, p2, rad;
+  fex = fabs(e0[0]);
+  fey = fabs(e0[1]);
+  fez = fabs(e0[2]);
+  
+  p0 = e0[2]*v0[1] - e0[1]*v0[2];
+  p2 = e0[2]*v2[1] - e0[1]*v2[2];
+  rad = fez * box_dims[1] + fey * box_dims[2];
+  CHECK_RANGE( p0, p2, rad );
+  
+  p0 = -e0[2]*v0[0] + e0[0]*v0[2];
+  p2 = -e0[2]*v2[0] + e0[0]+v2[2];
+  rad = fez * box_dims[0] + fex * box_dims[2];
+  CHECK_RANGE( p0, p2, rad );
+    
+  p1 = e0[1]*v1[0] - e0[0]*v1[1];
+  p2 = e0[1]*v2[0] - e0[0]*v2[1];
+  rad = fey * box_dims[0] + fex * box_dims[1];
+  CHECK_RANGE( p1, p2, rad );
+  
+  fex = fabs(e1[0]);
+  fey = fabs(e1[1]);
+  fez = fabs(e1[2]);
+  
+  p0 = e1[2]*v0[1] - e1[1]*v0[2];
+  p2 = e1[2]*v2[1] - e1[1]*v2[2];
+  rad = fez * box_dims[1] + fey * box_dims[2];
+  CHECK_RANGE( p0, p2, rad );
+  
+  p0 = -e1[2]*v0[0] + e1[0]*v0[2];
+  p2 = -e1[2]*v2[0] + e1[0]*v2[2];
+  rad = fez * box_dims[0] + fex * box_dims[2];
+  CHECK_RANGE( p0, p2, rad );
+  
+  p0 = e1[1]*v0[0] - e1[0]*v0[1];
+  p1 = e1[1]*v1[0] - e1[0]*v1[1];
+  rad = fey * box_dims[0] + fex * box_dims[1];
+  CHECK_RANGE( p0, p1, rad );
+  
+  fex = fabs(e2[0]);
+  fey = fabs(e2[1]);
+  fez = fabs(e2[2]);
+  
+  p0 = e2[2]*v0[1] - e2[1]*v0[2];
+  p1 = e2[2]*v1[1] - e2[1]*v1[2];
+  rad = fez * box_dims[1] + fey * box_dims[2];
+  CHECK_RANGE( p0, p1, rad );
+  
+  p0 = -e2[2]*v0[0] + e2[0]*v0[2];
+  p1 = -e2[2]*v1[0] + e2[0]*v1[2];
+  rad = fez * box_dims[0] + fex * box_dims[2];
+  CHECK_RANGE( p0, p1, rad );
+  
+  p1 = e2[1]*v1[0] - e2[0]*v1[1];
+  p2 = e2[1]*v2[0] - e2[0]*v2[1];
+  rad = fey * box_dims[0] + fex * box_dims[1];
+  CHECK_RANGE( p1, p2, rad );
+  
+  // do case 2) test
+  MBCartVect n = e0 * e1;
+  return box_plane_overlap( n, -(n % v0), -box_dims, box_dims );
+}
+  
+
+bool box_tri_overlap( const MBCartVect  triangle_corners[3],
+                      const MBCartVect& box_min_corner,
+                      const MBCartVect& box_max_corner,
+                      double            tolerance )
+{
+  const MBCartVect box_center = 0.5 * (box_max_corner + box_min_corner);
+  const MBCartVect box_hf_dim = 0.5 * (box_max_corner - box_min_corner);
+  return box_tri_overlap( triangle_corners,
+                          box_center,
+                          box_hf_dim + MBCartVect(tolerance) );
+} 
 
 //from: http://www.geometrictools.com/Documentation/DistancePoint3Triangle3.pdf#search=%22closest%20point%20on%20triangle%22

MOAB/trunk/MBGeomUtil.hpp

@@ -33 +33 @@
                         double& t_out,
                         const double* ray_length = 0 );
+
+/**\brief Test if plane intersects axis-aligned box
+ *
+ * Test for intersection between an unbounded plane and
+ * an axis-aligned box.
+ *\param plane_normal Vector in plane normal direction (need *not*
+ *                    be a unit vector).  The N in 
+ *                    the plane equation: N . X + D = 0
+ *\param plane_coeff  The scalar 'D' term in the plane equation:
+ *                    N . X + D = 0
+ *\param box_min_corner The smallest coordinates of the box along each
+ *                    axis.  The corner of the box for which all three
+ *                    coordinate values are smaller than those of any
+ *                    other corner.  The X, Y, Z values for the planes
+ *                    normal to those axes and bounding the box on the
+ *                    -X, -Y, and -Z sides respectively.
+ *\param box_max_corner The largest coordinates of the box along each
+ *                    axis.  The corner of the box for which all three
+ *                    coordinate values are larger than those of any
+ *                    other corner.  The X, Y, Z values for the planes
+ *                    normal to those axes and bounding the box on the
+ *                    +X, +Y, and +Z sides respectively.
+ *\return true if overlap, false otherwise.
+ */
+bool box_plane_overlap( const MBCartVect& plane_normal, 
+                        double            plane_coeff,
+                        MBCartVect        box_min_corner, 
+                        MBCartVect        box_max_corner );
+
+/**\brief Test if triangle intersects axis-aligned box
+ *
+ * Test if a triangle intersects an axis-aligned box.
+ *\param triangle_corners  The corners of the triangle.
+ *\param box_min_corner The smallest coordinates of the box along each
+ *                    axis.  The corner of the box for which all three
+ *                    coordinate values are smaller than those of any
+ *                    other corner.  The X, Y, Z values for the planes
+ *                    normal to those axes and bounding the box on the
+ *                    -X, -Y, and -Z sides respectively.
+ *\param box_max_corner The largest coordinates of the box along each
+ *                    axis.  The corner of the box for which all three
+ *                    coordinate values are larger than those of any
+ *                    other corner.  The X, Y, Z values for the planes
+ *                    normal to those axes and bounding the box on the
+ *                    +X, +Y, and +Z sides respectively.
+ *\param tolerance    The tolerance used in the intersection test.  The box
+ *                    size is increased by this amount before the intersection
+ *                    test.
+ *\return true if overlap, false otherwise.
+ */
+bool box_tri_overlap( const MBCartVect  triangle_corners[3],
+                      const MBCartVect& box_min_corner,
+                      const MBCartVect& box_max_corner,
+                      double            tolerance );
+
+/**\brief Test if triangle intersects axis-aligned box
+ *
+ * Test if a triangle intersects an axis-aligned box.
+ *\param triangle_corners  The corners of the triangle.
+ *\param box_center   The center of the box.
+ *\param box_hanf_dims The distance along each axis, respectively, from the
+ *                    box_center to the boundary of the box.
+ *\return true if overlap, false otherwise.
+ */
+bool box_tri_overlap( const MBCartVect  triangle_corners[3],
+                      const MBCartVect& box_center,
+                      const MBCartVect& box_half_dims );
+
+                       
 
 /**\brief find closest location on triangle