Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
OrientedBoxTreeTool.hpp
Go to the documentation of this file.
1 /*
2  * MOAB, a Mesh-Oriented datABase, is a software component for creating,
3  * storing and accessing finite element mesh data.
4  *
5  * Copyright 2004 Sandia Corporation. Under the terms of Contract
6  * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
7  * retains certain rights in this software.
8  *
9  * This library is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Lesser General Public
11  * License as published by the Free Software Foundation; either
12  * version 2.1 of the License, or (at your option) any later version.
13  *
14  */
15 
16 /**\file OrientedBoxTreeTool.hpp
17  *\author Jason Kraftcheck ([email protected])
18  *\date 2006-07-18
19  */
20 
21 #ifndef MOAB_ORIENTED_BOX_TREE_TOOL_HPP
22 #define MOAB_ORIENTED_BOX_TREE_TOOL_HPP
23 
24 #include "moab/Forward.hpp"
25 #include "moab/GeomUtil.hpp"
26 #include "moab/OrientedBox.hpp"
27 #include <iosfwd>
28 #include <list>
29 #include <vector>
30 
31 namespace moab
32 {
33 
34 class Range;
35 class OrientedBox;
36 class StatData;
37 class CartVect;
38 
39 /** \class OrientedBoxTreeTool
40  * \brief Class for constructing and querying Hierarchical Oriented Bounding Box trees
41  */
43 {
44  public:
45  /**\brief This provides the search range for ray intersections, measured
46  relative to the origin of the ray.
47 
48  first: nonnegative limit for search
49  second: negative limit for search
50 
51  These are const double* so that the window is always defined by
52  pointing to other quantities, but it is not posible to change those
53  quantities via the window.
54  **/
55  typedef std::pair< const double*, const double* > IntersectSearchWindow;
56 
57  /**\brief Misc. knobs controlling tree subdivision
58  *
59  * Available settings for controlling when and how nodes in the tree
60  * are split. The constructor will initialize to the default
61  * settings. All settings except best_split_ratio control when
62  * a node is subdivided. best_split_ratio influences the choice
63  * of how the node is subdivided.
64  *
65  * A calculated ratio is used in the determination of when and how
66  * to split a node. The ratio is calculated as:
67  * - \f$max(\frac{|n_L - n_R|}{n_L+n_R}, f*\frac{n_I}{n_L+n_R})\f$
68  * - \f$n_L\f$ : num entities to be placed in left child
69  * - \f$n_R\f$ : num entities to be placed in right child
70  * - \f$f\f$ : Settings::intersect_ratio_factor
71  * - \f$n_I\f$: num entities intersecting split plane
72  *
73  * ALL of the following conditions must be met for a node to be further
74  * subdivied:
75  * - Depth must be less than max_depth
76  * - Node must contain more than max_leaf_entities entities.
77  * - The 'ratio' must be less than worst_split_ratio
78  *
79  * The node will be subdivided using a plane normal to one of the
80  * box axis and containing the box center. The planes are tested
81  * beginning with the one orthogonal to the longest box axis and
82  * finishing with the one orthogonal to the shortest box axis. The
83  * search will stop at the first plane for which the 'ratio' is
84  * at least Settings::best_split_ratio . Giving Settings::best_split_ratio
85  * a non-zero value gives preference to a split orthogonal to larger
86  * box dimensions.
87  */
88  struct Settings
89  {
90  public:
91  Settings(); //!< set defaults
92  int max_leaf_entities; //!< Average number of entities per leaf
93  int max_depth; //!< Maximum tree depth - 0->no limit
94  //! Must be in [best_split_ratio,1.0]
95  //! A tree node will not be split if the ratio of children
96  //! in the child nodes is greater than this value.
98  //! Must be in [0.0,worst_split_ratio]
99  //! The search for an optimal split plane for splitting a node
100  //! will stop if at least this ratio is achieved for the number of
101  //! entities on each side of the split plane.
103  //! Flags used to create entity sets representing tree nodes
104  unsigned int set_options;
105  //! Check if settings are valid.
106  bool valid() const;
107  };
108 
109  OrientedBoxTreeTool( Interface* i, const char* tag_name = 0, bool destroy_created_trees = false );
110 
112 
113  /**\brief Build oriented bounding box tree
114  *
115  * Build an oriented bounding box tree.
116  *\param entities A list of either vertices or 2-D elements (not both)
117  * for which to build a tree.
118  *\param set_handle_out A handle for the entity set representing the
119  * root of the tree.
120  */
121  ErrorCode build( const Range& entities, EntityHandle& set_handle_out, const Settings* settings = 0 );
122 
123  /**\brief Build a tree of sets, where each set contains triangles.
124  *
125  * Build a tree of sets. Each set must contain at least one triangle
126  * to define its geometry. Each passed set will become a leaf of
127  * the OBB tree. Settings controlling tree depth are ignored by
128  * this method. The tree will be as deep as it needs to be for each
129  * input set to be a leaf.
130  *
131  * To build a tree representing the surfaces of a geometric volume,
132  * 1) Build an OBB tree for each surface using the 'build' method
133  * 2) Add each surface to the contents of the resulting OBB tree root set
134  * 3) Build a tree from all the surface OBB tree root sets using this
135  * method to get a combined tree for the volume.
136  */
137  ErrorCode join_trees( const Range& tree_roots, EntityHandle& root_set_out, const Settings* settings = 0 );
138 
139  /**\brief Traversal statistics structure
140  *
141  * Structure to accumulate statistics on traversal performance. Passed optionally
142  * to query functions, this structure contains the count of nodes visited at each
143  * level in a tree, and the count of traversals that ended at each level.
144  * One TrvStats structure can be used with multiple OBB trees or multiple queries,
145  * or used on only a single tree or a single query.
146  *
147  * Note that these traversal statistics are not related to the stats() query below,
148  * which calculates static information about a tree. These statistics relate
149  * to a tree's dynamic behavior on particular operations.
150  */
151  class TrvStats
152  {
153  public:
154  //! return counts of nodes visited, indexed by tree depth.
155  //! the counts include both leaves and interior nodes
156  const std::vector< unsigned >& nodes_visited() const
157  {
158  return nodes_visited_count;
159  }
160  //! return counts of tree leaves visited, indexed by tree depth
161  const std::vector< unsigned >& leaves_visited() const
162  {
163  return leaves_visited_count;
164  }
165  //! return counts of traversals ended, indexed by tree depth
166  const std::vector< unsigned >& traversals_ended() const
167  {
168  return traversals_ended_count;
169  }
170  //! return total number of ray-triangle intersection tests performed
171  //! in calls made with this TrvStats
172  unsigned int ray_tri_tests() const
173  {
174  return ray_tri_tests_count;
175  }
176  //! reset all counters on this structure
177  void reset();
178  //! print the contents of this structure to given stream
179  void print( std::ostream& str ) const;
180 
182 
183  private:
184  std::vector< unsigned > nodes_visited_count;
185  std::vector< unsigned > leaves_visited_count;
186  std::vector< unsigned > traversals_ended_count;
187  unsigned int ray_tri_tests_count;
188 
189  void increment( unsigned depth );
190  void increment_leaf( unsigned depth );
191  void end_traversal( unsigned depth );
192 
193  friend class OrientedBoxTreeTool;
194  };
195 
196  /**\brief Default/Base class to provide a context for registering intersections
197  *
198  * To enable different logic for how individual intersections are
199  * accumulated, depending on the usage of ray_intersect_sets().
200  *
201  * The API to this context has 3 parts:
202  * * getDesiredOrient() during initialization of ray_intersect_sets to
203  determine whether this context filters by context
204  * * update_orient() updates the context to know the orientation of the
205  current surface wrt to its volume during a traversal visit()
206  * * register_intersection() offers an intersection to the context so that
207  it can decide whether to accumulate it or ignore it
208  *
209  * This implementation also provides a default NOP version that accumulates
210  * all intersections without logic.
211  *
212  * A reference implementation can be found in GeomQueryTool::GQT_IntRegCtxt.
213  *
214  */
215 
217  {
218 
219  protected:
220  std::vector< double > intersections;
221  std::vector< EntityHandle > sets;
222  std::vector< EntityHandle > facets;
223 
224  public:
225  /* provide a default behavior that will simply add the intersection data to the relevent
226  lists with no logic or discrimination */
228  EntityHandle tri,
229  double dist,
230  IntersectSearchWindow& /* search_win */,
231  GeomUtil::intersection_type /* int_type */ )
232  {
233  intersections.push_back( dist );
234  sets.push_back( set );
235  facets.push_back( tri );
236 
237  return MB_SUCCESS;
238  };
239 
240  /* determine the orientation of the topological set with respect to any
241  topological set in the context */
242  virtual ErrorCode update_orient( EntityHandle /* set */, int* /* surfTriOrient */ )
243  {
244  return MB_SUCCESS;
245  };
246 
247  /* determine whether or not a preferred orientation is established */
248  virtual const int* getDesiredOrient()
249  {
250  return NULL;
251  };
252 
253  std::vector< double > get_intersections()
254  {
255  return intersections;
256  };
257  std::vector< EntityHandle > get_facets()
258  {
259  return facets;
260  };
261  std::vector< EntityHandle > get_sets()
262  {
263  return sets;
264  };
265  };
266 
267  /**\brief Intersect a ray with the triangles contained within the tree
268  *
269  * Intersect a ray with the triangles contained in the tree and return
270  * the distance at which the intersection occured.
271  *\param distances_out The output list of intersection points on the ray.
272  *\param facets_out Handles of intersected triangles corresponding to distances_out
273  *\param root_set The MBENTITYSET representing the root of the tree.
274  *\param tolerance The tolerance to use in intersection checks.
275  *\param ray_point The base point of the ray.
276  *\param unit_ray_dir The ray direction vector (must be unit length)
277  *\param ray_length Optional ray length (intersect segment instead of ray.)
278  */
279  ErrorCode ray_intersect_triangles( std::vector< double >& distances_out,
280  std::vector< EntityHandle >& facets_out,
281  EntityHandle root_set,
282  double tolerance,
283  const double ray_point[3],
284  const double unit_ray_dir[3],
285  const double* ray_length = 0,
286  TrvStats* accum = 0 );
287 
288  /**\brief Intersect ray with tree
289  *
290  * Return the tree nodes (as MBENTITYSET handles) for the leaf boxes
291  * of the tree intersected by a ray.
292  *\param boxes_out The boxes intersected by the ray.
293  *\param tolerance The tolerance to use in intersection checks.
294  *\param ray_point The base point of the ray.
295  *\param unit_ray_dir The ray direction vector (must be unit length)
296  *\param ray_length Optional ray length (intersect segment instead of ray.)
297  */
298  ErrorCode ray_intersect_boxes( Range& boxes_out,
299  EntityHandle root_set,
300  double tolerance,
301  const double ray_point[3],
302  const double unit_ray_dir[3],
303  const double* ray_length = 0,
304  TrvStats* accum = 0 );
305 
306  /**\brief Intersect ray with triangles contained in passed MBENTITYSETs
307  *
308  * \param raytri_test_count If non-NULL, count of ray-triangle intersect tests
309  * will be added to the value at which this points.
310  */
311  ErrorCode ray_intersect_triangles( std::vector< double >& intersection_distances_out,
312  std::vector< EntityHandle >& intersection_facets_out,
313  const Range& leaf_boxes_containing_tris,
314  double tolerance,
315  const double ray_point[3],
316  const double unit_ray_dir[3],
317  const double* ray_length = 0,
318  unsigned int* raytri_test_count = 0 );
319 
320  /**\brief Intersect a ray with the triangles contained within the tree
321  *
322  * Intersect a ray with the triangles contained in the tree and return
323  * the distance at which the intersection occured.
324  *\param distances_out The output list of intersection points on the ray.
325  *\param sets_out The contained set encountered during the tree traversal
326  * (see 'set_build'). For the most common use, this is the
327  * set corresponding to the geometric surface containing the
328  * intersected triangle.
329  *\param facets_out Handles of intersected triangles corresponding to distances_out
330  *\param root_set The MBENTITYSET representing the root of the tree.
331  *\param tolerance The tolerance to use in intersection checks.
332  *\param ray_point The base point of the ray.
333  *\param unit_ray_dir The ray direction vector (must be unit length)
334  *\param search_win An interval that defines the current window in which the
335  * an intersection is being sought: (nonnegative, negative)
336  *\param register_intersection A context for assessing and registering intersections
337  * derived from IntRegCtxt
338  *\param accum Optional class for tree traversal statistics.
339  */
340 
341  ErrorCode ray_intersect_sets( std::vector< double >& distances_out,
342  std::vector< EntityHandle >& sets_out,
343  std::vector< EntityHandle >& facets_out,
344  EntityHandle root_set,
345  double tolerance,
346  const double ray_point[3],
347  const double unit_ray_dir[3],
348  IntersectSearchWindow& search_win,
349  IntRegCtxt& register_intersection,
350  TrvStats* accum = 0 );
351 
352  /*\brief Version that doesn't require a search window or an intersection registration context
353  *
354  *
355  */
356  ErrorCode ray_intersect_sets( std::vector< double >& distances_out,
357  std::vector< EntityHandle >& sets_out,
358  std::vector< EntityHandle >& facets_out,
359  EntityHandle root_set,
360  double tolerance,
361  const double ray_point[3],
362  const double unit_ray_dir[3],
363  const double* ray_length = 0,
364  TrvStats* accum = 0 );
365 
367  double tolerance,
368  const double ray_point[3],
369  const double unit_ray_dir[3],
370  IntersectSearchWindow& search_win,
371  IntRegCtxt& register_intersection,
372  TrvStats* accum = 0 );
373 
374  /**\brief Find closest surface, facet in surface, and location on facet
375  *
376  * Find the closest location in the tree to the specified location.
377  *\param point Location to search from
378  *\param point_out Closest location on closest facet
379  *\param facet_out Closest 2D element to input position
380  *\param set_out Set containing closest facet. 0 if tree was not
381  * constructed using 'set_build'
382  */
383  ErrorCode closest_to_location( const double* point,
384  EntityHandle tree_root,
385  double* point_out,
386  EntityHandle& facet_out,
387  EntityHandle* set_out = 0,
388  TrvStats* accum = 0 );
389 
390  /**\brief Find closest facet(s) to input position.
391  *
392  * Find the closest location(s) in the tree to the specified location.
393  *\param point Location to search from
394  *\param facets_out Closest 2D elements to input position are appended to this list
395  *\param sets_out If non-null, sets owning facets are appended to this list.
396  */
397  ErrorCode closest_to_location( const double* point,
398  EntityHandle tree_root,
399  double tolerance,
400  std::vector< EntityHandle >& facets_out,
401  std::vector< EntityHandle >* sets_out = 0,
402  TrvStats* accum = 0 );
403 
404  /**\brief Find facets intersected by a sphere
405  *
406  * Find facets intersected by a spherical volume.
407  *\param center Sphere center
408  *\param radius Sphere radius
409  *\param tree_root Root of OBB tree
410  *\param facets_out List of triangles intersecting sphere
411  *\param sets_out If not null, sets owning facets are appended to this
412  * list in an order corresponding to the entries in
413  * facets_out.
414  */
416  double radius,
417  EntityHandle tree_root,
418  std::vector< EntityHandle >& facets_out,
419  std::vector< EntityHandle >* sets_out = 0,
420  TrvStats* accum = 0 );
421 
423  double tol,
424  const EntityHandle* rootSet,
425  const EntityHandle* geomVol,
426  const Tag* senseTag,
427  std::vector< EntityHandle >& close_tris,
428  std::vector< int >& close_senses );
429 
430  /**\brief Get oriented box at node in tree
431  *
432  * Get the oriented box for a node in an oriented bounding box tree.
433  */
434  ErrorCode box( EntityHandle node_set, double center[3], double axis1[3], double axis2[3], double axis3[3] );
435 
436  ErrorCode delete_tree( EntityHandle root_set );
437 
438  /**\brief Remove obb tree root from the Oriented Box Tree Tool data structure
439  *
440  * Remove obb tree root from the Oriented Box Tree Tool data structure (createdTrees)
441  */
442  ErrorCode remove_root( EntityHandle root_set );
443 
444  /**\brief Print out tree
445  *
446  * Print the tree to an output stream in a human-readable form.
447  *\param tree_root_set Entity set representing tree root.
448  *\param list_contents If true, list entities in each tree node,
449  * If false, just list number of entities.
450  *\param id_tag_name If specified, must be the name of an existing
451  * integer tag containing an ID for the entities.
452  * Not used if list_contents is false.
453  */
454  void print( EntityHandle tree_root_set,
455  std::ostream& stream,
456  bool list_contents = false,
457  const char* id_tag_name = 0 );
458 
459  /**\brief Print tree statistics
460  *
461  * Print misc. stats. describing tree
462  */
463  ErrorCode stats( EntityHandle tree_root_set, std::ostream& stream );
464 
465  /**\brief Get tree statistics
466  *
467  * Get summary stats. describing tree
468  * \param set Root of tree for which data is requested
469  * \param total_entities Entities in tree
470  * \param root_volume Total volume of root box
471  * \param tot_node_volume Total volume in all nodes
472  * \param tot_to_root_volume Ratio of total / root volume
473  * \param tree_height Maximum height of tree, from root to leaf
474  * \param node_count Number of nodes in tree
475  * \param num_leaves Number of leaf nodes in tree
476  */
478  unsigned& entities_in_tree,
479  double& root_volume,
480  double& tot_node_volume,
481  double& tot_to_root_volume,
482  unsigned& tree_height,
483  unsigned& node_count,
484  unsigned& num_leaves );
485 
486  /** \brief Implement this and pass instance to preorder_traverse
487  *
488  * This interface may be implemented and an instance passed to
489  * preorder_traverse to define some operation to do when traversing
490  * the tree.
491  */
492  class Op
493  {
494  public:
495  /**\brief Visit a node in the tree during a traversal.
496  *
497  * This method is called for each node in the tree visited
498  * during a pre-order traversal.
499  *\param node The EntityHandle for the entity set for the tree node.
500  *\param depth The current depth in the tree.
501  *\param descend Output: if false, traversal will skip children
502  * of the current node, or if the current node is a
503  * leaf, the 'leaf' method will not be called.
504  */
505  virtual ErrorCode visit( EntityHandle node, int depth, bool& descend ) = 0;
506 
507  /**\brief Process a leaf node during tree traversal */
508  virtual ErrorCode leaf( EntityHandle node ) = 0;
509 
510  virtual ~Op(); // probably isn't necessary in this case, and
511  // does nothing, but lots of compilers warn if
512  // virtual function but no virtual destructor.
513  };
514 
515  /**\brief Visitor pattern - do operation for each tree node
516  *
517  * Do a preorder traversal of the tree, calling the method
518  * in the passed operation instance for each node in the tree.
519  * Parent node is visited before either child (pre-order traversal).
520  * If operator method passes back the 'descend' argument as false,
521  * traversal will not descend to the children of the current node.
522  */
523  ErrorCode preorder_traverse( EntityHandle root_set, Op& operation, TrvStats* accum = 0 );
524 
526  {
527  return instance;
528  }
529 
530  struct SetData;
531 
532  /**\brief Get oriented box at node in tree
533  *
534  * Get the oriented box for a node in an oriented bounding box tree.
535  *
536  * NOTE: This function is provided for internal MOAB use only.
537  * The definition of OrientedBox is not available as a part
538  * of the MOAB API
539  */
540  ErrorCode box( EntityHandle node_set, OrientedBox& box );
541 
542  private:
543  ErrorCode build_tree( const Range& entities, EntityHandle& set, int depth, const Settings& settings );
544 
545  ErrorCode build_sets( std::list< SetData >& sets, EntityHandle& node_set, int depth, const Settings& settings );
546 
549  EntityHandle set,
550  int depth,
551  StatData& data,
552  unsigned& count_out,
553  CartVect& dimensions_out );
554 
557 
559  std::vector< EntityHandle > createdTrees;
560 };
561 
562 } // namespace moab
563 
564 #endif