Slic3r::Arachne::SquareGrid Class Reference

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

Inheritance diagram for Slic3r::Arachne::SquareGrid:

Public Types
using	GridPoint = Point
using	grid_coord_t = coord_t

Public Member Functions
	SquareGrid (const coord_t cell_size)
	Constructs a grid with the specified cell size.
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
grid_coord_t	nonzeroSign (grid_coord_t z) const

Protected Attributes
coord_t	cell_size
	The cell (square) size.

Detailed Description

Helper class to calculate coordinates on a square grid, and providing some utility functions to process grids.

Doesn't contain any data, except cell size. The purpose is only to automatically generate coordinates on a grid, and automatically feed them to functions. The grid is theoretically infinite (bar integer limits).

Member Typedef Documentation

grid_coord_t

using Slic3r::Arachne::SquareGrid::grid_coord_t = coord_t

GridPoint

using Slic3r::Arachne::SquareGrid::GridPoint = Point

Constructor & Destructor Documentation

SquareGrid()

SquareGrid::SquareGrid

(

const coord_t

cell_size

)

Constructs a grid with the specified cell size.

Parameters

[in]

cell_size

The size to use for a cell (square) in the grid.

                                        : cell_size(cell_size)
{
    assert(cell_size > 0U);
}

References cell_size.

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

Here is the caller graph for this function:

Member Function Documentation

getCellSize()

coord_t SquareGrid::getCellSize

(

)

const

Get the cell size this grid was created for.

{
    return cell_size;
}

References cell_size.

nonzeroSign()

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

protected

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

processLineCells() [1/2]

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

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

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

bool SquareGrid::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.

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

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

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

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

protected

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

---

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

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