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

Class for constructing and querying Hierarchical Oriented Bounding Box trees. More...

#include <OrientedBoxTreeTool.hpp>

+ Collaboration diagram for moab::OrientedBoxTreeTool:

Classes

class  IntRegCtxt
 Default/Base class to provide a context for registering intersections. More...
 
class  Op
 Implement this and pass instance to preorder_traverse. More...
 
struct  SetData
 
struct  Settings
 Misc. knobs controlling tree subdivision. More...
 
class  TrvStats
 Traversal statistics structure. More...
 

Public Types

typedef std::pair< const double *, const double * > IntersectSearchWindow
 This provides the search range for ray intersections, measured relative to the origin of the ray. More...
 

Public Member Functions

 OrientedBoxTreeTool (Interface *i, const char *tag_name=0, bool destroy_created_trees=false)
 
 ~OrientedBoxTreeTool ()
 
ErrorCode build (const Range &entities, EntityHandle &set_handle_out, const Settings *settings=0)
 Build oriented bounding box tree. More...
 
ErrorCode join_trees (const Range &tree_roots, EntityHandle &root_set_out, const Settings *settings=0)
 Build a tree of sets, where each set contains triangles. More...
 
ErrorCode ray_intersect_triangles (std::vector< double > &distances_out, std::vector< EntityHandle > &facets_out, EntityHandle root_set, double tolerance, const double ray_point[3], const double unit_ray_dir[3], const double *ray_length=0, TrvStats *accum=0)
 Intersect a ray with the triangles contained within the tree. More...
 
ErrorCode ray_intersect_boxes (Range &boxes_out, EntityHandle root_set, double tolerance, const double ray_point[3], const double unit_ray_dir[3], const double *ray_length=0, TrvStats *accum=0)
 Intersect ray with tree. More...
 
ErrorCode ray_intersect_triangles (std::vector< double > &intersection_distances_out, std::vector< EntityHandle > &intersection_facets_out, const Range &leaf_boxes_containing_tris, double tolerance, const double ray_point[3], const double unit_ray_dir[3], const double *ray_length=0, unsigned int *raytri_test_count=0)
 Intersect ray with triangles contained in passed MBENTITYSETs. More...
 
ErrorCode ray_intersect_sets (std::vector< double > &distances_out, std::vector< EntityHandle > &sets_out, std::vector< EntityHandle > &facets_out, EntityHandle root_set, double tolerance, const double ray_point[3], const double unit_ray_dir[3], IntersectSearchWindow &search_win, IntRegCtxt &register_intersection, TrvStats *accum=0)
 Intersect a ray with the triangles contained within the tree. More...
 
ErrorCode ray_intersect_sets (std::vector< double > &distances_out, std::vector< EntityHandle > &sets_out, std::vector< EntityHandle > &facets_out, EntityHandle root_set, double tolerance, const double ray_point[3], const double unit_ray_dir[3], const double *ray_length=0, TrvStats *accum=0)
 
ErrorCode ray_intersect_sets (EntityHandle root_set, double tolerance, const double ray_point[3], const double unit_ray_dir[3], IntersectSearchWindow &search_win, IntRegCtxt &register_intersection, TrvStats *accum=0)
 
ErrorCode closest_to_location (const double *point, EntityHandle tree_root, double *point_out, EntityHandle &facet_out, EntityHandle *set_out=0, TrvStats *accum=0)
 Find closest surface, facet in surface, and location on facet. More...
 
ErrorCode closest_to_location (const double *point, EntityHandle tree_root, double tolerance, std::vector< EntityHandle > &facets_out, std::vector< EntityHandle > *sets_out=0, TrvStats *accum=0)
 Find closest facet(s) to input position. More...
 
ErrorCode sphere_intersect_triangles (const double *center, double radius, EntityHandle tree_root, std::vector< EntityHandle > &facets_out, std::vector< EntityHandle > *sets_out=0, TrvStats *accum=0)
 Find facets intersected by a sphere. More...
 
ErrorCode get_close_tris (CartVect int_pt, double tol, const EntityHandle *rootSet, const EntityHandle *geomVol, const Tag *senseTag, std::vector< EntityHandle > &close_tris, std::vector< int > &close_senses)
 
ErrorCode box (EntityHandle node_set, double center[3], double axis1[3], double axis2[3], double axis3[3])
 Get oriented box at node in tree. More...
 
ErrorCode delete_tree (EntityHandle root_set)
 
ErrorCode remove_root (EntityHandle root_set)
 Remove obb tree root from the Oriented Box Tree Tool data structure. More...
 
void print (EntityHandle tree_root_set, std::ostream &stream, bool list_contents=false, const char *id_tag_name=0)
 Print out tree. More...
 
ErrorCode stats (EntityHandle tree_root_set, std::ostream &stream)
 Print tree statistics. More...
 
ErrorCode stats (EntityHandle set, unsigned &entities_in_tree, double &root_volume, double &tot_node_volume, double &tot_to_root_volume, unsigned &tree_height, unsigned &node_count, unsigned &num_leaves)
 Get tree statistics. More...
 
ErrorCode preorder_traverse (EntityHandle root_set, Op &operation, TrvStats *accum=0)
 Visitor pattern - do operation for each tree node. More...
 
Interfaceget_moab_instance () const
 
ErrorCode box (EntityHandle node_set, OrientedBox &box)
 Get oriented box at node in tree. More...
 

Private Member Functions

ErrorCode build_tree (const Range &entities, EntityHandle &set, int depth, const Settings &settings)
 
ErrorCode build_sets (std::list< SetData > &sets, EntityHandle &node_set, int depth, const Settings &settings)
 
ErrorCode recursive_stats (OrientedBoxTreeTool *tool, Interface *instance, EntityHandle set, int depth, StatData &data, unsigned &count_out, CartVect &dimensions_out)
 

Private Attributes

Interfaceinstance
 
Tag tagHandle
 
bool cleanUpTrees
 
std::vector< EntityHandlecreatedTrees
 

Detailed Description

Class for constructing and querying Hierarchical Oriented Bounding Box trees.

Definition at line 42 of file OrientedBoxTreeTool.hpp.

Member Typedef Documentation

◆ IntersectSearchWindow

typedef std::pair< const double*, const double* > moab::OrientedBoxTreeTool::IntersectSearchWindow

This provides the search range for ray intersections, measured relative to the origin of the ray.

first: nonnegative limit for search second: negative limit for search

These are const double* so that the window is always defined by pointing to other quantities, but it is not posible to change those quantities via the window.

Definition at line 55 of file OrientedBoxTreeTool.hpp.

Constructor & Destructor Documentation

◆ OrientedBoxTreeTool()

moab::OrientedBoxTreeTool::OrientedBoxTreeTool ( Interface i,
const char *  tag_name = 0,
bool  destroy_created_trees = false 
)

Definition at line 49 of file OrientedBoxTreeTool.cpp.

50  : instance( i ), cleanUpTrees( destroy_created_trees )
51 {
52  if( !tag_name ) tag_name = DEFAULT_TAG_NAME;
54  if( MB_SUCCESS != rval ) tagHandle = 0;
55 }

References moab::DEFAULT_TAG_NAME, ErrorCode, instance, MB_SUCCESS, moab::OrientedBox::tag_handle(), and tagHandle.

◆ ~OrientedBoxTreeTool()

moab::OrientedBoxTreeTool::~OrientedBoxTreeTool ( )

Definition at line 57 of file OrientedBoxTreeTool.cpp.

58 {
59  if( !cleanUpTrees ) return;
60 
61  while( !createdTrees.empty() )
62  {
63  EntityHandle tree = createdTrees.back();
64  // make sure this is a tree (rather than some other, stale handle)
65  const void* data_ptr = 0;
66  ErrorCode rval = instance->tag_get_by_ptr( tagHandle, &tree, 1, &data_ptr );
67  if( MB_SUCCESS == rval ) rval = delete_tree( tree );
68  if( MB_SUCCESS != rval ) createdTrees.pop_back();
69  }
70 }

References cleanUpTrees, createdTrees, delete_tree(), ErrorCode, instance, MB_SUCCESS, moab::Interface::tag_get_by_ptr(), and tagHandle.

Member Function Documentation

◆ box() [1/2]

ErrorCode moab::OrientedBoxTreeTool::box ( EntityHandle  node_set,
double  center[3],
double  axis1[3],
double  axis2[3],
double  axis3[3] 
)

Get oriented box at node in tree.

Get the oriented box for a node in an oriented bounding box tree.

Definition at line 91 of file OrientedBoxTreeTool.cpp.

96 {
97  OrientedBox obb;
98  ErrorCode rval = this->box( set, obb );
99  obb.center.get( center );
100  obb.scaled_axis( 0 ).get( axis1 );
101  obb.scaled_axis( 1 ).get( axis2 );
102  obb.scaled_axis( 2 ).get( axis3 );
103  return rval;
104 }

References moab::OrientedBox::center, center(), ErrorCode, moab::CartVect::get(), and moab::OrientedBox::scaled_axis().

Referenced by closest_to_location(), moab::GeomTopoTool::get_obb(), moab::FBEngine::getEntBoundBox(), TriStats::leaf(), main(), moab::TreeNodePrinter::print_geometry(), recursive_stats(), sphere_intersect_triangles(), moab::split_box(), moab::split_sets(), TriStats::TriStats(), moab::RayIntersector::visit(), moab::RayIntersectSets::visit(), and TriCounter::visit().

