MOAB: Mesh Oriented datABase  (version 5.4.1)
moab::BSPTree Class Reference

BSP tree, for sorting and searching entities spatially. More...

#include <BSPTree.hpp>

+ Collaboration diagram for moab::BSPTree:

Classes

struct  Plane
 struct to store a plane More...

Public Types

enum  Axis { X = 0, Y = 1, Z = 2 }
 Enumerate split plane directions. More...

Public Member Functions

 BSPTree (Interface *iface, const char *tagname=0, unsigned meshset_creation_flags=MESHSET_SET)
 BSPTree (Interface *iface, bool destroy_created_trees, const char *tagname=0, unsigned meshset_creation_flags=MESHSET_SET)
 ~BSPTree ()
ErrorCode get_split_plane (EntityHandle node, Plane &plane)
 Get split plane for tree node.
ErrorCode set_split_plane (EntityHandle node, const Plane &plane)
 Set split plane for tree node.
ErrorCode get_tree_box (EntityHandle root_node, double corner_coords[8][3])
 Get bounding box for entire tree.
ErrorCode get_tree_box (EntityHandle root_node, double corner_coords[24])
 Get bounding box for entire tree.
ErrorCode set_tree_box (EntityHandle root_node, const double box_min[3], const double box_max[3])
 Set bounding box for entire tree.
ErrorCode set_tree_box (EntityHandle root_node, const double corner_coords[8][3])
ErrorCode create_tree (const double box_min[3], const double box_max[3], EntityHandle &root_handle)
 Create tree root node.
ErrorCode create_tree (const double corner_coords[8][3], EntityHandle &root_handle)
ErrorCode create_tree (EntityHandle &root_handle)
 Create tree root node.
ErrorCode find_all_trees (Range &results)
 Find all tree roots.
ErrorCode delete_tree (EntityHandle root_handle)
 Destroy a tree.
Interfacemoab ()
ErrorCode get_tree_iterator (EntityHandle tree_root, BSPTreeIter &result)
 Get iterator for tree.
ErrorCode get_tree_end_iterator (EntityHandle tree_root, BSPTreeIter &result)
 Get iterator at right-most ('last') leaf.
ErrorCode split_leaf (BSPTreeIter &leaf, Plane plane)
ErrorCode split_leaf (BSPTreeIter &leaf, Plane plane, EntityHandle &left_child, EntityHandle &right_child)
ErrorCode split_leaf (BSPTreeIter &leaf, Plane plane, const Range &left_entities, const Range &right_entities)
ErrorCode split_leaf (BSPTreeIter &leaf, Plane plane, const std::vector< EntityHandle > &left_entities, const std::vector< EntityHandle > &right_entities)
ErrorCode merge_leaf (BSPTreeIter &iter)
ErrorCode leaf_containing_point (EntityHandle tree_root, const double point[3], EntityHandle &leaf_out)
ErrorCode leaf_containing_point (EntityHandle tree_root, const double xyz[3], BSPTreeIter &result)

Static Public Member Functions

static double epsilon ()

Private Member Functions

ErrorCode init_tags (const char *tagname=0)

Private Attributes

InterfacembInstance
Tag planeTag
Tag rootTag
unsigned meshSetFlags
bool cleanUpTrees
std::vector< EntityHandlecreatedTrees

Detailed Description

BSP tree, for sorting and searching entities spatially.

Definition at line 42 of file BSPTree.hpp.


Member Enumeration Documentation

Enumerate split plane directions.

Enumerator:
X 
Y 
Z 

Definition at line 69 of file BSPTree.hpp.

    {
        X = 0,
        Y = 1,
        Z = 2
    };

Constructor & Destructor Documentation

moab::BSPTree::BSPTree ( Interface iface,
const char *  tagname = 0,
unsigned  meshset_creation_flags = MESHSET_SET 
)

Definition at line 109 of file BSPTree.cpp.

References init_tags().

    : mbInstance( mb ), meshSetFlags( set_flags ), cleanUpTrees( false )
{
    init_tags( tagname );
}
moab::BSPTree::BSPTree ( Interface iface,
bool  destroy_created_trees,
const char *  tagname = 0,
unsigned  meshset_creation_flags = MESHSET_SET 
)

Definition at line 115 of file BSPTree.cpp.

References init_tags().

    : mbInstance( mb ), meshSetFlags( set_flags ), cleanUpTrees( destroy_created_trees )
{
    init_tags( tagname );
}

Definition at line 121 of file BSPTree.cpp.

References cleanUpTrees, createdTrees, delete_tree(), ErrorCode, MB_SUCCESS, moab(), rootTag, moab::Interface::tag_get_by_ptr(), and tree.

{
    if( !cleanUpTrees ) return;

    while( !createdTrees.empty() )
    {
        EntityHandle tree = createdTrees.back();
        // make sure this is a tree (rather than some other, stale handle)
        const void* data_ptr = 0;
        ErrorCode rval       = moab()->tag_get_by_ptr( rootTag, &tree, 1, &data_ptr );
        if( MB_SUCCESS == rval ) rval = delete_tree( tree );
        if( MB_SUCCESS != rval ) createdTrees.pop_back();
    }
}

Member Function Documentation

ErrorCode moab::BSPTree::create_tree ( const double  corner_coords[8][3],
EntityHandle root_handle 
)

Definition at line 186 of file BSPTree.cpp.

References moab::Interface::create_meshset(), createdTrees, moab::Interface::delete_entities(), ErrorCode, MB_SUCCESS, meshSetFlags, moab(), and set_tree_box().

{
    ErrorCode rval = moab()->create_meshset( meshSetFlags, root_handle );
    if( MB_SUCCESS != rval ) return rval;

    rval = set_tree_box( root_handle, corners );
    if( MB_SUCCESS != rval )
    {
        moab()->delete_entities( &root_handle, 1 );
        root_handle = 0;
        return rval;
    }

    createdTrees.push_back( root_handle );
    return MB_SUCCESS;
}

Create tree root node.

Definition at line 179 of file BSPTree.cpp.

References create_tree().

{
    const double min[3] = { -HUGE_VAL, -HUGE_VAL, -HUGE_VAL };
    const double max[3] = { HUGE_VAL, HUGE_VAL, HUGE_VAL };
    return create_tree( min, max, root_handle );
}

Destroy a tree.

Definition at line 210 of file BSPTree.cpp.

References children, createdTrees, moab::Interface::delete_entities(), ErrorCode, moab::Interface::get_child_meshsets(), MB_SUCCESS, moab(), rootTag, and moab::Interface::tag_delete_data().

Referenced by ~BSPTree().

{
    ErrorCode rval;

    std::vector< EntityHandle > children, dead_sets, current_sets;
    current_sets.push_back( root_handle );
    while( !current_sets.empty() )
    {
        EntityHandle set = current_sets.back();
        current_sets.pop_back();
        dead_sets.push_back( set );
        rval = moab()->get_child_meshsets( set, children );
        if( MB_SUCCESS != rval ) return rval;
        std::copy( children.begin(), children.end(), std::back_inserter( current_sets ) );
        children.clear();
    }

    rval = moab()->tag_delete_data( rootTag, &root_handle, 1 );
    if( MB_SUCCESS != rval ) return rval;

    createdTrees.erase( std::remove( createdTrees.begin(), createdTrees.end(), root_handle ), createdTrees.end() );
    return moab()->delete_entities( &dead_sets[0], dead_sets.size() );
}
static double moab::BSPTree::epsilon ( ) [inline, static]

Definition at line 54 of file BSPTree.hpp.

Referenced by moab::BSPTreeBoxIter::side_on_plane(), and moab::BSPTreeBoxIter::splits().

    {
        return 1e-6;
    }

Find all tree roots.

Definition at line 234 of file BSPTree.cpp.

References moab::Interface::get_entities_by_type_and_tag(), MBENTITYSET, moab(), and rootTag.

{
    return moab()->get_entities_by_type_and_tag( 0, MBENTITYSET, &rootTag, 0, 1, results );
}
ErrorCode moab::BSPTree::get_tree_box ( EntityHandle  root_node,
double  corner_coords[8][3] 
)

Get bounding box for entire tree.

Definition at line 169 of file BSPTree.cpp.

References moab(), rootTag, and moab::Interface::tag_get_data().

Referenced by moab::BSPTreeIter::calculate_polyhedron(), moab::BSPTreeBoxIter::initialize(), and moab::BSPTreeIter::intersect_ray().

{
    return moab()->tag_get_data( rootTag, &root_handle, 1, corners );
}
ErrorCode moab::BSPTree::get_tree_box ( EntityHandle  root_node,
double  corner_coords[24] 
)

Get bounding box for entire tree.

Definition at line 174 of file BSPTree.cpp.

References moab(), rootTag, and moab::Interface::tag_get_data().

{
    return moab()->tag_get_data( rootTag, &root_handle, 1, corners );
}

Get iterator at right-most ('last') leaf.

Definition at line 246 of file BSPTree.cpp.

References ErrorCode, moab::BSPTreeIter::initialize(), MB_SUCCESS, moab::BSPTreeIter::RIGHT, and moab::BSPTreeIter::step_to_first_leaf().

Referenced by test_box_iterator(), and test_iterator().

{
    ErrorCode rval = iter.initialize( this, root );
    if( MB_SUCCESS != rval ) return rval;
    return iter.step_to_first_leaf( BSPTreeIter::RIGHT );
}
ErrorCode moab::BSPTree::init_tags ( const char *  tagname = 0) [private]

Definition at line 93 of file BSPTree.cpp.

References ErrorCode, MB_BSP_TREE_DEFAULT_TAG_NAME, MB_SUCCESS, MB_TAG_CREAT, MB_TAG_DENSE, MB_TAG_SPARSE, MB_TYPE_DOUBLE, moab(), planeTag, rootTag, and moab::Interface::tag_get_handle().

Referenced by BSPTree().

{
    if( !tagname ) tagname = MB_BSP_TREE_DEFAULT_TAG_NAME;

    std::string rootname( tagname );
    rootname += "_box";

    ErrorCode rval = moab()->tag_get_handle( tagname, 4, MB_TYPE_DOUBLE, planeTag, MB_TAG_CREAT | MB_TAG_DENSE );
    if( MB_SUCCESS != rval )
        planeTag = 0;
    else
        rval = moab()->tag_get_handle( rootname.c_str(), 24, MB_TYPE_DOUBLE, rootTag, MB_TAG_CREAT | MB_TAG_SPARSE );
    if( MB_SUCCESS != rval ) rootTag = 0;
    return rval;
}
ErrorCode moab::BSPTree::leaf_containing_point ( EntityHandle  tree_root,
const double  point[3],
EntityHandle leaf_out 
)

Get leaf containing input position.

Does not take into account global bounding box of tree.

  • Therefore there is always one leaf containing the point.
  • If caller wants to account for global bounding box, then caller can test against that box and not call this method at all if the point is outside the box, as there is no leaf containing the point in that case.

Definition at line 1135 of file BSPTree.cpp.

References moab::BSPTree::Plane::above(), children, ErrorCode, moab::Interface::get_child_meshsets(), get_split_plane(), MB_SUCCESS, and moab().

Referenced by build_tree(), test_leaf_containing_point_bounded_tree(), and test_leaf_containing_point_unbounded_tree().

{
    std::vector< EntityHandle > children;
    Plane plane;
    EntityHandle node = tree_root;
    ErrorCode rval    = moab()->get_child_meshsets( node, children );
    if( MB_SUCCESS != rval ) return rval;
    while( !children.empty() )
    {
        rval = get_split_plane( node, plane );
        if( MB_SUCCESS != rval ) return rval;

        node = children[plane.above( point )];
        children.clear();
        rval = moab()->get_child_meshsets( node, children );
        if( MB_SUCCESS != rval ) return rval;
    }
    leaf_out = node;
    return MB_SUCCESS;
}
ErrorCode moab::BSPTree::leaf_containing_point ( EntityHandle  tree_root,
const double  xyz[3],
BSPTreeIter result 
)

Get iterator at leaf containing input position.

Returns MB_ENTITY_NOT_FOUND if point is not within bounding box of tree.

Definition at line 1156 of file BSPTree.cpp.

References moab::BSPTree::Plane::above(), moab::BSPTreeIter::childVect, moab::BSPTreeIter::down(), ErrorCode, moab::Interface::get_child_meshsets(), get_split_plane(), moab::BSPTreeIter::handle(), moab::BSPTreeIter::initialize(), MB_SUCCESS, and moab().

{
    ErrorCode rval;

    rval = iter.initialize( this, root, point );
    if( MB_SUCCESS != rval ) return rval;

    for( ;; )
    {
        iter.childVect.clear();
        rval = moab()->get_child_meshsets( iter.handle(), iter.childVect );
        if( MB_SUCCESS != rval || iter.childVect.empty() ) return rval;

        Plane plane;
        rval = get_split_plane( iter.handle(), plane );
        if( MB_SUCCESS != rval ) return rval;

        rval = iter.down( plane, ( BSPTreeIter::Direction )( plane.above( point ) ) );
        if( MB_SUCCESS != rval ) return rval;
    }
}

Merge the leaf pointed to by the current iterator with it's sibling. If the sibling is not a leaf, multiple merges may be done.

Definition at line 325 of file BSPTree.cpp.

References moab::Interface::add_entities(), moab::Range::back(), moab::BSPTreeIter::childVect, moab::Range::clear(), moab::Interface::delete_entities(), moab::BSPTreeIter::depth(), ErrorCode, moab::Interface::get_child_meshsets(), moab::Interface::get_entities_by_handle(), moab::BSPTreeIter::handle(), MB_CHK_ERR, MB_SUCCESS, moab(), moab::Interface::remove_child_meshset(), and moab::BSPTreeIter::up().

Referenced by test_merge_leaf().

{
    ErrorCode rval;
    if( iter.depth() == 1 )  // at root
        return MB_FAILURE;

    // Move iter to parent
    iter.up();

    // Get sets to merge
    EntityHandle parent = iter.handle();
    iter.childVect.clear();
    rval = moab()->get_child_meshsets( parent, iter.childVect );
    if( MB_SUCCESS != rval ) return rval;

    // Remove child links
    moab()->remove_child_meshset( parent, iter.childVect[0] );
    moab()->remove_child_meshset( parent, iter.childVect[1] );
    std::vector< EntityHandle > stack( iter.childVect );

    // Get all entities from children and put them in parent
    Range range;
    while( !stack.empty() )
    {
        EntityHandle h = stack.back();
        stack.pop_back();
        range.clear();
        rval = moab()->get_entities_by_handle( h, range );
        if( MB_SUCCESS != rval ) return rval;
        rval = moab()->add_entities( parent, range );
        if( MB_SUCCESS != rval ) return rval;

        iter.childVect.clear();
        rval = moab()->get_child_meshsets( h, iter.childVect );MB_CHK_ERR( rval );
        if( !iter.childVect.empty() )
        {
            moab()->remove_child_meshset( h, iter.childVect[0] );
            moab()->remove_child_meshset( h, iter.childVect[1] );
            stack.push_back( iter.childVect[0] );
            stack.push_back( iter.childVect[1] );
        }

        rval = moab()->delete_entities( &h, 1 );
        if( MB_SUCCESS != rval ) return rval;
    }

    return MB_SUCCESS;
}

Set split plane for tree node.

Definition at line 136 of file BSPTree.cpp.

References moab::BSPTree::Plane::coeff, moab::Util::is_finite(), moab(), moab::BSPTree::Plane::norm, planeTag, and moab::Interface::tag_set_data().

Referenced by split_leaf().

{
    // check for unit-length normal
    const double lensqr = p.norm[0] * p.norm[0] + p.norm[1] * p.norm[1] + p.norm[2] * p.norm[2];
    if( fabs( lensqr - 1.0 ) < std::numeric_limits< double >::epsilon() )
        return moab()->tag_set_data( planeTag, &node, 1, &p );

    const double inv_len = 1.0 / sqrt( lensqr );
    Plane p2( p );
    p2.norm[0] *= inv_len;
    p2.norm[1] *= inv_len;
    p2.norm[2] *= inv_len;
    p2.coeff *= inv_len;

    // check for zero-length normal
    if( !Util::is_finite( p2.norm[0] + p2.norm[1] + p2.norm[2] + p2.coeff ) ) return MB_FAILURE;

    // store plane
    return moab()->tag_set_data( planeTag, &node, 1, &p2 );
}
ErrorCode moab::BSPTree::set_tree_box ( EntityHandle  root_node,
const double  box_min[3],
const double  box_max[3] 
)

Set bounding box for entire tree.

Definition at line 157 of file BSPTree.cpp.

References moab::corners_from_box().

Referenced by create_tree().

{
    double corners[8][3];
    corners_from_box( box_min, box_max, corners );
    return set_tree_box( root_handle, corners );
}
ErrorCode moab::BSPTree::set_tree_box ( EntityHandle  root_node,
const double  corner_coords[8][3] 
)

Definition at line 164 of file BSPTree.cpp.

References moab(), rootTag, and moab::Interface::tag_set_data().

{
    return moab()->tag_set_data( rootTag, &root_handle, 1, corners );
}
ErrorCode moab::BSPTree::split_leaf ( BSPTreeIter leaf,
Plane  plane,
EntityHandle left_child,
EntityHandle right_child 
)

Split leaf of tree Updates iterator location to point to first new leaf node.

Definition at line 253 of file BSPTree.cpp.

References moab::Interface::add_child_meshset(), children, moab::Interface::create_meshset(), moab::Interface::delete_entities(), ErrorCode, moab::BSPTreeIter::handle(), moab::BSPTreeIter::LEFT, MB_SUCCESS, meshSetFlags, moab(), set_split_plane(), and moab::BSPTreeIter::step_to_first_leaf().

{
    ErrorCode rval;

    rval = moab()->create_meshset( meshSetFlags, left );
    if( MB_SUCCESS != rval ) return rval;

    rval = moab()->create_meshset( meshSetFlags, right );
    if( MB_SUCCESS != rval )
    {
        moab()->delete_entities( &left, 1 );
        return rval;
    }

    if( MB_SUCCESS != set_split_plane( leaf.handle(), plane ) ||
        MB_SUCCESS != moab()->add_child_meshset( leaf.handle(), left ) ||
        MB_SUCCESS != moab()->add_child_meshset( leaf.handle(), right ) ||
        MB_SUCCESS != leaf.step_to_first_leaf( BSPTreeIter::LEFT ) )
    {
        EntityHandle children[] = { left, right };
        moab()->delete_entities( children, 2 );
        return MB_FAILURE;
    }

    return MB_SUCCESS;
}
ErrorCode moab::BSPTree::split_leaf ( BSPTreeIter leaf,
Plane  plane,
const Range left_entities,
const Range right_entities 
)

Split leaf of tree Updates iterator location to point to first new leaf node.

Definition at line 286 of file BSPTree.cpp.

References children, moab::Interface::delete_entities(), ErrorCode, moab::BSPTreeIter::handle(), MB_SUCCESS, moab(), moab::Interface::remove_child_meshset(), and split_leaf().

{
    EntityHandle left, right, parent = leaf.handle();
    ErrorCode rval = split_leaf( leaf, plane, left, right );
    if( MB_SUCCESS != rval ) return rval;

    if( MB_SUCCESS == moab()->add_entities( left, left_entities ) &&
        MB_SUCCESS == moab()->add_entities( right, right_entities ) &&
        MB_SUCCESS == moab()->clear_meshset( &parent, 1 ) )
        return MB_SUCCESS;

    moab()->remove_child_meshset( parent, left );
    moab()->remove_child_meshset( parent, right );
    EntityHandle children[] = { left, right };
    moab()->delete_entities( children, 2 );
    return MB_FAILURE;
}
ErrorCode moab::BSPTree::split_leaf ( BSPTreeIter leaf,
Plane  plane,
const std::vector< EntityHandle > &  left_entities,
const std::vector< EntityHandle > &  right_entities 
)

Split leaf of tree Updates iterator location to point to first new leaf node.

Definition at line 304 of file BSPTree.cpp.

References moab::Interface::add_entities(), children, moab::Interface::clear_meshset(), moab::Interface::delete_entities(), ErrorCode, moab::BSPTreeIter::handle(), MB_SUCCESS, moab(), moab::Interface::remove_child_meshset(), and split_leaf().

{
    EntityHandle left, right, parent = leaf.handle();
    ErrorCode rval = split_leaf( leaf, plane, left, right );
    if( MB_SUCCESS != rval ) return rval;

    if( MB_SUCCESS == moab()->add_entities( left, &left_entities[0], left_entities.size() ) &&
        MB_SUCCESS == moab()->add_entities( right, &right_entities[0], right_entities.size() ) &&
        MB_SUCCESS == moab()->clear_meshset( &parent, 1 ) )
        return MB_SUCCESS;

    moab()->remove_child_meshset( parent, left );
    moab()->remove_child_meshset( parent, right );
    EntityHandle children[] = { left, right };
    moab()->delete_entities( children, 2 );
    return MB_FAILURE;
}

Member Data Documentation

Definition at line 48 of file BSPTree.hpp.

Referenced by ~BSPTree().

std::vector< EntityHandle > moab::BSPTree::createdTrees [private]

Definition at line 49 of file BSPTree.hpp.

Referenced by create_tree(), delete_tree(), and ~BSPTree().

Definition at line 45 of file BSPTree.hpp.

Referenced by moab().

unsigned moab::BSPTree::meshSetFlags [private]

Definition at line 47 of file BSPTree.hpp.

Referenced by create_tree(), and split_leaf().

Definition at line 46 of file BSPTree.hpp.

Referenced by get_split_plane(), init_tags(), and set_split_plane().

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