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 ()

BSPTree *	tool () 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< EntityHandle >	mStack

std::vector< EntityHandle >	childVect

Private Attributes
BSPTree *	treeTool

Friends
class	BSPTree

Detailed Description

Iterate over leaves of a BSPTree.

Definition at line 252 of file BSPTree.hpp.

Member Enumeration Documentation

◆ Direction

enum moab::BSPTreeIter::Direction

Enumerator
LEFT
RIGHT

Definition at line 255 of file BSPTree.hpp.

  {
  LEFT = 0,
  RIGHT = 1
  };

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.

  {
  return step( LEFT );
  }

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.

 {
  ErrorCode rval;
  
  assert( sizeof( CartVect ) == 3 * sizeof( double ) );
  CartVect corners[8];
  rval = treeTool->get_tree_box( mStack.front(), corners[0].array() );
  if( MB_SUCCESS != rval ) return rval;
  
  rval = poly_out.set( corners );
  if( MB_SUCCESS != rval ) return rval;
  
  BSPTree::Plane plane;
  std::vector< EntityHandle >::const_iterator i = mStack.begin();
  std::vector< EntityHandle >::const_iterator here = mStack.end() - 1;
  while( i != here )
  {
  rval = treeTool->get_split_plane( *i, plane );
  if( MB_SUCCESS != rval ) return rval;
  
  childVect.clear();
  rval = treeTool->moab()->get_child_meshsets( *i, childVect );
  if( MB_SUCCESS != rval ) return rval;
  if( childVect.size() != 2 ) return MB_FAILURE;
  
  ++i;
  if( childVect[1] == *i ) plane.flip();
  
  CartVect norm( plane.norm );
  poly_out.cut_polyhedron( norm, plane.coeff );
  }
  
  return MB_SUCCESS;
 }

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.

  {
  return mStack.size();
  }

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.

 {
  childVect.clear();
  ErrorCode rval = tool()->moab()->get_child_meshsets( mStack.back(), childVect );
  if( MB_SUCCESS != rval ) return rval;
  if( childVect.empty() ) return MB_ENTITY_NOT_FOUND;
  
  mStack.push_back( childVect[dir] );
  return MB_SUCCESS;
 }

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.

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

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.

  {
  return mStack.back();
  }

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.

 {
  treeTool = btool;
  mStack.clear();
  mStack.push_back( root );
  return MB_SUCCESS;
 }

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_point	Coordinates of start point of ray
ray_vect	Directionion vector for ray such that the ray is defined by r(t) = ray_point + t * ray_vect for t > 0.
t_enter	Output: 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_exit	Output: 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.

 {
  // intersect with half-spaces defining tree
  BSPTreePlaneIter iter1( tool(), &mStack[0], mStack.size() ), end1;
  if( !ray_intersect_halfspaces( CartVect( ray_point ), CartVect( ray_vect ), iter1, end1, t_enter, t_exit ) )
  return false;
  
  // itersect with box bounding entire tree
  double corners[8][3];
  ErrorCode rval = tool()->get_tree_box( mStack.front(), corners );
  if( MB_SUCCESS != rval )
  {
  assert( false );
  return false;
  }
  
  BoxPlaneIter iter2( corners ), end2;
  double t2_enter, t2_exit;
  if( !ray_intersect_halfspaces( CartVect( ray_point ), CartVect( ray_vect ), iter2, end2, t2_enter, t2_exit ) )
  return false;
  
  // if intersect both box and halfspaces, check that
  // two intersections overlap
  if( t_enter < t2_enter ) t_enter = t2_enter;
  if( t_exit > t2_exit ) t_exit = t2_exit;
  return t_enter <= t_exit;
 }

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.

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

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.

 {
  if( mStack.size() < 2 || other_leaf == handle() ) return false;
  EntityHandle parent = mStack[mStack.size() - 2];
  childVect.clear();
  ErrorCode rval = tool()->moab()->get_child_meshsets( parent, childVect );
  if( MB_SUCCESS != rval || childVect.size() != 2 )
  {
  assert( false );
  return false;
  }
  return childVect[0] == other_leaf || childVect[1] == other_leaf;
 }

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.

 {
  if( mStack.size() < 2 ) // if root
  return false;
  EntityHandle parent = mStack[mStack.size() - 2];
  childVect.clear();
  ErrorCode rval = tool()->moab()->get_child_meshsets( parent, childVect );
  if( MB_SUCCESS != rval || childVect.size() != 2 )
  {
  assert( false );
  return false;
  }
  return childVect[0] == handle();
 }

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.

  {
  return step( RIGHT );
  }

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.

 {
  EntityHandle node, parent;
  ErrorCode rval;
  const Direction opposite = static_cast< Direction >( 1 - direction );
  
  // If stack is empty, then either this iterator is uninitialized
  // or we reached the end of the iteration (and return
  // MB_ENTITY_NOT_FOUND) already.
  if( mStack.empty() ) return MB_FAILURE;
  
  // Pop the current node from the stack.
  // The stack should then contain the parent of the current node.
  // If the stack is empty after this pop, then we've reached the end.
  node = mStack.back();
  mStack.pop_back();
  
  while( !mStack.empty() )
  {
  // Get data for parent entity
  parent = mStack.back();
  childVect.clear();
  rval = tool()->moab()->get_child_meshsets( parent, childVect );
  if( MB_SUCCESS != rval ) return rval;
  
  // If we're at the left child
  if( childVect[opposite] == node )
  {
  // push right child on stack
  mStack.push_back( childVect[direction] );
  // descend to left-most leaf of the right child
  return step_to_first_leaf( opposite );
  }
  
  // The current node is the right child of the parent,
  // continue up the tree.
  assert( childVect[direction] == node );
  node = parent;
  mStack.pop_back();
  }
  
  return MB_ENTITY_NOT_FOUND;
 }

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.

 {
  ErrorCode rval;
  for( ;; )
  {
  childVect.clear();
  rval = tool()->moab()->get_child_meshsets( mStack.back(), childVect );
  if( MB_SUCCESS != rval ) return rval;
  if( childVect.empty() ) // leaf
  break;
  
  mStack.push_back( childVect[direction] );
  }
  return MB_SUCCESS;
 }

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()

BSPTree* moab::BSPTreeIter::tool ( ) const

inline

Definition at line 281 of file BSPTree.hpp.

  {
  return treeTool;
  }

References treeTool.

Referenced by down(), moab::BSPTreeBoxIter::down(), moab::BSPTreeBoxIter::get_neighbors(), get_parent_split_plane(), moab::BSPTreeBoxIter::initialize(), intersect_ray(), is_sibling(), sibling_is_forward(), moab::BSPTreeBoxIter::sibling_side(), step(), moab::BSPTreeBoxIter::step(), step_to_first_leaf(), moab::BSPTreeBoxIter::step_to_first_leaf(), and moab::BSPTreeBoxIter::up().

◆ up()

ErrorCode moab::BSPTreeIter::up ( )

protectedvirtual

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 442 of file BSPTree.cpp.

 {
  if( mStack.size() < 2 ) return MB_ENTITY_NOT_FOUND;
  mStack.pop_back();
  return MB_SUCCESS;
 }

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.

 {
  BSPTreePoly polyhedron;
  ErrorCode rval = calculate_polyhedron( polyhedron );
  return MB_SUCCESS == rval ? polyhedron.volume() : -1.0;
 }

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

std::vector< EntityHandle > moab::BSPTreeIter::childVect

mutableprotected

Definition at line 268 of file BSPTree.hpp.

Referenced by calculate_polyhedron(), down(), moab::BSPTreeBoxIter::down(), moab::BSPTreeBoxIter::get_neighbors(), is_sibling(), moab::BSPTree::leaf_containing_point(), moab::BSPTree::merge_leaf(), sibling_is_forward(), step(), moab::BSPTreeBoxIter::step(), step_to_first_leaf(), and moab::BSPTreeBoxIter::step_to_first_leaf().

◆ mStack

std::vector< EntityHandle > moab::BSPTreeIter::mStack

protected

Definition at line 267 of file BSPTree.hpp.

Referenced by calculate_polyhedron(), depth(), down(), moab::BSPTreeBoxIter::down(), get_parent_split_plane(), handle(), initialize(), intersect_ray(), is_sibling(), sibling_is_forward(), moab::BSPTreeBoxIter::sibling_side(), step(), moab::BSPTreeBoxIter::step(), step_to_first_leaf(), moab::BSPTreeBoxIter::step_to_first_leaf(), up(), and moab::BSPTreeBoxIter::up().

◆ 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:

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes

Friends

Detailed Description

Member Enumeration Documentation

◆ Direction

Constructor & Destructor Documentation

◆ BSPTreeIter()

◆ ~BSPTreeIter()

Member Function Documentation

◆ back()

◆ calculate_polyhedron()

◆ depth()

◆ down()

◆ get_parent_split_plane()

◆ handle()

◆ initialize()

◆ intersect_ray()

◆ is_sibling() [1/2]

◆ is_sibling() [2/2]

◆ sibling_is_forward()

◆ step() [1/2]

◆ step() [2/2]

◆ step_to_first_leaf()

◆ tool()

◆ up()

◆ volume()

Friends And Related Function Documentation

◆ BSPTree

Member Data Documentation

◆ childVect

◆ mStack

◆ treeTool