Mesh Oriented datABase  (version 5.4.1)
Array-based unstructured mesh datastructure
moab::AdaptiveKDTreeIter Class Reference

Iterate over leaves of an adaptive kD-tree. More...

#include <AdaptiveKDTree.hpp>

+ Collaboration diagram for moab::AdaptiveKDTreeIter:

Classes

struct  StackObj

Public Types

enum  Direction { LEFT = 0, RIGHT = 1 }

Public Member Functions

 AdaptiveKDTreeIter ()
ErrorCode initialize (AdaptiveKDTree *tool, EntityHandle root, const double box_min[3], const double box_max[3], Direction direction)
AdaptiveKDTreetool () const
EntityHandle handle () const
 Get handle for current leaf.
const double * box_min () const
 Get min corner of axis-aligned box for current leaf.
const double * box_max () const
 Get max corner of axis-aligned box for current leaf.
double volume () const
bool intersects (const AdaptiveKDTree::Plane &plane) const
 test if a plane intersects the leaf box
unsigned depth () const
 Get depth in tree. root is at depth of 1.
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.
ErrorCode step ()
 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.
ErrorCode back ()
 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.
ErrorCode sibling_side (AdaptiveKDTree::Axis &axis_out, bool &neg_out) const
 Return the side of the box bounding this tree node that is shared with the immediately adjacent sibling (the tree node that shares a common parent node with this node in the binary tree.)
ErrorCode get_neighbors (AdaptiveKDTree::Axis norm, bool neg, std::vector< AdaptiveKDTreeIter > &results, double epsilon=0.0) const
 Get adjacent leaf nodes on side indicated by norm and neg.
ErrorCode get_parent_split_plane (AdaptiveKDTree::Plane &plane) const
 Get split plane that separates this node from its immediate sibling.
bool is_sibling (const AdaptiveKDTreeIter &other_leaf) const
 Return true if thos node and the passed node share the same immediate parent.
bool is_sibling (EntityHandle other_leaf) const
 Return true if thos node and the passed node share the same immediate parent.
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.
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.

Private Types

enum  { BMIN = 0, BMAX = 1 }

Private Member Functions

ErrorCode step_to_first_leaf (Direction direction)
 Descend tree to left most leaf from current position No-op if at leaf.

Private Attributes

CartVect mBox [2]
 min and max corners of bounding box
AdaptiveKDTreetreeTool
 tool for tree
std::vector< StackObjmStack
 stack storing path through tree
std::vector< EntityHandlechildVect
 temporary storage of child handles

Friends

class AdaptiveKDTree

Detailed Description

Iterate over leaves of an adaptive kD-tree.

Definition at line 342 of file AdaptiveKDTree.hpp.


Member Enumeration Documentation

anonymous enum [private]
Enumerator:
BMIN 
BMAX 

Definition at line 360 of file AdaptiveKDTree.hpp.

    {
        BMIN = 0,
        BMAX = 1
    };  //!< indices into mBox and child list
Enumerator:
LEFT 
RIGHT 

Definition at line 345 of file AdaptiveKDTree.hpp.

    {
        LEFT  = 0,
        RIGHT = 1
    };

Constructor & Destructor Documentation

Definition at line 378 of file AdaptiveKDTree.hpp.

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

Member Function Documentation

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.

Definition at line 446 of file AdaptiveKDTree.hpp.

References LEFT, and step().

    {
        return step( LEFT );
    }
const double* moab::AdaptiveKDTreeIter::box_max ( ) const [inline]
const double* moab::AdaptiveKDTreeIter::box_min ( ) const [inline]
unsigned moab::AdaptiveKDTreeIter::depth ( ) const [inline]

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

Definition at line 422 of file AdaptiveKDTree.hpp.

References mStack.

Referenced by moab::AdaptiveKDTree::build_tree(), moab::AdaptiveKDTree::compute_depth(), moab::AdaptiveKDTree::merge_leaf(), and moab::AdaptiveKDTree::print().

    {
        return mStack.size();
    }
ErrorCode moab::AdaptiveKDTreeIter::get_neighbors ( AdaptiveKDTree::Axis  norm,
bool  neg,
std::vector< AdaptiveKDTreeIter > &  results,
double  epsilon = 0.0 
) const

Get adjacent leaf nodes on side indicated by norm and neg.

E.g. if norm == X and neg == true, then get neighbor(s) adjacent to the side of the box contained in the plane with normal to the X axis and with the x coordinate equal to the minimum x of the bounding box.

E.g. if norm == Y and neg == false, then get neighbor(s) adjacent to the side of the box with y = maximum y of bounding box.

Parameters:
normNormal vector for box side (X, Y, or Z)
negWhich of two planes with norm (true->smaller coord, false->larger coord)
resultsList to which to append results. This function does *not* clear existing values in list.
epsilonTolerance on overlap. A positive value E will result in nodes that are separated by as much as E to be considered touching. A negative value -E will cause leaves that do not overlap by at least E to be considered non-overlapping. Amongst other things, this value can be used to control whether or not leaves adjacent at only their edges or corners are returned.

Definition at line 578 of file AdaptiveKDTree.cpp.

References childVect, moab::AdaptiveKDTree::Plane::coord, moab::AdaptiveKDTreeIter::StackObj::coord, moab::AdaptiveKDTreeIter::StackObj::entity, ErrorCode, MB_SUCCESS, mBox, mStack, and moab::AdaptiveKDTree::Plane::norm.

{
    StackObj node, parent;
    ErrorCode rval;
    AdaptiveKDTree::Plane plane;
    int child_idx;

    // Find tree node at which the specified side of the box
    // for this node was created.
    AdaptiveKDTreeIter iter( *this );  // temporary iterator (don't modify *this)
    node = iter.mStack.back();
    iter.mStack.pop_back();
    for( ;; )
    {
        // reached the root - original node was on boundary (no neighbors)
        if( iter.mStack.empty() ) return MB_SUCCESS;

        // get parent node data
        parent = iter.mStack.back();
        iter.childVect.clear();
        rval = treeTool->moab()->get_child_meshsets( parent.entity, iter.childVect );
        if( MB_SUCCESS != rval ) return rval;
        rval = treeTool->get_split_plane( parent.entity, plane );
        if( MB_SUCCESS != rval ) return rval;

        child_idx = iter.childVect[0] == node.entity ? 0 : 1;
        assert( iter.childVect[child_idx] == node.entity );

        // if we found the split plane for the desired side
        // push neighbor on stack and stop
        if( plane.norm == norm && (int)neg == child_idx )
        {
            // change from box of previous child to box of parent
            iter.mBox[1 - child_idx][plane.norm] = node.coord;
            // push other child of parent onto stack
            node.entity = iter.childVect[1 - child_idx];
            node.coord  = iter.mBox[child_idx][plane.norm];
            iter.mStack.push_back( node );
            // change from parent box to box of new child
            iter.mBox[child_idx][plane.norm] = plane.coord;
            break;
        }

        // continue up the tree
        iter.mBox[1 - child_idx][plane.norm] = node.coord;
        node                                 = parent;
        iter.mStack.pop_back();
    }

    // now move down tree, searching for adjacent boxes
    std::vector< AdaptiveKDTreeIter > list;
    // loop over all potential paths to neighbors (until list is empty)
    for( ;; )
    {
        // follow a single path to a leaf, append any other potential
        // paths to neighbors to 'list'
        node = iter.mStack.back();
        for( ;; )
        {
            iter.childVect.clear();
            rval = treeTool->moab()->get_child_meshsets( node.entity, iter.childVect );
            if( MB_SUCCESS != rval ) return rval;

            // if leaf
            if( iter.childVect.empty() )
            {
                results.push_back( iter );
                break;
            }

            rval = treeTool->get_split_plane( node.entity, plane );
            if( MB_SUCCESS != rval ) return rval;

            // if split parallel to side
            if( plane.norm == norm )
            {
                // continue with whichever child is on the correct side of the split
                node.entity = iter.childVect[neg];
                node.coord  = iter.mBox[1 - neg][plane.norm];
                iter.mStack.push_back( node );
                iter.mBox[1 - neg][plane.norm] = plane.coord;
            }
            // if left child is adjacent
            else if( this->mBox[BMIN][plane.norm] - plane.coord <= epsilon )
            {
                // if right child is also adjacent, add to list
                if( plane.coord - this->mBox[BMAX][plane.norm] <= epsilon )
                {
                    list.push_back( iter );
                    list.back().mStack.push_back( StackObj( iter.childVect[1], iter.mBox[BMIN][plane.norm] ) );
                    list.back().mBox[BMIN][plane.norm] = plane.coord;
                }
                // continue with left child
                node.entity = iter.childVect[0];
                node.coord  = iter.mBox[BMAX][plane.norm];
                iter.mStack.push_back( node );
                iter.mBox[BMAX][plane.norm] = plane.coord;
            }
            // right child is adjacent
            else
            {
                // if left child is not adjacent, right must be or something
                // is really messed up.
                assert( plane.coord - this->mBox[BMAX][plane.norm] <= epsilon );
                // continue with left child
                node.entity = iter.childVect[1];
                node.coord  = iter.mBox[BMIN][plane.norm];
                iter.mStack.push_back( node );
                iter.mBox[BMIN][plane.norm] = plane.coord;
            }
        }

        if( list.empty() ) break;

        iter = list.back();
        list.pop_back();
    }

    return MB_SUCCESS;
}

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

Definition at line 722 of file AdaptiveKDTree.cpp.

References MB_ENTITY_NOT_FOUND.

{
    if( mStack.size() < 2 )  // at tree root
        return MB_ENTITY_NOT_FOUND;

    EntityHandle parent = mStack[mStack.size() - 2].entity;
    return tool()->get_split_plane( parent, plane );
}
ErrorCode moab::AdaptiveKDTreeIter::initialize ( AdaptiveKDTree tool,
EntityHandle  root,
const double  box_min[3],
const double  box_max[3],
Direction  direction 
)

Definition at line 475 of file AdaptiveKDTree.cpp.

Referenced by moab::AdaptiveKDTree::build_tree(), moab::AdaptiveKDTree::get_last_iterator(), and moab::AdaptiveKDTree::get_sub_tree_iterator().

{
    mStack.clear();
    treeTool      = ttool;
    mBox[BMIN][0] = bmin[0];
    mBox[BMIN][1] = bmin[1];
    mBox[BMIN][2] = bmin[2];
    mBox[BMAX][0] = bmax[0];
    mBox[BMAX][1] = bmax[1];
    mBox[BMAX][2] = bmax[2];
    mStack.push_back( StackObj( root, 0 ) );
    return step_to_first_leaf( direction );
}
bool moab::AdaptiveKDTreeIter::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.

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.

Definition at line 767 of file AdaptiveKDTree.cpp.

References box_max(), box_min(), and moab::GeomUtil::ray_box_intersect().

{
    treeTool->treeStats.traversalLeafObjectTests++;
    return GeomUtil::ray_box_intersect( CartVect( box_min() ), CartVect( box_max() ), CartVect( ray_point ),
                                        CartVect( ray_vect ), t_enter, t_exit );
}
bool moab::AdaptiveKDTreeIter::intersects ( const AdaptiveKDTree::Plane plane) const [inline]

test if a plane intersects the leaf box

Definition at line 416 of file AdaptiveKDTree.hpp.

References BMAX, BMIN, moab::AdaptiveKDTree::Plane::coord, mBox, and moab::AdaptiveKDTree::Plane::norm.

    {
        return mBox[BMIN][plane.norm] <= plane.coord && mBox[BMAX][plane.norm] >= plane.coord;
    }
bool moab::AdaptiveKDTreeIter::is_sibling ( const AdaptiveKDTreeIter other_leaf) const

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

Definition at line 731 of file AdaptiveKDTree.cpp.

References handle(), and mStack.

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

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

Definition at line 738 of file AdaptiveKDTree.cpp.

References ErrorCode, and MB_SUCCESS.

{
    if( mStack.size() < 2 || other_leaf == handle() ) return false;
    EntityHandle parent = mStack[mStack.size() - 2].entity;
    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 752 of file AdaptiveKDTree.cpp.

References ErrorCode, and MB_SUCCESS.

{
    if( mStack.size() < 2 )  // if root
        return false;
    EntityHandle parent = mStack[mStack.size() - 2].entity;
    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::AdaptiveKDTreeIter::sibling_side ( AdaptiveKDTree::Axis axis_out,
bool &  neg_out 
) const

Return the side of the box bounding this tree node that is shared with the immediately adjacent sibling (the tree node that shares a common parent node with this node in the binary tree.)

Parameters:
axis_outThe principal axis orthogonal to the side of the box
neg_outtrue if the side of the box is toward the decreasing direction of the principal axis indicated by axis_out, false if it is toward the increasing direction.
Returns:
MB_ENTITY_NOT FOUND if root node. MB_FAILURE if internal error. MB_SUCCESS otherwise.

Definition at line 702 of file AdaptiveKDTree.cpp.

References ErrorCode, MB_ENTITY_NOT_FOUND, MB_SUCCESS, and moab::AdaptiveKDTree::Plane::norm.

{
    if( mStack.size() < 2 )  // at tree root
        return MB_ENTITY_NOT_FOUND;

    EntityHandle parent = mStack[mStack.size() - 2].entity;
    AdaptiveKDTree::Plane plane;
    ErrorCode rval = tool()->get_split_plane( parent, plane );
    if( MB_SUCCESS != rval ) return MB_FAILURE;

    childVect.clear();
    rval = tool()->moab()->get_child_meshsets( parent, childVect );
    if( MB_SUCCESS != rval || childVect.size() != 2 ) return MB_FAILURE;

    axis_out = static_cast< AdaptiveKDTree::Axis >( plane.norm );
    neg_out  = ( childVect[1] == handle() );
    assert( childVect[neg_out] == handle() );
    return MB_SUCCESS;
}

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.

Definition at line 520 of file AdaptiveKDTree.cpp.

References moab::AdaptiveKDTree::Plane::coord, moab::AdaptiveKDTreeIter::StackObj::coord, moab::AdaptiveKDTreeIter::StackObj::entity, ErrorCode, MB_ENTITY_NOT_FOUND, MB_SUCCESS, and moab::AdaptiveKDTree::Plane::norm.

Referenced by moab::AdaptiveKDTree::build_tree(), moab::AdaptiveKDTree::compute_depth(), moab::MergeMesh::find_merged_to(), and moab::AdaptiveKDTree::print().

{
    StackObj node, parent;
    ErrorCode rval;
    AdaptiveKDTree::Plane plane;
    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();
    treeTool->treeStats.nodesVisited++;
    if( mStack.empty() ) treeTool->treeStats.leavesVisited++;

    while( !mStack.empty() )
    {
        // Get data for parent entity
        parent = mStack.back();
        childVect.clear();
        rval = treeTool->moab()->get_child_meshsets( parent.entity, childVect );
        if( MB_SUCCESS != rval ) return rval;
        rval = treeTool->get_split_plane( parent.entity, plane );
        if( MB_SUCCESS != rval ) return rval;

        // If we're at the left child
        if( childVect[opposite] == node.entity )
        {
            // change from box of left child to box of parent
            mBox[direction][plane.norm] = node.coord;
            // push right child on stack
            node.entity = childVect[direction];
            treeTool->treeStats.nodesVisited++;  // changed node
            node.coord = mBox[opposite][plane.norm];
            mStack.push_back( node );
            // change from box of parent to box of right child
            mBox[opposite][plane.norm] = plane.coord;
            // 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.entity );
        mBox[opposite][plane.norm] = node.coord;
        node                       = parent;
        treeTool->treeStats.nodesVisited++;
        mStack.pop_back();
    }

    return MB_ENTITY_NOT_FOUND;
}

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.

Definition at line 437 of file AdaptiveKDTree.hpp.

References RIGHT.

Referenced by back().

    {
        return step( RIGHT );
    }

Descend tree to left most leaf from current position No-op if at leaf.

Definition at line 493 of file AdaptiveKDTree.cpp.

References moab::AdaptiveKDTree::Plane::coord, ErrorCode, MB_SUCCESS, and moab::AdaptiveKDTree::Plane::norm.

Referenced by moab::AdaptiveKDTree::compute_depth(), and moab::AdaptiveKDTree::split_leaf().

{
    ErrorCode rval;
    AdaptiveKDTree::Plane plane;
    const Direction opposite = static_cast< Direction >( 1 - direction );

    for( ;; )
    {
        childVect.clear();
        treeTool->treeStats.nodesVisited++;  // not sure whether this is the visit or the push_back below
        rval = treeTool->moab()->get_child_meshsets( mStack.back().entity, childVect );
        if( MB_SUCCESS != rval ) return rval;
        if( childVect.empty() )
        {  // leaf
            treeTool->treeStats.leavesVisited++;
            break;
        }

        rval = treeTool->get_split_plane( mStack.back().entity, plane );
        if( MB_SUCCESS != rval ) return rval;

        mStack.push_back( StackObj( childVect[direction], mBox[opposite][plane.norm] ) );
        mBox[opposite][plane.norm] = plane.coord;
    }
    return MB_SUCCESS;
}
double moab::AdaptiveKDTreeIter::volume ( ) const [inline]

Definition at line 409 of file AdaptiveKDTree.hpp.

References BMAX, BMIN, and mBox.

    {
        return ( mBox[BMAX][0] - mBox[BMIN][0] ) * ( mBox[BMAX][1] - mBox[BMIN][1] ) *
               ( mBox[BMAX][2] - mBox[BMIN][2] );
    }

Friends And Related Function Documentation

friend class AdaptiveKDTree [friend]

Definition at line 375 of file AdaptiveKDTree.hpp.


Member Data Documentation

std::vector< EntityHandle > moab::AdaptiveKDTreeIter::childVect [mutable, private]

temporary storage of child handles

Definition at line 369 of file AdaptiveKDTree.hpp.

Referenced by get_neighbors(), moab::AdaptiveKDTree::merge_leaf(), and moab::AdaptiveKDTree::point_search().

std::vector< StackObj > moab::AdaptiveKDTreeIter::mStack [private]

stack storing path through tree

Definition at line 368 of file AdaptiveKDTree.hpp.

Referenced by depth(), get_neighbors(), handle(), is_sibling(), moab::AdaptiveKDTree::merge_leaf(), and moab::AdaptiveKDTree::point_search().

tool for tree

Definition at line 367 of file AdaptiveKDTree.hpp.

Referenced by moab::AdaptiveKDTree::point_search(), 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