Slic3r::Arachne::SparseLineGrid< ElemT, Locator > Class Template Reference

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

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

Inheritance diagram for Slic3r::Arachne::SparseLineGrid< ElemT, Locator >:

Collaboration diagram for Slic3r::Arachne::SparseLineGrid< ElemT, Locator >:

Public Types
using	Elem = ElemT
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
	SparseLineGrid (coord_t cell_size, size_t elem_reserve=0U, float max_load_factor=1.0f)
	Constructs a sparse grid with the specified cell size.
void	insert (const Elem &elem)
	Inserts elem into the sparse grid.
iterator	begin ()
const_iterator	begin () const
iterator	end ()
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.
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.
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.
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 Types
using	GridPoint = typename SparseGrid<ElemT>::GridPoint

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
Locator	m_locator
	Accessor for getting locations from elements.
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 Locator>
class Slic3r::Arachne::SparseLineGrid< ElemT, Locator >

Sparse grid which can locate spatially nearby elements efficiently.

Template Parameters

ElemT	The element type to store.
Locator	The functor to get the start and end locations from ElemT. must have: std::pair<Point, Point> operator()(const ElemT &elem) const which returns the location associated with val.

Member Typedef Documentation

const_iterator

template<class ElemT>

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

inherited

Elem

template<class ElemT, class Locator>

using Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::Elem = ElemT

grid_coord_t

template<class ElemT>

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

inherited

GridMap

template<class ElemT>

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

inherited

GridPoint

template<class ElemT, class Locator>

using Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::GridPoint = typename SparseGrid<ElemT>::GridPoint

protected

iterator

template<class ElemT>

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

inherited

Constructor & Destructor Documentation

SparseLineGrid()

template<class ElemT, class Locator>

Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::SparseLineGrid	(	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.

    : SparseGrid<ElemT>(cell_size, elem_reserve, max_load_factor) {}

References Slic3r::Arachne::SparseGrid< ElemT >::SparseGrid(), and Slic3r::Arachne::SquareGrid::cell_size.

Here is the call graph for this function:

Member Function Documentation

begin() [1/2]

template<class ElemT>

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

inlineinherited

{ return m_grid.begin(); }

References m_grid.

begin() [2/2]

template<class ElemT>

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

inlineinherited

{ return m_grid.begin(); }

References m_grid.

end() [1/2]

template<class ElemT>

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

inlineinherited

{ return m_grid.end(); }

References m_grid.

end() [2/2]

template<class ElemT>

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

inlineinherited

{ 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

inherited

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:

insert()

template<class ElemT, class Locator>

void Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::insert

(

const Elem &

elem

)

Inserts elem into the sparse grid.

Parameters

[in]

elem

The element to be inserted.

{
    const std::pair<Point, Point> line = m_locator(elem);
    using GridMap                      = std::unordered_multimap<GridPoint, Elem, PointHash>;
    // below is a workaround for the fact that lambda functions cannot access private or protected members
    // first we define a lambda which works on any GridMap and then we bind it to the actual protected GridMap of the parent class
    std::function<bool(GridMap *, const GridPoint)> process_cell_func_ = [&elem](GridMap *m_grid, const GridPoint grid_loc) {
        m_grid->emplace(grid_loc, elem);
        return true;
    };
    using namespace std::placeholders; // for _1, _2, _3...
    GridMap                             *m_grid = &(this->m_grid);
    std::function<bool(const GridPoint)> process_cell_func(std::bind(process_cell_func_, m_grid, _1));
 
    SparseGrid<ElemT>::processLineCells(line, process_cell_func);
}

References Slic3r::Arachne::SparseGrid< ElemT >::m_grid, m_locator, and Slic3r::Arachne::SquareGrid::processLineCells().

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

protectedinherited

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

inherited

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

protectedinherited

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().

m_locator

template<class ElemT, class Locator>

Locator Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::m_locator

protected

Accessor for getting locations from elements.

Referenced by insert().

---

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

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