Slic3r::Voronoi::detail Namespace Reference

Classes
struct	Intersections

Functions
double	first_circle_segment_intersection_parameter (const Vec2d &center, const double r, const Vec2d &pt, const Vec2d &v)
Intersections	point_point_equal_distance_points (const Point &pt1, const Point &pt2, const double d)
Intersections	line_point_equal_distance_points (const Line &line, const Point &ipt, const double d)
template<typename VertexType >
bool	vertex_equal_to_point (const VertexType &vertex, const Point &ipt)
bool	vertex_equal_to_point (const VD::vertex_type *vertex, const Point &ipt)
double	dist_to_site (const Lines &lines, const VD::cell_type &cell, const Vec2d &point)
bool	on_site (const Lines &lines, const VD::cell_type &cell, const Vec2d &pt)
std::pair< Vec2d, Vec2d >	point_point_dr_dl_thresholds (const Point &pt1_site, const Point &pt2_site, const Vec2d &voronoi_point1, const Vec2d &voronoi_point2, const double threshold_tan_alpha_half)
std::pair< Vec2d, Vec2d >	point_segment_dr_dl_thresholds (const Point &pt_site, const Line &line_site, const Vec2d &voronoi_point1, const Vec2d &voronoi_point2, const double threshold_tan_alpha_half)
std::pair< Vec2d, Vec2d >	point_point_skeleton_thresholds (const Point &pt1_site, const Point &pt2_site, const Vec2d &voronoi_point1, const Vec2d &voronoi_point2, const double tan_alpha_half)
std::pair< Vec2d, Vec2d >	point_segment_skeleton_thresholds (const Point &pt_site, const Line &line_site, const Vec2d &voronoi_point1, const Vec2d &voronoi_point2, const double threshold_cos_alpha)

---

Class Documentation

Slic3r::Voronoi::detail::Intersections

struct Slic3r::Voronoi::detail::Intersections

Collaboration diagram for Slic3r::Voronoi::detail::Intersections:

Class Members
int	count
Vec2d	pts[2]

Function Documentation

dist_to_site()

double Slic3r::Voronoi::detail::dist_to_site	(	const Lines &	lines,
		const VD::cell_type &	cell,
		const Vec2d &	point
	)

    {
        const Line &line = lines[cell.source_index()];
        return cell.contains_point() ?
            (((cell.source_category() == boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT) ? line.a : line.b).cast<double>() - point).norm() :
            (Geometry::foot_pt<Vec2d>(line.a.cast<double>(), (line.b - line.a).cast<double>(), point) - point).norm();
    };

References Slic3r::Line::a, and Slic3r::Line::b.

Referenced by Slic3r::Voronoi::edge_offset_contour_intersections(), Slic3r::Voronoi::offset(), Slic3r::Voronoi::debug::verify_offset_intersection_points(), and Slic3r::Voronoi::debug::verify_signed_distances().

Here is the caller graph for this function:

first_circle_segment_intersection_parameter()

double Slic3r::Voronoi::detail::first_circle_segment_intersection_parameter	(	const Vec2d &	center,
		const double	r,
		const Vec2d &	pt,
		const Vec2d &	v
	)

  {
    const Vec2d   d = pt - center;
#ifndef NDEBUG
        // Start point should be inside, end point should be outside the circle.
        double          d0 = (pt - center).norm();
        double          d1 = (pt + v - center).norm();
        assert(d0 < r + SCALED_EPSILON);
        assert(d1 > r - SCALED_EPSILON);
#endif /* NDEBUG */
        const double  a = v.squaredNorm();
    const double  b = 2. * d.dot(v);
    const double    c = d.squaredNorm() - r * r;
    std::pair<int, std::array<double, 2>> out;
        double          u = b * b - 4. * a * c;
    assert(u > - EPSILON);
    double          t;
    if (u <= 0) {
      // Degenerate to a single closest point.
      t = - b / (2. * a);
      assert(t >= - EPSILON && t <= 1. + EPSILON);
      return std::clamp(t, 0., 1.);
    } else {
      u = sqrt(u);
      out.first = 2;
      double t0 = (- b - u) / (2. * a);
      double t1 = (- b + u) / (2. * a);
      // One of the intersections shall be found inside the segment.
      assert((t0 >= - EPSILON && t0 <= 1. + EPSILON) || (t1 >= - EPSILON && t1 <= 1. + EPSILON));
      if (t1 < 0.)
        return 0.;
      if (t0 > 1.)
        return 1.;
      return (t0 > 0.) ? t0 : t1;
    }
  }

References EPSILON, SCALED_EPSILON, and sqrt().

Referenced by Slic3r::Voronoi::edge_offset_contour_intersections().

Here is the call graph for this function:

Here is the caller graph for this function:

line_point_equal_distance_points()

Intersections Slic3r::Voronoi::detail::line_point_equal_distance_points	(	const Line &	line,
		const Point &	ipt,
		const double	d
	)

    {   
        assert(line.a != ipt && line.b != ipt);
        // Calculating two points of distance "d" to a ray and a point.
        // Point.
        Vec2d  pt   = ipt.cast<double>();
        Vec2d  lv   = (line.b - line.a).cast<double>();
        double l2   = lv.squaredNorm();
        Vec2d  lpv  = (line.a - ipt).cast<double>();
        double c    = cross2(lpv, lv);
        if (c < 0) {
            lv = - lv;
            c  = - c;
        }
 
        // Line equation (ax + by + c - d * sqrt(l2)).
        auto   a    = - lv.y();
        auto   b    = lv.x();
        // Line point shifted by -ipt is on the line.
        assert(std::abs(lpv.x() * a + lpv.y() * b + c) < SCALED_EPSILON);
        // Line vector (a, b) points towards ipt.
        assert(a * lpv.x() + b * lpv.y() < - SCALED_EPSILON);
 
#ifndef NDEBUG
        {
            // Foot point of ipt on line.
            Vec2d ft = Geometry::foot_pt(line, ipt);
            // Center point between ipt and line, its distance to both line and ipt is equal.
            Vec2d centerpt = 0.5 * (ft + pt) - pt;
            double dcenter = 0.5 * (ft - pt).norm();
            // Verify that the center point
            assert(std::abs(centerpt.x() * a + centerpt.y() * b + c - dcenter * sqrt(l2)) < SCALED_EPSILON * sqrt(l2));
        }
#endif // NDEBUG
 
        // Calculate the two intersection points.
        // With the help of Python package sympy:
        //      res = solve([a * x + b * y + c - d * sqrt(a**2 + b**2), x**2 + y**2 - d**2], [x, y])
        //      ccode(cse((res[0][0], res[0][1], res[1][0], res[1][1])))
        // where (a, b, c, d) is the line equation, not normalized (vector a,b is not normalized),
        // d is distance from the line and the point (0, 0).
        // The result is then shifted to ipt.
 
        double dscaled = d * sqrt(l2);
        double s       = c * (2. * dscaled - c);
        if (s < 0.)
            // Distance of pt from line is bigger than 2 * d.
            return Intersections { 0 };
        double u;
        int    cnt;
        // Avoid division by zero if a gets too small.
        bool   xy_swapped = std::abs(a) < std::abs(b);
        if (xy_swapped)
            std::swap(a, b);
        if (s == 0.) {
            // Distance of pt from line is 2 * d.
            cnt = 1;
            u   = 0.;
        } else {
            // Distance of pt from line is smaller than 2 * d.
            cnt = 2;
            u   = a * sqrt(s) / l2;
        }
        double e = dscaled - c;
        double f = b * e / l2;
        double g = f - u;
        double h = f + u;
        Intersections out { cnt, { Vec2d((- b * g + e) / a, g),
                                   Vec2d((- b * h + e) / a, h) } };
        if (xy_swapped) {
            std::swap(out.pts[0].x(), out.pts[0].y());
            std::swap(out.pts[1].x(), out.pts[1].y());
        }
        out.pts[0] += pt;
        out.pts[1] += pt;
 
        assert(std::abs(Geometry::ray_point_distance<Vec2d>(line.a.cast<double>(), (line.b - line.a).cast<double>(), out.pts[0]) - d) < SCALED_EPSILON);
        assert(std::abs(Geometry::ray_point_distance<Vec2d>(line.a.cast<double>(), (line.b - line.a).cast<double>(), out.pts[1]) - d) < SCALED_EPSILON);
        assert(std::abs((out.pts[0] - ipt.cast<double>()).norm() - d) < SCALED_EPSILON);
        assert(std::abs((out.pts[1] - ipt.cast<double>()).norm() - d) < SCALED_EPSILON);
        return out;
    }

References Slic3r::Line::a, Slic3r::Line::b, Slic3r::cross2(), Slic3r::f(), Slic3r::Geometry::foot_pt(), Slic3r::l2(), SCALED_EPSILON, and sqrt().

Referenced by Slic3r::Voronoi::edge_offset_contour_intersections().

Here is the call graph for this function:

Here is the caller graph for this function:

on_site()

bool Slic3r::Voronoi::detail::on_site	(	const Lines &	lines,
		const VD::cell_type &	cell,
		const Vec2d &	pt
	)

    {
        const Line &line = lines[cell.source_index()];
        auto on_contour = [&pt](const Point &ipt) { return detail::vertex_equal_to_point(pt, ipt); };
        if (cell.contains_point()) {
            return on_contour(contour_point(cell, line));
        } else {
            assert(! (on_contour(line.a) && on_contour(line.b)));
            return on_contour(line.a) || on_contour(line.b);
        }
    };

References Slic3r::Line::a, Slic3r::Line::b, Slic3r::Voronoi::contour_point(), and vertex_equal_to_point().

Referenced by Slic3r::Voronoi::annotate_inside_outside(), and Slic3r::Voronoi::debug::verify_vertices_on_contour().

Here is the call graph for this function:

Here is the caller graph for this function:

point_point_dr_dl_thresholds()

std::pair< Vec2d, Vec2d > Slic3r::Voronoi::detail::point_point_dr_dl_thresholds	(	const Point &	pt1_site,
		const Point &	pt2_site,
		const Vec2d &	voronoi_point1,
		const Vec2d &	voronoi_point2,
		const double	threshold_tan_alpha_half
	)

    {
        // sympy code to calculate +-x
        // of a linear bisector of pt1_site, pt2_site parametrized with pt + x * v, |v| = 1
        // where dr/dl = threshold_dr_dl
        // equals d|pt1_site - pt + x * v| / dx = threshold_dr_dl
        //
        // y = sqrt(x^2 + d^2)
        // dy = diff(y, x)
        // solve(dy - c, x)
        //
        // Project voronoi_point1/2 to line_site.
        Vec2d  dir_y = (pt2_site - pt1_site).cast<double>();
        Vec2d  dir_x = Vec2d(- dir_y.y(), dir_y.x()).normalized();
        Vec2d  cntr  = 0.5 * (pt1_site.cast<double>() + pt2_site.cast<double>());
        double t1 = (voronoi_point1 - cntr).dot(dir_x);
        double t2 = (voronoi_point2 - cntr).dot(dir_x);
        if (t1 > t2) {
            t1 = -t1;
            t2 = -t2;
            dir_x = - dir_x;
        }
        auto x  = 0.5 * dir_y.norm() * threshold_tan_alpha_half;
        static constexpr double nan = std::numeric_limits<double>::quiet_NaN();
        auto out = std::make_pair(Vec2d(nan, nan), Vec2d(nan, nan));
        if (t2 > -x && t1 < x) {
            // Intervals overlap.
            dir_x *= x;
            out.first  = (t1 < -x) ? cntr - dir_x : voronoi_point1;
            out.second = (t2 > +x) ? cntr + dir_x : voronoi_point2;
        }
        return out;
    }

References Slic3r::dot().

Referenced by Slic3r::Voronoi::skeleton_edges_rough().

Here is the call graph for this function:

Here is the caller graph for this function:

point_point_equal_distance_points()

Intersections Slic3r::Voronoi::detail::point_point_equal_distance_points	(	const Point &	pt1,
		const Point &	pt2,
		const double	d
	)

    {
        // Calculate the two intersection points.
        // With the help of Python package sympy:
        //      res = solve([(x - cx)**2 + (y - cy)**2 - d**2, x**2 + y**2 - d**2], [x, y])
        //      ccode(cse((res[0][0], res[0][1], res[1][0], res[1][1])))
        // where cx, cy is the center of pt1 relative to pt2,
        // d is distance from the line and the point (0, 0).
        // The result is then shifted to pt2.
        auto   cx = double(pt1.x() - pt2.x());
        auto   cy = double(pt1.y() - pt2.y());
        double cl = cx * cx + cy * cy;
        double discr = 4. * d * d - cl;
        if (discr < 0.) {
            // No intersection point found, the two circles are too far away.
            return Intersections { 0, { Vec2d(), Vec2d() } };
        }
        // Avoid division by zero if a gets too small.
        bool   xy_swapped = std::abs(cx) < std::abs(cy);
        if (xy_swapped)
            std::swap(cx, cy);
        double u;
        int    cnt;
        if (discr == 0.) {
            cnt = 1;
            u   = 0;
        } else {
            cnt = 2;
            u = 0.5 * cx * sqrt(cl * discr) / cl;
        }
        double v = 0.5 * cy - u;
        double w = 2.  * cy;
        double e = 0.5 / cx;
        double f = 0.5 * cy + u;
        Intersections out { cnt, { Vec2d(-e * (v * w - cl), v),
                                   Vec2d(-e * (w * f - cl), f) } };
        if (xy_swapped) {
            std::swap(out.pts[0].x(), out.pts[0].y());
            std::swap(out.pts[1].x(), out.pts[1].y());
        }
        out.pts[0] += pt2.cast<double>();
        out.pts[1] += pt2.cast<double>();
 
        assert(std::abs((out.pts[0] - pt1.cast<double>()).norm() - d) < SCALED_EPSILON);
        assert(std::abs((out.pts[1] - pt1.cast<double>()).norm() - d) < SCALED_EPSILON);
        assert(std::abs((out.pts[0] - pt2.cast<double>()).norm() - d) < SCALED_EPSILON);
        assert(std::abs((out.pts[1] - pt2.cast<double>()).norm() - d) < SCALED_EPSILON);
        return out;
    }

References Slic3r::f(), SCALED_EPSILON, and sqrt().

Referenced by Slic3r::Voronoi::edge_offset_contour_intersections().

Here is the call graph for this function:

Here is the caller graph for this function:

point_point_skeleton_thresholds()

std::pair< Vec2d, Vec2d > Slic3r::Voronoi::detail::point_point_skeleton_thresholds	(	const Point &	pt1_site,
		const Point &	pt2_site,
		const Vec2d &	voronoi_point1,
		const Vec2d &	voronoi_point2,
		const double	tan_alpha_half
	)

    {
        // Project voronoi_point1/2 to line_site.
        Vec2d  dir_y = (pt2_site - pt1_site).cast<double>();
        Vec2d  dir_x = Vec2d(- dir_y.y(), dir_y.x()).normalized();
        Vec2d  cntr  = 0.5 * (pt1_site.cast<double>() + pt2_site.cast<double>());
        double t1 = (voronoi_point1 - cntr).dot(dir_x);
        double t2 = (voronoi_point2 - cntr).dot(dir_x);
        if (t1 > t2) {
            t1 = -t1;
            t2 = -t2;
            dir_x = - dir_x;
        }
        auto x = 0.5 * dir_y.norm() * tan_alpha_half;
        static constexpr double nan = std::numeric_limits<double>::quiet_NaN();
        auto out = std::make_pair(Vec2d(nan, nan), Vec2d(nan, nan));
        if (t2 > -x && t1 < x) {
            // Intervals overlap.
            dir_x *= x;
            out.first  = (t1 < -x) ? cntr - dir_x : voronoi_point1;
            out.second = (t2 > +x) ? cntr + dir_x : voronoi_point2;
        }
        return out;
    }

References Slic3r::dot().

Here is the call graph for this function:

point_segment_dr_dl_thresholds()

std::pair< Vec2d, Vec2d > Slic3r::Voronoi::detail::point_segment_dr_dl_thresholds	(	const Point &	pt_site,
		const Line &	line_site,
		const Vec2d &	voronoi_point1,
		const Vec2d &	voronoi_point2,
		const double	threshold_tan_alpha_half
	)

    {
        // sympy code to calculate  +-x
        // of a parabola            y = ax^2 + b
        // where                    dr/dl = threshold_dr_dl
        //
        // a = 1 / (4 * b)
        // y = a*x**2 + b
        // dy = diff(y, x)
        // solve(dy / sqrt(1 + dy**2) - c, x)
        //
        // Foot point of the point site on the line site.
        Vec2d  ft  = Geometry::foot_pt(line_site, pt_site);
        // Minimum distance of the bisector (parabolic arc) from the two sites, squared.
        Vec2d  dir_pt_ft = pt_site.cast<double>() - ft;
        double b   = 0.5 * dir_pt_ft.norm();
        static constexpr double nan = std::numeric_limits<double>::quiet_NaN();
        auto   out = std::make_pair(Vec2d(nan, nan), Vec2d(nan, nan));
        {
            // +x, -x are the two parameters along the line_site, where threshold_tan_alpha_half is met.
            double x  = 2. * b * threshold_tan_alpha_half;
            // Project voronoi_point1/2 to line_site.
            Vec2d  dir_x = (line_site.b - line_site.a).cast<double>().normalized();
            double t1 = (voronoi_point1 - ft).dot(dir_x);
            double t2 = (voronoi_point2 - ft).dot(dir_x);
            if (t1 > t2) {
                t1 = -t1;
                t2 = -t2;
                dir_x = - dir_x;
            }
            if (t2 > -x && t1 < x) {
                // Intervals overlap.
                bool t1_valid = t1 < -x;
                bool t2_valid = t2 > +x;
                // Direction of the Y axis of the parabola.
                Vec2d dir_y(- dir_x.y(), dir_x.x());
                // Orient the Y axis towards the point site.
                if (dir_y.dot(dir_pt_ft) < 0.)
                    dir_y = - dir_y;
                // Equation of the parabola: y = b + a * x^2
                double a = 0.25 / b;
                dir_x *= x;
                dir_y *= b + a * x * x;
                out.first  = t1_valid ? ft - dir_x + dir_y : voronoi_point1;
                out.second = t2_valid ? ft + dir_x + dir_y : voronoi_point2;
            }
        }
        return out;
    }

References Slic3r::Line::a, Slic3r::Line::b, Slic3r::dot(), and Slic3r::Geometry::foot_pt().

Referenced by Slic3r::Voronoi::skeleton_edges_rough().

Here is the call graph for this function:

Here is the caller graph for this function:

point_segment_skeleton_thresholds()

std::pair< Vec2d, Vec2d > Slic3r::Voronoi::detail::point_segment_skeleton_thresholds	(	const Point &	pt_site,
		const Line &	line_site,
		const Vec2d &	voronoi_point1,
		const Vec2d &	voronoi_point2,
		const double	threshold_cos_alpha
	)

    {
        // Foot point of the point site on the line site.
        Vec2d  ft = Geometry::foot_pt(line_site, pt_site);
        // Minimum distance of the bisector (parabolic arc) from the two sites, squared.
        Vec2d  dir_pt_ft = pt_site.cast<double>() - ft;
        // Distance of Voronoi point site from the Voronoi line site.
        double l  = dir_pt_ft.norm();
        static constexpr double nan = std::numeric_limits<double>::quiet_NaN();
        auto   out = std::make_pair(Vec2d(nan, nan), Vec2d(nan, nan));
        // +x, -x are the two parameters along the line_site, where threshold is met.
        double r  = l / (1. + threshold_cos_alpha);
        double x2 = r * r - Slic3r::sqr(l - r);
        double x  = sqrt(x2);
        // Project voronoi_point1/2 to line_site.
        Vec2d  dir_x = (line_site.b - line_site.a).cast<double>().normalized();
        double t1 = (voronoi_point1 - ft).dot(dir_x);
        double t2 = (voronoi_point2 - ft).dot(dir_x);
        if (t1 > t2) {
            t1 = -t1;
            t2 = -t2;
            dir_x = - dir_x;
        }
        if (t2 > -x && t1 < x) {
            // Intervals overlap.
            bool t1_valid = t1 < -x;
            bool t2_valid = t2 > +x;
            // Direction of the Y axis of the parabola.
            Vec2d dir_y(- dir_x.y(), dir_x.x());
            // Orient the Y axis towards the point site.
            if (dir_y.dot(dir_pt_ft) < 0.)
                dir_y = - dir_y;
            // Equation of the parabola: y = b + a * x^2
            double a = 0.5 / l;
            dir_x *= x;
            dir_y *= 0.5 * l + a * x2;
            out.first  = t1_valid ? ft - dir_x + dir_y : voronoi_point1;
            out.second = t2_valid ? ft + dir_x + dir_y : voronoi_point2;
        }
        return out;
    }

References Slic3r::Line::a, Slic3r::Line::b, Slic3r::dot(), Slic3r::Geometry::foot_pt(), Slic3r::sqr(), and sqrt().

Here is the call graph for this function:

vertex_equal_to_point() [1/2]

bool Slic3r::Voronoi::detail::vertex_equal_to_point	(	const VD::vertex_type *	vertex,
		const Point &	ipt
	)

        { return vertex_equal_to_point(*vertex, ipt); }

References vertex_equal_to_point().

Here is the call graph for this function:

vertex_equal_to_point() [2/2]

template<typename VertexType >

bool Slic3r::Voronoi::detail::vertex_equal_to_point ( const VertexType &  vertex, const Point &  ipt  )

inline

    {
        // Convert ipt to doubles, force the 80bit FPU temporary to 64bit and then compare.
        // This should work with any settings of math compiler switches and the C++ compiler
        // shall understand the memcpies as type punning and it shall optimize them out.
#if 1
        using ulp_cmp_type = boost::polygon::detail::ulp_comparison<double>;
        ulp_cmp_type ulp_cmp;
        static constexpr int ULPS = boost::polygon::voronoi_diagram_traits<double>::vertex_equality_predicate_type::ULPS;
        return ulp_cmp(vertex.x(), double(ipt.x()), ULPS) == ulp_cmp_type::EQUAL &&
               ulp_cmp(vertex.y(), double(ipt.y()), ULPS) == ulp_cmp_type::EQUAL;
#else
        volatile double u = static_cast<double>(ipt.x());
        volatile double v = vertex.x();
        if (u != v)
            return false;
        u = static_cast<double>(ipt.y());
        v = vertex.y();
        return u == v;
#endif
    };

Referenced by Slic3r::Voronoi::annotate_inside_outside(), on_site(), and vertex_equal_to_point().

Here is the caller graph for this function: