Detailed Description

MeshElementGrid implements a grid data structure supporting search operations and covers a given mesh. It consists of grid cells that are all of the same size. Grid cells contain pointers to intersecting mesh elements.

Attention: The user has to ensure the validity of the pointers while the MeshElementGrid instance lives.

Definition at line 24 of file MeshElementGrid.h.

#include <MeshElementGrid.h>

Collaboration diagram for MeshLib::MeshElementGrid:

[legend]

Public Member Functions
	MeshElementGrid (MeshLib::Mesh const &mesh)
template<typename POINT>
std::vector< MeshLib::Element const * >	getElementsInVolume (POINT const &min, POINT const &max) const
Eigen::Vector3d const &	getMinPoint () const
Eigen::Vector3d const &	getMaxPoint () const

Private Member Functions
void	sortElementsInGridCells (MeshLib::Mesh const &mesh)
bool	sortElementInGridCells (MeshLib::Element const &element)
std::pair< bool, std::array< std::size_t, 3 > >	getGridCellCoordinates (MathLib::Point3d const &p) const

Private Attributes
GeoLib::AABB	_aabb
std::array< double, 3 >	_step_sizes {}
std::array< double, 3 >	_inverse_step_sizes {}
std::array< std::size_t, 3 >	_n_steps
std::vector< std::vector< MeshLib::Element const * > >	_elements_in_grid_box

Constructor & Destructor Documentation

◆ MeshElementGrid()

MeshLib::MeshElementGrid::MeshElementGrid ( MeshLib::Mesh const & mesh )

explicit

Constructs a grid. Grid cells contains intersecting mesh elements.

Parameters

mesh	the MeshLib::Mesh instance the grid will be constructed from

Definition at line 17 of file MeshElementGrid.cpp.

    : _aabb{mesh.getNodes().cbegin(), mesh.getNodes().cend()},
      _n_steps({{1, 1, 1}})
{
    auto getDimensions = [](auto const& min, auto const& max)
    {
        std::bitset<3> dim;  // all bits are set to zero.
        for (std::size_t k(0); k < 3; ++k)
        {
            double const tolerance(
                std::nexttoward(max[k], std::numeric_limits<double>::max()) -
                max[k]);
            if (std::abs(max[k] - min[k]) > tolerance)
            {
                dim[k] = true;
            }
        }
        return dim;
    };
 
    auto const [min_pnt, max_pnt] = _aabb.getMinMaxPoints();
    auto const dim = getDimensions(min_pnt, max_pnt);
 
    std::array<double, 3> const delta{{max_pnt[0] - min_pnt[0],
                                       max_pnt[1] - min_pnt[1],
                                       max_pnt[2] - min_pnt[2]}};
 
    const std::size_t n_eles(mesh.getNumberOfElements());
    const std::size_t n_eles_per_cell(100);
 
    // *** condition: n_eles / n_cells < n_eles_per_cell
    //                where n_cells = _n_steps[0] * _n_steps[1] * _n_steps[2]
    // *** with _n_steps[0] =
    // ceil(pow(n_eles*delta[0]*delta[0]/(n_eles_per_cell*delta[1]*delta[2]),
    // 1/3.)));
    //          _n_steps[1] = _n_steps[0] * delta[1]/delta[0],
    //          _n_steps[2] = _n_steps[0] * delta[2]/delta[0]
    auto sc_ceil = [](double v)
    { return static_cast<std::size_t>(std::ceil(v)); };
 
    switch (dim.count())
    {
        case 3:  // 3d case
            _n_steps[0] =
                sc_ceil(std::cbrt(n_eles * delta[0] * delta[0] /
                                  (n_eles_per_cell * delta[1] * delta[2])));
            _n_steps[1] =
                sc_ceil(_n_steps[0] * std::min(delta[1] / delta[0], 100.0));
            _n_steps[2] =
                sc_ceil(_n_steps[0] * std::min(delta[2] / delta[0], 100.0));
            break;
        case 2:  // 2d cases
            if (dim[0] && dim[2])
            {  // 2d case: xz plane, y = const
                _n_steps[0] = sc_ceil(std::sqrt(n_eles * delta[0] /
                                                (n_eles_per_cell * delta[2])));
                _n_steps[2] = sc_ceil(_n_steps[0] * delta[2] / delta[0]);
            }
            else if (dim[0] && dim[1])
            {  // 2d case: xy plane, z = const
                _n_steps[0] = sc_ceil(std::sqrt(n_eles * delta[0] /
                                                (n_eles_per_cell * delta[1])));
                _n_steps[1] = sc_ceil(_n_steps[0] * delta[1] / delta[0]);
            }
            else if (dim[1] && dim[2])
            {  // 2d case: yz plane, x = const
                _n_steps[1] = sc_ceil(std::sqrt(n_eles * delta[1] /
                                                (n_eles_per_cell * delta[2])));
                _n_steps[2] =
                    sc_ceil(n_eles * delta[2] / (n_eles_per_cell * delta[1]));
            }
            break;
        case 1:  // 1d cases
            for (std::size_t k(0); k < 3; ++k)
            {
                if (dim[k])
                {
                    _n_steps[k] =
                        sc_ceil(static_cast<double>(n_eles) / n_eles_per_cell);
                }
            }
    }
 
    // some frequently used expressions to fill the vector of elements per grid
    // cell
    for (std::size_t k(0); k < 3; k++)
    {
        _step_sizes[k] = delta[k] / _n_steps[k];
        _inverse_step_sizes[k] = 1.0 / _step_sizes[k];
    }
 
    _elements_in_grid_box.resize(_n_steps[0] * _n_steps[1] * _n_steps[2]);
    sortElementsInGridCells(mesh);
}

References _aabb, _n_steps, and getNodes().

Member Function Documentation

◆ getElementsInVolume()

template<typename POINT>

std::vector< MeshLib::Element const * > MeshLib::MeshElementGrid::getElementsInVolume	(	POINT const &	min,
		POINT const &	max ) const

inline

Fill and return a vector containing elements of all grid cells that have a non-empty intersection with the box that is defined by min and max.

Parameters

min	min point of the box
max	max point of the box

Returns: a (possible empty) vector of elements

Definition at line 36 of file MeshElementGrid.h.

    {
        auto const min_coords(getGridCellCoordinates(min));
        auto const max_coords(getGridCellCoordinates(max));
 
        std::vector<MeshLib::Element const*> elements_vec;
 
        const std::size_t n_plane(_n_steps[0]*_n_steps[1]);
        for (std::size_t i(min_coords.second[0]); i<=max_coords.second[0]; i++) {
            for (std::size_t j(min_coords.second[1]); j<=max_coords.second[1]; j++) {
                for (std::size_t k(min_coords.second[2]); k<=max_coords.second[2]; k++) {
                    std::size_t idx(i+j*_n_steps[0]+k*n_plane);
                    elements_vec.insert(end(elements_vec),
                                        begin(_elements_in_grid_box[idx]),
                                        end(_elements_in_grid_box[idx]));
                }
            }
        }
        return elements_vec;
    }

References _elements_in_grid_box, _n_steps, getGridCellCoordinates(), and MeshLib::POINT.

Referenced by MeshGeoToolsLib::getCandidateElementsForLineSegmentIntersection(), getProjectedElement(), and main().

◆ getGridCellCoordinates()

std::pair< bool, std::array< std::size_t, 3 > > MeshLib::MeshElementGrid::getGridCellCoordinates ( MathLib::Point3d const & p ) const

private

Computes the grid cell coordinates for given point. The first element of the returned pair (bool) is true if the point is within the grid, else false.

Definition at line 201 of file MeshElementGrid.cpp.

{
    bool valid(true);
    std::array<std::size_t, 3> coords{};
 
    for (std::size_t k(0); k < 3; ++k)
    {
        const double d(p[k] - _aabb.getMinPoint()[k]);
        if (d < 0.0)
        {
            valid = false;
            coords[k] = 0;
        }
        else if (_aabb.getMaxPoint()[k] <= p[k])
        {
            valid = false;
            coords[k] = _n_steps[k] - 1;
        }
        else
        {
            coords[k] = static_cast<std::size_t>(d * _inverse_step_sizes[k]);
        }
    }
 
    return std::make_pair(valid, coords);
}

References _aabb, _inverse_step_sizes, and _n_steps.

Referenced by getElementsInVolume(), and sortElementInGridCells().

◆ getMaxPoint()

Eigen::Vector3d const & MeshLib::MeshElementGrid::getMaxPoint ( ) const

Returns the max point of the internal AABB. The method is a wrapper for AABB::getMaxPoint().

Definition at line 117 of file MeshElementGrid.cpp.

{
    return _aabb.getMaxPoint();
}

References _aabb.

Referenced by MeshGeoToolsLib::getCandidateElementsForLineSegmentIntersection().

◆ getMinPoint()

Eigen::Vector3d const & MeshLib::MeshElementGrid::getMinPoint ( ) const

Returns the min point of the internal AABB. The method is a wrapper for GeoLib::AABB::getMinPoint().

Definition at line 112 of file MeshElementGrid.cpp.

{
    return _aabb.getMinPoint();
}

References _aabb.

Referenced by MeshGeoToolsLib::getCandidateElementsForLineSegmentIntersection().

◆ sortElementInGridCells()

bool MeshLib::MeshElementGrid::sortElementInGridCells ( MeshLib::Element const & element )

private

Definition at line 134 of file MeshElementGrid.cpp.

{
    std::array<std::size_t, 3> min{};
    std::array<std::size_t, 3> max{};
    std::pair<bool, std::array<std::size_t, 3>> c(getGridCellCoordinates(
        *(static_cast<MathLib::Point3d const*>(element.getNode(0)))));
    if (c.first)
    {
        min = c.second;
        max = min;
    }
    else
    {
        return false;
    }
 
    for (std::size_t k(1); k < element.getNumberOfNodes(); ++k)
    {
        // compute coordinates of the grid for each node of the element
        c = getGridCellCoordinates(
            *(static_cast<MathLib::Point3d const*>(element.getNode(k))));
        if (!c.first)
        {
            return false;
        }
 
        for (std::size_t j(0); j < 3; ++j)
        {
            if (min[j] > c.second[j])
            {
                min[j] = c.second[j];
            }
            if (max[j] < c.second[j])
            {
                max[j] = c.second[j];
            }
        }
    }
 
    const std::size_t n_plane(_n_steps[0] * _n_steps[1]);
 
    // If a node of an element is almost equal to the upper right point of the
    // AABB the grid cell coordinates computed by getGridCellCoordintes() could
    // be to large (due to numerical errors). The following lines ensure that
    // the grid cell coordinates are in the valid range.
    for (std::size_t k(0); k < 3; ++k)
    {
        max[k] = std::min(_n_steps[k] - 1, max[k]);
    }
 
    // insert the element into the grid cells
    for (std::size_t i(min[0]); i <= max[0]; i++)
    {
        for (std::size_t j(min[1]); j <= max[1]; j++)
        {
            for (std::size_t k(min[2]); k <= max[2]; k++)
            {
                _elements_in_grid_box[i + j * _n_steps[0] + k * n_plane]
                    .push_back(&element);
            }
        }
    }
 
    return true;
}

References _elements_in_grid_box, _n_steps, getGridCellCoordinates(), MeshLib::Element::getNode(), and MeshLib::Element::getNumberOfNodes().

Referenced by sortElementsInGridCells().

◆ sortElementsInGridCells()

void MeshLib::MeshElementGrid::sortElementsInGridCells ( MeshLib::Mesh const & mesh )

private

Definition at line 122 of file MeshElementGrid.cpp.

{
    for (auto const element : mesh.getElements())
    {
        if (!sortElementInGridCells(*element))
        {
            OGS_FATAL("Sorting element (id={:d}) into mesh element grid.",
                      element->getID());
        }
    }
}

References MeshLib::Mesh::getElements(), OGS_FATAL, and sortElementInGridCells().

Member Data Documentation

◆ _aabb

GeoLib::AABB MeshLib::MeshElementGrid::_aabb

private

Definition at line 69 of file MeshElementGrid.h.

Referenced by MeshElementGrid(), getGridCellCoordinates(), getMaxPoint(), and getMinPoint().

◆ _elements_in_grid_box

std::vector<std::vector<MeshLib::Element const*> > MeshLib::MeshElementGrid::_elements_in_grid_box

private

Definition at line 78 of file MeshElementGrid.h.

Referenced by getElementsInVolume(), and sortElementInGridCells().

◆ _inverse_step_sizes

std::array<double,3> MeshLib::MeshElementGrid::_inverse_step_sizes {}

private

Definition at line 76 of file MeshElementGrid.h.

76{};

Referenced by getGridCellCoordinates().

◆ _n_steps

std::array<std::size_t,3> MeshLib::MeshElementGrid::_n_steps

private

Definition at line 77 of file MeshElementGrid.h.

Referenced by MeshElementGrid(), getElementsInVolume(), getGridCellCoordinates(), and sortElementInGridCells().

◆ _step_sizes

std::array<double,3> MeshLib::MeshElementGrid::_step_sizes {}

private

Definition at line 75 of file MeshElementGrid.h.

75{};

The documentation for this class was generated from the following files:

Detailed Description

Public Member Functions

Private Member Functions

Private Attributes

Constructor & Destructor Documentation

◆ MeshElementGrid()

Member Function Documentation

◆ getElementsInVolume()

◆ getGridCellCoordinates()

◆ getMaxPoint()

◆ getMinPoint()

◆ sortElementInGridCells()

◆ sortElementsInGridCells()

Member Data Documentation

◆ _aabb

◆ _elements_in_grid_box

◆ _inverse_step_sizes

◆ _n_steps

◆ _step_sizes