MeshLib::MeshElementGrid Class Reference

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 32 of file MeshElementGrid.h.

#include <MeshElementGrid.h>

Collaboration diagram for MeshLib::MeshElementGrid:

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 24 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);
}

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 44 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, and getGridCellCoordinates().

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 208 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, _n_steps, GeoLib::AABB::getMaxPoint(), and GeoLib::AABB::getMinPoint().

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 124 of file MeshElementGrid.cpp.

{
    return _aabb.getMaxPoint();
}

References _aabb, and GeoLib::AABB::getMaxPoint().

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 119 of file MeshElementGrid.cpp.

{
    return _aabb.getMinPoint();
}

References _aabb, and GeoLib::AABB::getMinPoint().

Referenced by MeshGeoToolsLib::getCandidateElementsForLineSegmentIntersection().

sortElementInGridCells()

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

private

Definition at line 141 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 129 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 77 of file MeshElementGrid.h.

Referenced by 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 86 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 84 of file MeshElementGrid.h.

{};

Referenced by getGridCellCoordinates().

_n_steps

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

private

Definition at line 85 of file MeshElementGrid.h.

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

_step_sizes

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

private

Definition at line 83 of file MeshElementGrid.h.

{};

---

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

• MeshLib/MeshSearch/MeshElementGrid.h
• MeshLib/MeshSearch/MeshElementGrid.cpp