| 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 |