◆ box() [2/2]

ErrorCode moab::OrientedBoxTreeTool::box ( EntityHandle  node_set,
OrientedBox box 
)

Get oriented box at node in tree.

Get the oriented box for a node in an oriented bounding box tree.

NOTE: This function is provided for internal MOAB use only. The definition of OrientedBox is not available as a part of the MOAB API

Definition at line 86 of file OrientedBoxTreeTool.cpp.

87 {
88  return instance->tag_get_data( tagHandle, &set, 1, &obb );
89 }

References instance, moab::Interface::tag_get_data(), and tagHandle.

◆ build()

ErrorCode moab::OrientedBoxTreeTool::build ( const Range entities,
EntityHandle set_handle_out,
const Settings settings = 0 
)

Build oriented bounding box tree.

Build an oriented bounding box tree.

Parameters
entitiesA list of either vertices or 2-D elements (not both) for which to build a tree.
set_handle_outA handle for the entity set representing the root of the tree.

Definition at line 115 of file OrientedBoxTreeTool.cpp.

116 {
117  if( !entities.all_of_dimension( 2 ) ) return MB_TYPE_OUT_OF_RANGE;
118  if( settings && !settings->valid() ) return MB_FAILURE;
119 
120  return build_tree( entities, set_handle_out, 0, settings ? *settings : Settings() );
121 }

References build_tree(), entities, MB_TYPE_OUT_OF_RANGE, and moab::OrientedBoxTreeTool::Settings::valid().

Referenced by moab::GeomTopoTool::construct_obb_tree(), and main().

◆ build_sets()

ErrorCode moab::OrientedBoxTreeTool::build_sets ( std::list< SetData > &  sets,
EntityHandle node_set,
int  depth,
const Settings settings 
)
private

Definition at line 340 of file OrientedBoxTreeTool.cpp.

344 {
345  ErrorCode rval;
346  int count = sets.size();
347  if( 0 == count ) return MB_FAILURE;
348 
349  // calculate box
350  OrientedBox obox;
351 
352  // make vector go out of scope when done, so memory is released
353  {
354  Range elems;
355  std::vector< OrientedBox::CovarienceData > data( sets.size() );
356  data.clear();
357  for( std::list< SetData >::iterator i = sets.begin(); i != sets.end(); ++i )
358  {
359  data.push_back( i->box_data );
360  rval = instance->get_entities_by_dimension( i->handle, 2, elems, true );
361  if( MB_SUCCESS != rval ) return rval;
362  }
363 
364  Range points;
365  rval = instance->get_adjacencies( elems, 0, false, points, Interface::UNION );
366  if( MB_SUCCESS != rval ) return rval;
367 
368  rval = OrientedBox::compute_from_covariance_data( obox, instance, &data[0], data.size(), points );
369  if( MB_SUCCESS != rval ) return rval;
370  }
371 
372  // If only one set in list...
373  if( count == 1 )
374  {
375  node_set = sets.front().handle;
376  return instance->tag_set_data( tagHandle, &node_set, 1, &obox );
377  }
378 
379  // create an entity set for the tree node
380  rval = instance->create_meshset( settings.set_options, node_set );
381  if( MB_SUCCESS != rval ) return rval;
382 
383  rval = instance->tag_set_data( tagHandle, &node_set, 1, &obox );
384  if( MB_SUCCESS != rval )
385  {
386  delete_tree( node_set );
387  return rval;
388  }
389 
390  double best_ratio = 2.0;
391  std::list< SetData > best_left_list, best_right_list;
392  for( int axis = 0; axis < 2; ++axis )
393  {
394  std::list< SetData > left_list, right_list;
395  rval = split_sets( instance, obox, axis, sets, left_list, right_list );
396  if( MB_SUCCESS != rval )
397  {
398  delete_tree( node_set );
399  return rval;
400  }
401 
402  double ratio = fabs( (double)right_list.size() - left_list.size() ) / sets.size();
403 
404  if( ratio < best_ratio )
405  {
406  best_ratio = ratio;
407  best_left_list.swap( left_list );
408  best_right_list.swap( right_list );
409  }
410  }
411 
412  // We must subdivide the list of sets, because we want to guarantee that
413  // there is a node in the tree corresponding to each of the sets. So if
414  // we couldn't find a usable split plane, just split them in an arbitrary
415  // manner.
416  if( best_left_list.empty() || best_right_list.empty() )
417  {
418  best_left_list.clear();
419  best_right_list.clear();
420  std::list< SetData >* lists[2] = { &best_left_list, &best_right_list };
421  int i = 0;
422  while( !sets.empty() )
423  {
424  lists[i]->push_back( sets.front() );
425  sets.pop_front();
426  i = 1 - i;
427  }
428  }
429  else
430  {
431  sets.clear(); // release memory before recursion
432  }
433 
434  // Create child sets
435 
436  EntityHandle child = 0;
437 
438  rval = build_sets( best_left_list, child, depth + 1, settings );
439  if( MB_SUCCESS != rval )
440  {
441  delete_tree( node_set );
442  return rval;
443  }
444  rval = instance->add_child_meshset( node_set, child );
445  if( MB_SUCCESS != rval )
446  {
447  delete_tree( node_set );
448  delete_tree( child );
449  return rval;
450  }
451 
452  rval = build_sets( best_right_list, child, depth + 1, settings );
453  if( MB_SUCCESS != rval )
454  {
455  delete_tree( node_set );
456  return rval;
457  }
458  rval = instance->add_child_meshset( node_set, child );
459  if( MB_SUCCESS != rval )
460  {
461  delete_tree( node_set );
462  delete_tree( child );
463  return rval;
464  }
465 
466  return MB_SUCCESS;
467 }

References moab::Interface::add_child_meshset(), child, moab::OrientedBox::compute_from_covariance_data(), moab::Interface::create_meshset(), delete_tree(), ErrorCode, moab::Interface::get_adjacencies(), moab::Interface::get_entities_by_dimension(), instance, MB_SUCCESS, moab::OrientedBoxTreeTool::Settings::set_options, moab::split_sets(), moab::Interface::tag_set_data(), tagHandle, and moab::Interface::UNION.

Referenced by join_trees().

◆ build_tree()

ErrorCode moab::OrientedBoxTreeTool::build_tree ( const Range entities,
EntityHandle set,
int  depth,
const Settings settings 
)
private

Definition at line 204 of file OrientedBoxTreeTool.cpp.

208 {
209  OrientedBox tmp_box;
210  ErrorCode rval;
211 
212  if( entities.empty() )
213  {
214  Matrix3 axis;
215  tmp_box = OrientedBox( axis, CartVect( 0. ) );
216  }
217  else
218  {
220  if( MB_SUCCESS != rval ) return rval;
221  }
222 
223  // create an entity set for the tree node
224  rval = instance->create_meshset( settings.set_options, set );
225  if( MB_SUCCESS != rval ) return rval;
226 
227  rval = instance->tag_set_data( tagHandle, &set, 1, &tmp_box );
228  if( MB_SUCCESS != rval )
229  {
230  delete_tree( set );
231  return rval;
232  }
233 
234  // check if should create children
235  bool leaf = true;
236  ++depth;
237  if( ( !settings.max_depth || depth < settings.max_depth ) &&
238  entities.size() > (unsigned)settings.max_leaf_entities )
239  {
240  // try splitting with planes normal to each axis of the box
241  // until we find an acceptable split
242  double best_ratio = settings.worst_split_ratio; // worst case ratio
243  Range best_left_list, best_right_list;
244  // Axes are sorted from shortest to longest, so search backwards
245  for( int axis = 2; best_ratio > settings.best_split_ratio && axis >= 0; --axis )
246  {
247  Range left_list, right_list;
248 
249  rval = split_box( instance, tmp_box, axis, entities, left_list, right_list );
250  if( MB_SUCCESS != rval )
251  {
252  delete_tree( set );
253  return rval;
254  }
255 
256  double ratio = fabs( (double)right_list.size() - left_list.size() ) / entities.size();
257 
258  if( ratio < best_ratio )
259  {
260  best_ratio = ratio;
261  best_left_list.swap( left_list );
262  best_right_list.swap( right_list );
263  }
264  }
265 
266  // create children
267  if( !best_left_list.empty() )
268  {
269  EntityHandle child = 0;
270 
271  rval = build_tree( best_left_list, child, depth, settings );
272  if( MB_SUCCESS != rval )
273  {
274  delete_tree( set );
275  return rval;
276  }
277  rval = instance->add_child_meshset( set, child );
278  if( MB_SUCCESS != rval )
279  {
280  delete_tree( set );
281  delete_tree( child );
282  return rval;
283  }
284 
285  rval = build_tree( best_right_list, child, depth, settings );
286  if( MB_SUCCESS != rval )
287  {
288  delete_tree( set );
289  return rval;
290  }
291  rval = instance->add_child_meshset( set, child );
292  if( MB_SUCCESS != rval )
293  {
294  delete_tree( set );
295  delete_tree( child );
296  return rval;
297  }
298 
299  leaf = false;
300  }
301  }
302 
303  if( leaf )
304  {
305  rval = instance->add_entities( set, entities );
306  if( MB_SUCCESS != rval )
307  {
308  delete_tree( set );
309  return rval;
310  }
311  }
312 
313  createdTrees.push_back( set );
314  return MB_SUCCESS;
315 }

References moab::Interface::add_child_meshset(), moab::Interface::add_entities(), moab::OrientedBoxTreeTool::Settings::best_split_ratio, child, moab::OrientedBox::compute_from_2d_cells(), moab::Interface::create_meshset(), createdTrees, delete_tree(), moab::Range::empty(), entities, ErrorCode, instance, moab::OrientedBoxTreeTool::Settings::max_depth, moab::OrientedBoxTreeTool::Settings::max_leaf_entities, MB_SUCCESS, moab::OrientedBoxTreeTool::Settings::set_options, moab::Range::size(), moab::split_box(), moab::Range::swap(), moab::Interface::tag_set_data(), tagHandle, and moab::OrientedBoxTreeTool::Settings::worst_split_ratio.

Referenced by build().

◆ closest_to_location() [1/2]

ErrorCode moab::OrientedBoxTreeTool::closest_to_location ( const double *  point,
EntityHandle  tree_root,
double *  point_out,
EntityHandle facet_out,
EntityHandle set_out = 0,
TrvStats accum = 0 
)

Find closest surface, facet in surface, and location on facet.

Find the closest location in the tree to the specified location.

Parameters
pointLocation to search from
point_outClosest location on closest facet
facet_outClosest 2D element to input position
set_outSet containing closest facet. 0 if tree was not constructed using 'set_build'

Definition at line 1118 of file OrientedBoxTreeTool.cpp.

1124 {
1125  ErrorCode rval;
1126  const CartVect loc( point );
1127  double smallest_dist_sqr = std::numeric_limits< double >::max();
1128 
1129  EntityHandle current_set = 0;
1130  Range sets;
1131  std::vector< EntityHandle > children( 2 );
1132  std::vector< double > coords;
1133  std::vector< OBBTreeCPFrame > stack;
1134  int max_depth = -1;
1135 
1136  stack.push_back( OBBTreeCPFrame( 0.0, root, current_set, 0 ) );
1137 
1138  while( !stack.empty() )
1139  {
1140 
1141  // pop from top of stack
1142  EntityHandle node = stack.back().node;
1143  double dist_sqr = stack.back().dist_sqr;
1144  current_set = stack.back().mset;
1145  int current_depth = stack.back().depth;
1146  stack.pop_back();
1147 
1148  // If current best result is closer than the box, skip this tree node.
1149  if( dist_sqr > smallest_dist_sqr ) continue;
1150 
1151  // increment traversal statistics.
1152  if( accum )
1153  {
1154  accum->increment( current_depth );
1155  max_depth = std::max( max_depth, current_depth );
1156  }
1157 
1158  // Check if this node has a set associated with it
1159  if( set_out && !current_set )
1160  {
1161  sets.clear();
1162  rval = instance->get_entities_by_type( node, MBENTITYSET, sets );
1163  if( MB_SUCCESS != rval ) return rval;
1164  if( !sets.empty() )
1165  {
1166  if( sets.size() != 1 ) return MB_MULTIPLE_ENTITIES_FOUND;
1167  current_set = sets.front();
1168  }
1169  }
1170 
1171  // Get child boxes
1172  children.clear();
1173  rval = instance->get_child_meshsets( node, children );
1174  if( MB_SUCCESS != rval ) return rval;
1175 
1176  // if not a leaf node
1177  if( !children.empty() )
1178  {
1179  if( children.size() != 2 ) return MB_MULTIPLE_ENTITIES_FOUND;
1180 
1181  // get boxes
1182  OrientedBox box1, box2;
1183  rval = box( children[0], box1 );
1184  if( MB_SUCCESS != rval ) return rval;
1185  rval = box( children[1], box2 );
1186  if( MB_SUCCESS != rval ) return rval;
1187 
1188  // get distance from each box
1189  CartVect pt1, pt2;
1190  box1.closest_location_in_box( loc, pt1 );
1191  box2.closest_location_in_box( loc, pt2 );
1192  pt1 -= loc;
1193  pt2 -= loc;
1194  const double dsqr1 = pt1 % pt1;
1195  const double dsqr2 = pt2 % pt2;
1196 
1197  // push children on tree such that closer one is on top
1198  if( dsqr1 < dsqr2 )
1199  {
1200  stack.push_back( OBBTreeCPFrame( dsqr2, children[1], current_set, current_depth + 1 ) );
1201  stack.push_back( OBBTreeCPFrame( dsqr1, children[0], current_set, current_depth + 1 ) );
1202  }
1203  else
1204  {
1205  stack.push_back( OBBTreeCPFrame( dsqr1, children[0], current_set, current_depth + 1 ) );
1206  stack.push_back( OBBTreeCPFrame( dsqr2, children[1], current_set, current_depth + 1 ) );
1207  }
1208  }
1209  else
1210  { // LEAF NODE
1211  if( accum )
1212  {
1213  accum->increment_leaf( current_depth );
1214  }
1215 
1216  Range facets;
1217  rval = instance->get_entities_by_dimension( node, 2, facets );
1218  if( MB_SUCCESS != rval ) return rval;
1219 
1220  const EntityHandle* conn = NULL;
1221  int len = 0;
1222  CartVect tmp, diff;
1223  for( Range::iterator i = facets.begin(); i != facets.end(); ++i )
1224  {
1225  rval = instance->get_connectivity( *i, conn, len, true );
1226  if( MB_SUCCESS != rval ) return rval;
1227 
1228  coords.resize( 3 * len );
1229  rval = instance->get_coords( conn, len, &coords[0] );
1230  if( MB_SUCCESS != rval ) return rval;
1231 
1232  if( len == 3 )
1233  GeomUtil::closest_location_on_tri( loc, (CartVect*)( &coords[0] ), tmp );
1234  else
1235  GeomUtil::closest_location_on_polygon( loc, (CartVect*)( &coords[0] ), len, tmp );
1236 
1237  diff = tmp - loc;
1238  dist_sqr = diff % diff;
1239  if( dist_sqr < smallest_dist_sqr )
1240  {
1241  smallest_dist_sqr = dist_sqr;
1242  facet_out = *i;
1243  tmp.get( point_out );
1244  if( set_out ) *set_out = current_set;
1245  }
1246  }
1247  } // LEAF NODE
1248  }
1249 
1250  if( accum )
1251  {
1252  accum->end_traversal( max_depth );
1253  }
1254 
1255  return MB_SUCCESS;
1256 }

References moab::Range::begin(), box(), children, moab::Range::clear(), moab::OrientedBox::closest_location_in_box(), moab::GeomUtil::closest_location_on_polygon(), moab::GeomUtil::closest_location_on_tri(), moab::Range::empty(), moab::Range::end(), moab::OrientedBoxTreeTool::TrvStats::end_traversal(), ErrorCode, moab::Range::front(), moab::CartVect::get(), moab::Interface::get_child_meshsets(), moab::Interface::get_connectivity(), moab::Interface::get_coords(), moab::Interface::get_entities_by_dimension(), moab::Interface::get_entities_by_type(), moab::OrientedBoxTreeTool::TrvStats::increment(), moab::OrientedBoxTreeTool::TrvStats::increment_leaf(), instance, MB_MULTIPLE_ENTITIES_FOUND, MB_SUCCESS, MBENTITYSET, and moab::Range::size().

Referenced by moab::GeomQueryTool::closest_to_location(), moab::GeomQueryTool::get_normal(), moab::FBEngine::getEntClosestPt(), moab::FBEngine::getEntNrmlXYZ(), moab::SmoothFace::project_to_facets_main(), and moab::GeomQueryTool::test_volume_boundary().

◆ closest_to_location() [2/2]

ErrorCode moab::OrientedBoxTreeTool::closest_to_location ( const double *  point,
EntityHandle  tree_root,
double  tolerance,
std::vector< EntityHandle > &  facets_out,
std::vector< EntityHandle > *  sets_out = 0,
TrvStats accum = 0 
)

Find closest facet(s) to input position.

Find the closest location(s) in the tree to the specified location.

Parameters
pointLocation to search from
facets_outClosest 2D elements to input position are appended to this list
sets_outIf non-null, sets owning facets are appended to this list.

Definition at line 1258 of file OrientedBoxTreeTool.cpp.

1264 {
1265  ErrorCode rval;
1266  const CartVect loc( point );
1267  double smallest_dist_sqr = std::numeric_limits< double >::max();
1268  double smallest_dist = smallest_dist_sqr;
1269 
1270  EntityHandle current_set = 0;
1271  Range sets;
1272  std::vector< EntityHandle > children( 2 );
1273  std::vector< double > coords;
1274  std::vector< OBBTreeCPFrame > stack;
1275  int max_depth = -1;
1276 
1277  stack.push_back( OBBTreeCPFrame( 0.0, root, current_set, 0 ) );
1278 
1279  while( !stack.empty() )
1280  {
1281 
1282  // pop from top of stack
1283  EntityHandle node = stack.back().node;
1284  double dist_sqr = stack.back().dist_sqr;
1285  current_set = stack.back().mset;
1286  int current_depth = stack.back().depth;
1287  stack.pop_back();
1288 
1289  // If current best result is closer than the box, skip this tree node.
1290  if( dist_sqr > smallest_dist_sqr + tolerance ) continue;
1291 
1292  // increment traversal statistics.
1293  if( accum )
1294  {
1295  accum->increment( current_depth );
1296  max_depth = std::max( max_depth, current_depth );
1297  }
1298 
1299  // Check if this node has a set associated with it
1300  if( sets_out && !current_set )
1301  {
1302  sets.clear();
1303  rval = instance->get_entities_by_type( node, MBENTITYSET, sets );
1304  if( MB_SUCCESS != rval ) return rval;
1305  if( !sets.empty() )
1306  {
1307  if( sets.size() != 1 ) return MB_MULTIPLE_ENTITIES_FOUND;
1308  current_set = *sets.begin();
1309  }
1310  }
1311 
1312  // Get child boxes
1313  children.clear();
1314  rval = instance->get_child_meshsets( node, children );
1315  if( MB_SUCCESS != rval ) return rval;
1316 
1317  // if not a leaf node
1318  if( !children.empty() )
1319  {
1320  if( children.size() != 2 ) return MB_MULTIPLE_ENTITIES_FOUND;
1321 
1322  // get boxes
1323  OrientedBox box1, box2;
1324  rval = box( children[0], box1 );
1325  if( MB_SUCCESS != rval ) return rval;
1326  rval = box( children[1], box2 );
1327  if( MB_SUCCESS != rval ) return rval;
1328 
1329  // get distance from each box
1330  CartVect pt1, pt2;
1331  box1.closest_location_in_box( loc, pt1 );
1332  box2.closest_location_in_box( loc, pt2 );
1333  pt1 -= loc;
1334  pt2 -= loc;
1335  const double dsqr1 = pt1 % pt1;
1336  const double dsqr2 = pt2 % pt2;
1337 
1338  // push children on tree such that closer one is on top
1339  if( dsqr1 < dsqr2 )
1340  {
1341  stack.push_back( OBBTreeCPFrame( dsqr2, children[1], current_set, current_depth + 1 ) );
1342  stack.push_back( OBBTreeCPFrame( dsqr1, children[0], current_set, current_depth + 1 ) );
1343  }
1344  else
1345  {
1346  stack.push_back( OBBTreeCPFrame( dsqr1, children[0], current_set, current_depth + 1 ) );
1347  stack.push_back( OBBTreeCPFrame( dsqr2, children[1], current_set, current_depth + 1 ) );
1348  }
1349  }
1350  else
1351  { // LEAF NODE
1352  if( accum )
1353  {
1354  accum->increment_leaf( current_depth );
1355  }
1356 
1357  Range facets;
1358  rval = instance->get_entities_by_dimension( node, 2, facets );
1359  if( MB_SUCCESS != rval ) return rval;
1360 
1361  const EntityHandle* conn = NULL;
1362  int len = 0;
1363  CartVect tmp, diff;
1364  for( Range::iterator i = facets.begin(); i != facets.end(); ++i )
1365  {
1366  rval = instance->get_connectivity( *i, conn, len, true );
1367  if( MB_SUCCESS != rval ) return rval;
1368 
1369  coords.resize( 3 * len );
1370  rval = instance->get_coords( conn, len, &coords[0] );
1371  if( MB_SUCCESS != rval ) return rval;
1372 
1373  if( len == 3 )
1374  GeomUtil::closest_location_on_tri( loc, (CartVect*)( &coords[0] ), tmp );
1375  else
1376  GeomUtil::closest_location_on_polygon( loc, (CartVect*)( &coords[0] ), len, tmp );
1377 
1378  diff = tmp - loc;
1379  dist_sqr = diff % diff;
1380  if( dist_sqr < smallest_dist_sqr )
1381  {
1382  if( 0.5 * dist_sqr < 0.5 * smallest_dist_sqr + tolerance * ( 0.5 * tolerance - smallest_dist ) )
1383  {
1384  facets_out.clear();
1385  if( sets_out ) sets_out->clear();
1386  }
1387  smallest_dist_sqr = dist_sqr;
1388  smallest_dist = sqrt( smallest_dist_sqr );
1389  // put closest result at start of lists
1390  facets_out.push_back( *i );
1391  std::swap( facets_out.front(), facets_out.back() );
1392  if( sets_out )
1393  {
1394  sets_out->push_back( current_set );
1395  std::swap( sets_out->front(), sets_out->back() );
1396  }
1397  }
1398  else if( dist_sqr <= smallest_dist_sqr + tolerance * ( tolerance + 2 * smallest_dist ) )
1399  {
1400  facets_out.push_back( *i );
1401  if( sets_out ) sets_out->push_back( current_set );
1402  }
1403  }
1404  } // LEAF NODE
1405  }
1406 
1407  if( accum )
1408  {
1409  accum->end_traversal( max_depth );
1410  }
1411 
1412  return MB_SUCCESS;
1413 }

References moab::Range::begin(), box(), children, moab::Range::clear(), moab::OrientedBox::closest_location_in_box(), moab::GeomUtil::closest_location_on_polygon(), moab::GeomUtil::closest_location_on_tri(), moab::Range::empty(), moab::Range::end(), moab::OrientedBoxTreeTool::TrvStats::end_traversal(), ErrorCode, moab::Interface::get_child_meshsets(), moab::Interface::get_connectivity(), moab::Interface::get_coords(), moab::Interface::get_entities_by_dimension(), moab::Interface::get_entities_by_type(), moab::OrientedBoxTreeTool::TrvStats::increment(), moab::OrientedBoxTreeTool::TrvStats::increment_leaf(), instance, MB_MULTIPLE_ENTITIES_FOUND, MB_SUCCESS, MBENTITYSET, moab::Range::size(), and moab::tolerance.

◆ delete_tree()

ErrorCode moab::OrientedBoxTreeTool::delete_tree ( EntityHandle  root_set)

Definition at line 469 of file OrientedBoxTreeTool.cpp.

470 {
471  std::vector< EntityHandle > children;
472  ErrorCode rval = instance->get_child_meshsets( set, children, 0 );
473  if( MB_SUCCESS != rval ) return rval;
474 
475  createdTrees.erase( std::remove( createdTrees.begin(), createdTrees.end(), set ), createdTrees.end() );
476  children.insert( children.begin(), set );
477  return instance->delete_entities( &children[0], children.size() );
478 }

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

Referenced by build_sets(), build_tree(), and ~OrientedBoxTreeTool().

◆ get_close_tris()

ErrorCode moab::OrientedBoxTreeTool::get_close_tris ( CartVect  int_pt,
double  tol,
const EntityHandle rootSet,
const EntityHandle geomVol,
const Tag senseTag,
std::vector< EntityHandle > &  close_tris,
std::vector< int > &  close_senses 
)

Definition at line 845 of file OrientedBoxTreeTool.cpp.

852 {
853  std::vector< EntityHandle > close_surfs;
854  ErrorCode rval = sphere_intersect_triangles( int_pt.array(), tol, *rootSet, close_tris, &close_surfs );
855  assert( MB_SUCCESS == rval );
856  if( MB_SUCCESS != rval ) return rval;
857 
858  // for each surface, get the surf sense wrt parent volume
859  close_senses.resize( close_surfs.size() );
860  for( unsigned i = 0; i < close_surfs.size(); ++i )
861  {
862  EntityHandle vols[2];
863  rval = get_moab_instance()->tag_get_data( *senseTag, &( close_surfs[i] ), 1, vols );
864  assert( MB_SUCCESS == rval );
865  if( MB_SUCCESS != rval ) return rval;
866  if( vols[0] == vols[1] )
867  {
868  std::cerr << "error: surf has positive and negative sense wrt same volume" << std::endl;
869  return MB_FAILURE;
870  }
871  if( *geomVol == vols[0] )
872  {
873  close_senses[i] = 1;
874  }
875  else if( *geomVol == vols[1] )
876  {
877  close_senses[i] = -1;
878  }
879  else
880  {
881  return MB_FAILURE;
882  }
883  }
884 
885  return MB_SUCCESS;
886 }

References moab::CartVect::array(), ErrorCode, get_moab_instance(), MB_SUCCESS, sphere_intersect_triangles(), and moab::Interface::tag_get_data().

Referenced by moab::GQT_IntRegCtxt::register_intersection().

◆ get_moab_instance()

Interface* moab::OrientedBoxTreeTool::get_moab_instance ( ) const
inline

◆ join_trees()

ErrorCode moab::OrientedBoxTreeTool::join_trees ( const Range tree_roots,
EntityHandle root_set_out,
const Settings settings = 0 
)

Build a tree of sets, where each set contains triangles.

Build a tree of sets. Each set must contain at least one triangle to define its geometry. Each passed set will become a leaf of the OBB tree. Settings controlling tree depth are ignored by this method. The tree will be as deep as it needs to be for each input set to be a leaf.

To build a tree representing the surfaces of a geometric volume, 1) Build an OBB tree for each surface using the 'build' method 2) Add each surface to the contents of the resulting OBB tree root set 3) Build a tree from all the surface OBB tree root sets using this method to get a combined tree for the volume.

Definition at line 123 of file OrientedBoxTreeTool.cpp.

124 {
125  if( !sets.all_of_type( MBENTITYSET ) ) return MB_TYPE_OUT_OF_RANGE;
126  if( settings && !settings->valid() ) return MB_FAILURE;
127 
128  // Build initial set data list.
129  std::list< SetData > data;
130  for( Range::const_iterator i = sets.begin(); i != sets.end(); ++i )
131  {
132  Range elements;
133  ErrorCode rval = instance->get_entities_by_dimension( *i, 2, elements, true );
134  if( MB_SUCCESS != rval ) return rval;
135  if( elements.empty() ) continue;
136 
137  data.push_back( SetData() );
138  SetData& set_data = data.back();
139  set_data.handle = *i;
140  rval = OrientedBox::covariance_data_from_tris( set_data.box_data, instance, elements );
141  if( MB_SUCCESS != rval ) return rval;
142  }
143 
144  ErrorCode result = build_sets( data, set_handle_out, 0, settings ? *settings : Settings() );
145  if( MB_SUCCESS != result ) return result;
146 
147  for( Range::reverse_iterator i = sets.rbegin(); i != sets.rend(); ++i )
148  {
149  createdTrees.erase( std::remove( createdTrees.begin(), createdTrees.end(), *i ), createdTrees.end() );
150  }
151  createdTrees.push_back( set_handle_out );
152  return MB_SUCCESS;
153 }

