Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
moab::BVHTree Class Reference

Bounding Volume Hierarchy (sorta like a tree), for sorting and searching entities spatially. More...

#include <BVHTree.hpp>

+ Inheritance diagram for moab::BVHTree:
+ Collaboration diagram for moab::BVHTree:

Classes

class  Bucket
 
class  HandleData
 
class  HandleData_comparator
 
class  Node
 
class  Split_comparator
 
class  SplitData
 
class  TreeNode
 

Public Member Functions

 BVHTree (Interface *impl)
 
 ~BVHTree ()
 
virtual ErrorCode reset_tree ()
 Destroy the tree maintained by this object, optionally checking we have the right root. More...
 
virtual ErrorCode parse_options (FileOptions &opts)
 Parse options for this tree, including common options for all trees. More...
 
virtual ErrorCode get_bounding_box (BoundBox &box, EntityHandle *tree_node=NULL) const
 Get bounding box for tree below tree_node, or entire tree If no tree has been built yet, returns +/- DBL_MAX for all dimensions. Note for some tree types, boxes are not available for non-root nodes, and this function will return failure if non-root is passed in. More...
 
virtual ErrorCode build_tree (const Range &entities, EntityHandle *tree_root_set=NULL, FileOptions *options=NULL)
 
virtual ErrorCode point_search (const double *point, EntityHandle &leaf_out, const double iter_tol=1.0e-10, const double inside_tol=1.0e-6, bool *multiple_leaves=NULL, EntityHandle *start_node=NULL, CartVect *params=NULL)
 Get leaf containing input position. More...
 
virtual ErrorCode distance_search (const double from_point[3], const double distance, std::vector< EntityHandle > &result_list, const double iter_tol=1.0e-10, const double inside_tol=1.0e-6, std::vector< double > *result_dists=NULL, std::vector< CartVect > *result_params=NULL, EntityHandle *tree_root=NULL)
 Find all leaves within a given distance from point If dists_out input non-NULL, also returns distances from each leaf; if point i is inside leaf, 0 is given as dists_out[i]. If params_out is non-NULL and myEval is non-NULL, will evaluate individual entities in tree nodes and return containing entities in leaves_out. In those cases, if params_out is also non-NULL, will return parameters in those elements in that vector. More...
 
virtual ErrorCode print ()
 print various things about this tree More...
 
- Public Member Functions inherited from moab::Tree
 Tree (Interface *iface)
 Constructor (bare) More...
 
virtual ~Tree ()
 Destructor. More...
 
ErrorCode delete_tree_sets ()
 Delete the entity sets associated with the tree, starting with the root and traversing children. More...
 
virtual ErrorCode get_info (EntityHandle root, double min[3], double max[3], unsigned int &max_dep)
 Return some basic information about the tree Stats are returned for tree starting from input node or tree root (root = 0) More...
 
ErrorCode find_all_trees (Range &results)
 Find all trees, by bounding box tag. More...
 
virtual ErrorCode distance_search (const double *point, const double distance, std::vector< EntityHandle > &leaves_out, const double iter_tol=1.0e-10, const double inside_tol=1.0e-6, std::vector< double > *dists_out=NULL, std::vector< CartVect > *params_out=NULL, EntityHandle *start_node=NULL)=0
 Find all leaves within a given distance from point If dists_out input non-NULL, also returns distances from each leaf; if point i is inside leaf, 0 is given as dists_out[i]. If params_out is non-NULL and myEval is non-NULL, will evaluate individual entities in tree nodes and return containing entities in leaves_out. In those cases, if params_out is also non-NULL, will return parameters in those elements in that vector. More...
 
Interfacemoab ()
 Return the MOAB interface associated with this tree. More...
 
const Interfacemoab () const
 Return the MOAB interface associated with this tree. More...
 
double get_max_depth ()
 Get max depth set on tree. More...
 
double get_max_per_leaf ()
 Get max entities per leaf set on tree. More...
 
TreeStatstree_stats ()
 Get tree traversal stats object. More...
 
const TreeStatstree_stats () const
 Get tree traversal stats object. More...
 
ErrorCode create_root (const double box_min[3], const double box_max[3], EntityHandle &root_handle)
 Create tree root and tag with bounding box. More...
 
ElemEvaluatorget_eval ()
 get/set the ElemEvaluator More...
 
void set_eval (ElemEvaluator *eval)
 get/set the ElemEvaluator More...
 

Private Types

typedef std::vector< HandleDataHandleDataVec
 

Private Member Functions

 BVHTree (const BVHTree &s)
 
void establish_buckets (HandleDataVec::const_iterator begin, HandleDataVec::const_iterator end, const BoundBox &interval, std::vector< std::vector< Bucket > > &buckets) const
 
unsigned int set_interval (BoundBox &interval, std::vector< Bucket >::const_iterator begin, std::vector< Bucket >::const_iterator end) const
 
void initialize_splits (std::vector< std::vector< SplitData > > &splits, const std::vector< std::vector< Bucket > > &buckets, const SplitData &data) const
 
void order_elements (HandleDataVec::iterator &begin, HandleDataVec::iterator &end, SplitData &data) const
 
void median_order (HandleDataVec::iterator &begin, HandleDataVec::iterator &end, SplitData &data) const
 
void choose_best_split (const std::vector< std::vector< SplitData > > &splits, SplitData &data) const
 
void find_split (HandleDataVec::iterator &begin, HandleDataVec::iterator &end, SplitData &data) const
 
ErrorCode find_point (const std::vector< double > &point, const unsigned int &index, const double iter_tol, const double inside_tol, std::pair< EntityHandle, CartVect > &result)
 
EntityHandle bruteforce_find (const double *point, const double iter_tol=1.0e-10, const double inside_tol=1.0e-6)
 
int local_build_tree (std::vector< Node > &tree_nodes, HandleDataVec::iterator begin, HandleDataVec::iterator end, const int index, const BoundBox &box, const int depth=0)
 
ErrorCode construct_element_vec (std::vector< HandleData > &handle_data_vec, const Range &elements, BoundBox &bounding_box)
 
ErrorCode convert_tree (std::vector< Node > &tree_nodes)
 
ErrorCode print_nodes (std::vector< Node > &nodes)
 

Private Attributes

Range entityHandles
 
std::vector< TreeNodemyTree
 
int splitsPerDir
 
EntityHandle startSetHandle
 

Static Private Attributes

static MOAB_EXPORT const char * treeName = "BVHTree"
 

Additional Inherited Members

- Protected Member Functions inherited from moab::Tree
ErrorCode parse_common_options (FileOptions &options)
 Parse options common to all trees. More...
 
Tag get_box_tag (bool create_if_missing=true)
 Get the box tag, possibly constructing it first. More...
 
- Protected Attributes inherited from moab::Tree
InterfacembImpl
 
BoundBox boundBox
 
int maxPerLeaf
 
int maxDepth
 
int treeDepth
 
double minWidth
 
unsigned int meshsetFlags
 
bool cleanUp
 
EntityHandle myRoot
 
Tag boxTag
 
std::string boxTagName
 
TreeStats treeStats
 
ElemEvaluatormyEval
 

Detailed Description

Bounding Volume Hierarchy (sorta like a tree), for sorting and searching entities spatially.

Definition at line 31 of file BVHTree.hpp.

Member Typedef Documentation

◆ HandleDataVec

typedef std::vector< HandleData > moab::BVHTree::HandleDataVec
private

Definition at line 139 of file BVHTree.hpp.

Constructor & Destructor Documentation

◆ BVHTree() [1/2]

moab::BVHTree::BVHTree ( Interface impl)
inline

Definition at line 357 of file BVHTree.hpp.

357  : Tree( impl ), splitsPerDir( 3 ), startSetHandle( 0 )
358 {
360 }

References moab::Tree::boxTagName, and treeName.

◆ ~BVHTree()

moab::BVHTree::~BVHTree ( )
inline

Definition at line 36 of file BVHTree.hpp.

37  {
38  reset_tree();
39  }

References reset_tree().

◆ BVHTree() [2/2]

moab::BVHTree::BVHTree ( const BVHTree s)
private

Member Function Documentation

◆ bruteforce_find()

EntityHandle moab::BVHTree::bruteforce_find ( const double *  point,
const double  iter_tol = 1.0e-10,
const double  inside_tol = 1.0e-6 
)
private

Definition at line 547 of file BVHTree.cpp.

548 {
550  CartVect params;
551  for( unsigned int i = 0; i < myTree.size(); i++ )
552  {
553  if( myTree[i].dim != 3 || !myTree[i].box.contains_point( point, iter_tol ) ) continue;
554  if( myEval )
555  {
556  EntityHandle entity = 0;
558  ErrorCode rval = myEval->find_containing_entity( startSetHandle + i, point, iter_tol, inside_tol, entity,
559  params.array(), &treeStats.traversalLeafObjectTests );
560  if( entity )
561  return entity;
562  else if( MB_SUCCESS != rval )
563  return 0;
564  }
565  else
566  return startSetHandle + i;
567  }
568  return 0;
569 }

References moab::CartVect::array(), dim, ErrorCode, moab::ElemEvaluator::find_containing_entity(), moab::TreeStats::leavesVisited, MB_SUCCESS, moab::Tree::myEval, myTree, moab::TreeStats::numTraversals, startSetHandle, moab::TreeStats::traversalLeafObjectTests, and moab::Tree::treeStats.

◆ build_tree()

ErrorCode moab::BVHTree::build_tree ( const Range entities,
EntityHandle tree_root_set = NULL,
FileOptions options = NULL 
)
virtual

Build the tree Build a tree with the entities input. If a non-NULL tree_root_set pointer is input, use the pointed-to set as the root of this tree (*tree_root_set!=0) otherwise construct a new root set and pass its handle back in *tree_root_set. Options vary by tree type; see Tree.hpp for common options; options specific to AdaptiveKDTree: SPLITS_PER_DIR: number of candidate splits considered per direction; default = 3 CANDIDATE_PLANE_SET: method used to decide split planes; see CandidatePlaneSet enum (below) for possible values; default = 1 (SUBDIVISION_SNAP)

Parameters
entitiesEntities with which to build the tree
tree_rootRoot set for tree (see function description)
optsOptions for tree (see function description)
Returns
Error is returned only on build failure

Implements moab::Tree.

Definition at line 11 of file BVHTree.cpp.

12 {
13  ErrorCode rval;
14  CpuTimer cp;
15 
16  if( options )
17  {
18  rval = parse_options( *options );
19  if( MB_SUCCESS != rval ) return rval;
20 
21  if( !options->all_seen() ) return MB_FAILURE;
22  }
23 
24  // calculate bounding box of elements
25  BoundBox box;
26  rval = box.update( *moab(), entities );
27  if( MB_SUCCESS != rval ) return rval;
28 
29  // create tree root
30  EntityHandle tmp_root;
31  if( !tree_root_set ) tree_root_set = &tmp_root;
32  rval = create_root( box.bMin.array(), box.bMax.array(), *tree_root_set );
33  if( MB_SUCCESS != rval ) return rval;
34  rval = mbImpl->add_entities( *tree_root_set, entities );
35  if( MB_SUCCESS != rval ) return rval;
36 
37  // a fully balanced tree will have 2*_entities.size()
38  // which is one doubling away..
39  std::vector< Node > tree_nodes;
40  tree_nodes.reserve( entities.size() / maxPerLeaf );
41  std::vector< HandleData > handle_data_vec;
42  rval = construct_element_vec( handle_data_vec, entities, boundBox );
43  if( MB_SUCCESS != rval ) return rval;
44 
45 #ifndef NDEBUG
46  for( std::vector< HandleData >::const_iterator i = handle_data_vec.begin(); i != handle_data_vec.end(); ++i )
47  {
48  if( !boundBox.intersects_box( i->myBox, 0 ) )
49  {
50  std::cerr << "BB:" << boundBox << "EB:" << i->myBox << std::endl;
51  return MB_FAILURE;
52  }
53  }
54 #endif
55  // We only build nonempty trees
56  if( !handle_data_vec.empty() )
57  {
58  // initially all bits are set
59  tree_nodes.push_back( Node() );
60  const int depth = local_build_tree( tree_nodes, handle_data_vec.begin(), handle_data_vec.end(), 0, boundBox );
61 #ifndef NDEBUG
62  std::set< EntityHandle > entity_handles;
63  for( std::vector< Node >::iterator n = tree_nodes.begin(); n != tree_nodes.end(); ++n )
64  {
65  for( HandleDataVec::const_iterator j = n->entities.begin(); j != n->entities.end(); ++j )
66  {
67  entity_handles.insert( j->myHandle );
68  }
69  }
70  if( entity_handles.size() != entities.size() )
71  {
72  std::cout << "Entity Handle Size Mismatch!" << std::endl;
73  }
74  for( Range::iterator i = entities.begin(); i != entities.end(); ++i )
75  {
76  if( entity_handles.find( *i ) == entity_handles.end() )
77  std::cout << "Tree is missing an entity! " << std::endl;
78  }
79 #endif
80  treeDepth = std::max( depth, treeDepth );
81  }
82 
83  // convert vector of Node's to entity sets and vector of TreeNode's
84  rval = convert_tree( tree_nodes );
85  if( MB_SUCCESS != rval ) return rval;
86 
87  treeStats.reset();
89  treeStats.initTime = cp.time_elapsed();
90 
91  return rval;
92 }

References moab::Interface::add_entities(), moab::FileOptions::all_seen(), moab::CartVect::array(), moab::BoundBox::bMax, moab::BoundBox::bMin, moab::Tree::boundBox, moab::TreeStats::compute_stats(), construct_element_vec(), convert_tree(), moab::Tree::create_root(), entities, ErrorCode, moab::TreeStats::initTime, moab::BoundBox::intersects_box(), local_build_tree(), moab::Tree::maxPerLeaf, MB_SUCCESS, moab::Tree::mbImpl, moab::Tree::moab(), parse_options(), moab::TreeStats::reset(), startSetHandle, moab::CpuTimer::time_elapsed(), moab::Tree::treeDepth, moab::Tree::treeStats, and moab::BoundBox::update().

◆ choose_best_split()

void moab::BVHTree::choose_best_split ( const std::vector< std::vector< SplitData > > &  splits,
SplitData data 
) const
inlineprivate

Definition at line 398 of file BVHTree.hpp.

399 {
400  std::vector< SplitData > best_splits;
401  for( std::vector< std::vector< SplitData > >::const_iterator i = splits.begin(); i != splits.end(); ++i )
402  {
403  std::vector< SplitData >::const_iterator j =
404  std::min_element( ( *i ).begin(), ( *i ).end(), Split_comparator() );
405  best_splits.push_back( *j );
406  }
407  data = *std::min_element( best_splits.begin(), best_splits.end(), Split_comparator() );
408 }

Referenced by find_split().

◆ construct_element_vec()

ErrorCode moab::BVHTree::construct_element_vec ( std::vector< HandleData > &  handle_data_vec,
const Range elements,
BoundBox bounding_box 
)
inlineprivate

Definition at line 410 of file BVHTree.hpp.

413 {
414  std::vector< double > coordinate( 3 * CN::MAX_NODES_PER_ELEMENT );
415  int num_conn;
416  ErrorCode rval = MB_SUCCESS;
417  std::vector< EntityHandle > storage;
418  for( Range::iterator i = elements.begin(); i != elements.end(); ++i )
419  {
420  // TODO: not generic enough. Why dim != 3
421  // Commence un-necessary deep copying.
422  const EntityHandle* connect;
423  rval = mbImpl->get_connectivity( *i, connect, num_conn, false, &storage );
424  if( MB_SUCCESS != rval ) return rval;
425  rval = mbImpl->get_coords( connect, num_conn, &coordinate[0] );
426  if( MB_SUCCESS != rval ) return rval;
427  BoundBox box;
428  for( int j = 0; j < num_conn; j++ )
429  box.update( &coordinate[3 * j] );
430  if( i == elements.begin() )
431  bounding_box = box;
432  else
433  bounding_box.update( box );
434  handle_data_vec.push_back( HandleData( *i, box, 0.0 ) );
435  }
436 
437  return rval;
438 }

References moab::Range::begin(), bounding_box, moab::Range::end(), ErrorCode, moab::Interface::get_connectivity(), moab::Interface::get_coords(), moab::CN::MAX_NODES_PER_ELEMENT, MB_SUCCESS, moab::Tree::mbImpl, and moab::BoundBox::update().

Referenced by build_tree().

◆ convert_tree()

ErrorCode moab::BVHTree::convert_tree ( std::vector< Node > &  tree_nodes)
private

Definition at line 94 of file BVHTree.cpp.

95 {
96  // first construct the proper number of entity sets
97  ReadUtilIface* read_util;
98  ErrorCode rval = mbImpl->query_interface( read_util );
99  if( MB_SUCCESS != rval ) return rval;
100 
101  { // isolate potentially-large std::vector so it gets deleted earlier
102  std::vector< unsigned int > tmp_flags( tree_nodes.size(), meshsetFlags );
103  rval = read_util->create_entity_sets( tree_nodes.size(), &tmp_flags[0], 0, startSetHandle );
104  if( MB_SUCCESS != rval ) return rval;
105  rval = mbImpl->release_interface( read_util );
106  if( MB_SUCCESS != rval ) return rval;
107  }
108 
109  // populate the sets and the TreeNode vector
110  EntityHandle set_handle = startSetHandle;
111  std::vector< Node >::iterator it;
112  myTree.reserve( tree_nodes.size() );
113  for( it = tree_nodes.begin(); it != tree_nodes.end(); ++it, set_handle++ )
114  {
115  if( it != tree_nodes.begin() && !it->entities.empty() )
116  {
117  Range range;
118  for( HandleDataVec::iterator hit = it->entities.begin(); hit != it->entities.end(); ++hit )
119  range.insert( hit->myHandle );
120  rval = mbImpl->add_entities( set_handle, range );
121  if( MB_SUCCESS != rval ) return rval;
122  }
123  myTree.push_back( TreeNode( it->dim, it->child, it->Lmax, it->Rmin, it->box ) );
124 
125  if( it->dim != 3 )
126  {
127  rval = mbImpl->add_child_meshset( set_handle, startSetHandle + it->child );
128  if( MB_SUCCESS != rval ) return rval;
129  rval = mbImpl->add_child_meshset( set_handle, startSetHandle + it->child + 1 );
130  if( MB_SUCCESS != rval ) return rval;
131  }
132  }
133 
134  return MB_SUCCESS;
135 }

References moab::Interface::add_child_meshset(), moab::Interface::add_entities(), moab::ReadUtilIface::create_entity_sets(), ErrorCode, moab::Range::insert(), MB_SUCCESS, moab::Tree::mbImpl, moab::Tree::meshsetFlags, myTree, moab::Interface::query_interface(), moab::Interface::release_interface(), and startSetHandle.

Referenced by build_tree().

◆ distance_search()

ErrorCode moab::BVHTree::distance_search ( const double  from_point[3],
const double  distance,
std::vector< EntityHandle > &  result_list,
const double  iter_tol = 1.0e-10,
const double  inside_tol = 1.0e-6,
std::vector< double > *  result_dists = NULL,
std::vector< CartVect > *  result_params = NULL,
EntityHandle tree_root = NULL 
)
virtual

