Lethe Open-Source Library version 1.2.0
Developer Guide
Loading...
Searching...
No Matches
lethe_grid_tools.cc
Go to the documentation of this file.
1// SPDX-FileCopyrightText: Copyright (c) 2021-2026 The Lethe Authors
2// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception OR LGPL-2.1-or-later
3
5#include <core/serial_solid.h>
7
8#include <deal.II/fe/fe_q.h>
9#include <deal.II/fe/mapping_manifold.h>
10#include <deal.II/fe/mapping_q1.h>
11#include <deal.II/fe/mapping_q_cache.h>
12
13#include <deal.II/grid/grid_tools.h>
14
15#include <cmath>
16#include <tuple>
17#include <utility>
18#include <vector>
19
20template <int dim>
21void
23 const DoFHandler<dim> &dof_handler,
24 std::map<unsigned int,
25 std::set<typename DoFHandler<dim>::active_cell_iterator>>
26 &vertices_cell_map)
27{
28 vertices_cell_map.clear();
29 const auto &cell_iterator = dof_handler.active_cell_iterators();
30
31 // Loop on all the cells and find their vertices, and fill
32 // the map with sets of cells around each vertex
33 for (const auto &cell : cell_iterator)
34 {
35 if (cell->is_locally_owned() || cell->is_ghost())
36 {
37 const unsigned int vertices_per_cell =
38 GeometryInfo<dim>::vertices_per_cell;
39 for (unsigned int i = 0; i < vertices_per_cell; i++)
40 {
41 // First obtain vertex index
42 unsigned int v_index = cell->vertex_index(i);
43
44 // Insert the cell into the set of cell around that vertex.
45 vertices_cell_map[v_index].insert(cell);
46 }
47 }
48 }
49}
50
51template <int dim>
52void
54 const DoFHandler<dim> &dof_handler,
55 std::map<unsigned int,
56 std::set<typename DoFHandler<dim>::active_cell_iterator>>
57 &vertices_cell_map)
58{
59 vertices_cell_map.clear();
60 const auto &cell_iterator = dof_handler.active_cell_iterators();
61 const auto &triangulation = dof_handler.get_triangulation();
62
63 // A map of coinciding vertices labeled by an arbitrary element from them
64 // <label, [coinciding vertex indices]>
65 std::map<unsigned int, std::vector<unsigned int>> coinciding_vertex_groups;
66
67 // Map of a vertex to the label of a group of coinciding vertices
68 // <vertex index, label>
69 std::map<unsigned int, unsigned int> vertex_to_coinciding_vertex_group;
70
71 auto v_to_c = GridTools::vertex_to_cell_map(triangulation);
72 GridTools::collect_coinciding_vertices(triangulation,
73 coinciding_vertex_groups,
74 vertex_to_coinciding_vertex_group);
75
76 std::set<unsigned int> explored_vertices;
77 for (const auto &cell : cell_iterator)
78 {
79 if (cell->is_locally_owned() || cell->is_ghost())
80 {
81 const unsigned int vertices_per_cell =
82 GeometryInfo<dim>::vertices_per_cell;
83 for (unsigned int i = 0; i < vertices_per_cell; i++)
84 {
85 // Current vertex index
86 unsigned int v_index = cell->vertex_index(i);
87
88 // Try to insert the current vertex to the explored vertices list,
89 // if it was already explored, it returns a pair with false value,
90 // and we continue to the next vertex of the current cell, meaning
91 // the periodic neighbor cells has been already mapped with the
92 // vertex
93 if (!explored_vertices.insert(v_index).second)
94 continue;
95
96 // Set of neighbor cells at periodic vertex
97 std::set<typename DoFHandler<dim>::active_cell_iterator>
98 periodic_neighbor_cells;
99
100 // Get the iterator of the coinciding vertex key to the current
101 // vertex. If the iterator is the end of map, there's no vertex at
102 // periodic boundary.
103 auto coinciding_vertex_key_iterator =
104 vertex_to_coinciding_vertex_group.find(v_index);
105 if (coinciding_vertex_key_iterator !=
106 vertex_to_coinciding_vertex_group.end())
107 {
108 // Store the neighbor cells in list
109 for (auto coinciding_vertex : coinciding_vertex_groups.at(
110 coinciding_vertex_key_iterator->second))
111 {
112 // Skip the current vertex since we only want cells linked
113 // to the periodic vertices
114 if (coinciding_vertex != v_index)
115 {
116 // Loop over all periodic neighbor
117 for (const auto &neighbor_id :
118 v_to_c[coinciding_vertex])
119 {
120 // Get the neighbor cell iterator as DofHandler
121 // iterator since the map gives the triangulation
122 // iterator
123 typename DoFHandler<dim>::active_cell_iterator
124 neighbor_cell(&(triangulation),
125 neighbor_id->level(),
126 neighbor_id->index(),
127 &dof_handler);
128
129 // Insert the cell into the set for this vertex
130 periodic_neighbor_cells.insert(neighbor_cell);
131 }
132 }
133 }
134 }
135 // Insert the set of periodic neighbor cells into the map after
136 // search for this vertex is done. If the vertex is not at a
137 // periodic boundary, the set will be empty
138 vertices_cell_map.insert({v_index, periodic_neighbor_cells});
139 }
140 }
141 }
142}
143
144template <int dim>
145typename DoFHandler<dim>::active_cell_iterator
147 const DoFHandler<dim> &dof_handler,
148 const Point<dim> &point)
149{
150 // Define temporary variables to store search parameters and intermediate
151 // results
152 MappingQ1<dim> mapping;
153 typename DoFHandler<dim>::cell_iterator best_cell_iter;
154
155 bool cell_found_on_level_search = false;
156 unsigned int lvl = 0;
157 unsigned int max_lvl_search = dof_handler.get_triangulation().n_levels() - 2;
158
159 if (max_lvl_search < 4)
160 max_lvl_search = dof_handler.get_triangulation().n_levels();
161
162 while (lvl < max_lvl_search)
163 {
164 const auto &cell_iterator = dof_handler.cell_iterators_on_level(lvl);
165
166 // Loop on the cells on current level of the mesh
167 for (const auto &cell : cell_iterator)
168 {
169 try
170 {
171 const Point<dim, double> p_cell =
172 mapping.transform_real_to_unit_cell(cell, point);
173
174 const double dist =
175 GeometryInfo<dim>::distance_to_unit_cell(p_cell);
176
177 if (dist < 1e-12)
178 {
179 // cell found
180 cell_found_on_level_search = true;
181 best_cell_iter = cell;
182 break;
183 }
184 }
185 catch (const typename MappingQGeneric<dim>::ExcTransformationFailed &)
186 {}
187 }
188 lvl += 1;
189 }
190
191 double best_dist_last = DBL_MAX;
192 if (cell_found_on_level_search)
193 {
194 // A cell found on level search contains the point, so we loop on the
195 // children of this cell. When we found the child of the cell that
196 // contains the point, we check if the cell is active and stop if it is.
197 // Otherwise, we repeat this process until we find the active cell that
198 // contains the point.
199
200 unsigned int max_childs = GeometryInfo<dim>::max_children_per_cell;
201 while (best_cell_iter->is_active() == false)
202 {
203 bool cell_found = false;
204 double best_dist = DBL_MAX;
205 unsigned int best_index = 0;
206 for (unsigned int i = 0; i < max_childs; ++i)
207 {
208 try
209 {
210 const Point<dim, double> p_cell =
211 mapping.transform_real_to_unit_cell(
212 best_cell_iter->child(i), point);
213 const double dist =
214 GeometryInfo<dim>::distance_to_unit_cell(p_cell);
215 bool inside = true;
216
217
218 if (dist <= best_dist and inside)
219 {
220 best_dist = dist;
221 best_index = i;
222 cell_found = true;
223 if (dist == 0)
224 break;
225 }
226 }
227 catch (
228 const typename MappingQGeneric<dim>::ExcTransformationFailed &)
229 {}
230 }
231
232 best_cell_iter = best_cell_iter->child(best_index);
233 if (!cell_found)
234 {
235 break;
236 }
237
238 lvl += 1;
239 best_dist_last = best_dist;
240 }
241 }
242
243 if (best_dist_last >= 1e-9 && !cell_found_on_level_search)
244 {
245 throw std::runtime_error("The point is not inside the mesh");
246 }
247 return best_cell_iter;
248}
249
250
251template <int dim>
252std::vector<typename DoFHandler<dim>::active_cell_iterator>
254 const DoFHandler<dim> &dof_handler,
255 const Point<dim> &center,
256 const double radius)
257{
258 MappingQ1<dim> mapping;
259 const auto &cell_iterator = dof_handler.cell_iterators_on_level(0);
260 unsigned int max_childs = GeometryInfo<dim>::max_children_per_cell;
261
262 std::set<typename DoFHandler<dim>::cell_iterator> boundary_cells_candidates;
263 std::set<typename DoFHandler<dim>::cell_iterator>
264 last_boundary_cells_candidates;
265 std::set<typename DoFHandler<dim>::cell_iterator> cells_at_boundary;
266 // Loop over the cells on level 0 of the mesh
267 for (const auto &cell : cell_iterator)
268 {
269 if (cell->at_boundary())
270 {
271 for (unsigned int i = 0; i < GeometryInfo<dim>::vertices_per_cell;
272 ++i)
273 {
274 if ((cell->vertex(i) - center).norm() <= radius ||
275 cell->point_inside(center))
276 {
277 boundary_cells_candidates.insert(cell);
278 break;
279 }
280 }
281 }
282 }
283 // Loop over the boundary cells on level 0 to check their children.
284 last_boundary_cells_candidates = boundary_cells_candidates;
285 if (boundary_cells_candidates.size() != 0)
286 {
287 bool all_cell_are_active = false;
288 while (!all_cell_are_active)
289 {
290 // Only stop when all the candidate cell are active
291 all_cell_are_active = true;
292 boundary_cells_candidates.clear();
293 // loop over the last set of candidates.
294 for (auto cell : last_boundary_cells_candidates)
295 {
296 if (cell->at_boundary())
297 {
298 for (unsigned int i = 0;
299 i < GeometryInfo<dim>::vertices_per_cell;
300 ++i)
301 {
302 // Check if the cell is in the sphere.
303 if ((cell->vertex(i) - center).norm() <= radius ||
304 cell->point_inside(center))
305 {
306 if (cell->is_active())
307 {
308 cells_at_boundary.insert(cell);
309 }
310 else
311 {
312 // If we are here, the cell has children.
313 all_cell_are_active = false;
314 for (unsigned int j = 0; j < max_childs; ++j)
315 {
316 // Store the children of the cell for further
317 // checks.
318 boundary_cells_candidates.insert(
319 cell->child(j));
320 }
321 }
322 break;
323 }
324 }
325 }
326 }
327 last_boundary_cells_candidates.clear();
328 last_boundary_cells_candidates = boundary_cells_candidates;
329 }
330 }
331 std::vector<typename DoFHandler<dim>::active_cell_iterator>
332 cells_at_boundary_v(cells_at_boundary.begin(), cells_at_boundary.end());
333 // Output all the active cells in the sphere radius that are at a boundary.
334 return cells_at_boundary_v;
335}
336
337
338template <int dim>
339typename DoFHandler<dim>::active_cell_iterator
341 const DoFHandler<dim> &dof_handler,
342 std::map<unsigned int,
343 std::set<typename DoFHandler<dim>::active_cell_iterator>>
344 &vertices_cell_map,
345 const typename DoFHandler<dim>::active_cell_iterator &cell,
346 const Point<dim> &point)
347{
348 // Find the cells that share a vertex with the original cell.
349 std::vector<typename DoFHandler<dim>::active_cell_iterator>
350 active_neighbors_set =
351 LetheGridTools::find_cells_around_cell<dim>(vertices_cell_map, cell);
352 // Loop over that group of cells
353 for (unsigned int i = 0; i < active_neighbors_set.size(); ++i)
354 {
355 if (active_neighbors_set[i]->point_inside(point))
356 {
357 return active_neighbors_set[i];
358 }
359 }
360 // The cell is not found near the initial cell, so we use the cell tree
361 // algorithm instead (much slower).
362 return LetheGridTools::find_cell_around_point_with_tree(dof_handler, point);
363}
364
365template <int dim>
366std::vector<typename DoFHandler<dim>::active_cell_iterator>
368 std::map<unsigned int,
369 std::set<typename DoFHandler<dim>::active_cell_iterator>>
370 &vertices_cell_map,
371 const typename DoFHandler<dim>::active_cell_iterator &cell)
372{
373 // Find all the cells that share a vertex with a reference cell, including the
374 // initial cell.
375 std::set<typename DoFHandler<dim>::active_cell_iterator> neighbors_cells;
376
377 // Loop over the vertices of the initial cell, find all the cells around
378 // each vertex and add them to the set of cells around the reference cell.
379 for (unsigned int i = 0; i < GeometryInfo<dim>::vertices_per_cell; i++)
380 {
381 unsigned int v_index = cell->vertex_index(i);
382 neighbors_cells.insert(vertices_cell_map[v_index].begin(),
383 vertices_cell_map[v_index].end());
384 }
385
386 // Transform the set into a vector.
387 std::vector<typename DoFHandler<dim>::active_cell_iterator>
388 cells_sharing_vertices(neighbors_cells.begin(), neighbors_cells.end());
389 return cells_sharing_vertices;
390}
391
392template <int dim>
393std::vector<typename DoFHandler<dim>::active_cell_iterator>
395 const DoFHandler<dim> &dof_handler,
396 const typename DoFHandler<dim>::active_cell_iterator &cell)
397{
398 std::vector<typename DoFHandler<dim>::active_cell_iterator> cells_inside;
399 // Loop over all the cells of the dof handler and check one of the vertices
400 // of each cell is contained in the external cell, or vice versa. If either
401 // of those are true, the cell_iter is added to the set of cells contained by
402 // the external cell.
403
404 for (const auto &cell_iter : dof_handler.active_cell_iterators())
405 {
406 for (unsigned int i = 0; i < GeometryInfo<dim>::vertices_per_cell; ++i)
407 {
408 if (cell->point_inside(cell_iter->vertex(i)))
409 {
410 cells_inside.push_back(cell_iter);
411 break;
412 }
413 }
414 for (unsigned int i = 0; i < GeometryInfo<dim>::vertices_per_cell; ++i)
415 {
416 if (cell_iter->point_inside(cell->vertex(i)))
417 {
418 cells_inside.push_back(cell_iter);
419 break;
420 }
421 }
422 }
423
424 return cells_inside;
425}
426
427
428template <int dim>
429bool
431 const typename DoFHandler<dim>::active_cell_iterator &cell,
432 const TriaIterator<CellAccessor<1, dim>> &cell_edge)
433{
434 std::vector<Point<dim>> manifold_points(GeometryInfo<1>::vertices_per_cell);
435
436 for (unsigned int i = 0; i < GeometryInfo<1>::vertices_per_cell; ++i)
437 {
438 manifold_points[i] = cell_edge->vertex(i);
439 }
440
441 using numbers::PI;
442
443 // A cell that is pierced either has to fill these two conditions:
444 // A1) The projection of one of the cell's
445 // vertices must fall on the edge
446 // A2) At least one of the scalar product of the normal as to be negative
447
448 for (const auto face : cell->face_indices())
449 {
450 bool condition_a1 = false;
451 bool condition_a2 = true;
452 auto local_face = cell->face(face);
453 std::vector<Tensor<1, dim>> normals_of_face_vertex(
454 GeometryInfo<dim>::vertices_per_face);
455 for (unsigned int i = 0; i < GeometryInfo<dim>::vertices_per_face; ++i)
456 {
457 Point<dim> projected_point =
458 GridTools::project_to_object(cell_edge, local_face->vertex(i));
459
460 if (cell_edge->point_inside(projected_point) &&
461 cell->point_inside(projected_point))
462 {
463 condition_a1 = true;
464 }
465 if ((local_face->vertex(i) - projected_point).norm() != 0)
466 normals_of_face_vertex[i] =
467 (local_face->vertex(i) - projected_point) /
468 (local_face->vertex(i) - projected_point).norm();
469 else
470 return true;
471 }
472
473 for (unsigned int i = 0; i < 3; ++i)
474 {
475 if (i == 2)
476 {
477 Tensor<1, dim> temp = normals_of_face_vertex[1];
478 normals_of_face_vertex[1] = normals_of_face_vertex[0];
479 normals_of_face_vertex[0] = temp;
480 }
481 if (i == 3)
482 {
483 Tensor<1, dim> temp = normals_of_face_vertex[3];
484 normals_of_face_vertex[3] = normals_of_face_vertex[1];
485 normals_of_face_vertex[1] = temp;
486 }
487
488 for (unsigned int j = 0; j < GeometryInfo<dim>::vertices_per_face;
489 ++j)
490 {
491 double s = 0;
492 for (unsigned int k = 0; k < 3; ++k)
493 {
494 unsigned int index_1 = j + k;
495 unsigned int index_2 = j + k + 1;
496 if ((j + k) >= GeometryInfo<dim>::vertices_per_face)
497 {
498 index_1 = j + k - GeometryInfo<dim>::vertices_per_face;
499 }
500 if ((j + k + 1) >= GeometryInfo<dim>::vertices_per_face)
501 {
502 index_2 =
503 j + k + 1 - GeometryInfo<dim>::vertices_per_face;
504 }
505
506 double dot = scalar_product(normals_of_face_vertex[index_1],
507 normals_of_face_vertex[index_2]);
508 s += std::acos(std::clamp(dot, -1.0, 1.0));
509 }
510 if (s < PI)
511 {
512 condition_a2 = false;
513 break;
514 }
515 }
516 }
517 if (condition_a2)
518 if (condition_a1 && condition_a2)
519 {
520 return true;
521 }
522 }
523
524
525
526 return false;
527}
528
529template <int dim>
530bool
532 const typename DoFHandler<dim>::active_cell_iterator &cell,
533 Point<dim> point_1,
534 Point<dim> point_2)
535{
536 Triangulation<1, dim> local_edge_triangulation;
537 std::vector<Point<dim>> vertices_of_edge(2);
538 std::vector<CellData<1>> local_edge_cell_data(1);
539
540 vertices_of_edge[0] = point_1;
541 vertices_of_edge[1] = point_2;
542 local_edge_cell_data[0].vertices[0] = 0;
543 local_edge_cell_data[0].vertices[1] = 1;
544
545 local_edge_triangulation.create_triangulation(vertices_of_edge,
546 local_edge_cell_data,
547 SubCellData());
548
549 for (const auto &edge_cell : local_edge_triangulation.active_cell_iterators())
550 {
551 return LetheGridTools::cell_pierced_by_edge<dim>(cell, edge_cell);
552 }
553
554 // Default return statement in case loop is empty;
555 return false;
556}
557
558
559
560template <int spacedim, int structdim>
561std::pair<std::pair<Point<spacedim>, bool>, Tensor<1, spacedim>>
563 const typename DoFHandler<structdim, spacedim>::active_cell_iterator &object,
564 const Point<spacedim> &trial_point)
565{
566 // let's look at this for simplicity for a quad (structdim==2) in a
567 // space with spacedim>2 (notate trial_point by y): all points on the
568 // surface are given by
569 // x(\xi) = sum_i v_i phi_x(\xi)
570 // where v_i are the vertices of the quad, and \xi=(\xi_1,\xi_2) are the
571 // reference coordinates of the quad. so what we are trying to do is
572 // find a point x on the surface that is closest to the point y. there
573 // are different ways to solve this problem, but in the end it's a
574 // nonlinear problem, and we have to find reference coordinates \xi so
575 // that J(\xi) = 1/2 || x(\xi)-y ||^2 is minimal. x(\xi) is a function
576 // that is structdim-linear in \xi, so J(\xi) is a polynomial of degree
577 // 2*structdim that we'd like to minimize. unless structdim==1, we'll
578 // have to use a Newton method to find the answer. This leads to the
579 // following formulation of Newton steps:
580 //
581 // Given \xi_k, find \delta\xi_k so that
582 // H_k \delta\xi_k = - F_k
583 // where H_k is an approximation to the second derivatives of J at
584 // \xi_k, and F_k is the first derivative of J. We'll iterate this a
585 // number of times until the right hand side is small enough. As a
586 // stopping criterion, we terminate if ||\delta\xi||<eps.
587 //
588 // As for the Hessian, the best choice would be
589 // H_k = J''(\xi_k)
590 // but we'll opt for the simpler Gauss-Newton form
591 // H_k = A^T A
592 // i.e.
593 // (H_k)_{nm} = \sum_{i,j} v_i*v_j *
594 // \partial_n phi_i *
595 // \partial_m phi_j
596 // we start at xi=(0.5, 0.5).
597 Point<structdim> xi;
598 for (unsigned int d = 0; std::cmp_less(d, structdim); ++d)
599 xi[d] = 0.5;
600
601 Point<spacedim> x_k;
602 for (const unsigned int i : GeometryInfo<structdim>::vertex_indices())
603 x_k += object->vertex(i) *
604 GeometryInfo<structdim>::d_linear_shape_function(xi, i);
605
606 do
607 {
608 Tensor<1, structdim> F_k;
609 for (const unsigned int i : GeometryInfo<structdim>::vertex_indices())
610 F_k += (x_k - trial_point) * object->vertex(i) *
611 GeometryInfo<structdim>::d_linear_shape_function_gradient(xi, i);
612
613 Tensor<2, structdim> H_k;
614 for (const unsigned int i : GeometryInfo<structdim>::vertex_indices())
615 for (const unsigned int j : GeometryInfo<structdim>::vertex_indices())
616 {
617 Tensor<2, structdim> tmp = outer_product(
618 GeometryInfo<structdim>::d_linear_shape_function_gradient(xi, i),
619 GeometryInfo<structdim>::d_linear_shape_function_gradient(xi, j));
620 H_k += (object->vertex(i) * object->vertex(j)) * tmp;
621 }
622
623 const Tensor<1, structdim> delta_xi = -invert(H_k) * F_k;
624 xi += delta_xi;
625
626 x_k = Point<spacedim>();
627 for (const unsigned int i : GeometryInfo<structdim>::vertex_indices())
628 x_k += object->vertex(i) *
629 GeometryInfo<structdim>::d_linear_shape_function(xi, i);
630
631 if (delta_xi.norm() < 1e-7)
632 {
633 break;
634 }
635 }
636 while (true);
637 Tensor<1, spacedim> normal;
638 if (spacedim == 3)
639 {
640 double dx = 1e-4;
641 Point<structdim> xi_dx = xi;
642 Point<structdim> xi_dy = xi;
643 xi_dx[0] = xi[0] + dx;
644 xi_dy[1] = xi[1] - dx;
645 Point<spacedim> x_k_dx(0, 0, 0);
646 Point<spacedim> x_k_dy(0, 0, 0);
647 for (const unsigned int i : GeometryInfo<structdim>::vertex_indices())
648 {
649 x_k_dx += object->vertex(i) *
650 GeometryInfo<structdim>::d_linear_shape_function(xi_dx, i);
651 x_k_dy += object->vertex(i) *
652 GeometryInfo<structdim>::d_linear_shape_function(xi_dy, i);
653 }
654
655 normal = cross_product_3d((x_k_dx - x_k), (x_k_dy - x_k));
656 normal = normal / normal.norm();
657 }
658
659 if (spacedim == 2)
660 {
661 Tensor<1, spacedim> temp = object->vertex(1) - object->vertex(0);
662 normal[0] = -temp[1];
663 normal[1] = temp[0];
664 }
665 bool inside = true;
666 for (int i = 0; i < structdim; ++i)
667 {
668 if (xi[i] < 0 || xi[i] > 1)
669 inside = false;
670 }
671
672 std::pair<Point<spacedim>, bool> point = std::make_pair(x_k, inside);
673 std::pair<std::pair<Point<spacedim>, bool>, Tensor<1, spacedim>> output =
674 std::make_pair(point, normal);
675
676
677 return output;
678}
679
680
681template <int dim>
682std::vector<typename DoFHandler<dim>::active_cell_iterator>
684 const DoFHandler<dim> &dof_handler,
685 std::map<unsigned int,
686 std::set<typename DoFHandler<dim>::active_cell_iterator>>
687 &vertices_cell_map,
688 [[maybe_unused]] const typename DoFHandler<dim>::active_cell_iterator &cell,
689 Point<dim> &point_1,
690 Point<dim> &point_2)
691{
692 std::set<typename DoFHandler<dim>::active_cell_iterator> cells_pierced_set;
693 DoFHandler<1, dim> local_edge_dof_handler;
694 Triangulation<1, dim> local_edge_triangulation;
695 std::vector<Point<dim>> vertices_of_edge(2);
696 std::vector<CellData<1>> local_edge_cell_data(1);
697 FESystem<dim - 1, dim> local_face_fe(FE_Q<dim - 1, dim>(1));
698
699 vertices_of_edge[0] = point_1;
700 vertices_of_edge[1] = point_2;
701 local_edge_cell_data[0].vertices[0] = 0;
702 local_edge_cell_data[0].vertices[1] = 1;
703
704 local_edge_triangulation.create_triangulation(vertices_of_edge,
705 local_edge_cell_data,
706 SubCellData());
707 local_edge_dof_handler.reinit(local_edge_triangulation);
708 local_edge_dof_handler.distribute_dofs(local_face_fe);
709
710 const typename DoFHandler<1, dim>::active_cell_iterator edge_cell;
711 edge_cell = local_edge_dof_handler.active_cell_iterators().begin();
712 if (dim == 2)
713 {
714 cells_pierced_set =
715 find_cells_around_flat_cell(dof_handler, edge_cell, vertices_cell_map);
716 }
717 if (dim == 3)
718 {
719 auto &starting_cell =
720 find_cell_around_point_with_tree(dof_handler, point_1);
721 Tensor<1, dim> unit_direction =
722 (point_2 - point_1) / (point_2 - point_1).norm();
723
724 // Temporarily commented to clean warnings
725 // double total_dist = (point_2 - point_1).norm();
726
727 std::unordered_set<typename DoFHandler<dim>::active_cell_iterator,
730 previous_candidate_cells;
731
732 std::unordered_set<typename DoFHandler<dim>::active_cell_iterator,
735 current_candidate_cells;
736
737 std::unordered_set<typename DoFHandler<dim>::active_cell_iterator,
740 intersected_cells;
741
742 previous_candidate_cells.insert(starting_cell);
743 current_candidate_cells.insert(starting_cell);
744 intersected_cells.insert(starting_cell);
745
746 int n_previous_intersected = 0;
747
748 while (intersected_cells.size() > n_previous_intersected)
749 {
750 n_previous_intersected = intersected_cells.size();
751 // Find all cells around previous candidate cells
752 for (const typename DoFHandler<dim>::active_cell_iterator &cell_iter :
753 previous_candidate_cells)
754 {
755 current_candidate_cells.insert(
757 cell_iter));
758 }
759
760 // Reset the list of previous candidates
761 previous_candidate_cells.clear();
762
763 // Check if current candidate cells are intersected, and if they are,
764 // add them to the intersected cell set. If the added cell was not
765 // already present in the intersected cell set, add it to the previous
766 // candidate cells as well.
767 for (const typename DoFHandler<dim>::active_cell_iterator &cell_iter :
768 current_candidate_cells)
769 {
770 if (LetheGridTools::cell_pierced_by_edge(cell_iter, edge_cell))
771 {
772 // If the cell was not present in the intersected cells set
773 if (intersected_cells.insert(cell_iter).second)
774 {
775 previous_candidate_cells.insert(cell_iter);
776 }
777 }
778 }
779 current_candidate_cells.clear();
780 }
781 }
782
783
784 std::vector<typename DoFHandler<dim>::active_cell_iterator> cells_pierced(
785 cells_pierced_set.begin(), cells_pierced_set.end());
786
787 return cells_pierced;
788}
789
790template <int dim>
791bool
793 const typename DoFHandler<dim>::active_cell_iterator &cell,
794 const typename DoFHandler<dim - 1, dim>::active_cell_iterator &cell_flat)
795{
796 std::vector<Point<dim>> manifold_points(
797 GeometryInfo<dim - 1>::vertices_per_cell);
798 for (unsigned int i = 0; i < GeometryInfo<dim - 1>::vertices_per_cell; ++i)
799 {
800 manifold_points[i] = cell_flat->vertex(i);
801 }
802
803 // A cell that is cut either has to:
804 // A) Contain a vertex from the flat
805 // B) Fill these two conditions
806 // B1) The projection of one of the cell's
807 // vertices must fall on the flat
808 // B2) The cell must have vertices on each side of the flat
809 // C) Fill these conditions
810 // C1) One of the faces of the cell must have vertices of the flat cell on
811 // either side of it.
812 // C2) The cell must have vertices on each side of the
813 // flat (identical to B2)
814
815
816 // Check for condition A
817 for (unsigned int i = 0; i < GeometryInfo<dim - 1>::vertices_per_cell; ++i)
818 {
819 if (cell->point_inside(cell_flat->vertex(i)))
820 return true;
821 }
822
823 if constexpr (dim == 3)
824 {
825 // Check for condition A
826 for (const auto face : cell_flat->face_indices())
827 {
828 auto local_face = cell_flat->face(face);
830 local_face->vertex(0),
831 local_face->vertex(1)))
832 return true;
833 }
834 }
835
836 // Check for condition B
837 bool condition_B1 = false;
838 bool condition_B2 = false;
839 Tensor<1, dim> last_normal;
840 last_normal.clear();
841 double last_scalar_prod = 0;
842
843 for (unsigned int i = 0; i < GeometryInfo<dim>::vertices_per_cell; ++i)
844 {
845 auto projected_point =
847 cell_flat, cell->vertex(i));
848
849 Tensor<1, dim> normal = cell->vertex(i) - projected_point.first.first;
850
851 // Check if the projected vertex falls inside the flat
852
853 if (projected_point.first.second &&
854 cell->point_inside(projected_point.first.first))
855 {
856 condition_B1 = true;
857 }
858
859 // Check if we switched to the other side
860 // of the flat during this iteration
861 double scalar_prod = scalar_product(normal, projected_point.second);
862
863 if (scalar_prod * last_scalar_prod < 0)
864 {
865 condition_B2 = true;
866 }
867 last_scalar_prod = scalar_prod;
868 if (condition_B1 && condition_B2)
869 {
870 return true;
871 }
872 }
873
874
875 if (condition_B2)
876 {
877 bool condition_C2 = false;
878 for (const auto face : cell->face_indices())
879 {
880 auto face_iter = cell->face(face);
881 last_normal.clear();
882 auto &local_face_manifold = face_iter->get_manifold();
883
884 for (unsigned int i = 0; i < GeometryInfo<dim - 1>::vertices_per_cell;
885 ++i)
886 {
887 manifold_points[i] = face_iter->vertex(i);
888 }
889 auto surrounding_points_face =
890 make_array_view(manifold_points.begin(), manifold_points.end());
891
892 for (unsigned int i = 0; i < GeometryInfo<dim>::vertices_per_face;
893 ++i)
894 {
895 Point<dim> projected_point =
896 local_face_manifold.project_to_manifold(surrounding_points_face,
897 cell_flat->vertex(i));
898 Tensor<1, dim> normal = cell->vertex(i) - projected_point;
899 double scalar_prod = scalar_product(normal, last_normal);
900 last_normal = normal;
901 if (scalar_prod < 0)
902 condition_C2 = true;
903 }
904 if (condition_B1 && condition_C2)
905 return true;
906 }
907 }
908 return false;
909}
910
911
912template <int dim>
913std::vector<typename DoFHandler<dim>::active_cell_iterator>
915 const DoFHandler<dim> &dof_handler,
916 const typename DoFHandler<dim - 1, dim>::active_cell_iterator &cell,
917 std::map<unsigned int,
918 std::set<typename DoFHandler<dim>::active_cell_iterator>>
919 &vertices_cell_map)
920{
921 TriaActiveIterator<DoFCellAccessor<dim, dim, false>> starting_cell =
922 find_cell_around_point_with_tree(dof_handler, cell->vertex(0));
923
924 std::unordered_set<typename DoFHandler<dim>::active_cell_iterator,
927 previous_candidate_cells;
928
929 std::unordered_set<typename DoFHandler<dim>::active_cell_iterator,
932 current_candidate_cells;
933
934 std::unordered_set<typename DoFHandler<dim>::active_cell_iterator,
937 intersected_cells;
938
939 previous_candidate_cells.insert(starting_cell);
940 current_candidate_cells.insert(starting_cell);
941 intersected_cells.insert(starting_cell);
942
943 size_t n_previous_intersected = 0;
944
945 while (intersected_cells.size() > n_previous_intersected)
946 {
947 n_previous_intersected = intersected_cells.size();
948 // Find all cells around previous candidate cells
949 for (const typename DoFHandler<dim>::active_cell_iterator &cell_iter :
950 previous_candidate_cells)
951 {
952 auto new_cells =
954 cell_iter);
955 for (unsigned int i = 0; i < new_cells.size(); ++i)
956 {
957 current_candidate_cells.insert(new_cells[i]);
958 }
959 }
960
961 // Reset the list of previous candidates
962 previous_candidate_cells.clear();
963
964 // Check if current candidate cells are intersected, and if they are, add
965 // them to the set of intersected cells . If the added cells were not
966 // already present in the set of intersected cells, add them to the
967 // previous candidate cells as well.
968 for (const typename DoFHandler<dim>::active_cell_iterator &cell_iter :
969 current_candidate_cells)
970 {
971 if (LetheGridTools::cell_cut_by_flat<dim>(cell_iter, cell))
972 {
973 previous_candidate_cells.insert(cell_iter);
974 intersected_cells.insert(cell_iter);
975 // If the cell was not present in the intersected cells set
976 }
977 }
978 current_candidate_cells.clear();
979 }
980
981 std::vector<typename DoFHandler<dim>::active_cell_iterator> cells_cut(
982 intersected_cells.begin(), intersected_cells.end());
983
984
985 return cells_cut;
986}
987
988template <int spacedim, int structdim>
989std::map<
990 typename DoFHandler<spacedim>::active_cell_iterator,
991 std::map<unsigned int,
992 typename DoFHandler<structdim, spacedim>::active_cell_iterator>>
994 const DoFHandler<spacedim> &dof_handler,
995 std::map<unsigned int,
996 std::set<typename DoFHandler<spacedim>::active_cell_iterator>>
997 &vertices_cell_map,
998 std::vector<SerialSolid<structdim, spacedim>> &list_of_objects)
999{
1000 std::map<
1001 typename DoFHandler<spacedim>::active_cell_iterator,
1002 std::map<unsigned int,
1003 typename DoFHandler<structdim, spacedim>::active_cell_iterator>>
1004 cells_cut_by_object;
1005 if constexpr (structdim == spacedim - 1)
1006 {
1007 for (unsigned int i = 0; i < list_of_objects.size(); ++i)
1008 {
1009 const auto &object = list_of_objects[i].get_dof_handler();
1010
1011 const auto &object_cell_iterator = object.active_cell_iterators();
1012 // Loop on all the cells and find their vertices, and use them to fill
1013 // the map with sets of cells around each vertex
1014 for (const auto &cell : object_cell_iterator)
1015 {
1016 std::vector<typename DoFHandler<spacedim>::active_cell_iterator>
1018 dof_handler, cell, vertices_cell_map);
1019 for (unsigned int j = 0; j < cells_cut.size(); ++j)
1020 {
1021 cells_cut_by_object[cells_cut[j]]
1022 [list_of_objects[i].get_solid_id()] = cell;
1023 }
1024 }
1025 }
1026 return cells_cut_by_object;
1027 }
1028 else
1029 {
1030 for (unsigned int i = 0; i < list_of_objects.size(); ++i)
1031 {
1032 auto &object = list_of_objects[i].get_dof_handler();
1033
1034 const auto &object_cell_iterator = object.active_cell_iterators();
1035 // Loop on all the cells and find their vertices, and use them to fill
1036 // the map with sets of cells around each vertex
1037 for (const auto &cell : object_cell_iterator)
1038 {
1039 if (cell->at_boundary())
1040 {
1041 std::vector<
1042 typename DoFHandler<spacedim>::active_cell_iterator>
1044 dof_handler, cell, vertices_cell_map);
1045 for (unsigned int j = 0; j < cells_cut.size(); ++j)
1046 {
1047 cells_cut_by_object[cells_cut[j]]
1048 [list_of_objects[i].get_solid_id()] =
1049 cell;
1050 }
1051 }
1052 }
1053 }
1054 return cells_cut_by_object;
1055 }
1056}
1057
1058
1059template DoFHandler<3>::active_cell_iterator
1061 const DoFHandler<3> &dof_handler,
1062 const Point<3> &point);
1063template DoFHandler<2>::active_cell_iterator
1065 const DoFHandler<2> &dof_handler,
1066 const Point<2> &point);
1067
1068template void
1070 const DoFHandler<2> &dof_handler,
1071 std::map<unsigned int, std::set<DoFHandler<2>::active_cell_iterator>>
1072 &vertices_cell_map);
1073template void
1075 const DoFHandler<3> &dof_handler,
1076 std::map<unsigned int, std::set<DoFHandler<3>::active_cell_iterator>>
1077 &vertices_cell_map);
1078
1079template void
1081 const DoFHandler<2> &dof_handler,
1082 std::map<unsigned int, std::set<DoFHandler<2>::active_cell_iterator>>
1083 &vertices_cell_map);
1084template void
1086 const DoFHandler<3> &dof_handler,
1087 std::map<unsigned int, std::set<DoFHandler<3>::active_cell_iterator>>
1088 &vertices_cell_map);
1089
1090template typename DoFHandler<2>::active_cell_iterator
1092 const DoFHandler<2> &dof_handler,
1093 std::map<unsigned int, std::set<DoFHandler<2>::active_cell_iterator>>
1094 &vertices_cell_map,
1095 const DoFHandler<2>::active_cell_iterator &cell,
1096 const Point<2> &point);
1097
1098template typename DoFHandler<3>::active_cell_iterator
1100 const DoFHandler<3> &dof_handler,
1101 std::map<unsigned int, std::set<DoFHandler<3>::active_cell_iterator>>
1102 &vertices_cell_map,
1103 const DoFHandler<3>::active_cell_iterator &cell,
1104 const Point<3> &point);
1105
1106template std::vector<DoFHandler<2>::active_cell_iterator>
1108 std::map<unsigned int, std::set<DoFHandler<2>::active_cell_iterator>>
1109 &vertices_cell_map,
1110 const DoFHandler<2>::active_cell_iterator &cell);
1111
1112template std::vector<DoFHandler<3>::active_cell_iterator>
1114 std::map<unsigned int, std::set<DoFHandler<3>::active_cell_iterator>>
1115 &vertices_cell_map,
1116 const DoFHandler<3>::active_cell_iterator &cell);
1117
1118template std::vector<DoFHandler<2>::active_cell_iterator>
1120 const DoFHandler<2> &dof_handler,
1121 const DoFHandler<2>::active_cell_iterator &cell);
1122
1123template std::vector<DoFHandler<3>::active_cell_iterator>
1125 const DoFHandler<3> &dof_handler,
1126 const DoFHandler<3>::active_cell_iterator &cell);
1127
1128template bool
1130 const DoFHandler<2>::active_cell_iterator &cell,
1131 const DoFHandler<2 - 1, 2>::active_cell_iterator &cell_flat);
1132
1133template bool
1135 const DoFHandler<3>::active_cell_iterator &cell,
1136 const DoFHandler<3 - 1, 3>::active_cell_iterator &cell_flat);
1137
1138
1139template std::vector<DoFHandler<2>::active_cell_iterator>
1141 const DoFHandler<2> &dof_handler,
1142 const DoFHandler<2 - 1, 2>::active_cell_iterator &cell,
1143 std::map<unsigned int, std::set<DoFHandler<2>::active_cell_iterator>>
1144 &vertices_cell_map);
1145
1146template std::vector<DoFHandler<3>::active_cell_iterator>
1148 const DoFHandler<3> &dof_handler,
1149 const DoFHandler<3 - 1, 3>::active_cell_iterator &cell,
1150 std::map<unsigned int, std::set<DoFHandler<3>::active_cell_iterator>>
1151 &vertices_cell_map);
1152
1153template std::pair<std::pair<Point<2>, bool>, Tensor<1, 2>>
1155 const DoFHandler<1, 2>::active_cell_iterator &object,
1156 const Point<2> &trial_point);
1157
1158template std::pair<std::pair<Point<3>, bool>, Tensor<1, 3>>
1160 const DoFHandler<2, 3>::active_cell_iterator &object,
1161 const Point<3> &trial_point);
1162
1163
1164template bool
1166 const DoFHandler<3>::active_cell_iterator &cell,
1167 const TriaIterator<CellAccessor<1, 3>> &cell_edge);
1168
1169template bool
1171 const DoFHandler<3>::active_cell_iterator &cell,
1172 Point<3> point_1,
1173 Point<3> point_2);
1174
1175template std::vector<DoFHandler<2>::active_cell_iterator>
1176LetheGridTools::find_boundary_cells_in_sphere(const DoFHandler<2> &dof_handler,
1177 const Point<2> &center,
1178 const double radius);
1179template std::vector<DoFHandler<3>::active_cell_iterator>
1180LetheGridTools::find_boundary_cells_in_sphere(const DoFHandler<3> &dof_handler,
1181 const Point<3> &center,
1182 const double radius);
1183
1184
1185template std::map<
1186 DoFHandler<3>::active_cell_iterator,
1187 std::map<unsigned int, DoFHandler<3, 3>::active_cell_iterator>>
1189 const DoFHandler<3> &dof_handler,
1190 std::map<unsigned int, std::set<DoFHandler<3>::active_cell_iterator>>
1191 &vertices_cell_map,
1192 std::vector<SerialSolid<3, 3>> &list_of_objects);
1193
1194template std::map<
1195 DoFHandler<2>::active_cell_iterator,
1196 std::map<unsigned int, DoFHandler<2, 2>::active_cell_iterator>>
1198 const DoFHandler<2> &dof_handler,
1199 std::map<unsigned int, std::set<DoFHandler<2>::active_cell_iterator>>
1200 &vertices_cell_map,
1201 std::vector<SerialSolid<2, 2>> &list_of_objects);
1202
1203template std::map<
1204 DoFHandler<3>::active_cell_iterator,
1205 std::map<unsigned int, DoFHandler<2, 3>::active_cell_iterator>>
1207 const DoFHandler<3> &dof_handler,
1208 std::map<unsigned int, std::set<DoFHandler<3>::active_cell_iterator>>
1209 &vertices_cell_map,
1210 std::vector<SerialSolid<2, 3>> &list_of_objects);
1211
1212template std::map<
1213 DoFHandler<2>::active_cell_iterator,
1214 std::map<unsigned int, DoFHandler<1, 2>::active_cell_iterator>>
1216 const DoFHandler<2> &dof_handler,
1217 std::map<unsigned int, std::set<DoFHandler<2>::active_cell_iterator>>
1218 &vertices_cell_map,
1219 std::vector<SerialSolid<1, 2>> &list_of_objects);
1220
1221
1222template <int dim>
1225 const std::vector<Point<dim>> &triangle)
1226{
1227 const auto &p_0 = triangle[0];
1228 const auto &p_1 = triangle[1];
1229 const auto &p_2 = triangle[2];
1230
1231 TriangleProjectionData<dim> triangle_data;
1232 triangle_data.p_0 = p_0;
1233 triangle_data.e_0 = p_1 - p_0;
1234 triangle_data.e_1 = p_2 - p_0;
1235
1236 const Tensor<1, dim> normal =
1237 cross_product_3d(triangle_data.e_0, triangle_data.e_1);
1238 triangle_data.unit_normal = normal / normal.norm();
1239
1240 triangle_data.a = triangle_data.e_0.norm_square();
1241 triangle_data.b = scalar_product(triangle_data.e_0, triangle_data.e_1);
1242 triangle_data.c = triangle_data.e_1.norm_square();
1243 triangle_data.det =
1244 triangle_data.a * triangle_data.c - triangle_data.b * triangle_data.b;
1245
1246 return triangle_data;
1247}
1248
1249template <int dim>
1250std::tuple<bool,
1251 Point<3>,
1252 Tensor<1, 3>,
1255 const TriangleProjectionData<dim> &triangle_data,
1256 const Point<dim> &particle_position,
1257 const double cutoff_distance)
1258{
1259 // Variable declarations
1260 bool pass_distance_check;
1261
1262 const Point<dim> &p_0 = triangle_data.p_0;
1263 const Tensor<1, dim> &e_0 = triangle_data.e_0;
1264 const Tensor<1, dim> &e_1 = triangle_data.e_1;
1265
1266 Tensor<1, dim> unit_normal = triangle_data.unit_normal;
1267 Tensor<1, 3> unit_normal_3d;
1268
1269 const double a = triangle_data.a;
1270 const double b = triangle_data.b;
1271 const double c = triangle_data.c;
1272 const double det = triangle_data.det;
1273
1274 // Pre-allocation for speed
1275 const Tensor<1, dim> vector_to_plane = p_0 - particle_position;
1276
1277 ParticleTriangleContactIndicator contact_indicator;
1278 // A bool variable for region 0
1279 bool region_zero = false;
1280
1281 // Check to see if the particle is located on the correct side (with
1282 // respect to the normal vector) of the triangle
1283 if (vector_to_plane * unit_normal > 0)
1284 unit_normal *= -1.0;
1285
1286 // Distance between the particle center and the plane of the triangle. The
1287 // normal vector points toward the particle, so the scalar product is
1288 // negative or zero.
1289 const double distance_to_plane =
1290 -scalar_product(vector_to_plane, unit_normal);
1291
1292 // If the particle is too far from the plane, it is also too far from the
1293 // triangle
1294 if (distance_to_plane > cutoff_distance)
1295 {
1296 // We return right away since the particle is too far from the triangle
1297 // anyways.
1298 pass_distance_check = false;
1299 contact_indicator = ParticleTriangleContactIndicator::no_contact;
1300 return std::make_tuple(pass_distance_check,
1301 Point<3>(),
1302 Tensor<1, 3>(),
1303 contact_indicator);
1304 }
1305
1306 // Otherwise, do the full calculation taken from Eberly 2003
1307 const double d = scalar_product(e_0, vector_to_plane);
1308 const double e = scalar_product(e_1, vector_to_plane);
1309
1310 // Calculate necessary values;
1311 double s = b * e - c * d;
1312 double t = b * d - a * e;
1313
1314 if (s + t <= det)
1315 {
1316 if (s < 0)
1317 {
1318 if (t < 0)
1319 {
1320 // Region 4
1321 contact_indicator =
1322 ParticleTriangleContactIndicator::vertex_contact;
1323 if (d < 0)
1324 {
1325 t = 0;
1326 if (-d >= a)
1327 s = 1;
1328 else
1329 s = -d / a;
1330 }
1331 else
1332 {
1333 s = 0;
1334 if (e >= 0)
1335 t = 0;
1336 else if (-e >= c)
1337 t = 1;
1338 else
1339 t = e / c;
1340 }
1341 }
1342 else
1343 {
1344 // Region 3
1345 contact_indicator =
1346 ParticleTriangleContactIndicator::edge_contact;
1347
1348 s = 0;
1349 if (e >= 0)
1350 t = 0;
1351 else if (-e >= c)
1352 t = 1;
1353 else
1354 t = -e / c;
1355 }
1356 }
1357 else if (t < 0)
1358 {
1359 // Region 5
1360 contact_indicator = ParticleTriangleContactIndicator::edge_contact;
1361
1362 t = 0;
1363 if (d >= 0)
1364 s = 0;
1365 else if (-d >= a)
1366 s = 1;
1367 else
1368 s = -d / a;
1369 }
1370 else
1371 {
1372 // Region 0
1373 const double inv_det = 1. / det;
1374 s *= inv_det;
1375 t *= inv_det;
1376
1377 // In region 0, normal vector is the face normal vector
1378 // Cast unit_normal to a tensor<1, 3>
1379 unit_normal_3d = tensor_nd_to_3d(unit_normal);
1380
1381 region_zero = true;
1382 contact_indicator = ParticleTriangleContactIndicator::face_contact;
1383 }
1384 }
1385 else
1386 {
1387 if (s < 0)
1388 {
1389 // Region 2
1390 contact_indicator = ParticleTriangleContactIndicator::vertex_contact;
1391
1392 const double tmp0 = b + d;
1393 const double tmp1 = c + e;
1394 if (tmp1 > tmp0)
1395 {
1396 const double numer = tmp1 - tmp0;
1397 const double denom = a - 2 * b + c;
1398 if (numer >= denom)
1399 s = 1;
1400 else
1401 s = numer / denom;
1402
1403 t = 1 - s;
1404 }
1405 else
1406 {
1407 s = 0;
1408 if (tmp1 <= 0)
1409 t = 1;
1410 else if (e >= 0)
1411 t = 0;
1412 else
1413 t = -e / c;
1414 }
1415 }
1416 else if (t < 0)
1417 {
1418 // Region 6
1419 contact_indicator = ParticleTriangleContactIndicator::vertex_contact;
1420
1421 const double tmp0 = b + e;
1422 const double tmp1 = a + d;
1423 if (tmp1 > tmp0)
1424 {
1425 const double numer = tmp1 - tmp0;
1426 const double denom = a - 2 * b + c;
1427 if (numer >= denom)
1428 t = 1;
1429 else
1430 t = numer / denom;
1431 s = 1 - t;
1432 }
1433 else
1434 {
1435 t = 0;
1436 if (tmp1 <= 0)
1437 s = 1;
1438 else if (d >= 0)
1439 s = 0;
1440 else
1441 s = -d / a;
1442 }
1443 }
1444 else
1445 {
1446 // Region 1
1447 contact_indicator = ParticleTriangleContactIndicator::edge_contact;
1448
1449 const double numer = (c + e) - (b + d);
1450 if (numer <= 0)
1451 s = 0;
1452 else
1453 {
1454 const double denom = a - 2 * b + c;
1455 if (numer >= denom)
1456 s = 1;
1457 else
1458 s = numer / denom;
1459 }
1460 t = 1 - s;
1461 }
1462 }
1463
1464 const Point<dim> pt_in_triangle = p_0 + s * e_0 + t * e_1;
1465
1466 if (!region_zero)
1467 {
1468 // normal vector
1469 const Tensor<1, dim> point_to_particle_normal =
1470 particle_position - pt_in_triangle;
1471 unit_normal_3d = tensor_nd_to_3d(point_to_particle_normal /
1472 point_to_particle_normal.norm());
1473 }
1474
1475 // Cast pt_in_triangle on Point<3>
1476 Point<3> pt_in_triangle_3d = point_nd_to_3d(pt_in_triangle);
1477 pass_distance_check = true;
1478
1479 return std::make_tuple(pass_distance_check,
1480 pt_in_triangle_3d,
1481 unit_normal_3d,
1482 contact_indicator);
1483}
1484
1487 const std::vector<Point<2>> &triangle);
1488
1491 const std::vector<Point<3>> &triangle);
1492
1493template std::tuple<bool,
1494 Point<3>,
1495 Tensor<1, 3>,
1498 const LetheGridTools::TriangleProjectionData<2> &triangle_data,
1499 const Point<2> &particle_position,
1500 const double cutoff_distance);
1501
1502template std::tuple<bool,
1503 Point<3>,
1504 Tensor<1, 3>,
1507 const LetheGridTools::TriangleProjectionData<3> &triangle_data,
1508 const Point<3> &particle_position,
1509 const double cutoff_distance);
1510
1511
1512template <int dim>
1513double
1515 const std::vector<Point<dim>> &triangle,
1516 const Point<dim> &point)
1517{
1518 double distance = 0.0;
1519
1520 const Point<dim> &point_0 = triangle[0];
1521 const Point<dim> &point_1 = triangle[1];
1522
1523 if constexpr (dim == 3)
1524 {
1525 const Point<dim> &point_2 = triangle[2];
1526
1527 const Tensor<1, dim> e_0 = point_1 - point_0;
1528 const Tensor<1, dim> e_1 = point_2 - point_0;
1529
1530 const double a = e_0.norm_square();
1531 const double b = scalar_product(e_0, e_1);
1532 const double c = e_1.norm_square();
1533 const double det = a * c - b * b;
1534
1535
1536 Tensor<1, dim> vector_to_plane;
1537 Point<dim> pt_in_triangle;
1538
1539 vector_to_plane = point_0 - point;
1540
1541 // From this point onward, the variable name follow the notation of
1542 // Geometric Tools for Computer Graphics, Eberly 2003 Chapter 10.3.2 -
1543 // Point to triangle.
1544
1545 const double d = scalar_product(e_0, vector_to_plane);
1546 const double e = scalar_product(e_1, vector_to_plane);
1547
1548 // Calculate necessary values;
1549 double s = b * e - c * d;
1550 double t = b * d - a * e;
1551
1552 if (s + t <= det)
1553 {
1554 if (s < 0)
1555 {
1556 if (t < 0)
1557 {
1558 // Region 4
1559 if (d < 0)
1560 {
1561 t = 0;
1562 if (-d >= a)
1563 s = 1;
1564 else
1565 s = -d / a;
1566 }
1567 else
1568 {
1569 s = 0;
1570 if (e >= 0)
1571 t = 0;
1572 else if (-e >= c)
1573 t = 1;
1574 else
1575 t = e / c;
1576 }
1577 }
1578 else
1579 {
1580 // Region 3
1581 s = 0;
1582 if (e >= 0)
1583 t = 0;
1584 else if (-e >= c)
1585 t = 1;
1586 else
1587 t = -e / c;
1588 }
1589 }
1590 else if (t < 0)
1591 {
1592 // Region 5
1593 t = 0;
1594 if (d >= 0)
1595 s = 0;
1596 else if (-d >= a)
1597 s = 1;
1598 else
1599 s = -d / a;
1600 }
1601 else
1602 {
1603 // Region 0
1604 const double inv_det = 1. / det;
1605 s *= inv_det;
1606 t *= inv_det;
1607 }
1608 }
1609 else
1610 {
1611 if (s < 0)
1612 {
1613 // Region 2
1614 const double tmp0 = b + d;
1615 const double tmp1 = c + e;
1616 if (tmp1 > tmp0)
1617 {
1618 const double numer = tmp1 - tmp0;
1619 const double denom = a - 2 * b + c;
1620 if (numer >= denom)
1621 s = 1;
1622 else
1623 s = numer / denom;
1624
1625 t = 1 - s;
1626 }
1627 else
1628 {
1629 s = 0;
1630 if (tmp1 <= 0)
1631 t = 1;
1632 else if (e >= 0)
1633 t = 0;
1634 else
1635 t = -e / c;
1636 }
1637 }
1638 else if (t < 0)
1639 {
1640 // Region 6
1641 const double tmp0 = b + e;
1642 const double tmp1 = a + d;
1643 if (tmp1 > tmp0)
1644 {
1645 const double numer = tmp1 - tmp0;
1646 const double denom = a - 2 * b + c;
1647 if (numer >= denom)
1648 t = 1;
1649 else
1650 t = numer / denom;
1651 s = 1 - t;
1652 }
1653 else
1654 {
1655 t = 0;
1656 if (tmp1 <= 0)
1657 s = 1;
1658 else if (d >= 0)
1659 s = 0;
1660 else
1661 s = -d / a;
1662 }
1663 }
1664 else
1665 {
1666 // Region 1
1667 const double numer = (c + e) - (b + d);
1668 if (numer <= 0)
1669 s = 0;
1670 else
1671 {
1672 const double denom = a - 2 * b + c;
1673 if (numer >= denom)
1674 s = 1;
1675 else
1676 s = numer / denom;
1677 }
1678 t = 1 - s;
1679 }
1680 }
1681
1682 pt_in_triangle = point_0 + s * e_0 + t * e_1;
1683
1684 distance = pt_in_triangle.distance(point);
1685 }
1686
1687 if constexpr (dim == 2)
1688 {
1689 const Tensor<1, dim> d = point_1 - point_0;
1690
1691 const double t_bar =
1692 d * (point - point_0) / (d.norm() * d.norm() + 1e-12);
1693
1694 if (t_bar <= 0.0)
1695 {
1696 const Tensor<1, dim> point_minus_p0 = point - point_0;
1697 distance = point_minus_p0.norm();
1698 }
1699 else if (t_bar >= 1.0)
1700 {
1701 const Tensor<1, dim> point_minus_p1 = point - point_1;
1702 distance = point_minus_p1.norm();
1703 }
1704 else
1705 {
1706 const Tensor<1, dim> projection = point - (point_0 + t_bar * d);
1707 distance = projection.norm();
1708 }
1709 }
1710
1711 return distance;
1712}
1713
1714template double
1716 const std::vector<Point<2>> &triangle,
1717 const Point<2> &point);
1718template double
1720 const std::vector<Point<3>> &triangle,
1721 const Point<3> &point);
1722
1723template <int dim>
1724std::vector<Point<dim>>
1726 const Point<dim> &line_start,
1727 const Tensor<1, dim> &line_direction,
1728 const Point<dim> &sphere_center,
1729 const double &sphere_diameter)
1730{
1731 // Calculate the coefficients of the quadratic equation
1732 const double sphere_radius = 0.5 * sphere_diameter;
1733
1734 const double a = line_direction.norm_square();
1735 const double b =
1736 2 * scalar_product(line_direction, line_start - sphere_center);
1737 const double c =
1738 (line_start - sphere_center).norm_square() - sphere_radius * sphere_radius;
1739
1740 // Initialize the vector to store intersection points
1741 // Note: This vector will be empty if there are no intersection points
1742 std::vector<Point<dim>> intersection_points;
1743
1744 // Calculate the discriminant
1745 const double discriminant = b * b - 4 * a * c;
1746 if (discriminant > 0.)
1747 {
1748 // Two intersection points
1749 const double sqrt_discriminant = std::sqrt(discriminant);
1750 const double t1 = (-b - sqrt_discriminant) / (2. * a);
1751 const double t2 = (-b + sqrt_discriminant) / (2. * a);
1752
1753 intersection_points.push_back(line_start + t1 * line_direction);
1754 intersection_points.push_back(line_start + t2 * line_direction);
1755
1756 return intersection_points;
1757 }
1758 if (discriminant == 0.)
1759 {
1760 // One intersection point
1761 const double t = -b / (2. * a);
1762 intersection_points.push_back(line_start + t * line_direction);
1763
1764 return intersection_points;
1765 }
1766 // If the discriminant is negative, there are no intersection points therefore
1767 // the vector remains empty
1768 return intersection_points;
1769}
1770
1771template std::vector<Point<2>>
1773 const Point<2> &line_start,
1774 const Tensor<1, 2> &line_direction,
1775 const Point<2> &sphere_center,
1776 const double &sphere_radius);
1777template std::vector<Point<3>>
1779 const Point<3> &line_start,
1780 const Tensor<1, 3> &line_direction,
1781 const Point<3> &sphere_center,
1782 const double &sphere_radius);
1783
1784
1785template <int dim>
1786void
1787LetheGridTools::rotate_mapping(const DoFHandler<dim> &dof_handler,
1788 MappingQCache<dim> &mapping_cache,
1789 const Mapping<dim> &mapping,
1790 const double rotation_angle,
1791 const Point<dim> &center_of_rotation,
1792 const unsigned int rotation_axis_direction)
1793{
1794 if constexpr (dim == 2)
1795 {
1796 mapping_cache.initialize(
1797 mapping,
1798 dof_handler.get_triangulation(),
1799 [&](const auto &cell, const auto &point) {
1800 // Do not rotate the point if current cell is part of the stator
1801 if (cell->material_id() == 0)
1802 return point;
1803
1804 // Shift point by the center of rotation
1805 const auto shift_point = point - center_of_rotation;
1806 // Rotate
1807 const auto rotate_point =
1808 Physics::Transformations::Rotations::rotation_matrix_2d(
1809 rotation_angle) *
1810 shift_point;
1811 // Return rotated point according to center of rotation
1812 return static_cast<Point<dim>>(rotate_point + center_of_rotation);
1813 },
1814 false);
1815 }
1816 else if constexpr (dim == 3)
1817 {
1818 mapping_cache.initialize(
1819 mapping,
1820 dof_handler.get_triangulation(),
1821 [&](const auto &cell, const auto &point) {
1822 // Do not rotate point if current cell is part of the stator
1823 if (cell->material_id() == 0)
1824 return point;
1825
1826 // Shift point by the center of rotation
1827 const auto shift_point = point - center_of_rotation;
1828 // Rotation axis tensor
1829 Tensor<1, 3> rotation_axis;
1830 rotation_axis[rotation_axis_direction] = 1.0;
1831 // Rotate
1832 const auto rotate_point =
1833 Physics::Transformations::Rotations::rotation_matrix_3d(
1834 rotation_axis, rotation_angle) *
1835 shift_point;
1836 // Return rotated point according to the center of rotation
1837 return static_cast<Point<dim>>(rotate_point + center_of_rotation);
1838 },
1839 false);
1840 }
1841}
1842
1843template void
1844LetheGridTools::rotate_mapping(const DoFHandler<2> &dof_handler,
1845 MappingQCache<2> &mapping_cache,
1846 const Mapping<2> &mapping,
1847 const double rotation_angle,
1848 const Point<2> &center_of_rotation,
1849 const unsigned int rotation_axis_direction);
1850
1851template void
1852LetheGridTools::rotate_mapping(const DoFHandler<3> &dof_handler,
1853 MappingQCache<3> &mapping_cache,
1854 const Mapping<3> &mapping,
1855 const double rotation_angle,
1856 const Point<3> &center_of_rotation,
1857 const unsigned int rotation_axis_direction);
1858
1859template <int dim, int spacedim>
1860void
1862 const Triangulation<dim, spacedim> &tria,
1863 std::map<
1864 unsigned int,
1865 std::set<typename Triangulation<dim, spacedim>::active_cell_iterator>>
1866 &vertices_cell_map)
1867{
1868 vertices_cell_map.clear();
1869 const auto &cell_iterator = tria.active_cell_iterators();
1870
1871 // Loop on all the cells and find their vertices, and fill
1872 // the map with sets of cells around each vertex
1873 for (const auto &cell : cell_iterator)
1874 {
1875 // Since this is a serial triangulation, no need to check if the cells
1876 // are locally own.
1877 const unsigned int vertices_per_cell = cell->n_vertices();
1878 for (unsigned int i = 0; i < vertices_per_cell; i++)
1879 {
1880 // First obtain vertex index
1881 unsigned int v_index = cell->vertex_index(i);
1882
1883 // Insert the cell into the set of cell around that vertex.
1884 vertices_cell_map[v_index].insert(cell);
1885 }
1886 }
1887}
1888template void
1890 const Triangulation<1, 2> &tria,
1891 std::map<unsigned int,
1892 std::set<typename Triangulation<1, 2>::active_cell_iterator>>
1893 &vertices_cell_map);
1894template void
1896 const Triangulation<2, 2> &tria,
1897 std::map<unsigned int,
1898 std::set<typename Triangulation<2, 2>::active_cell_iterator>>
1899 &vertices_cell_map);
1900template void
1902 const Triangulation<2, 3> &tria,
1903 std::map<unsigned int,
1904 std::set<typename Triangulation<2, 3>::active_cell_iterator>>
1905 &vertices_cell_map);
1906template void
1908 const Triangulation<3, 3> &tria,
1909 std::map<unsigned int,
1910 std::set<typename Triangulation<3, 3>::active_cell_iterator>>
1911 &vertices_cell_map);
1912
1913
1914template <int dim, int spacedim>
1915std::vector<typename Triangulation<dim, spacedim>::active_cell_iterator>
1917 std::map<
1918 unsigned int,
1919 std::set<typename Triangulation<dim, spacedim>::active_cell_iterator>>
1920 &vertices_cell_map,
1921 const typename Triangulation<dim, spacedim>::active_cell_iterator &cell)
1922{
1923 // Find all the cells that share a vertex with a reference cell, including
1924 // the initial cell.
1925 std::set<typename Triangulation<dim, spacedim>::active_cell_iterator>
1926 neighbors_cells;
1927
1928 // Loop over the vertices of the initial cell, find all the cells around
1929 // each vertex and add them to the set of cells around the reference cell.
1930 unsigned int vertices_per_cell = cell->n_vertices();
1931 for (unsigned int i = 0; i < vertices_per_cell; i++)
1932 {
1933 unsigned int v_index = cell->vertex_index(i);
1934 neighbors_cells.insert(vertices_cell_map[v_index].begin(),
1935 vertices_cell_map[v_index].end());
1936 }
1937
1938 // Transform the set into a vector.
1939 std::vector<typename Triangulation<dim, spacedim>::active_cell_iterator>
1940 cells_sharing_vertices(neighbors_cells.begin(), neighbors_cells.end());
1941 return cells_sharing_vertices;
1942}
1943
1944template std::vector<typename Triangulation<1, 2>::active_cell_iterator>
1946 std::map<unsigned int, std::set<Triangulation<1, 2>::active_cell_iterator>>
1947 &vertices_cell_map,
1948 const typename Triangulation<1, 2>::active_cell_iterator &cell);
1949
1950template std::vector<typename Triangulation<2>::active_cell_iterator>
1952 std::map<unsigned int,
1953 std::set<typename Triangulation<2>::active_cell_iterator>>
1954 &vertices_cell_map,
1955 const typename Triangulation<2>::active_cell_iterator &cell);
1956
1957template std::vector<typename Triangulation<2, 3>::active_cell_iterator>
1959 std::map<unsigned int,
1960 std::set<typename Triangulation<2, 3>::active_cell_iterator>>
1961 &vertices_cell_map,
1962 const typename Triangulation<2, 3>::active_cell_iterator &cell);
1963
1964template std::vector<typename Triangulation<3>::active_cell_iterator>
1966 std::map<unsigned int,
1967 std::set<typename Triangulation<3>::active_cell_iterator>>
1968 &vertices_cell_map,
1969 const typename Triangulation<3>::active_cell_iterator &cell);
1970
1971template <int dim>
1972void
1974 const DoFHandler<dim> &dof_handler,
1975 const Triangulation<dim> &box_triangulation)
1976{
1977 // A local DoFHandler on the box mesh is needed to iterate over its cells with
1978 // the iterator type expected by LetheGridTools::find_cells_in_cells. No dofs
1979 // need to be distributed on it, since the search is purely geometric.
1980 const DoFHandler<dim> box_dof_handler(box_triangulation);
1981
1982 // Find all the cells of the principal mesh that are partially contained
1983 // inside the box mesh and flag them for refinement.
1984 for (const auto &box_cell : box_dof_handler.active_cell_iterators())
1985 {
1986 const std::vector<typename DoFHandler<dim>::active_cell_iterator>
1987 cells_to_refine =
1988 LetheGridTools::find_cells_in_cells(dof_handler, box_cell);
1989
1990 for (const auto &cell_to_refine : cells_to_refine)
1991 {
1992 if (cell_to_refine->is_locally_owned())
1993 cell_to_refine->set_refine_flag();
1994 }
1995 }
1996}
1997
1998template void
2000 const DoFHandler<2> &dof_handler,
2001 const Triangulation<2> &box_triangulation);
2002template void
2004 const DoFHandler<3> &dof_handler,
2005 const Triangulation<3> &box_triangulation);
double find_point_triangle_distance(const std::vector< Point< dim > > &triangle_vertices, const Point< dim > &point)
Calculates the distance between points and a triangle (defined using three vertices)....
std::vector< typename DoFHandler< dim >::active_cell_iterator > find_cells_in_cells(const DoFHandler< dim > &dof_handler, const typename DoFHandler< dim >::active_cell_iterator &cell)
Return a vector of cells from the dof_handler that are inside a cell from another mesh.
void vertices_cell_mapping(const DoFHandler< dim > &dof_handler, std::map< unsigned int, std::set< typename DoFHandler< dim >::active_cell_iterator > > &vertices_cell_map)
Map the vertex index to the cells that includes that vertex.
std::vector< typename DoFHandler< dim >::active_cell_iterator > find_cells_around_edge(const DoFHandler< dim > &dof_handler, std::map< unsigned int, std::set< typename DoFHandler< dim >::active_cell_iterator > > &vertices_cell_map, const typename DoFHandler< dim >::active_cell_iterator &cell, Point< dim > &point_1, Point< dim > &point_2)
Return a vector of cells around an edge cell in spacedim. An edge cell as a dim of 1.
bool cell_pierced_by_edge(const typename DoFHandler< dim >::active_cell_iterator &cell, const TriaIterator< CellAccessor< 1, dim > > &cell_edge)
Return a bool that say if a cell is cut by a edge cell.
void vertices_cell_mapping_with_periodic_boundaries(const DoFHandler< dim > &dof_handler, std::map< unsigned int, std::set< typename DoFHandler< dim >::active_cell_iterator > > &vertices_cell_map)
Map the vertex index to the cells on periodic boundaries that includes the periodic coinciding vertex...
std::vector< Point< dim > > find_line_sphere_intersection(const Point< dim > &line_start, const Tensor< 1, dim > &line_direction, const Point< dim > &sphere_center, const double &sphere_diameter)
Calculates the intersection points between a line and a sphere. The full calculation is taken from Ge...
void rotate_mapping(const DoFHandler< dim > &dof_handler, MappingQCache< dim > &mapping_cache, const Mapping< dim > &mapping, const double rotation_angle, const Point< dim > &center_of_rotation=Point< dim >(), const unsigned int rotation_axis_direction=2)
Rotate the mapping according to the rotation angle in a rotor-stator configuration.
std::vector< typename DoFHandler< dim >::active_cell_iterator > find_cells_around_cell(std::map< unsigned int, std::set< typename DoFHandler< dim >::active_cell_iterator > > &vertices_cell_map, const typename DoFHandler< dim >::active_cell_iterator &cell)
Return a vector of cells around a cell. The vector of cells includes all the cells that share a verte...
std::pair< std::pair< Point< spacedim >, bool >, Tensor< 1, spacedim > > project_to_d_linear_object(const typename DoFHandler< structdim, spacedim >::active_cell_iterator &object, const Point< spacedim > &trial_point)
A copy of the project_to_d_linear from dealii that also outputs the normal of the flat.
ParticleTriangleContactIndicator
Indicates the type of contact between a particle and a triangle.
TriangleProjectionData< dim > prepare_triangle_projection_data(const std::vector< Point< dim > > &triangle)
Precomputes the particle-independent geometric data of a triangle (see TriangleProjectionData) used b...
std::vector< typename DoFHandler< dim >::active_cell_iterator > find_boundary_cells_in_sphere(const DoFHandler< dim > &dof_handler, const Point< dim > &center, const double radius)
Function returns all the boundary cells with at least one vertex in a sphere.
DoFHandler< dim >::active_cell_iterator find_cell_around_point_with_neighbors(const DoFHandler< dim > &dof_handler, std::map< unsigned int, std::set< typename DoFHandler< dim >::active_cell_iterator > > &vertices_cell_map, const typename DoFHandler< dim >::active_cell_iterator &cell, const Point< dim > &point)
Return the cell around a point based on an initial guess of a nearby cell.
bool cell_cut_by_flat(const typename DoFHandler< dim >::active_cell_iterator &cell, const typename DoFHandler< dim - 1, dim >::active_cell_iterator &cell_flat)
Return a bool that indicates if a cell is cut by a flat cell.
void flag_cells_in_refinement_box(const DoFHandler< dim > &dof_handler, const Triangulation< dim > &box_triangulation)
Flag for refinement of all the cells of a triangulation which lie within a refinement box.
std::tuple< bool, Point< 3 >, Tensor< 1, 3 >, ParticleTriangleContactIndicator > find_particle_triangle_projection(const TriangleProjectionData< dim > &triangle_data, const Point< dim > &particle_position, const double cutoff_distance)
Finds the contact point between a triangle (defined using three vertices) and a particle center,...
std::map< typename DoFHandler< spacedim >::active_cell_iterator, std::map< unsigned int, typename DoFHandler< structdim, spacedim >::active_cell_iterator > > find_cells_cut_by_object(const DoFHandler< spacedim > &dof_handler, std::map< unsigned int, std::set< typename DoFHandler< spacedim >::active_cell_iterator > > &vertices_cell_map, std::vector< SerialSolid< structdim, spacedim > > &list_of_objects)
Function returns all the cells cut by a list of object defined by a mesh.
DoFHandler< dim >::active_cell_iterator find_cell_around_point_with_tree(const DoFHandler< dim > &dof_handler, const Point< dim > &point)
Return the cell around a point by starting from the least refined level and iterating over children.
std::vector< typename DoFHandler< dim >::active_cell_iterator > find_cells_around_flat_cell(const DoFHandler< dim > &dof_handler, const typename DoFHandler< dim - 1, dim >::active_cell_iterator &cell, std::map< unsigned int, std::set< typename DoFHandler< dim >::active_cell_iterator > > &vertices_cell_map)
Return a vector of cells around a flat cell in spacedim. A flat cell has a dim of spacedim-1.
Particle-independent geometric data of a triangle (its first vertex, edge vectors,...
A functor that provides a way to check if two cells are the same cell. Used to store cells in hash se...
A functor that provides a unique and uniformly distributed hash for a a cell. Used to store cells in ...
Tensor< 1, 3 > tensor_nd_to_3d(const Tensor< 1, dim > &tensor)
Point< 3 > point_nd_to_3d(const Point< dim > &point)