References moab::Range::all_of_type(), moab::Range::begin(), moab::OrientedBoxTreeTool::SetData::box_data, build_sets(), moab::OrientedBox::covariance_data_from_tris(), createdTrees, moab::Range::empty(), moab::Range::end(), ErrorCode, moab::Interface::get_entities_by_dimension(), moab::OrientedBoxTreeTool::SetData::handle, instance, MB_SUCCESS, MB_TYPE_OUT_OF_RANGE, MBENTITYSET, moab::Range::rbegin(), moab::Range::rend(), and moab::OrientedBoxTreeTool::Settings::valid().

Referenced by moab::GeomTopoTool::construct_obb_tree(), and moab::GeomTopoTool::construct_obb_trees().

◆ preorder_traverse()

ErrorCode moab::OrientedBoxTreeTool::preorder_traverse ( EntityHandle  root_set,
Op operation,
TrvStats accum = 0 
)

Visitor pattern - do operation for each tree node.

Do a preorder traversal of the tree, calling the method in the passed operation instance for each node in the tree. Parent node is visited before either child (pre-order traversal). If operator method passes back the 'descend' argument as false, traversal will not descend to the children of the current node.

Definition at line 498 of file OrientedBoxTreeTool.cpp.

499 {
500  ErrorCode rval;
501  std::vector< EntityHandle > children;
502  std::vector< Data > the_stack;
503  Data data = { set, 0 };
504  the_stack.push_back( data );
505  int max_depth = -1;
506 
507  while( !the_stack.empty() )
508  {
509  data = the_stack.back();
510  the_stack.pop_back();
511 
512  // increment traversal statistics
513  if( accum )
514  {
515  accum->increment( data.depth );
516  max_depth = std::max( max_depth, data.depth );
517  }
518 
519  bool descend = true;
520  rval = operation.visit( data.set, data.depth, descend );
521  assert( MB_SUCCESS == rval );
522  if( MB_SUCCESS != rval ) return rval;
523 
524  if( !descend ) continue;
525 
526  children.clear();
527  rval = instance->get_child_meshsets( data.set, children );
528  assert( MB_SUCCESS == rval );
529  if( MB_SUCCESS != rval ) return rval;
530  if( children.empty() )
531  {
532  if( accum )
533  {
534  accum->increment_leaf( data.depth );
535  }
536  rval = operation.leaf( data.set );
537  assert( MB_SUCCESS == rval );
538  if( MB_SUCCESS != rval ) return rval;
539  }
540  else if( children.size() == 2 )
541  {
542  data.depth++;
543  data.set = children[0];
544  the_stack.push_back( data );
545  data.set = children[1];
546  the_stack.push_back( data );
547  }
548  else
550  }
551 
552  if( accum )
553  {
554  accum->end_traversal( max_depth );
555  }
556 
557  return MB_SUCCESS;
558 }

References children, moab::Data::depth, moab::OrientedBoxTreeTool::TrvStats::end_traversal(), ErrorCode, moab::Interface::get_child_meshsets(), moab::OrientedBoxTreeTool::TrvStats::increment(), moab::OrientedBoxTreeTool::TrvStats::increment_leaf(), instance, moab::OrientedBoxTreeTool::Op::leaf(), MB_MULTIPLE_ENTITIES_FOUND, MB_SUCCESS, moab::Data::set, and moab::OrientedBoxTreeTool::Op::visit().

Referenced by obbstat_write(), obbvis_create(), print(), ray_intersect_boxes(), and ray_intersect_sets().

◆ print()

void moab::OrientedBoxTreeTool::print ( EntityHandle  tree_root_set,
std::ostream &  stream,
bool  list_contents = false,
const char *  id_tag_name = 0 
)

Print out tree.

Print the tree to an output stream in a human-readable form.

Parameters
tree_root_setEntity set representing tree root.
list_contentsIf true, list entities in each tree node, If false, just list number of entities.
id_tag_nameIf specified, must be the name of an existing integer tag containing an ID for the entities. Not used if list_contents is false.

Definition at line 1653 of file OrientedBoxTreeTool.cpp.

1654 {
1655  TreeLayoutPrinter op1( str, instance );
1656  TreeNodePrinter op2( str, list, true, tag, this );
1657  ErrorCode r1 = preorder_traverse( set, op1 );
1658  str << std::endl;
1659  ErrorCode r2 = preorder_traverse( set, op2 );
1660  if( r1 != MB_SUCCESS || r2 != MB_SUCCESS )
1661  {
1662  std::cerr << "Errors encountered while printing tree\n";
1663  str << "Errors encountered while printing tree\n";
1664  }
1665 }

References ErrorCode, instance, MB_SUCCESS, and preorder_traverse().

◆ ray_intersect_boxes()

ErrorCode moab::OrientedBoxTreeTool::ray_intersect_boxes ( Range boxes_out,
EntityHandle  root_set,
double  tolerance,
const double  ray_point[3],
const double  unit_ray_dir[3],
const double *  ray_length = 0,
TrvStats accum = 0 
)

Intersect ray with tree.

Return the tree nodes (as MBENTITYSET handles) for the leaf boxes of the tree intersected by a ray.

Parameters
boxes_outThe boxes intersected by the ray.
toleranceThe tolerance to use in intersection checks.
ray_pointThe base point of the ray.
unit_ray_dirThe ray direction vector (must be unit length)
ray_lengthOptional ray length (intersect segment instead of ray.)

Definition at line 815 of file OrientedBoxTreeTool.cpp.

822 {
823  RayIntersector op( this, ray_point, unit_ray_dir, ray_length, tolerance, boxes_out );
824  return preorder_traverse( root_set, op, accum );
825 }

References preorder_traverse(), and moab::tolerance.

Referenced by ray_intersect_triangles().

◆ ray_intersect_sets() [1/3]

ErrorCode moab::OrientedBoxTreeTool::ray_intersect_sets ( EntityHandle  root_set,
double  tolerance,
const double  ray_point[3],
const double  unit_ray_dir[3],
IntersectSearchWindow search_win,
IntRegCtxt register_intersection,
TrvStats accum = 0 
)

Definition at line 1090 of file OrientedBoxTreeTool.cpp.

1098 {
1099  RayIntersectSets op( this, ray_point, unit_ray_dir, tolerance, search_win,
1100  accum ? &( accum->ray_tri_tests_count ) : NULL, int_reg_callback );
1101  return preorder_traverse( root_set, op, accum );
1102 }

References preorder_traverse(), moab::OrientedBoxTreeTool::TrvStats::ray_tri_tests_count, and moab::tolerance.

◆ ray_intersect_sets() [2/3]

ErrorCode moab::OrientedBoxTreeTool::ray_intersect_sets ( std::vector< double > &  distances_out,
std::vector< EntityHandle > &  sets_out,
std::vector< EntityHandle > &  facets_out,
EntityHandle  root_set,
double  tolerance,
const double  ray_point[3],
const double  unit_ray_dir[3],
const double *  ray_length = 0,
TrvStats accum = 0 
)

Definition at line 1059 of file OrientedBoxTreeTool.cpp.

1068 {
1069  IntRegCtxt int_reg_ctxt;
1070 
1071  OrientedBoxTreeTool::IntersectSearchWindow search_win( ray_length, (double*)0 );
1072 
1073  RayIntersectSets op( this, ray_point, unit_ray_dir, tolerance, search_win,
1074  accum ? &( accum->ray_tri_tests_count ) : NULL, int_reg_ctxt );
1075 
1076  ErrorCode rval = preorder_traverse( root_set, op, accum );
1077 
1078  if( MB_SUCCESS != rval )
1079  {
1080  return rval;
1081  }
1082 
1083  distances_out = int_reg_ctxt.get_intersections();
1084  sets_out = int_reg_ctxt.get_sets();
1085  facets_out = int_reg_ctxt.get_facets();
1086 
1087  return MB_SUCCESS;
1088 }

References ErrorCode, moab::OrientedBoxTreeTool::IntRegCtxt::get_facets(), moab::OrientedBoxTreeTool::IntRegCtxt::get_intersections(), moab::OrientedBoxTreeTool::IntRegCtxt::get_sets(), MB_SUCCESS, preorder_traverse(), moab::OrientedBoxTreeTool::TrvStats::ray_tri_tests_count, and moab::tolerance.

◆ ray_intersect_sets() [3/3]

ErrorCode moab::OrientedBoxTreeTool::ray_intersect_sets ( std::vector< double > &  distances_out,
std::vector< EntityHandle > &  sets_out,
std::vector< EntityHandle > &  facets_out,
EntityHandle  root_set,
double  tolerance,
const double  ray_point[3],
const double  unit_ray_dir[3],
IntersectSearchWindow search_win,
IntRegCtxt register_intersection,
TrvStats accum = 0 
)

Intersect a ray with the triangles contained within the tree.

Intersect a ray with the triangles contained in the tree and return the distance at which the intersection occured.

Parameters
distances_outThe output list of intersection points on the ray.
sets_outThe contained set encountered during the tree traversal (see 'set_build'). For the most common use, this is the set corresponding to the geometric surface containing the intersected triangle.
facets_outHandles of intersected triangles corresponding to distances_out
root_setThe MBENTITYSET representing the root of the tree.
toleranceThe tolerance to use in intersection checks.
ray_pointThe base point of the ray.
unit_ray_dirThe ray direction vector (must be unit length)
search_winAn interval that defines the current window in which the an intersection is being sought: (nonnegative, negative)
register_intersectionA context for assessing and registering intersections derived from IntRegCtxt
accumOptional class for tree traversal statistics.

Definition at line 1036 of file OrientedBoxTreeTool.cpp.

1047 {
1048  RayIntersectSets op( this, ray_point, unit_ray_dir, tolerance, search_win,
1049  accum ? &( accum->ray_tri_tests_count ) : NULL, int_reg_callback );
1050  ErrorCode rval = preorder_traverse( root_set, op, accum );
1051 
1052  distances_out = int_reg_callback.get_intersections();
1053  sets_out = int_reg_callback.get_sets();
1054  facets_out = int_reg_callback.get_facets();
1055 
1056  return rval;
1057 }

References ErrorCode, moab::OrientedBoxTreeTool::IntRegCtxt::get_facets(), moab::OrientedBoxTreeTool::IntRegCtxt::get_intersections(), moab::OrientedBoxTreeTool::IntRegCtxt::get_sets(), preorder_traverse(), moab::OrientedBoxTreeTool::TrvStats::ray_tri_tests_count, and moab::tolerance.

Referenced by moab::GeomQueryTool::find_volume(), moab::FBEngine::getPntRayIntsct(), moab::GeomQueryTool::point_in_volume(), moab::GeomQueryTool::ray_fire(), and moab::FBEngine::split_surface_with_direction().

◆ ray_intersect_triangles() [1/2]

ErrorCode moab::OrientedBoxTreeTool::ray_intersect_triangles ( std::vector< double > &  distances_out,
std::vector< EntityHandle > &  facets_out,
EntityHandle  root_set,
double  tolerance,
const double  ray_point[3],
const double  unit_ray_dir[3],
const double *  ray_length = 0,
TrvStats accum = 0 
)

Intersect a ray with the triangles contained within the tree.

Intersect a ray with the triangles contained in the tree and return the distance at which the intersection occured.

Parameters
distances_outThe output list of intersection points on the ray.
facets_outHandles of intersected triangles corresponding to distances_out
root_setThe MBENTITYSET representing the root of the tree.
toleranceThe tolerance to use in intersection checks.
ray_pointThe base point of the ray.
unit_ray_dirThe ray direction vector (must be unit length)
ray_lengthOptional ray length (intersect segment instead of ray.)

Definition at line 796 of file OrientedBoxTreeTool.cpp.

804 {
805  Range boxes;
806  ErrorCode rval;
807 
808  rval = ray_intersect_boxes( boxes, root_set, tolerance, ray_point, unit_ray_dir, ray_length, accum );
809  if( MB_SUCCESS != rval ) return rval;
810 
811  return ray_intersect_triangles( intersection_distances_out, intersection_facets_out, boxes, tolerance, ray_point,
812  unit_ray_dir, ray_length, accum ? &( accum->ray_tri_tests_count ) : NULL );
813 }

References ErrorCode, MB_SUCCESS, ray_intersect_boxes(), moab::OrientedBoxTreeTool::TrvStats::ray_tri_tests_count, and moab::tolerance.

Referenced by main().

◆ ray_intersect_triangles() [2/2]

ErrorCode moab::OrientedBoxTreeTool::ray_intersect_triangles ( std::vector< double > &  intersection_distances_out,
std::vector< EntityHandle > &  intersection_facets_out,
const Range leaf_boxes_containing_tris,
double  tolerance,
const double  ray_point[3],
const double  unit_ray_dir[3],
const double *  ray_length = 0,
unsigned int *  raytri_test_count = 0 
)

Intersect ray with triangles contained in passed MBENTITYSETs.

Parameters
raytri_test_countIf non-NULL, count of ray-triangle intersect tests will be added to the value at which this points.

Definition at line 729 of file OrientedBoxTreeTool.cpp.

737 {
738  ErrorCode rval;
739  intersection_distances_out.clear();
740 #ifdef MB_OBB_USE_VECTOR_QUERIES
741  std::vector< EntityHandle > tris;
742 #endif
743 
744  const CartVect point( ray_point );
745  const CartVect dir( unit_ray_dir );
746 
747  for( Range::iterator b = boxes.begin(); b != boxes.end(); ++b )
748  {
749 #ifndef MB_OBB_USE_VECTOR_QUERIES
750  Range tris;
751 #ifdef MB_OBB_USE_TYPE_QUERIES
752  rval = instance->get_entities_by_type( *b, MBTRI, tris );
753 #else
754  rval = instance->get_entities_by_handle( *b, tris );
755 #endif
756 #else
757  tris.clear();
758  rval = instance->get_entities_by_handle( *b, tris );
759 #endif
760  if( MB_SUCCESS != rval ) return rval;
761  // dump_fragmentation( tris );
762 
763 #ifndef MB_OBB_USE_VECTOR_QUERIES
764  for( Range::iterator t = tris.begin(); t != tris.end(); ++t )
765 #else
766  for( std::vector< EntityHandle >::iterator t = tris.begin(); t != tris.end(); ++t )
767 #endif
768  {
769 #ifndef MB_OBB_USE_TYPE_QUERIES
770  if( TYPE_FROM_HANDLE( *t ) != MBTRI ) continue;
771 #endif
772 
773  const EntityHandle* conn = NULL;
774  int len = 0;
775  rval = instance->get_connectivity( *t, conn, len, true );
776  if( MB_SUCCESS != rval ) return rval;
777 
778  CartVect coords[3];
779  rval = instance->get_coords( conn, 3, coords[0].array() );
780  if( MB_SUCCESS != rval ) return rval;
781 
782  if( raytri_test_count ) *raytri_test_count += 1;
783 
784  double td;
785  if( GeomUtil::plucker_ray_tri_intersect( coords, point, dir, td, ray_length ) )
786  {
787  intersection_distances_out.push_back( td );
788  intersection_facets_out.push_back( *t );
789  }
790  }
791  }
792 
793  return MB_SUCCESS;
794 }

References moab::Range::begin(), moab::Range::clear(), moab::Range::end(), ErrorCode, moab::Interface::get_connectivity(), moab::Interface::get_coords(), moab::Interface::get_entities_by_handle(), moab::Interface::get_entities_by_type(), instance, MB_SUCCESS, MBTRI, moab::GeomUtil::plucker_ray_tri_intersect(), and moab::TYPE_FROM_HANDLE().

◆ recursive_stats()

ErrorCode moab::OrientedBoxTreeTool::recursive_stats ( OrientedBoxTreeTool tool,
Interface instance,
EntityHandle  set,
int  depth,
StatData data,
unsigned &  count_out,
CartVect dimensions_out 
)
private

Definition at line 1813 of file OrientedBoxTreeTool.cpp.

1820 {
1821  ErrorCode rval;
1822  OrientedBox tmp_box;
1823  std::vector< EntityHandle > children( 2 );
1824  unsigned counts[2];
1825  bool isleaf;
1826 
1827  ++data.count;
1828 
1829  rval = tool->box( set, tmp_box );
1830  if( MB_SUCCESS != rval ) return rval;
1831  children.clear();
1832  rval = inst->get_child_meshsets( set, children );
1833  if( MB_SUCCESS != rval ) return rval;
1834  isleaf = children.empty();
1835  if( !isleaf && children.size() != 2 ) return MB_MULTIPLE_ENTITIES_FOUND;
1836 
1837  dimensions_out = tmp_box.dimensions();
1838  data.radius.accum( tmp_box.inner_radius() / tmp_box.outer_radius() );
1839  data.vol.accum( tmp_box.volume() );
1840  data.area.accum( tmp_box.area() );
1841 
1842  if( isleaf )
1843  {
1844  if( data.leaf_depth.size() <= (unsigned)depth ) data.leaf_depth.resize( depth + 1, 0 );
1845  ++data.leaf_depth[depth];
1846 
1847  int count;
1848  rval = inst->get_number_entities_by_handle( set, count );
1849  if( MB_SUCCESS != rval ) return rval;
1850  count_out = count;
1851  data.leaf_ent.accum( count_out );
1852  }
1853  else
1854  {
1855  for( int i = 0; i < 2; ++i )
1856  {
1857  CartVect dims;
1858  rval = recursive_stats( tool, inst, children[i], depth + 1, data, counts[i], dims );
1859  if( MB_SUCCESS != rval ) return rval;
1860  double this_measure, chld_measure;
1861  int this_dim = measure( dimensions_out, this_measure );
1862  int chld_dim = measure( dims, chld_measure );
1863  double ratio;
1864  if( chld_dim < this_dim )
1865  ratio = 0;
1866  else
1867  ratio = chld_measure / this_measure;
1868 
1869  data.volume.accum( ratio );
1870  }
1871  count_out = counts[0] + counts[1];
1872  data.entities.accum( (double)counts[0] / count_out );
1873  data.entities.accum( (double)counts[1] / count_out );
1874  }
1875  return MB_SUCCESS;
1876 }

References moab::StatData::Ratio::accum(), moab::StatData::Stat< T >::accum(), moab::OrientedBox::area(), moab::StatData::area, box(), children, moab::StatData::count, moab::OrientedBox::dimensions(), moab::StatData::entities, ErrorCode, moab::Interface::get_child_meshsets(), moab::Interface::get_number_entities_by_handle(), moab::OrientedBox::inner_radius(), moab::StatData::leaf_depth, moab::StatData::leaf_ent, MB_MULTIPLE_ENTITIES_FOUND, MB_SUCCESS, moab::measure(), moab::OrientedBox::outer_radius(), moab::StatData::radius, moab::StatData::vol, moab::OrientedBox::volume(), and moab::StatData::volume.

Referenced by stats().

◆ remove_root()

ErrorCode moab::OrientedBoxTreeTool::remove_root ( EntityHandle  root_set)

Remove obb tree root from the Oriented Box Tree Tool data structure.

Remove obb tree root from the Oriented Box Tree Tool data structure (createdTrees)

Definition at line 480 of file OrientedBoxTreeTool.cpp.

481 {
482  std::vector< EntityHandle >::iterator i = find( createdTrees.begin(), createdTrees.end(), root );
483  if( i != createdTrees.end() )
484  {
485  createdTrees.erase( i );
486  return MB_SUCCESS;
487  }
488  else
489  return MB_ENTITY_NOT_FOUND;
490 }

References createdTrees, MB_ENTITY_NOT_FOUND, and MB_SUCCESS.

Referenced by moab::GeomTopoTool::remove_root().

◆ sphere_intersect_triangles()

ErrorCode moab::OrientedBoxTreeTool::sphere_intersect_triangles ( const double *  center,
double  radius,
EntityHandle  tree_root,
std::vector< EntityHandle > &  facets_out,
std::vector< EntityHandle > *  sets_out = 0,
TrvStats accum = 0 
)

Find facets intersected by a sphere.

Find facets intersected by a spherical volume.

Parameters
centerSphere center
radiusSphere radius
tree_rootRoot of OBB tree
facets_outList of triangles intersecting sphere
sets_outIf not null, sets owning facets are appended to this list in an order corresponding to the entries in facets_out.

Definition at line 570 of file OrientedBoxTreeTool.cpp.

576 {
577  const double radsqr = radius * radius;
578  OrientedBox b;
579  ErrorCode rval;
580  Range sets;
581  const CartVect center( center_v );
582  CartVect closest, coords[3];
583  const EntityHandle* conn;
584  int num_conn;
585 #ifndef MB_OBB_USE_VECTOR_QUERIES
586  Range tris;
587  Range::const_iterator t;
588 #else
589  std::vector< EntityHandle > tris;
590  std::vector< EntityHandle >::const_iterator t;
591 #endif
592 
593  std::vector< OBBTreeSITFrame > stack;
594  std::vector< EntityHandle > children;
595  stack.reserve( 30 );
596  stack.push_back( OBBTreeSITFrame( tree_root, 0, 0 ) );
597 
598  int max_depth = -1;
599 
600  while( !stack.empty() )
601  {
602  EntityHandle surf = stack.back().surf;
603  EntityHandle node = stack.back().node;
604  int current_depth = stack.back().depth;
605  stack.pop_back();
606 
607  // increment traversal statistics.
608  if( accum )
609  {
610  accum->increment( current_depth );
611  max_depth = std::max( max_depth, current_depth );
612  }
613 
614  if( !surf && sets_out )
615  {
616  rval = get_moab_instance()->get_entities_by_type( node, MBENTITYSET, sets );
617  if( !sets.empty() ) surf = sets.front();
618  sets.clear();
619  }
620 
621  // check if sphere intersects box
622  rval = box( node, b );
623  if( MB_SUCCESS != rval ) return rval;
624  b.closest_location_in_box( center, closest );
625  closest -= center;
626  if( ( closest % closest ) > radsqr ) continue;
627 
628  // push child boxes on stack
629  children.clear();
630  rval = instance->get_child_meshsets( node, children );
631  if( MB_SUCCESS != rval ) return rval;
632  if( !children.empty() )
633  {
634  assert( children.size() == 2 );
635  stack.push_back( OBBTreeSITFrame( children[0], surf, current_depth + 1 ) );
636  stack.push_back( OBBTreeSITFrame( children[1], surf, current_depth + 1 ) );
637  continue;
638  }
639 
640  if( accum )
641  {
642  accum->increment_leaf( current_depth );
643  }
644  // if leaf, intersect sphere with triangles
645 #ifndef MB_OBB_USE_VECTOR_QUERIES
646 #ifdef MB_OBB_USE_TYPE_QUERIES
647  rval = get_moab_instance()->get_entities_by_type( node, MBTRI, tris );
648 #else
649  rval = get_moab_instance()->get_entities_by_handle( node, tris );
650 #endif
651  t = tris.begin();
652 #else
653  rval = get_moab_instance()->get_entities_by_handle( node, tris );
654  t = tris.lower_bound( MBTRI );
655 #endif
656  if( MB_SUCCESS != rval ) return rval;
657 
658  for( t = tris.begin(); t != tris.end(); ++t )
659  {
660 #ifndef MB_OBB_USE_VECTOR_QUERIES
661  if( TYPE_FROM_HANDLE( *t ) != MBTRI ) break;
662 #elif !defined( MB_OBB_USE_TYPE_QUERIES )
663  if( TYPE_FROM_HANDLE( *t ) != MBTRI ) continue;
664 #endif
665  rval = get_moab_instance()->get_connectivity( *t, conn, num_conn, true );
666  if( MB_SUCCESS != rval ) return rval;
667  if( num_conn != 3 ) continue;
668 
669  rval = get_moab_instance()->get_coords( conn, num_conn, coords[0].array() );
670  if( MB_SUCCESS != rval ) return rval;
671 
672  GeomUtil::closest_location_on_tri( center, coords, closest );
673  closest -= center;
674  if( ( closest % closest ) <= radsqr &&
675  std::find( facets_out.begin(), facets_out.end(), *t ) == facets_out.end() )
676  {
677  facets_out.push_back( *t );
678  if( sets_out ) sets_out->push_back( surf );
679  }
680  }
681  }
682 
683  if( accum )
684  {
685  accum->end_traversal( max_depth );
686  }
687 
688  return MB_SUCCESS;
689 }

References moab::Range::begin(), box(), center(), children, moab::Range::clear(), moab::OrientedBox::closest_location_in_box(), moab::GeomUtil::closest_location_on_tri(), moab::Range::empty(), moab::Range::end(), moab::OrientedBoxTreeTool::TrvStats::end_traversal(), ErrorCode, moab::Range::front(), moab::Interface::get_child_meshsets(), moab::Interface::get_connectivity(), moab::Interface::get_coords(), moab::Interface::get_entities_by_handle(), moab::Interface::get_entities_by_type(), get_moab_instance(), moab::OrientedBoxTreeTool::TrvStats::increment(), moab::OrientedBoxTreeTool::TrvStats::increment_leaf(), instance, moab::Range::lower_bound(), MB_SUCCESS, MBENTITYSET, MBTRI, and moab::TYPE_FROM_HANDLE().

Referenced by get_close_tris().

◆ stats() [1/2]

ErrorCode moab::OrientedBoxTreeTool::stats ( EntityHandle  set,
unsigned &  entities_in_tree,
double &  root_volume,
double &  tot_node_volume,
double &  tot_to_root_volume,
unsigned &  tree_height,
unsigned &  node_count,
unsigned &  num_leaves 
)

Get tree statistics.

Get summary stats. describing tree

Parameters
setRoot of tree for which data is requested
total_entitiesEntities in tree
root_volumeTotal volume of root box
tot_node_volumeTotal volume in all nodes
tot_to_root_volumeRatio of total / root volume
tree_heightMaximum height of tree, from root to leaf
node_countNumber of nodes in tree
num_leavesNumber of leaf nodes in tree

Definition at line 1888 of file OrientedBoxTreeTool.cpp.

1896 {
1897  StatData d;
1898  ErrorCode rval;
1899  unsigned i;
1900  CartVect total_dim;
1901 
1902  rval = recursive_stats( this, instance, set, 0, d, total_entities, total_dim );
1903  if( MB_SUCCESS != rval ) return rval;
1904 
1905  tree_height = d.leaf_depth.size();
1906  unsigned min_leaf_depth = tree_height;
1907  num_leaves = 0;
1908  unsigned max_leaf_per_depth = 0;
1909  // double sum_leaf_depth = 0, sqr_leaf_depth = 0;
1910  for( i = 0; i < d.leaf_depth.size(); ++i )
1911  {
1912  unsigned val = d.leaf_depth[i];
1913  num_leaves += val;
1914  // sum_leaf_depth += (double)val*i;
1915  // sqr_leaf_depth += (double)val*i*i;
1916  if( val && i < min_leaf_depth ) min_leaf_depth = i;
1917  if( max_leaf_per_depth < val ) max_leaf_per_depth = val;
1918  }
1919  rv = total_dim[0] * total_dim[1] * total_dim[2];
1920  tot_node_volume = d.vol.sum;
1921  tot_to_root_volume = d.vol.sum / rv;
1922  node_count = d.count;
1923 
1924  return MB_SUCCESS;
1925 }

References moab::StatData::count, ErrorCode, instance, moab::StatData::leaf_depth, MB_SUCCESS, recursive_stats(), moab::StatData::Stat< T >::sum, and moab::StatData::vol.

◆ stats() [2/2]

ErrorCode moab::OrientedBoxTreeTool::stats ( EntityHandle  tree_root_set,
std::ostream &  stream 
)

Print tree statistics.

Print misc. stats. describing tree

Definition at line 1927 of file OrientedBoxTreeTool.cpp.

1928 {
1929  StatData d;
1930  ErrorCode rval;
1931  unsigned total_entities, i;
1932  CartVect total_dim;
1933 
1934  rval = recursive_stats( this, instance, set, 0, d, total_entities, total_dim );
1935  if( MB_SUCCESS != rval ) return rval;
1936 
1937  unsigned tree_height = d.leaf_depth.size();
1938  unsigned min_leaf_depth = tree_height, num_leaves = 0;
1939  unsigned max_leaf_per_depth = 0;
1940  double sum_leaf_depth = 0, sqr_leaf_depth = 0;
1941  for( i = 0; i < d.leaf_depth.size(); ++i )
1942  {
1943  unsigned val = d.leaf_depth[i];
1944  num_leaves += val;
1945  sum_leaf_depth += (double)val * i;
1946  sqr_leaf_depth += (double)val * i * i;
1947  if( val && i < min_leaf_depth ) min_leaf_depth = i;
1948  if( max_leaf_per_depth < val ) max_leaf_per_depth = val;
1949  }
1950  unsigned num_non_leaf = d.count - num_leaves;
1951 
1952  double rv = total_dim[0] * total_dim[1] * total_dim[2];
1953  s << "entities in tree: " << total_entities << std::endl
1954  << "root volume: " << rv << std::endl
1955  << "total node volume: " << d.vol.sum << std::endl
1956  << "total/root volume: " << d.vol.sum / rv << std::endl
1957  << "tree height: " << tree_height << std::endl
1958  << "node count: " << d.count << std::endl
1959  << "leaf count: " << num_leaves << std::endl
1960  << std::endl;
1961 
1962  double avg_leaf_depth = sum_leaf_depth / num_leaves;
1963  double rms_leaf_depth = sqrt( sqr_leaf_depth / num_leaves );
1964  double std_leaf_depth = std_dev( sqr_leaf_depth, sum_leaf_depth, num_leaves );
1965 
1966  double avg_leaf_ent = d.leaf_ent.sum / num_leaves;
1967  double rms_leaf_ent = sqrt( d.leaf_ent.sqr / num_leaves );
1968  double std_leaf_ent = std_dev( d.leaf_ent.sqr, d.leaf_ent.sum, num_leaves );
1969 
1970  unsigned num_child = 2 * num_non_leaf;
1971 
1972  double avg_vol_ratio = d.volume.sum / num_child;
1973  double rms_vol_ratio = sqrt( d.volume.sqr / num_child );
1974  double std_vol_ratio = std_dev( d.volume.sqr, d.volume.sum, num_child );
1975 
1976  double avg_ent_ratio = d.entities.sum / num_child;
1977  double rms_ent_ratio = sqrt( d.entities.sqr / num_child );
1978  double std_ent_ratio = std_dev( d.entities.sqr, d.entities.sum, num_child );
1979 
1980  double avg_rad_ratio = d.radius.sum / d.count;
1981  double rms_rad_ratio = sqrt( d.radius.sqr / d.count );
1982  double std_rad_ratio = std_dev( d.radius.sqr, d.radius.sum, d.count );
1983 
1984  double avg_vol = d.vol.sum / d.count;
1985  double rms_vol = sqrt( d.vol.sqr / d.count );
1986  double std_vol = std_dev( d.vol.sqr, d.vol.sum, d.count );
1987 
1988  double avg_area = d.area.sum / d.count;
1989  double rms_area = sqrt( d.area.sqr / d.count );
1990  double std_area = std_dev( d.area.sqr, d.area.sum, d.count );
1991 
1992  int prec = s.precision();
1993  s << " " WW "Minimum" WW "Average" WW "RMS" WW "Maximum" WW "Std.Dev." << std::endl;
1994  s << std::setprecision( 1 )
1995  << "Leaf Depth " WW min_leaf_depth WW avg_leaf_depth WW rms_leaf_depth WW d.leaf_depth.size() -
1996  1 WW std_leaf_depth
1997  << std::endl;
1998  s << std::setprecision( 0 )
1999  << "Entities/Leaf " WW d.leaf_ent.min WW avg_leaf_ent WW rms_leaf_ent WW d.leaf_ent.max WW std_leaf_ent
2000  << std::endl;
2001  s << std::setprecision( 3 )
2002  << "Child Volume Ratio " WW d.volume.min WW avg_vol_ratio WW rms_vol_ratio WW d.volume.max WW std_vol_ratio
2003  << std::endl;
2004  s << std::setprecision( 3 )
2005  << "Child Entity Ratio " WW d.entities.min WW avg_ent_ratio WW rms_ent_ratio WW d.entities.max WW std_ent_ratio
2006  << std::endl;
2007  s << std::setprecision( 3 )
2008  << "Box Radius Ratio " WW d.radius.min WW avg_rad_ratio WW rms_rad_ratio WW d.radius.max WW std_rad_ratio
2009  << std::endl;
2010  s << std::setprecision( 0 ) << "Box volume " WE d.vol.min WE avg_vol WE rms_vol WE d.vol.max WE std_vol
2011  << std::endl;
2012  s << std::setprecision( 0 ) << "Largest side area " WE d.area.min WE avg_area WE rms_area WE d.area.max WE std_area
2013  << std::endl;
2014  s << std::setprecision( prec ) << std::endl;
2015 
2016  s << "Leaf Depth Histogram (Root depth is 0)" << std::endl;
2017  double f = 60.0 / max_leaf_per_depth;
2018  for( i = min_leaf_depth; i < d.leaf_depth.size(); ++i )
2019  s << std::setw( 2 ) << i << " " << std::setw( 5 ) << d.leaf_depth[i] << " |" << std::setfill( '*' )
2020  << std::setw( (int)floor( f * d.leaf_depth[i] + 0.5 ) ) << "" << std::setfill( ' ' ) << std::endl;
2021  s << std::endl;
2022 
2023  s << "Child/Parent Volume Ratio Histogram" << std::endl;
2024  f = 60.0 / *( std::max_element( d.volume.hist, d.volume.hist + 10 ) );
2025  for( i = 0; i < 10u; ++i )
2026  s << "0." << i << " " << std::setw( 5 ) << d.volume.hist[i] << " |" << std::setfill( '*' )
2027  << std::setw( (int)floor( f * d.volume.hist[i] + 0.5 ) ) << "" << std::setfill( ' ' ) << std::endl;
2028  s << std::endl;
2029 
2030  s << "Child/Parent Entity Count Ratio Histogram" << std::endl;
2031  f = 60.0 / *( std::max_element( d.entities.hist, d.entities.hist + 10 ) );
2032  for( i = 0; i < 10u; ++i )
2033  s << "0." << i << " " << std::setw( 5 ) << d.entities.hist[i] << " |" << std::setfill( '*' )
2034  << std::setw( (int)floor( f * d.entities.hist[i] + 0.5 ) ) << "" << std::setfill( ' ' ) << std::endl;
2035  s << std::endl;
2036 
2037  s << "Inner/Outer Radius Ratio Histogram (~0.70 for cube)" << std::endl;
2038  // max radius ratio for a box is about 0.7071. Move any boxes
2039  // in the .7 bucket into .6 and print .0 to .6.
2040  d.radius.hist[6] += d.radius.hist[7];
2041  f = 60.0 / *( std::max_element( d.entities.hist, d.entities.hist + 7 ) );
2042  for( i = 0; i < 7u; ++i )
2043  s << "0." << i << " " << std::setw( 5 ) << d.entities.hist[i] << " |" << std::setfill( '*' )
2044  << std::setw( (int)floor( f * d.entities.hist[i] + 0.5 ) ) << "" << std::setfill( ' ' ) << std::endl;
2045  s << std::endl;
2046 
2047  return MB_SUCCESS;
2048 }

References moab::StatData::area, moab::StatData::count, moab::StatData::entities, ErrorCode, moab::StatData::Ratio::hist, instance, moab::StatData::leaf_depth, moab::StatData::leaf_ent, moab::StatData::Ratio::max, moab::StatData::Stat< T >::max, MB_SUCCESS, moab::StatData::Ratio::min, moab::StatData::Stat< T >::min, moab::StatData::radius, recursive_stats(), moab::StatData::Ratio::sqr, moab::StatData::Stat< T >::sqr, moab::std_dev(), moab::StatData::Ratio::sum, moab::StatData::Stat< T >::sum, moab::StatData::vol, moab::StatData::volume, WE, and WW.

Referenced by obbstat_write(), and moab::SmoothFace::SmoothFace().

Member Data Documentation

◆ cleanUpTrees

bool moab::OrientedBoxTreeTool::cleanUpTrees
private

Definition at line 558 of file OrientedBoxTreeTool.hpp.

Referenced by ~OrientedBoxTreeTool().

◆ createdTrees

std::vector< EntityHandle > moab::OrientedBoxTreeTool::createdTrees
private

◆ instance

◆ tagHandle

Tag moab::OrientedBoxTreeTool::tagHandle
private

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