marchsq::__impl::Grid< Rst > Class Template Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MarchingSquares.hpp>

Collaboration diagram for marchsq::__impl::Grid< Rst >:

Classes
struct	CellIt
struct	Edge

Public Member Functions
	Grid (const Rst &rst, const Coord &window)
template<class ExecutionPolicy>
void	tag_grid (ExecutionPolicy &&policy, TRasterValue< Rst > isoval)
std::vector< Ring >	scan_rings ()
template<class ExecutionPolicy>
void	interpolate_rings (ExecutionPolicy &&policy, std::vector< Ring > &rings, TRasterValue< Rst > isov)
std::ostream &	streamtags (std::ostream &os)
std::ostream &	streamdirs (std::ostream &os)

Private Member Functions
Coord	rastercoord (const Coord &crd) const
Coord	bl (const Coord &crd) const
Coord	br (const Coord &crd) const
Coord	tr (const Coord &crd) const
Coord	tl (const Coord &crd) const
bool	is_within (const Coord &crd) const
uint32_t	get_tags_block32 (const size_t bidx, const TRasterValue< Rst > v) const
uint32_t	get_dirs_block8 (const size_t bidx) const
uint32_t	get_tags9 (size_t gidx) const
void	clr_dirs (const size_t gidx, const Dir d)
Dir	get_dirs (const size_t gidx) const
Coord	coord (size_t i) const
size_t	seq (const Coord &crd) const
size_t	stepidx (const size_t idx, const Dir d) const
size_t	search_start_cell (size_t gidx=0) const
Dir	next_dir (size_t idx, Dir prev=Dir::all) const
Edge	_edge (const Coord &ringvertex) const
Edge	edge (const Coord &ringvertex) const
void	interpolate_edge (Coord &ecrd, TRasterValue< Rst > isoval) const

Private Attributes
const Rst *	m_rst = nullptr
Coord	m_window
Coord	m_rastsize
Coord	m_gridsize
size_t	m_gridlen
std::vector< uint32_t >	m_tags
std::vector< uint32_t >	m_dirs

Detailed Description

template<class Rst>
class marchsq::__impl::Grid< Rst >

---

Class Documentation

marchsq::__impl::Grid::Edge

struct marchsq::__impl::Grid::Edge

template<class Rst>
struct marchsq::__impl::Grid< Rst >::Edge

Collaboration diagram for marchsq::__impl::Grid< Rst >::Edge:

Class Members
CellIt	from
CellIt	to

Constructor & Destructor Documentation

Grid()

template<class Rst>

marchsq::__impl::Grid< Rst >::Grid ( const Rst & rst, const Coord & window )

inlineexplicit

        : m_rst{&rst}
        , m_window{window}
        , m_rastsize{static_cast<long>(rows(rst)), static_cast<long>(cols(rst))}
        , m_gridsize{2 + m_rastsize.r / m_window.r, 2 + m_rastsize.c / m_window.c}
        , m_gridlen{static_cast<size_t>(m_gridsize.r * m_gridsize.c)}
        , m_tags(m_gridlen / 32 + 1, 0) // 1 bit per tag means 32 per uint32_t.
        , m_dirs(m_gridlen / 8 + 1, 0)  // 4 bits per cell means 32/4=8 per uint32_t.
    {}

References marchsq::__impl::cols(), m_dirs, m_gridlen, m_gridsize, m_rastsize, m_rst, m_tags, m_window, and marchsq::__impl::rows().

Here is the call graph for this function:

Member Function Documentation

_edge()

template<class Rst>

Edge marchsq::__impl::Grid< Rst >::_edge ( const Coord & ringvertex ) const

inlineprivate

    {
        size_t idx  = ringvertex.r;
        Coord  cell = coord(idx);
        Dir    d    = Dir(ringvertex.c);
 
        switch (d) {
        case Dir::left: return {{tl(cell), Dir::down, m_rst}, {bl(cell)}};
        case Dir::down: return {{bl(cell), Dir::right, m_rst}, {br(cell)}};
        case Dir::right: return {{br(cell), Dir::up, m_rst}, {tr(cell)}};
        case Dir::up: return {{tr(cell), Dir::left, m_rst}, {tl(cell)}};
        default: assert(false);
        }
        return {};
    }

References bl(), br(), marchsq::Coord::c, coord(), marchsq::__impl::down, marchsq::__impl::left, m_rst, marchsq::Coord::r, marchsq::__impl::right, tl(), tr(), and marchsq::__impl::up.

Referenced by edge().

Here is the call graph for this function:

Here is the caller graph for this function:

bl()

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::bl ( const Coord & crd ) const

inlineprivate

{ return tl(crd) + Coord{m_window.r, 0}; }

References m_window, and tl().

Referenced by _edge().

Here is the call graph for this function:

Here is the caller graph for this function:

br()

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::br ( const Coord & crd ) const

inlineprivate

{ return tl(crd) + Coord{m_window.r, m_window.c}; }

References m_window, and tl().

Referenced by _edge().

Here is the call graph for this function:

Here is the caller graph for this function:

clr_dirs()

template<class Rst>

void marchsq::__impl::Grid< Rst >::clr_dirs ( const size_t gidx, const Dir d )

inlineprivate

    {
        assert(gidx < m_gridlen);
        size_t i = gidx / 8;   // the dirs block index
        int    o = (gidx % 8); // the dirs block offset
 
        m_dirs[i] &= ~(static_cast<uint32_t>(d) << (o * 4));
    }

References m_dirs, and m_gridlen.

Referenced by scan_rings().

Here is the caller graph for this function:

coord()

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::coord ( size_t i ) const

inlineprivate

{ return {long(i) / m_gridsize.c, long(i) % m_gridsize.c}; }

References m_gridsize.

Referenced by _edge(), and get_tags_block32().

Here is the caller graph for this function:

edge()

template<class Rst>

Edge marchsq::__impl::Grid< Rst >::edge ( const Coord & ringvertex ) const

inlineprivate

    {
        Edge e   = _edge(ringvertex);
        e.to.dir = e.from.dir;
        ++e.to;
 
        e.from.crd.r = std::clamp(e.from.crd.r, 0l, m_rastsize.r - 1);
        e.from.crd.c = std::clamp(e.from.crd.c, 0l, m_rastsize.c - 1);
        e.to.crd.r   = std::clamp(e.to.crd.r, 0l, m_rastsize.r);
        e.to.crd.c   = std::clamp(e.to.crd.c, 0l, m_rastsize.c);
        return e;
    }

References _edge(), marchsq::Coord::c, marchsq::__impl::Grid< Rst >::CellIt::crd, marchsq::__impl::Grid< Rst >::CellIt::dir, marchsq::__impl::Grid< Rst >::Edge::from, m_rastsize, marchsq::Coord::r, and marchsq::__impl::Grid< Rst >::Edge::to.

Referenced by interpolate_edge().

Here is the call graph for this function:

Here is the caller graph for this function:

get_dirs()

template<class Rst>

Dir marchsq::__impl::Grid< Rst >::get_dirs ( const size_t gidx ) const

inlineprivate

    {
        assert(gidx < m_gridlen);
        size_t i = gidx / 8;   // the dirs block index
        int    o = (gidx % 8); // the dirs block offset
 
        return Dir((m_dirs[i] >> (o * 4)) & 0b1111);
    }

References m_dirs, and m_gridlen.

Referenced by next_dir(), and streamdirs().

Here is the caller graph for this function:

get_dirs_block8()

template<class Rst>

uint32_t marchsq::__impl::Grid< Rst >::get_dirs_block8 ( const size_t bidx ) const

inlineprivate

    {
        size_t   gidx = bidx * 8;
        uint32_t dirs = 0;
 
        // Get the next 9 top-row tags at this grid index into the bottom 16
        // bits, and the 9 bottom-row tags into the top 16 bits.
        uint32_t tags9 = get_tags9(gidx) | (get_tags9(gidx + m_gridsize.c) << 16);
        // Skip generating dirs if the tags are all 1's or all 0's.
        if ((tags9 != 0) && (tags9 != 0x01ff01ff)) {
            for (auto s = 0; s < 32; s += 4) {
                uint8_t tags = (tags9 & 0b11) | ((tags9 >> 14) & 0b1100);
                dirs |= NEXT_CCW[tags] << s;
                tags9 >>= 1;
            }
        }
        return dirs;
    }

References get_tags9(), m_gridsize, and marchsq::__impl::NEXT_CCW.

Here is the call graph for this function:

get_tags9()

template<class Rst>

uint32_t marchsq::__impl::Grid< Rst >::get_tags9 ( size_t gidx ) const

inlineprivate

    {
        uint32_t tags = 0;         // the tags value.
        size_t   i    = gidx / 32; // the tags block index
        int      o    = gidx % 32; // the tags block offset
 
        if (gidx < m_gridlen) {
            // get the next 9 tags in the row.
            tags = (m_tags[i] >> o) & 0x1ff;
            // Some of the tags are in the next tags block.
            if ((o > (32 - 9)) && ((i + 1) < m_tags.size())) {
                tags |= (m_tags[i + 1] << (32 - o)) & 0x1ff;
            }
        }
        return tags;
    }

References m_gridlen, and m_tags.

Referenced by get_dirs_block8(), and streamtags().

Here is the caller graph for this function:

get_tags_block32()

template<class Rst>

uint32_t marchsq::__impl::Grid< Rst >::get_tags_block32 ( const size_t bidx, const TRasterValue< Rst > v ) const

inlineprivate

    {
        Coord    gcrd = coord(bidx * 32);  // position in grid coordinates of the block.
        Coord    rcrd = rastercoord(gcrd); // position in raster coordinates.
        uint32_t tags = 0;
        // Set a bit for each corner that has osoval > v.
        for (uint32_t b = 1; b; b <<= 1) {
            if (is_within(rcrd) && isoval(*m_rst, rcrd) > v)
                tags |= b;
            gcrd.c += 1;
            rcrd.c += m_window.c;
            // If we hit the end of the row, start on the next row.
            if (gcrd.c >= m_gridsize.c) {
                gcrd = Coord(gcrd.r + 1, 0);
                rcrd = rastercoord(gcrd);
            }
        }
        return tags;
    }

References marchsq::Coord::c, coord(), is_within(), marchsq::__impl::isoval(), m_gridsize, m_rst, m_window, marchsq::Coord::r, and rastercoord().

Here is the call graph for this function:

interpolate_edge()

template<class Rst>

void marchsq::__impl::Grid< Rst >::interpolate_edge ( Coord & ecrd, TRasterValue< Rst > isoval ) const

inlineprivate

    {
        // The ecrd must have a grid index in r and a direction in c.
        assert((0 <= ecrd.r) && (ecrd.r < m_gridlen));
        assert((ecrd.c == long(Dir::left)) || (ecrd.c == long(Dir::down)) || (ecrd.c == long(Dir::right)) || (ecrd.c == long(Dir::up)));
        Edge e = edge(ecrd);
        ecrd   = std::lower_bound(e.from, e.to, isoval).crd;
        // Shift bottom and right side points "out" by one to account for
        // raster pixel width. Note "dir" is the direction of interpolation
        // along the cell edge, not the next move direction.
        if (e.from.dir == Dir::up)
            ecrd.r += 1;
        else if (e.from.dir == Dir::left)
            ecrd.c += 1;
    }

References marchsq::Coord::c, marchsq::__impl::Grid< Rst >::CellIt::dir, marchsq::__impl::down, edge(), marchsq::__impl::Grid< Rst >::Edge::from, marchsq::__impl::isoval(), marchsq::__impl::left, m_gridlen, marchsq::Coord::r, marchsq::__impl::right, marchsq::__impl::Grid< Rst >::Edge::to, and marchsq::__impl::up.

Here is the call graph for this function:

interpolate_rings()

template<class Rst>

template<class ExecutionPolicy>

void marchsq::__impl::Grid< Rst >::interpolate_rings ( ExecutionPolicy && policy, std::vector< Ring > & rings, TRasterValue< Rst > isov )

inline

    {
        for_each_idx(std::forward<ExecutionPolicy>(policy), rings.begin(), rings.end(), [this, isov](Ring& ring, size_t) {
            for (Coord& e : ring)
                interpolate_edge(e, isov);
        });
    }

References marchsq::__impl::for_each_idx().

Here is the call graph for this function:

is_within()

template<class Rst>

bool marchsq::__impl::Grid< Rst >::is_within ( const Coord & crd ) const

inlineprivate

{ return crd.r >= 0 && crd.r < m_rastsize.r && crd.c >= 0 && crd.c < m_rastsize.c; }

References marchsq::Coord::c, m_rastsize, and marchsq::Coord::r.

Referenced by get_tags_block32().

Here is the caller graph for this function:

next_dir()

template<class Rst>

Dir marchsq::__impl::Grid< Rst >::next_dir ( size_t idx, Dir prev = Dir::all ) const

inlineprivate

    {
        Dir next = get_dirs(idx);
 
        // Treat ambiguous cases as two separate regions in one square. If
        // there are two possible next directions, pick based on the prev
        // direction. If prev=all we are starting a new line so pick the one
        // that leads "forwards" (right or down) in the search.
        switch (next) {
        case Dir::leftright:
            // We must be coming from up, down, or starting a new line.
            assert(prev == Dir::up || prev == Dir::down || prev == Dir::all);
            return (prev == Dir::up) ? Dir::left : Dir::right;
        case Dir::updown:
            // We must be coming from left, right, or starting a new line.
            assert(prev == Dir::left || prev == Dir::right || prev == Dir::all);
            return (prev == Dir::right) ? Dir::up : Dir::down;
        default:
            // Next must be a single direction or none to stop.
            assert(next == Dir::none || next == Dir::left || next == Dir::down || next == Dir::right || next == Dir::up);
            return next;
        }
    }

References marchsq::__impl::all, marchsq::__impl::down, get_dirs(), marchsq::__impl::left, marchsq::__impl::leftright, marchsq::__impl::none, marchsq::__impl::right, marchsq::__impl::up, and marchsq::__impl::updown.

Referenced by scan_rings().

Here is the call graph for this function:

Here is the caller graph for this function:

rastercoord()

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::rastercoord ( const Coord & crd ) const

inlineprivate

    {
        // Note the -1 offset for the grid border around the raster area.
        return {(crd.r - 1) * m_window.r, (crd.c - 1) * m_window.c};
    }

References marchsq::Coord::c, m_window, and marchsq::Coord::r.

Referenced by get_tags_block32(), and tl().

Here is the caller graph for this function:

scan_rings()

template<class Rst>

std::vector< Ring > marchsq::__impl::Grid< Rst >::scan_rings ( )

inline

    {
        std::vector<Ring> rings;
        size_t            startidx = 0;
        while ((startidx = search_start_cell(startidx)) < m_gridlen) {
            Ring ring;
 
            size_t idx  = startidx;
            Dir    next = next_dir(idx);
            do {
                // We should never touch a cell with no remaining directions
                // until we get back to the start cell.
                assert(next != Dir::none);
                Coord ringvertex{long(idx), long(next)};
                ring.emplace_back(ringvertex);
                clr_dirs(idx, next);
                idx  = stepidx(idx, next);
                next = next_dir(idx, next);
                assert(idx < m_gridlen);
            } while (idx != startidx);
            // The start cell on returning should either have its directions
            // cleared or have the second ambiguous direction.
            assert(next == Dir::none || next == Dir::left || next == Dir::up);
            if (ring.size() > 1)
                rings.emplace_back(ring);
        }
        return rings;
    }

References clr_dirs(), marchsq::__impl::left, m_gridlen, next_dir(), marchsq::__impl::none, search_start_cell(), stepidx(), and marchsq::__impl::up.

Here is the call graph for this function:

search_start_cell()

template<class Rst>

size_t marchsq::__impl::Grid< Rst >::search_start_cell ( size_t gidx = 0 ) const

inlineprivate

    {
        size_t i = gidx / 8; // The dirs block index.
        int    o = gidx % 8; // The dirs block offset.
 
        // Skip cells without any unvisited edges.
        while (i < m_dirs.size()) {
            if (!m_dirs[i]) {
                // Whole block is clear, advance to the next block;
                i++;
                o = 0;
            } else {
                // Block not clear, find the next non-zero tags in the block. Note
                // all dirs before gidx are cleared, so any set bits must be in
                // block offsets >= o, not before.
                for (uint32_t m = 0b1111 << (o * 4); !(m_dirs[i] & m); m <<= 4)
                    o++;
                break;
            }
        }
        return i * 8 + o;
    }

References m_dirs.

Referenced by scan_rings().

Here is the caller graph for this function:

seq()

template<class Rst>

size_t marchsq::__impl::Grid< Rst >::seq ( const Coord & crd ) const

inlineprivate

{ return crd.seq(m_gridsize); }

References m_gridsize, and marchsq::Coord::seq().

Referenced by streamdirs(), and streamtags().

Here is the call graph for this function:

Here is the caller graph for this function:

stepidx()

template<class Rst>

size_t marchsq::__impl::Grid< Rst >::stepidx ( const size_t idx, const Dir d ) const

inlineprivate

    {
        assert(idx < m_gridlen);
        switch (d) {
        case Dir::left: return idx - 1;
        case Dir::down: return idx + m_gridsize.c;
        case Dir::right: return idx + 1;
        case Dir::up: return idx - m_gridsize.c;
        default: return idx;
        }
    }

References marchsq::__impl::down, marchsq::__impl::left, m_gridlen, m_gridsize, marchsq::__impl::right, and marchsq::__impl::up.

Referenced by scan_rings().

Here is the caller graph for this function:

streamdirs()

template<class Rst>

std::ostream & marchsq::__impl::Grid< Rst >::streamdirs ( std::ostream & os )

inline

    {
        os << "   :";
        for (auto c = 0; c < m_gridsize.c; c++)
            os << (c % 10);
        os << "\n";
        for (auto r = 0; r < m_gridsize.r; r++) {
            os << std::setw(3) << r << ":";
            for (auto c = 0; c < m_gridsize.c; c++)
                os << get_dirs(seq(Coord(r, c)));
            os << std::endl;
        }
        return os;
    }

References get_dirs(), m_gridsize, and seq().

Here is the call graph for this function:

streamtags()

template<class Rst>

std::ostream & marchsq::__impl::Grid< Rst >::streamtags ( std::ostream & os )

inline

    {
        os << "   :";
        for (auto c = 0; c < m_gridsize.c; c++)
            os << (c % 10);
        os << "\n";
        for (auto r = 0; r < m_gridsize.r; r++) {
            os << std::setw(3) << r << ":";
            for (auto c = 0; c < m_gridsize.c; c++)
                os << ((get_tags9(seq(Coord(r, c))) & 1) ? "H" : ".");
            os << "\n";
        }
        return os;
    }

References get_tags9(), m_gridsize, and seq().

Here is the call graph for this function:

tag_grid()

template<class Rst>

template<class ExecutionPolicy>

void marchsq::__impl::Grid< Rst >::tag_grid ( ExecutionPolicy && policy, TRasterValue< Rst > isoval )

inline

    {
        // Get all the tags. parallel?
        for_each_idx(std::forward<ExecutionPolicy>(policy), m_tags.begin(), m_tags.end(),
                     [this, isoval](uint32_t& tag_block, size_t bidx) { tag_block = get_tags_block32(bidx, isoval); });
        // streamtags(std::cerr);
        //  Get all the dirs. parallel?
        for_each_idx(std::forward<ExecutionPolicy>(policy), m_dirs.begin(), m_dirs.end(),
                     [this](uint32_t& dirs_block, size_t bidx) { dirs_block = get_dirs_block8(bidx); });
        // streamdirs(std::cerr);
    }

References marchsq::__impl::for_each_idx(), marchsq::__impl::isoval(), m_dirs, and m_tags.

Here is the call graph for this function:

tl()

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::tl ( const Coord & crd ) const

inlineprivate

{ return rastercoord(crd); }

References rastercoord().

Referenced by _edge(), bl(), br(), and tr().

Here is the call graph for this function:

Here is the caller graph for this function:

tr()

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::tr ( const Coord & crd ) const

inlineprivate

{ return tl(crd) + Coord{0, m_window.c}; }

References m_window, and tl().

Referenced by _edge().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

m_dirs

template<class Rst>

std::vector<uint32_t> marchsq::__impl::Grid< Rst >::m_dirs

private

Referenced by Grid(), clr_dirs(), get_dirs(), search_start_cell(), and tag_grid().

m_gridlen

template<class Rst>

size_t marchsq::__impl::Grid< Rst >::m_gridlen

private

Referenced by Grid(), clr_dirs(), get_dirs(), get_tags9(), interpolate_edge(), scan_rings(), and stepidx().

m_gridsize

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::m_gridsize

private

Referenced by Grid(), coord(), get_dirs_block8(), get_tags_block32(), seq(), stepidx(), streamdirs(), and streamtags().

m_rastsize

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::m_rastsize

private

Referenced by Grid(), edge(), and is_within().

m_rst

template<class Rst>

const Rst* marchsq::__impl::Grid< Rst >::m_rst = nullptr

private

Referenced by Grid(), _edge(), and get_tags_block32().

m_tags

template<class Rst>

std::vector<uint32_t> marchsq::__impl::Grid< Rst >::m_tags

private

Referenced by Grid(), get_tags9(), and tag_grid().

m_window

template<class Rst>

Coord marchsq::__impl::Grid< Rst >::m_window

private

Referenced by Grid(), bl(), br(), get_tags_block32(), rastercoord(), and tr().

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MarchingSquares.hpp