Slic3r::Arachne::SparseGrid< ElemT > Class Template Reference

Sparse grid which can locate spatially nearby elements efficiently. More...

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Arachne/utils/SparseGrid.hpp>

Inheritance diagram for Slic3r::Arachne::SparseGrid< ElemT >:

Collaboration diagram for Slic3r::Arachne::SparseGrid< ElemT >:

Public Types
using	Elem = ElemT
using	GridPoint = SquareGrid::GridPoint
using	grid_coord_t = SquareGrid::grid_coord_t
using	GridMap = std::unordered_multimap<GridPoint, Elem, PointHash>
using	iterator = typename GridMap::iterator
using	const_iterator = typename GridMap::const_iterator

Public Member Functions
	SparseGrid (coord_t cell_size, size_t elem_reserve=0U, float max_load_factor=1.0f)
	Constructs a sparse grid with the specified cell size.
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
std::vector< Elem >	getNearby (const Point &query_pt, coord_t radius) const
	Returns all data within radius of query_pt.
bool	processNearby (const Point &query_pt, coord_t radius, const std::function< bool(const ElemT &)> &process_func) const
	Process elements from cells that might contain sought after points.
coord_t	getCellSize () const
bool	processLineCells (const std::pair< Point, Point > line, const std::function< bool(GridPoint)> &process_cell_func)
	Process cells along a line indicated by line.
bool	processLineCells (const std::pair< Point, Point > line, const std::function< bool(GridPoint)> &process_cell_func) const
	Process cells along a line indicated by line.
bool	processNearby (const Point &query_pt, coord_t radius, const std::function< bool(const GridPoint &)> &process_func) const
	Process cells that might contain sought after points.
GridPoint	toGridPoint (const Vec2i64 &point) const
	Compute the grid coordinates of a point.
grid_coord_t	toGridCoord (const int64_t &coord) const
	Compute the grid coordinate of a real space coordinate.
coord_t	toLowerCoord (const grid_coord_t &grid_coord) const
	Compute the lowest coord in a grid cell. The lowest point is the point in the grid cell closest to the origin.

Protected Member Functions
bool	processFromCell (const GridPoint &grid_pt, const std::function< bool(const Elem &)> &process_func) const
	Process elements from the cell indicated by grid_pt.
grid_coord_t	nonzeroSign (grid_coord_t z) const

Protected Attributes
GridMap	m_grid
	Map from grid locations (GridPoint) to elements (Elem).
coord_t	cell_size
	The cell (square) size.

Detailed Description

template<class ElemT>
class Slic3r::Arachne::SparseGrid< ElemT >

Sparse grid which can locate spatially nearby elements efficiently.

Note

This is an abstract template class which doesn't have any functions to insert elements.

See also

SparsePointGrid

Template Parameters

ElemT

The element type to store.

Member Typedef Documentation

const_iterator

template<class ElemT>

using Slic3r::Arachne::SparseGrid< ElemT >::const_iterator = typename GridMap::const_iterator

Elem

template<class ElemT>

using Slic3r::Arachne::SparseGrid< ElemT >::Elem = ElemT

grid_coord_t

template<class ElemT>

using Slic3r::Arachne::SparseGrid< ElemT >::grid_coord_t = SquareGrid::grid_coord_t

GridMap

template<class ElemT>

using Slic3r::Arachne::SparseGrid< ElemT >::GridMap = std::unordered_multimap<GridPoint, Elem, PointHash>

GridPoint

template<class ElemT>

using Slic3r::Arachne::SparseGrid< ElemT >::GridPoint = SquareGrid::GridPoint

iterator

template<class ElemT>

using Slic3r::Arachne::SparseGrid< ElemT >::iterator = typename GridMap::iterator

Constructor & Destructor Documentation

SparseGrid()

template<class ElemT>

Slic3r::Arachne::SparseGrid< ElemT >::SparseGrid	(	coord_t	cell_size,
		size_t	elem_reserve = 0U,
		float	max_load_factor = 1.0f )

Constructs a sparse grid with the specified cell size.

Parameters

[in]	cell_size	The size to use for a cell (square) in the grid. Typical values would be around 0.5-2x of expected query radius.
[in]	elem_reserve	Number of elements to research space for.
[in]	max_load_factor	Maximum average load factor before rehashing.

                                                                                                                 : SquareGrid(cell_size)
{
    // Must be before the reserve call.
    m_grid.max_load_factor(max_load_factor);
    if (elem_reserve != 0U)
        m_grid.reserve(elem_reserve);
}

References Slic3r::Arachne::SquareGrid::SquareGrid(), Slic3r::Arachne::SquareGrid::cell_size, and m_grid.

Referenced by Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::SparseLineGrid(), and Slic3r::Arachne::SparsePointGrid< ElemT, Locator >::SparsePointGrid().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

begin() [1/2]

template<class ElemT>

iterator Slic3r::Arachne::SparseGrid< ElemT >::begin ( )

inline

{ return m_grid.begin(); }

References m_grid.

begin() [2/2]

template<class ElemT>

const_iterator Slic3r::Arachne::SparseGrid< ElemT >::begin ( ) const

inline

{ return m_grid.begin(); }

References m_grid.

end() [1/2]

template<class ElemT>

iterator Slic3r::Arachne::SparseGrid< ElemT >::end ( )

inline

{ return m_grid.end(); }

References m_grid.

end() [2/2]

template<class ElemT>

const_iterator Slic3r::Arachne::SparseGrid< ElemT >::end ( ) const

inline

{ return m_grid.end(); }

References m_grid.

getCellSize()

coord_t SquareGrid::getCellSize ( ) const

inherited

Get the cell size this grid was created for.

{
    return cell_size;
}

References cell_size.

getNearby()

template<class ElemT>

std::vector< typename SparseGrid< ElemT >::Elem > Slic3r::Arachne::SparseGrid< ElemT >::getNearby	(	const Point &	query_pt,
		coord_t	radius ) const

Returns all data within radius of query_pt.

Finds all elements with location within radius of query_pt. May return additional elements that are beyond radius.

Average running time is a*(1 + 2 * radius / cell_size)**2 + b*cnt where a and b are proportionality constance and cnt is the number of returned items. The search will return items in an area of (2*radius + cell_size)**2 on average. The max range of an item from the query_point is radius + cell_size.

Parameters

[in]	query_pt	The point to search around.
[in]	radius	The search radius.

Returns

Vector of elements found

{
    std::vector<Elem>                       ret;
    const std::function<bool(const Elem &)> process_func = [&ret](const Elem &elem) {
        ret.push_back(elem);
        return true;
    };
    processNearby(query_pt, radius, process_func);
    return ret;
}

References processNearby().

Here is the call graph for this function:

nonzeroSign()

SquareGrid::grid_coord_t SquareGrid::nonzeroSign ( grid_coord_t z ) const

protectedinherited

Compute the sign of a number.

The number 0 will result in a positive sign (1).

Parameters

z	The number to find the sign of.

Returns

1 if the number is positive or 0, or -1 if the number is negative.

{
    return (z >= 0) - (z < 0);
}

processFromCell()

template<class ElemT>

bool Slic3r::Arachne::SparseGrid< ElemT >::processFromCell ( const GridPoint & grid_pt, const std::function< bool(const Elem &)> & process_func ) const

protected

Process elements from the cell indicated by grid_pt.

Parameters

[in]	grid_pt	The grid coordinates of the cell.
[in]	process_func	Processes each element. process_func(elem) is called for each element in the cell. Processing stops if function returns false.

Returns

Whether we need to continue processing a next cell.

{
    auto grid_range = m_grid.equal_range(grid_pt);
    for (auto iter = grid_range.first; iter != grid_range.second; ++iter)
        if (!process_func(iter->second))
            return false;
    return true;
}

References m_grid.

Referenced by processNearby().

Here is the caller graph for this function:

processLineCells() [1/2]

bool SquareGrid::processLineCells ( const std::pair< Point, Point > line, const std::function< bool(GridPoint)> & process_cell_func )

inherited

Process cells along a line indicated by line.

Parameters

line	The line along which to process cells.
process_func	Processes each cell. process_func(elem) is called for each cell. Processing stops if function returns false.

Returns

Whether we need to continue processing after this function.

{
    return static_cast<const SquareGrid*>(this)->processLineCells(line, process_cell_func);
}

References SquareGrid(), and processLineCells().

Referenced by Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::insert(), and processLineCells().

Here is the call graph for this function:

Here is the caller graph for this function:

processLineCells() [2/2]

bool SquareGrid::processLineCells ( const std::pair< Point, Point > line, const std::function< bool(GridPoint)> & process_cell_func ) const

inherited

Process cells along a line indicated by line.

Parameters

line	The line along which to process cells
process_func	Processes each cell. process_func(elem) is called for each cell. Processing stops if function returns false.

Returns

Whether we need to continue processing after this function.

{
    Point start = line.first;
    Point end = line.second;
    if (end.x() < start.x())
    { // make sure X increases between start and end
        std::swap(start, end);
    }
 
    const GridPoint start_cell = toGridPoint(start.cast<int64_t>());
    const GridPoint end_cell = toGridPoint(end.cast<int64_t>());
    const int64_t y_diff = int64_t(end.y() - start.y());
    const grid_coord_t y_dir = nonzeroSign(y_diff);
 
    /* This line drawing algorithm iterates over the range of Y coordinates, and
    for each Y coordinate computes the range of X coordinates crossed in one
    unit of Y. These ranges are rounded to be inclusive, so effectively this
    creates a "fat" line, marking more cells than a strict one-cell-wide path.*/
    grid_coord_t x_cell_start = start_cell.x();
    for (grid_coord_t cell_y = start_cell.y(); cell_y * y_dir <= end_cell.y() * y_dir; cell_y += y_dir)
    { // for all Y from start to end
        // nearest y coordinate of the cells in the next row
        const coord_t nearest_next_y = toLowerCoord(cell_y + ((nonzeroSign(cell_y) == y_dir || cell_y == 0) ? y_dir : coord_t(0)));
        grid_coord_t x_cell_end; // the X coord of the last cell to include from this row
        if (y_diff == 0)
        {
            x_cell_end = end_cell.x();
        }
        else
        {
            const int64_t area = int64_t(end.x() - start.x()) * int64_t(nearest_next_y - start.y());
            // corresponding_x: the x coordinate corresponding to nearest_next_y
            int64_t corresponding_x = int64_t(start.x()) + area / y_diff;
            x_cell_end = toGridCoord(corresponding_x + ((corresponding_x < 0) && ((area % y_diff) != 0)));
            if (x_cell_end < start_cell.x())
            { // process at least one cell!
                x_cell_end = x_cell_start;
            }
        }
 
        for (grid_coord_t cell_x = x_cell_start; cell_x <= x_cell_end; ++cell_x)
        {
            GridPoint grid_loc(cell_x, cell_y);
            if (! process_cell_func(grid_loc))
            {
                return false;
            }
            if (grid_loc == end_cell)
            {
                return true;
            }
        }
        // TODO: this causes at least a one cell overlap for each row, which
        // includes extra cells when crossing precisely on the corners
        // where positive slope where x > 0 and negative slope where x < 0
        x_cell_start = x_cell_end;
    }
    assert(false && "We should have returned already before here!");
    return false;
}

processNearby() [1/2]

template<class ElemT>

bool Slic3r::Arachne::SparseGrid< ElemT >::processNearby	(	const Point &	query_pt,
		coord_t	radius,
		const std::function< bool(const ElemT &)> &	process_func ) const

Process elements from cells that might contain sought after points.

Processes elements from cell that might have elements within radius of query_pt. Processes all elements that are within radius of query_pt. May process elements that are up to radius + cell_size from query_pt.

Parameters

[in]	query_pt	The point to search around.
[in]	radius	The search radius.
[in]	process_func	Processes each element. process_func(elem) is called for each element in the cell. Processing stops if function returns false.

Returns

Whether we need to continue processing after this function

{
    return SquareGrid::processNearby(query_pt, radius, [&process_func, this](const GridPoint &grid_pt) { return processFromCell(grid_pt, process_func); });
}

References processFromCell(), and Slic3r::Arachne::SquareGrid::processNearby().

Referenced by getNearby().

Here is the call graph for this function:

Here is the caller graph for this function:

processNearby() [2/2]

bool SquareGrid::processNearby ( const Point & query_pt, coord_t radius, const std::function< bool(const GridPoint &)> & process_func ) const

inherited

Process cells that might contain sought after points.

Processes cells that might be within a square with twice radius as width, centered around query_pt. May process elements that are up to radius + cell_size from query_pt.

Parameters

query_pt	The point to search around.
radius	The search radius.
process_func	Processes each cell. process_func(loc) is called for each cell coord within range. Processing stops if function returns false.

Returns

Whether we need to continue processing after this function.

{
    const Point min_loc(query_pt.x() - radius, query_pt.y() - radius);
    const Point max_loc(query_pt.x() + radius, query_pt.y() + radius);
 
    GridPoint min_grid = toGridPoint(min_loc.cast<int64_t>());
    GridPoint max_grid = toGridPoint(max_loc.cast<int64_t>());
 
    for (coord_t grid_y = min_grid.y(); grid_y <= max_grid.y(); ++grid_y)
    {
        for (coord_t grid_x = min_grid.x(); grid_x <= max_grid.x(); ++grid_x)
        {
            GridPoint grid_pt(grid_x,grid_y);
            if (!process_func(grid_pt))
            {
                return false;
            }
        }
    }
    return true;
}

References toGridPoint().

Referenced by Slic3r::Arachne::SparseGrid< ElemT >::processNearby().

Here is the call graph for this function:

Here is the caller graph for this function:

toGridCoord()

SquareGrid::grid_coord_t SquareGrid::toGridCoord ( const int64_t & coord ) const

inherited

Compute the grid coordinate of a real space coordinate.

Parameters

coord

The actual location.

Returns

The grid coordinate that corresponds to coord.

{
    // This mapping via truncation results in the cells with
    // GridPoint.x==0 being twice as large and similarly for
    // GridPoint.y==0.  This doesn't cause any incorrect behavior,
    // just changes the running time slightly.  The change in running
    // time from this is probably not worth doing a proper floor
    // operation.
    return coord / cell_size;
}

References cell_size.

Referenced by Slic3r::Arachne::SparseLineGrid< PolygonsPointIndex, PolygonsPointIndexSegmentLocator >::toGridCoord(), and toGridPoint().

Here is the caller graph for this function:

toGridPoint()

SquareGrid::GridPoint SquareGrid::toGridPoint ( const Vec2i64 & point ) const

inherited

Compute the grid coordinates of a point.

Parameters

point

The actual location.

Returns

The grid coordinates that correspond to point.

{
    return Point(toGridCoord(point.x()), toGridCoord(point.y()));
}

References toGridCoord().

Referenced by Slic3r::Arachne::SparsePointGrid< ElemT, Locator >::insert(), and processNearby().

Here is the call graph for this function:

Here is the caller graph for this function:

toLowerCoord()

coord_t SquareGrid::toLowerCoord ( const grid_coord_t & grid_coord ) const

inherited

Compute the lowest coord in a grid cell. The lowest point is the point in the grid cell closest to the origin.

Parameters

grid_coord

The grid coordinate.

Returns

The print space coordinate that corresponds to grid_coord.

{
    // This mapping via truncation results in the cells with
    // GridPoint.x==0 being twice as large and similarly for
    // GridPoint.y==0.  This doesn't cause any incorrect behavior,
    // just changes the running time slightly.  The change in running
    // time from this is probably not worth doing a proper floor
    // operation.
    return grid_coord * cell_size;
}

References cell_size.

Member Data Documentation

cell_size

coord_t Slic3r::Arachne::SquareGrid::cell_size

protectedinherited

The cell (square) size.

Referenced by Slic3r::Arachne::SparseGrid< ElemT >::SparseGrid(), Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::SparseLineGrid(), Slic3r::Arachne::SparsePointGrid< ElemT, Locator >::SparsePointGrid(), SquareGrid(), getCellSize(), toGridCoord(), and toLowerCoord().

m_grid

template<class ElemT>

GridMap Slic3r::Arachne::SparseGrid< ElemT >::m_grid

protected

Map from grid locations (GridPoint) to elements (Elem).

Referenced by SparseGrid(), begin(), begin(), end(), end(), Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::insert(), Slic3r::Arachne::SparsePointGrid< ElemT, Locator >::insert(), and processFromCell().

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Arachne/utils/SparseGrid.hpp