Mesh Oriented datABase  (version 5.4.1)
Array-based unstructured mesh datastructure
OrientedBoxTreeTool.hpp
Go to the documentation of this file.
00001 /*
00002  * MOAB, a Mesh-Oriented datABase, is a software component for creating,
00003  * storing and accessing finite element mesh data.
00004  *
00005  * Copyright 2004 Sandia Corporation.  Under the terms of Contract
00006  * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
00007  * retains certain rights in this software.
00008  *
00009  * This library is free software; you can redistribute it and/or
00010  * modify it under the terms of the GNU Lesser General Public
00011  * License as published by the Free Software Foundation; either
00012  * version 2.1 of the License, or (at your option) any later version.
00013  *
00014  */
00015 
00016 /**\file OrientedBoxTreeTool.hpp
00017  *\author Jason Kraftcheck ([email protected])
00018  *\date 2006-07-18
00019  */
00020 
00021 #ifndef MOAB_ORIENTED_BOX_TREE_TOOL_HPP
00022 #define MOAB_ORIENTED_BOX_TREE_TOOL_HPP
00023 
00024 #include "moab/Forward.hpp"
00025 #include "moab/GeomUtil.hpp"
00026 #include "moab/OrientedBox.hpp"
00027 #include <iosfwd>
00028 #include <list>
00029 #include <vector>
00030 
00031 namespace moab
00032 {
00033 
00034 class Range;
00035 class OrientedBox;
00036 class StatData;
00037 class CartVect;
00038 
00039 /** \class OrientedBoxTreeTool
00040  * \brief Class for constructing and querying Hierarchical Oriented Bounding Box trees
00041  */
00042 class OrientedBoxTreeTool
00043 {
00044   public:
00045     /**\brief This provides the search range for ray intersections, measured
00046        relative to the origin of the ray.
00047 
00048        first: nonnegative limit for search
00049        second: negative limit for search
00050 
00051        These are const double* so that the window is always defined by
00052        pointing to other quantities, but it is not posible to change those
00053        quantities via the window.
00054      **/
00055     typedef std::pair< const double*, const double* > IntersectSearchWindow;
00056 
00057     /**\brief Misc. knobs controlling tree subdivision
00058      *
00059      * Available settings for controlling when and how nodes in the tree
00060      * are split.  The constructor will initialize to the default
00061      * settings.  All settings except best_split_ratio control when
00062      * a node is subdivided.  best_split_ratio influences the choice
00063      * of how the node is subdivided.
00064      *
00065      * A calculated ratio is used in the determination of when and how
00066      * to split a node.  The ratio is calculated as:
00067      * - \f$max(\frac{|n_L - n_R|}{n_L+n_R}, f*\frac{n_I}{n_L+n_R})\f$
00068      * - \f$n_L\f$ : num entities to be placed in left child
00069      * - \f$n_R\f$ : num entities to be placed in right child
00070      * - \f$f\f$ : Settings::intersect_ratio_factor
00071      * - \f$n_I\f$: num entities intersecting split plane
00072      *
00073      * ALL of the following conditions must be met for a node to be further
00074      * subdivied:
00075      *  - Depth must be less than max_depth
00076      *  - Node must contain more than max_leaf_entities entities.
00077      *  - The 'ratio' must be less than worst_split_ratio
00078      *
00079      * The node will be subdivided using a plane normal to one of the
00080      * box axis and containing the box center.  The planes are tested
00081      * beginning with the one orthogonal to the longest box axis and
00082      * finishing with the one orthogonal to the shortest box axis.  The
00083      * search will stop at the first plane for which the 'ratio' is
00084      * at least Settings::best_split_ratio .  Giving Settings::best_split_ratio
00085      * a non-zero value gives preference to a split orthogonal to larger
00086      * box dimensions.
00087      */
00088     struct Settings
00089     {
00090       public:
00091         Settings();             //!< set defaults
00092         int max_leaf_entities;  //!< Average number of entities per leaf
00093         int max_depth;          //!< Maximum tree depth - 0->no limit
00094         //! Must be in [best_split_ratio,1.0]
00095         //! A tree node will not be split if the ratio of children
00096         //! in the child nodes is greater than this value.
00097         double worst_split_ratio;
00098         //! Must be in [0.0,worst_split_ratio]
00099         //! The search for an optimal split plane for splitting a node
00100         //! will stop if at least this ratio is achieved for the number of
00101         //! entities on each side of the split plane.
00102         double best_split_ratio;
00103         //! Flags used to create entity sets representing tree nodes
00104         unsigned int set_options;
00105         //! Check if settings are valid.
00106         bool valid() const;
00107     };
00108 
00109     OrientedBoxTreeTool( Interface* i, const char* tag_name = 0, bool destroy_created_trees = false );
00110 
00111     ~OrientedBoxTreeTool();
00112 
00113     /**\brief Build oriented bounding box tree
00114      *
00115      * Build an oriented bounding box tree.
00116      *\param entities A list of either vertices or 2-D elements (not both)
00117      *                for which to build a tree.
00118      *\param set_handle_out A handle for the entity set representing the
00119      *                root of the tree.
00120      */
00121     ErrorCode build( const Range& entities, EntityHandle& set_handle_out, const Settings* settings = 0 );
00122 
00123     /**\brief Build a tree of sets, where each set contains triangles.
00124      *
00125      * Build a tree of sets.  Each set must contain at least one triangle
00126      * to define its geometry.  Each passed set will become a leaf of
00127      * the OBB tree.  Settings controlling tree depth are ignored by
00128      * this method.  The tree will be as deep as it needs to be for each
00129      * input set to be a leaf.
00130      *
00131      * To build a tree representing the surfaces of a geometric volume,
00132      * 1) Build an OBB tree for each surface using the 'build' method
00133      * 2) Add each surface to the contents of the resulting OBB tree root set
00134      * 3) Build a tree from all the surface OBB tree root sets using this
00135      *    method to get a combined tree for the volume.
00136      */
00137     ErrorCode join_trees( const Range& tree_roots, EntityHandle& root_set_out, const Settings* settings = 0 );
00138 
00139     /**\brief Traversal statistics structure
00140      *
00141      * Structure to accumulate statistics on traversal performance. Passed optionally
00142      * to query functions, this structure contains the count of nodes visited at each
00143      * level in a tree, and the count of traversals that ended at each level.
00144      * One TrvStats structure can be used with multiple OBB trees or multiple queries,
00145      * or used on only a single tree or a single query.
00146      *
00147      * Note that these traversal statistics are not related to the stats() query below,
00148      * which calculates static information about a tree.  These statistics relate
00149      * to a tree's dynamic behavior on particular operations.
00150      */
00151     class TrvStats
00152     {
00153       public:
00154         //! return counts of nodes visited, indexed by tree depth.
00155         //! the counts include both leaves and interior nodes
00156         const std::vector< unsigned >& nodes_visited() const
00157         {
00158             return nodes_visited_count;
00159         }
00160         //! return counts of tree leaves visited, indexed by tree depth
00161         const std::vector< unsigned >& leaves_visited() const
00162         {
00163             return leaves_visited_count;
00164         }
00165         //! return counts of traversals ended, indexed by tree depth
00166         const std::vector< unsigned >& traversals_ended() const
00167         {
00168             return traversals_ended_count;
00169         }
00170         //! return total number of ray-triangle intersection tests performed
00171         //! in calls made with this TrvStats
00172         unsigned int ray_tri_tests() const
00173         {
00174             return ray_tri_tests_count;
00175         }
00176         //! reset all counters on this structure
00177         void reset();
00178         //! print the contents of this structure to given stream
00179         void print( std::ostream& str ) const;
00180 
00181         TrvStats() : ray_tri_tests_count( 0 ) {}
00182 
00183       private:
00184         std::vector< unsigned > nodes_visited_count;
00185         std::vector< unsigned > leaves_visited_count;
00186         std::vector< unsigned > traversals_ended_count;
00187         unsigned int ray_tri_tests_count;
00188 
00189         void increment( unsigned depth );
00190         void increment_leaf( unsigned depth );
00191         void end_traversal( unsigned depth );
00192 
00193         friend class OrientedBoxTreeTool;
00194     };
00195 
00196     /**\brief Default/Base class to provide a context for registering intersections
00197      *
00198      * To enable different logic for how individual intersections are
00199      * accumulated, depending on the usage of ray_intersect_sets().
00200      *
00201      * The API to this context has 3 parts:
00202      * * getDesiredOrient() during initialization of ray_intersect_sets to
00203           determine whether this context filters by context
00204      * * update_orient() updates the context to know the orientation of the
00205          current surface wrt to its volume during a traversal visit()
00206      * * register_intersection() offers an intersection to the context so that
00207          it can decide whether to accumulate it or ignore it
00208      *
00209      * This implementation also provides a default NOP version that accumulates
00210      * all intersections without logic.
00211      *
00212      * A reference implementation can be found in GeomQueryTool::GQT_IntRegCtxt.
00213      *
00214      */
00215 
00216     class IntRegCtxt
00217     {
00218 
00219       protected:
00220         std::vector< double > intersections;
00221         std::vector< EntityHandle > sets;
00222         std::vector< EntityHandle > facets;
00223 
00224       public:
00225         /* provide a default behavior that will simply add the intersection data to the relevent
00226            lists with no logic or discrimination */
00227         virtual ErrorCode register_intersection( EntityHandle set,
00228                                                  EntityHandle tri,
00229                                                  double dist,
00230                                                  IntersectSearchWindow& /* search_win */,
00231                                                  GeomUtil::intersection_type /* int_type */ )
00232         {
00233             intersections.push_back( dist );
00234             sets.push_back( set );
00235             facets.push_back( tri );
00236 
00237             return MB_SUCCESS;
00238         };
00239 
00240         /* determine the orientation of the topological set with respect to any
00241            topological set in the context */
00242         virtual ErrorCode update_orient( EntityHandle /* set */, int* /* surfTriOrient */ )
00243         {
00244             return MB_SUCCESS;
00245         };
00246 
00247         /* determine whether or not a preferred orientation is established  */
00248         virtual const int* getDesiredOrient()
00249         {
00250             return NULL;
00251         };
00252 
00253         std::vector< double > get_intersections()
00254         {
00255             return intersections;
00256         };
00257         std::vector< EntityHandle > get_facets()
00258         {
00259             return facets;
00260         };
00261         std::vector< EntityHandle > get_sets()
00262         {
00263             return sets;
00264         };
00265     };
00266 
00267     /**\brief Intersect a ray with the triangles contained within the tree
00268      *
00269      * Intersect a ray with the triangles contained in the tree and return
00270      * the distance at which the intersection occured.
00271      *\param distances_out The output list of intersection points on the ray.
00272      *\param facets_out    Handles of intersected triangles corresponding to distances_out
00273      *\param root_set      The MBENTITYSET representing the root of the tree.
00274      *\param tolerance     The tolerance to use in intersection checks.
00275      *\param ray_point     The base point of the ray.
00276      *\param unit_ray_dir  The ray direction vector (must be unit length)
00277      *\param ray_length    Optional ray length (intersect segment instead of ray.)
00278      */
00279     ErrorCode ray_intersect_triangles( std::vector< double >& distances_out,
00280                                        std::vector< EntityHandle >& facets_out,
00281                                        EntityHandle root_set,
00282                                        double tolerance,
00283                                        const double ray_point[3],
00284                                        const double unit_ray_dir[3],
00285                                        const double* ray_length = 0,
00286                                        TrvStats* accum          = 0 );
00287 
00288     /**\brief Intersect ray with tree
00289      *
00290      * Return the tree nodes (as MBENTITYSET handles) for the leaf boxes
00291      * of the tree intersected by a ray.
00292      *\param boxes_out    The boxes intersected by the ray.
00293      *\param tolerance     The tolerance to use in intersection checks.
00294      *\param ray_point     The base point of the ray.
00295      *\param unit_ray_dir  The ray direction vector (must be unit length)
00296      *\param ray_length    Optional ray length (intersect segment instead of ray.)
00297      */
00298     ErrorCode ray_intersect_boxes( Range& boxes_out,
00299                                    EntityHandle root_set,
00300                                    double tolerance,
00301                                    const double ray_point[3],
00302                                    const double unit_ray_dir[3],
00303                                    const double* ray_length = 0,
00304                                    TrvStats* accum          = 0 );
00305 
00306     /**\brief Intersect ray with triangles contained in passed MBENTITYSETs
00307      *
00308      * \param raytri_test_count    If non-NULL, count of ray-triangle intersect tests
00309      *                             will be added to the value at which this points.
00310      */
00311     ErrorCode ray_intersect_triangles( std::vector< double >& intersection_distances_out,
00312                                        std::vector< EntityHandle >& intersection_facets_out,
00313                                        const Range& leaf_boxes_containing_tris,
00314                                        double tolerance,
00315                                        const double ray_point[3],
00316                                        const double unit_ray_dir[3],
00317                                        const double* ray_length        = 0,
00318                                        unsigned int* raytri_test_count = 0 );
00319 
00320     /**\brief Intersect a ray with the triangles contained within the tree
00321      *
00322      * Intersect a ray with the triangles contained in the tree and return
00323      * the distance at which the intersection occured.
00324      *\param distances_out The output list of intersection points on the ray.
00325      *\param sets_out      The contained set encountered during the tree traversal
00326      *                     (see 'set_build').  For the most common use, this is the
00327      *                     set corresponding to the geometric surface containing the
00328      *                     intersected triangle.
00329      *\param facets_out    Handles of intersected triangles corresponding to distances_out
00330      *\param root_set      The MBENTITYSET representing the root of the tree.
00331      *\param tolerance     The tolerance to use in intersection checks.
00332      *\param ray_point     The base point of the ray.
00333      *\param unit_ray_dir  The ray direction vector (must be unit length)
00334      *\param search_win    An interval that defines the current window in which the
00335      *                     an intersection is being sought: (nonnegative, negative)
00336      *\param register_intersection A context for assessing and registering intersections
00337      *                     derived from IntRegCtxt
00338      *\param accum         Optional class for tree traversal statistics.
00339      */
00340 
00341     ErrorCode ray_intersect_sets( std::vector< double >& distances_out,
00342                                   std::vector< EntityHandle >& sets_out,
00343                                   std::vector< EntityHandle >& facets_out,
00344                                   EntityHandle root_set,
00345                                   double tolerance,
00346                                   const double ray_point[3],
00347                                   const double unit_ray_dir[3],
00348                                   IntersectSearchWindow& search_win,
00349                                   IntRegCtxt& register_intersection,
00350                                   TrvStats* accum = 0 );
00351 
00352     /*\brief Version that doesn't require a search window or an intersection registration context
00353      *
00354      *
00355      */
00356     ErrorCode ray_intersect_sets( std::vector< double >& distances_out,
00357                                   std::vector< EntityHandle >& sets_out,
00358                                   std::vector< EntityHandle >& facets_out,
00359                                   EntityHandle root_set,
00360                                   double tolerance,
00361                                   const double ray_point[3],
00362                                   const double unit_ray_dir[3],
00363                                   const double* ray_length = 0,
00364                                   TrvStats* accum          = 0 );
00365 
00366     ErrorCode ray_intersect_sets( EntityHandle root_set,
00367                                   double tolerance,
00368                                   const double ray_point[3],
00369                                   const double unit_ray_dir[3],
00370                                   IntersectSearchWindow& search_win,
00371                                   IntRegCtxt& register_intersection,
00372                                   TrvStats* accum = 0 );
00373 
00374     /**\brief Find closest surface, facet in surface, and location on facet
00375      *
00376      * Find the closest location in the tree to the specified location.
00377      *\param point Location to search from
00378      *\param point_out Closest location on closest facet
00379      *\param facet_out Closest 2D element to input position
00380      *\param set_out Set containing closest facet.  0 if tree was not
00381      *               constructed using 'set_build'
00382      */
00383     ErrorCode closest_to_location( const double* point,
00384                                    EntityHandle tree_root,
00385                                    double* point_out,
00386                                    EntityHandle& facet_out,
00387                                    EntityHandle* set_out = 0,
00388                                    TrvStats* accum       = 0 );
00389 
00390     /**\brief Find closest facet(s) to input position.
00391      *
00392      * Find the closest location(s) in the tree to the specified location.
00393      *\param point Location to search from
00394      *\param facets_out Closest 2D elements to input position are appended to this list
00395      *\param sets_out If non-null, sets owning facets are appended to this list.
00396      */
00397     ErrorCode closest_to_location( const double* point,
00398                                    EntityHandle tree_root,
00399                                    double tolerance,
00400                                    std::vector< EntityHandle >& facets_out,
00401                                    std::vector< EntityHandle >* sets_out = 0,
00402                                    TrvStats* accum                       = 0 );
00403 
00404     /**\brief Find facets intersected by a sphere
00405      *
00406      * Find facets intersected by a spherical volume.
00407      *\param center     Sphere center
00408      *\param radius     Sphere radius
00409      *\param tree_root  Root of OBB tree
00410      *\param facets_out List of triangles intersecting sphere
00411      *\param sets_out   If not null, sets owning facets are appended to this
00412      *                  list in an order corresponding to the entries in
00413      *                  facets_out.
00414      */
00415     ErrorCode sphere_intersect_triangles( const double* center,
00416                                           double radius,
00417                                           EntityHandle tree_root,
00418                                           std::vector< EntityHandle >& facets_out,
00419                                           std::vector< EntityHandle >* sets_out = 0,
00420                                           TrvStats* accum                       = 0 );
00421 
00422     ErrorCode get_close_tris( CartVect int_pt,
00423                               double tol,
00424                               const EntityHandle* rootSet,
00425                               const EntityHandle* geomVol,
00426                               const Tag* senseTag,
00427                               std::vector< EntityHandle >& close_tris,
00428                               std::vector< int >& close_senses );
00429 
00430     /**\brief Get oriented box at node in tree
00431      *
00432      * Get the oriented box for a node in an oriented bounding box tree.
00433      */
00434     ErrorCode box( EntityHandle node_set, double center[3], double axis1[3], double axis2[3], double axis3[3] );
00435 
00436     ErrorCode delete_tree( EntityHandle root_set );
00437 
00438     /**\brief Remove obb tree root from the Oriented Box Tree Tool data structure
00439      *
00440      * Remove obb tree root from the Oriented Box Tree Tool data structure (createdTrees)
00441      */
00442     ErrorCode remove_root( EntityHandle root_set );
00443 
00444     /**\brief Print out tree
00445      *
00446      * Print the tree to an output stream in a human-readable form.
00447      *\param tree_root_set  Entity set representing tree root.
00448      *\param list_contents  If true, list entities in each tree node,
00449      *                      If false, just list number of entities.
00450      *\param id_tag_name    If specified, must be the name of an existing
00451      *                      integer tag containing an ID for the entities.
00452      *                      Not used if list_contents is false.
00453      */
00454     void print( EntityHandle tree_root_set,
00455                 std::ostream& stream,
00456                 bool list_contents      = false,
00457                 const char* id_tag_name = 0 );
00458 
00459     /**\brief Print tree statistics
00460      *
00461      * Print misc. stats. describing tree
00462      */
00463     ErrorCode stats( EntityHandle tree_root_set, std::ostream& stream );
00464 
00465     /**\brief Get tree statistics
00466      *
00467      * Get summary stats. describing tree
00468      * \param set Root of tree for which data is requested
00469      * \param total_entities Entities in tree
00470      * \param root_volume Total volume of root box
00471      * \param tot_node_volume Total volume in all nodes
00472      * \param tot_to_root_volume Ratio of total / root volume
00473      * \param tree_height Maximum height of tree, from root to leaf
00474      * \param node_count Number of nodes in tree
00475      * \param num_leaves Number of leaf nodes in tree
00476      */
00477     ErrorCode stats( EntityHandle set,
00478                      unsigned& entities_in_tree,
00479                      double& root_volume,
00480                      double& tot_node_volume,
00481                      double& tot_to_root_volume,
00482                      unsigned& tree_height,
00483                      unsigned& node_count,
00484                      unsigned& num_leaves );
00485 
00486     /** \brief Implement this and pass instance to preorder_traverse
00487      *
00488      * This interface may be implemented and an instance passed to
00489      * preorder_traverse to define some operation to do when traversing
00490      * the tree.
00491      */
00492     class Op
00493     {
00494       public:
00495         /**\brief Visit a node in the tree during a traversal.
00496          *
00497          * This method is called for each node in the tree visited
00498          * during a pre-order traversal.
00499          *\param node The EntityHandle for the entity set for the tree node.
00500          *\param depth The current depth in the tree.
00501          *\param descend Output: if false, traversal will skip children
00502          *             of the current node, or if the current node is a
00503          *             leaf, the 'leaf' method will not be called.
00504          */
00505         virtual ErrorCode visit( EntityHandle node, int depth, bool& descend ) = 0;
00506 
00507         /**\brief Process a leaf node during tree traversal */
00508         virtual ErrorCode leaf( EntityHandle node ) = 0;
00509 
00510         virtual ~Op();  // probably isn't necessary in this case, and
00511                         // does nothing, but lots of compilers warn if
00512                         // virtual function but no virtual destructor.
00513     };
00514 
00515     /**\brief Visitor pattern - do operation for each tree node
00516      *
00517      * Do a preorder traversal of the tree, calling the method
00518      * in the passed operation instance for each node in the tree.
00519      * Parent node is visited before either child (pre-order traversal).
00520      * If operator method passes back the 'descend' argument as false,
00521      * traversal will not descend to the children of the current node.
00522      */
00523     ErrorCode preorder_traverse( EntityHandle root_set, Op& operation, TrvStats* accum = 0 );
00524 
00525     Interface* get_moab_instance() const
00526     {
00527         return instance;
00528     }
00529 
00530     struct SetData;
00531 
00532     /**\brief Get oriented box at node in tree
00533      *
00534      * Get the oriented box for a node in an oriented bounding box tree.
00535      *
00536      * NOTE: This function is provided for internal MOAB use only.
00537      *       The definition of OrientedBox is not available as a part
00538      *       of the MOAB API
00539      */
00540     ErrorCode box( EntityHandle node_set, OrientedBox& box );
00541 
00542   private:
00543     ErrorCode build_tree( const Range& entities, EntityHandle& set, int depth, const Settings& settings );
00544 
00545     ErrorCode build_sets( std::list< SetData >& sets, EntityHandle& node_set, int depth, const Settings& settings );
00546 
00547     ErrorCode recursive_stats( OrientedBoxTreeTool* tool,
00548                                Interface* instance,
00549                                EntityHandle set,
00550                                int depth,
00551                                StatData& data,
00552                                unsigned& count_out,
00553                                CartVect& dimensions_out );
00554 
00555     Interface* instance;
00556     Tag tagHandle;
00557 
00558     bool cleanUpTrees;
00559     std::vector< EntityHandle > createdTrees;
00560 };
00561 
00562 }  // namespace moab
00563 
00564 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines