Branch data Line data Source code
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 : : */
42 : : class OrientedBoxTreeTool
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.
97 : : double worst_split_ratio;
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.
102 : : double best_split_ratio;
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 : :
111 : : ~OrientedBoxTreeTool();
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 : :
181 : : TrvStats() : ray_tri_tests_count( 0 ) {}
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 : :
216 [ + - ][ + - ]: 5268 : class IntRegCtxt
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 */
227 : 51 : virtual ErrorCode register_intersection( EntityHandle set, EntityHandle tri, double dist,
228 : : IntersectSearchWindow& /* search_win */,
229 : : GeomUtil::intersection_type /* int_type */ )
230 : : {
231 : 51 : intersections.push_back( dist );
232 : 51 : sets.push_back( set );
233 : 51 : facets.push_back( tri );
234 : :
235 : 51 : return MB_SUCCESS;
236 : : };
237 : :
238 : : /* determine the orientation of the topological set with respect to any
239 : : topological set in the context */
240 : 1375 : virtual ErrorCode update_orient( EntityHandle /* set */, int* /* surfTriOrient */ )
241 : : {
242 : 1375 : return MB_SUCCESS;
243 : : };
244 : :
245 : : /* determine whether or not a preferred orientation is established */
246 : 836 : virtual const int* getDesiredOrient()
247 : : {
248 : 836 : return NULL;
249 : : };
250 : :
251 : 1756 : std::vector< double > get_intersections()
252 : : {
253 : 1756 : return intersections;
254 : : };
255 : 1756 : std::vector< EntityHandle > get_facets()
256 : : {
257 : 1756 : return facets;
258 : : };
259 : 1756 : std::vector< EntityHandle > get_sets()
260 : : {
261 : 1756 : return sets;
262 : : };
263 : : };
264 : :
265 : : /**\brief Intersect a ray with the triangles contained within the tree
266 : : *
267 : : * Intersect a ray with the triangles contained in the tree and return
268 : : * the distance at which the intersection occured.
269 : : *\param distances_out The output list of intersection points on the ray.
270 : : *\param facets_out Handles of intersected triangles corresponding to distances_out
271 : : *\param root_set The MBENTITYSET representing the root of the tree.
272 : : *\param tolerance The tolerance to use in intersection checks.
273 : : *\param ray_point The base point of the ray.
274 : : *\param unit_ray_dir The ray direction vector (must be unit length)
275 : : *\param ray_length Optional ray length (intersect segment instead of ray.)
276 : : */
277 : : ErrorCode ray_intersect_triangles( std::vector< double >& distances_out, std::vector< EntityHandle >& facets_out,
278 : : EntityHandle root_set, double tolerance, const double ray_point[3],
279 : : const double unit_ray_dir[3], const double* ray_length = 0,
280 : : TrvStats* accum = 0 );
281 : :
282 : : /**\brief Intersect ray with tree
283 : : *
284 : : * Return the tree nodes (as MBENTITYSET handles) for the leaf boxes
285 : : * of the tree intersected by a ray.
286 : : *\param boxes_out The boxes intersected by the ray.
287 : : *\param tolerance The tolerance to use in intersection checks.
288 : : *\param ray_point The base point of the ray.
289 : : *\param unit_ray_dir The ray direction vector (must be unit length)
290 : : *\param ray_length Optional ray length (intersect segment instead of ray.)
291 : : */
292 : : ErrorCode ray_intersect_boxes( Range& boxes_out, EntityHandle root_set, double tolerance, const double ray_point[3],
293 : : const double unit_ray_dir[3], const double* ray_length = 0, TrvStats* accum = 0 );
294 : :
295 : : /**\brief Intersect ray with triangles contained in passed MBENTITYSETs
296 : : *
297 : : * \param raytri_test_count If non-NULL, count of ray-triangle intersect tests
298 : : * will be added to the value at which this points.
299 : : */
300 : : ErrorCode ray_intersect_triangles( std::vector< double >& intersection_distances_out,
301 : : std::vector< EntityHandle >& intersection_facets_out,
302 : : const Range& leaf_boxes_containing_tris, double tolerance,
303 : : const double ray_point[3], const double unit_ray_dir[3],
304 : : const double* ray_length = 0, unsigned int* raytri_test_count = 0 );
305 : :
306 : : /**\brief Intersect a ray with the triangles contained within the tree
307 : : *
308 : : * Intersect a ray with the triangles contained in the tree and return
309 : : * the distance at which the intersection occured.
310 : : *\param distances_out The output list of intersection points on the ray.
311 : : *\param sets_out The contained set encountered during the tree traversal
312 : : * (see 'set_build'). For the most common use, this is the
313 : : * set corresponding to the geometric surface containing the
314 : : * intersected triangle.
315 : : *\param facets_out Handles of intersected triangles corresponding to distances_out
316 : : *\param root_set The MBENTITYSET representing the root of the tree.
317 : : *\param tolerance The tolerance to use in intersection checks.
318 : : *\param ray_point The base point of the ray.
319 : : *\param unit_ray_dir The ray direction vector (must be unit length)
320 : : *\param search_win An interval that defines the current window in which the
321 : : * an intersection is being sought: (nonnegative, negative)
322 : : *\param register_intersection A context for assessing and registering intersections
323 : : * derived from IntRegCtxt
324 : : *\param accum Optional class for tree traversal statistics.
325 : : */
326 : :
327 : : ErrorCode ray_intersect_sets( std::vector< double >& distances_out, std::vector< EntityHandle >& sets_out,
328 : : std::vector< EntityHandle >& facets_out, EntityHandle root_set, double tolerance,
329 : : const double ray_point[3], const double unit_ray_dir[3],
330 : : IntersectSearchWindow& search_win, IntRegCtxt& register_intersection,
331 : : TrvStats* accum = 0 );
332 : :
333 : : /*\brief Version that doesn't require a search window or an intersection registration context
334 : : *
335 : : *
336 : : */
337 : : ErrorCode ray_intersect_sets( std::vector< double >& distances_out, std::vector< EntityHandle >& sets_out,
338 : : std::vector< EntityHandle >& facets_out, EntityHandle root_set, double tolerance,
339 : : const double ray_point[3], const double unit_ray_dir[3], const double* ray_length = 0,
340 : : TrvStats* accum = 0 );
341 : :
342 : : ErrorCode ray_intersect_sets( EntityHandle root_set, double tolerance, const double ray_point[3],
343 : : const double unit_ray_dir[3], IntersectSearchWindow& search_win,
344 : : IntRegCtxt& register_intersection, TrvStats* accum = 0 );
345 : :
346 : : /**\brief Find closest surface, facet in surface, and location on facet
347 : : *
348 : : * Find the closest location in the tree to the specified location.
349 : : *\param point Location to search from
350 : : *\param point_out Closest location on closest facet
351 : : *\param facet_out Closest 2D element to input position
352 : : *\param set_out Set containing closest facet. 0 if tree was not
353 : : * constructed using 'set_build'
354 : : */
355 : : ErrorCode closest_to_location( const double* point, EntityHandle tree_root, double* point_out,
356 : : EntityHandle& facet_out, EntityHandle* set_out = 0, TrvStats* accum = 0 );
357 : :
358 : : /**\brief Find closest facet(s) to input position.
359 : : *
360 : : * Find the closest location(s) in the tree to the specified location.
361 : : *\param point Location to search from
362 : : *\param facets_out Closest 2D elements to input position are appended to this list
363 : : *\param sets_out If non-null, sets owning facets are appended to this list.
364 : : */
365 : : ErrorCode closest_to_location( const double* point, EntityHandle tree_root, double tolerance,
366 : : std::vector< EntityHandle >& facets_out, std::vector< EntityHandle >* sets_out = 0,
367 : : TrvStats* accum = 0 );
368 : :
369 : : /**\brief Find facets intersected by a sphere
370 : : *
371 : : * Find facets intersected by a spherical volume.
372 : : *\param center Sphere center
373 : : *\param radius Sphere radius
374 : : *\param tree_root Root of OBB tree
375 : : *\param facets_out List of triangles intersecting sphere
376 : : *\param sets_out If not null, sets owning facets are appended to this
377 : : * list in an order corresponding to the entries in
378 : : * facets_out.
379 : : */
380 : : ErrorCode sphere_intersect_triangles( const double* center, double radius, EntityHandle tree_root,
381 : : std::vector< EntityHandle >& facets_out,
382 : : std::vector< EntityHandle >* sets_out = 0, TrvStats* accum = 0 );
383 : :
384 : : ErrorCode get_close_tris( CartVect int_pt, double tol, const EntityHandle* rootSet, const EntityHandle* geomVol,
385 : : const Tag* senseTag, std::vector< EntityHandle >& close_tris,
386 : : std::vector< int >& close_senses );
387 : :
388 : : /**\brief Get oriented box at node in tree
389 : : *
390 : : * Get the oriented box for a node in an oriented bounding box tree.
391 : : */
392 : : ErrorCode box( EntityHandle node_set, double center[3], double axis1[3], double axis2[3], double axis3[3] );
393 : :
394 : : ErrorCode delete_tree( EntityHandle root_set );
395 : :
396 : : /**\brief Remove obb tree root from the Oriented Box Tree Tool data structure
397 : : *
398 : : * Remove obb tree root from the Oriented Box Tree Tool data structure (createdTrees)
399 : : */
400 : : ErrorCode remove_root( EntityHandle root_set );
401 : :
402 : : /**\brief Print out tree
403 : : *
404 : : * Print the tree to an output stream in a human-readable form.
405 : : *\param tree_root_set Entity set representing tree root.
406 : : *\param list_contents If true, list entities in each tree node,
407 : : * If false, just list number of entities.
408 : : *\param id_tag_name If specified, must be the name of an existing
409 : : * integer tag containing an ID for the entities.
410 : : * Not used if list_contents is false.
411 : : */
412 : : void print( EntityHandle tree_root_set, std::ostream& stream, bool list_contents = false,
413 : : const char* id_tag_name = 0 );
414 : :
415 : : /**\brief Print tree statistics
416 : : *
417 : : * Print misc. stats. describing tree
418 : : */
419 : : ErrorCode stats( EntityHandle tree_root_set, std::ostream& stream );
420 : :
421 : : /**\brief Get tree statistics
422 : : *
423 : : * Get summary stats. describing tree
424 : : * \param set Root of tree for which data is requested
425 : : * \param total_entities Entities in tree
426 : : * \param root_volume Total volume of root box
427 : : * \param tot_node_volume Total volume in all nodes
428 : : * \param tot_to_root_volume Ratio of total / root volume
429 : : * \param tree_height Maximum height of tree, from root to leaf
430 : : * \param node_count Number of nodes in tree
431 : : * \param num_leaves Number of leaf nodes in tree
432 : : */
433 : : ErrorCode stats( EntityHandle set, unsigned& entities_in_tree, double& root_volume, double& tot_node_volume,
434 : : double& tot_to_root_volume, unsigned& tree_height, unsigned& node_count, unsigned& num_leaves );
435 : :
436 : : /** \brief Implement this and pass instance to preorder_traverse
437 : : *
438 : : * This interface may be implemented and an instance passed to
439 : : * preorder_traverse to define some operation to do when traversing
440 : : * the tree.
441 : : */
442 : 1756 : class Op
443 : : {
444 : : public:
445 : : /**\brief Visit a node in the tree during a traversal.
446 : : *
447 : : * This method is called for each node in the tree visited
448 : : * during a pre-order traversal.
449 : : *\param node The EntityHandle for the entity set for the tree node.
450 : : *\param depth The current depth in the tree.
451 : : *\param descend Output: if false, traversal will skip children
452 : : * of the current node, or if the current node is a
453 : : * leaf, the 'leaf' method will not be called.
454 : : */
455 : : virtual ErrorCode visit( EntityHandle node, int depth, bool& descend ) = 0;
456 : :
457 : : /**\brief Process a leaf node during tree traversal */
458 : : virtual ErrorCode leaf( EntityHandle node ) = 0;
459 : :
460 : : virtual ~Op(); // probably isn't necessary in this case, and
461 : : // does nothing, but lots of compilers warn if
462 : : // virtual function but no virtual destructor.
463 : : };
464 : :
465 : : /**\brief Visitor pattern - do operation for each tree node
466 : : *
467 : : * Do a preorder traversal of the tree, calling the method
468 : : * in the passed operation instance for each node in the tree.
469 : : * Parent node is visited before either child (pre-order traversal).
470 : : * If operator method passes back the 'descend' argument as false,
471 : : * traversal will not descend to the children of the current node.
472 : : */
473 : : ErrorCode preorder_traverse( EntityHandle root_set, Op& operation, TrvStats* accum = 0 );
474 : :
475 : 40405 : Interface* get_moab_instance() const
476 : : {
477 : 40405 : return instance;
478 : : }
479 : :
480 : : struct SetData;
481 : :
482 : : /**\brief Get oriented box at node in tree
483 : : *
484 : : * Get the oriented box for a node in an oriented bounding box tree.
485 : : *
486 : : * NOTE: This function is provided for internal MOAB use only.
487 : : * The definition of OrientedBox is not available as a part
488 : : * of the MOAB API
489 : : */
490 : : ErrorCode box( EntityHandle node_set, OrientedBox& box );
491 : :
492 : : private:
493 : : ErrorCode build_tree( const Range& entities, EntityHandle& set, int depth, const Settings& settings );
494 : :
495 : : ErrorCode build_sets( std::list< SetData >& sets, EntityHandle& node_set, int depth, const Settings& settings );
496 : :
497 : : ErrorCode recursive_stats( OrientedBoxTreeTool* tool, Interface* instance, EntityHandle set, int depth,
498 : : StatData& data, unsigned& count_out, CartVect& dimensions_out );
499 : :
500 : : Interface* instance;
501 : : Tag tagHandle;
502 : :
503 : : bool cleanUpTrees;
504 : : std::vector< EntityHandle > createdTrees;
505 : : };
506 : :
507 : : } // namespace moab
508 : :
509 : : #endif
|
