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

#include <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 &cellsz, const Coord &overlap)
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)

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)
uint8_t	get_tag_for_cell (const Coord &cell, TRasterValue< Rst > v)
Coord	coord (size_t i) const
size_t	seq (const Coord &crd) const
bool	is_visited (size_t idx, Dir d=Dir::none) const
void	set_visited (size_t idx, Dir d=Dir::none)
bool	is_ambiguous (size_t idx) const
size_t	search_start_cell (size_t i=0) const
SquareTag	get_tag (size_t idx) const
Dir	next_dir (Dir prev, SquareTag tag) const
Edge	_edge (const Coord &ringvertex) const
Edge	edge (const Coord &ringvertex) const

Private Attributes
const Rst *	m_rst = nullptr
Coord	m_cellsize
Coord	m_res_1
Coord	m_window
Coord	m_gridsize
Coord	m_grid_1
std::vector< uint8_t >	m_tags

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 &  cellsz, const Coord &  overlap  )

inlineexplicit

        : m_rst{&rst}
        , m_cellsize{cellsz}
        , m_res_1{m_cellsize.r - 1, m_cellsize.c - 1}
        , m_window{overlap.r < cellsz.r ? cellsz.r - overlap.r : cellsz.r,
                   overlap.c < cellsz.c ? cellsz.c - overlap.c : cellsz.c}
        , m_gridsize{2 + (long(rows(rst)) - overlap.r) / m_window.r,
                     2 + (long(cols(rst)) - overlap.c) / m_window.c}
        , m_tags(m_gridsize.r * m_gridsize.c, 0)
    {}

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);
        uint8_t tg = m_tags[ringvertex.r];
        SquareTag t = SquareTag(tg & 0x0f);
        
        switch (t) {
        case SquareTag::a:
        case SquareTag::ab:
        case SquareTag::abc:
            return {{tl(cell), Dir::down,  m_rst}, {bl(cell)}};
        case SquareTag::b:
        case SquareTag::bc:
        case SquareTag::bcd:
            return {{bl(cell), Dir::right, m_rst}, {br(cell)}};
        case SquareTag::c:
            return {{br(cell), Dir::up,    m_rst}, {tr(cell)}};
        case SquareTag::ac:
            switch (Dir(ringvertex.c)) {
            case Dir::left:  return {{tl(cell), Dir::down, m_rst}, {bl(cell)}};
            case Dir::right: return {{br(cell), Dir::up,   m_rst}, {tr(cell)}};
            default: assert(false);
            }
        case SquareTag::d:
        case SquareTag::ad:
        case SquareTag::abd:
            return {{tr(cell), Dir::left, m_rst}, {tl(cell)}};
        case SquareTag::bd:
            switch (Dir(ringvertex.c)) {
            case Dir::down: return {{bl(cell), Dir::right, m_rst}, {br(cell)}};
            case Dir::up:   return {{tr(cell), Dir::left,  m_rst}, {tl(cell)}};
            default: assert(false);
            }
        case SquareTag::cd:
        case SquareTag::acd:
            return {{br(cell), Dir::up, m_rst}, {tr(cell)}};
        case SquareTag::full:
        case SquareTag::none: {
            Coord crd{tl(cell) + Coord{m_cellsize.r / 2, m_cellsize.c / 2}};
            return {{crd, Dir::none, m_rst}, {crd}};
        }
        }
        
        return {}; 
    }

References marchsq::__impl::a, marchsq::__impl::ab, marchsq::__impl::abc, marchsq::__impl::abd, marchsq::__impl::ac, marchsq::__impl::acd, marchsq::__impl::ad, marchsq::__impl::b, marchsq::__impl::bc, marchsq::__impl::bcd, marchsq::__impl::bd, marchsq::__impl::Grid< Rst >::bl(), marchsq::__impl::Grid< Rst >::br(), marchsq::Coord::c, marchsq::__impl::c, marchsq::__impl::cd, marchsq::__impl::Grid< Rst >::coord(), marchsq::__impl::d, marchsq::__impl::down, marchsq::__impl::full, marchsq::__impl::left, marchsq::__impl::Grid< Rst >::m_cellsize, marchsq::__impl::Grid< Rst >::m_rst, marchsq::__impl::Grid< Rst >::m_tags, marchsq::__impl::none, marchsq::Coord::r, marchsq::__impl::right, marchsq::__impl::Grid< Rst >::tl(), marchsq::__impl::Grid< Rst >::tr(), and marchsq::__impl::up.

Referenced by marchsq::__impl::Grid< Rst >::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_res_1.r, 0}; }

References marchsq::__impl::Grid< Rst >::m_res_1, marchsq::Coord::r, and marchsq::__impl::Grid< Rst >::tl().

Referenced by marchsq::__impl::Grid< Rst >::_edge(), and marchsq::__impl::Grid< Rst >::get_tag_for_cell().

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_res_1.r, m_res_1.c}; }

References marchsq::Coord::c, marchsq::__impl::Grid< Rst >::m_res_1, marchsq::Coord::r, and marchsq::__impl::Grid< Rst >::tl().

Referenced by marchsq::__impl::Grid< Rst >::_edge(), and marchsq::__impl::Grid< Rst >::get_tag_for_cell().

Here is the call graph for this function:

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 marchsq::Coord::c, long, and marchsq::__impl::Grid< Rst >::m_gridsize.

Referenced by marchsq::__impl::Grid< Rst >::_edge(), and marchsq::__impl::Grid< Rst >::scan_rings().

Here is the caller graph for this function:

edge()

template<class Rst >

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

inlineprivate

    {
        const long R = rows(*m_rst), C = cols(*m_rst);
        const long R_1 = R - 1, C_1 = C - 1;
        
        Edge e = _edge(ringvertex);
        e.to.dir = e.from.dir;
        ++e.to;
        
        e.from.crd.r = std::min(e.from.crd.r, R_1);
        e.from.crd.r = std::max(e.from.crd.r, 0l);
        e.from.crd.c = std::min(e.from.crd.c, C_1);
        e.from.crd.c = std::max(e.from.crd.c, 0l);
        
        e.to.crd.r = std::min(e.to.crd.r, R);
        e.to.crd.r = std::max(e.to.crd.r, 0l);
        e.to.crd.c = std::min(e.to.crd.c, C);
        e.to.crd.c = std::max(e.to.crd.c, 0l);
        
        return e;
    }

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

Here is the call graph for this function:

get_tag()

template<class Rst >

SquareTag marchsq::__impl::Grid< Rst >::get_tag ( size_t  idx ) const

inlineprivate

{ return SquareTag(m_tags[idx] & 0x0f); }

References marchsq::__impl::Grid< Rst >::m_tags.

Referenced by marchsq::__impl::Grid< Rst >::is_ambiguous(), marchsq::__impl::Grid< Rst >::is_visited(), and marchsq::__impl::Grid< Rst >::scan_rings().

Here is the caller graph for this function:

get_tag_for_cell()

template<class Rst >

uint8_t marchsq::__impl::Grid< Rst >::get_tag_for_cell ( const Coord &  cell, TRasterValue< Rst >  v  )

inlineprivate

    {        
        Coord sqr[] = {bl(cell), br(cell), tr(cell), tl(cell)};
        
        uint8_t t = ((is_within(sqr[0]) && isoval(*m_rst, sqr[0]) >= v)) +
                    ((is_within(sqr[1]) && isoval(*m_rst, sqr[1]) >= v) << 1) +
                    ((is_within(sqr[2]) && isoval(*m_rst, sqr[2]) >= v) << 2) +
                    ((is_within(sqr[3]) && isoval(*m_rst, sqr[3]) >= v) << 3);
        
        assert(t < 16);
        return t;
    }

References marchsq::__impl::Grid< Rst >::bl(), marchsq::__impl::Grid< Rst >::br(), marchsq::__impl::Grid< Rst >::is_within(), marchsq::__impl::isoval(), marchsq::__impl::Grid< Rst >::m_rst, marchsq::__impl::Grid< Rst >::tl(), and marchsq::__impl::Grid< Rst >::tr().

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(std::forward<ExecutionPolicy>(policy),
                 rings.begin(), rings.end(), [this, isov] (Ring &ring, size_t)
        {
            for (Coord &ringvertex : ring) {
                Edge e = edge(ringvertex);
                
                CellIt found = std::lower_bound(e.from, e.to, isov);
                ringvertex = found.crd;
            }
        });
    }

References marchsq::__impl::for_each().

Here is the call graph for this function:

is_ambiguous()

template<class Rst >

bool marchsq::__impl::Grid< Rst >::is_ambiguous ( size_t  idx ) const

inlineprivate

    {
        SquareTag t = get_tag(idx);
        return t == SquareTag::ac || t == SquareTag::bd;
    }

References marchsq::__impl::ac, marchsq::__impl::bd, and marchsq::__impl::Grid< Rst >::get_tag().

Referenced by marchsq::__impl::Grid< Rst >::search_start_cell().

Here is the call graph for this function:

Here is the caller graph for this function:

is_visited()

template<class Rst >

bool marchsq::__impl::Grid< Rst >::is_visited ( size_t  idx, Dir  d = Dir::none  ) const

inlineprivate

    {
        SquareTag t = get_tag(idx);
        uint8_t ref = d == Dir::none ? PREV_CCW[_t(t)] : uint8_t(1 << _t(d));
        return t == SquareTag::full || t == SquareTag::none ||
               ((m_tags[idx] & 0xf0) >> 4) == ref;
    }

References marchsq::__impl::_t(), marchsq::__impl::d, marchsq::__impl::full, marchsq::__impl::Grid< Rst >::get_tag(), marchsq::__impl::Grid< Rst >::m_tags, marchsq::__impl::none, and marchsq::__impl::PREV_CCW.

Referenced by marchsq::__impl::Grid< Rst >::scan_rings(), and marchsq::__impl::Grid< Rst >::search_start_cell().

Here is the call graph for this function:

Here is the caller graph for this function:

is_within()

template<class Rst >

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

inlineprivate

    {
        long R = rows(*m_rst), C = cols(*m_rst);
        return crd.r >= 0 && crd.r < R && crd.c >= 0 && crd.c < C;
    };

References marchsq::Coord::c, marchsq::__impl::cols(), marchsq::__impl::Grid< Rst >::m_rst, marchsq::Coord::r, and marchsq::__impl::rows().

Referenced by marchsq::__impl::Grid< Rst >::get_tag_for_cell().

Here is the call graph for this function:

Here is the caller graph for this function:

next_dir()

template<class Rst >

Dir marchsq::__impl::Grid< Rst >::next_dir ( Dir  prev, SquareTag  tag  ) const

inlineprivate

    {
        // Treat ambiguous cases as two separate regions in one square.
        switch (tag) {
        case SquareTag::ac:
            switch (prev) {
            case Dir::down: return Dir::right;
            case Dir::up:   return Dir::left;
            default:        assert(false); return Dir::none;
            }
        case SquareTag::bd:
            switch (prev) {
            case Dir::right: return Dir::up;
            case Dir::left:  return Dir::down;
            default:         assert(false); return Dir::none;
            }
        default:
            return NEXT_CCW[uint8_t(tag)];
        }
        
        return Dir::none;
    }

References marchsq::__impl::ac, marchsq::__impl::bd, marchsq::__impl::down, marchsq::__impl::left, marchsq::__impl::NEXT_CCW, marchsq::__impl::none, marchsq::__impl::right, and marchsq::__impl::up.

Referenced by marchsq::__impl::Grid< Rst >::scan_rings().

Here is the caller graph for this function:

rastercoord()

template<class Rst >

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

inlineprivate

    {
        return {(crd.r - 1) * m_window.r, (crd.c - 1) * m_window.c};
    }

References marchsq::Coord::c, marchsq::__impl::Grid< Rst >::m_window, and marchsq::Coord::r.

Referenced by marchsq::__impl::Grid< Rst >::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_tags.size()) {
            Ring ring;
            
            size_t idx = startidx;
            Dir prev = Dir::none, next = next_dir(prev, get_tag(idx));
            
            while (next != Dir::none && !is_visited(idx, prev)) {
                Coord ringvertex{long(idx), long(next)};
                ring.emplace_back(ringvertex);
                set_visited(idx, prev);
                
                idx  = seq(step(coord(idx), next));
                prev = next;
                next = next_dir(next, get_tag(idx));
            }
            
            // To prevent infinite loops in case of degenerate input
            if (next == Dir::none) m_tags[startidx] = _t(SquareTag::none);
            
            if (ring.size() > 1) {
                ring.pop_back();
                rings.emplace_back(ring);
            }
        }
        
        return rings;
    }

References marchsq::__impl::_t(), marchsq::__impl::Grid< Rst >::coord(), marchsq::__impl::Grid< Rst >::get_tag(), marchsq::__impl::Grid< Rst >::is_visited(), long, marchsq::__impl::Grid< Rst >::m_tags, marchsq::__impl::Grid< Rst >::next_dir(), marchsq::__impl::none, marchsq::__impl::Grid< Rst >::search_start_cell(), marchsq::__impl::Grid< Rst >::seq(), marchsq::__impl::Grid< Rst >::set_visited(), and marchsq::__impl::step().

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  i = 0 ) const

inlineprivate

    {
        // Skip ambiguous tags as starting tags due to unknown previous
        // direction.
        while ((i < m_tags.size()) && (is_visited(i) || is_ambiguous(i))) ++i;
        
        return i;
    }

References marchsq::__impl::Grid< Rst >::is_ambiguous(), marchsq::__impl::Grid< Rst >::is_visited(), and marchsq::__impl::Grid< Rst >::m_tags.

Referenced by marchsq::__impl::Grid< Rst >::scan_rings().

Here is the call graph for this function:

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 marchsq::__impl::Grid< Rst >::m_gridsize, and marchsq::Coord::seq().

Referenced by marchsq::__impl::Grid< Rst >::scan_rings().

Here is the call graph for this function:

Here is the caller graph for this function:

set_visited()

template<class Rst >

void marchsq::__impl::Grid< Rst >::set_visited ( size_t  idx, Dir  d = Dir::none  )

inlineprivate

    {
        m_tags[idx] |= (1 << (_t(d)) << 4);
    }

References marchsq::__impl::_t(), marchsq::__impl::d, and marchsq::__impl::Grid< Rst >::m_tags.

Referenced by marchsq::__impl::Grid< Rst >::scan_rings().

Here is the call graph for this function:

Here is the caller 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

    {        
        // parallel for r
        for_each (std::forward<ExecutionPolicy>(policy),
                 m_tags.begin(), m_tags.end(),
                 [this, isoval](uint8_t& tag, size_t idx) {
            tag = get_tag_for_cell(coord(idx), isoval);
        });
    }

References marchsq::__impl::for_each(), marchsq::__impl::isoval(), and marchsq::__impl::Grid< Rst >::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 marchsq::__impl::Grid< Rst >::rastercoord().

Referenced by marchsq::__impl::Grid< Rst >::_edge(), marchsq::__impl::Grid< Rst >::bl(), marchsq::__impl::Grid< Rst >::br(), marchsq::__impl::Grid< Rst >::get_tag_for_cell(), and marchsq::__impl::Grid< Rst >::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_res_1.c}; }

References marchsq::Coord::c, marchsq::__impl::Grid< Rst >::m_res_1, and marchsq::__impl::Grid< Rst >::tl().

Referenced by marchsq::__impl::Grid< Rst >::_edge(), and marchsq::__impl::Grid< Rst >::get_tag_for_cell().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

m_cellsize

template<class Rst >

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

private

Referenced by marchsq::__impl::Grid< Rst >::_edge().

m_grid_1

template<class Rst >

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

private

m_gridsize

template<class Rst >

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

private

Referenced by marchsq::__impl::Grid< Rst >::coord(), and marchsq::__impl::Grid< Rst >::seq().

m_res_1

template<class Rst >

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

private

Referenced by marchsq::__impl::Grid< Rst >::bl(), marchsq::__impl::Grid< Rst >::br(), and marchsq::__impl::Grid< Rst >::tr().

m_rst

template<class Rst >

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

private

Referenced by marchsq::__impl::Grid< Rst >::_edge(), marchsq::__impl::Grid< Rst >::edge(), marchsq::__impl::Grid< Rst >::get_tag_for_cell(), and marchsq::__impl::Grid< Rst >::is_within().

m_tags

template<class Rst >

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

private

Referenced by marchsq::__impl::Grid< Rst >::_edge(), marchsq::__impl::Grid< Rst >::get_tag(), marchsq::__impl::Grid< Rst >::is_visited(), marchsq::__impl::Grid< Rst >::scan_rings(), marchsq::__impl::Grid< Rst >::search_start_cell(), marchsq::__impl::Grid< Rst >::set_visited(), and marchsq::__impl::Grid< Rst >::tag_grid().

m_window

template<class Rst >

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

private

Referenced by marchsq::__impl::Grid< Rst >::rastercoord().

---

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

• src/libslic3r/MarchingSquares.hpp