From e39c5e46d9e68de995b29cd61a2cf4bd04264a2c Mon Sep 17 00:00:00 2001 From: David Wells Date: Wed, 21 Apr 2021 11:40:49 -0400 Subject: [PATCH] Move GridReordering::invert_all_negative_measure_cells(). --- include/deal.II/grid/grid_reordering.h | 3 + include/deal.II/grid/grid_tools.h | 24 +++++ source/grid/grid_generator.cc | 4 +- source/grid/grid_in.cc | 34 ++---- source/grid/grid_reordering.cc | 142 ++----------------------- source/grid/grid_tools.cc | 71 +++++++++++++ source/grid/grid_tools.inst.in | 5 + 7 files changed, 124 insertions(+), 159 deletions(-) diff --git a/include/deal.II/grid/grid_reordering.h b/include/deal.II/grid/grid_reordering.h index 9a9386a889..6d7d76ac78 100644 --- a/include/deal.II/grid/grid_reordering.h +++ b/include/deal.II/grid/grid_reordering.h @@ -81,7 +81,10 @@ public: * vertices within a cell. If false (the default), then use the "old-style" * ordering of vertices within cells used by deal.II before version 5.2 and * as explained in the documentation of this class. + * + * @deprecated Use GridTools::invert_all_negative_measure_cells() instead. */ + DEAL_II_DEPRECATED_EARLY static void invert_all_cells_of_negative_grid( const std::vector> &all_vertices, diff --git a/include/deal.II/grid/grid_tools.h b/include/deal.II/grid/grid_tools.h index a9a1666399..723ed0f802 100644 --- a/include/deal.II/grid/grid_tools.h +++ b/include/deal.II/grid/grid_tools.h @@ -436,6 +436,30 @@ namespace GridTools std::vector & considered_vertices, const double tol = 1e-12); + /** + * Grids generated by grid generators may have an orientation of cells which + * is the inverse of the orientation required by deal.II. + * + * In 2d and 3d this function checks whether all cells have negative or + * positive measure/volume. In the former case, all cells are inverted. It + * does nothing in 1d. + * + * The inversion of cells might also work when only a subset of all cells + * have negative volume. However, grids consisting of a mixture of negative + * and positively oriented cells are very likely to be broken. Therefore, an + * exception is thrown, in case cells are not uniformly oriented. + * + * @note This function should be called before GridTools::consistently_order_cells(). + * + * @param all_vertices The vertices of the mesh. + * @param cells The array of CellData objects that describe the mesh's topology. + */ + template + void + invert_all_negative_measure_cells( + const std::vector> &all_vertices, + std::vector> & cells); + /*@}*/ /** * @name Rotating, stretching and otherwise transforming meshes diff --git a/source/grid/grid_generator.cc b/source/grid/grid_generator.cc index 2330327063..f7e99e478c 100644 --- a/source/grid/grid_generator.cc +++ b/source/grid/grid_generator.cc @@ -1860,9 +1860,7 @@ namespace GridGenerator cells[n_cells - 1].vertices[GeometryInfo<3>::ucd_to_deal[7]] = (1 + n_rotations) % 4; - GridReordering::invert_all_cells_of_negative_grid(vertices, - cells, - true); + GridTools::invert_all_negative_measure_cells(vertices, cells); tria.create_triangulation(vertices, cells, SubCellData()); } diff --git a/source/grid/grid_in.cc b/source/grid/grid_in.cc index 4696f6a679..0ee5e9b82e 100644 --- a/source/grid/grid_in.cc +++ b/source/grid/grid_in.cc @@ -560,7 +560,7 @@ GridIn::read_vtk(std::istream &in) // TODO: the functions below (GridTools::delete_unused_vertices(), - // GridTools::invert_all_cells_of_negative_grid(), + // GridTools::invert_all_negative_measure_cells(), // GridReordering::reorder_cells()) need to be // revisited for simplex/mixed meshes @@ -569,8 +569,7 @@ GridIn::read_vtk(std::istream &in) GridTools::delete_unused_vertices(vertices, cells, subcelldata); if (dim == spacedim) - GridReordering::invert_all_cells_of_negative_grid( - vertices, cells, true); + GridTools::invert_all_negative_measure_cells(vertices, cells); GridReordering::reorder_cells(cells, true); tria->create_triangulation(vertices, cells, subcelldata); @@ -861,9 +860,7 @@ GridIn::read_unv(std::istream &in) GridTools::delete_unused_vertices(vertices, cells, subcelldata); if (dim == spacedim) - GridReordering::invert_all_cells_of_negative_grid(vertices, - cells, - true); + GridTools::invert_all_negative_measure_cells(vertices, cells); GridReordering::reorder_cells(cells, true); @@ -1097,9 +1094,7 @@ GridIn::read_ucd(std::istream &in, GridTools::delete_unused_vertices(vertices, cells, subcelldata); // ... and cells if (dim == spacedim) - GridReordering::invert_all_cells_of_negative_grid(vertices, - cells, - true); + GridTools::invert_all_negative_measure_cells(vertices, cells); GridReordering::reorder_cells(cells, true); tria->create_triangulation(vertices, cells, subcelldata); } @@ -1352,9 +1347,7 @@ GridIn::read_dbmesh(std::istream &in) // do some clean-up on vertices... GridTools::delete_unused_vertices(vertices, cells, subcelldata); // ...and cells - GridReordering::invert_all_cells_of_negative_grid(vertices, - cells, - true); + GridTools::invert_all_negative_measure_cells(vertices, cells); GridReordering::reorder_cells(cells, true); tria->create_triangulation(vertices, cells, subcelldata); } @@ -1422,9 +1415,7 @@ GridIn::read_xda(std::istream &in) // do some clean-up on vertices... GridTools::delete_unused_vertices(vertices, cells, subcelldata); // ... and cells - GridReordering::invert_all_cells_of_negative_grid(vertices, - cells, - true); + GridTools::invert_all_negative_measure_cells(vertices, cells); GridReordering::reorder_cells(cells, true); tria->create_triangulation(vertices, cells, subcelldata); } @@ -2104,7 +2095,7 @@ GridIn::read_msh(std::istream &in) AssertThrow(cells.size() > 0, ExcGmshNoCellInformation()); // TODO: the functions below (GridTools::delete_unused_vertices(), - // GridTools::invert_all_cells_of_negative_grid(), + // GridTools::invert_all_negative_measure_cells(), // GridReordering::reorder_cells()) need to be revisited // for simplex/mixed meshes @@ -2114,8 +2105,7 @@ GridIn::read_msh(std::istream &in) GridTools::delete_unused_vertices(vertices, cells, subcelldata); // ... and cells if (dim == spacedim) - GridReordering::invert_all_cells_of_negative_grid( - vertices, cells, true); + GridTools::invert_all_negative_measure_cells(vertices, cells); GridReordering::reorder_cells(cells, true); } tria->create_triangulation(vertices, cells, subcelldata); @@ -2808,9 +2798,7 @@ GridIn<2>::read_tecplot(std::istream &in) AssertThrow(in, ExcIO()); // do some cleanup on cells - GridReordering::invert_all_cells_of_negative_grid(vertices, - cells, - true); + GridTools::invert_all_negative_measure_cells(vertices, cells); GridReordering::reorder_cells(cells, true); tria->create_triangulation(vertices, cells, subcelldata); } @@ -2965,9 +2953,7 @@ GridIn::read_assimp(const std::string &filename, GridTools::delete_unused_vertices(vertices, cells, subcelldata); if (dim == spacedim) - GridReordering::invert_all_cells_of_negative_grid(vertices, - cells, - true); + GridTools::invert_all_negative_measure_cells(vertices, cells); GridReordering::reorder_cells(cells, true); tria->create_triangulation(vertices, cells, subcelldata); diff --git a/source/grid/grid_reordering.cc b/source/grid/grid_reordering.cc index 922af99583..76f532e1d5 100644 --- a/source/grid/grid_reordering.cc +++ b/source/grid/grid_reordering.cc @@ -1154,66 +1154,13 @@ GridReordering<2>::invert_all_cells_of_negative_grid( std::vector> & cells, const bool use_new_style_ordering) { - unsigned int vertices_lex[GeometryInfo<2>::vertices_per_cell]; - unsigned int n_negative_cells = 0; - - // GridTools::cell_measure requires the vertices to be in lexicographic - // ordering - auto copy_vertices_to_temp = [&](const CellData<2> &cell) { - if (use_new_style_ordering) - { - std::copy(cell.vertices.begin(), - cell.vertices.end(), - std::begin(vertices_lex)); - } - else - { - for (const unsigned int i : GeometryInfo<2>::vertex_indices()) - vertices_lex[GeometryInfo<2>::ucd_to_deal[i]] = cell.vertices[i]; - } - }; + if (!use_new_style_ordering) + reorder_old_to_new_style(cells); - for (auto &cell : cells) - { - copy_vertices_to_temp(cell); - if (GridTools::cell_measure<2>(all_vertices, vertices_lex) < 0) - { - ++n_negative_cells; - if (use_new_style_ordering) - std::swap(cell.vertices[1], cell.vertices[2]); - else - std::swap(cell.vertices[1], cell.vertices[3]); - - // Check whether the resulting cell is now ok. - // If not, then the grid is seriously broken and - // we just give up. - copy_vertices_to_temp(cell); - AssertThrow(GridTools::cell_measure<2>(all_vertices, vertices_lex) > - 0, - ExcInternalError()); - } - } + GridTools::invert_all_negative_measure_cells(all_vertices, cells); - // We assume that all cells of a grid have - // either positive or negative volumes but - // not both mixed. Although above reordering - // might work also on single cells, grids - // with both kind of cells are very likely to - // be broken. Check for this here. - AssertThrow( - n_negative_cells == 0 || n_negative_cells == cells.size(), - ExcMessage( - std::string("This class assumes that either all cells have positive " - "volume, or that all cells have been specified in an " - "inverted vertex order so that their volume is negative. " - "(In the latter case, this class automatically inverts " - "every cell.) However, the mesh you have specified " - "appears to have both cells with positive and cells with " - "negative volume. You need to check your mesh which " - "cells these are and how they got there.\n" - "As a hint, of the total ") + - std::to_string(cells.size()) + " cells in the mesh, " + - std::to_string(n_negative_cells) + " appear to have a negative volume.")); + if (!use_new_style_ordering) + reorder_new_to_old_style(cells); } @@ -1237,82 +1184,13 @@ GridReordering<3>::invert_all_cells_of_negative_grid( std::vector> & cells, const bool use_new_style_ordering) { - unsigned int vertices_lex[GeometryInfo<3>::vertices_per_cell]; - unsigned int n_negative_cells = 0; - - // GridTools::cell_measure requires the vertices to be in lexicographic - // ordering - auto copy_vertices_to_temp = [&](const CellData<3> &cell) { - if (use_new_style_ordering) - { - std::copy(cell.vertices.begin(), - cell.vertices.end(), - std::begin(vertices_lex)); - } - else - { - for (const unsigned int i : GeometryInfo<3>::vertex_indices()) - vertices_lex[GeometryInfo<3>::ucd_to_deal[i]] = cell.vertices[i]; - } - }; + if (!use_new_style_ordering) + reorder_old_to_new_style(cells); - for (auto &cell : cells) - { - copy_vertices_to_temp(cell); - if (GridTools::cell_measure<3>(all_vertices, vertices_lex) < 0) - { - ++n_negative_cells; - // reorder vertices: swap front and back face - if (use_new_style_ordering) - { - std::swap(cell.vertices[0], cell.vertices[2]); - std::swap(cell.vertices[1], cell.vertices[3]); - std::swap(cell.vertices[4], cell.vertices[6]); - std::swap(cell.vertices[5], cell.vertices[7]); - } - else - { - for (unsigned int i = 0; i < 4; ++i) - std::swap(cell.vertices[i], cell.vertices[i + 4]); - } - copy_vertices_to_temp(cell); - - // Check whether the resulting cell is now ok. - // If not, then the grid is seriously broken and - // we just give up. - AssertThrow(GridTools::cell_measure<3>(all_vertices, vertices_lex) > - 0, - ExcInternalError()); - } - } + GridTools::invert_all_negative_measure_cells(all_vertices, cells); - // We assume that all cells of a - // grid have either positive or - // negative volumes but not both - // mixed. Although above reordering - // might work also on single cells, - // grids with both kind of cells - // are very likely to be - // broken. Check for this here. - AssertThrow(n_negative_cells == 0 || n_negative_cells == cells.size(), - ExcMessage("While sorting the cells that will be passed for " - "creating a Triangulation object, deal.II found that " - "some but not all cells have a negative volume. (If " - "all cells had a negative volume, they would simply " - "all have been inverted.) This usually happens in " - "hand-generated meshes if one accidentally uses an " - "incorrect convention for ordering the vertices in " - "one or more cells; in that case, you may want to " - "double check that you specified the vertex indices " - "in their correct order. If you are reading a mesh " - "that was created by a mesh generator, then this " - "exception indicates that some of the cells created " - "are so badly distorted that their volume becomes " - "negative; this commonly occurs at complex geometric " - "features, and you may see if the problem can be " - "fixed by playing with the parameters that control " - "mesh properties in your mesh generator, such as " - "the number of cells, the mesh density, etc.")); + if (!use_new_style_ordering) + reorder_new_to_old_style(cells); } diff --git a/source/grid/grid_tools.cc b/source/grid/grid_tools.cc index 0b7195776d..8b125a912f 100644 --- a/source/grid/grid_tools.cc +++ b/source/grid/grid_tools.cc @@ -858,6 +858,77 @@ namespace GridTools + template + void + invert_all_negative_measure_cells( + const std::vector> &all_vertices, + std::vector> & cells) + { + if (dim == 1) + return; + if (dim == 2 && spacedim == 3) + Assert(false, ExcNotImplemented()); + + std::size_t n_negative_cells = 0; + for (auto &cell : cells) + { + Assert(cell.vertices.size() == + ReferenceCells::get_hypercube().n_vertices(), + ExcNotImplemented()); + const ArrayView vertices(cell.vertices); + if (GridTools::cell_measure(all_vertices, vertices) < 0) + { + ++n_negative_cells; + + // TODO: this only works for quads and hexes + if (dim == 2) + { + // flip the cell across the y = x line in 2D + std::swap(cell.vertices[1], cell.vertices[2]); + } + else if (dim == 3) + { + // swap the front and back faces in 3D + std::swap(cell.vertices[0], cell.vertices[2]); + std::swap(cell.vertices[1], cell.vertices[3]); + std::swap(cell.vertices[4], cell.vertices[6]); + std::swap(cell.vertices[5], cell.vertices[7]); + } + + // Check whether the resulting cell is now ok. + // If not, then the grid is seriously broken and + // we just give up. + AssertThrow(GridTools::cell_measure(all_vertices, vertices) > + 0, + ExcInternalError()); + } + } + + // We assume that all cells of a grid have + // either positive or negative volumes but + // not both mixed. Although above reordering + // might work also on single cells, grids + // with both kind of cells are very likely to + // be broken. Check for this here. + AssertThrow(n_negative_cells == 0 || n_negative_cells == cells.size(), + ExcMessage( + std::string( + "This function assumes that either all cells have positive " + "volume, or that all cells have been specified in an " + "inverted vertex order so that their volume is negative. " + "(In the latter case, this class automatically inverts " + "every cell.) However, the mesh you have specified " + "appears to have both cells with positive and cells with " + "negative volume. You need to check your mesh which " + "cells these are and how they got there.\n" + "As a hint, of the total ") + + std::to_string(cells.size()) + " cells in the mesh, " + + std::to_string(n_negative_cells) + + " appear to have a negative volume.")); + } + + + // define some transformations namespace internal { diff --git a/source/grid/grid_tools.inst.in b/source/grid/grid_tools.inst.in index b972191dc9..145b5922a9 100644 --- a/source/grid/grid_tools.inst.in +++ b/source/grid/grid_tools.inst.in @@ -245,6 +245,11 @@ for (deal_II_dimension : DIMENSIONS; deal_II_space_dimension : SPACE_DIMENSIONS) std::vector &, double); + template void + invert_all_negative_measure_cells( + const std::vector> &, + std::vector> &); + template void shift( const Tensor<1, deal_II_space_dimension> &, -- 2.39.5