moab
Classes | Public Types | Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes
moab::BSPTree Class Reference

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

#include <BSPTree.hpp>

List of all members.

Classes

struct  Plane
 struct to store a plane More...

Public Types

enum  Axis { X = 0, Y = 1, Z = 2 }
 Enumeriate 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.
Interface * moab ()
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

Interface * mbInstance
Tag planeTag
Tag rootTag
unsigned meshSetFlags
bool cleanUpTrees
std::vector< EntityHandle > createdTrees

Detailed Description

BSP tree, for sorting and searching entities spatially.

Definition at line 41 of file BSPTree.hpp.

Member Enumeration Documentation

enum moab::BSPTree::Axis

Enumeriate split plane directions.

Enumerator:
X 
Y 
Z 

Definition at line 68 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 120 of file BSPTree.cpp.

  : 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 126 of file BSPTree.cpp.

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

Definition at line 133 of file BSPTree.cpp.

{
  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  box_min[3],
const double  box_max[3],
EntityHandle &  root_handle 
)

Create tree root node.

Definition at line 227 of file BSPTree.cpp.

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

Definition at line 208 of file BSPTree.cpp.

{
  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;
}
ErrorCode moab::BSPTree::create_tree ( EntityHandle &  root_handle)

Create tree root node.

Definition at line 201 of file BSPTree.cpp.

{
  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 );
}
ErrorCode moab::BSPTree::delete_tree ( EntityHandle  root_handle)

Destroy a tree.

Definition at line 236 of file BSPTree.cpp.

{
  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.

{ return 1e-6; }
ErrorCode moab::BSPTree::find_all_trees ( Range &  results)

Find all tree roots.

Definition at line 263 of file BSPTree.cpp.

{
  return moab()->get_entities_by_type_and_tag( 0, MBENTITYSET, 
                                               &rootTag, 0, 1,
                                               results );
}
ErrorCode moab::BSPTree::get_split_plane ( EntityHandle  node,
Plane &  plane 
) [inline]

Get split plane for tree node.

Definition at line 133 of file BSPTree.hpp.

    { return moab()->tag_get_data( planeTag, &node, 1, &plane ); }
ErrorCode moab::BSPTree::get_tree_box ( EntityHandle  root_node,
double  corner_coords[8][3] 
)

Get bounding box for entire tree.

Definition at line 189 of file BSPTree.cpp.

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

{
  return moab()->tag_get_data( rootTag, &root_handle, 1, corners );
}
ErrorCode moab::BSPTree::get_tree_end_iterator ( EntityHandle  tree_root,
BSPTreeIter &  result 
)

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

Definition at line 279 of file BSPTree.cpp.

{
  ErrorCode rval = iter.initialize( this, root );
  if (MB_SUCCESS != rval)
    return rval;
  return iter.step_to_first_leaf( BSPTreeIter::RIGHT );
}
ErrorCode moab::BSPTree::get_tree_iterator ( EntityHandle  tree_root,
BSPTreeIter &  result 
)

Get iterator for tree.

Definition at line 270 of file BSPTree.cpp.

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

Definition at line 102 of file BSPTree.cpp.

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

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

{
  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;
  }
}
ErrorCode moab::BSPTree::merge_leaf ( BSPTreeIter &  iter)

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

{
  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();
    moab()->get_child_meshsets( h, iter.childVect );
    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;
}
Interface* moab::BSPTree::moab ( ) [inline]

Definition at line 170 of file BSPTree.hpp.

{ return mbInstance; }
ErrorCode moab::BSPTree::set_split_plane ( EntityHandle  node,
const Plane &  plane 
)

Set split plane for tree node.

Definition at line 150 of file BSPTree.cpp.

{ 
    // 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 (!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 174 of file BSPTree.cpp.

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

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

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

Definition at line 317 of file BSPTree.cpp.

{
  EntityHandle left, right;
  return split_leaf( leaf, plane, left, right );
}
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 288 of file BSPTree.cpp.

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

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

{
  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

bool moab::BSPTree::cleanUpTrees [private]

Definition at line 47 of file BSPTree.hpp.

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

Definition at line 48 of file BSPTree.hpp.

Interface* moab::BSPTree::mbInstance [private]

Definition at line 44 of file BSPTree.hpp.

unsigned moab::BSPTree::meshSetFlags [private]

Definition at line 46 of file BSPTree.hpp.

Tag moab::BSPTree::planeTag [private]

Definition at line 45 of file BSPTree.hpp.

Tag moab::BSPTree::rootTag [private]

Definition at line 45 of file BSPTree.hpp.

The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines