Lethe Open-Source Library version 1.2.0
Developer Guide
Loading...
Searching...
No Matches
find_cell_neighbors.cc
Go to the documentation of this file.
1// SPDX-FileCopyrightText: Copyright (c) 2020-2026 The Lethe Authors
2// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception OR LGPL-2.1-or-later
3
5
6#include <deal.II/grid/cell_id.h>
7#include <deal.II/grid/grid_tools.h>
8
9using namespace DEM;
10
11template <int dim, bool reciprocal>
12void
14 const parallel::distributed::Triangulation<dim> &triangulation,
16 &cells_local_neighbor_list,
18 &cells_ghost_neighbor_list)
19{
20 // The output vectors of the function are cells_local_neighbor_list and
21 // cells_ghost_neighbor_list. The first contains all the local neighbors cells
22 // of all local cells; while the second contains all the ghost cells of all
23 // local cells. They are two vectors with size of the number of active cells.
24 // The first elements of all vectors are the main cells
25 typename dem_data_structures<dim>::cell_vector local_neighbor_vector;
26 typename dem_data_structures<dim>::cell_vector ghost_neighbor_vector;
27
28 // This vector is used to avoid repetition of adjacent cells. For instance if
29 // cell B is recognized as the neighbor of cell A, cell A will not be added to
30 // the neighbor list of cell B again. This is done using the total_cell_list
31 // vector
32 typename dem_data_structures<dim>::cell_set total_cell_list;
33
34 // For each cell, the cell vertices are found and used to find adjacent cells.
35 // The reason is to find the cells located on the corners of the main cell.
36 auto v_to_c = GridTools::vertex_to_cell_map(triangulation);
37
38 // Looping over cells
39 for (const auto &cell : triangulation.active_cell_iterators())
40 {
41 // If the cell is owned by the processor
42 if (cell->is_locally_owned())
43 {
44 // The first element of each vector is the cell itself.
45 local_neighbor_vector.push_back(cell);
46
47 if constexpr (!reciprocal)
48 total_cell_list.insert(cell);
49
50 for (unsigned int vertex = 0; vertex < cell->n_vertices(); ++vertex)
51 {
52 for (const auto &neighbor : v_to_c[cell->vertex_index(vertex)])
53 {
54 if (neighbor->is_locally_owned())
55 {
56 auto search_iterator = total_cell_list.find(neighbor);
57 auto local_search_iterator =
58 std::find(local_neighbor_vector.begin(),
59 local_neighbor_vector.end(),
60 neighbor);
61
62 // If the cell (neighbor) is a local cell and not present
63 // in the total_cell_list vector, it will be added as the
64 // neighbor of the main cell
65 // ("cell") and also to the total_cell_list to avoid
66 // repetition for next cells.
67 if (search_iterator == total_cell_list.end() &&
68 local_search_iterator == local_neighbor_vector.end())
69 {
70 local_neighbor_vector.push_back(neighbor);
71 }
72
73 // If the neighbor cell is a ghost, it should be added in
74 // the ghost_neighbor_vector container
75 }
76 else if (neighbor->is_ghost())
77 {
78 auto ghost_search_iterator =
79 std::find(ghost_neighbor_vector.begin(),
80 ghost_neighbor_vector.end(),
81 neighbor);
82 if (ghost_search_iterator == ghost_neighbor_vector.end())
83 {
84 if (ghost_neighbor_vector.empty())
85 {
86 ghost_neighbor_vector.push_back(cell);
87 }
88
89 ghost_neighbor_vector.push_back(neighbor);
90 }
91 }
92 }
93 }
94 }
95 if (!local_neighbor_vector.empty())
96 cells_local_neighbor_list.push_back(local_neighbor_vector);
97 if (!ghost_neighbor_vector.empty())
98 cells_ghost_neighbor_list.push_back(ghost_neighbor_vector);
99
100 local_neighbor_vector.clear();
101 ghost_neighbor_vector.clear();
102 }
103}
104
105template <int dim>
106void
108 const parallel::distributed::Triangulation<dim> &triangulation,
110 &periodic_boundaries_cells_information,
112 &cells_local_periodic_neighbor_list,
114 &cells_ghost_periodic_neighbor_list,
116 &cells_ghost_local_periodic_neighbor_list)
117{
118 typename dem_data_structures<dim>::cell_vector local_periodic_neighbor_vector;
119 typename dem_data_structures<dim>::cell_vector ghost_periodic_neighbor_vector;
121 ghost_local_periodic_neighbor_vector;
122
123 typename dem_data_structures<dim>::cell_set total_cell_list;
124
125 // Every distinct cell of periodic_boundaries_cells_information touches at
126 // least one principal periodic boundary and is therefore processed as a
127 // periodic main cell by the loop below. Since we support multiple PBC, it is
128 // possible that a main cell on the principal boundary of PBC 0 is also a
129 // periodic neighbor of another main cell relative to PBC 1. We need to store
130 // all the cells that were treated as "main" otherwise we are gonna have
131 // duplicated neighboring cell pairs. this cell_set stores the those cells.
132 typename dem_data_structures<dim>::cell_set all_main_cell_list;
133 for (const auto &pb_cell_struct : periodic_boundaries_cells_information)
134 all_main_cell_list.insert(pb_cell_struct.second.cell);
135
136 // For each cell, the cell vertices are found and used to find adjacent cells.
137 // The reason is to find the cells located on the corners of the main cell.
138 auto v_to_c = GridTools::vertex_to_cell_map(triangulation);
139
140 // A map of coinciding vertices labeled by an arbitrary element from them
141 std::map<unsigned int, std::vector<unsigned int>> coinciding_vertex_groups;
142
143 // Map of a vertex to the label of a group of coinciding vertices
144 std::map<unsigned int, unsigned int> vertex_to_coinciding_vertex_group;
145
146 // Collect for a given triangulation all locally relevant vertices that
147 // coincide due to periodicity.
148 GridTools::collect_coinciding_vertices(triangulation,
149 coinciding_vertex_groups,
150 vertex_to_coinciding_vertex_group);
151
152 // Keep track of cells already processed to avoid redundant corner handling,
153 // since periodic_boundaries_cells_information is an unordered_multimap
154 std::set<typename Triangulation<dim>::active_cell_iterator> processed_cells;
155
156 // Looping over cells struct at periodic boundaries 0
157 for (const auto &pb_cell_struct : periodic_boundaries_cells_information)
158 {
159 auto &cell = pb_cell_struct.second.cell;
160
161 // Skip if we already mapped this cell's periodic neighbors. This could
162 // happen if a cell is located at a corner formed by two primary PBC.
163 if (processed_cells.contains(cell))
164 continue;
165
166 // Since the cell is gonna be processed, we add it to the list.
167 processed_cells.insert(cell);
168
169 // If the cell is owned by the processor
170 if (cell->is_locally_owned())
171 {
172 // The first element of each vector is the cell itself.
173 local_periodic_neighbor_vector.push_back(cell);
174
175 // Store every main cell
176 total_cell_list.insert(cell);
177
178 // Empty list of periodic cell neighbor
179 typename dem_data_structures<dim>::cell_vector periodic_neighbor_list;
180
181 // Get the periodic neighbor of the cell
183 coinciding_vertex_groups,
184 vertex_to_coinciding_vertex_group,
185 v_to_c,
186 periodic_neighbor_list);
187
188 for (const auto &periodic_neighbor : periodic_neighbor_list)
189 {
190 if (periodic_neighbor->is_locally_owned())
191 {
192 // Check if the neighbor cell has been processed as a
193 // main cell
194 auto search_iterator =
195 total_cell_list.find(periodic_neighbor);
196
197 // Check if the neighbor cell is in already in the
198 // local_periodic_neighbor_vector
199 // Note from Gabo: I don't understand how this could happen
200 // since we are looping over cell on boundary 1.
201 // I think the only case would be if periodic_neighbor_list
202 // has duplicate cell. If this is the case, it is weird that
203 // get_periodic_neighbor_list returns a list with duplicates.
204 auto local_search_iterator =
205 std::find(local_periodic_neighbor_vector.begin(),
206 local_periodic_neighbor_vector.end(),
207 periodic_neighbor);
208
209 // If the cell neighbor is a local cell and not present
210 // in the total_cell_list vector, it will be added as the
211 // neighbor of the main cell.
212 if (search_iterator == total_cell_list.end() &&
213 local_search_iterator ==
214 local_periodic_neighbor_vector.end())
215 {
216 local_periodic_neighbor_vector.push_back(
217 periodic_neighbor);
218 }
219 }
220 else if (periodic_neighbor->is_ghost())
221 {
222 // If the periodic neighbor was also processed as a main
223 // cell, both cells discover this pair. Only the cell with
224 // the smallest CellId records it, otherwise the ghost
225 // branch below will records it a second time and the contact
226 // force will br applied twice to the same local particle. If
227 // the periodic neighbor is never treated as main cell, it
228 // never discovers this pair and the current cell must record
229 // it. CellId is used since it identifies a cell identically
230 // on every process, ghost cells included.
231 if (all_main_cell_list.contains(periodic_neighbor) &&
232 periodic_neighbor->id() < cell->id())
233 continue;
234
235 // If the cell neighbor is a ghost, it should be added in
236 // the ghost_periodic_neighbor_vector container
237 auto ghost_search_iterator =
238 std::find(ghost_periodic_neighbor_vector.begin(),
239 ghost_periodic_neighbor_vector.end(),
240 periodic_neighbor);
241 if (ghost_search_iterator ==
242 ghost_periodic_neighbor_vector.end())
243 {
244 if (ghost_periodic_neighbor_vector.empty())
245 {
246 ghost_periodic_neighbor_vector.push_back(cell);
247 }
248
249 ghost_periodic_neighbor_vector.push_back(
250 periodic_neighbor);
251 }
252 }
253 }
254 if (!local_periodic_neighbor_vector.empty())
255 cells_local_periodic_neighbor_list.push_back(
256 local_periodic_neighbor_vector);
257 if (!ghost_periodic_neighbor_vector.empty())
258 cells_ghost_periodic_neighbor_list.push_back(
259 ghost_periodic_neighbor_vector);
260 local_periodic_neighbor_vector.clear();
261 ghost_periodic_neighbor_vector.clear();
262 }
263 else if (cell->is_ghost())
264 {
265 // Since periodic cells are mapped on one side only (cells on pb 0
266 // with cells on pb 1), we need a 3rd container for ghost-local
267 // contacts for force calculation. Here we store local neighbors of
268 // ghost cells.
269
270 // The first element of each vector is the cell itself
271 ghost_local_periodic_neighbor_vector.push_back(cell);
272
273 // Empty list of periodic cell neighbor
274 typename dem_data_structures<dim>::cell_vector periodic_neighbor_list;
275
276 // Get the periodic neighbor of the cell
278 coinciding_vertex_groups,
279 vertex_to_coinciding_vertex_group,
280 v_to_c,
281 periodic_neighbor_list);
282
283 for (const auto &periodic_neighbor : periodic_neighbor_list)
284 {
285 if (periodic_neighbor->is_locally_owned())
286 {
287 // Same rule as in the local branch above: if the periodic
288 // neighbor is also a main cell, only the cell with the
289 // smallest CellId records the pair.
290 if (all_main_cell_list.contains(periodic_neighbor) &&
291 periodic_neighbor->id() < cell->id())
292 continue;
293
294 // Check if the neighbor cell is already in
295 // ghost_local_periodic_neighbor_vector. Duplicates are
296 // expected here: get_periodic_neighbor_list sweeps every
297 // one of this cell's periodic vertices independently, and
298 // a shared periodic face has multiple coinciding
299 // vertices, each contributing the same neighbor cell.
300 if (std::ranges::find(ghost_local_periodic_neighbor_vector,
301 periodic_neighbor) ==
302 ghost_local_periodic_neighbor_vector.end())
303 {
304 ghost_local_periodic_neighbor_vector.push_back(
305 periodic_neighbor);
306 }
307 }
308 }
309 if (!ghost_local_periodic_neighbor_vector.empty())
310 cells_ghost_local_periodic_neighbor_list.push_back(
311 ghost_local_periodic_neighbor_vector);
312 ghost_local_periodic_neighbor_vector.clear();
313 }
314 }
315}
316
317// This function finds the full neighbor list (with repetition) of all the
318// active cells in the triangulation. Because particle-floating mesh
319// contacts need all the particles located in ALL the neighbor cells of
320// the main cell to search for possible collisions with the floating mesh.
321template <int dim>
322void
324 const parallel::distributed::Triangulation<dim> &triangulation,
326 &cells_total_neighbor_list)
327{
328 auto v_to_c = GridTools::vertex_to_cell_map(triangulation);
329
330 // Looping over cells
331 for (const auto &cell : triangulation.active_cell_iterators())
332 {
333 // If the cell is owned by the processor
334 if (cell->is_locally_owned())
335 {
336 std::vector<typename Triangulation<dim>::active_cell_iterator>
337 full_neighbor_vector(0);
338
339 full_neighbor_vector.push_back(cell);
340
341 for (unsigned int vertex = 0; vertex < cell->n_vertices(); ++vertex)
342 {
343 for (const auto &neighbor : v_to_c[cell->vertex_index(vertex)])
344 {
345 if (neighbor->is_locally_owned())
346 {
347 auto search_iterator =
348 std::find(full_neighbor_vector.begin(),
349 full_neighbor_vector.end(),
350 neighbor);
351
352 if (search_iterator == full_neighbor_vector.end())
353 {
354 full_neighbor_vector.push_back(neighbor);
355 }
356 }
357 }
358 }
359
360 cells_total_neighbor_list.insert(
361 {cell->global_active_cell_index(), full_neighbor_vector});
362 }
363 }
364}
365
366template <int dim>
367void
369 const typename Triangulation<dim>::active_cell_iterator &cell,
370 const std::map<unsigned int, std::vector<unsigned int>>
371 &coinciding_vertex_groups,
372 const std::map<unsigned int, unsigned int> &vertex_to_coinciding_vertex_group,
373 const std::vector<std::set<typename Triangulation<dim>::active_cell_iterator>>
374 &v_to_c,
375 typename dem_data_structures<dim>::cell_vector &periodic_neighbor_list)
376{
377 // Loop over all vertices of the cell (periodic and non periodic)
378 for (unsigned int vertex = 0; vertex < cell->n_vertices(); ++vertex)
379 {
380 // Get global id of vertex
381 unsigned int vertex_id = cell->vertex_index(vertex);
382
383 // Check if vertex is at periodic boundary, there should be a key if so
384 if (vertex_to_coinciding_vertex_group.contains(vertex_id))
385 {
386 // Get the coinciding vertex key to the current vertex
387 unsigned int coinciding_vertex_key =
388 vertex_to_coinciding_vertex_group.at(vertex_id);
389
390 // Store the neighbor cells in list
391 for (auto coinciding_vertex :
392 coinciding_vertex_groups.at(coinciding_vertex_key))
393 {
394 // Skip the current vertex since we want only cells linked
395 // to the periodic vertices
396 if (coinciding_vertex != vertex_id)
397 {
398 // Loop over all periodic neighbor
399 for (const auto &neighbor_id : v_to_c[coinciding_vertex])
400 {
401 periodic_neighbor_list.push_back(neighbor_id);
402 }
403 }
404 }
405 }
406 }
407}
408
409template void
411 const parallel::distributed::Triangulation<2> &triangulation,
412 dem_data_structures<2>::cells_neighbor_list &cells_local_neighbor_list,
413 dem_data_structures<2>::cells_neighbor_list &cells_ghost_neighbor_list);
414
415template void
417 const parallel::distributed::Triangulation<3> &triangulation,
418 dem_data_structures<3>::cells_neighbor_list &cells_local_neighbor_list,
419 dem_data_structures<3>::cells_neighbor_list &cells_ghost_neighbor_list);
420
421template void
423 const parallel::distributed::Triangulation<2> &triangulation,
424 dem_data_structures<2>::cells_neighbor_list &cells_local_neighbor_list,
425 dem_data_structures<2>::cells_neighbor_list &cells_ghost_neighbor_list);
426
427template void
429 const parallel::distributed::Triangulation<3> &triangulation,
430 dem_data_structures<3>::cells_neighbor_list &cells_local_neighbor_list,
431 dem_data_structures<3>::cells_neighbor_list &cells_ghost_neighbor_list);
432
433template void
435 const parallel::distributed::Triangulation<2> &triangulation,
437 &periodic_boundaries_cells_information,
439 &cells_local_periodic_neighbor_list,
441 &cells_ghost_periodic_neighbor_list,
443 &cells_ghost_local_periodic_neighbor_list);
444
445template void
447 const parallel::distributed::Triangulation<3> &triangulation,
449 &periodic_boundaries_cells_information,
451 &cells_local_periodic_neighbor_list,
453 &cells_ghost_periodic_neighbor_list,
455 &cells_ghost_local_periodic_neighbor_list);
456
457template void
459 const parallel::distributed::Triangulation<2> &triangulation,
460 dem_data_structures<2>::cells_total_neighbor_list &cells_total_neighbor_list);
461
462template void
464 const parallel::distributed::Triangulation<3> &triangulation,
465 dem_data_structures<3>::cells_total_neighbor_list &cells_total_neighbor_list);
template void find_cell_neighbors< 2, true >(const parallel::distributed::Triangulation< 2 > &triangulation, dem_data_structures< 2 >::cells_neighbor_list &cells_local_neighbor_list, dem_data_structures< 2 >::cells_neighbor_list &cells_ghost_neighbor_list)
template void find_cell_neighbors< 2, false >(const parallel::distributed::Triangulation< 2 > &triangulation, dem_data_structures< 2 >::cells_neighbor_list &cells_local_neighbor_list, dem_data_structures< 2 >::cells_neighbor_list &cells_ghost_neighbor_list)
template void find_cell_periodic_neighbors< 3 >(const parallel::distributed::Triangulation< 3 > &triangulation, const dem_data_structures< 3 >::periodic_boundaries_cells_info &periodic_boundaries_cells_information, dem_data_structures< 3 >::cells_neighbor_list &cells_local_periodic_neighbor_list, dem_data_structures< 3 >::cells_neighbor_list &cells_ghost_periodic_neighbor_list, dem_data_structures< 3 >::cells_neighbor_list &cells_ghost_local_periodic_neighbor_list)
template void find_cell_neighbors< 3, true >(const parallel::distributed::Triangulation< 3 > &triangulation, dem_data_structures< 3 >::cells_neighbor_list &cells_local_neighbor_list, dem_data_structures< 3 >::cells_neighbor_list &cells_ghost_neighbor_list)
void find_cell_periodic_neighbors(const parallel::distributed::Triangulation< dim > &triangulation, const typename dem_data_structures< dim >::periodic_boundaries_cells_info &periodic_boundaries_cells_information, typename dem_data_structures< dim >::cells_neighbor_list &cells_local_periodic_neighbor_list, typename dem_data_structures< dim >::cells_neighbor_list &cells_ghost_periodic_neighbor_list, typename dem_data_structures< dim >::cells_neighbor_list &cells_ghost_local_periodic_neighbor_list)
Finds the periodic neighbor list (without repetition) of all the active cells in the triangulation....
void get_periodic_neighbor_list(const typename Triangulation< dim >::active_cell_iterator &cell, const std::map< unsigned int, std::vector< unsigned int > > &coinciding_vertex_groups, const std::map< unsigned int, unsigned int > &vertex_to_coinciding_vertex_group, const std::vector< std::set< typename Triangulation< dim >::active_cell_iterator > > &v_to_c, typename dem_data_structures< dim >::cell_vector &periodic_neighbor_list)
Generate a periodic neighbor cells list of the cell. With the coinciding_vertex_groups and the vertex...
template void find_cell_neighbors< 3, false >(const parallel::distributed::Triangulation< 3 > &triangulation, dem_data_structures< 3 >::cells_neighbor_list &cells_local_neighbor_list, dem_data_structures< 3 >::cells_neighbor_list &cells_ghost_neighbor_list)
template void find_full_cell_neighbors< 2 >(const parallel::distributed::Triangulation< 2 > &triangulation, dem_data_structures< 2 >::cells_total_neighbor_list &cells_total_neighbor_list)
void find_full_cell_neighbors(const parallel::distributed::Triangulation< dim > &triangulation, typename dem_data_structures< dim >::cells_total_neighbor_list &cells_total_neighbor_list)
Finds the full neighbor list (with repetition) of all the active cells in the triangulation....
template void find_full_cell_neighbors< 3 >(const parallel::distributed::Triangulation< 3 > &triangulation, dem_data_structures< 3 >::cells_total_neighbor_list &cells_total_neighbor_list)
template void find_cell_periodic_neighbors< 2 >(const parallel::distributed::Triangulation< 2 > &triangulation, const dem_data_structures< 2 >::periodic_boundaries_cells_info &periodic_boundaries_cells_information, dem_data_structures< 2 >::cells_neighbor_list &cells_local_periodic_neighbor_list, dem_data_structures< 2 >::cells_neighbor_list &cells_ghost_periodic_neighbor_list, dem_data_structures< 2 >::cells_neighbor_list &cells_ghost_local_periodic_neighbor_list)
void find_cell_neighbors(const parallel::distributed::Triangulation< dim > &triangulation, typename dem_data_structures< dim >::cells_neighbor_list &cells_local_neighbor_list, typename dem_data_structures< dim >::cells_neighbor_list &cells_ghost_neighbor_list)
Finds the neighbor list (without repetition) of all the active cells in the triangulation....
This namespace defines all the data containers and required operations on these containers for the DE...
std::vector< std::vector< typename Triangulation< dim >::active_cell_iterator > > cells_neighbor_list
std::unordered_multimap< types::global_cell_index, periodic_boundaries_cells_info_struct< dim > > periodic_boundaries_cells_info
ankerl::unordered_dense::map< types::global_cell_index, std::vector< typename Triangulation< dim >::active_cell_iterator > > cells_total_neighbor_list
std::set< typename Triangulation< dim >::active_cell_iterator > cell_set
std::vector< typename Triangulation< dim >::active_cell_iterator > cell_vector