DOLFIN
DOLFIN C++ interface
GenericBoundingBoxTree.h
1 // Copyright (C) 2013 Anders Logg
2 //
3 // This file is part of DOLFIN.
4 //
5 // DOLFIN is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU Lesser General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // DOLFIN is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU Lesser General Public License for more details.
14 //
15 // You should have received a copy of the GNU Lesser General Public License
16 // along with DOLFIN. If not, see <http://www.gnu.org/licenses/>.
17 //
18 // First added: 2013-04-23
19 // Last changed: 2014-02-06
20 
21 #ifndef __GENERIC_BOUNDING_BOX_TREE_H
22 #define __GENERIC_BOUNDING_BOX_TREE_H
23 
24 #include <memory>
25 #include <sstream>
26 #include <set>
27 #include <vector>
28 #include <dolfin/geometry/Point.h>
29 
30 namespace dolfin
31 {
32 
33  // Forward declarations
34  class Mesh;
35  class MeshEntity;
36 
39 
41  {
42  public:
43 
46 
49 
51  static std::shared_ptr<GenericBoundingBoxTree> create(unsigned int dim);
52 
54  void build(const Mesh& mesh, std::size_t tdim);
55 
57  void build(const std::vector<Point>& points);
58 
60  std::vector<unsigned int>
61  compute_collisions(const Point& point) const;
62 
64  std::pair<std::vector<unsigned int>, std::vector<unsigned int> >
65  compute_collisions(const GenericBoundingBoxTree& tree) const;
66 
68  std::vector<unsigned int>
69  compute_entity_collisions(const Point& point,
70  const Mesh& mesh) const;
71 
73  std::vector<unsigned int>
74  compute_process_collisions(const Point& point) const;
75 
77  std::pair<std::vector<unsigned int>, std::vector<unsigned int> >
79  const Mesh& mesh_A, const Mesh& mesh_B) const;
80 
82  unsigned int compute_first_collision(const Point& point) const;
83 
85  unsigned int compute_first_entity_collision(const Point& point,
86  const Mesh& mesh) const;
87 
89  std::pair<unsigned int, double> compute_closest_entity(const Point& point,
90  const Mesh& mesh) const;
91 
93  std::pair<unsigned int, double> compute_closest_point(const Point& point) const;
94 
96  std::string str(bool verbose=false);
97 
98  protected:
99 
103  struct BBox
104  {
106  unsigned int child_0;
108  unsigned int child_1;
109  };
110 
112  std::size_t _tdim;
113 
115  std::vector<BBox> _bboxes;
116 
118  std::vector<double> _bbox_coordinates;
119 
121  mutable std::shared_ptr<GenericBoundingBoxTree> _point_search_tree;
122 
124  std::shared_ptr<GenericBoundingBoxTree> _global_tree;
125 
127  void clear();
128 
129  //--- Recursive build functions ---
130 
132  unsigned int _build(const std::vector<double>& leaf_bboxes,
133  const std::vector<unsigned int>::iterator& begin,
134  const std::vector<unsigned int>::iterator& end,
135  std::size_t gdim);
136 
138  unsigned int _build(const std::vector<Point>& points,
139  const std::vector<unsigned int>::iterator& begin,
140  const std::vector<unsigned int>::iterator& end,
141  std::size_t gdim);
142 
143  //--- Recursive search functions ---
144 
145  // Note that these functions are made static for consistency as
146  // some of them need to deal with more than tree.
147 
148  // Compute collisions with point (recursive)
149  static void
150  _compute_collisions(const GenericBoundingBoxTree& tree,
151  const Point& point,
152  unsigned int node,
153  std::vector<unsigned int>& entities,
154  const Mesh* mesh);
155 
156  // Compute collisions with tree (recursive)
157  static void
158  _compute_collisions(const GenericBoundingBoxTree& A,
159  const GenericBoundingBoxTree& B,
160  unsigned int node_A,
161  unsigned int node_B,
162  std::vector<unsigned int>& entities_A,
163  std::vector<unsigned int>& entities_B,
164  const Mesh* mesh_A,
165  const Mesh* mesh_B);
166 
167  // Compute first collision (recursive)
168  static unsigned int
169  _compute_first_collision(const GenericBoundingBoxTree& tree,
170  const Point& point,
171  unsigned int node);
172 
173  // Compute first entity collision (recursive)
174  static unsigned int
175  _compute_first_entity_collision(const GenericBoundingBoxTree& tree,
176  const Point& point,
177  unsigned int node,
178  const Mesh& mesh);
179 
180  // Compute closest entity (recursive)
181  static void _compute_closest_entity(const GenericBoundingBoxTree& tree,
182  const Point& point,
183  unsigned int node,
184  const Mesh& mesh,
185  unsigned int& closest_entity,
186  double& R2);
187 
188  // Compute closest point (recursive)
189  static void
190  _compute_closest_point(const GenericBoundingBoxTree& tree,
191  const Point& point,
192  unsigned int node,
193  unsigned int& closest_point,
194  double& R2);
195 
196  //--- Utility functions ---
197 
199  void build_point_search_tree(const Mesh& mesh) const;
200 
202  void compute_bbox_of_entity(double* b,
203  const MeshEntity& entity,
204  std::size_t gdim) const;
205 
207  void sort_points(std::size_t axis,
208  const std::vector<Point>& points,
209  const std::vector<unsigned int>::iterator& begin,
210  const std::vector<unsigned int>::iterator& middle,
211  const std::vector<unsigned int>::iterator& end);
212 
214  inline unsigned int add_bbox(const BBox& bbox,
215  const double* b,
216  std::size_t gdim)
217  {
218  // Add bounding box
219  _bboxes.push_back(bbox);
220 
221  // Add bounding box coordinates
222  for (std::size_t i = 0; i < 2*gdim; ++i)
223  _bbox_coordinates.push_back(b[i]);
224 
225  return _bboxes.size() - 1;
226  }
227 
229  inline const BBox& get_bbox(unsigned int node) const
230  {
231  return _bboxes[node];
232  }
233 
235  inline unsigned int num_bboxes() const
236  {
237  return _bboxes.size();
238  }
239 
241  inline unsigned int add_point(const BBox& bbox,
242  const Point& point,
243  std::size_t gdim)
244  {
245  // Add bounding box
246  _bboxes.push_back(bbox);
247 
248  // Add point coordinates (twice)
249  const double* x = point.coordinates();
250  for (std::size_t i = 0; i < gdim; ++i)
251  _bbox_coordinates.push_back(x[i]);
252  for (std::size_t i = 0; i < gdim; ++i)
253  _bbox_coordinates.push_back(x[i]);
254 
255  return _bboxes.size() - 1;
256  }
257 
259  inline bool is_leaf(const BBox& bbox, unsigned int node) const
260  {
261  // Leaf nodes are marked by setting child_0 equal to the node itself
262  return bbox.child_0 == node;
263  }
264 
269  {
271  const std::vector<Point>& points;
272 
274  less_x_point(const std::vector<Point>& points): points(points) {}
275 
277  inline bool operator()(unsigned int i, unsigned int j)
278  {
279  const double* pi = points[i].coordinates();
280  const double* pj = points[j].coordinates();
281  return pi[0] < pj[0];
282  }
283  };
284 
289  {
291  const std::vector<Point>& points;
292 
294  less_y_point(const std::vector<Point>& points): points(points) {}
295 
297  inline bool operator()(unsigned int i, unsigned int j)
298  {
299  const double* pi = points[i].coordinates();
300  const double* pj = points[j].coordinates();
301  return pi[1] < pj[1];
302  }
303  };
304 
309  {
311  const std::vector<Point>& points;
312 
314  less_z_point(const std::vector<Point>& points): points(points) {}
315 
317  inline bool operator()(unsigned int i, unsigned int j)
318  {
319  const double* pi = points[i].coordinates();
320  const double* pj = points[j].coordinates();
321  return pi[2] < pj[2];
322  }
323  };
324 
325  //--- Dimension-dependent functions to be implemented by subclass ---
326 
328  virtual std::size_t gdim() const = 0;
329 
331  virtual const double* get_bbox_coordinates(unsigned int node) const = 0;
332 
334  virtual bool
335  point_in_bbox(const double* x, unsigned int node) const = 0;
336 
338  virtual bool
339  bbox_in_bbox(const double* a, unsigned int node) const = 0;
340 
342  virtual double
343  compute_squared_distance_bbox(const double* x, unsigned int node) const = 0;
344 
346  virtual double
347  compute_squared_distance_point(const double* x, unsigned int node) const = 0;
348 
350  virtual void
351  compute_bbox_of_bboxes(double* bbox,
352  std::size_t& axis,
353  const std::vector<double>& leaf_bboxes,
354  const std::vector<unsigned int>::iterator& begin,
355  const std::vector<unsigned int>::iterator& end) = 0;
356 
358  virtual void
359  compute_bbox_of_points(double* bbox,
360  std::size_t& axis,
361  const std::vector<Point>& points,
362  const std::vector<unsigned int>::iterator& begin,
363  const std::vector<unsigned int>::iterator& end) = 0;
364 
366  virtual void
367  sort_bboxes(std::size_t axis,
368  const std::vector<double>& leaf_bboxes,
369  const std::vector<unsigned int>::iterator& begin,
370  const std::vector<unsigned int>::iterator& middle,
371  const std::vector<unsigned int>::iterator& end) = 0;
372 
374  void tree_print(std::stringstream& s, unsigned int i);
375 
376 
377  };
378 
379 }
380 
381 #endif
unsigned int child_0
Child 0.
Definition: GenericBoundingBoxTree.h:106
std::vector< unsigned int > compute_collisions(const Point &point) const
Compute all collisions between bounding boxes and Point
Definition: GenericBoundingBoxTree.cpp:150
unsigned int add_bbox(const BBox &bbox, const double *b, std::size_t gdim)
Add bounding box and coordinates.
Definition: GenericBoundingBoxTree.h:214
std::shared_ptr< GenericBoundingBoxTree > _global_tree
Global tree for mesh ownership of each process (same on all processes)
Definition: GenericBoundingBoxTree.h:124
std::pair< unsigned int, double > compute_closest_entity(const Point &point, const Mesh &mesh) const
Compute closest entity and distance to Point
Definition: GenericBoundingBoxTree.cpp:257
Definition: GenericBoundingBoxTree.h:308
GenericBoundingBoxTree()
Constructor.
Definition: GenericBoundingBoxTree.cpp:40
std::shared_ptr< GenericBoundingBoxTree > _point_search_tree
Point search tree used to accelerate distance queries.
Definition: GenericBoundingBoxTree.h:121
Definition: adapt.h:29
Definition: GenericBoundingBoxTree.h:40
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition: GenericBoundingBoxTree.h:277
Definition: Point.h:40
void begin(std::string msg,...)
Begin task (increase indentation level)
Definition: log.cpp:153
less_y_point(const std::vector< Point > &points)
Constructor.
Definition: GenericBoundingBoxTree.h:294
Definition: GenericBoundingBoxTree.h:268
virtual double compute_squared_distance_bbox(const double *x, unsigned int node) const =0
Compute squared distance between point and bounding box.
void build(const Mesh &mesh, std::size_t tdim)
Build bounding box tree for mesh entities of given dimension.
Definition: GenericBoundingBoxTree.cpp:70
std::string str(bool verbose=false)
Print out for debugging.
Definition: GenericBoundingBoxTree.cpp:778
std::pair< unsigned int, double > compute_closest_point(const Point &point) const
Compute closest point and distance to Point
Definition: GenericBoundingBoxTree.cpp:297
bool is_leaf(const BBox &bbox, unsigned int node) const
Check whether bounding box is a leaf node.
Definition: GenericBoundingBoxTree.h:259
unsigned int compute_first_collision(const Point &point) const
Compute first collision between bounding boxes and Point
Definition: GenericBoundingBoxTree.cpp:234
void sort_points(std::size_t axis, const std::vector< Point > &points, const std::vector< unsigned int >::iterator &begin, const std::vector< unsigned int >::iterator &middle, const std::vector< unsigned int >::iterator &end)
Sort points along given axis.
Definition: GenericBoundingBoxTree.cpp:759
void clear()
Clear existing data if any.
Definition: GenericBoundingBoxTree.cpp:324
void end()
End task (decrease indentation level)
Definition: log.cpp:168
const std::vector< Point > & points
Points.
Definition: GenericBoundingBoxTree.h:291
less_x_point(const std::vector< Point > &points)
Constructor.
Definition: GenericBoundingBoxTree.h:274
virtual double compute_squared_distance_point(const double *x, unsigned int node) const =0
Compute squared distance between point and point.
virtual void compute_bbox_of_points(double *bbox, std::size_t &axis, const std::vector< Point > &points, const std::vector< unsigned int >::iterator &begin, const std::vector< unsigned int >::iterator &end)=0
Compute bounding box of points.
virtual const double * get_bbox_coordinates(unsigned int node) const =0
Return bounding box coordinates for node.
std::size_t _tdim
Topological dimension of leaf entities.
Definition: GenericBoundingBoxTree.h:112
virtual bool point_in_bbox(const double *x, unsigned int node) const =0
Check whether point (x) is in bounding box (node)
const std::vector< Point > & points
Points.
Definition: GenericBoundingBoxTree.h:271
virtual bool bbox_in_bbox(const double *a, unsigned int node) const =0
Check whether bounding box (a) collides with bounding box (node)
std::vector< unsigned int > compute_process_collisions(const Point &point) const
Compute all collisions between processes and Point
Definition: GenericBoundingBoxTree.cpp:199
Definition: GenericBoundingBoxTree.h:103
virtual void compute_bbox_of_bboxes(double *bbox, std::size_t &axis, const std::vector< double > &leaf_bboxes, const std::vector< unsigned int >::iterator &begin, const std::vector< unsigned int >::iterator &end)=0
Compute bounding box of bounding boxes.
unsigned int child_1
Child 1.
Definition: GenericBoundingBoxTree.h:108
double * coordinates()
Definition: Point.h:132
virtual ~GenericBoundingBoxTree()
Destructor.
Definition: GenericBoundingBoxTree.h:48
unsigned int compute_first_entity_collision(const Point &point, const Mesh &mesh) const
Compute first collision between entities and Point
Definition: GenericBoundingBoxTree.cpp:241
std::vector< unsigned int > compute_entity_collisions(const Point &point, const Mesh &mesh) const
Compute all collisions between entities and Point
Definition: GenericBoundingBoxTree.cpp:180
Definition: MeshEntity.h:42
Definition: GenericBoundingBoxTree.h:288
unsigned int add_point(const BBox &bbox, const Point &point, std::size_t gdim)
Add bounding box and point coordinates.
Definition: GenericBoundingBoxTree.h:241
void compute_bbox_of_entity(double *b, const MeshEntity &entity, std::size_t gdim) const
Compute bounding box of mesh entity.
Definition: GenericBoundingBoxTree.cpp:727
static std::shared_ptr< GenericBoundingBoxTree > create(unsigned int dim)
Factory function returning (empty) tree of appropriate dimension.
Definition: GenericBoundingBoxTree.cpp:46
std::vector< BBox > _bboxes
List of bounding boxes (parent-child-entity relations)
Definition: GenericBoundingBoxTree.h:115
virtual void sort_bboxes(std::size_t axis, const std::vector< double > &leaf_bboxes, const std::vector< unsigned int >::iterator &begin, const std::vector< unsigned int >::iterator &middle, const std::vector< unsigned int >::iterator &end)=0
Sort leaf bounding boxes along given axis.
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition: GenericBoundingBoxTree.h:297
unsigned int num_bboxes() const
Return number of bounding boxes.
Definition: GenericBoundingBoxTree.h:235
std::vector< double > _bbox_coordinates
List of bounding box coordinates.
Definition: GenericBoundingBoxTree.h:118
void tree_print(std::stringstream &s, unsigned int i)
Print out recursively, for debugging.
Definition: GenericBoundingBoxTree.cpp:785
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition: GenericBoundingBoxTree.h:317
const BBox & get_bbox(unsigned int node) const
Return bounding box for given node.
Definition: GenericBoundingBoxTree.h:229
Definition: Mesh.h:82
less_z_point(const std::vector< Point > &points)
Constructor.
Definition: GenericBoundingBoxTree.h:314
virtual std::size_t gdim() const =0
Return geometric dimension.
unsigned int _build(const std::vector< double > &leaf_bboxes, const std::vector< unsigned int >::iterator &begin, const std::vector< unsigned int >::iterator &end, std::size_t gdim)
Build bounding box tree for entities (recursive)
Definition: GenericBoundingBoxTree.cpp:333
const std::vector< Point > & points
Points.
Definition: GenericBoundingBoxTree.h:311
void build_point_search_tree(const Mesh &mesh) const
Compute point search tree if not already done.
Definition: GenericBoundingBoxTree.cpp:707