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