Loading...
Searching...
No Matches
GenericBoundingBoxTree.h
// Copyright (C) 2013 Anders Logg
//
// This file is part of DOLFIN.
//
// DOLFIN is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// DOLFIN is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with DOLFIN. If not, see <http://www.gnu.org/licenses/>.
//
// First added: 2013-04-23
// Last changed: 2014-02-06
#ifndef __GENERIC_BOUNDING_BOX_TREE_H
#define __GENERIC_BOUNDING_BOX_TREE_H
#include <memory>
#include <sstream>
#include <set>
#include <vector>
#include <dolfin/geometry/Point.h>
namespace dolfin
{
// Forward declarations
class Mesh;
class MeshEntity;
class GenericBoundingBoxTree
{
public:
GenericBoundingBoxTree();
virtual ~GenericBoundingBoxTree() {}
static std::shared_ptr<GenericBoundingBoxTree> create(unsigned int dim);
void build(const Mesh& mesh, std::size_t tdim);
void build(const std::vector<Point>& points);
std::vector<unsigned int>
compute_collisions(const Point& point) const;
std::pair<std::vector<unsigned int>, std::vector<unsigned int> >
compute_collisions(const GenericBoundingBoxTree& tree) const;
std::vector<unsigned int>
compute_entity_collisions(const Point& point,
const Mesh& mesh) const;
std::vector<unsigned int>
compute_process_collisions(const Point& point) const;
std::pair<std::vector<unsigned int>, std::vector<unsigned int> >
compute_entity_collisions(const GenericBoundingBoxTree& tree,
const Mesh& mesh_A, const Mesh& mesh_B) const;
unsigned int compute_first_collision(const Point& point) const;
unsigned int compute_first_entity_collision(const Point& point,
const Mesh& mesh) const;
std::pair<unsigned int, double> compute_closest_entity(const Point& point,
const Mesh& mesh) const;
std::pair<unsigned int, double> compute_closest_point(const Point& point) const;
std::string str(bool verbose=false);
protected:
struct BBox
{
unsigned int child_0;
unsigned int child_1;
};
std::size_t _tdim;
std::vector<BBox> _bboxes;
std::vector<double> _bbox_coordinates;
mutable std::shared_ptr<GenericBoundingBoxTree> _point_search_tree;
std::shared_ptr<GenericBoundingBoxTree> _global_tree;
void clear();
//--- Recursive build functions ---
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);
unsigned int _build(const std::vector<Point>& points,
const std::vector<unsigned int>::iterator& begin,
const std::vector<unsigned int>::iterator& end,
std::size_t gdim);
//--- Recursive search functions ---
// Note that these functions are made static for consistency as
// some of them need to deal with more than tree.
// Compute collisions with point (recursive)
static void
_compute_collisions(const GenericBoundingBoxTree& tree,
const Point& point,
unsigned int node,
std::vector<unsigned int>& entities,
const Mesh* mesh);
// Compute collisions with tree (recursive)
static void
_compute_collisions(const GenericBoundingBoxTree& A,
const GenericBoundingBoxTree& B,
unsigned int node_A,
unsigned int node_B,
std::vector<unsigned int>& entities_A,
std::vector<unsigned int>& entities_B,
const Mesh* mesh_A,
const Mesh* mesh_B);
// Compute first collision (recursive)
static unsigned int
_compute_first_collision(const GenericBoundingBoxTree& tree,
const Point& point,
unsigned int node);
// Compute first entity collision (recursive)
static unsigned int
_compute_first_entity_collision(const GenericBoundingBoxTree& tree,
const Point& point,
unsigned int node,
const Mesh& mesh);
// Compute closest entity (recursive)
static void _compute_closest_entity(const GenericBoundingBoxTree& tree,
const Point& point,
unsigned int node,
const Mesh& mesh,
unsigned int& closest_entity,
double& R2);
// Compute closest point (recursive)
static void
_compute_closest_point(const GenericBoundingBoxTree& tree,
const Point& point,
unsigned int node,
unsigned int& closest_point,
double& R2);
//--- Utility functions ---
void build_point_search_tree(const Mesh& mesh) const;
void compute_bbox_of_entity(double* b,
const MeshEntity& entity,
std::size_t gdim) const;
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);
inline unsigned int add_bbox(const BBox& bbox,
const double* b,
std::size_t gdim)
{
// Add bounding box
_bboxes.push_back(bbox);
// Add bounding box coordinates
for (std::size_t i = 0; i < 2*gdim; ++i)
_bbox_coordinates.push_back(b[i]);
return _bboxes.size() - 1;
}
inline const BBox& get_bbox(unsigned int node) const
{
return _bboxes[node];
}
inline unsigned int num_bboxes() const
{
return _bboxes.size();
}
inline unsigned int add_point(const BBox& bbox,
const Point& point,
std::size_t gdim)
{
// Add bounding box
_bboxes.push_back(bbox);
// Add point coordinates (twice)
const double* x = point.coordinates();
for (std::size_t i = 0; i < gdim; ++i)
_bbox_coordinates.push_back(x[i]);
for (std::size_t i = 0; i < gdim; ++i)
_bbox_coordinates.push_back(x[i]);
return _bboxes.size() - 1;
}
inline bool is_leaf(const BBox& bbox, unsigned int node) const
{
// Leaf nodes are marked by setting child_0 equal to the node itself
return bbox.child_0 == node;
}
struct less_x_point
{
const std::vector<Point>& points;
less_x_point(const std::vector<Point>& points): points(points) {}
inline bool operator()(unsigned int i, unsigned int j)
{
const double* pi = points[i].coordinates();
const double* pj = points[j].coordinates();
return pi[0] < pj[0];
}
};
struct less_y_point
{
const std::vector<Point>& points;
less_y_point(const std::vector<Point>& points): points(points) {}
inline bool operator()(unsigned int i, unsigned int j)
{
const double* pi = points[i].coordinates();
const double* pj = points[j].coordinates();
return pi[1] < pj[1];
}
};
struct less_z_point
{
const std::vector<Point>& points;
less_z_point(const std::vector<Point>& points): points(points) {}
inline bool operator()(unsigned int i, unsigned int j)
{
const double* pi = points[i].coordinates();
const double* pj = points[j].coordinates();
return pi[2] < pj[2];
}
};
//--- Dimension-dependent functions to be implemented by subclass ---
virtual std::size_t gdim() const = 0;
virtual const double* get_bbox_coordinates(unsigned int node) const = 0;
virtual bool
point_in_bbox(const double* x, unsigned int node) const = 0;
virtual bool
bbox_in_bbox(const double* a, unsigned int node) const = 0;
virtual double
compute_squared_distance_bbox(const double* x, unsigned int node) const = 0;
virtual double
compute_squared_distance_point(const double* x, unsigned int node) const = 0;
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;
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;
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;
void tree_print(std::stringstream& s, unsigned int i);
};
}
#endif
dolfin::GenericBoundingBoxTree
Definition GenericBoundingBoxTree.h:41
dolfin::GenericBoundingBoxTree::_global_tree
std::shared_ptr< GenericBoundingBoxTree > _global_tree
Global tree for mesh ownership of each process (same on all processes).
Definition GenericBoundingBoxTree.h:124
dolfin::GenericBoundingBoxTree::bbox_in_bbox
virtual bool bbox_in_bbox(const double *a, unsigned int node) const =0
Check whether bounding box (a) collides with bounding box (node).
dolfin::GenericBoundingBoxTree::compute_squared_distance_bbox
virtual double compute_squared_distance_bbox(const double *x, unsigned int node) const =0
Compute squared distance between point and bounding box.
dolfin::GenericBoundingBoxTree::GenericBoundingBoxTree
GenericBoundingBoxTree()
Constructor.
Definition GenericBoundingBoxTree.cpp:40
dolfin::GenericBoundingBoxTree::compute_first_collision
unsigned int compute_first_collision(const Point &point) const
Compute first collision between bounding boxes and Point.
Definition GenericBoundingBoxTree.cpp:238
dolfin::GenericBoundingBoxTree::sort_points
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:763
dolfin::GenericBoundingBoxTree::compute_first_entity_collision
unsigned int compute_first_entity_collision(const Point &point, const Mesh &mesh) const
Compute first collision between entities and Point.
Definition GenericBoundingBoxTree.cpp:245
dolfin::GenericBoundingBoxTree::add_bbox
unsigned int add_bbox(const BBox &bbox, const double *b, std::size_t gdim)
Add bounding box and coordinates.
Definition GenericBoundingBoxTree.h:214
dolfin::GenericBoundingBoxTree::point_in_bbox
virtual bool point_in_bbox(const double *x, unsigned int node) const =0
Check whether point (x) is in bounding box (node).
dolfin::GenericBoundingBoxTree::_tdim
std::size_t _tdim
Topological dimension of leaf entities.
Definition GenericBoundingBoxTree.h:112
dolfin::GenericBoundingBoxTree::~GenericBoundingBoxTree
virtual ~GenericBoundingBoxTree()
Destructor.
Definition GenericBoundingBoxTree.h:48
dolfin::GenericBoundingBoxTree::_bbox_coordinates
std::vector< double > _bbox_coordinates
List of bounding box coordinates.
Definition GenericBoundingBoxTree.h:118
dolfin::GenericBoundingBoxTree::compute_closest_entity
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:261
dolfin::GenericBoundingBoxTree::_build
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:337
dolfin::GenericBoundingBoxTree::num_bboxes
unsigned int num_bboxes() const
Return number of bounding boxes.
Definition GenericBoundingBoxTree.h:235
dolfin::GenericBoundingBoxTree::compute_collisions
std::vector< unsigned int > compute_collisions(const Point &point) const
Compute all collisions between bounding boxes and Point.
Definition GenericBoundingBoxTree.cpp:154
dolfin::GenericBoundingBoxTree::sort_bboxes
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.
dolfin::GenericBoundingBoxTree::compute_bbox_of_points
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.
dolfin::GenericBoundingBoxTree::compute_bbox_of_bboxes
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.
dolfin::GenericBoundingBoxTree::add_point
unsigned int add_point(const BBox &bbox, const Point &point, std::size_t gdim)
Add bounding box and point coordinates.
Definition GenericBoundingBoxTree.h:241
dolfin::GenericBoundingBoxTree::clear
void clear()
Clear existing data if any.
Definition GenericBoundingBoxTree.cpp:328
dolfin::GenericBoundingBoxTree::compute_process_collisions
std::vector< unsigned int > compute_process_collisions(const Point &point) const
Compute all collisions between processes and Point.
Definition GenericBoundingBoxTree.cpp:203
dolfin::GenericBoundingBoxTree::compute_entity_collisions
std::vector< unsigned int > compute_entity_collisions(const Point &point, const Mesh &mesh) const
Compute all collisions between entities and Point.
Definition GenericBoundingBoxTree.cpp:184
dolfin::GenericBoundingBoxTree::_bboxes
std::vector< BBox > _bboxes
List of bounding boxes (parent-child-entity relations).
Definition GenericBoundingBoxTree.h:115
dolfin::GenericBoundingBoxTree::compute_squared_distance_point
virtual double compute_squared_distance_point(const double *x, unsigned int node) const =0
Compute squared distance between point and point.
dolfin::GenericBoundingBoxTree::gdim
virtual std::size_t gdim() const =0
Return geometric dimension.
dolfin::GenericBoundingBoxTree::tree_print
void tree_print(std::stringstream &s, unsigned int i)
Print out recursively, for debugging.
Definition GenericBoundingBoxTree.cpp:789
dolfin::GenericBoundingBoxTree::is_leaf
bool is_leaf(const BBox &bbox, unsigned int node) const
Check whether bounding box is a leaf node.
Definition GenericBoundingBoxTree.h:259
dolfin::GenericBoundingBoxTree::compute_bbox_of_entity
void compute_bbox_of_entity(double *b, const MeshEntity &entity, std::size_t gdim) const
Compute bounding box of mesh entity.
Definition GenericBoundingBoxTree.cpp:731
dolfin::GenericBoundingBoxTree::_point_search_tree
std::shared_ptr< GenericBoundingBoxTree > _point_search_tree
Point search tree used to accelerate distance queries.
Definition GenericBoundingBoxTree.h:121
dolfin::GenericBoundingBoxTree::get_bbox
const BBox & get_bbox(unsigned int node) const
Return bounding box for given node.
Definition GenericBoundingBoxTree.h:229
dolfin::GenericBoundingBoxTree::build_point_search_tree
void build_point_search_tree(const Mesh &mesh) const
Compute point search tree if not already done.
Definition GenericBoundingBoxTree.cpp:711
dolfin::GenericBoundingBoxTree::create
static std::shared_ptr< GenericBoundingBoxTree > create(unsigned int dim)
Factory function returning (empty) tree of appropriate dimension.
Definition GenericBoundingBoxTree.cpp:46
dolfin::GenericBoundingBoxTree::compute_closest_point
std::pair< unsigned int, double > compute_closest_point(const Point &point) const
Compute closest point and distance to Point.
Definition GenericBoundingBoxTree.cpp:301
dolfin::GenericBoundingBoxTree::str
std::string str(bool verbose=false)
Print out for debugging.
Definition GenericBoundingBoxTree.cpp:782
dolfin::GenericBoundingBoxTree::get_bbox_coordinates
virtual const double * get_bbox_coordinates(unsigned int node) const =0
Return bounding box coordinates for node.
dolfin::GenericBoundingBoxTree::build
void build(const Mesh &mesh, std::size_t tdim)
Build bounding box tree for mesh entities of given dimension.
Definition GenericBoundingBoxTree.cpp:70
dolfin::MeshEntity
Definition MeshEntity.h:43
dolfin::Mesh
Definition Mesh.h:84
dolfin::Point
Definition Point.h:41
dolfin::Point::coordinates
double * coordinates()
Definition Point.h:132
dolfin
Definition adapt.h:30
dolfin::begin
void begin(std::string msg,...)
Begin task (increase indentation level).
Definition log.cpp:153
dolfin::end
void end()
End task (decrease indentation level).
Definition log.cpp:168
dolfin::GenericBoundingBoxTree::BBox
Definition GenericBoundingBoxTree.h:104
dolfin::GenericBoundingBoxTree::BBox::child_1
unsigned int child_1
Child 1.
Definition GenericBoundingBoxTree.h:108
dolfin::GenericBoundingBoxTree::BBox::child_0
unsigned int child_0
Child 0.
Definition GenericBoundingBoxTree.h:106
dolfin::GenericBoundingBoxTree::less_x_point::operator()
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition GenericBoundingBoxTree.h:277
dolfin::GenericBoundingBoxTree::less_x_point::less_x_point
less_x_point(const std::vector< Point > &points)
Constructor.
Definition GenericBoundingBoxTree.h:274
dolfin::GenericBoundingBoxTree::less_x_point::points
const std::vector< Point > & points
Points.
Definition GenericBoundingBoxTree.h:271
dolfin::GenericBoundingBoxTree::less_y_point::points
const std::vector< Point > & points
Points.
Definition GenericBoundingBoxTree.h:291
dolfin::GenericBoundingBoxTree::less_y_point::less_y_point
less_y_point(const std::vector< Point > &points)
Constructor.
Definition GenericBoundingBoxTree.h:294
dolfin::GenericBoundingBoxTree::less_y_point::operator()
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition GenericBoundingBoxTree.h:297
dolfin::GenericBoundingBoxTree::less_z_point::less_z_point
less_z_point(const std::vector< Point > &points)
Constructor.
Definition GenericBoundingBoxTree.h:314
dolfin::GenericBoundingBoxTree::less_z_point::operator()
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition GenericBoundingBoxTree.h:317
dolfin::GenericBoundingBoxTree::less_z_point::points
const std::vector< Point > & points
Points.
Definition GenericBoundingBoxTree.h:311