MOAB: Mesh Oriented datABase  (version 5.3.1)
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 (kraftche@cae.wisc.edu)
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, EntityHandle tri, double dist,
00228                                                  IntersectSearchWindow& /* search_win */,
00229                                                  GeomUtil::intersection_type /* int_type */ )
00230         {
00231             intersections.push_back( dist );
00232             sets.push_back( set );
00233             facets.push_back( tri );
00234 
00235             return MB_SUCCESS;
00236         };
00237 
00238         /* determine the orientation of the topological set with respect to any
00239            topological set in the context */
00240         virtual ErrorCode update_orient( EntityHandle /* set */, int* /* surfTriOrient */ )
00241         {
00242             return MB_SUCCESS;
00243         };
00244 
00245         /* determine whether or not a preferred orientation is established  */
00246         virtual const int* getDesiredOrient()
00247         {
00248             return NULL;
00249         };
00250 
00251         std::vector< double > get_intersections()
00252         {
00253             return intersections;
00254         };
00255         std::vector< EntityHandle > get_facets()
00256         {
00257             return facets;
00258         };
00259         std::vector< EntityHandle > get_sets()
00260         {
00261             return sets;
00262         };
00263     };
00264 
00265     /**\brief Intersect a ray with the triangles contained within the tree
00266      *
00267      * Intersect a ray with the triangles contained in the tree and return
00268      * the distance at which the intersection occured.
00269      *\param distances_out The output list of intersection points on the ray.
00270      *\param facets_out    Handles of intersected triangles corresponding to distances_out
00271      *\param root_set      The MBENTITYSET representing the root of the tree.
00272      *\param tolerance     The tolerance to use in intersection checks.
00273      *\param ray_point     The base point of the ray.
00274      *\param unit_ray_dir  The ray direction vector (must be unit length)
00275      *\param ray_length    Optional ray length (intersect segment instead of ray.)
00276      */
00277     ErrorCode ray_intersect_triangles( std::vector< double >& distances_out, std::vector< EntityHandle >& facets_out,
00278                                        EntityHandle root_set, double tolerance, const double ray_point[3],
00279                                        const double unit_ray_dir[3], const double* ray_length = 0,
00280                                        TrvStats* accum = 0 );
00281 
00282     /**\brief Intersect ray with tree
00283      *
00284      * Return the tree nodes (as MBENTITYSET handles) for the leaf boxes
00285      * of the tree intersected by a ray.
00286      *\param boxes_out    The boxes intersected by the ray.
00287      *\param tolerance     The tolerance to use in intersection checks.
00288      *\param ray_point     The base point of the ray.
00289      *\param unit_ray_dir  The ray direction vector (must be unit length)
00290      *\param ray_length    Optional ray length (intersect segment instead of ray.)
00291      */
00292     ErrorCode ray_intersect_boxes( Range& boxes_out, EntityHandle root_set, double tolerance, const double ray_point[3],
00293                                    const double unit_ray_dir[3], const double* ray_length = 0, TrvStats* accum = 0 );
00294 
00295     /**\brief Intersect ray with triangles contained in passed MBENTITYSETs
00296      *
00297      * \param raytri_test_count    If non-NULL, count of ray-triangle intersect tests
00298      *                             will be added to the value at which this points.
00299      */
00300     ErrorCode ray_intersect_triangles( std::vector< double >& intersection_distances_out,
00301                                        std::vector< EntityHandle >& intersection_facets_out,
00302                                        const Range& leaf_boxes_containing_tris, double tolerance,
00303                                        const double ray_point[3], const double unit_ray_dir[3],
00304                                        const double* ray_length = 0, unsigned int* raytri_test_count = 0 );
00305 
00306     /**\brief Intersect a ray with the triangles contained within the tree
00307      *
00308      * Intersect a ray with the triangles contained in the tree and return
00309      * the distance at which the intersection occured.
00310      *\param distances_out The output list of intersection points on the ray.
00311      *\param sets_out      The contained set encountered during the tree traversal
00312      *                     (see 'set_build').  For the most common use, this is the
00313      *                     set corresponding to the geometric surface containing the
00314      *                     intersected triangle.
00315      *\param facets_out    Handles of intersected triangles corresponding to distances_out
00316      *\param root_set      The MBENTITYSET representing the root of the tree.
00317      *\param tolerance     The tolerance to use in intersection checks.
00318      *\param ray_point     The base point of the ray.
00319      *\param unit_ray_dir  The ray direction vector (must be unit length)
00320      *\param search_win    An interval that defines the current window in which the
00321      *                     an intersection is being sought: (nonnegative, negative)
00322      *\param register_intersection A context for assessing and registering intersections
00323      *                     derived from IntRegCtxt
00324      *\param accum         Optional class for tree traversal statistics.
00325      */
00326 
00327     ErrorCode ray_intersect_sets( std::vector< double >& distances_out, std::vector< EntityHandle >& sets_out,
00328                                   std::vector< EntityHandle >& facets_out, EntityHandle root_set, double tolerance,
00329                                   const double ray_point[3], const double unit_ray_dir[3],
00330                                   IntersectSearchWindow& search_win, IntRegCtxt& register_intersection,
00331                                   TrvStats* accum = 0 );
00332 
00333     /*\brief Version that doesn't require a search window or an intersection registration context
00334      *
00335      *
00336      */
00337     ErrorCode ray_intersect_sets( std::vector< double >& distances_out, std::vector< EntityHandle >& sets_out,
00338                                   std::vector< EntityHandle >& facets_out, EntityHandle root_set, double tolerance,
00339                                   const double ray_point[3], const double unit_ray_dir[3], const double* ray_length = 0,
00340                                   TrvStats* accum = 0 );
00341 
00342     ErrorCode ray_intersect_sets( EntityHandle root_set, double tolerance, const double ray_point[3],
00343                                   const double unit_ray_dir[3], IntersectSearchWindow& search_win,
00344                                   IntRegCtxt& register_intersection, TrvStats* accum = 0 );
00345 
00346     /**\brief Find closest surface, facet in surface, and location on facet
00347      *
00348      * Find the closest location in the tree to the specified location.
00349      *\param point Location to search from
00350      *\param point_out Closest location on closest facet
00351      *\param facet_out Closest 2D element to input position
00352      *\param set_out Set containing closest facet.  0 if tree was not
00353      *               constructed using 'set_build'
00354      */
00355     ErrorCode closest_to_location( const double* point, EntityHandle tree_root, double* point_out,
00356                                    EntityHandle& facet_out, EntityHandle* set_out = 0, TrvStats* accum = 0 );
00357 
00358     /**\brief Find closest facet(s) to input position.
00359      *
00360      * Find the closest location(s) in the tree to the specified location.
00361      *\param point Location to search from
00362      *\param facets_out Closest 2D elements to input position are appended to this list
00363      *\param sets_out If non-null, sets owning facets are appended to this list.
00364      */
00365     ErrorCode closest_to_location( const double* point, EntityHandle tree_root, double tolerance,
00366                                    std::vector< EntityHandle >& facets_out, std::vector< EntityHandle >* sets_out = 0,
00367                                    TrvStats* accum = 0 );
00368 
00369     /**\brief Find facets intersected by a sphere
00370      *
00371      * Find facets intersected by a spherical volume.
00372      *\param center     Sphere center
00373      *\param radius     Sphere radius
00374      *\param tree_root  Root of OBB tree
00375      *\param facets_out List of triangles intersecting sphere
00376      *\param sets_out   If not null, sets owning facets are appended to this
00377      *                  list in an order corresponding to the entries in
00378      *                  facets_out.
00379      */
00380     ErrorCode sphere_intersect_triangles( const double* center, double radius, EntityHandle tree_root,
00381                                           std::vector< EntityHandle >& facets_out,
00382                                           std::vector< EntityHandle >* sets_out = 0, TrvStats* accum = 0 );
00383 
00384     ErrorCode get_close_tris( CartVect int_pt, double tol, const EntityHandle* rootSet, const EntityHandle* geomVol,
00385                               const Tag* senseTag, std::vector< EntityHandle >& close_tris,
00386                               std::vector< int >& close_senses );
00387 
00388     /**\brief Get oriented box at node in tree
00389      *
00390      * Get the oriented box for a node in an oriented bounding box tree.
00391      */
00392     ErrorCode box( EntityHandle node_set, double center[3], double axis1[3], double axis2[3], double axis3[3] );
00393 
00394     ErrorCode delete_tree( EntityHandle root_set );
00395 
00396     /**\brief Remove obb tree root from the Oriented Box Tree Tool data structure
00397      *
00398      * Remove obb tree root from the Oriented Box Tree Tool data structure (createdTrees)
00399      */
00400     ErrorCode remove_root( EntityHandle root_set );
00401 
00402     /**\brief Print out tree
00403      *
00404      * Print the tree to an output stream in a human-readable form.
00405      *\param tree_root_set  Entity set representing tree root.
00406      *\param list_contents  If true, list entities in each tree node,
00407      *                      If false, just list number of entities.
00408      *\param id_tag_name    If specified, must be the name of an existing
00409      *                      integer tag containing an ID for the entities.
00410      *                      Not used if list_contents is false.
00411      */
00412     void print( EntityHandle tree_root_set, std::ostream& stream, bool list_contents = false,
00413                 const char* id_tag_name = 0 );
00414 
00415     /**\brief Print tree statistics
00416      *
00417      * Print misc. stats. describing tree
00418      */
00419     ErrorCode stats( EntityHandle tree_root_set, std::ostream& stream );
00420 
00421     /**\brief Get tree statistics
00422      *
00423      * Get summary stats. describing tree
00424      * \param set Root of tree for which data is requested
00425      * \param total_entities Entities in tree
00426      * \param root_volume Total volume of root box
00427      * \param tot_node_volume Total volume in all nodes
00428      * \param tot_to_root_volume Ratio of total / root volume
00429      * \param tree_height Maximum height of tree, from root to leaf
00430      * \param node_count Number of nodes in tree
00431      * \param num_leaves Number of leaf nodes in tree
00432      */
00433     ErrorCode stats( EntityHandle set, unsigned& entities_in_tree, double& root_volume, double& tot_node_volume,
00434                      double& tot_to_root_volume, unsigned& tree_height, unsigned& node_count, unsigned& num_leaves );
00435 
00436     /** \brief Implement this and pass instance to preorder_traverse
00437      *
00438      * This interface may be implemented and an instance passed to
00439      * preorder_traverse to define some operation to do when traversing
00440      * the tree.
00441      */
00442     class Op
00443     {
00444       public:
00445         /**\brief Visit a node in the tree during a traversal.
00446          *
00447          * This method is called for each node in the tree visited
00448          * during a pre-order traversal.
00449          *\param node The EntityHandle for the entity set for the tree node.
00450          *\param depth The current depth in the tree.
00451          *\param descend Output: if false, traversal will skip children
00452          *             of the current node, or if the current node is a
00453          *             leaf, the 'leaf' method will not be called.
00454          */
00455         virtual ErrorCode visit( EntityHandle node, int depth, bool& descend ) = 0;
00456 
00457         /**\brief Process a leaf node during tree traversal */
00458         virtual ErrorCode leaf( EntityHandle node ) = 0;
00459 
00460         virtual ~Op();  // probably isn't necessary in this case, and
00461                         // does nothing, but lots of compilers warn if
00462                         // virtual function but no virtual destructor.
00463     };
00464 
00465     /**\brief Visitor pattern - do operation for each tree node
00466      *
00467      * Do a preorder traversal of the tree, calling the method
00468      * in the passed operation instance for each node in the tree.
00469      * Parent node is visited before either child (pre-order traversal).
00470      * If operator method passes back the 'descend' argument as false,
00471      * traversal will not descend to the children of the current node.
00472      */
00473     ErrorCode preorder_traverse( EntityHandle root_set, Op& operation, TrvStats* accum = 0 );
00474 
00475     Interface* get_moab_instance() const
00476     {
00477         return instance;
00478     }
00479 
00480     struct SetData;
00481 
00482     /**\brief Get oriented box at node in tree
00483      *
00484      * Get the oriented box for a node in an oriented bounding box tree.
00485      *
00486      * NOTE: This function is provided for internal MOAB use only.
00487      *       The definition of OrientedBox is not available as a part
00488      *       of the MOAB API
00489      */
00490     ErrorCode box( EntityHandle node_set, OrientedBox& box );
00491 
00492   private:
00493     ErrorCode build_tree( const Range& entities, EntityHandle& set, int depth, const Settings& settings );
00494 
00495     ErrorCode build_sets( std::list< SetData >& sets, EntityHandle& node_set, int depth, const Settings& settings );
00496 
00497     ErrorCode recursive_stats( OrientedBoxTreeTool* tool, Interface* instance, EntityHandle set, int depth,
00498                                StatData& data, unsigned& count_out, CartVect& dimensions_out );
00499 
00500     Interface* instance;
00501     Tag tagHandle;
00502 
00503     bool cleanUpTrees;
00504     std::vector< EntityHandle > createdTrees;
00505 };
00506 
00507 }  // namespace moab
00508 
00509 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines