Debian Codegraph @

include/deal.II/grid/cell_id_translator.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2021 - 2024 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_cell_id_translator_h
16 #define dealii_cell_id_translator_h
17
18 #include <deal.II/base/exceptions.h>
19 #include <deal.II/base/geometry_info.h>
20
21 #include <deal.II/grid/cell_id.h>
22 #include <deal.II/grid/tria_accessor.h>
23
24 #include <cstdint>
25 #include <limits>
26
27 DEAL_II_NAMESPACE_OPEN
28
29 namespace internal
30 {
31 /**
32 * A class that helps to translate between CellIDs and globally unique
33 * indices. The resulting index space might be non-contiguous in the case
34 * of locally refined meshes.
35 *
36 * The following code snippet shows how to set up an IndexSet for active
37 * cells, using this class:
38 * @code
39 * // set up translator
40 * CellIDTranslator<dim> translator(tria.n_global_coarse_cells(),
41 * tria.n_global_levels());
42 *
43 * // initialize the index set with the correct size
44 * IndexSet index_set(translator.size());
45 *
46 * // convert IDs to indices and add them to the index set
47 * for(const auto & cell : tria.active_cell_iterators())
48 * index_set.add_index(translator.translate(cell));
49 * @endcode
50 *
51 * @note The definition of the indices are not relevant.
52 */
53 template <int dim>
54 class CellIDTranslator
55 {
56 public:
57 /**
58 * Constructor taking the number of global coarse cells and number of
59 * global levels of a triangulation.
60 */
61 CellIDTranslator(const types::global_cell_index n_coarse_cells,
62 const types::global_cell_index n_global_levels);
63
64 /**
65 * Return maximum number of cells, i.e., in the case the triangulation
66 * were globally refined `n_global_levels - 1` times.
67 */
68 types::global_cell_index
69 size() const;
70
71 /**
72 * Convert a @p cell of type TriaAccessor, CellAccessor, DoFAccessor, or
73 * DoFCellAccessor to an index.
74 */
75 template <typename Accessor>
76 types::global_cell_index
77 translate(const TriaIterator<Accessor> &cell) const;
78
79 /**
80 * Convert a @p cell of type TriaAccessor, CellAccessor, DoFAccessor, or
81 * DoFCellAccessor to an index unique on a level.
82 */
83 template <typename Accessor>
84 static types::global_cell_index
85 translate_level(const TriaIterator<Accessor> &cell);
86
87 /**
88 * Convert the @p i-th child of @p to an index.
89 */
90 template <typename Accessor>
91 types::global_cell_index
92 translate(const TriaIterator<Accessor> &cell,
93 const types::global_cell_index i) const;
94
95 /**
96 * Convert an index to a CellId.
97 */
98 CellId
99 to_cell_id(const types::global_cell_index id) const;
100
101 private:
102 /**
103 * Convert a binary representation to a index.
104 */
105 static types::global_cell_index
106 convert_cell_id_binary_type_to_level_coarse_cell_id(
107 const typename CellId::binary_type &binary_representation);
108
109 /**
110 * Number of global coarse cells.
111 */
112 const types::global_cell_index n_coarse_cells;
113
114 /**
115 * Number of global levels.
116 */
117 const types::global_cell_index n_global_levels;
118
119 /**
120 * Offset of each level in the index space.
121 */
122 std::vector<types::global_cell_index> tree_sizes;
123 };
124
125
126
127 template <int dim>
128 CellIDTranslator<dim>::CellIDTranslator(
129 const types::global_cell_index n_coarse_cells,
130 const types::global_cell_index n_global_levels)
131 : n_coarse_cells(n_coarse_cells)
132 , n_global_levels(n_global_levels)
133 {
134 // The class stores indices as types::global_cell_index variables,
135 // but when configuring deal.II with default flags, this is a 32-bit
136 // data type and it is possible with highly (locally) refined meshes
137 // that we exceed the maximal 32-bit numbers even with relatively
138 // modest numbers of cells. Check for this by first calculating
139 // the maximal index we will get in 64-bit arithmetic and testing
140 // that it is representable in 32-bit arithmetic:
141 std::uint64_t max_cell_index = 0;
142
143 for (unsigned int i = 0; i < n_global_levels; ++i)
144 max_cell_index +=
145 Utilities::pow<std::uint64_t>(GeometryInfo<dim>::max_children_per_cell,
146 i) *
147 n_coarse_cells;
148
149 max_cell_index -= 1;
150
151 AssertThrow(
152 max_cell_index <= std::numeric_limits<types::global_cell_index>::max(),
153 ExcMessage(
154 "You have exceeded the maximal number of possible indices this function "
155 "can handle. The current setup (n_coarse_cells=" +
156 std::to_string(n_coarse_cells) +
157 ", n_global_levels=" + std::to_string(n_global_levels) + ") requires " +
158 std::to_string(max_cell_index + 1) +
159 " indices but the current deal.II configuration only supports " +
160 std::to_string(std::numeric_limits<types::global_cell_index>::max()) +
161 " indices. You may want to consider to build deal.II with 64bit "
162 "indices (-D DEAL_II_WITH_64BIT_INDICES=\"ON\") to increase the limit "
163 "of indices."));
164
165 // Now do the whole computation again, but for real:
166 tree_sizes.reserve(n_global_levels + 1);
167 tree_sizes.push_back(0);
168 for (unsigned int i = 0; i < n_global_levels; ++i)
169 tree_sizes.push_back(tree_sizes.back() +
170 Utilities::pow<types::global_cell_index>(
171 GeometryInfo<dim>::max_children_per_cell, i) *
172 n_coarse_cells);
173 }
174
175
176
177 template <int dim>
178 types::global_cell_index
179 CellIDTranslator<dim>::size() const
180 {
181 return n_coarse_cells *
182 (Utilities::pow<types::global_cell_index>(
183 GeometryInfo<dim>::max_children_per_cell, n_global_levels) -
184 1);
185 }
186
187
188
189 template <int dim>
190 template <typename Accessor>
191 types::global_cell_index
192 CellIDTranslator<dim>::translate(const TriaIterator<Accessor> &cell) const
193 {
194 static_assert(dim == Accessor::dimension &&
195 dim == Accessor::structure_dimension,
196 "The information can only be queried for cells.");
197
198 return translate_level(cell) + tree_sizes[cell->level()];
199 }
200
201
202
203 template <int dim>
204 template <typename Accessor>
205 types::global_cell_index
206 CellIDTranslator<dim>::translate_level(const TriaIterator<Accessor> &cell)
207 {
208 static_assert(dim == Accessor::dimension &&
209 dim == Accessor::structure_dimension,
210 "The information can only be queried for cells.");
211
212 return convert_cell_id_binary_type_to_level_coarse_cell_id(
213 CellAccessor<Accessor::dimension, Accessor::space_dimension>(*cell)
214 .id()
215 .template to_binary<dim>());
216 }
217
218
219
220 template <int dim>
221 template <typename Accessor>
222 types::global_cell_index
223 CellIDTranslator<dim>::translate(const TriaIterator<Accessor> &cell,
224 const types::global_cell_index i) const
225 {
226 static_assert(dim == Accessor::dimension &&
227 dim == Accessor::structure_dimension,
228 "The information can only be queried for cells.");
229
230 return (translate(cell) - tree_sizes[cell->level()]) *
231 GeometryInfo<dim>::max_children_per_cell +
232 i + tree_sizes[cell->level() + 1];
233 }
234
235
236
237 template <int dim>
238 CellId
239 CellIDTranslator<dim>::to_cell_id(const types::global_cell_index id) const
240 {
241 std::vector<std::uint8_t> child_indices;
242
243 types::global_cell_index id_temp = id;
244
245 types::global_cell_index level = 0;
246
247 for (; level < n_global_levels; ++level)
248 if (id < tree_sizes[level])
249 break;
250 level -= 1;
251
252 id_temp -= tree_sizes[level];
253
254 for (types::global_cell_index l = 0; l < level; ++l)
255 {
256 child_indices.push_back(id_temp %
257 GeometryInfo<dim>::max_children_per_cell);
258 id_temp /= GeometryInfo<dim>::max_children_per_cell;
259 }
260
261 std::reverse(child_indices.begin(), child_indices.end());
262
263 return {id_temp, child_indices};
264 }
265
266
267
268 template <int dim>
269 types::global_cell_index
270 CellIDTranslator<dim>::convert_cell_id_binary_type_to_level_coarse_cell_id(
271 const typename CellId::binary_type &binary_representation)
272 {
273 // exploiting the structure of CellId::binary_type
274 // see also the documentation of CellId
275
276 // actual coarse-grid id
277 const unsigned int coarse_cell_id = binary_representation[0];
278 const unsigned int n_child_indices = binary_representation[1] >> 2;
279
280 const unsigned int children_per_value =
281 sizeof(CellId::binary_type::value_type) * 8 / dim;
282 unsigned int child_level = 0;
283 unsigned int binary_entry = 2;
284
285 // compute new coarse-grid id: c_{i+1} = c_{i}*2^dim + q on path to cell
286 types::global_cell_index level_coarse_cell_id = coarse_cell_id;
287 while (child_level < n_child_indices)
288 {
289 Assert(binary_entry < binary_representation.size(), ExcInternalError());
290
291 for (unsigned int j = 0; j < children_per_value; ++j)
292 {
293 unsigned int cell_index =
294 (((binary_representation[binary_entry] >> (j * dim))) &
295 (GeometryInfo<dim>::max_children_per_cell - 1));
296 level_coarse_cell_id =
297 level_coarse_cell_id * GeometryInfo<dim>::max_children_per_cell +
298 cell_index;
299 ++child_level;
300 if (child_level == n_child_indices)
301 break;
302 }
303 ++binary_entry;
304 }
305
306 return level_coarse_cell_id;
307 }
308
309 } // namespace internal
310
311 DEAL_II_NAMESPACE_CLOSE
312
313 #endif