MOAB: Mesh Oriented datABase  (version 5.3.1)
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.
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< EntityHandlemStack
std::vector< EntityHandlechildVect

Private Attributes

BSPTreetreeTool

Friends

class BSPTree

Detailed Description

Iterate over leaves of a BSPTree.

Definition at line 248 of file BSPTree.hpp.


Member Enumeration Documentation

Enumerator:
LEFT 
RIGHT 

Definition at line 251 of file BSPTree.hpp.

    {
        LEFT  = 0,
        RIGHT = 1
    };

Constructor & Destructor Documentation

Definition at line 274 of file BSPTree.hpp.

: treeTool( 0 ), childVect( 2 ) {}
virtual moab::BSPTreeIter::~BSPTreeIter ( ) [inline, virtual]

Definition at line 275 of file BSPTree.hpp.

{}

Member Function Documentation

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 313 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 510 of file BSPTree.cpp.

References moab::CartVect::array(), childVect, moab::BSPTree::Plane::coeff, corners, 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 289 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 447 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;
}

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

Definition at line 458 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 );
}
ErrorCode moab::BSPTreeIter::initialize ( BSPTree tool,
EntityHandle  root,
const double *  point = 0 
) [protected, virtual]

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 372 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_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 1327 of file BSPTree.cpp.

References corners, 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 474 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 481 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;
}

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 495 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 396 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;
}

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 304 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 380 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;
}
ErrorCode moab::BSPTreeIter::up ( ) [protected, virtual]

Reimplemented in moab::BSPTreeBoxIter.

Definition at line 440 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 467 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 258 of file BSPTree.hpp.


Member Data Documentation

Definition at line 260 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:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines