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.
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 252 of file BSPTree.hpp.

Member Enumeration Documentation

enum moab::BSPTreeIter::Direction

Enumerator:

LEFT
RIGHT

Definition at line 255 of file BSPTree.hpp.

    {
        LEFT  = 0,
        RIGHT = 1
    };

Constructor & Destructor Documentation

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

Definition at line 278 of file BSPTree.hpp.

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

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

Definition at line 279 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: stepping past the start of the tree will invalidate the iterator. Calling step() will not work.

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 317 of file BSPTree.hpp.

References LEFT, and step().

Referenced by test_iterator().

    {
        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 512 of file BSPTree.cpp.

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 test_leaf_polyhedron(), and volume().

{
    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 293 of file BSPTree.hpp.

References mStack.

Referenced by moab::BSPTree::merge_leaf(), test_box_iterator(), test_box_tree_create(), test_iterator(), test_merge_leaf(), and test_tree_create().

    {
        return mStack.size();
    }

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

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 449 of file BSPTree.cpp.

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

{
    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 460 of file BSPTree.cpp.

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

Referenced by test_box_iterator(), test_box_tree_create(), test_iterator(), test_leaf_containing_point_bounded_tree(), test_leaf_containing_point_unbounded_tree(), test_merge_leaf(), and test_tree_create().

{
    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 287 of file BSPTree.hpp.

References mStack.

Referenced by build_tree(), moab::BSPTreeBoxIter::get_neighbors(), is_sibling(), moab::BSPTree::leaf_containing_point(), moab::BSPTree::merge_leaf(), sibling_is_forward(), moab::BSPTree::split_leaf(), test_box_iter_neighbors(), test_box_iterator(), test_box_tree_create(), test_iterator(), test_leaf_containing_point_bounded_tree(), test_leaf_containing_point_unbounded_tree(), test_leaf_polyhedron(), test_merge_leaf(), and test_tree_create().

    {
        return mStack.back();
    }

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

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 374 of file BSPTree.cpp.

References MB_SUCCESS, mStack, and treeTool.

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

{
    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 1338 of file BSPTree.cpp.

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

Referenced by test_leaf_intersects_ray_common().

{
    // 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 476 of file BSPTree.cpp.

References handle(), and mStack.

{
    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 483 of file BSPTree.cpp.

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

{
    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 497 of file BSPTree.cpp.

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

{
    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 398 of file BSPTree.cpp.

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

Referenced by build_tree(), test_iterator(), test_leaf_containing_point_bounded_tree(), test_leaf_containing_point_unbounded_tree(), test_leaf_intersects_ray_common(), test_leaf_polyhedron(), test_leaf_volume(), and test_tree_create().

{
    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: stepping past the end of the tree will invalidate the iterator. Calling back() will not work.

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 308 of file BSPTree.hpp.

References RIGHT.

Referenced by back().

    {
        return step( RIGHT );
    }

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

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 382 of file BSPTree.cpp.

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

{
    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 281 of file BSPTree.hpp.

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(), test_box_iterator(), test_box_tree_create(), test_iterator(), test_tree_create(), and moab::BSPTreeBoxIter::up().

    {
        return treeTool;
    }

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

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 442 of file BSPTree.cpp.

References MB_ENTITY_NOT_FOUND, MB_SUCCESS, and mStack.

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

{
    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 469 of file BSPTree.cpp.

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

Referenced by test_leaf_volume().

{
    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 262 of file BSPTree.hpp.

Member Data Documentation

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

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

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

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

Definition at line 264 of file BSPTree.hpp.

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

List of all members.

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