Find all leaves within a given distance from point If dists_out input non-NULL, also returns distances from each leaf; if point i is inside leaf, 0 is given as dists_out[i]. If params_out is non-NULL and myEval is non-NULL, will evaluate individual entities in tree nodes and return containing entities in leaves_out. In those cases, if params_out is also non-NULL, will return parameters in those elements in that vector.

Parameters
from_pointPoint to be located in tree
distanceDistance within which to query
result_listLeaves within distance or containing point
iter_tolTolerance for convergence of point search
inside_tolTolerance for inside element calculation
result_distsIf non-NULL, will contain distsances to leaves
result_paramsIf non-NULL, will contain parameters of the point in the ents in leaves_out
tree_rootStart from this tree node (non-NULL) instead of tree root (NULL)

Definition at line 646 of file BVHTree.cpp.

654 {
655  // non-NULL root should be in tree
656  // convoluted check because the root is different from startSetHandle
657  EntityHandle this_set = ( tree_root ? *tree_root : startSetHandle );
658  if( this_set != myRoot && ( this_set < startSetHandle || this_set >= startSetHandle + myTree.size() ) )
659  return MB_FAILURE;
660  else if( this_set == myRoot )
661  this_set = startSetHandle;
662 
664 
665  const double dist_sqr = distance * distance;
666  const CartVect from( from_point );
667  std::vector< EntityHandle > candidates; // list of subtrees to traverse
668  // pre-allocate space for default max tree depth
669  candidates.reserve( maxDepth );
670 
671  // misc temporary values
672  ErrorCode rval;
673  BoundBox box;
674 
675  candidates.push_back( this_set - startSetHandle );
676 
677  while( !candidates.empty() )
678  {
679 
680  EntityHandle ind = candidates.back();
681  this_set = startSetHandle + ind;
682  candidates.pop_back();
684  if( myTree[ind].dim == 3 ) treeStats.leavesVisited++;
685 
686  // test box of this node
687  rval = get_bounding_box( box, &this_set );
688  if( MB_SUCCESS != rval ) return rval;
689  double d_sqr = box.distance_squared( from_point );
690 
691  // if greater than cutoff, continue
692  if( d_sqr > dist_sqr ) continue;
693 
694  // else if not a leaf, test children & put on list
695  else if( myTree[ind].dim != 3 )
696  {
697  candidates.push_back( myTree[ind].child );
698  candidates.push_back( myTree[ind].child + 1 );
699  continue;
700  }
701 
702  if( myEval && result_params )
703  {
704  EntityHandle ent;
705  CartVect params;
706  rval = myEval->find_containing_entity( startSetHandle + ind, from_point, iter_tol, inside_tol, ent,
707  params.array(), &treeStats.traversalLeafObjectTests );
708  if( MB_SUCCESS != rval )
709  return rval;
710  else if( ent )
711  {
712  result_list.push_back( ent );
713  result_params->push_back( params );
714  if( result_dists ) result_dists->push_back( 0.0 );
715  }
716  }
717  else
718  {
719  // leaf node within distance; return in list
720  result_list.push_back( this_set );
721  if( result_dists ) result_dists->push_back( sqrt( d_sqr ) );
722  }
723  }
724 
725  return MB_SUCCESS;
726 }

References moab::CartVect::array(), child, dim, moab::BoundBox::distance_squared(), ErrorCode, moab::ElemEvaluator::find_containing_entity(), get_bounding_box(), moab::TreeStats::leavesVisited, moab::Tree::maxDepth, MB_SUCCESS, moab::Tree::myEval, moab::Tree::myRoot, myTree, moab::TreeStats::nodesVisited, moab::TreeStats::numTraversals, startSetHandle, moab::TreeStats::traversalLeafObjectTests, and moab::Tree::treeStats.

◆ establish_buckets()

void moab::BVHTree::establish_buckets ( HandleDataVec::const_iterator  begin,
HandleDataVec::const_iterator  end,
const BoundBox interval,
std::vector< std::vector< Bucket > > &  buckets 
) const
private

Definition at line 150 of file BVHTree.cpp.

154 {
155  // put each element into its bucket
156  for( HandleDataVec::const_iterator i = begin; i != end; ++i )
157  {
158  const BoundBox& box = i->myBox;
159  for( unsigned int dim = 0; dim < 3; ++dim )
160  {
161  const unsigned int index = Bucket::bucket_index( splitsPerDir, box, interval, dim );
162  assert( index < buckets[dim].size() );
163  Bucket& bucket = buckets[dim][index];
164  if( bucket.mySize > 0 )
165  bucket.boundingBox.update( box );
166  else
167  bucket.boundingBox = box;
168  bucket.mySize++;
169  }
170  }
171 
172 #ifndef NDEBUG
173  BoundBox elt_union = begin->myBox;
174  for( HandleDataVec::const_iterator i = begin; i != end; ++i )
175  {
176  const BoundBox& box = i->myBox;
177  elt_union.update( box );
178  for( unsigned int dim = 0; dim < 3; ++dim )
179  {
180  const unsigned int index = Bucket::bucket_index( splitsPerDir, box, interval, dim );
181  Bucket& bucket = buckets[dim][index];
182  if( !bucket.boundingBox.intersects_box( box ) ) std::cerr << "Buckets not covering elements!" << std::endl;
183  }
184  }
185  if( !elt_union.intersects_box( interval ) )
186  {
187  std::cout << "element union: " << std::endl << elt_union;
188  std::cout << "intervals: " << std::endl << interval;
189  std::cout << "union of elts does not contain original box!" << std::endl;
190  }
191  if( !interval.intersects_box( elt_union ) )
192  {
193  std::cout << "original box does not contain union of elts" << std::endl;
194  std::cout << interval << std::endl << elt_union << std::endl;
195  }
196  for( unsigned int d = 0; d < 3; ++d )
197  {
198  std::vector< unsigned int > nonempty;
199  const std::vector< Bucket >& buckets_ = buckets[d];
200  unsigned int j = 0;
201  for( std::vector< Bucket >::const_iterator i = buckets_.begin(); i != buckets_.end(); ++i, ++j )
202  {
203  if( i->mySize > 0 )
204  {
205  nonempty.push_back( j );
206  }
207  }
208  BoundBox test_box = buckets_[nonempty.front()].boundingBox;
209  for( unsigned int i = 0; i < nonempty.size(); ++i )
210  test_box.update( buckets_[nonempty[i]].boundingBox );
211 
212  if( !test_box.intersects_box( interval ) )
213  std::cout << "union of buckets in dimension: " << d << "does not contain original box!" << std::endl;
214  if( !interval.intersects_box( test_box ) )
215  {
216  std::cout << "original box does "
217  << "not contain union of buckets"
218  << "in dimension: " << d << std::endl;
219  std::cout << interval << std::endl << test_box << std::endl;
220  }
221  }
222 #endif
223 }

References moab::BVHTree::Bucket::boundingBox, moab::BVHTree::Bucket::bucket_index(), dim, moab::BoundBox::intersects_box(), moab::BVHTree::Bucket::mySize, size, splitsPerDir, and moab::BoundBox::update().

Referenced by find_split().

◆ find_point()

ErrorCode moab::BVHTree::find_point ( const std::vector< double > &  point,
const unsigned int &  index,
const double  iter_tol,
const double  inside_tol,
std::pair< EntityHandle, CartVect > &  result 
)
private

Definition at line 466 of file BVHTree.cpp.

471 {
472  if( index == 0 ) treeStats.numTraversals++;
473  const TreeNode& node = myTree[index];
475  CartVect params;
476  int is_inside;
477  ErrorCode rval = MB_SUCCESS;
478  if( node.dim == 3 )
479  {
481  Range entities;
483  if( MB_SUCCESS != rval ) return rval;
484 
485  for( Range::iterator i = entities.begin(); i != entities.end(); ++i )
486  {
488  myEval->set_ent_handle( *i );
489  myEval->reverse_eval( &point[0], iter_tol, inside_tol, params.array(), &is_inside );
490  if( is_inside )
491  {
492  result.first = *i;
493  result.second = params;
494  return MB_SUCCESS;
495  }
496  }
497  result.first = 0;
498  return MB_SUCCESS;
499  }
500  // the extra tol here considers the case where
501  // 0 < Rmin - Lmax < 2tol
502  std::vector< EntityHandle > children;
503  rval = mbImpl->get_child_meshsets( startSetHandle + index, children );
504  if( MB_SUCCESS != rval || children.size() != 2 ) return rval;
505 
506  if( ( node.Lmax + iter_tol ) < ( node.Rmin - iter_tol ) )
507  {
508  if( point[node.dim] <= ( node.Lmax + iter_tol ) )
509  return find_point( point, children[0] - startSetHandle, iter_tol, inside_tol, result );
510  else if( point[node.dim] >= ( node.Rmin - iter_tol ) )
511  return find_point( point, children[1] - startSetHandle, iter_tol, inside_tol, result );
512  result = std::make_pair( 0, CartVect( &point[0] ) ); // point lies in empty space.
513  return MB_SUCCESS;
514  }
515 
516  // Boxes overlap
517  // left of Rmin, you must be on the left
518  // we can't be sure about the boundaries since the boxes overlap
519  // this was a typo in the paper which caused pain.
520  if( point[node.dim] < ( node.Rmin - iter_tol ) )
521  return find_point( point, children[0] - startSetHandle, iter_tol, inside_tol, result );
522  // if you are on the right Lmax, you must be on the right
523  else if( point[node.dim] > ( node.Lmax + iter_tol ) )
524  return find_point( point, children[1] - startSetHandle, iter_tol, inside_tol, result );
525 
526  /* pg5 of paper
527  * However, instead of always traversing either subtree
528  * first (e.g. left always before right), we first traverse
529  * the subtree whose bounding plane has the larger distance to the
530  * sought point. This results in less overall traversal, and the correct
531  * cell is identified more quickly.
532  */
533  // So far all testing confirms that this 'heuristic' is
534  // significantly slower.
535  // I conjecture this is because it gets improperly
536  // branch predicted..
537  // bool dir = (point[ node.dim] - node.Rmin) <=
538  // (node.Lmax - point[ node.dim]);
539  find_point( point, children[0] - startSetHandle, iter_tol, inside_tol, result );
540  if( result.first == 0 )
541  {
542  return find_point( point, children[1] - startSetHandle, iter_tol, inside_tol, result );
543  }
544  return MB_SUCCESS;
545 }

References moab::CartVect::array(), children, moab::BVHTree::TreeNode::dim, entities, ErrorCode, moab::Interface::get_child_meshsets(), moab::Interface::get_entities_by_handle(), moab::TreeStats::leavesVisited, moab::BVHTree::TreeNode::Lmax, MB_SUCCESS, moab::Tree::mbImpl, moab::Tree::myEval, myTree, moab::TreeStats::nodesVisited, moab::TreeStats::numTraversals, moab::ElemEvaluator::reverse_eval(), moab::BVHTree::TreeNode::Rmin, moab::ElemEvaluator::set_ent_handle(), startSetHandle, moab::TreeStats::traversalLeafObjectTests, and moab::Tree::treeStats.

◆ find_split()

void moab::BVHTree::find_split ( HandleDataVec::iterator &  begin,
HandleDataVec::iterator &  end,
SplitData data 
) const
private

Definition at line 320 of file BVHTree.cpp.

321 {
322  std::vector< std::vector< Bucket > > buckets( 3, std::vector< Bucket >( splitsPerDir + 1 ) );
323  std::vector< std::vector< SplitData > > splits( 3, std::vector< SplitData >( splitsPerDir, data ) );
324 
325  const BoundBox interval = data.boundingBox;
326  establish_buckets( begin, end, interval, buckets );
327  initialize_splits( splits, buckets, data );
328  choose_best_split( splits, data );
329  const bool use_median = ( 0 == data.nl ) || ( data.nr == 0 );
330  if( !use_median )
331  order_elements( begin, end, data );
332  else
333  median_order( begin, end, data );
334 
335 #ifndef NDEBUG
336  bool seen_one = false, issue = false;
337  bool first_left = true, first_right = true;
338  unsigned int count_left = 0, count_right = 0;
339  BoundBox left_box, right_box;
340  for( HandleDataVec::iterator i = begin; i != end; ++i )
341  {
342  int order = i->myDim;
343  if( order != 0 && order != 1 )
344  {
345  std::cerr << "Invalid order element !";
346  std::cerr << order << std::endl;
347  std::exit( -1 );
348  }
349  if( order == 1 )
350  {
351  seen_one = 1;
352  count_right++;
353  if( first_right )
354  {
355  right_box = i->myBox;
356  first_right = false;
357  }
358  else
359  {
360  right_box.update( i->myBox );
361  }
362  if( !right_box.intersects_box( i->myBox ) )
363  {
364  if( !issue )
365  {
366  std::cerr << "Bounding right box issue!" << std::endl;
367  }
368  issue = true;
369  }
370  }
371  if( order == 0 )
372  {
373  count_left++;
374  if( first_left )
375  {
376  left_box = i->myBox;
377  first_left = false;
378  }
379  else
380  {
381  left_box.update( i->myBox );
382  }
383  if( !data.leftBox.intersects_box( i->myBox ) )
384  {
385  if( !issue )
386  {
387  std::cerr << "Bounding left box issue!" << std::endl;
388  }
389  issue = true;
390  }
391  if( seen_one )
392  {
393  std::cerr << "Invalid ordering!" << std::endl;
394  std::cout << ( i - 1 )->myDim << order << std::endl;
395  exit( -1 );
396  }
397  }
398  }
399  if( !left_box.intersects_box( data.leftBox ) ) std::cout << "left elts do not contain left box" << std::endl;
400  if( !data.leftBox.intersects_box( left_box ) ) std::cout << "left box does not contain left elts" << std::endl;
401  if( !right_box.intersects_box( data.rightBox ) ) std::cout << "right elts do not contain right box" << std::endl;
402  if( !data.rightBox.intersects_box( right_box ) ) std::cout << "right box do not contain right elts" << std::endl;
403 
404  if( count_left != data.nl || count_right != data.nr )
405  {
406  std::cerr << "counts are off!" << std::endl;
407  std::cerr << "total: " << std::distance( begin, end ) << std::endl;
408  std::cerr << "Dim: " << data.dim << std::endl;
409  std::cerr << data.Lmax << " , " << data.Rmin << std::endl;
410  std::cerr << "Right box: " << std::endl << data.rightBox << "Left box: " << std::endl << data.leftBox;
411  std::cerr << "supposed to be: " << data.nl << " " << data.nr << std::endl;
412  std::cerr << "accountant says: " << count_left << " " << count_right << std::endl;
413  std::exit( -1 );
414  }
415 #endif
416 }

References moab::BVHTree::SplitData::boundingBox, choose_best_split(), moab::BVHTree::SplitData::dim, establish_buckets(), initialize_splits(), moab::BoundBox::intersects_box(), left_box, moab::BVHTree::SplitData::leftBox, moab::BVHTree::SplitData::Lmax, median_order(), moab::BVHTree::SplitData::nl, moab::BVHTree::SplitData::nr, order_elements(), right_box, moab::BVHTree::SplitData::rightBox, moab::BVHTree::SplitData::Rmin, and splitsPerDir.

Referenced by local_build_tree().

◆ get_bounding_box()

ErrorCode moab::BVHTree::get_bounding_box ( BoundBox box,
EntityHandle tree_node = NULL 
) const
virtual

Get bounding box for tree below tree_node, or entire tree If no tree has been built yet, returns +/- DBL_MAX for all dimensions. Note for some tree types, boxes are not available for non-root nodes, and this function will return failure if non-root is passed in.

Parameters
boxThe box for this tree
tree_nodeIf non-NULL, node for which box is requested, tree root if NULL
Returns
Only returns error on fatal condition

Reimplemented from moab::Tree.

Definition at line 571 of file BVHTree.cpp.

572 {
573  if( !tree_node || *tree_node == startSetHandle )
574  {
575  box = boundBox;
576  return MB_SUCCESS;
577  }
578  else if( ( tree_node && !startSetHandle ) || *tree_node < startSetHandle ||
579  *tree_node - startSetHandle > myTree.size() )
580  return MB_FAILURE;
581 
582  box = myTree[*tree_node - startSetHandle].box;
583  return MB_SUCCESS;
584 }

References moab::Tree::boundBox, MB_SUCCESS, myTree, and startSetHandle.

Referenced by distance_search(), and point_search().

◆ initialize_splits()

void moab::BVHTree::initialize_splits ( std::vector< std::vector< SplitData > > &  splits,
const std::vector< std::vector< Bucket > > &  buckets,
const SplitData data 
) const
private

Definition at line 225 of file BVHTree.cpp.

228 {
229  for( unsigned int d = 0; d < 3; ++d )
230  {
231  std::vector< SplitData >::iterator splits_begin = splits[d].begin();
232  std::vector< SplitData >::iterator splits_end = splits[d].end();
233  std::vector< Bucket >::const_iterator left_begin = buckets[d].begin();
234  std::vector< Bucket >::const_iterator _end = buckets[d].end();
235  std::vector< Bucket >::const_iterator left_end = buckets[d].begin() + 1;
236  for( std::vector< SplitData >::iterator s = splits_begin; s != splits_end; ++s, ++left_end )
237  {
238  s->nl = set_interval( s->leftBox, left_begin, left_end );
239  if( s->nl == 0 )
240  {
241  s->leftBox = data.boundingBox;
242  s->leftBox.bMax[d] = s->leftBox.bMin[d];
243  }
244  s->nr = set_interval( s->rightBox, left_end, _end );
245  if( s->nr == 0 )
246  {
247  s->rightBox = data.boundingBox;
248  s->rightBox.bMin[d] = s->rightBox.bMax[d];
249  }
250  s->Lmax = s->leftBox.bMax[d];
251  s->Rmin = s->rightBox.bMin[d];
252  s->split = std::distance( splits_begin, s );
253  s->dim = d;
254  }
255 #ifndef NDEBUG
256  for( std::vector< SplitData >::iterator s = splits_begin; s != splits_end; ++s )
257  {
258  BoundBox test_box = s->leftBox;
259  test_box.update( s->rightBox );
260  if( !data.boundingBox.intersects_box( test_box ) )
261  {
262  std::cout << "nr: " << s->nr << std::endl;
263  std::cout << "Test box: " << std::endl << test_box;
264  std::cout << "Left box: " << std::endl << s->leftBox;
265  std::cout << "Right box: " << std::endl << s->rightBox;
266  std::cout << "Interval: " << std::endl << data.boundingBox;
267  std::cout << "Split boxes larger than bb" << std::endl;
268  }
269  if( !test_box.intersects_box( data.boundingBox ) )
270  {
271  std::cout << "bb larger than union of split boxes" << std::endl;
272  }
273  }
274 #endif
275  }
276 }

References moab::BoundBox::bMax, moab::BoundBox::bMin, moab::BVHTree::SplitData::boundingBox, moab::BoundBox::intersects_box(), set_interval(), and moab::BoundBox::update().

Referenced by find_split().

◆ local_build_tree()

int moab::BVHTree::local_build_tree ( std::vector< Node > &  tree_nodes,
HandleDataVec::iterator  begin,
HandleDataVec::iterator  end,
const int  index,
const BoundBox box,
const int  depth = 0 
)
private

Definition at line 418 of file BVHTree.cpp.

424 {
425 #ifndef NDEBUG
426  for( HandleDataVec::const_iterator i = begin; i != end; ++i )
427  {
428  if( !box.intersects_box( i->myBox, 0 ) )
429  {
430  std::cerr << "depth: " << depth << std::endl;
431  std::cerr << "BB:" << box << "EB:" << i->myBox << std::endl;
432  std::exit( -1 );
433  }
434  }
435 #endif
436 
437  const unsigned int total_num_elements = std::distance( begin, end );
438  tree_nodes[index].box = box;
439 
440  // logic for splitting conditions
441  if( (int)total_num_elements > maxPerLeaf && depth < maxDepth )
442  {
443  SplitData data;
444  data.boundingBox = box;
445  find_split( begin, end, data );
446  // assign data to node
447  tree_nodes[index].Lmax = data.Lmax;
448  tree_nodes[index].Rmin = data.Rmin;
449  tree_nodes[index].dim = data.dim;
450  tree_nodes[index].child = tree_nodes.size();
451  // insert left, right children;
452  tree_nodes.push_back( Node() );
453  tree_nodes.push_back( Node() );
454  const int left_depth =
455  local_build_tree( tree_nodes, begin, begin + data.nl, tree_nodes[index].child, data.leftBox, depth + 1 );
456  const int right_depth =
457  local_build_tree( tree_nodes, begin + data.nl, end, tree_nodes[index].child + 1, data.rightBox, depth + 1 );
458  return std::max( left_depth, right_depth );
459  }
460 
461  tree_nodes[index].dim = 3;
462  std::copy( begin, end, std::back_inserter( tree_nodes[index].entities ) );
463  return depth;
464 }

References moab::BVHTree::SplitData::boundingBox, moab::BVHTree::SplitData::dim, entities, find_split(), moab::BoundBox::intersects_box(), moab::BVHTree::SplitData::leftBox, moab::BVHTree::SplitData::Lmax, moab::Tree::maxDepth, moab::Tree::maxPerLeaf, moab::BVHTree::SplitData::nl, moab::BVHTree::SplitData::rightBox, and moab::BVHTree::SplitData::Rmin.

Referenced by build_tree().

◆ median_order()

void moab::BVHTree::median_order ( HandleDataVec::iterator &  begin,
HandleDataVec::iterator &  end,
SplitData data 
) const
private

Definition at line 278 of file BVHTree.cpp.

279 {
280  int dim = data.dim;
281  for( HandleDataVec::iterator i = begin; i != end; ++i )
282  {
283  i->myDim = 0.5 * ( i->myBox.bMin[dim], i->myBox.bMax[dim] );
284  }
285  std::sort( begin, end, BVHTree::HandleData_comparator() );
286  const unsigned int total = std::distance( begin, end );
287  HandleDataVec::iterator middle = begin + ( total / 2 );
288  double middle_center = middle->myDim;
289  middle_center += ( ++middle )->myDim;
290  middle_center *= 0.5;
291  data.split = middle_center;
292  data.nl = std::distance( begin, middle ) + 1;
293  data.nr = total - data.nl;
294  ++middle;
295  data.leftBox = begin->myBox;
296  data.rightBox = middle->myBox;
297  for( HandleDataVec::iterator i = begin; i != middle; ++i )
298  {
299  i->myDim = 0;
300  data.leftBox.update( i->myBox );
301  }
302  for( HandleDataVec::iterator i = middle; i != end; ++i )
303  {
304  i->myDim = 1;
305  data.rightBox.update( i->myBox );
306  }
307  data.Rmin = data.rightBox.bMin[data.dim];
308  data.Lmax = data.leftBox.bMax[data.dim];
309 #ifndef NDEBUG
310  BoundBox test_box( data.rightBox );
311  if( !data.boundingBox.intersects_box( test_box ) )
312  {
313  std::cerr << "MEDIAN: BB Does not contain splits" << std::endl;
314  std::cerr << "test_box: " << test_box << std::endl;
315  std::cerr << "data.boundingBox: " << data.boundingBox << std::endl;
316  }
317 #endif
318 }

References moab::BoundBox::bMax, moab::BoundBox::bMin, moab::BVHTree::SplitData::boundingBox, moab::BVHTree::SplitData::dim, dim, moab::BoundBox::intersects_box(), moab::BVHTree::SplitData::leftBox, moab::BVHTree::SplitData::Lmax, moab::BVHTree::SplitData::nl, moab::BVHTree::SplitData::nr, moab::BVHTree::SplitData::rightBox, moab::BVHTree::SplitData::Rmin, moab::BVHTree::SplitData::split, and moab::BoundBox::update().

Referenced by find_split().

◆ order_elements()

void moab::BVHTree::order_elements ( HandleDataVec::iterator &  begin,
HandleDataVec::iterator &  end,
SplitData data 
) const
inlineprivate

Definition at line 386 of file BVHTree.hpp.

389 {
390  for( HandleDataVec::iterator i = begin; i != end; ++i )
391  {
392  const int index = Bucket::bucket_index( splitsPerDir, i->myBox, data.boundingBox, data.dim );
393  i->myDim = ( index <= data.split ) ? 0 : 1;
394  }
395  std::sort( begin, end, HandleData_comparator() );
396 }

References moab::BVHTree::SplitData::boundingBox, moab::BVHTree::Bucket::bucket_index(), moab::BVHTree::SplitData::dim, moab::BVHTree::SplitData::split, and splitsPerDir.

Referenced by find_split().

◆ parse_options()

ErrorCode moab::BVHTree::parse_options ( FileOptions opts)
virtual

Parse options for this tree, including common options for all trees.

Parameters
optsOptions

Implements moab::Tree.

Definition at line 137 of file BVHTree.cpp.

138 {
139  ErrorCode rval = parse_common_options( opts );
140  if( MB_SUCCESS != rval ) return rval;
141 
142  // SPLITS_PER_DIR: number of candidate splits considered per direction; default = 3
143  int tmp_int;
144  rval = opts.get_int_option( "SPLITS_PER_DIR", tmp_int );
145  if( MB_SUCCESS == rval ) splitsPerDir = tmp_int;
146 
147  return MB_SUCCESS;
148 }

References ErrorCode, moab::FileOptions::get_int_option(), MB_SUCCESS, moab::Tree::parse_common_options(), and splitsPerDir.

Referenced by build_tree().

◆ point_search()

ErrorCode moab::BVHTree::point_search ( const double *  point,
EntityHandle leaf_out,
const double  iter_tol = 1.0e-10,
const double  inside_tol = 1.0e-6,
bool *  multiple_leaves = NULL,
EntityHandle start_node = NULL,
CartVect params = NULL 
)
virtual

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.
    Parameters
    pointPoint to be located in tree
    leaf_outLeaf containing point
    iter_tolTolerance for convergence of point search
    inside_tolTolerance for inside element calculation
    multiple_leavesSome tree types can have multiple leaves containing a point; if non-NULL, this parameter is returned true if multiple leaves contain the input point
    start_nodeStart from this tree node (non-NULL) instead of tree root (NULL)
    Returns
    Non-success returned only in case of failure; not-found indicated by leaf_out=0

Implements moab::Tree.

Definition at line 586 of file BVHTree.cpp.

593 {
595 
596  EntityHandle this_set = ( start_node ? *start_node : startSetHandle );
597  // convoluted check because the root is different from startSetHandle
598  if( this_set != myRoot && ( this_set < startSetHandle || this_set >= startSetHandle + myTree.size() ) )
599  return MB_FAILURE;
600  else if( this_set == myRoot )
601  this_set = startSetHandle;
602 
603  std::vector< EntityHandle > candidates,
604  result_list; // list of subtrees to traverse, and results
605  candidates.push_back( this_set - startSetHandle );
606 
607  BoundBox box;
608  while( !candidates.empty() )
609  {
610  EntityHandle ind = candidates.back();
612  if( myTree[ind].dim == 3 ) treeStats.leavesVisited++;
613  this_set = startSetHandle + ind;
614  candidates.pop_back();
615 
616  // test box of this node
617  ErrorCode rval = get_bounding_box( box, &this_set );
618  if( MB_SUCCESS != rval ) return rval;
619  if( !box.contains_point( point, iter_tol ) ) continue;
620 
621  // else if not a leaf, test children & put on list
622  else if( myTree[ind].dim != 3 )
623  {
624  candidates.push_back( myTree[ind].child );
625  candidates.push_back( myTree[ind].child + 1 );
626  continue;
627  }
628  else if( myTree[ind].dim == 3 && myEval && params )
629  {
630  rval = myEval->find_containing_entity( startSetHandle + ind, point, iter_tol, inside_tol, leaf_out,
631  params->array(), &treeStats.traversalLeafObjectTests );
632  if( leaf_out || MB_SUCCESS != rval ) return rval;
633  }
634  else
635  {
636  // leaf node within distance; return in list
637  result_list.push_back( this_set );
638  }
639  }
640 
641  if( !result_list.empty() ) leaf_out = result_list[0];
642  if( multiple_leaves && result_list.size() > 1 ) *multiple_leaves = true;
643  return MB_SUCCESS;
644 }

References moab::CartVect::array(), child, moab::BoundBox::contains_point(), dim, ErrorCode, moab::ElemEvaluator::find_containing_entity(), get_bounding_box(), moab::TreeStats::leavesVisited, MB_SUCCESS, moab::Tree::myEval, moab::Tree::myRoot, myTree, moab::TreeStats::nodesVisited, moab::TreeStats::numTraversals, startSetHandle, moab::TreeStats::traversalLeafObjectTests, and moab::Tree::treeStats.

◆ print()

ErrorCode moab::BVHTree::print ( )
virtual

print various things about this tree

Implements moab::Tree.

Definition at line 740 of file BVHTree.cpp.

741 {
742  int i;
743  std::vector< TreeNode >::iterator it;
744  for( it = myTree.begin(), i = 0; it != myTree.end(); ++it, i++ )
745  {
746  std::cout << "Node " << i << ": dim = " << it->dim << ", child = " << it->child << ", Lmax/Rmin = " << it->Lmax
747  << "/" << it->Rmin << ", box = " << it->box << std::endl;
748  }
749  return MB_SUCCESS;
750 }

References MB_SUCCESS, and myTree.

◆ print_nodes()

ErrorCode moab::BVHTree::print_nodes ( std::vector< Node > &  nodes)
private

Definition at line 728 of file BVHTree.cpp.

729 {
730  int i;
731  std::vector< Node >::iterator it;
732  for( it = nodes.begin(), i = 0; it != nodes.end(); ++it, i++ )
733  {
734  std::cout << "Node " << i << ": dim = " << it->dim << ", child = " << it->child << ", Lmax/Rmin = " << it->Lmax
735  << "/" << it->Rmin << ", box = " << it->box << std::endl;
736  }
737  return MB_SUCCESS;
738 }

References MB_SUCCESS.

◆ reset_tree()

ErrorCode moab::BVHTree::reset_tree ( )
inlinevirtual

Destroy the tree maintained by this object, optionally checking we have the right root.

Parameters
rootIf non-NULL, check that this is the root, return failure if not

Implements moab::Tree.

Definition at line 440 of file BVHTree.hpp.

441 {
442  return delete_tree_sets();
443 }

References moab::Tree::delete_tree_sets().

Referenced by ~BVHTree().

◆ set_interval()

unsigned int moab::BVHTree::set_interval ( BoundBox interval,
std::vector< Bucket >::const_iterator  begin,
std::vector< Bucket >::const_iterator  end 
) const
inlineprivate

Definition at line 362 of file BVHTree.hpp.

365 {
366  bool first = true;
367  unsigned int count = 0;
368  for( std::vector< Bucket >::const_iterator b = begin; b != end; ++b )
369  {
370  const BoundBox& box = b->boundingBox;
371  count += b->mySize;
372  if( b->mySize != 0 )
373  {
374  if( first )
375  {
376  interval = box;
377  first = false;
378  }
379  else
380  interval.update( box );
381  }
382  }
383  return count;
384 }

References moab::GeomUtil::first(), and moab::BoundBox::update().

Referenced by initialize_splits().

Member Data Documentation

◆ entityHandles

Range moab::BVHTree::entityHandles
private

Definition at line 323 of file BVHTree.hpp.

◆ myTree

std::vector< TreeNode > moab::BVHTree::myTree
private

◆ splitsPerDir

int moab::BVHTree::splitsPerDir
private

Definition at line 325 of file BVHTree.hpp.

Referenced by establish_buckets(), find_split(), order_elements(), and parse_options().

◆ startSetHandle

EntityHandle moab::BVHTree::startSetHandle
private

◆ treeName

const char * moab::BVHTree::treeName = "BVHTree"
staticprivate

Definition at line 327 of file BVHTree.hpp.

Referenced by BVHTree().


The documentation for this class was generated from the following files: