DOLFIN
DOLFIN C++ interface
Loading...
Searching...
No Matches
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
30namespace 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> >
66
68 std::vector<unsigned int>
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
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
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
Definition GenericBoundingBoxTree.h:41
std::shared_ptr< GenericBoundingBoxTree > _global_tree
Global tree for mesh ownership of each process (same on all processes)
Definition GenericBoundingBoxTree.h:124
virtual bool bbox_in_bbox(const double *a, unsigned int node) const =0
Check whether bounding box (a) collides with bounding box (node)
virtual double compute_squared_distance_bbox(const double *x, unsigned int node) const =0
Compute squared distance between point and bounding box.
GenericBoundingBoxTree()
Constructor.
Definition GenericBoundingBoxTree.cpp:40
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
unsigned int compute_first_entity_collision(const Point &point, const Mesh &mesh) const
Compute first collision between entities and Point
Definition GenericBoundingBoxTree.cpp:241
unsigned int add_bbox(const BBox &bbox, const double *b, std::size_t gdim)
Add bounding box and coordinates.
Definition GenericBoundingBoxTree.h:214
virtual bool point_in_bbox(const double *x, unsigned int node) const =0
Check whether point (x) is in bounding box (node)
std::size_t _tdim
Topological dimension of leaf entities.
Definition GenericBoundingBoxTree.h:112
virtual ~GenericBoundingBoxTree()
Destructor.
Definition GenericBoundingBoxTree.h:48
std::vector< double > _bbox_coordinates
List of bounding box coordinates.
Definition GenericBoundingBoxTree.h:118
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
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
unsigned int num_bboxes() const
Return number of bounding boxes.
Definition GenericBoundingBoxTree.h:235
std::vector< unsigned int > compute_collisions(const Point &point) const
Compute all collisions between bounding boxes and Point
Definition GenericBoundingBoxTree.cpp:150
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.
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 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 add_point(const BBox &bbox, const Point &point, std::size_t gdim)
Add bounding box and point coordinates.
Definition GenericBoundingBoxTree.h:241
void clear()
Clear existing data if any.
Definition GenericBoundingBoxTree.cpp:324
std::vector< unsigned int > compute_process_collisions(const Point &point) const
Compute all collisions between processes and Point
Definition GenericBoundingBoxTree.cpp:199
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
std::vector< BBox > _bboxes
List of bounding boxes (parent-child-entity relations)
Definition GenericBoundingBoxTree.h:115
virtual double compute_squared_distance_point(const double *x, unsigned int node) const =0
Compute squared distance between point and point.
virtual std::size_t gdim() const =0
Return geometric dimension.
void tree_print(std::stringstream &s, unsigned int i)
Print out recursively, for debugging.
Definition GenericBoundingBoxTree.cpp:785
bool is_leaf(const BBox &bbox, unsigned int node) const
Check whether bounding box is a leaf node.
Definition GenericBoundingBoxTree.h:259
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
std::shared_ptr< GenericBoundingBoxTree > _point_search_tree
Point search tree used to accelerate distance queries.
Definition GenericBoundingBoxTree.h:121
const BBox & get_bbox(unsigned int node) const
Return bounding box for given node.
Definition GenericBoundingBoxTree.h:229
void build_point_search_tree(const Mesh &mesh) const
Compute point search tree if not already done.
Definition GenericBoundingBoxTree.cpp:707
static std::shared_ptr< GenericBoundingBoxTree > create(unsigned int dim)
Factory function returning (empty) tree of appropriate dimension.
Definition GenericBoundingBoxTree.cpp:46
std::pair< unsigned int, double > compute_closest_point(const Point &point) const
Compute closest point and distance to Point
Definition GenericBoundingBoxTree.cpp:297
std::string str(bool verbose=false)
Print out for debugging.
Definition GenericBoundingBoxTree.cpp:778
virtual const double * get_bbox_coordinates(unsigned int node) const =0
Return bounding box coordinates for node.
void build(const Mesh &mesh, std::size_t tdim)
Build bounding box tree for mesh entities of given dimension.
Definition GenericBoundingBoxTree.cpp:70
Definition MeshEntity.h:43
Definition Mesh.h:84
Definition Point.h:41
double * coordinates()
Definition Point.h:132
Definition adapt.h:30
void begin(std::string msg,...)
Begin task (increase indentation level)
Definition log.cpp:153
void end()
End task (decrease indentation level)
Definition log.cpp:168
Definition GenericBoundingBoxTree.h:104
unsigned int child_1
Child 1.
Definition GenericBoundingBoxTree.h:108
unsigned int child_0
Child 0.
Definition GenericBoundingBoxTree.h:106
Definition GenericBoundingBoxTree.h:269
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition GenericBoundingBoxTree.h:277
less_x_point(const std::vector< Point > &points)
Constructor.
Definition GenericBoundingBoxTree.h:274
const std::vector< Point > & points
Points.
Definition GenericBoundingBoxTree.h:271
Definition GenericBoundingBoxTree.h:289
const std::vector< Point > & points
Points.
Definition GenericBoundingBoxTree.h:291
less_y_point(const std::vector< Point > &points)
Constructor.
Definition GenericBoundingBoxTree.h:294
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition GenericBoundingBoxTree.h:297
Definition GenericBoundingBoxTree.h:309
less_z_point(const std::vector< Point > &points)
Constructor.
Definition GenericBoundingBoxTree.h:314
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition GenericBoundingBoxTree.h:317
const std::vector< Point > & points
Points.
Definition GenericBoundingBoxTree.h:311