Debian Codegraph @

include/deal.II/grid/tria_objects.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2006 - 2023 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_tria_objects_h
16 #define dealii_tria_objects_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/array_view.h>
21 #include <deal.II/base/exceptions.h>
22 #include <deal.II/base/geometry_info.h>
23
24 #include <vector>
25
26 DEAL_II_NAMESPACE_OPEN
27
28 // Forward declarations
29 #ifndef DOXYGEN
30 template <int dim, int spacedim>
31 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
32 class Triangulation;
33 template <class Accessor>
34 class TriaRawIterator;
35 template <int, int, int>
36 class TriaAccessor;
37 #endif
38
39 namespace internal
40 {
41 namespace TriangulationImplementation
42 {
43 /**
44 * General template for information belonging to the geometrical objects
45 * of a triangulation, i.e. lines, quads, hexahedra... Apart from the
46 * vector of objects additional information is included, namely vectors
47 * indicating the children, the used-status, user-flags, material-ids..
48 *
49 * Objects of these classes are included in the TriaLevel and TriaFaces
50 * classes.
51 */
52 class TriaObjects
53 {
54 public:
55 /**
56 * Constructor resetting some data.
57 */
58 TriaObjects();
59
60 /**
61 * Constructor for a specific dimension.
62 */
63 TriaObjects(const unsigned int structdim);
64
65 unsigned int structdim;
66
67 /**
68 * Vector of the objects belonging to this level. The index of the
69 * object equals the index in this container.
70 */
71 std::vector<int> cells;
72
73 /**
74 * Return number of geometric objects stored by this class.
75 */
76 unsigned int
77 n_objects() const;
78
79 /**
80 * Return a view on the indices of the objects that bound the @p
81 * index-th object stored by the current object. For example, if
82 * the current object stores cells, then this function returns
83 * the equivalent of an array containing the indices of the
84 * faces that bound the @p index-th cell.
85 */
86 ArrayView<int>
87 get_bounding_object_indices(const unsigned int index);
88
89 /**
90 * Index of the even children of an object. Since when objects are
91 * refined, all children are created at the same time, they are appended
92 * to the list at least in pairs after each other. We therefore only
93 * store the index of the even children, the uneven follow immediately
94 * afterwards.
95 *
96 * If an object has no children, -1 is stored in this list. An object is
97 * called active if it has no children. The function
98 * TriaAccessorBase::has_children() tests for this.
99 */
100 std::vector<int> children;
101
102 /**
103 * Store the refinement case each of the cells is refined with. This
104 * vector might be replaced by vector<vector<bool> > (dim, vector<bool>
105 * (n_cells)) which is more memory efficient.
106 */
107 std::vector<std::uint8_t> refinement_cases;
108
109 /**
110 * Vector storing whether an object is used in the @p cells vector.
111 *
112 * Since it is difficult to delete elements in a @p vector, when an
113 * element is not needed any more (e.g. after derefinement), it is not
114 * deleted from the list, but rather the according @p used flag is set
115 * to @p false.
116 */
117 std::vector<bool> used;
118
119 /**
120 * Make available a field for user data, one bit per object. This field
121 * is usually used when an operation runs over all cells and needs
122 * information whether another cell (e.g. a neighbor) has already been
123 * processed.
124 *
125 * You can clear all used flags using
126 * Triangulation::clear_user_flags().
127 */
128 std::vector<bool> user_flags;
129
130
131 /**
132 * We use this union to store boundary and material data. Because only
133 * one out of these two is actually needed here, we use an union.
134 */
135 struct BoundaryOrMaterialId
136 {
137 union
138 {
139 types::boundary_id boundary_id;
140 types::material_id material_id;
141 };
142
143
144 /**
145 * Default constructor.
146 */
147 BoundaryOrMaterialId();
148
149 /**
150 * Return the size of objects of this kind.
151 */
152 static std::size_t
153 memory_consumption();
154
155 /**
156 * Read or write the data of this object to or from a stream for the
157 * purpose of serialization using the [BOOST serialization
158 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
159 */
160 template <class Archive>
161 void
162 serialize(Archive &ar, const unsigned int version);
163 };
164
165 /**
166 * Store boundary and material data. For example, in one dimension, this
167 * field stores the material id of a line, which is a number between 0
168 * and numbers::invalid_material_id-1. In more than one dimension, lines
169 * have no material id, but they may be at the boundary; then, we store
170 * the boundary indicator in this field, which denotes to which part of
171 * the boundary this line belongs and which boundary conditions hold on
172 * this part. The boundary indicator also is a number between zero and
173 * numbers::internal_face_boundary_id-1; the id
174 * numbers::internal_face_boundary_id is reserved for lines in the
175 * interior and may be used to check whether a line is at the boundary
176 * or not, which otherwise is not possible if you don't know which cell
177 * it belongs to.
178 */
179 std::vector<BoundaryOrMaterialId> boundary_or_material_id;
180
181 /**
182 * Store manifold ids. This field stores the manifold id of each object,
183 * which is a number between 0 and numbers::flat_manifold_id-1.
184 */
185 std::vector<types::manifold_id> manifold_id;
186
187 /**
188 * Return an iterator to the next free slot for a single object. This
189 * function is only used by Triangulation::execute_refinement()
190 * in 3d.
191 *
192 * @warning Interestingly, this function is not used for 1d or 2d
193 * triangulations, where it seems the authors of the refinement function
194 * insist on reimplementing its contents.
195 *
196 * @todo This function is not instantiated for the codim-one case
197 */
198 template <int structdim, int dim, int spacedim>
199 dealii::TriaRawIterator<dealii::TriaAccessor<structdim, dim, spacedim>>
200 next_free_single_object(const Triangulation<dim, spacedim> &tria);
201
202 /**
203 * Return an iterator to the next free slot for a pair of objects. This
204 * function is only used by Triangulation::execute_refinement()
205 * in 3d.
206 *
207 * @warning Interestingly, this function is not used for 1d or 2d
208 * triangulations, where it seems the authors of the refinement function
209 * insist on reimplementing its contents.
210 *
211 * @todo This function is not instantiated for the codim-one case
212 */
213 template <int structdim, int dim, int spacedim>
214 dealii::TriaRawIterator<dealii::TriaAccessor<structdim, dim, spacedim>>
215 next_free_pair_object(const Triangulation<dim, spacedim> &tria);
216
217 /**
218 * Return an iterator to the next free slot for a pair of hexes. Only
219 * implemented for <code>G=Hexahedron</code>.
220 */
221 template <int dim, int spacedim>
222 typename Triangulation<dim, spacedim>::raw_hex_iterator
223 next_free_hex(const Triangulation<dim, spacedim> &tria,
224 const unsigned int level);
225
226 /**
227 * Access to user pointers.
228 */
229 void *&
230 user_pointer(const unsigned int i);
231
232 /**
233 * Read-only access to user pointers.
234 */
235 const void *
236 user_pointer(const unsigned int i) const;
237
238 /**
239 * Access to user indices.
240 */
241 unsigned int &
242 user_index(const unsigned int i);
243
244 /**
245 * Read-only access to user pointers.
246 */
247 unsigned int
248 user_index(const unsigned int i) const;
249
250 /**
251 * Reset user data to zero.
252 */
253 void
254 clear_user_data(const unsigned int i);
255
256 /**
257 * Clear all user pointers or indices and reset their type, such that
258 * the next access may be either or.
259 */
260 void
261 clear_user_data();
262
263 /**
264 * Clear all user flags.
265 */
266 void
267 clear_user_flags();
268
269 /**
270 * Determine an estimate for the memory consumption (in bytes) of this
271 * object.
272 */
273 std::size_t
274 memory_consumption() const;
275
276 /**
277 * Read or write the data of this object to or from a stream for the
278 * purpose of serialization using the [BOOST serialization
279 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
280 */
281 template <class Archive>
282 void
283 serialize(Archive &ar, const unsigned int version);
284
285 /**
286 * Triangulation objects can either access a user pointer or a
287 * user index. What you tried to do is trying to access one of those
288 * after using the other.
289 *
290 * @ingroup Exceptions
291 */
292 DeclException0(ExcPointerIndexClash);
293
294 /**
295 * Counter for next_free_single_* functions
296 */
297 unsigned int next_free_single;
298
299 /**
300 * Counter for next_free_pair_* functions
301 */
302 unsigned int next_free_pair;
303
304 /**
305 * Bool flag for next_free_single_* functions
306 */
307 bool reverse_order_next_free_single;
308
309 /**
310 * The data type storing user pointers or user indices.
311 */
312 struct UserData
313 {
314 union
315 {
316 /// The entry used as user
317 /// pointer.
318 void *p;
319 /// The entry used as user
320 /// index.
321 unsigned int i;
322 };
323
324 /**
325 * Default constructor.
326 */
327 UserData()
328 {
329 p = nullptr;
330 }
331
332 /**
333 * Write the data of this object to a stream for the purpose of
334 * serialization using the [BOOST serialization
335 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
336 */
337 template <class Archive>
338 void
339 serialize(Archive &ar, const unsigned int version);
340 };
341
342 /**
343 * Enum describing the possible types of userdata.
344 */
345 enum UserDataType
346 {
347 /// No userdata used yet.
348 data_unknown,
349 /// UserData contains pointers.
350 data_pointer,
351 /// UserData contains indices.
352 data_index
353 };
354
355
356 /**
357 * Pointer which is not used by the library but may be accessed and set
358 * by the user to handle data local to a line/quad/etc.
359 */
360 std::vector<UserData> user_data;
361
362 /**
363 * In order to avoid confusion between user pointers and indices, this
364 * enum is set by the first function accessing either and subsequent
365 * access will not be allowed to change the type of data accessed.
366 */
367 mutable UserDataType user_data_type;
368 };
369
370
371 //----------------------------------------------------------------------//
372
373 inline unsigned int
374 TriaObjects::n_objects() const
375 {
376 // ensure that sizes are consistent, and then return one that
377 // corresponds to the number of objects
378 AssertDimension(cells.size(), manifold_id.size() * 2 * this->structdim);
379 return manifold_id.size();
380 }
381
382
383
384 inline ArrayView<int>
385 TriaObjects::get_bounding_object_indices(const unsigned int index)
386 {
387 // assume that each cell has the same number of faces
388 const unsigned int faces_per_cell = 2 * this->structdim;
389 return ArrayView<int>(cells.data() + index * faces_per_cell,
390 faces_per_cell);
391 }
392
393
394
395 inline TriaObjects::BoundaryOrMaterialId::BoundaryOrMaterialId()
396 {
397 material_id = numbers::invalid_material_id;
398 }
399
400
401
402 inline std::size_t
403 TriaObjects::BoundaryOrMaterialId::memory_consumption()
404 {
405 return sizeof(BoundaryOrMaterialId);
406 }
407
408
409
410 template <class Archive>
411 void
412 TriaObjects::BoundaryOrMaterialId::serialize(Archive &ar,
413 const unsigned int /*version*/)
414 {
415 // serialize this
416 // structure by
417 // writing and
418 // reading the larger
419 // of the two values,
420 // in order to make
421 // sure we get all
422 // bits
423 if (sizeof(material_id) > sizeof(boundary_id))
424 ar &material_id;
425 else
426 ar &boundary_id;
427 }
428
429
430 inline void *&
431 TriaObjects::user_pointer(const unsigned int i)
432 {
433 Assert(user_data_type == data_unknown || user_data_type == data_pointer,
434 ExcPointerIndexClash());
435 user_data_type = data_pointer;
436
437 AssertIndexRange(i, user_data.size());
438 return user_data[i].p;
439 }
440
441
442 inline const void *
443 TriaObjects::user_pointer(const unsigned int i) const
444 {
445 Assert(user_data_type == data_unknown || user_data_type == data_pointer,
446 ExcPointerIndexClash());
447 user_data_type = data_pointer;
448
449 AssertIndexRange(i, user_data.size());
450 return user_data[i].p;
451 }
452
453
454 inline unsigned int &
455 TriaObjects::user_index(const unsigned int i)
456 {
457 Assert(user_data_type == data_unknown || user_data_type == data_index,
458 ExcPointerIndexClash());
459 user_data_type = data_index;
460
461 AssertIndexRange(i, user_data.size());
462 return user_data[i].i;
463 }
464
465
466 inline void
467 TriaObjects::clear_user_data(const unsigned int i)
468 {
469 AssertIndexRange(i, user_data.size());
470 user_data[i].i = 0;
471 }
472
473
474 inline TriaObjects::TriaObjects()
475 : structdim(numbers::invalid_unsigned_int)
476 , next_free_single(numbers::invalid_unsigned_int)
477 , next_free_pair(numbers::invalid_unsigned_int)
478 , reverse_order_next_free_single(false)
479 , user_data_type(data_unknown)
480 {}
481
482
483 inline TriaObjects::TriaObjects(const unsigned int structdim)
484 : structdim(structdim)
485 , next_free_single(numbers::invalid_unsigned_int)
486 , next_free_pair(numbers::invalid_unsigned_int)
487 , reverse_order_next_free_single(false)
488 , user_data_type(data_unknown)
489 {}
490
491
492 inline unsigned int
493 TriaObjects::user_index(const unsigned int i) const
494 {
495 Assert(user_data_type == data_unknown || user_data_type == data_index,
496 ExcPointerIndexClash());
497 user_data_type = data_index;
498
499 AssertIndexRange(i, user_data.size());
500 return user_data[i].i;
501 }
502
503
504 inline void
505 TriaObjects::clear_user_data()
506 {
507 user_data_type = data_unknown;
508 for (auto &data : user_data)
509 data.p = nullptr;
510 }
511
512
513 inline void
514 TriaObjects::clear_user_flags()
515 {
516 user_flags.assign(user_flags.size(), false);
517 }
518
519
520 template <class Archive>
521 void
522 TriaObjects::UserData::serialize(Archive &ar, const unsigned int)
523 {
524 // serialize this as an integer
525 ar &i;
526 }
527
528
529
530 template <class Archive>
531 void
532 TriaObjects::serialize(Archive &ar, const unsigned int)
533 {
534 ar &structdim;
535 ar &cells &children;
536 ar &refinement_cases;
537 ar &used;
538 ar &user_flags;
539 ar &boundary_or_material_id;
540 ar &manifold_id;
541 ar &next_free_single &next_free_pair &reverse_order_next_free_single;
542 ar &user_data &user_data_type;
543 }
544
545
546 //----------------------------------------------------------------------//
547
548 template <int structdim_, int dim, int spacedim>
549 dealii::TriaRawIterator<dealii::TriaAccessor<structdim_, dim, spacedim>>
550 TriaObjects::next_free_single_object(
551 const Triangulation<dim, spacedim> &tria)
552 {
553 // TODO: Think of a way to ensure that we are using the correct
554 // triangulation, i.e. the one containing *this.
555
556 AssertDimension(structdim_, this->structdim);
557
558 int pos = next_free_single, last = used.size() - 1;
559 if (!reverse_order_next_free_single)
560 {
561 // first sweep forward, only use really single slots, do not use
562 // pair slots
563 for (; pos < last; ++pos)
564 if (!used[pos])
565 if (used[++pos])
566 {
567 // this was a single slot
568 pos -= 1;
569 break;
570 }
571 if (pos >= last)
572 {
573 reverse_order_next_free_single = true;
574 next_free_single = used.size() - 1;
575 pos = used.size() - 1;
576 }
577 else
578 next_free_single = pos + 1;
579 }
580
581 if (reverse_order_next_free_single)
582 {
583 // second sweep, use all slots, even
584 // in pairs
585 for (; pos >= 0; --pos)
586 if (!used[pos])
587 break;
588 if (pos > 0)
589 next_free_single = pos - 1;
590 else
591 // no valid single object anymore
592 return dealii::TriaRawIterator<
593 dealii::TriaAccessor<structdim_, dim, spacedim>>(&tria, -1, -1);
594 }
595
596 return dealii::TriaRawIterator<
597 dealii::TriaAccessor<structdim_, dim, spacedim>>(&tria, 0, pos);
598 }
599
600
601
602 template <int structdim_, int dim, int spacedim>
603 dealii::TriaRawIterator<dealii::TriaAccessor<structdim_, dim, spacedim>>
604 TriaObjects::next_free_pair_object(const Triangulation<dim, spacedim> &tria)
605 {
606 // TODO: Think of a way to ensure that we are using the correct
607 // triangulation, i.e. the one containing *this.
608
609 AssertDimension(structdim_, this->structdim);
610
611 int pos = next_free_pair, last = used.size() - 1;
612 for (; pos < last; ++pos)
613 if (!used[pos])
614 if (!used[++pos])
615 {
616 // this was a pair slot
617 pos -= 1;
618 break;
619 }
620 if (pos >= last)
621 // no free slot
622 return dealii::TriaRawIterator<
623 dealii::TriaAccessor<structdim_, dim, spacedim>>(&tria, -1, -1);
624 else
625 next_free_pair = pos + 2;
626
627 return dealii::TriaRawIterator<
628 dealii::TriaAccessor<structdim_, dim, spacedim>>(&tria, 0, pos);
629 }
630 } // namespace TriangulationImplementation
631 } // namespace internal
632
633
634
635 DEAL_II_NAMESPACE_CLOSE
636
637 #endif