Iterate over leaves of a BSPTree. More...

#include <BSPTree.hpp>

Inheritance 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.
unsigned	depth () const
	Get depth in tree. root is at depth of 1.
virtual ErrorCode	step (Direction direction)
ErrorCode	step ()
ErrorCode	back ()
ErrorCode	get_parent_split_plane (BSPTree::Plane &plane) const
	Get split plane that separates this node from its immediate sibling.
virtual double	volume () const
	Get volume of leaf polyhedron.
virtual bool	intersect_ray (const double ray_point[3], const double ray_vect[3], double &t_enter, double &t_exit) const
bool	is_sibling (const BSPTreeIter &other_leaf) const
bool	is_sibling (EntityHandle other_leaf) const
bool	sibling_is_forward () const
virtual ErrorCode	calculate_polyhedron (BSPTreePoly &polyhedron_out) const
	Calculate the convex polyhedron bounding this leaf.
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 234 of file BSPTree.hpp.

Member Enumeration Documentation

enum moab::BSPTreeIter::Direction

Enumerator:

LEFT
RIGHT

Definition at line 238 of file BSPTree.hpp.

{ LEFT = 0, RIGHT = 1 };

Constructor & Destructor Documentation

moab::BSPTreeIter::BSPTreeIter ( ) [inline]

Definition at line 260 of file BSPTree.hpp.

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

virtual moab::BSPTreeIter::~BSPTreeIter ( ) [inline, virtual]

Definition at line 261 of file BSPTree.hpp.

{}

Member Function Documentation

ErrorCode moab::BSPTreeIter::back ( ) [inline]

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

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 291 of file BSPTree.hpp.

{ return step(LEFT); }

ErrorCode moab::BSPTreeIter::calculate_polyhedron ( BSPTreePoly & polyhedron_out ) const [virtual]

Calculate the convex polyhedron bounding this leaf.

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 563 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;
}

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

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

Definition at line 272 of file BSPTree.hpp.

    { return mStack.size(); }

ErrorCode moab::BSPTreeIter::down	(	const BSPTree::Plane &	plane,
		Direction	direction
	)		`[protected, virtual]`

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 498 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;
}

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 511 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 );
}

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

Get handle for current leaf.

Definition at line 268 of file BSPTree.hpp.

    { return mStack.back(); }

ErrorCode moab::BSPTreeIter::initialize	(	BSPTree *	tool,
		EntityHandle	root,
		const double *	point = `0`
	)		`[protected, virtual]`

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 419 of file BSPTree.cpp.

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

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 1418 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;
}

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 527 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();
}

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 535 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;
}

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 549 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();
}

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 446 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;
}

ErrorCode moab::BSPTreeIter::step ( ) [inline]

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

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 285 of file BSPTree.hpp.

{ return step(RIGHT); }

ErrorCode moab::BSPTreeIter::step_to_first_leaf ( Direction direction ) [protected, virtual]

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 430 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;
}

BSPTree* moab::BSPTreeIter::tool ( ) const [inline]

Definition at line 264 of file BSPTree.hpp.

    { return treeTool; }

ErrorCode moab::BSPTreeIter::up ( ) [protected, virtual]

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 490 of file BSPTree.cpp.

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

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

Get volume of leaf polyhedron.

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 520 of file BSPTree.cpp.

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

Friends And Related Function Documentation

friend class BSPTree [friend]

Definition at line 241 of file BSPTree.hpp.

Member Data Documentation

std::vector<EntityHandle> moab::BSPTreeIter::childVect [mutable, protected]

Definition at line 247 of file BSPTree.hpp.

std::vector<EntityHandle> moab::BSPTreeIter::mStack [protected]

Definition at line 246 of file BSPTree.hpp.

BSPTree* moab::BSPTreeIter::treeTool [private]

Definition at line 243 of file BSPTree.hpp.

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

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation