Slic3r::FillAdaptive::noncrossing Namespace Reference

Classes
struct	SweepLine
struct	Junction
struct	LevelPath

Typedefs
using	Lin = Vec2d

Functions
static void	clip_profile (std::vector< Vec2d > &f, const Lin &c, int side, double w0, double w1, double lim0, double lim1, bool cut_at_window, bool drop_past_limits)
static std::vector< Vec2d >	path_points (const LevelPath &path, const std::vector< SweepLine > &lines, double reach)
static double	polyline_length (const std::vector< Vec2d > &pts)
static std::pair< Vec2d, size_t >	point_along (const std::vector< Vec2d > &pts, double t)

Variables
static const Vec2d	family_dir [3] { Vec2d(1., 0.), Vec2d(0.5, 0.5 * sqrt(3.)), Vec2d(0.5, -0.5 * sqrt(3.)) }

---

Class Documentation

Slic3r::FillAdaptive::noncrossing::SweepLine

struct Slic3r::FillAdaptive::noncrossing::SweepLine

Collaboration diagram for Slic3r::FillAdaptive::noncrossing::SweepLine:

Class Members
Vec2d	a
Vec2d	b
int	family
vector< pair< double, int > >	junctions
Lin	lin

Slic3r::FillAdaptive::noncrossing::Junction

struct Slic3r::FillAdaptive::noncrossing::Junction

Collaboration diagram for Slic3r::FillAdaptive::noncrossing::Junction:

Class Members
vector< pair< int, int > >	bends
vector< int >	lines
Vec2d	p
vector< pair< int, int > >	pairs

Slic3r::FillAdaptive::noncrossing::LevelPath

struct Slic3r::FillAdaptive::noncrossing::LevelPath

Collaboration diagram for Slic3r::FillAdaptive::noncrossing::LevelPath:

Class Members
vector< vector< Lin > >	cuts
int	end_term { -1 }
vector< int >	junctions
vector< int >	lines
vector< pair< Lin, int > >	pushes
int	start_term { -1 }
vector< int >	turn
vector< Vec2d >	verts

Typedef Documentation

Lin

using Slic3r::FillAdaptive::noncrossing::Lin = Vec2d

Function Documentation

clip_profile()

void Slic3r::FillAdaptive::noncrossing::clip_profile ( std::vector< Vec2d > & f, const Lin & c, int side, double w0, double w1, double lim0, double lim1, bool cut_at_window, bool drop_past_limits )

static

{
    const double r0 = std::max(lim0, f.front().x()), r1 = std::min(lim1, f.back().x());
    if (r1 <= r0)
        return;
    const size_t ia = std::upper_bound(f.begin(), f.end(), r0, [](double x, const Vec2d &p) { return x < p.x(); }) - f.begin();
    const size_t ib = std::lower_bound(f.begin() + ia, f.end(), r1, [](const Vec2d &p, double x) { return p.x() < x; }) - f.begin();
    auto interpolate = [](const Vec2d &a, const Vec2d &b, double x) { return b.x() > a.x() ? a.y() + (x - a.x()) / (b.x() - a.x()) * (b.y() - a.y()) : b.y(); };
    std::vector<Vec2d> local{ Vec2d(r0, interpolate(f[ia - 1], f[ia], r0)) };
    local.insert(local.end(), f.begin() + ia, f.begin() + ib);
    local.emplace_back(r1, interpolate(f[ib - 1], f[ib], r1));
 
    const double tol    = 1.;
    auto         beyond = [&c, side, tol](const Vec2d &p) { return side * (c.x() * p.x() + c.y() - p.y()) - tol; };
    std::vector<std::pair<double, double>> stretches;
    auto add = [&stretches](double x0, double x1) {
        if (!stretches.empty() && stretches.back().second >= x0)
            stretches.back().second = x1;
        else
            stretches.emplace_back(x0, x1);
    };
    for (size_t i = 1; i < local.size(); ++i) {
        const Vec2d &p = local[i - 1], &q = local[i];
        if (q.x() <= p.x())
            continue;
        const double bp = beyond(p), bq = beyond(q);
        if (bp > 0. && bq > 0.)
            add(p.x(), q.x());
        else if (bp > 0. || bq > 0.) {
            const double x = p.x() + bp / (bp - bq) * (q.x() - p.x());
            if (bp > 0.)
                add(p.x(), x);
            else
                add(x, q.x());
        }
    }
    std::vector<std::pair<double, double>> keep;
    for (auto [x0, x1] : stretches) {
        if (x1 < w0 || x0 > w1)
            continue;
        if (drop_past_limits && ((x0 <= r0 && r0 == lim0) || (x1 >= r1 && r1 == lim1)))
            continue;
        keep.emplace_back(cut_at_window ? std::max(x0, w0) : x0, cut_at_window ? std::min(x1, w1) : x1);
    }
    if (keep.empty())
        return;
 
    auto y_local = [&](double x) {
        size_t i = 1;
        while (i + 1 < local.size() && local[i].x() < x)
            ++i;
        return interpolate(local[i - 1], local[i], x);
    };
    std::vector<Vec2d> out(f.begin(), f.begin() + ia);
    auto push = [&out, tol](double x, double y) {
        if (out.empty() || x > out.back().x() || std::abs(y - out.back().y()) > 2. * tol)
            out.emplace_back(x, y);
    };
    size_t k = 0;
    for (const Vec2d &p : local) {
        for (; k < keep.size() && keep[k].second < p.x(); ++k) {
            const auto [x0, x1] = keep[k];
            push(x0, y_local(x0));
            push(x0, c.x() * x0 + c.y());
            push(x1, c.x() * x1 + c.y());
            push(x1, y_local(x1));
        }
        if (k < keep.size() && keep[k].first <= p.x() && p.x() <= keep[k].second)
            continue;
        push(p.x(), p.y());
    }
    for (; k < keep.size(); ++k) {
        const auto [x0, x1] = keep[k];
        push(x0, y_local(x0));
        push(x0, c.x() * x0 + c.y());
        push(x1, c.x() * x1 + c.y());
        push(x1, y_local(x1));
    }
    for (size_t i = ib; i < f.size(); ++i)
        push(f[i].x(), f[i].y());
    f = std::move(out);
}

References Slic3r::f().

Referenced by path_points().

Here is the call graph for this function:

Here is the caller graph for this function:

path_points()

std::vector< Vec2d > Slic3r::FillAdaptive::noncrossing::path_points ( const LevelPath & path, const std::vector< SweepLine > & lines, double reach )

static

{
    std::vector<Vec2d> f  = path.verts;
    const int          nb = int(path.junctions.size());
    auto x_of  = [&path](int b) { return path.verts[b + 1].x(); };
    auto sharp = [&](int b) { return lines[path.lines[b]].family != 0 && lines[path.lines[b + 1]].family != 0; };
    // The run of bends turning the same way as bend b, up to the neighbouring bends turning the other way.
    auto window = [&](int b) {
        int l = b - 1, r = b + 1;
        while (l >= 0 && path.turn[l] == path.turn[b])
            --l;
        while (r < nb && path.turn[r] == path.turn[b])
            ++r;
        return std::make_pair(l >= 0 ? x_of(l) : f.front().x(), r < nb ? x_of(r) : f.back().x());
    };
    // Sharp bends between the slanted lines go last, so they win at the tip of a small triangle.
    for (int b = 0; b < nb; ++b)
        if (!sharp(b)) {
            const auto [w0, w1] = window(b);
            for (const Lin &c : path.cuts[b])
                clip_profile(f, c, path.turn[b], w0, w1, x_of(b) - reach, x_of(b) + reach, true, false);
        }
    for (int b = 0; b < nb; ++b)
        if (sharp(b))
            for (const Lin &c : path.cuts[b])
                clip_profile(f, c, path.turn[b], x_of(b), x_of(b), x_of(b) - reach, x_of(b) + reach, false, true);
    for (const auto &[c, b] : path.pushes) {
        const auto [w0, w1] = window(b);
        clip_profile(f, c, path.turn[b], w0, w1, x_of(b) - reach, x_of(b) + reach, true, true);
    }
    std::vector<Vec2d> pts;
    for (const Vec2d &p : f) {
        while (pts.size() >= 2 && std::abs(cross2(Vec2d(pts.back() - pts[pts.size() - 2]), Vec2d(p - pts.back()))) <=
                                      1e-9 * (pts.back() - pts[pts.size() - 2]).norm() * (p - pts.back()).norm())
            pts.pop_back();
        pts.push_back(p);
    }
    return pts;
}

References clip_profile(), Slic3r::cross2(), Slic3r::FillAdaptive::noncrossing::LevelPath::cuts, Slic3r::f(), Slic3r::FillAdaptive::noncrossing::LevelPath::junctions, Slic3r::FillAdaptive::noncrossing::LevelPath::lines, Slic3r::FillAdaptive::noncrossing::LevelPath::pushes, Slic3r::FillAdaptive::noncrossing::LevelPath::turn, and Slic3r::FillAdaptive::noncrossing::LevelPath::verts.

Here is the call graph for this function:

point_along()

std::pair< Vec2d, size_t > Slic3r::FillAdaptive::noncrossing::point_along ( const std::vector< Vec2d > & pts, double t )

static

{
    for (size_t i = 1; i < pts.size(); ++i) {
        const double len = (pts[i] - pts[i - 1]).norm();
        if (t <= len)
            return { pts[i - 1] + (len > 0. ? t / len : 0.) * (pts[i] - pts[i - 1]), i };
        t -= len;
    }
    return { pts.back(), pts.size() - 1 };
}

polyline_length()

double Slic3r::FillAdaptive::noncrossing::polyline_length ( const std::vector< Vec2d > & pts )

static

{
    double len = 0.;
    for (size_t i = 1; i < pts.size(); ++i)
        len += (pts[i] - pts[i - 1]).norm();
    return len;
}

Variable Documentation

family_dir

const Vec2d Slic3r::FillAdaptive::noncrossing::family_dir[3] { Vec2d(1., 0.), Vec2d(0.5, 0.5 * sqrt(3.)), Vec2d(0.5, -0.5 * sqrt(3.)) }

static

{ Vec2d(1., 0.), Vec2d(0.5, 0.5 * sqrt(3.)), Vec2d(0.5, -0.5 * sqrt(3.)) };