Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
moab::BSPTreeIter Class Reference

Iterate over leaves of a BSPTree. More...

#include <BSPTree.hpp>

+ Inheritance diagram for moab::BSPTreeIter:
+ Collaboration diagram for moab::BSPTreeIter:

Public Types

enum  Direction { LEFT = 0 , RIGHT = 1 }
 

Public Member Functions

 BSPTreeIter ()
 
virtual ~BSPTreeIter ()
 
BSPTreetool () const
 
EntityHandle handle () const
 Get handle for current leaf. More...
 
unsigned depth () const
 Get depth in tree. root is at depth of 1. More...
 
virtual ErrorCode step (Direction direction)
 Advance the iterator either left or right in the tree Note: stepping past the end of the tree will invalidate the iterator. It will not be work step the other direction. More...
 
ErrorCode step ()
 Advance to next leaf Returns MB_ENTITY_NOT_FOUND if at end. Note: stepping past the end of the tree will invalidate the iterator. Calling back() will not work. More...
 
ErrorCode back ()
 Move back to previous leaf Returns MB_ENTITY_NOT_FOUND if at beginning. Note: stepping past the start of the tree will invalidate the iterator. Calling step() will not work. More...
 
ErrorCode get_parent_split_plane (BSPTree::Plane &plane) const
 Get split plane that separates this node from its immediate sibling. More...
 
virtual double volume () const
 Get volume of leaf polyhedron. More...
 
virtual bool intersect_ray (const double ray_point[3], const double ray_vect[3], double &t_enter, double &t_exit) const
 Find range of overlap between ray and leaf. More...
 
bool is_sibling (const BSPTreeIter &other_leaf) const
 Return true if thos node and the passed node share the same immediate parent. More...
 
bool is_sibling (EntityHandle other_leaf) const
 Return true if thos node and the passed node share the same immediate parent. More...
 
bool sibling_is_forward () const
 Returns true if calling step() will advance to the immediate sibling of the current node. Returns false if current node is root or back() will move to the immediate sibling. More...
 
virtual ErrorCode calculate_polyhedron (BSPTreePoly &polyhedron_out) const
 Calculate the convex polyhedron bounding this leaf. More...
 

Protected Member Functions

virtual ErrorCode step_to_first_leaf (Direction direction)
 
virtual ErrorCode up ()
 
virtual ErrorCode down (const BSPTree::Plane &plane, Direction direction)
 
virtual ErrorCode initialize (BSPTree *tool, EntityHandle root, const double *point=0)
 

Protected Attributes

std::vector< EntityHandlemStack
 
std::vector< EntityHandlechildVect
 

Private Attributes

BSPTreetreeTool
 

Friends

class BSPTree
 

Detailed Description

Iterate over leaves of a BSPTree.

Definition at line 252 of file BSPTree.hpp.

Member Enumeration Documentation

◆ Direction

Enumerator
LEFT 
RIGHT 

Definition at line 255 of file BSPTree.hpp.

256  {
257  LEFT = 0,
258  RIGHT = 1
259  };

Constructor & Destructor Documentation

◆ BSPTreeIter()

moab::BSPTreeIter::BSPTreeIter ( )
inline

Definition at line 278 of file BSPTree.hpp.

278 : treeTool( 0 ), childVect( 2 ) {}

◆ ~BSPTreeIter()

virtual moab::BSPTreeIter::~BSPTreeIter ( )
inlinevirtual

Definition at line 279 of file BSPTree.hpp.

279 {}

Member Function Documentation

◆ back()

ErrorCode moab::BSPTreeIter::back ( )
inline

Move back to previous leaf Returns MB_ENTITY_NOT_FOUND if at beginning. Note: stepping past the start of the tree will invalidate the iterator. Calling step() will not work.

Definition at line 317 of file BSPTree.hpp.

318  {
319  return step( LEFT );
320  }

References LEFT, and step().

Referenced by moab::BSPTreeBoxIter::back().

◆ calculate_polyhedron()

ErrorCode moab::BSPTreeIter::calculate_polyhedron ( BSPTreePoly polyhedron_out) const
virtual

Calculate the convex polyhedron bounding this leaf.

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 512 of file BSPTree.cpp.

513 {
514  ErrorCode rval;
515 
516  assert( sizeof( CartVect ) == 3 * sizeof( double ) );
517  CartVect corners[8];
518  rval = treeTool->get_tree_box( mStack.front(), corners[0].array() );
519  if( MB_SUCCESS != rval ) return rval;
520 
521  rval = poly_out.set( corners );
522  if( MB_SUCCESS != rval ) return rval;
523 
524  BSPTree::Plane plane;
525  std::vector< EntityHandle >::const_iterator i = mStack.begin();
526  std::vector< EntityHandle >::const_iterator here = mStack.end() - 1;
527  while( i != here )
528  {
529  rval = treeTool->get_split_plane( *i, plane );
530  if( MB_SUCCESS != rval ) return rval;
531 
532  childVect.clear();
533  rval = treeTool->moab()->get_child_meshsets( *i, childVect );
534  if( MB_SUCCESS != rval ) return rval;
535  if( childVect.size() != 2 ) return MB_FAILURE;
536 
537  ++i;
538  if( childVect[1] == *i ) plane.flip();
539 
540  CartVect norm( plane.norm );
541  poly_out.cut_polyhedron( norm, plane.coeff );
542  }
543 
544  return MB_SUCCESS;
545 }

References moab::CartVect::array(), childVect, moab::BSPTree::Plane::coeff, moab::BSPTreePoly::cut_polyhedron(), ErrorCode, moab::BSPTree::Plane::flip(), moab::Interface::get_child_meshsets(), moab::BSPTree::get_split_plane(), moab::BSPTree::get_tree_box(), MB_SUCCESS, moab::BSPTree::moab(), mStack, moab::BSPTree::Plane::norm, moab::BSPTreePoly::set(), and treeTool.

Referenced by volume().

◆ depth()

unsigned moab::BSPTreeIter::depth ( ) const
inline

Get depth in tree. root is at depth of 1.

Definition at line 293 of file BSPTree.hpp.

294  {
295  return mStack.size();
296  }

References mStack.

Referenced by moab::BSPTree::merge_leaf().

◆ down()

ErrorCode moab::BSPTreeIter::down ( const BSPTree::Plane plane,
Direction  direction 
)
protectedvirtual

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 449 of file BSPTree.cpp.

450 {
451  childVect.clear();
452  ErrorCode rval = tool()->moab()->get_child_meshsets( mStack.back(), childVect );
453  if( MB_SUCCESS != rval ) return rval;
454  if( childVect.empty() ) return MB_ENTITY_NOT_FOUND;
455 
456  mStack.push_back( childVect[dir] );
457  return MB_SUCCESS;
458 }

References childVect, ErrorCode, moab::Interface::get_child_meshsets(), MB_ENTITY_NOT_FOUND, MB_SUCCESS, moab::BSPTree::moab(), mStack, and tool().

Referenced by moab::BSPTree::leaf_containing_point().

◆ get_parent_split_plane()

ErrorCode moab::BSPTreeIter::get_parent_split_plane ( BSPTree::Plane plane) const

Get split plane that separates this node from its immediate sibling.

Definition at line 460 of file BSPTree.cpp.

461 {
462  if( mStack.size() < 2 ) // at tree root
463  return MB_ENTITY_NOT_FOUND;
464 
465  EntityHandle parent = mStack[mStack.size() - 2];
466  return tool()->get_split_plane( parent, plane );
467 }

References moab::BSPTree::get_split_plane(), MB_ENTITY_NOT_FOUND, mStack, and tool().

◆ handle()

EntityHandle moab::BSPTreeIter::handle ( ) const
inline

Get handle for current leaf.

Definition at line 287 of file BSPTree.hpp.

288  {
289  return mStack.back();
290  }

References mStack.

Referenced by moab::BSPTreeBoxIter::get_neighbors(), is_sibling(), moab::BSPTree::leaf_containing_point(), moab::BSPTree::merge_leaf(), sibling_is_forward(), and moab::BSPTree::split_leaf().

◆ initialize()

ErrorCode moab::BSPTreeIter::initialize ( BSPTree tool,
EntityHandle  root,
const double *  point = 0 
)
protectedvirtual

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 374 of file BSPTree.cpp.

375 {
376  treeTool = btool;
377  mStack.clear();
378  mStack.push_back( root );
379  return MB_SUCCESS;
380 }

References MB_SUCCESS, mStack, and treeTool.

Referenced by moab::BSPTree::get_tree_end_iterator(), moab::BSPTree::get_tree_iterator(), moab::BSPTreeBoxIter::initialize(), and moab::BSPTree::leaf_containing_point().

◆ intersect_ray()

bool moab::BSPTreeIter::intersect_ray ( const double  ray_point[3],
const double  ray_vect[3],
double &  t_enter,
double &  t_exit 
) const
virtual

Find range of overlap between ray and leaf.

Parameters
ray_pointCoordinates of start point of ray
ray_vectDirectionion vector for ray such that the ray is defined by r(t) = ray_point + t * ray_vect for t > 0.
t_enterOutput: if return value is true, this value is the parameter location along the ray at which the ray entered the leaf. If return value is false, then this value is undefined.
t_exitOutput: if return value is true, this value is the parameter location along the ray at which the ray exited the leaf. If return value is false, then this value is undefined.
Returns
true if ray intersects leaf, false otherwise.

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 1338 of file BSPTree.cpp.

1342 {
1343  // intersect with half-spaces defining tree
1344  BSPTreePlaneIter iter1( tool(), &mStack[0], mStack.size() ), end1;
1345  if( !ray_intersect_halfspaces( CartVect( ray_point ), CartVect( ray_vect ), iter1, end1, t_enter, t_exit ) )
1346  return false;
1347 
1348  // itersect with box bounding entire tree
1349  double corners[8][3];
1350  ErrorCode rval = tool()->get_tree_box( mStack.front(), corners );
1351  if( MB_SUCCESS != rval )
1352  {
1353  assert( false );
1354  return false;
1355  }
1356 
1357  BoxPlaneIter iter2( corners ), end2;
1358  double t2_enter, t2_exit;
1359  if( !ray_intersect_halfspaces( CartVect( ray_point ), CartVect( ray_vect ), iter2, end2, t2_enter, t2_exit ) )
1360  return false;
1361 
1362  // if intersect both box and halfspaces, check that
1363  // two intersections overlap
1364  if( t_enter < t2_enter ) t_enter = t2_enter;
1365  if( t_exit > t2_exit ) t_exit = t2_exit;
1366  return t_enter <= t_exit;
1367 }

References ErrorCode, moab::BSPTree::get_tree_box(), MB_SUCCESS, mStack, moab::ray_intersect_halfspaces(), and tool().

◆ is_sibling() [1/2]

bool moab::BSPTreeIter::is_sibling ( const BSPTreeIter other_leaf) const

Return true if thos node and the passed node share the same immediate parent.

Definition at line 476 of file BSPTree.cpp.

477 {
478  const size_t s = mStack.size();
479  return ( s > 1 ) && ( s == other_leaf.mStack.size() ) && ( other_leaf.mStack[s - 2] == mStack[s - 2] ) &&
480  other_leaf.handle() != handle();
481 }

References handle(), and mStack.

◆ is_sibling() [2/2]

bool moab::BSPTreeIter::is_sibling ( EntityHandle  other_leaf) const

Return true if thos node and the passed node share the same immediate parent.

Definition at line 483 of file BSPTree.cpp.

484 {
485  if( mStack.size() < 2 || other_leaf == handle() ) return false;
486  EntityHandle parent = mStack[mStack.size() - 2];
487  childVect.clear();
488  ErrorCode rval = tool()->moab()->get_child_meshsets( parent, childVect );
489  if( MB_SUCCESS != rval || childVect.size() != 2 )
490  {
491  assert( false );
492  return false;
493  }
494  return childVect[0] == other_leaf || childVect[1] == other_leaf;
495 }

References childVect, ErrorCode, moab::Interface::get_child_meshsets(), handle(), MB_SUCCESS, moab::BSPTree::moab(), mStack, and tool().

◆ sibling_is_forward()

bool moab::BSPTreeIter::sibling_is_forward ( ) const

Returns true if calling step() will advance to the immediate sibling of the current node. Returns false if current node is root or back() will move to the immediate sibling.

Definition at line 497 of file BSPTree.cpp.

498 {
499  if( mStack.size() < 2 ) // if root
500  return false;
501  EntityHandle parent = mStack[mStack.size() - 2];
502  childVect.clear();
503  ErrorCode rval = tool()->moab()->get_child_meshsets( parent, childVect );
504  if( MB_SUCCESS != rval || childVect.size() != 2 )
505  {
506  assert( false );
507  return false;
508  }
509  return childVect[0] == handle();
510 }

References childVect, ErrorCode, moab::Interface::get_child_meshsets(), handle(), MB_SUCCESS, moab::BSPTree::moab(), mStack, and tool().

◆ step() [1/2]

ErrorCode moab::BSPTreeIter::step ( )
inline

Advance to next leaf Returns MB_ENTITY_NOT_FOUND if at end. Note: stepping past the end of the tree will invalidate the iterator. Calling back() will not work.

Definition at line 308 of file BSPTree.hpp.

309  {
310  return step( RIGHT );
311  }

References RIGHT.

Referenced by back(), and moab::BSPTreeBoxIter::step().

◆ step() [2/2]

ErrorCode moab::BSPTreeIter::step ( Direction  direction)
virtual

Advance the iterator either left or right in the tree Note: stepping past the end of the tree will invalidate the iterator. It will not be work step the other direction.

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 398 of file BSPTree.cpp.

399 {
400  EntityHandle node, parent;
401  ErrorCode rval;
402  const Direction opposite = static_cast< Direction >( 1 - direction );
403 
404  // If stack is empty, then either this iterator is uninitialized
405  // or we reached the end of the iteration (and return
406  // MB_ENTITY_NOT_FOUND) already.
407  if( mStack.empty() ) return MB_FAILURE;
408 
409  // Pop the current node from the stack.
410  // The stack should then contain the parent of the current node.
411  // If the stack is empty after this pop, then we've reached the end.
412  node = mStack.back();
413  mStack.pop_back();
414 
415  while( !mStack.empty() )
416  {
417  // Get data for parent entity
418  parent = mStack.back();
419  childVect.clear();
420  rval = tool()->moab()->get_child_meshsets( parent, childVect );
421  if( MB_SUCCESS != rval ) return rval;
422 
423  // If we're at the left child
424  if( childVect[opposite] == node )
425  {
426  // push right child on stack
427  mStack.push_back( childVect[direction] );
428  // descend to left-most leaf of the right child
429  return step_to_first_leaf( opposite );
430  }
431 
432  // The current node is the right child of the parent,
433  // continue up the tree.
434  assert( childVect[direction] == node );
435  node = parent;
436  mStack.pop_back();
437  }
438 
439  return MB_ENTITY_NOT_FOUND;
440 }

References childVect, ErrorCode, moab::Interface::get_child_meshsets(), MB_ENTITY_NOT_FOUND, MB_SUCCESS, moab::BSPTree::moab(), mStack, step_to_first_leaf(), and tool().

◆ step_to_first_leaf()

ErrorCode moab::BSPTreeIter::step_to_first_leaf ( Direction  direction)
protectedvirtual

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 382 of file BSPTree.cpp.

383 {
384  ErrorCode rval;
385  for( ;; )
386  {
387  childVect.clear();
388  rval = tool()->moab()->get_child_meshsets( mStack.back(), childVect );
389  if( MB_SUCCESS != rval ) return rval;
390  if( childVect.empty() ) // leaf
391  break;
392 
393  mStack.push_back( childVect[direction] );
394  }
395  return MB_SUCCESS;
396 }

References childVect, ErrorCode, moab::Interface::get_child_meshsets(), MB_SUCCESS, moab::BSPTree::moab(), mStack, and tool().

Referenced by moab::BSPTree::get_tree_end_iterator(), moab::BSPTree::get_tree_iterator(), moab::BSPTree::split_leaf(), and step().

◆ tool()

◆ up()

ErrorCode moab::BSPTreeIter::up ( )
protectedvirtual

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 442 of file BSPTree.cpp.

443 {
444  if( mStack.size() < 2 ) return MB_ENTITY_NOT_FOUND;
445  mStack.pop_back();
446  return MB_SUCCESS;
447 }

References MB_ENTITY_NOT_FOUND, MB_SUCCESS, and mStack.

Referenced by moab::BSPTree::merge_leaf().

◆ volume()

double moab::BSPTreeIter::volume ( ) const
virtual

Get volume of leaf polyhedron.

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 469 of file BSPTree.cpp.

470 {
471  BSPTreePoly polyhedron;
472  ErrorCode rval = calculate_polyhedron( polyhedron );
473  return MB_SUCCESS == rval ? polyhedron.volume() : -1.0;
474 }

References calculate_polyhedron(), ErrorCode, MB_SUCCESS, and moab::BSPTreePoly::volume().

Friends And Related Function Documentation

◆ BSPTree

friend class BSPTree
friend

Definition at line 262 of file BSPTree.hpp.

Member Data Documentation

◆ childVect

◆ mStack

◆ treeTool

BSPTree* moab::BSPTreeIter::treeTool
private

Definition at line 264 of file BSPTree.hpp.

Referenced by calculate_polyhedron(), initialize(), and tool().


The documentation for this class was generated from the following files: