[MOAB-dev] r3133 - MOAB/trunk
kraftche at cae.wisc.edu
kraftche at cae.wisc.edu
Fri Sep 4 16:04:23 CDT 2009
Author: kraftche
Date: 2009-09-04 16:04:22 -0500 (Fri, 04 Sep 2009)
New Revision: 3133
Modified:
MOAB/trunk/MBAdaptiveKDTree.cpp
MOAB/trunk/MBAdaptiveKDTree.hpp
MOAB/trunk/MBBSPTree.cpp
MOAB/trunk/MBBSPTree.hpp
MOAB/trunk/adaptive_kd_tree_tests.cpp
MOAB/trunk/bsp_tree_test.cpp
Log:
add some utility methods
Modified: MOAB/trunk/MBAdaptiveKDTree.cpp
===================================================================
--- MOAB/trunk/MBAdaptiveKDTree.cpp 2009-09-04 18:01:57 UTC (rev 3132)
+++ MOAB/trunk/MBAdaptiveKDTree.cpp 2009-09-04 21:04:22 UTC (rev 3133)
@@ -716,6 +716,42 @@
}
+bool MBAdaptiveKDTreeIter::is_sibling( const MBAdaptiveKDTreeIter& other_leaf ) const
+{
+ const size_t s = mStack.size();
+ return (s > 1) && (s == other_leaf.mStack.size()) &&
+ (other_leaf.mStack[s-2].entity == mStack[s-2].entity) &&
+ other_leaf.handle() != handle();
+}
+
+bool MBAdaptiveKDTreeIter::is_sibling( MBEntityHandle other_leaf ) const
+{
+ if (mStack.size() < 2 || other_leaf == handle())
+ return false;
+ MBEntityHandle parent = mStack[mStack.size()-2].entity;
+ childVect.clear();
+ MBErrorCode rval = tool()->moab()->get_child_meshsets( parent, childVect );
+ if (MB_SUCCESS != rval || childVect.size() != 2) {
+ assert(false);
+ return false;
+ }
+ return childVect[0] == other_leaf || childVect[1] == other_leaf;
+}
+
+bool MBAdaptiveKDTreeIter::sibling_is_forward() const
+{
+ if (mStack.size() < 2) // if root
+ return false;
+ MBEntityHandle parent = mStack[mStack.size()-2].entity;
+ childVect.clear();
+ MBErrorCode rval = tool()->moab()->get_child_meshsets( parent, childVect );
+ if (MB_SUCCESS != rval || childVect.size() != 2) {
+ assert(false);
+ return false;
+ }
+ return childVect[0] == handle();
+}
+
static MBErrorCode intersect_children_with_elems(
MBAdaptiveKDTree* tool,
const MBRange& elems,
Modified: MOAB/trunk/MBAdaptiveKDTree.hpp
===================================================================
--- MOAB/trunk/MBAdaptiveKDTree.hpp 2009-09-04 18:01:57 UTC (rev 3132)
+++ MOAB/trunk/MBAdaptiveKDTree.hpp 2009-09-04 21:04:22 UTC (rev 3133)
@@ -302,7 +302,17 @@
//! Get max corner of axis-aligned box for current leaf
const double* box_max() const
{ return mBox[BMAX]; }
-
+
+ double volume() const
+ { return (mBox[BMAX][0] - mBox[BMIN][0]) *
+ (mBox[BMAX][1] - mBox[BMIN][1]) *
+ (mBox[BMAX][2] - mBox[BMIN][2]); }
+
+ //! test if a plane intersects the leaf box
+ bool intersects( const MBAdaptiveKDTree::Plane& plane ) const
+ { return mBox[BMIN][plane.norm] <= plane.coord &&
+ mBox[BMAX][plane.norm] >= plane.coord; }
+
//! Get depth in tree. root is at depth of 1.
unsigned depth() const
{ return mStack.size(); }
@@ -369,6 +379,20 @@
//! Get split plane that separates this node from its immediate sibling.
MBErrorCode get_parent_split_plane( MBAdaptiveKDTree::Plane& plane ) const;
+
+ //! Return true if thos node and the passed node share the
+ //! same immediate parent.
+ bool is_sibling( const MBAdaptiveKDTreeIter& other_leaf ) const;
+
+ //! Return true if thos node and the passed node share the
+ //! same immediate parent.
+ bool is_sibling( MBEntityHandle other_leaf ) const;
+
+ //! Returns true if calling step() will advance to the
+ //! immediate sibling of the current node. Returns false
+ //! if current node is root or back() will move to the
+ //! immediate sibling.
+ bool sibling_is_forward( ) const;
};
#endif
Modified: MOAB/trunk/MBBSPTree.cpp
===================================================================
--- MOAB/trunk/MBBSPTree.cpp 2009-09-04 18:01:57 UTC (rev 3132)
+++ MOAB/trunk/MBBSPTree.cpp 2009-09-04 21:04:22 UTC (rev 3133)
@@ -507,6 +507,42 @@
return tool()->get_split_plane( parent, plane );
}
+bool MBBSPTreeIter::is_sibling( const MBBSPTreeIter& other_leaf ) const
+{
+ const size_t s = mStack.size();
+ return (s > 1) && (s == other_leaf.mStack.size()) &&
+ (other_leaf.mStack[s-2] == mStack[s-2]) &&
+ other_leaf.handle() != handle();
+}
+
+bool MBBSPTreeIter::is_sibling( MBEntityHandle other_leaf ) const
+{
+ if (mStack.size() < 2 || other_leaf == handle())
+ return false;
+ MBEntityHandle parent = mStack[mStack.size()-2];
+ childVect.clear();
+ MBErrorCode rval = tool()->moab()->get_child_meshsets( parent, childVect );
+ if (MB_SUCCESS != rval || childVect.size() != 2) {
+ assert(false);
+ return false;
+ }
+ return childVect[0] == other_leaf || childVect[1] == other_leaf;
+}
+
+bool MBBSPTreeIter::sibling_is_forward() const
+{
+ if (mStack.size() < 2) // if root
+ return false;
+ MBEntityHandle parent = mStack[mStack.size()-2];
+ childVect.clear();
+ MBErrorCode rval = tool()->moab()->get_child_meshsets( parent, childVect );
+ if (MB_SUCCESS != rval || childVect.size() != 2) {
+ assert(false);
+ return false;
+ }
+ return childVect[0] == handle();
+}
+
MBErrorCode MBBSPTreeBoxIter::initialize( MBBSPTree* tool_ptr,
MBEntityHandle root,
const double* point )
@@ -894,6 +930,108 @@
return MB_SUCCESS;
}
+// result = a - b
+static void subtr( double result[3], const double a[3], const double b[3] )
+{
+ result[0] = a[0] - b[0];
+ result[1] = a[1] - b[1];
+ result[2] = a[2] - b[2];
+}
+
+// result = a + b + c + d
+static void sum( double result[3],
+ const double a[3],
+ const double b[3],
+ const double c[3],
+ const double d[3] )
+{
+ result[0] = a[0] + b[0] + c[0] + d[0];
+ result[1] = a[1] + b[1] + c[1] + d[1];
+ result[2] = a[2] + b[2] + c[2] + d[2];
+}
+
+// result = a cross b
+static void cross( double result[3], const double a[3], const double b[3] )
+{
+ result[0] = a[1]*b[2] - a[2]*b[1];
+ result[1] = a[2]*b[0] - a[0]*b[2];
+ result[2] = a[0]*b[1] - a[1]*b[0];
+}
+
+static double dot( const double a[3], const double b[3] )
+{
+ return a[0]*b[0] + a[1]*b[1] + a[2]*b[2];
+}
+
+double MBBSPTreeBoxIter::volume() const
+{
+ // have planar sides, so use mid-face tripple product
+ double f1[3], f2[3], f3[3], f4[3], f5[3], f6[3];
+ sum( f1, leafCoords[0], leafCoords[1], leafCoords[4], leafCoords[5] );
+ sum( f2, leafCoords[1], leafCoords[2], leafCoords[5], leafCoords[6] );
+ sum( f3, leafCoords[2], leafCoords[3], leafCoords[6], leafCoords[7] );
+ sum( f4, leafCoords[0], leafCoords[3], leafCoords[4], leafCoords[7] );
+ sum( f5, leafCoords[0], leafCoords[1], leafCoords[2], leafCoords[3] );
+ sum( f6, leafCoords[4], leafCoords[5], leafCoords[6], leafCoords[7] );
+ double v13[3], v24[3], v65[3];
+ subtr( v13, f1, f3 );
+ subtr( v24, f2, f4 );
+ subtr( v65, f6, f5 );
+ double cr[3];
+ cross( cr, v13, v24 );
+ return (1./64) * dot( cr, v65 );
+}
+
+MBBSPTreeBoxIter::XSect
+MBBSPTreeBoxIter::splits( const MBBSPTree::Plane& plane ) const
+{
+ // test each corner relative to the plane
+ unsigned result = 0;
+ for (unsigned i = 0; i < 8u; ++i) {
+ double d = plane.signed_distance( leafCoords[i] );
+ // if corner is on plane, than intersection
+ // will result in a degenerate hex
+ if (fabs(d) < MBBSPTree::epsilon())
+ return NONHEX;
+ // if mark vertices above plane
+ if (d > 0.0)
+ result |= 1<<i;
+ }
+
+ switch (result) {
+ // if all vertices or no vertices above plane,
+ // then plane doesn't intersect
+ case 0:
+ case 0xFF:
+ return MISS;
+
+ // if there are four vertices above the plane
+ // and they compose a single face of the hex,
+ // then the cut will result in two hexes
+ case B0154:
+ case B1265:
+ case B2376:
+ case B3047:
+ case B3210:
+ case B4567:
+ return SPLIT;
+
+ // otherwise intersects, but split would not result
+ // in two hexahedrons
+ default:
+ return NONHEX;
+ }
+}
+
+bool MBBSPTreeBoxIter::intersects( const MBBSPTree::Plane& plane ) const
+{
+ // test each corner relative to the plane
+ unsigned count = 0;
+ for (unsigned i = 0; i < 8u; ++i)
+ count += plane.above( leafCoords[i] );
+ return count > 0 && count < 8u;
+}
+
MBErrorCode MBBSPTreeBoxIter::sibling_side( SideBits& side_out ) const
{
if (mStack.size() < 2) // at tree root
Modified: MOAB/trunk/MBBSPTree.hpp
===================================================================
--- MOAB/trunk/MBBSPTree.hpp 2009-09-04 18:01:57 UTC (rev 3132)
+++ MOAB/trunk/MBBSPTree.hpp 2009-09-04 21:04:22 UTC (rev 3133)
@@ -111,6 +111,9 @@
void set( const double pt1[3], const double pt2[3], const double pt3[3] );
+ void set( double i, double j, double k, double coeff )
+ { *this = Plane( i, j, k, coeff ); }
+
/** Create Y = 1 plane by doing set( Y, 1.0 ); */
void set( Axis normal, double point_on_axis )
{
@@ -277,6 +280,20 @@
//! Get split plane that separates this node from its immediate sibling.
MBErrorCode get_parent_split_plane( MBBSPTree::Plane& plane ) const;
+
+ //! Return true if thos node and the passed node share the
+ //! same immediate parent.
+ bool is_sibling( const MBBSPTreeIter& other_leaf ) const;
+
+ //! Return true if thos node and the passed node share the
+ //! same immediate parent.
+ bool is_sibling( MBEntityHandle other_leaf ) const;
+
+ //! Returns true if calling step() will advance to the
+ //! immediate sibling of the current node. Returns false
+ //! if current node is root or back() will move to the
+ //! immediate sibling.
+ bool sibling_is_forward( ) const;
};
class MBBSPTreeBoxIter : public MBBSPTreeIter
@@ -340,9 +357,19 @@
//! the iterator. Calling step() will not work.
MBErrorCode back() { return MBBSPTreeIter::back(); }
- //! Get coordinates of box corners, in Exodus II hexahedral ordering.
+ //! Get coordinates of box corners, in Exodus II hexahedral ordering.
MBErrorCode get_box_corners( double coords[8][3] ) const;
+ //! Get volume of leaf box
+ double volume() const;
+
+ //! test if a plane intersects the leaf box
+ enum XSect { MISS = 0, SPLIT = 1, NONHEX = -1 };
+ XSect splits( const MBBSPTree::Plane& plane ) const;
+
+ //! test if a plane intersects the leaf box
+ bool intersects( const MBBSPTree::Plane& plane ) const;
+
//! Return the side of the box bounding this tree node
//! that is shared with the immediately adjacent sibling
//! (the tree node that shares a common parent node with
Modified: MOAB/trunk/adaptive_kd_tree_tests.cpp
===================================================================
--- MOAB/trunk/adaptive_kd_tree_tests.cpp 2009-09-04 18:01:57 UTC (rev 3132)
+++ MOAB/trunk/adaptive_kd_tree_tests.cpp 2009-09-04 21:04:22 UTC (rev 3133)
@@ -395,7 +395,7 @@
*/
void create_simple_2d_tree( MBAdaptiveKDTree& tool,
MBEntityHandle& root,
- MBEntityHandle leaves[9] )
+ MBEntityHandle leaves[9] = 0 )
{
MBErrorCode rval;
MBAdaptiveKDTree::Plane plane;
@@ -432,13 +432,15 @@
rval = tool.split_leaf( iter, plane );
CHECK( MB_SUCCESS == rval );
CHECK( box_equal( iter, -5, -4, -1, -1, -2, 1 ) );
- leaves[1] = iter.handle();
+ if (leaves)
+ leaves[1] = iter.handle();
// leaf [2]
rval = iter.step();
CHECK( MB_SUCCESS == rval );
CHECK( box_equal( iter, -5, -2, -1, -1, 0, 1 ) );
- leaves[2] = iter.handle();
+ if (leaves)
+ leaves[2] = iter.handle();
// non-leaf right of split plane (2)
rval = iter.step();
@@ -451,13 +453,15 @@
rval = tool.split_leaf( iter, plane );
CHECK( MB_SUCCESS == rval );
CHECK( box_equal( iter, -1, -4, -1, 4, 0, 1 ) );
- leaves[3] = iter.handle();
+ if (leaves)
+ leaves[3] = iter.handle();
// leaf [4]
rval = iter.step();
CHECK( MB_SUCCESS == rval );
CHECK( box_equal( iter, 4, -4, -1, 5, 0, 1 ) );
- leaves[4] = iter.handle();
+ if (leaves)
+ leaves[4] = iter.handle();
// non-leaf above split plane (1)
rval = iter.step();
@@ -477,13 +481,15 @@
rval = tool.split_leaf( iter, plane );
CHECK( MB_SUCCESS == rval );
CHECK( box_equal( iter, -5, 0, -1, -3, 4, 1 ) );
- leaves[5] = iter.handle();
+ if (leaves)
+ leaves[5] = iter.handle();
// leaf [6];
rval = iter.step();
CHECK( MB_SUCCESS == rval );
CHECK( box_equal( iter, -3, 0, -1, 0, 4, 1 ) );
- leaves[6] = iter.handle();
+ if (leaves)
+ leaves[6] = iter.handle();
// non-leaf right of split plane (5)
rval = iter.step();
@@ -496,13 +502,15 @@
rval = tool.split_leaf( iter, plane );
CHECK( MB_SUCCESS == rval );
CHECK( box_equal( iter, 0, 0, -1, 5, 3, 1 ) );
- leaves[7] = iter.handle();
+ if (leaves)
+ leaves[7] = iter.handle();
// leaf [8];
rval = iter.step();
CHECK( MB_SUCCESS == rval );
CHECK( box_equal( iter, 0, 3, -1, 5, 4, 1 ) );
- leaves[8] = iter.handle();
+ if (leaves)
+ leaves[8] = iter.handle();
// the end
rval = iter.step();
@@ -1062,8 +1070,152 @@
check_point_in_triangles( &moab, &tris[i], 1, tript );
}
}
+
+void test_leaf_volume()
+{
+ MBCore moab;
+ MBAdaptiveKDTree tool( &moab );
+ MBEntityHandle root;
+ create_simple_2d_tree( tool, root );
+ MBAdaptiveKDTreeIter iter;
+ MBErrorCode rval = tool.get_tree_iterator( root, iter );
+ CHECK_ERR(rval);
+ CHECK_REAL_EQUAL( 16.0, iter.volume(), 1e-12 ); // 1
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 16.0, iter.volume(), 1e-12 ); // 2
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 40.0, iter.volume(), 1e-12 ); // 3
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 8.0, iter.volume(), 1e-12 ); // 4
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 16.0, iter.volume(), 1e-12 ); // 5
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 24.0, iter.volume(), 1e-12 ); // 6
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 30.0, iter.volume(), 1e-12 ); // 7
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 10.0, iter.volume(), 1e-12 ); // 8
+}
+
+void test_leaf_sibling()
+{
+ MBErrorCode rval;
+ MBCore moab;
+ MBAdaptiveKDTree tool( &moab );
+ MBEntityHandle root;
+
+ create_simple_2d_tree( tool, root );
+ MBAdaptiveKDTreeIter iter1, iter2;
+ rval = tool.get_tree_iterator( root, iter1 );
+ CHECK_ERR(rval);
+ rval = tool.get_tree_iterator( root, iter2 );
+ CHECK_ERR(rval);
+
+ // iter1 == 1, iter2 == 1
+ CHECK( !iter1.is_sibling( iter1 ) );
+ CHECK( !iter1.is_sibling( iter1.handle() ) );
+ CHECK( !iter1.is_sibling( iter2 ) );
+ CHECK( iter1.sibling_is_forward() );
+
+ // iter1 == 1, iter2 == 2
+ rval = iter2.step();
+ CHECK_ERR(rval);
+ CHECK( iter1.is_sibling( iter2 ) );
+ CHECK( iter1.is_sibling( iter2.handle() ) );
+ CHECK( iter2.is_sibling( iter1 ) );
+ CHECK( iter2.is_sibling( iter1.handle() ) );
+ CHECK( !iter2.sibling_is_forward() );
+
+ // iter1 == 1, iter2 == 3
+ rval = iter2.step();
+ CHECK_ERR(rval);
+ CHECK( !iter1.is_sibling( iter2 ) );
+ CHECK( !iter1.is_sibling( iter2.handle() ) );
+ CHECK( !iter2.is_sibling( iter1 ) );
+ CHECK( !iter2.is_sibling( iter1.handle() ) );
+ CHECK( iter2.sibling_is_forward() );
+
+ // iter1 == 2, iter2 == 3
+ rval = iter1.step();
+ CHECK_ERR(rval);
+ CHECK( !iter1.is_sibling( iter2 ) );
+ CHECK( !iter1.is_sibling( iter2.handle() ) );
+ CHECK( !iter2.is_sibling( iter1 ) );
+ CHECK( !iter2.is_sibling( iter1.handle() ) );
+ CHECK( !iter1.sibling_is_forward() );
+
+ // iter1 == 4, iter2 == 3
+ rval = iter1.step();
+ CHECK_ERR(rval);
+ CHECK_EQUAL( iter1.handle(), iter2.handle() );
+ rval = iter1.step();
+ CHECK_ERR(rval);
+ CHECK( iter1.is_sibling( iter2 ) );
+ CHECK( iter1.is_sibling( iter2.handle() ) );
+ CHECK( iter2.is_sibling( iter1 ) );
+ CHECK( iter2.is_sibling( iter1.handle() ) );
+ CHECK( !iter1.sibling_is_forward() );
+}
+
+
+void test_leaf_intersects_plane()
+{
+ MBErrorCode rval;
+ MBCore moab;
+ MBAdaptiveKDTree tool( &moab );
+
+ MBEntityHandle root;
+ const double min[3] = { -5, -4, -1 };
+ const double max[3] = { 1, 2, 3 };
+ rval = tool.create_tree( min, max, root );
+ CHECK_ERR(rval);
+
+ MBAdaptiveKDTreeIter iter;
+ rval = tool.get_tree_iterator( root, iter );
+ CHECK_ERR(rval);
+
+ MBAdaptiveKDTree::Plane x1 = { min[0] - 1, MBAdaptiveKDTree::X };
+ CHECK( !iter.intersects( x1 ) );
+ MBAdaptiveKDTree::Plane x2 = { min[0] , MBAdaptiveKDTree::X };
+ CHECK( iter.intersects( x2 ) );
+ MBAdaptiveKDTree::Plane x3 = { min[0] + 1, MBAdaptiveKDTree::X };
+ CHECK( iter.intersects( x3 ) );
+ MBAdaptiveKDTree::Plane x4 = { max[0] - 1, MBAdaptiveKDTree::X };
+ CHECK( iter.intersects( x4 ) );
+ MBAdaptiveKDTree::Plane x5 = { max[0] , MBAdaptiveKDTree::X };
+ CHECK( iter.intersects( x5 ) );
+ MBAdaptiveKDTree::Plane x6 = { max[0] + 1, MBAdaptiveKDTree::X };
+ CHECK( !iter.intersects( x6 ) );
+
+ MBAdaptiveKDTree::Plane y1 = { min[1] - 1, MBAdaptiveKDTree::Y };
+ CHECK( !iter.intersects( y1 ) );
+ MBAdaptiveKDTree::Plane y2 = { min[1] , MBAdaptiveKDTree::Y };
+ CHECK( iter.intersects( y2 ) );
+ MBAdaptiveKDTree::Plane y3 = { min[1] + 1, MBAdaptiveKDTree::Y };
+ CHECK( iter.intersects( y3 ) );
+ MBAdaptiveKDTree::Plane y4 = { max[1] - 1, MBAdaptiveKDTree::Y };
+ CHECK( iter.intersects( y4 ) );
+ MBAdaptiveKDTree::Plane y5 = { max[1] , MBAdaptiveKDTree::Y };
+ CHECK( iter.intersects( y5 ) );
+ MBAdaptiveKDTree::Plane y6 = { max[1] + 1, MBAdaptiveKDTree::Y };
+ CHECK( !iter.intersects( y6 ) );
+
+ MBAdaptiveKDTree::Plane z1 = { min[2] - 1, MBAdaptiveKDTree::Z };
+ CHECK( !iter.intersects( z1 ) );
+ MBAdaptiveKDTree::Plane z2 = { min[2] , MBAdaptiveKDTree::Z };
+ CHECK( iter.intersects( z2 ) );
+ MBAdaptiveKDTree::Plane z3 = { min[2] + 1, MBAdaptiveKDTree::Z };
+ CHECK( iter.intersects( z3 ) );
+ MBAdaptiveKDTree::Plane z4 = { max[2] - 1, MBAdaptiveKDTree::Z };
+ CHECK( iter.intersects( z4 ) );
+ MBAdaptiveKDTree::Plane z5 = { max[2] , MBAdaptiveKDTree::Z };
+ CHECK( iter.intersects( z5 ) );
+ MBAdaptiveKDTree::Plane z6 = { max[2] + 1, MBAdaptiveKDTree::Z };
+ CHECK( !iter.intersects( z6 ) );
+}
+
int main()
{
int error_count = 0;
@@ -1074,6 +1226,8 @@
error_count += RUN_TEST(test_sphere_intersect_triangles);
error_count += RUN_TEST(test_ray_intersect_triangles);
error_count += RUN_TEST(test_tree_merge_nodes);
- error_count += RUN_TEST(test_tree_merge_nodes);
+ error_count += RUN_TEST(test_leaf_volume);
+ error_count += RUN_TEST(test_leaf_sibling);
+ error_count += RUN_TEST(test_leaf_intersects_plane);
return error_count;
}
Modified: MOAB/trunk/bsp_tree_test.cpp
===================================================================
--- MOAB/trunk/bsp_tree_test.cpp 2009-09-04 18:01:57 UTC (rev 3132)
+++ MOAB/trunk/bsp_tree_test.cpp 2009-09-04 21:04:22 UTC (rev 3133)
@@ -12,6 +12,9 @@
void test_leaf_containing_point_unbounded_tree();
void test_merge_leaf();
void test_box_iter_neighbors();
+void test_leaf_sibling();
+void test_leaf_volume();
+void test_leaf_splits_intersects();
int main()
{
@@ -26,6 +29,9 @@
failures += RUN_TEST( test_leaf_containing_point_unbounded_tree );
failures += RUN_TEST( test_merge_leaf );
failures += RUN_TEST( test_box_iter_neighbors );
+ failures += RUN_TEST( test_leaf_sibling );
+ failures += RUN_TEST( test_leaf_volume );
+ failures += RUN_TEST( test_leaf_splits_intersects );
return failures;
}
@@ -1460,3 +1466,238 @@
CHECK_EQUAL( expected, neighbors( iter, leaves, MBBSPTreeBoxIter::B1265, 1e-6 ) );
}
+
+void test_leaf_sibling()
+{
+ MBCore moab;
+ MBBSPTree tool( &moab );
+ MBErrorCode rval;
+ MBEntityHandle root;
+ MBBSPTreeIter iter;
+
+
+/* Build Tree
+
+ 1.0 +---------+--------------+
+ | A | |
+ | | |
+ 0.7 +---------+ C |
+ | | |
+ | | |
+ | B | |
+ | +--------------+ 0.3
+ | | D |
+ | | |
+ 0.0 +---------+--------------+
+ 0.0 0.4 1.0 */
+
+ const MBBSPTree::Plane X_split(1.0, 0.0, 0.0,-0.4);
+ const MBBSPTree::Plane AB_split(0.0,-1.0, 0.0, 0.7);
+ const MBBSPTree::Plane CD_split(0.0,-1.0, 0.0, 0.3);
+
+ const double min[3] = { 0, 0, 0 };
+ const double max[3] = { 1, 1, 1 };
+ rval = tool.create_tree( min, max, root );
+ CHECK_ERR(rval);
+ rval = tool.get_tree_iterator( root, iter );
+ CHECK_ERR(rval);
+ rval = tool.split_leaf( iter, X_split );
+ CHECK_ERR(rval);
+ rval = tool.split_leaf( iter, AB_split );
+ CHECK_ERR(rval);
+ rval = iter.step();
+ CHECK_ERR(rval);
+ rval = iter.step();
+ CHECK_ERR(rval);
+ rval = tool.split_leaf( iter, CD_split );
+ CHECK_ERR(rval);
+
+ // create two iterators for testing
+ MBBSPTreeIter iter1, iter2;
+ rval = tool.get_tree_iterator( root, iter1 );
+ CHECK_ERR(rval);
+ rval = tool.get_tree_iterator( root, iter2 );
+ CHECK_ERR(rval);
+
+
+ // iter1 == A, iter2 == A
+ CHECK( !iter1.is_sibling( iter1 ) );
+ CHECK( !iter1.is_sibling( iter1.handle() ) );
+ CHECK( !iter1.is_sibling( iter2 ) );
+ CHECK( iter1.sibling_is_forward() );
+
+ // iter1 == A, iter2 == B
+ rval = iter2.step();
+ CHECK_ERR(rval);
+ CHECK( iter1.is_sibling( iter2 ) );
+ CHECK( iter1.is_sibling( iter2.handle() ) );
+ CHECK( iter2.is_sibling( iter1 ) );
+ CHECK( iter2.is_sibling( iter1.handle() ) );
+ CHECK( !iter2.sibling_is_forward() );
+
+ // iter1 == A, iter2 == C
+ rval = iter2.step();
+ CHECK_ERR(rval);
+ CHECK( !iter1.is_sibling( iter2 ) );
+ CHECK( !iter1.is_sibling( iter2.handle() ) );
+ CHECK( !iter2.is_sibling( iter1 ) );
+ CHECK( !iter2.is_sibling( iter1.handle() ) );
+ CHECK( iter2.sibling_is_forward() );
+
+ // iter1 == B, iter2 == C
+ rval = iter1.step();
+ CHECK_ERR(rval);
+ CHECK( !iter1.is_sibling( iter2 ) );
+ CHECK( !iter1.is_sibling( iter2.handle() ) );
+ CHECK( !iter2.is_sibling( iter1 ) );
+ CHECK( !iter2.is_sibling( iter1.handle() ) );
+ CHECK( !iter1.sibling_is_forward() );
+
+ // iter1 == D, iter2 == C
+ rval = iter1.step();
+ CHECK_ERR(rval);
+ CHECK_EQUAL( iter1.handle(), iter2.handle() );
+ rval = iter1.step();
+ CHECK_ERR(rval);
+ CHECK( iter1.is_sibling( iter2 ) );
+ CHECK( iter1.is_sibling( iter2.handle() ) );
+ CHECK( iter2.is_sibling( iter1 ) );
+ CHECK( iter2.is_sibling( iter1.handle() ) );
+ CHECK( !iter1.sibling_is_forward() );
+}
+
+void test_leaf_volume()
+{
+ MBCore moab;
+ MBBSPTree tool( &moab );
+ MBErrorCode rval;
+ MBEntityHandle root;
+ MBBSPTreeBoxIter iter;
+
+
+/* Build Tree
+
+ 1.0 +---------+--------------+
+ | A | |
+ | | |
+ 0.7 +---------+ C |
+ | | |
+ | | |
+ | B | |
+ | +--------------+ 0.3
+ | | D |
+ | | |
+ 0.0 +---------+--------------+
+ 0.0 0.4 1.0 */
+
+ const MBBSPTree::Plane X_split(1.0, 0.0, 0.0,-0.4);
+ const MBBSPTree::Plane AB_split(0.0,-1.0, 0.0, 0.7);
+ const MBBSPTree::Plane CD_split(0.0,-1.0, 0.0, 0.3);
+
+ const double min[3] = { 0, 0, 0 };
+ const double max[3] = { 1, 1, 1 };
+ rval = tool.create_tree( min, max, root );
+ CHECK_ERR(rval);
+ rval = tool.get_tree_iterator( root, iter );
+ CHECK_ERR(rval);
+ rval = tool.split_leaf( iter, X_split );
+ CHECK_ERR(rval);
+ rval = tool.split_leaf( iter, AB_split );
+ CHECK_ERR(rval);
+ rval = iter.step();
+ CHECK_ERR(rval);
+ rval = iter.step();
+ CHECK_ERR(rval);
+ rval = tool.split_leaf( iter, CD_split );
+ CHECK_ERR(rval);
+
+ // reset iterator
+ rval = tool.get_tree_iterator( root, iter );
+ CHECK_ERR(rval);
+
+ // check leaf volumes
+ CHECK_REAL_EQUAL( 0.12, iter.volume(), 1e-12 ); // A
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 0.28, iter.volume(), 1e-12 ); // B
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 0.42, iter.volume(), 1e-12 ); // C
+ CHECK_ERR(iter.step());
+ CHECK_REAL_EQUAL( 0.18, iter.volume(), 1e-12 ); // D
+}
+
+void test_leaf_splits_intersects()
+{
+ MBCore moab;
+ MBBSPTree tool( &moab );
+ MBErrorCode rval;
+ MBEntityHandle root;
+ MBBSPTreeBoxIter iter;
+ MBBSPTree::Plane p;
+
+ const double min[3] = { 0, 0, 0 };
+ const double max[3] = { 1, 2, 3 };
+ rval = tool.create_tree( min, max, root );
+ CHECK_ERR(rval);
+ rval = tool.get_tree_iterator( root, iter );
+ CHECK_ERR(rval);
+
+ p.set( 1, 0, 0, 1 ); // x == -1
+ CHECK_EQUAL( MBBSPTreeBoxIter::MISS, iter.splits( p ) );
+ CHECK( !iter.intersects( p ) );
+ p.flip();
+ CHECK_EQUAL( MBBSPTreeBoxIter::MISS, iter.splits( p ) );
+ CHECK( !iter.intersects( p ) );
+
+ p.set( 1, 0, 0, 0 ); // x == 0
+ CHECK_EQUAL( MBBSPTreeBoxIter::NONHEX, iter.splits( p ) );
+ p.flip();
+ CHECK_EQUAL( MBBSPTreeBoxIter::NONHEX, iter.splits( p ) );
+
+ p.set( 1, 0, 0, -0.5 ); // x == 0.5
+ CHECK_EQUAL( MBBSPTreeBoxIter::SPLIT, iter.splits( p ) );
+ CHECK( iter.intersects( p ) );
+ p.flip();
+ CHECK_EQUAL( MBBSPTreeBoxIter::SPLIT, iter.splits( p ) );
+ CHECK( iter.intersects( p ) );
+
+ p.set( 1, 0, 0, -1 ); // x == 1
+ CHECK_EQUAL( MBBSPTreeBoxIter::NONHEX, iter.splits( p ) );
+ p.flip();
+ CHECK_EQUAL( MBBSPTreeBoxIter::NONHEX, iter.splits( p ) );
+
+ p.set( 1, 0, 0, -2 ); // x == 2
+ CHECK_EQUAL( MBBSPTreeBoxIter::MISS, iter.splits( p ) );
+ CHECK( !iter.intersects( p ) );
+ p.flip();
+ CHECK_EQUAL( MBBSPTreeBoxIter::MISS, iter.splits( p ) );
+ CHECK( !iter.intersects( p ) );
+
+ double pt1[3] = { 0, 0, 1.5 };
+ double pt2[3] = { 1, 0, 1.5 };
+ double pt3[3] = { 0, 1, 3.0 };
+ p.set( pt1, pt2, pt3 );
+ CHECK_EQUAL( MBBSPTreeBoxIter::NONHEX, iter.splits( p ) );
+ CHECK( iter.intersects( p ) );
+ p.flip();
+ CHECK_EQUAL( MBBSPTreeBoxIter::NONHEX, iter.splits( p ) );
+ CHECK( iter.intersects( p ) );
+
+ double pt4[3] = { 0, 2, 2.8 };
+ p.set( pt1, pt2, pt4 );
+ CHECK_EQUAL( MBBSPTreeBoxIter::SPLIT, iter.splits( p ) );
+ CHECK( iter.intersects( p ) );
+ p.flip();
+ CHECK_EQUAL( MBBSPTreeBoxIter::SPLIT, iter.splits( p ) );
+ CHECK( iter.intersects( p ) );
+
+ double pta[3] = { 0.8, 0, 0 };
+ double ptb[3] = { 0, 0.2, 3 };
+ double ptc[3] = { 0.8, 2, 3 };
+ p.set( pta, ptb, ptc );
+ CHECK_EQUAL( MBBSPTreeBoxIter::NONHEX, iter.splits( p ) );
+ CHECK( iter.intersects( p ) );
+ p.flip();
+ CHECK_EQUAL( MBBSPTreeBoxIter::NONHEX, iter.splits( p ) );
+ CHECK( iter.intersects( p ) );
+}
+
More information about the moab-dev
mailing list