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

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

#include <src/libslic3r/Arachne/utils/SparsePointGrid.hpp>

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

Collaboration diagram for Slic3r::Arachne::SparsePointGrid< 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
	SparsePointGrid (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.
const ElemT *	getAnyNearby (const Point &query_pt, coord_t radius)
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::SparsePointGrid< 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 location from ElemT. Locator must have: 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::SparsePointGrid< 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::SparsePointGrid< 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

SparsePointGrid()

template<class ElemT , class Locator >

Slic3r::Arachne::SparsePointGrid< ElemT, Locator >::SparsePointGrid	(	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) {}

Member Function Documentation

begin() [1/2]

template<class ElemT >

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

inlineinherited

{ return m_grid.begin(); }

References Slic3r::Arachne::SparseGrid< ElemT >::m_grid.

begin() [2/2]

template<class ElemT >

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

inlineinherited

{ return m_grid.begin(); }

References Slic3r::Arachne::SparseGrid< ElemT >::m_grid.

end() [1/2]

template<class ElemT >

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

inlineinherited

{ return m_grid.end(); }

References Slic3r::Arachne::SparseGrid< ElemT >::m_grid.

end() [2/2]

template<class ElemT >

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

inlineinherited

{ return m_grid.end(); }

References Slic3r::Arachne::SparseGrid< ElemT >::m_grid.

getAnyNearby()

template<class ElemT , class Locator >

const ElemT * Slic3r::Arachne::SparsePointGrid< ElemT, Locator >::getAnyNearby	(	const Point &	query_pt,
		coord_t	radius
	)

Get just any element that's within a certain radius of a point.

Rather than giving a vector of nearby elements, this function just gives a single element, any element, in no particular order.

Parameters

query_pt	The point to query for an object nearby.
radius	The radius of what is considered "nearby".

{
    const ElemT                              *ret          = nullptr;
    const std::function<bool(const ElemT &)> &process_func = [&ret, query_pt, radius, this](const ElemT &maybe_nearby) {
        if (shorter_then(m_locator(maybe_nearby) - query_pt, radius)) {
            ret = &maybe_nearby;
            return false;
        }
        return true;
    };
    SparseGrid<ElemT>::processNearby(query_pt, radius, process_func);
 
    return ret;
}

References Slic3r::Arachne::SparseGrid< ElemT >::processNearby(), and Slic3r::shorter_then().

Here is the call graph for this function:

getCellSize()

coord_t SquareGrid::getCellSize ( ) const

inherited

Get the cell size this grid was created for.

{
    return cell_size;
}

References Slic3r::Arachne::SquareGrid::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;
}

insert()

template<class ElemT , class Locator >

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

(

const Elem &

elem

)

Inserts elem into the sparse grid.

Parameters

[in]

elem

The element to be inserted.

{
    Point     loc      = m_locator(elem);
    GridPoint grid_loc = SparseGrid<ElemT>::toGridPoint(loc.template cast<int64_t>());
 
    SparseGrid<ElemT>::m_grid.emplace(grid_loc, elem);
}

References Slic3r::Arachne::SquareGrid::toGridPoint().

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

Referenced by Slic3r::Arachne::SquareGrid::processLineCells().

Here is the caller graph for this function:

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

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 Slic3r::Arachne::SquareGrid::processLineCells().

Referenced by Slic3r::Arachne::SparseLineGrid< ElemT, Locator >::insert(), and Slic3r::Arachne::SquareGrid::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;
}

References Slic3r::area(), Slic3r::Arachne::SquareGrid::nonzeroSign(), Slic3r::Arachne::SquareGrid::toGridCoord(), Slic3r::Arachne::SquareGrid::toGridPoint(), and Slic3r::Arachne::SquareGrid::toLowerCoord().

Here is the call graph for this function:

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 Slic3r::Arachne::SquareGrid::processNearby().

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

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 Slic3r::Arachne::SquareGrid::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 Slic3r::Arachne::SquareGrid::cell_size.

Referenced by Slic3r::Arachne::SquareGrid::processLineCells(), and Slic3r::Arachne::SquareGrid::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 Slic3r::Arachne::SquareGrid::toGridCoord().

Referenced by Slic3r::Arachne::SparsePointGrid< ElemT, Locator >::insert(), Slic3r::Arachne::SquareGrid::processLineCells(), and Slic3r::Arachne::SquareGrid::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 Slic3r::Arachne::SquareGrid::cell_size.

Referenced by Slic3r::Arachne::SquareGrid::processLineCells().

Here is the caller graph for this function:

Member Data Documentation

cell_size

coord_t Slic3r::Arachne::SquareGrid::cell_size

protectedinherited

The cell (square) size.

Referenced by Slic3r::Arachne::SquareGrid::SquareGrid(), Slic3r::Arachne::SquareGrid::getCellSize(), Slic3r::Arachne::SquareGrid::toGridCoord(), and Slic3r::Arachne::SquareGrid::toLowerCoord().

m_grid

template<class ElemT >

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

protectedinherited

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

Referenced by Slic3r::Arachne::SparseGrid< ElemT >::SparseGrid(), Slic3r::Arachne::SparseGrid< ElemT >::begin(), Slic3r::Arachne::SparseGrid< ElemT >::begin(), Slic3r::Arachne::SparseGrid< ElemT >::end(), and Slic3r::Arachne::SparseGrid< ElemT >::end().

m_locator

template<class ElemT , class Locator >

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

protected

Accessor for getting locations from elements.

---

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

• src/libslic3r/Arachne/utils/SparsePointGrid.hpp