MOAB: Mesh Oriented datABase
(version 5.2.1)
|
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