Flow123d  master-f44eb46
inspect_elements_algorithm.hh
Go to the documentation of this file.
1 /*!
2  *
3 * Copyright (C) 2015 Technical University of Liberec. All rights reserved.
4  *
5  * This program is free software; you can redistribute it and/or modify it under
6  * the terms of the GNU General Public License version 3 as published by the
7  * Free Software Foundation. (http://www.gnu.org/licenses/gpl-3.0.en.html)
8  *
9  * This program is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12  *
13  *
14  * @file intersection_local.hh
15  * @brief Classes with algorithms for computation of intersections of meshes.
16  * @author Pavel Exner
17  *
18  */
19 
20 #ifndef INSPECT_ELEMENTS_ALGORITHM_H_
21 #define INSPECT_ELEMENTS_ALGORITHM_H_
22 
23 #include "mesh/bounding_box.hh"
24 
25 // #include "simplex.hh"
26 
27 #include <queue>
28 
29 class Mesh; // forward declare
30 class BIHTree;
31 
32 template<unsigned int N, unsigned int M> class IntersectionPointAux;
33 template<unsigned int N, unsigned int M> class IntersectionAux;
34 template<unsigned int N, unsigned int M> class IntersectionLocal;
37 template <int spacedim> class ElementAccessor;
38 
39 
40 /// First = element index, Second = pointer to intersection object.
41 typedef std::pair<unsigned int, IntersectionLocalBase*> ILpair;
42 
43 template<unsigned int dimA, unsigned int dimB>
45 public:
47 protected:
48 
49  /// Auxiliary function that translates @p ElementAccessor<3> to @p Simplex<simplex_dim>.
50 // template<unsigned int simplex_dim>
51 // void update_simplex(const ElementAccessor<3> &element, Simplex<simplex_dim> & simplex);
52 
53  /// Mesh pointer.
55 
56  const unsigned int undefined_elm_idx_ = -1;
57 
58  /// Objects representing single elements.
59 // Simplex<dimA> simplexA;
60 // Simplex<dimB> simplexB;
61 };
62 
63 /** @brief Class implements algorithm for dim-dimensional intersections with 3D elements.
64  *
65  * @p dim-D elements that are continuously neighbouring are called component elements.
66  * 3D elements are called bulk elements.
67  *
68  * Implements the initialization routine, that finds the first candidate for intersection.
69  * It uses bounding boxes to fastly resolve intersection candidates.
70  * We call elements whose bounding boxes are intersecting 'candidates'.
71  *
72  * Finding first candidate:
73  * - BIH search algorithm - build BIH and use it to find first candidates of components
74  * - BB search algorithm - compute only bounding boxes and search through till finding candidates
75  *
76  * Implements prolongation algorithm that recursively searches neighbouring elements for next intersection candidates.
77  * The candidates -- neighbouring component elements and bulk elements -- are pushed into separate queues.
78  * The bulk elements queue is emptied at first, then the component elements queue is popped.
79  *
80  * The recuring prolongation algorithm is as follows:
81  * Function @p prolongation_decide fills the queues.
82  * A candidate pair of elements is popped out of a queue.
83  * Function @p prolongate computes intersection for a candidate pair and calls @p prolongation_decide again.
84  * This is done in an infinite cycle, until both queues are empty.
85  *
86  * Three algorithms are implemented:
87  *
88  * - BIH only: creates BIH, uses BIH to search through all elements to find candidates
89  * - BIH search: creates BIH, uses BIH to find only first candidates of components; then uses prolongation
90  * - BB search: does not create BIH, uses bounding boxes to search through all elements to find candidates
91  *
92  * Due to optimal tracing algorithm for 2d-3d, we consider tetrahedron only with positive Jacobian.
93  * This is checked in assert.
94  *
95  * TODO: check unit test prolongation 13d, because it has different results for BIH only and BB search
96  */
97 template<unsigned int dim>
99 {
100 public:
103 
104  ///@name Algorithms
105  /// Runs the core algorithm for computing dimD-3D intersection.
106  //@{
107  /// Uses BIHtree to find the initial candidate of a component and then prolongates the component intersetion.
108  void compute_intersections(const BIHTree& bih);
109  /// Uses only BIHtree to find intersection candidates. (No prolongation).
110  void compute_intersections_BIHtree(const BIHTree& bih);
111  /// Tests bounding boxes intersectioss to find the initial candidate of a component
112  /// and then prolongates the component intersetion. (No BIHtree).
114  //@}
115 
116 private:
119 // using IntersectionAlgorithmBase<dim,3>::simplexA;
120 // using IntersectionAlgorithmBase<dim,3>::simplexB;
121 
122  /** @brief Auxiliary structure for prolongation process.
123  *
124  * Contains index of component element, index of bulk element
125  * and its index in vector of bulk elements intersecting with the component element.
126  */
127  struct Prolongation{
128  unsigned int component_elm_idx;
129  unsigned int elm_3D_idx;
130  unsigned int dictionary_idx;
131  };
132 
133  /// Counter for intersection among elements.
134  unsigned int n_intersections_;
135 
136  /// Prolongation queue in the component mesh.
137  std::queue<Prolongation> component_queue_;
138  /// Prolongation queue in the bulk mesh.
139  std::queue<Prolongation> bulk_queue_;
140 
141  // Array of flags, which elements are computed
144 
145  /// Elements bounding boxes.
147  /// Bounding box of all 3D elements.
149 
150  /// Resulting vector of intersections.
152 
153  /// Initialization.
154  /// Sets vector sizes and computes bulk bounding box.
155  void init();
156 
157  /// Computes bounding boxes of all elements. Fills @p elements_bb and @p mesh_3D_bb.
158  void compute_bounding_boxes();
159 
160  void assert_same_intersection(unsigned int comp_ele_idx, unsigned int bulk_ele_idx);
161 
162  /// A hard way to find whether the intersection of two elements has already been computed, or not.
163  bool intersection_exists(unsigned int component_ele_idx, unsigned int bulk_ele_idx);
164 
165  /// Computes the first intersection, from which we then prolongate.
166  bool compute_initial_CI(const ElementAccessor<3> &comp_ele, const ElementAccessor<3> &bulk_ele);
167 
168  /// Finds neighbouring elements that are new candidates for intersection and pushes
169  /// them into component queue or bulk queue.
170  void prolongation_decide(const ElementAccessor<3> &comp_ele, const ElementAccessor<3> &bulk_ele,
172 
173  /// Computes the intersection for a candidate in a queue and calls @p prolongation_decide again.
174  void prolongate(const Prolongation &pr);
175 
176  template<unsigned int ele_dim>
178  unsigned int ip_dim,
179  unsigned int ip_obj_idx);
180 
181 // unsigned int create_prolongation_to_bulk(unsigned int bulk_ele_idx,
182 // unsigned int component_ele_idx);
183 
184  unsigned int create_prolongation(unsigned int bulk_ele_idx,
185  unsigned int component_ele_idx,
186  std::queue<Prolongation>& queue);
187 
189 };
190 
191 /** @brief Implements algorithm for finding 2D-2D intersections.
192  *
193  * It uses previously computed 2D-3D intersections and find candidates
194  * which have intersection in the same bulk (3D) element.
195  */
197 {
198 public:
199  InspectElementsAlgorithm22(Mesh *input_mesh);
200 
201  /// Runs the core algorithm for computing 2D-2D intersection in 3D.
202 // void compute_intersections(const std::vector<std::vector<ILpair>> &intersection_map_);
203 
204  void compute_intersections(std::vector<std::vector<ILpair>> &intersection_map,
206 
207 private:
208  unsigned int component_counter_;
209  const unsigned int unset_comp = (unsigned int)(-1);
210 
211  /// Stores temporarily 2D-2D intersections.
213 
214  // Auxiliary vector which keeps component indices for 2d elements.
216 
217  /// Computes fundamental intersection of two 2D elements.
220 
221  /// Creates numbering of the 2D components and fills component_idx_ vector.
223 
224  /// Auxiliary function for front-advancing alg. for component numbering.
225  //void prolongate22(const ElementAccessor<3>& ele, std::queue<unsigned int>& queue);
226 
228 };
229 
230 
231 /** @brief Implements algorithm for finding 1D-2D intersections.
232  *
233  * There are 3 possibilities of computation:
234  *
235  * 1) 2D problem with 1D fractures
236  * 2D mesh is a plane and 1D mesh is the same plane; then we can solve the intersection only in 2D,
237  * probably not using Plucker; we can apply some prolongation algorithm like in 1D-3D..
238  *
239  * 2) 1D-2D intersection in 3D space
240  * 1D and 2D meshes are arbitrarily placed in 3D space; then we need to compute intersections using Plucker
241  * coordinates and we cannot rely on prolongation algorithm (only if there are 2 IPs
242  * -> both lie in the same plane)
243  * - assuming that a 2D mesh component is mostly a plane in our applications (not an arbitrarily curved surface)
244  *
245  * 3) 1D-2D intersection inside 3D mesh
246  * 1D and 2D mesh is inside a bulk mesh (3D); if 2D-3D and 1D-3D has been computed,
247  * we can iterate over 3D intersection and get candidates if there is both 1D-3D and 2D-3D
248  * at the same time.
249  * We might need to deal with intersections outside 3D mesh, using partially algorithm (2)
250  */
252 {
253 public:
254  InspectElementsAlgorithm12(Mesh *input_mesh);
255 
256  /** @brief Runs the algorithm (3): compute 1D-2D intersection inside 3D mesh.
257  * It directly fills the intersection map and intersection storage.
258  * The intersection map is then also used to avoid duplicit intersections.
259  * @param intersection_map_ map of intersections where 1D-3D and 2D-3D must be already computed
260  * @param storage vector of intersection objects 1D-2D
261  */
264 
265  /** @brief Runs the algorithm (2): compute 1D-2D intersection in 3D ambient space
266  * BIH is used to find intersection candidates.
267  */
268  void compute_intersections_2(const BIHTree& bih);
269 
270  /** @brief Runs the algorithm (1): compute 1D-2D intersection in 2D plane.
271  * BIH is used to find intersection candidates.
272  */
273  void compute_intersections_1(const BIHTree& bih);
274 
275 private:
276  /// Stores temporarily 1D-2D intersections.
278 
279  /// Computes fundamental 1D-2D intersection of candidate pair.
280 // void compute_single_intersection(const ElementAccessor<3> &comp_ele, const ElementAccessor<3> &bulk_ele);
281 
283 };
284 
285 
286 #endif // INSPECT_ELEMENTS_ALGORITHM_H_
Class for O(log N) lookup for intersections with a set of bounding boxes.
Definition: bih_tree.hh:38
Bounding box in 3d ambient space.
Definition: bounding_box.hh:53
Implements algorithm for finding 1D-2D intersections.
void compute_intersections_3(std::vector< std::vector< ILpair >> &intersection_map, std::vector< IntersectionLocal< 1, 2 >> &storage)
Runs the algorithm (3): compute 1D-2D intersection inside 3D mesh. It directly fills the intersection...
void compute_intersections_1(const BIHTree &bih)
Runs the algorithm (1): compute 1D-2D intersection in 2D plane. BIH is used to find intersection cand...
std::vector< IntersectionAux< 1, 2 > > intersectionaux_storage12_
Stores temporarily 1D-2D intersections.
void compute_intersections_2(const BIHTree &bih)
Runs the algorithm (2): compute 1D-2D intersection in 3D ambient space BIH is used to find intersecti...
Implements algorithm for finding 2D-2D intersections.
std::vector< IntersectionAux< 2, 2 > > intersectionaux_storage22_
Stores temporarily 2D-2D intersections.
std::vector< unsigned int > component_idx_
void compute_single_intersection(const ElementAccessor< 3 > &eleA, const ElementAccessor< 3 > &eleB, std::vector< IntersectionLocal< 2, 2 >> &storage)
Computes fundamental intersection of two 2D elements.
void create_component_numbering()
Creates numbering of the 2D components and fills component_idx_ vector.
void compute_intersections(std::vector< std::vector< ILpair >> &intersection_map, std::vector< IntersectionLocal< 2, 2 >> &storage)
Runs the core algorithm for computing 2D-2D intersection in 3D.
Class implements algorithm for dim-dimensional intersections with 3D elements.
bool intersection_exists(unsigned int component_ele_idx, unsigned int bulk_ele_idx)
A hard way to find whether the intersection of two elements has already been computed,...
unsigned int create_prolongation(unsigned int bulk_ele_idx, unsigned int component_ele_idx, std::queue< Prolongation > &queue)
std::vector< BoundingBox > elements_bb
Elements bounding boxes.
std::queue< Prolongation > component_queue_
Prolongation queue in the component mesh.
void assert_same_intersection(unsigned int comp_ele_idx, unsigned int bulk_ele_idx)
void prolongate(const Prolongation &pr)
Computes the intersection for a candidate in a queue and calls prolongation_decide again.
std::vector< unsigned int > get_element_neighbors(const ElementAccessor< 3 > &ele, unsigned int ip_dim, unsigned int ip_obj_idx)
BoundingBox mesh_3D_bb
Bounding box of all 3D elements.
void compute_intersections(const BIHTree &bih)
Uses BIHtree to find the initial candidate of a component and then prolongates the component interset...
unsigned int n_intersections_
Counter for intersection among elements.
void prolongation_decide(const ElementAccessor< 3 > &comp_ele, const ElementAccessor< 3 > &bulk_ele, IntersectionAux< dim, 3 > is)
void compute_bounding_boxes()
Computes bounding boxes of all elements. Fills elements_bb and mesh_3D_bb.
bool compute_initial_CI(const ElementAccessor< 3 > &comp_ele, const ElementAccessor< 3 > &bulk_ele)
Computes the first intersection, from which we then prolongate.
std::vector< unsigned int > last_slave_for_3D_elements
std::vector< std::vector< IntersectionAux< dim, 3 > > > intersection_list_
Resulting vector of intersections.
std::queue< Prolongation > bulk_queue_
Prolongation queue in the bulk mesh.
void compute_intersections_BIHtree(const BIHTree &bih)
Uses only BIHtree to find intersection candidates. (No prolongation).
Mesh * mesh
Auxiliary function that translates ElementAccessor<3> to Simplex<simplex_dim>.
Internal auxiliary class representing intersection object of simplex<dimA> and simplex<dimB>.
Common base for intersection object.
Class represents intersection of two elements.
Internal auxiliary class represents an intersection point of simplex<N> and simplex<M>.
Definition: mesh.h:362
Main class for computation of intersection of meshes of combined dimensions.
std::pair< unsigned int, IntersectionLocalBase * > ILpair
First = element index, Second = pointer to intersection object.
Auxiliary structure for prolongation process.