MOAB: Mesh Oriented datABase  (version 5.4.0)
bsp_tree_test.cpp
Go to the documentation of this file.
00001 #include "moab/Core.hpp"
00002 #include "TestUtil.hpp"
00003 #include "moab/BSPTree.hpp"
00004 #include "moab/CartVect.hpp"
00005 #include "moab/BSPTreePoly.hpp"
00006 #include "moab/Range.hpp"
00007 #include <algorithm>
00008 
00009 using namespace moab;
00010 
00011 void test_set_plane();
00012 void test_iterator();
00013 void test_box_iterator();
00014 void test_tree_create();
00015 void test_box_tree_create();
00016 void test_leaf_containing_point_bounded_tree();
00017 void test_leaf_containing_point_unbounded_tree();
00018 void test_merge_leaf();
00019 void test_box_iter_neighbors();
00020 void test_leaf_sibling();
00021 void test_leaf_volume( bool box );
00022 void test_leaf_volume_box()
00023 {
00024     test_leaf_volume( true );
00025 }
00026 void test_leaf_volume_gen()
00027 {
00028     test_leaf_volume( false );
00029 }
00030 void test_leaf_splits_intersects();
00031 void test_leaf_intersects_ray_common( bool box );
00032 void test_box_leaf_intersects_ray()
00033 {
00034     test_leaf_intersects_ray_common( true );
00035 }
00036 void test_gen_leaf_intersects_ray()
00037 {
00038     test_leaf_intersects_ray_common( false );
00039 }
00040 void test_leaf_polyhedron();
00041 
00042 int main()
00043 {
00044     int failures = 0;
00045 
00046     failures += RUN_TEST( test_set_plane );
00047     failures += RUN_TEST( test_iterator );
00048     failures += RUN_TEST( test_box_iterator );
00049     failures += RUN_TEST( test_tree_create );
00050     failures += RUN_TEST( test_box_tree_create );
00051     failures += RUN_TEST( test_leaf_containing_point_bounded_tree );
00052     failures += RUN_TEST( test_leaf_containing_point_unbounded_tree );
00053     failures += RUN_TEST( test_merge_leaf );
00054     failures += RUN_TEST( test_box_iter_neighbors );
00055     failures += RUN_TEST( test_leaf_sibling );
00056     failures += RUN_TEST( test_leaf_volume_box );
00057     failures += RUN_TEST( test_leaf_volume_gen );
00058     failures += RUN_TEST( test_leaf_splits_intersects );
00059     failures += RUN_TEST( test_box_leaf_intersects_ray );
00060     failures += RUN_TEST( test_gen_leaf_intersects_ray );
00061     failures += RUN_TEST( test_leaf_polyhedron );
00062 
00063     return failures;
00064 }
00065 
00066 // Make CHECK_EQUAL macro work for planes
00067 void check_equal( const BSPTree::Plane& p1,
00068                   const BSPTree::Plane& p2,
00069                   const char* exp1,
00070                   const char* exp2,
00071                   int line,
00072                   const char* file )
00073 {
00074     if( fabs( p1.norm[0] - p2.norm[0] ) > 1e-6 || fabs( p1.norm[1] - p2.norm[1] ) > 1e-6 ||
00075         fabs( p1.norm[2] - p2.norm[2] ) > 1e-6 || fabs( p1.coeff - p2.coeff ) > 1e-6 )
00076     {
00077         printf( "Equality Test Failed: %s == %s\n", exp1, exp2 );
00078         printf( "  at line %d of '%s'\n", line, file );
00079         printf( "  Expected: %f x + %f y + %f z + %f = 0\n", p1.norm[0], p1.norm[1], p1.norm[2], p1.coeff );
00080         printf( "  Actual  : %f x + %f y + %f z + %f = 0\n", p2.norm[0], p2.norm[1], p2.norm[2], p2.coeff );
00081         printf( "\n" );
00082         FLAG_ERROR;
00083     }
00084 }
00085 
00086 void test_set_plane()
00087 {
00088     BSPTree::Plane p;
00089     const double points[3][3] = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
00090     p.set( points[0], points[1], points[2] );
00091     CHECK_REAL_EQUAL( 0.0, p.distance( points[0] ), 1e-10 );
00092     CHECK_REAL_EQUAL( 0.0, p.distance( points[1] ), 1e-10 );
00093     CHECK_REAL_EQUAL( 0.0, p.distance( points[2] ), 1e-10 );
00094 }
00095 
00096 void test_iterator()
00097 {
00098     Core moab;
00099     BSPTree tool( &moab );
00100     ErrorCode rval;
00101     EntityHandle root;
00102     BSPTreeIter iter;
00103 
00104     // create a depth-1 tree
00105     rval = tool.create_tree( root );CHECK_ERR( rval );
00106     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00107 
00108     // check initial state of iterator
00109     CHECK_EQUAL( &tool, iter.tool() );
00110     CHECK_EQUAL( root, iter.handle() );
00111     CHECK_EQUAL( 1u, iter.depth() );
00112 
00113     // should fail if at root
00114     BSPTree::Plane p;
00115     rval = iter.get_parent_split_plane( p );
00116     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00117 
00118     // check that step past end returns correct value
00119     rval = iter.step();
00120     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00121 
00122     // reset iterator
00123     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00124 
00125     // check that step past start returns correct value
00126     rval = iter.back();
00127     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00128 
00129     // reset iterator
00130     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00131 
00132     // insert a single split plane
00133     rval = tool.split_leaf( iter, BSPTree::Plane( 2, 0, 0, 0 ) );CHECK_ERR( rval );
00134 
00135     // check initial location
00136     CHECK_EQUAL( 2u, iter.depth() );
00137     CHECK( iter.handle() != root );
00138 
00139     // create new iterators at left and right ends
00140     BSPTreeIter left, right;
00141     rval = tool.get_tree_iterator( root, left );CHECK_ERR( rval );
00142     rval = tool.get_tree_end_iterator( root, right );CHECK_ERR( rval );
00143 
00144     // compare post-split iterator to left
00145     CHECK_EQUAL( left.depth(), iter.depth() );
00146     CHECK_EQUAL( left.handle(), iter.handle() );
00147 
00148     // step to other leaf
00149     rval = iter.step();CHECK_ERR( rval );
00150 
00151     // check location
00152     CHECK_EQUAL( 2u, iter.depth() );
00153     CHECK( iter.handle() != root );
00154 
00155     // compare stepped iterator to right
00156     CHECK_EQUAL( right.depth(), iter.depth() );
00157     CHECK_EQUAL( right.handle(), iter.handle() );
00158 
00159     // step to back to first leaf
00160     rval = iter.back();CHECK_ERR( rval );
00161 
00162     // compare to left
00163     CHECK_EQUAL( left.depth(), iter.depth() );
00164     CHECK_EQUAL( left.handle(), iter.handle() );
00165 
00166     // check plane
00167     // should have unit normal
00168     left.get_parent_split_plane( p );
00169     CHECK_EQUAL( BSPTree::Plane( 1, 0, 0, 0 ), p );
00170     p.norm[0] = 11;
00171     right.get_parent_split_plane( p );
00172     CHECK_EQUAL( BSPTree::Plane( 1, 0, 0, 0 ), p );
00173 
00174     // check step past ends
00175     rval = left.back();
00176     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00177     rval = right.step();
00178     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00179 }
00180 
00181 bool compare_hexes( const double expected[8][3], const double actual[8][3], double epsilon )
00182 {
00183     // for each of three possible rotations
00184     const int rotation_maps[3][8] = {
00185         { 0, 1, 2, 3, 4, 5, 6, 7 }, { 3, 2, 6, 7, 0, 1, 5, 4 }, { 7, 3, 2, 6, 4, 0, 1, 5 } };
00186     for( int i = 0; i < 3; ++i )
00187     {
00188         // compare for rotationts about axis from face 4 to 5
00189         for( int j = 0; j < 4; ++j )
00190         {
00191             bool match = true;
00192             // for each face vertex
00193             for( int k = 0; k < 4 && match; ++k )
00194             {
00195                 // for each coordinate
00196                 for( int d = 0; d < 3; ++d )
00197                 {
00198                     if( fabs( expected[( j + k ) % 4][d] - actual[rotation_maps[i][k]][d] ) > epsilon ||
00199                         fabs( expected[( j + k ) % 4 + 4][d] - actual[rotation_maps[i][k + 4]][d] ) > epsilon )
00200                     {
00201                         match = false;
00202                         break;
00203                     }
00204                 }
00205             }
00206 
00207             if( match ) return true;
00208         }
00209     }
00210 
00211     printf( "Hex vertex copmarison failed.\n" );
00212     printf( "           Exected                         Actual\n" );
00213     for( int v = 0; v < 8; ++v )
00214     {
00215         printf( "% 9f % 9f % 9f   % 9f % 9f % 9f\n", expected[v][0], expected[v][1], expected[v][2], actual[v][0],
00216                 actual[v][1], actual[v][2] );
00217     }
00218 
00219     return false;
00220 }
00221 
00222 static void aabox_corners( const double min[3], const double max[3], double corners[8][3] )
00223 {
00224     const double expt[8][3] = { { min[0], min[1], min[2] }, { max[0], min[1], min[2] }, { max[0], max[1], min[2] },
00225                                 { min[0], max[1], min[2] }, { min[0], min[1], max[2] }, { max[0], min[1], max[2] },
00226                                 { max[0], max[1], max[2] }, { min[0], max[1], max[2] } };
00227     memcpy( corners, expt, sizeof( expt ) );
00228 }
00229 
00230 static void aabox_corners( double min_x,
00231                            double min_y,
00232                            double min_z,
00233                            double max_x,
00234                            double max_y,
00235                            double max_z,
00236                            double corners[8][3] )
00237 {
00238     double min[] = { min_x, min_y, min_z };
00239     double max[] = { max_x, max_y, max_z };
00240     aabox_corners( min, max, corners );
00241 }
00242 
00243 void test_box_iterator()
00244 {
00245     Core moab;
00246     BSPTree tool( &moab );
00247     ErrorCode rval;
00248     EntityHandle root;
00249     BSPTreeBoxIter iter;
00250     const double min[3] = { -1, -2, -3 };
00251     const double max[3] = { 3, 2, 1 };
00252 
00253     // create a depth-1 tree
00254     rval = tool.create_tree( min, max, root );CHECK_ERR( rval );
00255     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00256 
00257     // check initial state of iterator
00258     CHECK_EQUAL( &tool, iter.tool() );
00259     CHECK_EQUAL( root, iter.handle() );
00260     CHECK_EQUAL( 1u, iter.depth() );
00261 
00262     // check initial corner values
00263     double corners[8][3], expt[8][3];
00264     aabox_corners( min, max, expt );
00265     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00266     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00267 
00268     // should fail if at root
00269     BSPTree::Plane p;
00270     rval = iter.get_parent_split_plane( p );
00271     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00272 
00273     // check that step past end returns correct value
00274     rval = iter.step();
00275     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00276 
00277     // reset iterator
00278     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00279 
00280     // check that step past start returns correct value
00281     rval = iter.back();
00282     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00283 
00284     // reset iterator
00285     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00286 
00287     // insert a single split plane
00288     rval = tool.split_leaf( iter, BSPTree::Plane( 2, 0, 0, 0 ) );CHECK_ERR( rval );
00289 
00290     // check initial location
00291     CHECK_EQUAL( 2u, iter.depth() );
00292     CHECK( iter.handle() != root );
00293 
00294     // create new iterators at left and right ends
00295     BSPTreeIter left, right;
00296     rval = tool.get_tree_iterator( root, left );CHECK_ERR( rval );
00297     rval = tool.get_tree_end_iterator( root, right );CHECK_ERR( rval );
00298 
00299     // compare post-split iterator to left
00300     CHECK_EQUAL( left.depth(), iter.depth() );
00301     CHECK_EQUAL( left.handle(), iter.handle() );
00302 
00303     // check box
00304     aabox_corners( min, max, expt );
00305     for( int i = 0; i < 8; ++i )
00306         if( expt[i][0] > 0 ) expt[i][0] = 0;
00307     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00308     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00309 
00310     // step to other leaf
00311     rval = iter.step();CHECK_ERR( rval );
00312 
00313     // check location
00314     CHECK_EQUAL( 2u, iter.depth() );
00315     CHECK( iter.handle() != root );
00316 
00317     // compare stepped iterator to right
00318     CHECK_EQUAL( right.depth(), iter.depth() );
00319     CHECK_EQUAL( right.handle(), iter.handle() );
00320 
00321     // check box
00322     aabox_corners( min, max, expt );
00323     for( int i = 0; i < 8; ++i )
00324         if( expt[i][0] < 0 ) expt[i][0] = 0;
00325     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00326     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00327 
00328     // step to back to first leaf
00329     rval = iter.back();CHECK_ERR( rval );
00330 
00331     // compare to left
00332     CHECK_EQUAL( left.depth(), iter.depth() );
00333     CHECK_EQUAL( left.handle(), iter.handle() );
00334 
00335     // check box
00336     aabox_corners( min, max, expt );
00337     for( int i = 0; i < 8; ++i )
00338         if( expt[i][0] > 0 ) expt[i][0] = 0;
00339     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00340     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00341 
00342     // check plane
00343     // should have unit normal
00344     left.get_parent_split_plane( p );
00345     CHECK_EQUAL( BSPTree::Plane( 1, 0, 0, 0 ), p );
00346     p.norm[0] = 11;
00347     right.get_parent_split_plane( p );
00348     CHECK_EQUAL( BSPTree::Plane( 1, 0, 0, 0 ), p );
00349 
00350     // check step past ends
00351     rval = left.back();
00352     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00353     rval = right.step();
00354     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00355 }
00356 
00357 void test_tree_create()
00358 {
00359     Core moab;
00360     BSPTree tool( &moab );
00361     ErrorCode rval;
00362     EntityHandle root;
00363     BSPTreeIter iter;
00364     BSPTree::Plane p;
00365 
00366     // create a depth-1 tree
00367     rval = tool.create_tree( root );CHECK_ERR( rval );
00368     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00369 
00370     // check initial state of iterator
00371     CHECK_EQUAL( &tool, iter.tool() );
00372     CHECK_EQUAL( root, iter.handle() );
00373     CHECK_EQUAL( 1u, iter.depth() );
00374 
00375     // split with z=0
00376     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 0, 0.5, 0 ) );CHECK_ERR( rval );
00377     CHECK_EQUAL( 2u, iter.depth() );
00378 
00379     // check that parent split plane is correct
00380     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00381     CHECK_EQUAL( BSPTree::Plane( 0, 0, 1, 0 ), p );
00382 
00383     // split lower leaf with diagonal plane
00384     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 1, 0, 0 ) );CHECK_ERR( rval );
00385     CHECK_EQUAL( 3u, iter.depth() );
00386 
00387     const double r = 0.5 * sqrt( 2.0 );
00388 
00389     // check that parent split plane is correct
00390     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00391     CHECK_EQUAL( BSPTree::Plane( r, r, 0, 0 ), p );
00392 
00393     // step to upper leaf
00394     rval = iter.step();CHECK_ERR( rval );
00395 
00396     // split upper leaf with diagonal plane
00397     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 1, 0, 0 ) );CHECK_ERR( rval );
00398     CHECK_EQUAL( 4u, iter.depth() );
00399 
00400     // check that parent split plane is correct
00401     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00402     CHECK_EQUAL( BSPTree::Plane( -r, r, 0, 0 ), p );
00403 
00404     // iterate over four leaves
00405 
00406     // first leaf
00407     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00408     CHECK_EQUAL( 3u, iter.depth() );
00409     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00410     CHECK_EQUAL( BSPTree::Plane( r, r, 0, 0 ), p );
00411 
00412     // second leaf
00413     rval = iter.step();CHECK_ERR( rval );
00414     CHECK_EQUAL( 4u, iter.depth() );
00415     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00416     CHECK_EQUAL( BSPTree::Plane( -r, r, 0, 0 ), p );
00417 
00418     // third leaf
00419     rval = iter.step();CHECK_ERR( rval );
00420     CHECK_EQUAL( 4u, iter.depth() );
00421     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00422     CHECK_EQUAL( BSPTree::Plane( -r, r, 0, 0 ), p );
00423 
00424     // fourth leaf
00425     rval = iter.step();CHECK_ERR( rval );
00426     CHECK_EQUAL( 2u, iter.depth() );
00427     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00428     CHECK_EQUAL( BSPTree::Plane( 0, 0, 1, 0 ), p );
00429 
00430     // no more leaves
00431     rval = iter.step();
00432     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00433 }
00434 
00435 void test_box_tree_create()
00436 {
00437     Core moab;
00438     BSPTree tool( &moab );
00439     ErrorCode rval;
00440     EntityHandle root;
00441     BSPTreeBoxIter iter;
00442     BSPTree::Plane p;
00443     const double min[3] = { -2, -2, -2 };
00444     const double max[3] = { 2, 2, 2 };
00445 
00446     // create a depth-1 tree
00447     rval = tool.create_tree( min, max, root );CHECK_ERR( rval );
00448     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00449 
00450     // check initial state of iterator
00451     CHECK_EQUAL( &tool, iter.tool() );
00452     CHECK_EQUAL( root, iter.handle() );
00453     CHECK_EQUAL( 1u, iter.depth() );
00454 
00455     // check initial corner values
00456     double corners[8][3], expt[8][3];
00457     aabox_corners( min, max, expt );
00458     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00459     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00460 
00461     // Try splits that should fail because they
00462     // do not intersect the leaf at all
00463     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 0, 1, 4 ) );
00464     CHECK_EQUAL( MB_FAILURE, rval );
00465     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 0, 1, -4 ) );
00466     CHECK_EQUAL( MB_FAILURE, rval );
00467     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 1, 0, 4 ) );
00468     CHECK_EQUAL( MB_FAILURE, rval );
00469     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 1, 0, -4 ) );
00470     CHECK_EQUAL( MB_FAILURE, rval );
00471     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 0, 0, 4 ) );
00472     CHECK_EQUAL( MB_FAILURE, rval );
00473     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 0, 0, -4 ) );
00474     CHECK_EQUAL( MB_FAILURE, rval );
00475     rval = tool.split_leaf( iter, BSPTree::Plane( -1, -1, -1, 7 ) );
00476     CHECK_EQUAL( MB_FAILURE, rval );
00477     rval = tool.split_leaf( iter, BSPTree::Plane( -1, -1, -1, -7 ) );
00478     CHECK_EQUAL( MB_FAILURE, rval );
00479     rval = tool.split_leaf( iter, BSPTree::Plane( 1, -1, -1, 7 ) );
00480     CHECK_EQUAL( MB_FAILURE, rval );
00481     rval = tool.split_leaf( iter, BSPTree::Plane( 1, -1, -1, -7 ) );
00482     CHECK_EQUAL( MB_FAILURE, rval );
00483     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 1, -1, 7 ) );
00484     CHECK_EQUAL( MB_FAILURE, rval );
00485     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 1, -1, -7 ) );
00486     CHECK_EQUAL( MB_FAILURE, rval );
00487     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 1, -1, 7 ) );
00488     CHECK_EQUAL( MB_FAILURE, rval );
00489     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 1, -1, -7 ) );
00490     CHECK_EQUAL( MB_FAILURE, rval );
00491 
00492     // Try a split that should fail because the
00493     // resulting leaf would not be a hexahedron.
00494     // Clip each corner twice using planes with opposing normals
00495     rval = tool.split_leaf( iter, BSPTree::Plane( -1, -1, -1, -4 ) );
00496     CHECK_EQUAL( MB_FAILURE, rval );
00497     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 1, 1, 4 ) );
00498     CHECK_EQUAL( MB_FAILURE, rval );
00499     rval = tool.split_leaf( iter, BSPTree::Plane( 1, -1, -1, -4 ) );
00500     CHECK_EQUAL( MB_FAILURE, rval );
00501     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 1, 1, 4 ) );
00502     CHECK_EQUAL( MB_FAILURE, rval );
00503     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 1, -1, -4 ) );
00504     CHECK_EQUAL( MB_FAILURE, rval );
00505     rval = tool.split_leaf( iter, BSPTree::Plane( -1, -1, 1, 4 ) );
00506     CHECK_EQUAL( MB_FAILURE, rval );
00507     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 1, -1, -4 ) );
00508     CHECK_EQUAL( MB_FAILURE, rval );
00509     rval = tool.split_leaf( iter, BSPTree::Plane( 1, -1, 1, 4 ) );
00510     CHECK_EQUAL( MB_FAILURE, rval );
00511     rval = tool.split_leaf( iter, BSPTree::Plane( -1, -1, 1, -4 ) );
00512     CHECK_EQUAL( MB_FAILURE, rval );
00513     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 1, -1, 4 ) );
00514     CHECK_EQUAL( MB_FAILURE, rval );
00515     rval = tool.split_leaf( iter, BSPTree::Plane( 1, -1, 1, -4 ) );
00516     CHECK_EQUAL( MB_FAILURE, rval );
00517     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 1, -1, 4 ) );
00518     CHECK_EQUAL( MB_FAILURE, rval );
00519     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 1, 1, -4 ) );
00520     CHECK_EQUAL( MB_FAILURE, rval );
00521     rval = tool.split_leaf( iter, BSPTree::Plane( -1, -1, -1, 4 ) );
00522     CHECK_EQUAL( MB_FAILURE, rval );
00523     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 1, 1, -4 ) );
00524     CHECK_EQUAL( MB_FAILURE, rval );
00525     rval = tool.split_leaf( iter, BSPTree::Plane( 1, -1, -1, 4 ) );
00526     CHECK_EQUAL( MB_FAILURE, rval );
00527     // Clip each edge
00528     rval = tool.split_leaf( iter, BSPTree::Plane( -1, -1, 0, -2 ) );
00529     CHECK_EQUAL( MB_FAILURE, rval );
00530     rval = tool.split_leaf( iter, BSPTree::Plane( 1, -1, 0, -2 ) );
00531     CHECK_EQUAL( MB_FAILURE, rval );
00532     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 1, 0, -2 ) );
00533     CHECK_EQUAL( MB_FAILURE, rval );
00534     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 1, 0, -2 ) );
00535     CHECK_EQUAL( MB_FAILURE, rval );
00536     rval = tool.split_leaf( iter, BSPTree::Plane( 0, -1, -1, -2 ) );
00537     CHECK_EQUAL( MB_FAILURE, rval );
00538     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 1, -1, -2 ) );
00539     CHECK_EQUAL( MB_FAILURE, rval );
00540     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 1, 1, -2 ) );
00541     CHECK_EQUAL( MB_FAILURE, rval );
00542     rval = tool.split_leaf( iter, BSPTree::Plane( 0, -1, 1, -2 ) );
00543     CHECK_EQUAL( MB_FAILURE, rval );
00544     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 0, -1, -2 ) );
00545     CHECK_EQUAL( MB_FAILURE, rval );
00546     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 0, -1, -2 ) );
00547     CHECK_EQUAL( MB_FAILURE, rval );
00548     rval = tool.split_leaf( iter, BSPTree::Plane( 1, 0, 1, -2 ) );
00549     CHECK_EQUAL( MB_FAILURE, rval );
00550     rval = tool.split_leaf( iter, BSPTree::Plane( -1, 0, 1, -2 ) );
00551     CHECK_EQUAL( MB_FAILURE, rval );
00552 
00553     // verify that iterator is still valid after many failed splits
00554     CHECK_EQUAL( &tool, iter.tool() );
00555     CHECK_EQUAL( root, iter.handle() );
00556     CHECK_EQUAL( 1u, iter.depth() );
00557     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00558     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00559 
00560     // split with z=0
00561     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 0, 0.5, 0 ) );CHECK_ERR( rval );
00562     CHECK_EQUAL( 2u, iter.depth() );
00563 
00564     // check that parent split plane is correct
00565     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00566     CHECK_EQUAL( BSPTree::Plane( 0, 0, 1, 0 ), p );
00567 
00568     // check that box corners are correct
00569     aabox_corners( min, max, expt );
00570     for( unsigned i = 0; i < 8; ++i )
00571         if( expt[i][2] > 0.0 ) expt[i][2] = 0.0;
00572     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00573     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00574 
00575     // split with z=-1 and normal in opposite direction
00576     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 0, -2, -2 ) );CHECK_ERR( rval );
00577     CHECK_EQUAL( 3u, iter.depth() );
00578     for( unsigned i = 0; i < 8; ++i )
00579         if( expt[i][2] < -1.0 ) expt[i][2] = -1.0;
00580     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00581     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00582 
00583     // step to next leaf (z < -1)
00584     rval = iter.step();CHECK_ERR( rval );
00585     CHECK_EQUAL( 3u, iter.depth() );
00586     aabox_corners( min, max, expt );
00587     for( unsigned i = 0; i < 8; ++i )
00588         if( expt[i][2] > -1.0 ) expt[i][2] = -1.0;
00589     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00590     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00591 
00592     // split at x = -1
00593     rval = tool.split_leaf( iter, BSPTree::Plane( -0.1, 0, 0, -0.1 ) );CHECK_ERR( rval );
00594     CHECK_EQUAL( 4u, iter.depth() );
00595 
00596     // check that parent split plane is correct
00597     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00598     CHECK_EQUAL( BSPTree::Plane( -1, 0, 0, -1 ), p );
00599 
00600     // check that leaf box is correct
00601     aabox_corners( -1, -2, -2, 2, 2, -1, expt );
00602     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00603     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00604 
00605     // split at x = 1
00606     rval = tool.split_leaf( iter, BSPTree::Plane( 5, 0, 0, -5 ) );CHECK_ERR( rval );
00607     CHECK_EQUAL( 5u, iter.depth() );
00608 
00609     // check that parent split plane is correct
00610     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00611     CHECK_EQUAL( BSPTree::Plane( 1, 0, 0, -1 ), p );
00612 
00613     // check that leaf box is correct
00614     aabox_corners( -1, -2, -2, 1, 2, -1, expt );
00615     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00616     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00617 
00618     // split at y = -1
00619     rval = tool.split_leaf( iter, BSPTree::Plane( 0, -1, 0, -1 ) );CHECK_ERR( rval );
00620     CHECK_EQUAL( 6u, iter.depth() );
00621 
00622     // check that parent split plane is correct
00623     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00624     CHECK_EQUAL( BSPTree::Plane( 0, -1, 0, -1 ), p );
00625 
00626     // check that leaf box is correct
00627     aabox_corners( -1, -1, -2, 1, 2, -1, expt );
00628     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00629     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00630 
00631     // split at y = 1
00632     rval = tool.split_leaf( iter, BSPTree::Plane( 0, 1, 0, -1 ) );CHECK_ERR( rval );
00633     CHECK_EQUAL( 7u, iter.depth() );
00634 
00635     // check that parent split plane is correct
00636     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00637     CHECK_EQUAL( BSPTree::Plane( 0, 1, 0, -1 ), p );
00638 
00639     // check that leaf box is correct
00640     aabox_corners( -1, -1, -2, 1, 1, -1, expt );
00641     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00642     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00643 
00644     // iterate over tree, verifying
00645     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00646     CHECK_EQUAL( 3u, iter.depth() );
00647     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00648     CHECK_EQUAL( BSPTree::Plane( 0, 0, -1, -1 ), p );
00649     aabox_corners( -2, -2, -1, 2, 2, 0, expt );
00650     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00651     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00652 
00653     rval = iter.step();CHECK_ERR( rval );
00654     CHECK_EQUAL( 7u, iter.depth() );
00655     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00656     CHECK_EQUAL( BSPTree::Plane( 0, 1, 0, -1 ), p );
00657     aabox_corners( -1, -1, -2, 1, 1, -1, expt );
00658     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00659     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00660 
00661     rval = iter.step();CHECK_ERR( rval );
00662     CHECK_EQUAL( 7u, iter.depth() );
00663     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00664     CHECK_EQUAL( BSPTree::Plane( 0, 1, 0, -1 ), p );
00665     aabox_corners( -1, 1, -2, 1, 2, -1, expt );
00666     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00667     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00668 
00669     rval = iter.step();CHECK_ERR( rval );
00670     CHECK_EQUAL( 6u, iter.depth() );
00671     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00672     CHECK_EQUAL( BSPTree::Plane( 0, -1, 0, -1 ), p );
00673     aabox_corners( -1, -2, -2, 1, -1, -1, expt );
00674     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00675     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00676 
00677     rval = iter.step();CHECK_ERR( rval );
00678     CHECK_EQUAL( 5u, iter.depth() );
00679     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00680     CHECK_EQUAL( BSPTree::Plane( 1, 0, 0, -1 ), p );
00681     aabox_corners( 1, -2, -2, 2, 2, -1, expt );
00682     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00683     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00684 
00685     rval = iter.step();CHECK_ERR( rval );
00686     CHECK_EQUAL( 4u, iter.depth() );
00687     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00688     CHECK_EQUAL( BSPTree::Plane( -1, 0, 0, -1 ), p );
00689     aabox_corners( -2, -2, -2, -1, 2, -1, expt );
00690     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00691     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00692 
00693     rval = iter.step();CHECK_ERR( rval );
00694     CHECK_EQUAL( 2u, iter.depth() );
00695     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00696     CHECK_EQUAL( BSPTree::Plane( 0, 0, 1, 0 ), p );
00697     aabox_corners( -2, -2, 0, 2, 2, 2, expt );
00698     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00699     CHECK( compare_hexes( expt, corners, 1e-6 ) );
00700 
00701     // no more leaves
00702     rval = iter.step();
00703     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00704 }
00705 
00706 void test_leaf_containing_point_bounded_tree()
00707 {
00708     Core moab;
00709     BSPTree tool( &moab );
00710     ErrorCode rval;
00711     EntityHandle root;
00712     BSPTreeIter iter;
00713     BSPTreeBoxIter b_iter;
00714     BSPTree::Plane p;
00715     EntityHandle h;
00716     double expected[8][3], corners[8][3];
00717 
00718     /*  Build Tree
00719 
00720       1.0 +---------+--------------+
00721           |    A    |              |
00722           |         |              |
00723       0.7 +---------+      C       |
00724           |         |              |
00725           |         |              |
00726           |    B    |              |
00727           |         +--------------+ 0.3
00728           |         |      D       |
00729           |         |              |
00730       0.0 +---------+--------------+
00731           0.0       0.4            1.0  */
00732 
00733     const BSPTree::Plane X_split( 1.0, 0.0, 0.0, -0.4 );
00734     const BSPTree::Plane AB_split( 0.0, -1.0, 0.0, 0.7 );
00735     const BSPTree::Plane CD_split( 0.0, -1.0, 0.0, 0.3 );
00736 
00737     const double min[3] = { 0, 0, 0 };
00738     const double max[3] = { 1, 1, 1 };
00739     rval                = tool.create_tree( min, max, root );CHECK_ERR( rval );
00740     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00741 
00742     rval = tool.split_leaf( iter, X_split );CHECK_ERR( rval );
00743 
00744     rval = tool.split_leaf( iter, AB_split );CHECK_ERR( rval );
00745     const EntityHandle A = iter.handle();
00746 
00747     rval = iter.step();CHECK_ERR( rval );
00748     const EntityHandle B = iter.handle();
00749 
00750     rval = iter.step();CHECK_ERR( rval );
00751     rval = tool.split_leaf( iter, CD_split );CHECK_ERR( rval );
00752     const EntityHandle C = iter.handle();
00753 
00754     rval = iter.step();CHECK_ERR( rval );
00755     const EntityHandle D = iter.handle();
00756 
00757     // Test queries inside tree
00758 
00759     const double A_point[] = { 0.1, 0.8, 0.5 };
00760     rval                   = tool.leaf_containing_point( root, A_point, h );CHECK_ERR( rval );
00761     CHECK_EQUAL( A, h );
00762     rval = tool.leaf_containing_point( root, A_point, iter );CHECK_ERR( rval );
00763     CHECK_EQUAL( A, iter.handle() );
00764     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00765     CHECK_EQUAL( AB_split, p );
00766     rval = tool.leaf_containing_point( root, A_point, b_iter );CHECK_ERR( rval );
00767     CHECK_EQUAL( A, b_iter.handle() );
00768     aabox_corners( 0.0, 0.7, 0.0, 0.4, 1.0, 1.0, expected );
00769     rval = b_iter.get_box_corners( corners );CHECK_ERR( rval );
00770     CHECK( compare_hexes( expected, corners, 1e-6 ) );
00771 
00772     const double B_point[] = { 0.3, 0.1, 0.6 };
00773     rval                   = tool.leaf_containing_point( root, B_point, h );CHECK_ERR( rval );
00774     CHECK_EQUAL( B, h );
00775     rval = tool.leaf_containing_point( root, B_point, iter );CHECK_ERR( rval );
00776     CHECK_EQUAL( B, iter.handle() );
00777     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00778     CHECK_EQUAL( AB_split, p );
00779     rval = tool.leaf_containing_point( root, B_point, b_iter );CHECK_ERR( rval );
00780     CHECK_EQUAL( B, b_iter.handle() );
00781     aabox_corners( 0.0, 0.0, 0.0, 0.4, 0.7, 1.0, expected );
00782     rval = b_iter.get_box_corners( corners );CHECK_ERR( rval );
00783     CHECK( compare_hexes( expected, corners, 1e-6 ) );
00784 
00785     const double C_point[] = { 0.9, 0.9, 0.1 };
00786     rval                   = tool.leaf_containing_point( root, C_point, h );CHECK_ERR( rval );
00787     CHECK_EQUAL( C, h );
00788     rval = tool.leaf_containing_point( root, C_point, iter );CHECK_ERR( rval );
00789     CHECK_EQUAL( C, iter.handle() );
00790     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00791     CHECK_EQUAL( CD_split, p );
00792     rval = tool.leaf_containing_point( root, C_point, b_iter );CHECK_ERR( rval );
00793     CHECK_EQUAL( C, b_iter.handle() );
00794     aabox_corners( 0.4, 0.3, 0.0, 1.0, 1.0, 1.0, expected );
00795     rval = b_iter.get_box_corners( corners );CHECK_ERR( rval );
00796     CHECK( compare_hexes( expected, corners, 1e-6 ) );
00797 
00798     const double D_point[] = { 0.5, 0.2, 0.9 };
00799     rval                   = tool.leaf_containing_point( root, D_point, h );CHECK_ERR( rval );
00800     CHECK_EQUAL( D, h );
00801     rval = tool.leaf_containing_point( root, D_point, iter );CHECK_ERR( rval );
00802     CHECK_EQUAL( D, iter.handle() );
00803     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00804     CHECK_EQUAL( CD_split, p );
00805     rval = tool.leaf_containing_point( root, D_point, b_iter );CHECK_ERR( rval );
00806     CHECK_EQUAL( D, b_iter.handle() );
00807     aabox_corners( 0.4, 0.0, 0.0, 1.0, 0.3, 1.0, expected );
00808     rval = b_iter.get_box_corners( corners );CHECK_ERR( rval );
00809     CHECK( compare_hexes( expected, corners, 1e-6 ) );
00810 
00811     // Try a couple points outside of the tree
00812 
00813     const double above_pt[] = { 0.5, 0.5, 2.0 };
00814     rval                    = tool.leaf_containing_point( root, above_pt, b_iter );
00815     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00816 
00817     const double left_pt[] = { -1.0, 0.5, 0.5 };
00818     rval                   = tool.leaf_containing_point( root, left_pt, b_iter );
00819     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00820 }
00821 
00822 void test_leaf_containing_point_unbounded_tree()
00823 {
00824     Core moab;
00825     BSPTree tool( &moab );
00826     ErrorCode rval;
00827     EntityHandle root;
00828     BSPTreeIter iter;
00829     BSPTree::Plane p;
00830     EntityHandle h;
00831 
00832     /*  Build Tree
00833 
00834         \      |
00835          \  C  o (0,4,0)
00836           \    |
00837            \   |
00838             \  |
00839          B   \ |         D
00840               \|
00841        ________o (0,0,0)
00842                 \
00843                  \
00844            A      \
00845                    o (1,-2,0)
00846                     \
00847      */
00848     const BSPTree::Plane X_split( 2.0, 1.0, 0.0, 0.0 );
00849     const BSPTree::Plane AB_split( 0.0, 1.0, 0.0, 0.0 );
00850     const BSPTree::Plane CD_split( 1.0, 0.0, 0.0, 0.0 );
00851 
00852     rval = tool.create_tree( root );CHECK_ERR( rval );
00853     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00854 
00855     rval = tool.split_leaf( iter, X_split );CHECK_ERR( rval );
00856 
00857     rval = tool.split_leaf( iter, AB_split );CHECK_ERR( rval );
00858     const EntityHandle A = iter.handle();
00859 
00860     rval = iter.step();CHECK_ERR( rval );
00861     const EntityHandle B = iter.handle();
00862 
00863     rval = iter.step();CHECK_ERR( rval );
00864     rval = tool.split_leaf( iter, CD_split );CHECK_ERR( rval );
00865     const EntityHandle C = iter.handle();
00866 
00867     rval = iter.step();CHECK_ERR( rval );
00868     const EntityHandle D = iter.handle();
00869 
00870     // Test queries inside tree
00871 
00872     const double A_point[] = { -1000, -1000, -1000 };
00873     rval                   = tool.leaf_containing_point( root, A_point, h );CHECK_ERR( rval );
00874     CHECK_EQUAL( A, h );
00875     rval = tool.leaf_containing_point( root, A_point, iter );CHECK_ERR( rval );
00876     CHECK_EQUAL( A, iter.handle() );
00877     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00878     CHECK_EQUAL( AB_split, p );
00879 
00880     const double B_point[] = { -3, 1, 100 };
00881     rval                   = tool.leaf_containing_point( root, B_point, h );CHECK_ERR( rval );
00882     CHECK_EQUAL( B, h );
00883     rval = tool.leaf_containing_point( root, B_point, iter );CHECK_ERR( rval );
00884     CHECK_EQUAL( B, iter.handle() );
00885     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00886     CHECK_EQUAL( AB_split, p );
00887 
00888     const double C_point[] = { -10, 500, 0 };
00889     rval                   = tool.leaf_containing_point( root, C_point, h );CHECK_ERR( rval );
00890     CHECK_EQUAL( C, h );
00891     rval = tool.leaf_containing_point( root, C_point, iter );CHECK_ERR( rval );
00892     CHECK_EQUAL( C, iter.handle() );
00893     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00894     CHECK_EQUAL( CD_split, p );
00895 
00896     const double D_point[] = { 10, 500, 0 };
00897     rval                   = tool.leaf_containing_point( root, D_point, h );CHECK_ERR( rval );
00898     CHECK_EQUAL( D, h );
00899     rval = tool.leaf_containing_point( root, D_point, iter );CHECK_ERR( rval );
00900     CHECK_EQUAL( D, iter.handle() );
00901     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00902     CHECK_EQUAL( CD_split, p );
00903 }
00904 
00905 void test_merge_leaf()
00906 {
00907     Core moab;
00908     BSPTree tool( &moab );
00909     ErrorCode rval;
00910     EntityHandle root;
00911     BSPTreeBoxIter iter;
00912     BSPTree::Plane p;
00913     double expected[8][3], corners[8][3];
00914 
00915     /*  Build Tree
00916 
00917       1.0 +---------+--------------+
00918           |    A    |              |
00919           |         |              |
00920       0.7 +---------+      C       |
00921           |         |              |
00922           |         |              |
00923           |    B    |              |
00924           |         +--------------+ 0.3
00925           |         |      D       |
00926           |         |              |
00927       0.0 +---------+--------------+
00928           0.0       0.4            1.0  */
00929 
00930     const BSPTree::Plane X_split( 1.0, 0.0, 0.0, -0.4 );
00931     const BSPTree::Plane AB_split( 0.0, -1.0, 0.0, 0.7 );
00932     const BSPTree::Plane CD_split( 0.0, -1.0, 0.0, 0.3 );
00933 
00934     const double min[3] = { 0, 0, 0 };
00935     const double max[3] = { 1, 1, 1 };
00936     rval                = tool.create_tree( min, max, root );CHECK_ERR( rval );
00937     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00938     rval = tool.split_leaf( iter, X_split );CHECK_ERR( rval );
00939     const EntityHandle AB = iter.handle();
00940     rval                  = tool.split_leaf( iter, AB_split );CHECK_ERR( rval );
00941     rval = iter.step();CHECK_ERR( rval );
00942     rval = iter.step();CHECK_ERR( rval );
00943     const EntityHandle CD = iter.handle();
00944     rval                  = tool.split_leaf( iter, CD_split );CHECK_ERR( rval );
00945     rval = iter.step();CHECK_ERR( rval );
00946 
00947     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
00948     rval = tool.merge_leaf( iter );CHECK_ERR( rval );
00949     CHECK_EQUAL( AB, iter.handle() );
00950     CHECK_EQUAL( 2u, iter.depth() );
00951     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00952     CHECK_EQUAL( X_split, p );
00953     aabox_corners( 0.0, 0.0, 0.0, 0.4, 1.0, 1.0, expected );
00954     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00955     CHECK( compare_hexes( expected, corners, 1e-6 ) );
00956 
00957     rval = iter.step();CHECK_ERR( rval );
00958     rval = iter.step();CHECK_ERR( rval );
00959     rval = tool.merge_leaf( iter );CHECK_ERR( rval );
00960     CHECK_EQUAL( CD, iter.handle() );
00961     CHECK_EQUAL( 2u, iter.depth() );
00962     rval = iter.get_parent_split_plane( p );CHECK_ERR( rval );
00963     CHECK_EQUAL( X_split, p );
00964     aabox_corners( 0.4, 0.0, 0.0, 1.0, 1.0, 1.0, expected );
00965     rval = iter.get_box_corners( corners );CHECK_ERR( rval );
00966     CHECK( compare_hexes( expected, corners, 1e-6 ) );
00967 
00968     rval = iter.step();
00969     CHECK_EQUAL( MB_ENTITY_NOT_FOUND, rval );
00970 }
00971 
00972 static std::vector< int > neighbors( const BSPTreeBoxIter& iter,
00973                                      const EntityHandle leaves[8],
00974                                      BSPTreeBoxIter::SideBits side,
00975                                      double epsilon )
00976 {
00977     std::vector< BSPTreeBoxIter > list;
00978     ErrorCode rval = iter.get_neighbors( side, list, epsilon );CHECK_ERR( rval );
00979 
00980     std::vector< int > results;
00981     for( size_t i = 0; i < list.size(); ++i )
00982         results.push_back( std::find( leaves, leaves + 8, list[i].handle() ) - leaves );
00983     std::sort( results.begin(), results.end() );
00984     return results;
00985 }
00986 
00987 void test_box_iter_neighbors()
00988 {
00989     Core moab;
00990     BSPTree tool( &moab );
00991     ErrorCode rval;
00992     EntityHandle root;
00993     BSPTreeBoxIter iter;
00994     BSPTree::Plane p;
00995 
00996     /*  Build Tree */
00997 
00998     const double corners[8][3] = { { 0, 0, 0 }, { 8, 0, 0 }, { 8, 2, 0 }, { 0, 2, 0 },
00999                                    { 0, 0, 1 }, { 8, 0, 1 }, { 8, 2, 1 }, { 0, 2, 1 } };
01000     rval                       = tool.create_tree( corners, root );CHECK_ERR( rval );
01001     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01002     EntityHandle leaves[8];
01003 
01004     /* +----------------------------------------+
01005        |                                        |
01006        |                   0*                   |
01007        |                                        |
01008        +----------------------------------------+ */
01009 
01010     p    = BSPTree::Plane( 1, 0, 0, -4 );
01011     rval = tool.split_leaf( iter, p );CHECK_ERR( rval );
01012 
01013     /* +-------------------+--------------------+
01014        |                   |                    |
01015        |         0*        |         1          |
01016        |                   |                    |
01017        +----------------------------------------+ */
01018 
01019     p    = BSPTree::Plane( -1, 0, 0, 2 );
01020     rval = tool.split_leaf( iter, p );CHECK_ERR( rval );
01021 
01022     /* +---------+---------+--------------------+
01023        |         |         |                    |
01024        |    1    |    0*   |         2          |
01025        |         |         |                    |
01026        +----------------------------------------+ */
01027 
01028     p    = BSPTree::Plane( 0, 1, 0, -1 );
01029     rval = tool.split_leaf( iter, p );CHECK_ERR( rval );
01030 
01031     /* +---------+---------+--------------------+
01032        |         |    1    |                    |
01033        |    2    +---------+         3          |
01034        |         |    0*   |                    |
01035        +----------------------------------------+ */
01036 
01037     leaves[0] = iter.handle();
01038     rval      = iter.step();CHECK_ERR( rval );
01039     leaves[1] = iter.handle();
01040     rval      = iter.step();CHECK_ERR( rval );
01041 
01042     /* +---------+---------+--------------------+
01043        |         |    1    |                    |
01044        |    2*   +---------+         3          |
01045        |         |    0    |                    |
01046        +----------------------------------------+ */
01047 
01048     p    = BSPTree::Plane( 0, -1, 0, 1 );
01049     rval = tool.split_leaf( iter, p );CHECK_ERR( rval );
01050 
01051     /* +---------+---------+--------------------+
01052        |    2*   |    1    |                    |
01053        +---------+---------+         4          |
01054        |    3    |    0    |                    |
01055        +----------------------------------------+ */
01056 
01057     leaves[2] = iter.handle();
01058     rval      = iter.step();CHECK_ERR( rval );
01059     leaves[3] = iter.handle();
01060     rval      = iter.step();CHECK_ERR( rval );
01061 
01062     /* +---------+---------+--------------------+
01063        |    2    |    1    |                    |
01064        +---------+---------+         4*         |
01065        |    3    |    0    |                    |
01066        +----------------------------------------+ */
01067 
01068     p    = BSPTree::Plane( 0, 1, 0, -1 );
01069     rval = tool.split_leaf( iter, p );CHECK_ERR( rval );
01070 
01071     /* +---------+---------+--------------------+
01072        |    2    |    1    |         5          |
01073        +---------+---------+--------------------+
01074        |    3    |    0    |         4*         |
01075        +----------------------------------------+ */
01076 
01077     p    = BSPTree::Plane( 1, 0, 0, -6 );
01078     rval = tool.split_leaf( iter, p );CHECK_ERR( rval );
01079 
01080     /* +---------+---------+--------------------+
01081        |    2    |    1    |          6         |
01082        +---------+---------+----------+---------+
01083        |    3    |    0    |    4*    |    5    |
01084        +------------------------------+---------+ */
01085 
01086     leaves[4] = iter.handle();
01087     rval      = iter.step();CHECK_ERR( rval );
01088     leaves[5] = iter.handle();
01089     rval      = iter.step();CHECK_ERR( rval );
01090 
01091     /* +---------+---------+--------------------+
01092        |    2    |    1    |          6*        |
01093        +---------+---------+----------+---------+
01094        |    3    |    0    |     4    |    5    |
01095        +------------------------------+---------+ */
01096 
01097     p    = BSPTree::Plane( -1, 0, 0, 6 );
01098     rval = tool.split_leaf( iter, p );CHECK_ERR( rval );
01099 
01100     /* +---------+---------+--------------------+
01101        |    2    |    1    |     7    |    6    |
01102        +---------+---------+----------+---------+
01103        |    3    |    0    |     4    |    5    |
01104        +------------------------------+---------+ */
01105 
01106     leaves[6] = iter.handle();
01107     rval      = iter.step();CHECK_ERR( rval );
01108     leaves[7] = iter.handle();
01109 
01110     /* check all neighbors of each leaf */
01111 
01112     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01113 
01114     // NOTE:  Several values in the expected result list are
01115     //        commented out in the tests below.  When the tolerance
01116     //        is greater than zero, the search algorithm may or may
01117     //        not return leaves that are not face-adjacent (e.g. adjacent
01118     //        only along edges or at corners.)  The determining factor
01119     //        for whether or not such a neighbor is returned is which
01120     //        sub-tree of the split that defined the source leaf side
01121     //        the neighbor is on.  The algorithm will not search the subtree
01122     //        of the split that created the side and that contains the
01123     //        source leaf.
01124 
01125     // check neighbors of leaf 0
01126     std::vector< int > expected;
01127     CHECK_EQUAL( leaves[0], iter.handle() );
01128     expected.clear();
01129     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, 1e-6 ) );
01130     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3210, 1e-6 ) );
01131     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B4567, 1e-6 ) );
01132     expected.push_back( 3 );
01133     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, -1e-6 ) );
01134     expected.insert( expected.begin(), 2 );
01135     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, 1e-6 ) );
01136     expected.clear();
01137     expected.push_back( 1 );
01138     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, -1e-6 ) );
01139     // See NOTE //  expected.push_back( 2 ); expected.push_back( 7 );
01140     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, 1e-6 ) );
01141     expected.clear();
01142     expected.push_back( 4 );
01143     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, -1e-6 ) );
01144     expected.push_back( 7 );
01145     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, 1e-6 ) );
01146 
01147     // check neighbors of leaf 1
01148     CHECK_ERR( iter.step() );
01149     CHECK_EQUAL( leaves[1], iter.handle() );
01150     expected.clear();
01151     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, 1e-6 ) );
01152     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3210, 1e-6 ) );
01153     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B4567, 1e-6 ) );
01154     expected.push_back( 2 );
01155     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, -1e-6 ) );
01156     expected.push_back( 3 );
01157     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, 1e-6 ) );
01158     expected.clear();
01159     expected.push_back( 0 );
01160     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, -1e-6 ) );
01161     // See NOTE //  expected.push_back( 3 ); expected.push_back( 4 );
01162     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, 1e-6 ) );
01163     expected.clear();
01164     expected.push_back( 7 );
01165     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, -1e-6 ) );
01166     expected.insert( expected.begin(), 4 );
01167     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, 1e-6 ) );
01168 
01169     /* +---------+---------+--------------------+
01170        |    2    |    1    |     7    |    6    |
01171        +---------+---------+----------+---------+
01172        |    3    |    0    |     4    |    5    |
01173        +------------------------------+---------+ */
01174 
01175     // check neighbors of leaf 2
01176     CHECK_ERR( iter.step() );
01177     CHECK_EQUAL( leaves[2], iter.handle() );
01178     expected.clear();
01179     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, 1e-6 ) );
01180     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, 1e-6 ) );
01181     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3210, 1e-6 ) );
01182     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B4567, 1e-6 ) );
01183     expected.push_back( 3 );
01184     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, -1e-6 ) );
01185     // See NOTE // expected.insert( expected.begin(), 0 );
01186     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, 1e-6 ) );
01187     expected.clear();
01188     expected.push_back( 1 );
01189     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, -1e-6 ) );
01190     expected.insert( expected.begin(), 0 );
01191     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, 1e-6 ) );
01192 
01193     // check neighbors of leaf 3
01194     CHECK_ERR( iter.step() );
01195     CHECK_EQUAL( leaves[3], iter.handle() );
01196     expected.clear();
01197     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, 1e-6 ) );
01198     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, 1e-6 ) );
01199     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3210, 1e-6 ) );
01200     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B4567, 1e-6 ) );
01201     expected.push_back( 2 );
01202     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, -1e-6 ) );
01203     // See NOTE // expected.insert( expected.begin(), 1 );
01204     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, 1e-6 ) );
01205     expected.clear();
01206     expected.push_back( 0 );
01207     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, -1e-6 ) );
01208     expected.push_back( 1 );
01209     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, 1e-6 ) );
01210 
01211     /* +---------+---------+--------------------+
01212        |    2    |    1    |     7    |    6    |
01213        +---------+---------+----------+---------+
01214        |    3    |    0    |     4    |    5    |
01215        +------------------------------+---------+ */
01216 
01217     // check neighbors of leaf 4
01218     CHECK_ERR( iter.step() );
01219     CHECK_EQUAL( leaves[4], iter.handle() );
01220     expected.clear();
01221     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, 1e-6 ) );
01222     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3210, 1e-6 ) );
01223     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B4567, 1e-6 ) );
01224     expected.push_back( 0 );
01225     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, -1e-6 ) );
01226     expected.push_back( 1 );
01227     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, 1e-6 ) );
01228     expected.clear();
01229     expected.push_back( 7 );
01230     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, -1e-6 ) );
01231     expected.insert( expected.begin(), 6 );
01232     // See NOTE // expected.insert( expected.begin(), 1 );
01233     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, 1e-6 ) );
01234     expected.clear();
01235     expected.push_back( 5 );
01236     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, -1e-6 ) );
01237     // See NOTE // expected.push_back( 6 );
01238     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, 1e-6 ) );
01239 
01240     // check neighbors of leaf 5
01241     CHECK_ERR( iter.step() );
01242     CHECK_EQUAL( leaves[5], iter.handle() );
01243     expected.clear();
01244     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, 1e-6 ) );
01245     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, 1e-6 ) );
01246     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3210, 1e-6 ) );
01247     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B4567, 1e-6 ) );
01248     expected.push_back( 4 );
01249     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, -1e-6 ) );
01250     // See NOTE // expected.push_back( 7 );
01251     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, 1e-6 ) );
01252     expected.clear();
01253     expected.push_back( 6 );
01254     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, -1e-6 ) );
01255     expected.push_back( 7 );
01256     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, 1e-6 ) );
01257 
01258     /* +---------+---------+--------------------+
01259        |    2    |    1    |     7    |    6    |
01260        +---------+---------+----------+---------+
01261        |    3    |    0    |     4    |    5    |
01262        +------------------------------+---------+ */
01263 
01264     // check neighbors of leaf 6
01265     CHECK_ERR( iter.step() );
01266     CHECK_EQUAL( leaves[6], iter.handle() );
01267     expected.clear();
01268     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, 1e-6 ) );
01269     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, 1e-6 ) );
01270     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3210, 1e-6 ) );
01271     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B4567, 1e-6 ) );
01272     expected.push_back( 7 );
01273     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, -1e-6 ) );
01274     // See NOTE // expected.insert( expected.begin(), 4 );
01275     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, 1e-6 ) );
01276     expected.clear();
01277     expected.push_back( 5 );
01278     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, -1e-6 ) );
01279     expected.insert( expected.begin(), 4 );
01280     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, 1e-6 ) );
01281 
01282     // check neighbors of leaf 7
01283     CHECK_ERR( iter.step() );
01284     CHECK_EQUAL( leaves[7], iter.handle() );
01285     expected.clear();
01286     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B2376, 1e-6 ) );
01287     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3210, 1e-6 ) );
01288     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B4567, 1e-6 ) );
01289     expected.push_back( 1 );
01290     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, -1e-6 ) );
01291     expected.insert( expected.begin(), 0 );
01292     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B3047, 1e-6 ) );
01293     expected.clear();
01294     expected.push_back( 4 );
01295     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, -1e-6 ) );
01296     // See NOTE // expected.insert( expected.begin(), 0 );
01297     expected.push_back( 5 );
01298     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B0154, 1e-6 ) );
01299     expected.clear();
01300     expected.push_back( 6 );
01301     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, -1e-6 ) );
01302     // See NOTE // expected.insert( expected.begin(), 5 );
01303     CHECK_EQUAL( expected, neighbors( iter, leaves, BSPTreeBoxIter::B1265, 1e-6 ) );
01304 }
01305 
01306 void test_leaf_sibling()
01307 {
01308     Core moab;
01309     BSPTree tool( &moab );
01310     ErrorCode rval;
01311     EntityHandle root;
01312     BSPTreeIter iter;
01313 
01314     /*  Build Tree
01315 
01316       1.0 +---------+--------------+
01317           |    A    |              |
01318           |         |              |
01319       0.7 +---------+      C       |
01320           |         |              |
01321           |         |              |
01322           |    B    |              |
01323           |         +--------------+ 0.3
01324           |         |      D       |
01325           |         |              |
01326       0.0 +---------+--------------+
01327           0.0       0.4            1.0  */
01328 
01329     const BSPTree::Plane X_split( 1.0, 0.0, 0.0, -0.4 );
01330     const BSPTree::Plane AB_split( 0.0, -1.0, 0.0, 0.7 );
01331     const BSPTree::Plane CD_split( 0.0, -1.0, 0.0, 0.3 );
01332 
01333     const double min[3] = { 0, 0, 0 };
01334     const double max[3] = { 1, 1, 1 };
01335     rval                = tool.create_tree( min, max, root );CHECK_ERR( rval );
01336     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01337     rval = tool.split_leaf( iter, X_split );CHECK_ERR( rval );
01338     rval = tool.split_leaf( iter, AB_split );CHECK_ERR( rval );
01339     rval = iter.step();CHECK_ERR( rval );
01340     rval = iter.step();CHECK_ERR( rval );
01341     rval = tool.split_leaf( iter, CD_split );CHECK_ERR( rval );
01342 
01343     // create two iterators for testing
01344     BSPTreeIter iter1, iter2;
01345     rval = tool.get_tree_iterator( root, iter1 );CHECK_ERR( rval );
01346     rval = tool.get_tree_iterator( root, iter2 );CHECK_ERR( rval );
01347 
01348     // iter1 == A, iter2 == A
01349     CHECK( !iter1.is_sibling( iter1 ) );
01350     CHECK( !iter1.is_sibling( iter1.handle() ) );
01351     CHECK( !iter1.is_sibling( iter2 ) );
01352     CHECK( iter1.sibling_is_forward() );
01353 
01354     // iter1 == A, iter2 == B
01355     rval = iter2.step();CHECK_ERR( rval );
01356     CHECK( iter1.is_sibling( iter2 ) );
01357     CHECK( iter1.is_sibling( iter2.handle() ) );
01358     CHECK( iter2.is_sibling( iter1 ) );
01359     CHECK( iter2.is_sibling( iter1.handle() ) );
01360     CHECK( !iter2.sibling_is_forward() );
01361 
01362     // iter1 == A, iter2 == C
01363     rval = iter2.step();CHECK_ERR( rval );
01364     CHECK( !iter1.is_sibling( iter2 ) );
01365     CHECK( !iter1.is_sibling( iter2.handle() ) );
01366     CHECK( !iter2.is_sibling( iter1 ) );
01367     CHECK( !iter2.is_sibling( iter1.handle() ) );
01368     CHECK( iter2.sibling_is_forward() );
01369 
01370     // iter1 == B, iter2 == C
01371     rval = iter1.step();CHECK_ERR( rval );
01372     CHECK( !iter1.is_sibling( iter2 ) );
01373     CHECK( !iter1.is_sibling( iter2.handle() ) );
01374     CHECK( !iter2.is_sibling( iter1 ) );
01375     CHECK( !iter2.is_sibling( iter1.handle() ) );
01376     CHECK( !iter1.sibling_is_forward() );
01377 
01378     // iter1 == D, iter2 == C
01379     rval = iter1.step();CHECK_ERR( rval );
01380     CHECK_EQUAL( iter1.handle(), iter2.handle() );
01381     rval = iter1.step();CHECK_ERR( rval );
01382     CHECK( iter1.is_sibling( iter2 ) );
01383     CHECK( iter1.is_sibling( iter2.handle() ) );
01384     CHECK( iter2.is_sibling( iter1 ) );
01385     CHECK( iter2.is_sibling( iter1.handle() ) );
01386     CHECK( !iter1.sibling_is_forward() );
01387 }
01388 
01389 void test_leaf_volume( bool box )
01390 {
01391     Core moab;
01392     BSPTree tool( &moab );
01393     ErrorCode rval;
01394     EntityHandle root;
01395     BSPTreeBoxIter b_iter;
01396     BSPTreeIter g_iter;
01397     BSPTreeIter& iter = box ? b_iter : g_iter;
01398 
01399     /*  Build Tree
01400 
01401       1.0 +---------+--------------+
01402           |    A    |              |
01403           |         |              |
01404       0.7 +---------+      C       |
01405           |         |              |
01406           |         |              |
01407           |    B    |              |
01408           |         +--------------+ 0.3
01409           |         |      D       |
01410           |         |              |
01411       0.0 +---------+--------------+
01412           0.0       0.4            1.0  */
01413 
01414     const BSPTree::Plane X_split( 1.0, 0.0, 0.0, -0.4 );
01415     const BSPTree::Plane AB_split( 0.0, -1.0, 0.0, 0.7 );
01416     const BSPTree::Plane CD_split( 0.0, -1.0, 0.0, 0.3 );
01417 
01418     const double min[3] = { 0, 0, 0 };
01419     const double max[3] = { 1, 1, 1 };
01420     rval                = tool.create_tree( min, max, root );CHECK_ERR( rval );
01421     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01422     rval = tool.split_leaf( iter, X_split );CHECK_ERR( rval );
01423     rval = tool.split_leaf( iter, AB_split );CHECK_ERR( rval );
01424     rval = iter.step();CHECK_ERR( rval );
01425     rval = iter.step();CHECK_ERR( rval );
01426     rval = tool.split_leaf( iter, CD_split );CHECK_ERR( rval );
01427 
01428     // reset iterator
01429     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01430 
01431     // check leaf volumes
01432     CHECK_REAL_EQUAL( 0.12, iter.volume(), 1e-12 );  // A
01433     CHECK_ERR( iter.step() );
01434     CHECK_REAL_EQUAL( 0.28, iter.volume(), 1e-12 );  // B
01435     CHECK_ERR( iter.step() );
01436     CHECK_REAL_EQUAL( 0.42, iter.volume(), 1e-12 );  // C
01437     CHECK_ERR( iter.step() );
01438     CHECK_REAL_EQUAL( 0.18, iter.volume(), 1e-12 );  // D
01439 }
01440 
01441 void test_leaf_splits_intersects()
01442 {
01443     Core moab;
01444     BSPTree tool( &moab );
01445     ErrorCode rval;
01446     EntityHandle root;
01447     BSPTreeBoxIter iter;
01448     BSPTree::Plane p;
01449 
01450     const double min[3] = { 0, 0, 0 };
01451     const double max[3] = { 1, 2, 3 };
01452     rval                = tool.create_tree( min, max, root );CHECK_ERR( rval );
01453     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01454 
01455     p.set( 1, 0, 0, 1 );  // x == -1
01456     CHECK_EQUAL( BSPTreeBoxIter::MISS, iter.splits( p ) );
01457     CHECK( !iter.intersects( p ) );
01458     p.flip();
01459     CHECK_EQUAL( BSPTreeBoxIter::MISS, iter.splits( p ) );
01460     CHECK( !iter.intersects( p ) );
01461 
01462     p.set( 1, 0, 0, 0 );  // x == 0
01463     CHECK_EQUAL( BSPTreeBoxIter::NONHEX, iter.splits( p ) );
01464     p.flip();
01465     CHECK_EQUAL( BSPTreeBoxIter::NONHEX, iter.splits( p ) );
01466 
01467     p.set( 1, 0, 0, -0.5 );  // x == 0.5
01468     CHECK_EQUAL( BSPTreeBoxIter::SPLIT, iter.splits( p ) );
01469     CHECK( iter.intersects( p ) );
01470     p.flip();
01471     CHECK_EQUAL( BSPTreeBoxIter::SPLIT, iter.splits( p ) );
01472     CHECK( iter.intersects( p ) );
01473 
01474     p.set( 1, 0, 0, -1 );  // x == 1
01475     CHECK_EQUAL( BSPTreeBoxIter::NONHEX, iter.splits( p ) );
01476     p.flip();
01477     CHECK_EQUAL( BSPTreeBoxIter::NONHEX, iter.splits( p ) );
01478 
01479     p.set( 1, 0, 0, -2 );  // x == 2
01480     CHECK_EQUAL( BSPTreeBoxIter::MISS, iter.splits( p ) );
01481     CHECK( !iter.intersects( p ) );
01482     p.flip();
01483     CHECK_EQUAL( BSPTreeBoxIter::MISS, iter.splits( p ) );
01484     CHECK( !iter.intersects( p ) );
01485 
01486     double pt1[3] = { 0, 0, 1.5 };
01487     double pt2[3] = { 1, 0, 1.5 };
01488     double pt3[3] = { 0, 1, 3.0 };
01489     p.set( pt1, pt2, pt3 );
01490     CHECK_EQUAL( BSPTreeBoxIter::NONHEX, iter.splits( p ) );
01491     CHECK( iter.intersects( p ) );
01492     p.flip();
01493     CHECK_EQUAL( BSPTreeBoxIter::NONHEX, iter.splits( p ) );
01494     CHECK( iter.intersects( p ) );
01495 
01496     double pt4[3] = { 0, 2, 2.8 };
01497     p.set( pt1, pt2, pt4 );
01498     CHECK_EQUAL( BSPTreeBoxIter::SPLIT, iter.splits( p ) );
01499     CHECK( iter.intersects( p ) );
01500     p.flip();
01501     CHECK_EQUAL( BSPTreeBoxIter::SPLIT, iter.splits( p ) );
01502     CHECK( iter.intersects( p ) );
01503 
01504     double pta[3] = { 0.8, 0, 0 };
01505     double ptb[3] = { 0, 0.2, 3 };
01506     double ptc[3] = { 0.8, 2, 3 };
01507     p.set( pta, ptb, ptc );
01508     CHECK_EQUAL( BSPTreeBoxIter::NONHEX, iter.splits( p ) );
01509     CHECK( iter.intersects( p ) );
01510     p.flip();
01511     CHECK_EQUAL( BSPTreeBoxIter::NONHEX, iter.splits( p ) );
01512     CHECK( iter.intersects( p ) );
01513 }
01514 
01515 #define CHECK_RAY_XSECTS( PT, DIR, T_IN, T_OUT )                     \
01516     do                                                               \
01517     {                                                                \
01518         CHECK( iter.intersect_ray( ( PT ), ( DIR ), t_in, t_out ) ); \
01519         CHECK_REAL_EQUAL( ( T_IN ), t_in, 1e-6 );                    \
01520         CHECK_REAL_EQUAL( ( T_OUT ), t_out, 1e-6 );                  \
01521     } while( false )
01522 
01523 void test_leaf_intersects_ray_common( bool box )
01524 {
01525     ErrorCode rval;
01526     Core moab;
01527     BSPTree tool( &moab );
01528     double t_in, t_out;
01529 
01530     /** Start with only root box for initial testing **/
01531 
01532     /*  (1,5,-3)   (2,5,-3)
01533               o----o
01534              /:   / \
01535             / :  /    \
01536    (1,5,-1)o----o       \
01537            |  :  \        \
01538            |  :  Y \        \
01539            |  :  ^   \        \
01540            |  :  |     \        \
01541            |  :  +-->X   \        \ (6,1,-3)
01542            |  o./..........\.......o
01543            | . L             \    /
01544            |. Z                \ /
01545            o--------------------o
01546     (1,1,-1)                    (6,1,-1)
01547     */
01548     EntityHandle root;
01549     const double corners[][3] = { { 1, 1, -3 }, { 6, 1, -3 }, { 2, 5, -3 }, { 1, 5, -3 },
01550                                   { 1, 1, -1 }, { 6, 1, -1 }, { 2, 5, -1 }, { 1, 5, -1 } };
01551     rval                      = tool.create_tree( corners, root );CHECK_ERR( rval );
01552 
01553     BSPTreeIter gen_iter;
01554     BSPTreeBoxIter box_iter;
01555     BSPTreeIter& iter = box ? static_cast< BSPTreeIter& >( box_iter ) : gen_iter;
01556     rval              = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01557 
01558     // start with point inside box
01559     const double pt1[]  = { 3.5, 3, -2 };
01560     const double dir1[] = { 0.1, 0.1, 0.1 };
01561     CHECK_RAY_XSECTS( pt1, dir1, 0, 2.5 );
01562     const double dir2[] = { 5, 5, 5 };
01563     CHECK_RAY_XSECTS( pt1, dir2, 0, 0.05 );
01564     const double pxdir[] = { 1, 0, 0 };
01565     CHECK_RAY_XSECTS( pt1, pxdir, 0, 0.5 );
01566     const double nxdir[] = { -1, 0, 0 };
01567     CHECK_RAY_XSECTS( pt1, nxdir, 0, 2.5 );
01568     const double pydir[] = { 0, 1, 0 };
01569     CHECK_RAY_XSECTS( pt1, pydir, 0, 0.5 );
01570     const double nydir[] = { 0, -1, 0 };
01571     CHECK_RAY_XSECTS( pt1, nydir, 0, 2 );
01572     const double pzdir[] = { 0, 0, 1 };
01573     CHECK_RAY_XSECTS( pt1, pzdir, 0, 1 );
01574     const double nzdir[] = { 0, 0, -1 };
01575     CHECK_RAY_XSECTS( pt1, nzdir, 0, 1 );
01576 
01577     // point below box
01578     const double pt2[] = { 3.5, 3, -4 };
01579     CHECK( !iter.intersect_ray( pt2, dir1, t_in, t_out ) );
01580     CHECK( !iter.intersect_ray( pt2, dir2, t_in, t_out ) );
01581     CHECK( !iter.intersect_ray( pt2, pxdir, t_in, t_out ) );
01582     CHECK( !iter.intersect_ray( pt2, nxdir, t_in, t_out ) );
01583     CHECK( !iter.intersect_ray( pt2, pydir, t_in, t_out ) );
01584     CHECK( !iter.intersect_ray( pt2, nydir, t_in, t_out ) );
01585     CHECK_RAY_XSECTS( pt2, pzdir, 1, 3 );
01586     CHECK( !iter.intersect_ray( pt2, nzdir, t_in, t_out ) );
01587 
01588     // point right of box
01589     const double pt3[] = { 7, 3, -2 };
01590     CHECK( !iter.intersect_ray( pt3, dir1, t_in, t_out ) );
01591     CHECK( !iter.intersect_ray( pt3, dir2, t_in, t_out ) );
01592     CHECK( !iter.intersect_ray( pt3, pxdir, t_in, t_out ) );
01593     CHECK_RAY_XSECTS( pt3, nxdir, 3, 6 );
01594     CHECK( !iter.intersect_ray( pt3, pydir, t_in, t_out ) );
01595     CHECK( !iter.intersect_ray( pt3, nydir, t_in, t_out ) );
01596     CHECK( !iter.intersect_ray( pt3, pzdir, t_in, t_out ) );
01597     CHECK( !iter.intersect_ray( pt3, nzdir, t_in, t_out ) );
01598 
01599     // a few more complex test cases
01600     const double dira[] = { -2, -2, 0 };
01601     CHECK_RAY_XSECTS( pt3, dira, 0.75, 1.0 );
01602     const double dirb[] = { -1, -2.1, 0 };
01603     CHECK( !iter.intersect_ray( pt3, dirb, t_in, t_out ) );
01604 
01605     /** Now split twice and test the bottom right corne **/
01606 
01607     BSPTree::Plane Y3( BSPTree::Y, 3.0 );
01608     rval = tool.split_leaf( iter, Y3 );CHECK_ERR( rval );
01609     BSPTree::Plane X2( BSPTree::X, 2.0 );
01610     rval = tool.split_leaf( iter, X2 );CHECK_ERR( rval );
01611     rval = iter.step();CHECK_ERR( rval );
01612 
01613     /*
01614                (2,3,-3)
01615                    o--------o (4,3,-3)
01616                   /:       /  \
01617                  / :      /     \
01618         (2,3,-1)o--------o(4,3,-1)\ (6,1,-3)
01619                 |  o.......\.......o
01620                 | .          \    /
01621                 |.             \ /
01622                 o---------------o
01623            (2,1,-1)             (6,1,-1)
01624     */
01625 
01626     // start with point inside box
01627     const double pt4[] = { 4, 2, -2 };
01628     CHECK_RAY_XSECTS( pt4, dir1, 0, 5 );
01629     CHECK_RAY_XSECTS( pt4, dir2, 0, 0.1 );
01630     CHECK_RAY_XSECTS( pt4, pxdir, 0, 1 );
01631     CHECK_RAY_XSECTS( pt4, nxdir, 0, 2 );
01632     CHECK_RAY_XSECTS( pt4, pydir, 0, 1 );
01633     CHECK_RAY_XSECTS( pt4, nydir, 0, 1 );
01634     CHECK_RAY_XSECTS( pt4, pzdir, 0, 1 );
01635     CHECK_RAY_XSECTS( pt4, nzdir, 0, 1 );
01636 
01637     // point below box
01638     const double pt5[] = { 4, 2, -4 };
01639     CHECK( !iter.intersect_ray( pt5, dir1, t_in, t_out ) );
01640     CHECK( !iter.intersect_ray( pt5, dir2, t_in, t_out ) );
01641     CHECK( !iter.intersect_ray( pt5, pxdir, t_in, t_out ) );
01642     CHECK( !iter.intersect_ray( pt5, nxdir, t_in, t_out ) );
01643     CHECK( !iter.intersect_ray( pt5, pydir, t_in, t_out ) );
01644     CHECK( !iter.intersect_ray( pt5, nydir, t_in, t_out ) );
01645     CHECK_RAY_XSECTS( pt5, pzdir, 1, 3 );
01646     CHECK( !iter.intersect_ray( pt5, nzdir, t_in, t_out ) );
01647 
01648     // point right of box
01649     const double pt6[] = { 7, 2, -2 };
01650     CHECK( !iter.intersect_ray( pt6, dir1, t_in, t_out ) );
01651     CHECK( !iter.intersect_ray( pt6, dir2, t_in, t_out ) );
01652     CHECK( !iter.intersect_ray( pt6, pxdir, t_in, t_out ) );
01653     CHECK_RAY_XSECTS( pt6, nxdir, 2, 5 );
01654     CHECK( !iter.intersect_ray( pt6, pydir, t_in, t_out ) );
01655     CHECK( !iter.intersect_ray( pt6, nydir, t_in, t_out ) );
01656     CHECK( !iter.intersect_ray( pt6, pzdir, t_in, t_out ) );
01657     CHECK( !iter.intersect_ray( pt6, nzdir, t_in, t_out ) );
01658 
01659     // a few more complex test cases
01660     const double dird[] = { -2, -2, 0 };
01661     CHECK_RAY_XSECTS( pt6, dird, 0.5, 0.5 );
01662     const double dire[] = { -3, -2, 0 };
01663     CHECK_RAY_XSECTS( pt6, dire, 0.4, 0.5 );
01664     const double dirf[] = { -2, -2.1, 0 };
01665     CHECK( !iter.intersect_ray( pt6, dirf, t_in, t_out ) );
01666 }
01667 
01668 static void box( const double pts[], int num_pts, double minpt[3], double maxpt[3] )
01669 {
01670     minpt[0] = maxpt[0] = pts[0];
01671     minpt[1] = maxpt[1] = pts[1];
01672     minpt[2] = maxpt[2] = pts[2];
01673     for( int i = 1; i < num_pts; ++i )
01674     {
01675         for( int d = 0; d < 3; ++d )
01676         {
01677             if( pts[3 * i + d] < minpt[d] ) minpt[d] = pts[3 * i + d];
01678             if( pts[3 * i + d] > maxpt[d] ) maxpt[d] = pts[3 * i + d];
01679         }
01680     }
01681 }
01682 
01683 static EntityHandle build_tree( const double points[], int num_points, BSPTree& tool )
01684 {
01685     // create points
01686     ErrorCode rval;
01687     std::vector< EntityHandle > pts( num_points );
01688     for( int i = 0; i < num_points; ++i )
01689     {
01690         rval = tool.moab()->create_vertex( points + 3 * i, pts[i] );CHECK_ERR( rval );
01691     }
01692 
01693     // calculate bounding box of tree
01694     double minpt[3], maxpt[3];
01695     box( points, num_points, minpt, maxpt );
01696 
01697     // create initial (1-node) tree
01698     EntityHandle root;
01699     rval = tool.create_tree( minpt, maxpt, root );CHECK_ERR( rval );
01700 
01701     BSPTreeIter iter;
01702     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01703 
01704     rval = tool.moab()->add_entities( root, &pts[0], pts.size() );CHECK_ERR( rval );
01705 
01706     // build tree
01707     std::vector< EntityHandle > left_pts, right_pts;
01708     std::vector< CartVect > coords( num_points ), tmp_coords;
01709     for( ; MB_SUCCESS == rval; rval = iter.step() )
01710     {
01711         pts.clear();
01712         rval = tool.moab()->get_entities_by_handle( iter.handle(), pts );CHECK_ERR( rval );
01713         while( pts.size() > 1 )
01714         {
01715 
01716             coords.resize( pts.size() );
01717             rval = tool.moab()->get_coords( &pts[0], pts.size(), coords[0].array() );CHECK_ERR( rval );
01718 
01719             // find two points far apart apart
01720             std::vector< CartVect >* ptr;
01721             if( coords.size() < 10 )
01722                 ptr = &coords;
01723             else
01724             {
01725                 tmp_coords.resize( 16 );
01726                 CartVect pn, px;
01727                 box( coords[0].array(), coords.size(), pn.array(), px.array() );
01728                 tmp_coords[8]  = pn;
01729                 tmp_coords[9]  = CartVect( px[0], pn[1], pn[2] );
01730                 tmp_coords[10] = CartVect( px[0], px[1], pn[2] );
01731                 tmp_coords[11] = CartVect( pn[0], px[1], pn[2] );
01732                 tmp_coords[12] = CartVect( pn[0], pn[1], px[2] );
01733                 tmp_coords[13] = CartVect( px[0], pn[1], px[2] );
01734                 tmp_coords[14] = px;
01735                 tmp_coords[15] = CartVect( pn[0], px[1], px[2] );
01736                 for( int i = 0; i < 8; ++i )
01737                 {
01738                     tmp_coords[i] = coords[0];
01739                     for( size_t j = 1; j < coords.size(); ++j )
01740                         if( ( coords[j] - tmp_coords[i + 8] ).length_squared() <
01741                             ( tmp_coords[i] - tmp_coords[i + 8] ).length_squared() )
01742                             tmp_coords[i] = coords[j];
01743                 }
01744                 tmp_coords.resize( 8 );
01745                 ptr = &tmp_coords;
01746             }
01747 
01748             size_t pt1 = 0, pt2 = 0;
01749             double lsqr = -1;
01750             for( size_t i = 0; i < ptr->size(); ++i )
01751             {
01752                 for( size_t j = 0; j < ptr->size(); ++j )
01753                 {
01754                     double ls = ( ( *ptr )[i] - ( *ptr )[j] ).length_squared();
01755                     if( ls > lsqr )
01756                     {
01757                         lsqr = ls;
01758                         pt1  = i;
01759                         pt2  = j;
01760                     }
01761                 }
01762             }
01763 
01764             // if all points are coincident
01765             if( lsqr <= 1e-12 ) break;
01766 
01767             // define normal orthogonal to line through two points
01768             CartVect norm = ( *ptr )[pt1] - ( *ptr )[pt2];
01769             norm.normalize();
01770 
01771             // find mean position for plane
01772             double coeff = 0.0;
01773             for( size_t i = 0; i < coords.size(); ++i )
01774                 coeff -= norm % coords[i];
01775             coeff /= coords.size();
01776 
01777             // left/right sort points
01778             left_pts.clear();
01779             right_pts.clear();
01780             for( size_t i = 0; i < coords.size(); ++i )
01781             {
01782                 double d = -( norm % coords[i] );
01783                 if( d >= coeff )
01784                     left_pts.push_back( pts[i] );
01785                 else
01786                     right_pts.push_back( pts[i] );
01787             }
01788 
01789             rval = tool.split_leaf( iter, BSPTree::Plane( norm.array(), coeff ), left_pts, right_pts );CHECK_ERR( rval );
01790             CHECK( !left_pts.empty() && !right_pts.empty() );
01791             pts.swap( left_pts );
01792         }
01793 
01794         //    printf("Leaf %d contains %d vertices: ", (int)ID_FROM_HANDLE(iter.handle()),
01795         //                                             (int)(pts.size()) );
01796         //    for (size_t i = 0; i < pts.size(); ++i)
01797         //      printf( "%d, ", (int)ID_FROM_HANDLE(pts[i]));
01798         //    printf("\n");
01799     }
01800 
01801     CHECK( rval == MB_ENTITY_NOT_FOUND );
01802 
01803     // verify that tree is constructed correctly
01804     for( int i = 0; i < num_points; ++i )
01805     {
01806         CartVect pt( points + 3 * i );
01807         EntityHandle leaf;
01808         rval = tool.leaf_containing_point( root, pt.array(), leaf );CHECK_ERR( rval );
01809         Range ents;
01810         rval = tool.moab()->get_entities_by_handle( leaf, ents );CHECK_ERR( rval );
01811         bool found = false;
01812         for( Range::iterator j = ents.begin(); j != ents.end(); ++j )
01813         {
01814             CartVect ent_coords;
01815             rval = tool.moab()->get_coords( &*j, 1, ent_coords.array() );CHECK_ERR( rval );
01816             if( ( pt - ent_coords ).length_squared() < 1e-6 ) found = true;
01817         }
01818         CHECK( found );
01819     }
01820 
01821     return root;
01822 }
01823 
01824 void test_leaf_polyhedron()
01825 {
01826     // array of 20 points used to construct tree
01827     static const double points[] = { 7, 6, 3, 5, 3, 5, 9, 2, 6, 7, 2, 1, 3, 9, 0, 6, 0, 6, 1, 6,
01828                                      2, 9, 7, 8, 2, 0, 2, 5, 7, 3, 2, 2, 9, 7, 9, 8, 1, 6, 3, 3,
01829                                      9, 2, 4, 9, 1, 4, 8, 7, 3, 0, 5, 0, 1, 6, 2, 3, 6, 1, 6, 0 };
01830     const int num_pts            = sizeof( points ) / ( 3 * sizeof( double ) );
01831 
01832     ErrorCode rval;
01833     Core moab;
01834     BSPTree tool( &moab );
01835     EntityHandle root = build_tree( points, num_pts, tool );
01836 
01837     BSPTreeIter iter;
01838     rval = tool.get_tree_iterator( root, iter );CHECK_ERR( rval );
01839 
01840     std::vector< EntityHandle > pts;
01841     std::vector< CartVect > coords;
01842 
01843     for( ; rval == MB_SUCCESS; rval = iter.step() )
01844     {
01845         BSPTreePoly poly;
01846         rval = iter.calculate_polyhedron( poly );CHECK_ERR( rval );
01847 
01848         CHECK( poly.is_valid() );
01849         CHECK( poly.volume() > 0.0 );
01850 
01851         pts.clear();
01852         rval = tool.moab()->get_entities_by_handle( iter.handle(), pts );CHECK_ERR( rval );
01853         CHECK( !pts.empty() );
01854         coords.resize( pts.size() );
01855         rval = tool.moab()->get_coords( &pts[0], pts.size(), coords[0].array() );CHECK_ERR( rval );
01856 
01857         for( size_t i = 0; i < pts.size(); ++i )
01858             CHECK( poly.is_point_contained( coords[i] ) );
01859     }
01860 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines