Slic3r::Geometry Namespace Reference

Namespaces
namespace	ArcWelder
namespace	BicubicInternal
namespace	rotcalip
namespace	impl

Classes
class	ArrangeItem
class	ArrangeItemIndex
class	Transformation
struct	TransformationSVD
struct	CubicKernelWrapper
struct	CircleSq
struct	Circle
struct	PolynomialCurve
struct	PiecewiseFittedCurve
class	Lines2VDSegments
class	MedialAxis
class	VoronoiDiagram
struct	SegmentCellRange
struct	PointCellRange
class	VoronoiUtils
struct	ParabolicSegment
class	VoronoiUtilsCgal

Typedefs
template<typename NumberType>
using	LinearKernel = CubicKernelWrapper<BicubicInternal::LinearKernel<NumberType>>
template<typename NumberType>
using	CubicCatmulRomKernel = CubicKernelWrapper<BicubicInternal::CubicCatmulRomKernel<NumberType>>
template<typename NumberType>
using	CubicBSplineKernel = CubicKernelWrapper<BicubicInternal::CubicBSplineKernel<NumberType>>
using	Circlef = Circle<Vec2f>
using	Circled = Circle<Vec2d>
using	VD = VoronoiDiagram
using	PolygonsSegmentIndexConstIt = std::vector<Arachne::PolygonsSegmentIndex>::const_iterator
using	LinesIt = Lines::iterator
using	ColoredLinesConstIt = ColoredLines::const_iterator
using	ColoredLinesIt = ColoredLines::iterator
using	ParabolicTangentToSegmentOrientation = impl::ParabolicTangentToSegmentOrientationPredicateFiltered
using	ParabolicTangentToParabolicTangentOrientation = impl::ParabolicTangentToParabolicTangentOrientationPredicateFiltered
using	CGAL_Point = impl::K::Point_2

Enumerations
enum	Orientation { ORIENTATION_CCW = 1 , ORIENTATION_CW = -1 , ORIENTATION_COLINEAR = 0 }

Functions
bool	directions_parallel (double angle1, double angle2, double max_diff)
bool	directions_perpendicular (double angle1, double angle2, double max_diff)
template<class T>
bool	contains (const std::vector< T > &vector, const Point &point)
template bool	contains (const ExPolygons &vector, const Point &point)
double	rad2deg_dir (double angle)
void	simplify_polygons (const Polygons &polygons, double tolerance, Polygons *retval)
double	linint (double value, double oldmin, double oldmax, double newmin, double newmax)
bool	arrange (size_t total_parts, const Vec2d &part_size, coordf_t dist, const BoundingBoxf *bb, Pointfs &positions)
template<typename T>
T	dist (const boost::polygon::point_data< T > &p1, const boost::polygon::point_data< T > &p2)
template<typename segment_type, typename point_type>
point_type	project_point_to_segment (segment_type &seg, point_type &px)
void	assemble_transform (Transform3d &transform, const Vec3d &translation, const Vec3d &rotation, const Vec3d &scale, const Vec3d &mirror)
Transform3d	assemble_transform (const Vec3d &translation, const Vec3d &rotation, const Vec3d &scale, const Vec3d &mirror)
void	assemble_transform (Transform3d &transform, const Transform3d &translation, const Transform3d &rotation, const Transform3d &scale, const Transform3d &mirror)
Transform3d	assemble_transform (const Transform3d &translation, const Transform3d &rotation, const Transform3d &scale, const Transform3d &mirror)
void	translation_transform (Transform3d &transform, const Vec3d &translation)
Transform3d	translation_transform (const Vec3d &translation)
void	rotation_transform (Transform3d &transform, const Vec3d &rotation)
Transform3d	rotation_transform (const Vec3d &rotation)
void	scale_transform (Transform3d &transform, double scale)
void	scale_transform (Transform3d &transform, const Vec3d &scale)
Transform3d	scale_transform (double scale)
Transform3d	scale_transform (const Vec3d &scale)
Vec3d	extract_euler_angles (const Eigen::Matrix< double, 3, 3, Eigen::DontAlign > &rotation_matrix)
Vec3d	extract_euler_angles (const Transform3d &transform)
void	rotation_from_two_vectors (Vec3d from, Vec3d to, Vec3d &rotation_axis, double &phi, Matrix3d *rotation_matrix)
static std::pair< Transform3d, Transform3d >	extract_rotation_scale (const Transform3d &trafo)
static Transform3d	extract_rotation_matrix (const Transform3d &trafo)
static Transform3d	extract_scale (const Transform3d &trafo)
static bool	contains_skew (const Transform3d &trafo)
Transform3d	transform3d_from_string (const std::string &transform_str)
Eigen::Quaterniond	rotation_xyz_diff (const Vec3d &rot_xyz_from, const Vec3d &rot_xyz_to)
double	rotation_diff_z (const Vec3d &rot_xyz_from, const Vec3d &rot_xyz_to)
Transformation	mat_around_a_point_rotate (const Transformation &InMat, const Vec3d &pt, const Vec3d &axis, float rotate_theta_radian)
Transformation	generate_transform (const Vec3d &x_dir, const Vec3d &y_dir, const Vec3d &z_dir, const Vec3d &origin)
bool	is_point_inside_polygon_corner (const Point &a, const Point &b, const Point &c, const Point &query_point)
static Orientation	orient (const Point &a, const Point &b, const Point &c)
static bool	is_ccw (const Polygon &poly)
bool	ray_ray_intersection (const Vec2d &p1, const Vec2d &v1, const Vec2d &p2, const Vec2d &v2, Vec2d &res)
bool	segment_segment_intersection (const Vec2d &p1, const Vec2d &v1, const Vec2d &p2, const Vec2d &v2, Vec2d &res)
bool	segments_intersect (const Slic3r::Point &ip1, const Slic3r::Point &ip2, const Slic3r::Point &jp1, const Slic3r::Point &jp2)
template<typename T>
T	foot_pt (const T &line_pt, const T &line_dir, const T &pt)
Vec2d	foot_pt (const Line &iline, const Point &ipt)
template<typename T>
auto	ray_point_distance_squared (const T &ray_pt, const T &ray_dir, const T &pt)
template<typename T>
auto	ray_point_distance (const T &ray_pt, const T &ray_dir, const T &pt)
double	ray_point_distance_squared (const Line &iline, const Point &ipt)
double	ray_point_distance (const Line &iline, const Point &ipt)
template<typename T>
bool	liang_barsky_line_clipping_interval (const Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &x0, const Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &v, const BoundingBoxBase< Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > &bbox, std::pair< double, double > &out_interval)
template<typename T>
bool	liang_barsky_line_clipping (Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &x0, Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &x1, const BoundingBoxBase< Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > &bbox)
template<typename T>
bool	liang_barsky_line_clipping (const Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &x0src, const Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &x1src, const BoundingBoxBase< Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > &bbox, Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &x0clip, Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &x1clip)
template<typename T>
T	rad2deg (T angle)
template<typename T>
constexpr T	deg2rad (const T angle)
template<typename T>
T	angle_to_0_2PI (T angle)
template<typename T>
void	to_range_pi_pi (T &angle)
bool	is_rotation_ninety_degrees (double a)
bool	is_rotation_ninety_degrees (const Vec3d &rotation)
template<typename KernelWrapper>
static KernelWrapper::FloatType	cubic_interpolate (const Eigen::ArrayBase< typename KernelWrapper::FloatType > &F, const typename KernelWrapper::FloatType pt)
template<typename Kernel, typename Derived>
static float	bicubic_interpolate (const Eigen::MatrixBase< Derived > &F, const Eigen::Matrix< typename Kernel::FloatType, 2, 1, Eigen::DontAlign > &pt)
Point	circle_center_taubin_newton (const Points::const_iterator &input_start, const Points::const_iterator &input_end, size_t cycles=20)
	Find the center of the circle corresponding to the vector of Points as an arc.
Vec2d	circle_center_taubin_newton (const Vec2ds::const_iterator &input_begin, const Vec2ds::const_iterator &input_end, size_t cycles)
	Adapted from work in "Circular and Linear Regression: Fitting circles and lines by least squares", pg 126 Returns a point corresponding to the center of a circle for which all of the points from input_begin to input_end lie on.
Circled	circle_taubin_newton (const Vec2ds &input, size_t cycles)
Circled	circle_ransac (const Vec2ds &input, size_t iterations, double *min_error)
template<typename Vector>
Vector	circle_center (const Vector &a, const Vector &bsrc, const Vector &csrc, typename Vector::Scalar epsilon)
Point	circle_center_taubin_newton (const Points &input, size_t cycles=20)
Vec2d	circle_center_taubin_newton (const Vec2ds &input, size_t cycles=20)
template<typename Vector, typename Points>
CircleSq< Vector >	smallest_enclosing_circle2_welzl (const Points &points, const typename Vector::Scalar epsilon)
template<typename Vector, typename Points>
Circle< Vector >	smallest_enclosing_circle_welzl (const Points &points, const typename Vector::Scalar epsilon)
Circled	smallest_enclosing_circle_welzl (const Points &points)
template<typename T>
int	ray_circle_intersections_r2_lv2_c (T r2, T a, T b, T lv2, T c, std::pair< Eigen::Matrix< T, 2, 1, Eigen::DontAlign >, Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > &out)
template<typename T>
int	ray_circle_intersections (T r, T a, T b, T c, std::pair< Eigen::Matrix< T, 2, 1, Eigen::DontAlign >, Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > &out)
Polygon	convex_hull (Points pts)
Pointf3s	convex_hull (Pointf3s points)
Polygon	convex_hull (const Polygons &polygons)
Polygon	convex_hull (const ExPolygons &expolygons)
Polygon	convex_hulll (const Polylines &polylines)
bool	convex_polygons_intersect (const Polygon &A, const Polygon &B)
std::pair< std::vector< Vec2d >, std::vector< Vec2d > >	decompose_convex_polygon_top_bottom (const std::vector< Vec2d > &src)
bool	inside_convex_polygon (const std::pair< std::vector< Vec2d >, std::vector< Vec2d > > &top_bottom_decomposition, const Vec2d &pt)
template<int Dimension, typename NumberType>
PolynomialCurve< Dimension, NumberType >	fit_polynomial (const std::vector< Vec< Dimension, NumberType > > &observations, const std::vector< NumberType > &observation_points, const std::vector< NumberType > &weights, size_t order)
template<typename Kernel, int Dimension, typename NumberType>
PiecewiseFittedCurve< Dimension, NumberType, Kernel >	fit_curve (const std::vector< Vec< Dimension, NumberType > > &observations, const std::vector< NumberType > &observation_points, const std::vector< NumberType > &weights, size_t segments_count, size_t endpoints_level_of_freedom)
template<int Dimension, typename NumberType>
PiecewiseFittedCurve< Dimension, NumberType, LinearKernel< NumberType > >	fit_linear_spline (const std::vector< Vec< Dimension, NumberType > > &observations, std::vector< NumberType > observation_points, std::vector< NumberType > weights, size_t segments_count, size_t endpoints_level_of_freedom=0)
template<int Dimension, typename NumberType>
PiecewiseFittedCurve< Dimension, NumberType, CubicBSplineKernel< NumberType > >	fit_cubic_bspline (const std::vector< Vec< Dimension, NumberType > > &observations, std::vector< NumberType > observation_points, std::vector< NumberType > weights, size_t segments_count, size_t endpoints_level_of_freedom=0)
template<int Dimension, typename NumberType>
PiecewiseFittedCurve< Dimension, NumberType, CubicCatmulRomKernel< NumberType > >	fit_catmul_rom_spline (const std::vector< Vec< Dimension, NumberType > > &observations, std::vector< NumberType > observation_points, std::vector< NumberType > weights, size_t segments_count, size_t endpoints_level_of_freedom=0)
template<typename VD, typename SEGMENTS>
const VD::point_type	retrieve_cell_point (const typename VD::cell_type &cell, const SEGMENTS &segments)
template<typename VD, typename SEGMENTS>
std::pair< typename VD::coord_type, typename VD::coord_type >	measure_edge_thickness (const VD &vd, const typename VD::edge_type &edge, const SEGMENTS &segments)
VD::vertex_type::color_type	encode_input_segment_endpoint (const VD::cell_type::source_index_type cell_source_index, const boost::polygon::direction_1d dir)
template<typename SegmentIterator>
boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, typenameboost::polygon::segment_point_type< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type	decode_input_segment_endpoint (const VD::vertex_type::color_type color, const SegmentIterator segment_begin, const SegmentIterator segment_end)
CGAL_Point	to_cgal_point (const VD::vertex_type *pt)
CGAL_Point	to_cgal_point (const Point &pt)
CGAL_Point	to_cgal_point (const Vec2d &pt)
Linef	make_linef (const VD::edge_type &edge)
bool	is_equal (const VD::vertex_type &vertex_first, const VD::vertex_type &vertex_second)
template<typename SegmentIterator>
static boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, ParabolicSegment >::type	get_parabolic_segment (const VD::edge_type &edge, const SegmentIterator segment_begin, const SegmentIterator segment_end)
template<typename SegmentIterator>
static boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, CGAL::Orientation >::type	orientation_of_two_edges (const VD::edge_type &edge_a, const VD::edge_type &edge_b, const SegmentIterator segment_begin, const SegmentIterator segment_end)
template<typename SegmentIterator>
static boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, bool >::type	check_if_three_edges_are_ccw (const VD::edge_type &edge_first, const VD::edge_type &edge_second, const VD::edge_type &edge_third, const SegmentIterator segment_begin, const SegmentIterator segment_end)

---

Class Documentation

Slic3r::Geometry::ArrangeItem

class Slic3r::Geometry::ArrangeItem

Class Members
coordf_t	dist
size_t	index_x
size_t	index_y
Vec2d	pos = Vec2d::Zero()

Slic3r::Geometry::ParabolicSegment

struct Slic3r::Geometry::ParabolicSegment

Collaboration diagram for Slic3r::Geometry::ParabolicSegment:

Class Members
const Line	directrix
const Point	focus
const Orientation	is_focus_on_left
const Linef	segment

Typedef Documentation

CGAL_Point

using Slic3r::Geometry::CGAL_Point = impl::K::Point_2

Circled

using Slic3r::Geometry::Circled = Circle<Vec2d>

Circlef

using Slic3r::Geometry::Circlef = Circle<Vec2f>

ColoredLinesConstIt

using Slic3r::Geometry::ColoredLinesConstIt = ColoredLines::const_iterator

ColoredLinesIt

using Slic3r::Geometry::ColoredLinesIt = ColoredLines::iterator

CubicBSplineKernel

template<typename NumberType>

using Slic3r::Geometry::CubicBSplineKernel = CubicKernelWrapper<BicubicInternal::CubicBSplineKernel<NumberType>>

CubicCatmulRomKernel

template<typename NumberType>

using Slic3r::Geometry::CubicCatmulRomKernel = CubicKernelWrapper<BicubicInternal::CubicCatmulRomKernel<NumberType>>

LinearKernel

template<typename NumberType>

using Slic3r::Geometry::LinearKernel = CubicKernelWrapper<BicubicInternal::LinearKernel<NumberType>>

LinesIt

using Slic3r::Geometry::LinesIt = Lines::iterator

ParabolicTangentToParabolicTangentOrientation

using Slic3r::Geometry::ParabolicTangentToParabolicTangentOrientation = impl::ParabolicTangentToParabolicTangentOrientationPredicateFiltered

ParabolicTangentToSegmentOrientation

using Slic3r::Geometry::ParabolicTangentToSegmentOrientation = impl::ParabolicTangentToSegmentOrientationPredicateFiltered

PolygonsSegmentIndexConstIt

typedef std::vector< Arachne::PolygonsSegmentIndex >::const_iterator Slic3r::Geometry::PolygonsSegmentIndexConstIt = std::vector<Arachne::PolygonsSegmentIndex>::const_iterator

VD

using Slic3r::Geometry::VD = VoronoiDiagram

Enumeration Type Documentation

Orientation

enum Slic3r::Geometry::Orientation

Enumerator
ORIENTATION_CCW
ORIENTATION_CW
ORIENTATION_COLINEAR

{
    ORIENTATION_CCW = 1,
    ORIENTATION_CW = -1,
    ORIENTATION_COLINEAR = 0
};

Function Documentation

angle_to_0_2PI()

template<typename T>

T Slic3r::Geometry::angle_to_0_2PI

(

T

angle

)

{
    static const T TWO_PI = T(2) * T(PI);
    while (angle < T(0))
    {
        angle += TWO_PI;
    }
    while (TWO_PI < angle)
    {
        angle -= TWO_PI;
    }
 
    return angle;
}

References Slic3r::angle(), and PI.

Referenced by Slic3r::Geometry::Transformation::set_rotation().

Here is the call graph for this function:

Here is the caller graph for this function:

arrange()

bool Slic3r::Geometry::arrange	(	size_t	total_parts,
		const Vec2d &	part_size,
		coordf_t	dist,
		const BoundingBoxf *	bb,
		Pointfs &	positions )

{
    positions.clear();
 
    Vec2d part = part_size;
 
    // use actual part size (the largest) plus separation distance (half on each side) in spacing algorithm
    part(0) += dist;
    part(1) += dist;
    
    Vec2d area(Vec2d::Zero());
    if (bb != NULL && bb->defined) {
        area = bb->size();
    } else {
        // bogus area size, large enough not to trigger the error below
        area(0) = part(0) * total_parts;
        area(1) = part(1) * total_parts;
    }
    
    // this is how many cells we have available into which to put parts
    size_t cellw = floor((area(0) + dist) / part(0));
    size_t cellh = floor((area(1) + dist) / part(1));
    if (total_parts > (cellw * cellh))
        return false;
    
    // total space used by cells
    Vec2d cells(cellw * part(0), cellh * part(1));
    
    // bounding box of total space used by cells
    BoundingBoxf cells_bb;
    cells_bb.merge(Vec2d(0,0)); // min
    cells_bb.merge(cells);  // max
    
    // center bounding box to area
    cells_bb.translate(
        (area(0) - cells(0)) / 2,
        (area(1) - cells(1)) / 2
    );
    
    // list of cells, sorted by distance from center
    std::vector<ArrangeItemIndex> cellsorder;
    
    // work out distance for all cells, sort into list
    for (size_t i = 0; i <= cellw-1; ++i) {
        for (size_t j = 0; j <= cellh-1; ++j) {
            coordf_t cx = linint(i + 0.5, 0, cellw, cells_bb.min(0), cells_bb.max(0));
            coordf_t cy = linint(j + 0.5, 0, cellh, cells_bb.min(1), cells_bb.max(1));
            
            coordf_t xd = fabs((area(0) / 2) - cx);
            coordf_t yd = fabs((area(1) / 2) - cy);
            
            ArrangeItem c;
            c.pos(0) = cx;
            c.pos(1) = cy;
            c.index_x = i;
            c.index_y = j;
            c.dist = xd * xd + yd * yd - fabs((cellw / 2) - (i + 0.5));
            
            // binary insertion sort
            {
                coordf_t index = c.dist;
                size_t low = 0;
                size_t high = cellsorder.size();
                while (low < high) {
                    size_t mid = (low + ((high - low) / 2)) | 0;
                    coordf_t midval = cellsorder[mid].index;
                    
                    if (midval < index) {
                        low = mid + 1;
                    } else if (midval > index) {
                        high = mid;
                    } else {
                        cellsorder.insert(cellsorder.begin() + mid, ArrangeItemIndex(index, c));
                        goto ENDSORT;
                    }
                }
                cellsorder.insert(cellsorder.begin() + low, ArrangeItemIndex(index, c));
            }
            ENDSORT: ;
        }
    }
    
    // the extents of cells actually used by objects
    coordf_t lx = 0;
    coordf_t ty = 0;
    coordf_t rx = 0;
    coordf_t by = 0;
 
    // now find cells actually used by objects, map out the extents so we can position correctly
    for (size_t i = 1; i <= total_parts; ++i) {
        ArrangeItemIndex c = cellsorder[i - 1];
        coordf_t cx = c.item.index_x;
        coordf_t cy = c.item.index_y;
        if (i == 1) {
            lx = rx = cx;
            ty = by = cy;
        } else {
            if (cx > rx) rx = cx;
            if (cx < lx) lx = cx;
            if (cy > by) by = cy;
            if (cy < ty) ty = cy;
        }
    }
    // now we actually place objects into cells, positioned such that the left and bottom borders are at 0
    for (size_t i = 1; i <= total_parts; ++i) {
        ArrangeItemIndex c = cellsorder.front();
        cellsorder.erase(cellsorder.begin());
        coordf_t cx = c.item.index_x - lx;
        coordf_t cy = c.item.index_y - ty;
        
        positions.push_back(Vec2d(cx * part(0), cy * part(1)));
    }
    
    if (bb != NULL && bb->defined) {
        for (Pointfs::iterator p = positions.begin(); p != positions.end(); ++p) {
            p->x() += bb->min(0);
            p->y() += bb->min(1);
        }
    }
    
    return true;
}

References Slic3r::area(), Slic3r::BoundingBoxBase< PointType, APointsType >::defined, Slic3r::Geometry::ArrangeItem::dist, dist(), Slic3r::Geometry::ArrangeItem::index_x, Slic3r::Geometry::ArrangeItem::index_y, Slic3r::Geometry::ArrangeItemIndex::item, linint(), Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::BoundingBoxBase< PointType, APointsType >::min, Slic3r::Geometry::ArrangeItem::pos, Slic3r::BoundingBoxBase< PointType, APointsType >::size(), and Slic3r::BoundingBoxBase< PointType, APointsType >::translate().

Referenced by Slic3r::arrangement::arrange().

Here is the call graph for this function:

Here is the caller graph for this function:

assemble_transform() [1/4]

Transform3d Slic3r::Geometry::assemble_transform	(	const Transform3d &	translation,
		const Transform3d &	rotation,
		const Transform3d &	scale,
		const Transform3d &	mirror )

{
    Transform3d transform;
    assemble_transform(transform, translation, rotation, scale, mirror);
    return transform;
}

References assemble_transform(), scale(), and Slic3r::transform().

Here is the call graph for this function:

assemble_transform() [2/4]

Transform3d Slic3r::Geometry::assemble_transform	(	const Vec3d &	translation,
		const Vec3d &	rotation,
		const Vec3d &	scale,
		const Vec3d &	mirror )

{
    Transform3d transform;
    assemble_transform(transform, translation, rotation, scale, mirror);
    return transform;
}

References assemble_transform(), scale(), and Slic3r::transform().

Here is the call graph for this function:

assemble_transform() [3/4]

void Slic3r::Geometry::assemble_transform	(	Transform3d &	transform,
		const Transform3d &	translation,
		const Transform3d &	rotation,
		const Transform3d &	scale,
		const Transform3d &	mirror )

{
    transform = translation * rotation * scale * mirror;
}

References scale(), and Slic3r::transform().

Here is the call graph for this function:

assemble_transform() [4/4]

void Slic3r::Geometry::assemble_transform	(	Transform3d &	transform,
		const Vec3d &	translation,
		const Vec3d &	rotation,
		const Vec3d &	scale,
		const Vec3d &	mirror )

{
    transform = Transform3d::Identity();
    transform.translate(translation);
    transform.rotate(Eigen::AngleAxisd(rotation(2), Vec3d::UnitZ()) * Eigen::AngleAxisd(rotation(1), Vec3d::UnitY()) * Eigen::AngleAxisd(rotation(0), Vec3d::UnitX()));
    transform.scale(scale.cwiseProduct(mirror));
}

References scale(), and Slic3r::transform().

Referenced by Slic3r::GUI::GLCanvas3D::_render_sla_slices(), assemble_transform(), assemble_transform(), Slic3r::compacted_tower_print_instance_hull(), Slic3r::GUI::GLCanvas3D::get_empty_cells(), Slic3r::sla::RotfinderBoilerplate< MAX_ITER >::get_mesh_to_rotate(), Slic3r::layered_print_cleareance_valid(), Slic3r::GLVolume::SinkingContours::render(), Slic3r::GUI::Bed3D::Axes::render(), Slic3r::GUI::GLGizmoBase::Grabber::render(), Slic3r::GUI::GLGizmoTextureDisplacement::render_adjust_texture_gizmo(), Slic3r::GUI::GLGizmoPainterBase::render_cursor_height_range(), Slic3r::GUI::GLGizmoPainterBase::render_cursor_sphere(), Slic3r::GUI::Bed3D::render_model(), Slic3r::GUI::Selection::render_sidebar_hints(), Slic3r::GUI::Selection::render_sidebar_position_hints(), Slic3r::GUI::Selection::render_sidebar_rotation_hints(), Slic3r::GUI::Selection::render_sidebar_scale_hints(), Slic3r::GUI::Selection::scale_and_translate(), Slic3r::Print::sequential_print_clearance_valid(), and Slic3r::GUI::GLCanvas3D::update_sequential_clearance().

Here is the call graph for this function:

Here is the caller graph for this function:

bicubic_interpolate()

template<typename Kernel, typename Derived>

float Slic3r::Geometry::bicubic_interpolate ( const Eigen::MatrixBase< Derived > & F, const Eigen::Matrix< typename Kernel::FloatType, 2, 1, Eigen::DontAlign > & pt )

static

                                                                               {
    typedef typename Kernel::FloatType T;
    const int w = F.cols();
    const int h = F.rows();
    const int ix = (int) floor(pt[0]);
    const int iy = (int) floor(pt[1]);
    const T s = pt[0] - T( ix);
    const T t = pt[1] - T( iy);
 
    if (ix > 1 && ix + 2 < w && iy > 1 && iy + 2 < h) {
        // Inside the fully interpolated region.
        return Kernel::interpolate(
                Kernel::interpolate(F(ix - 1, iy - 1), F(ix, iy - 1), F(ix + 1, iy - 1), F(ix + 2, iy - 1), s),
                Kernel::interpolate(F(ix - 1, iy), F(ix, iy), F(ix + 1, iy), F(ix + 2, iy), s),
                Kernel::interpolate(F(ix - 1, iy + 1), F(ix, iy + 1), F(ix + 1, iy + 1), F(ix + 2, iy + 1), s),
                Kernel::interpolate(F(ix - 1, iy + 2), F(ix, iy + 2), F(ix + 1, iy + 2), F(ix + 2, iy + 2), s), t);
    }
    // Transition region. Extend with a constant function.
    auto f = [&F, w, h](int x, int y) {
        return F(BicubicInternal::clamp(x, 0, w - 1), BicubicInternal::clamp(y, 0, h - 1));
    };
    return Kernel::interpolate(
            Kernel::interpolate(f(ix - 1, iy - 1), f(ix, iy - 1), f(ix + 1, iy - 1), f(ix + 2, iy - 1), s),
            Kernel::interpolate(f(ix - 1, iy), f(ix, iy), f(ix + 1, iy), f(ix + 2, iy), s),
            Kernel::interpolate(f(ix - 1, iy + 1), f(ix, iy + 1), f(ix + 1, iy + 1), f(ix + 2, iy + 1), s),
            Kernel::interpolate(f(ix - 1, iy + 2), f(ix, iy + 2), f(ix + 1, iy + 2), f(ix + 2, iy + 2), s), t);
}

References Slic3r::Geometry::BicubicInternal::clamp(), Slic3r::F, and Slic3r::f().

Here is the call graph for this function:

check_if_three_edges_are_ccw()

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, bool >::type Slic3r::Geometry::check_if_three_edges_are_ccw ( const VD::edge_type & edge_first, const VD::edge_type & edge_second, const VD::edge_type & edge_third, const SegmentIterator segment_begin, const SegmentIterator segment_end )

static

{
    assert(is_equal(*edge_first.vertex0(), *edge_second.vertex0()) && is_equal(*edge_second.vertex0(), *edge_third.vertex0()));
 
    CGAL::Orientation orientation = orientation_of_two_edges(edge_first, edge_second, segment_begin, segment_end);
    if (orientation == CGAL::Orientation::COLLINEAR) {
        // The first two edges are collinear, so the third edge must be on the right side on the first of them.
        return orientation_of_two_edges(edge_first, edge_third, segment_begin, segment_end) == CGAL::Orientation::RIGHT_TURN;
    } else if (orientation == CGAL::Orientation::LEFT_TURN) {
        // CCW oriented angle between vectors (common_pt, pt1) and (common_pt, pt2) is bellow PI.
        // So we need to check if test_pt isn't between them.
        CGAL::Orientation orientation1 = orientation_of_two_edges(edge_first, edge_third, segment_begin, segment_end);
        CGAL::Orientation orientation2 = orientation_of_two_edges(edge_second, edge_third, segment_begin, segment_end);
        return (orientation1 != CGAL::Orientation::LEFT_TURN || orientation2 != CGAL::Orientation::RIGHT_TURN);
    } else {
        assert(orientation == CGAL::Orientation::RIGHT_TURN);
        // CCW oriented angle between vectors (common_pt, pt1) and (common_pt, pt2) is upper PI.
        // So we need to check if test_pt is between them.
        CGAL::Orientation orientation1 = orientation_of_two_edges(edge_first, edge_third, segment_begin, segment_end);
        CGAL::Orientation orientation2 = orientation_of_two_edges(edge_second, edge_third, segment_begin, segment_end);
        return (orientation1 == CGAL::Orientation::RIGHT_TURN || orientation2 == CGAL::Orientation::LEFT_TURN);
    }
}

References is_equal(), and orientation_of_two_edges().

Referenced by Slic3r::Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_angle().

Here is the call graph for this function:

Here is the caller graph for this function:

circle_center()

template<typename Vector>

Vector Slic3r::Geometry::circle_center	(	const Vector &	a,
		const Vector &	bsrc,
		const Vector &	csrc,
		typename Vector::Scalar	epsilon )

{
    using Scalar = typename Vector::Scalar;
    Vector b  = bsrc - a;
    Vector c  = csrc - a;
  Scalar lb = b.squaredNorm();
  Scalar lc = c.squaredNorm();
    if (Scalar d = b.x() * c.y() - b.y() * c.x(); std::abs(d) < epsilon) {
      // The three points are collinear. Take the center of the two points
      // furthest away from each other.
      Scalar lbc = (csrc - bsrc).squaredNorm();
    return Scalar(0.5) * (
      lb > lc && lb > lbc ? a + bsrc :
      lc > lb && lc > lbc ? a + csrc : bsrc + csrc);
    } else {
        Vector v = lc * b - lb * c;
        return a + Vector(- v.y(), v.x()) / (2 * d);
    }
}

Referenced by Slic3r::Geometry::CircleSq< Vector >::CircleSq(), and circle_ransac().

Here is the caller graph for this function:

circle_center_taubin_newton() [1/4]

Point Slic3r::Geometry::circle_center_taubin_newton ( const Points & input, size_t cycles = 20 )

inline

{ return circle_center_taubin_newton(input.cbegin(), input.cend(), cycles); }

References circle_center_taubin_newton().

Here is the call graph for this function:

circle_center_taubin_newton() [2/4]

Point Slic3r::Geometry::circle_center_taubin_newton	(	const Points::const_iterator &	input_begin,
		const Points::const_iterator &	input_end,
		size_t	cycles )

Find the center of the circle corresponding to the vector of Points as an arc.

{
    Vec2ds tmp;
    tmp.reserve(std::distance(input_begin, input_end));
    std::transform(input_begin, input_end, std::back_inserter(tmp), [] (const Point& in) { return unscale(in); } );
    Vec2d center = circle_center_taubin_newton(tmp.cbegin(), tmp.end(), cycles);
  return Point::new_scale(center.x(), center.y());
}

References Slic3r::center(), circle_center_taubin_newton(), Slic3r::Point::new_scale(), and Slic3r::unscale().

Referenced by circle_center_taubin_newton(), circle_center_taubin_newton(), circle_center_taubin_newton(), and circle_taubin_newton().

Here is the call graph for this function:

Here is the caller graph for this function:

circle_center_taubin_newton() [3/4]

Vec2d Slic3r::Geometry::circle_center_taubin_newton ( const Vec2ds & input, size_t cycles = 20 )

inline

{ return circle_center_taubin_newton(input.cbegin(), input.cend(), cycles); }

References circle_center_taubin_newton().

Here is the call graph for this function:

circle_center_taubin_newton() [4/4]

Vec2d Slic3r::Geometry::circle_center_taubin_newton	(	const Vec2ds::const_iterator &	input_begin,
		const Vec2ds::const_iterator &	input_end,
		size_t	cycles )

Adapted from work in "Circular and Linear Regression: Fitting circles and lines by least squares", pg 126 Returns a point corresponding to the center of a circle for which all of the points from input_begin to input_end lie on.

Find the center of the circle corresponding to the vector of Pointfs as an arc.

{
    // calculate the centroid of the data set
    const Vec2d sum = std::accumulate(input_begin, input_end, Vec2d(0,0));
    const size_t n = std::distance(input_begin, input_end);
    const double n_flt = static_cast<double>(n);
    const Vec2d centroid { sum / n_flt };
 
    // Compute the normalized moments of the data set.
    double Mxx = 0, Myy = 0, Mxy = 0, Mxz = 0, Myz = 0, Mzz = 0;
    for (auto it = input_begin; it < input_end; ++it) {
        // center/normalize the data.
        double Xi {it->x() - centroid.x()};
        double Yi {it->y() - centroid.y()};
        double Zi {Xi*Xi + Yi*Yi};
        Mxy += (Xi*Yi);
        Mxx += (Xi*Xi);
        Myy += (Yi*Yi);
        Mxz += (Xi*Zi);
        Myz += (Yi*Zi);
        Mzz += (Zi*Zi);
    }
 
    // divide by number of points to get the moments
    Mxx /= n_flt;
    Myy /= n_flt;
    Mxy /= n_flt;
    Mxz /= n_flt;
    Myz /= n_flt;
    Mzz /= n_flt;
 
    // Compute the coefficients of the characteristic polynomial for the circle
    // eq 5.60
    const double Mz {Mxx + Myy}; // xx + yy = z
    const double Cov_xy {Mxx*Myy - Mxy*Mxy}; // this shows up a couple times so cache it here.
    const double C3 {4.0*Mz};
    const double C2 {-3.0*(Mz*Mz) - Mzz};
    const double C1 {Mz*(Mzz - (Mz*Mz)) + 4.0*Mz*Cov_xy - (Mxz*Mxz) - (Myz*Myz)};
    const double C0 {(Mxz*Mxz)*Myy + (Myz*Myz)*Mxx - 2.0*Mxz*Myz*Mxy - Cov_xy*(Mzz - (Mz*Mz))};
 
    const double C22 = {C2 + C2};
    const double C33 = {C3 + C3 + C3};
 
    // solve the characteristic polynomial with Newton's method.
    double xnew = 0.0;
    double ynew = 1e20;
 
    for (size_t i = 0; i < cycles; ++i) {
        const double yold {ynew};
        ynew = C0 + xnew * (C1 + xnew*(C2 + xnew * C3));
        if (std::abs(ynew) > std::abs(yold)) {
      BOOST_LOG_TRIVIAL(error) << "Geometry: Fit is going in the wrong direction.\n";
            return Vec2d(std::nan(""), std::nan(""));
        }
        const double Dy {C1 + xnew*(C22 + xnew*C33)};
 
        const double xold {xnew};
        xnew = xold - (ynew / Dy);
 
        if (std::abs((xnew-xold) / xnew) < 1e-12) i = cycles; // converged, we're done here
 
        if (xnew < 0) {
            // reset, we went negative
            xnew = 0.0;
        }
    }
    
    // compute the determinant and the circle's parameters now that we've solved.
    double DET = xnew*xnew - xnew*Mz + Cov_xy;
 
    Vec2d center(Mxz * (Myy - xnew) - Myz * Mxy, Myz * (Mxx - xnew) - Mxz*Mxy);
    center /= (DET * 2.);
    return center + centroid;
}

References Slic3r::center().

Here is the call graph for this function:

circle_ransac()

Circled Slic3r::Geometry::circle_ransac	(	const Vec2ds &	input,
		size_t	iterations,
		double *	min_error )

{
    if (input.size() < 3)
        return Circled::make_invalid();
 
    std::mt19937 rng;
    std::vector<Vec2d> samples;
    Circled circle_best = Circled::make_invalid();
    double  err_min = std::numeric_limits<double>::max();
    for (size_t iter = 0; iter < iterations; ++ iter) {
        samples.clear();
        std::sample(input.begin(), input.end(), std::back_inserter(samples), 3, rng);
        Circled c;
        c.center = Geometry::circle_center(samples[0], samples[1], samples[2], EPSILON);
        c.radius = std::accumulate(input.begin(), input.end(), 0., [&c](double acc, const Vec2d& pt) { return (pt - c.center).norm() + acc; });
        c.radius /= double(input.size());
        double err = 0;
        for (const Vec2d &pt : input)
            err = std::max(err, std::abs((pt - c.center).norm() - c.radius));
        if (err < err_min) {
            err_min = err;
            circle_best = c;
        }
    }
    if (min_error)
        *min_error = err_min;
    return circle_best;
}

References Slic3r::Geometry::Circle< Vector >::center, circle_center(), EPSILON, Slic3r::Geometry::Circle< Vec2d >::make_invalid(), and Slic3r::Geometry::Circle< Vector >::radius.

Referenced by Slic3r::BuildVolume::BuildVolume(), and Slic3r::Measure::get_center_and_radius().

Here is the call graph for this function:

Here is the caller graph for this function:

circle_taubin_newton()

Circled Slic3r::Geometry::circle_taubin_newton	(	const Vec2ds &	input,
		size_t	cycles )

{
    Circled out;
    if (input.size() < 3) {
        out = Circled::make_invalid();
    } else {
        out.center = circle_center_taubin_newton(input, cycles);
        out.radius = std::accumulate(input.begin(), input.end(), 0., [&out](double acc, const Vec2d& pt) { return (pt - out.center).norm() + acc; });
        out.radius /= double(input.size());
    }
    return out;
}

References Slic3r::Geometry::Circle< Vector >::center, circle_center_taubin_newton(), Slic3r::Geometry::Circle< Vec2d >::make_invalid(), and Slic3r::Geometry::Circle< Vector >::radius.

Here is the call graph for this function:

contains() [1/2]

template bool Slic3r::Geometry::contains	(	const ExPolygons &	vector,
		const Point &	point )

contains() [2/2]

template<class T>

bool Slic3r::Geometry::contains	(	const std::vector< T > &	vector,
		const Point &	point )

{
    for (typename std::vector<T>::const_iterator it = vector.begin(); it != vector.end(); ++it) {
        if (it->contains(point)) return true;
    }
    return false;
}

Referenced by Slic3r::FillSpiralInset::_fill_surface_single(), Slic3r::GUI::HMSQuery::_is_internal_error(), Slic3r::GUI::HMSQuery::_query_error_msg(), Slic3r::active_capability_config(), Slic3r::anonymous_namespace{PythonInterpreter.cpp}::add_sys_path_entry(), Slic3r::GUI::MenuFactory::append_menu_items_flush_options(), Slic3r::check_filaments(), Slic3r::GUI::GUI_App::check_new_version(), Slic3r::ExPolygon::contains(), Slic3r::Polygon::contains(), Slic3r::TreeSupport3D::convert_lines_to_internal(), Slic3r::TreeSupport3D::evaluate_point_for_next_layer_function(), Slic3r::SnapmakerPrinterAgent::fetch_filament_info(), Slic3r::IslandLocator::find(), Slic3r::find_containing_expolygon_index(), Slic3r::find_nearby_points(), Slic3r::TreeSupport3D::get_avoidance_status(), Slic3r::GUI::get_error_message(), Slic3r::DevPrinterConfigUtil::get_fan_mode_text(), Slic3r::handle_extrusion_collection(), Slic3r::MoonrakerPrinterAgent::handle_request(), Slic3r::FillLightning::inside(), Slic3r::ClipperUtils::interior_point(), Slic3r::is_inside_ex(), Slic3r::load_assemble_plate_list(), Slic3r::GUI::GuideFrame::LoadProfileFamily(), Slic3r::TreeSupport3D::move_inside_if_outside(), Slic3r::one_of(), Slic3r::one_of(), Slic3r::GUI::GuideFrame::OnScriptMessage(), Slic3r::GUI::ZUserLogin::OnScriptMessage(), Slic3r::BBLSubTask::parse_content_json(), Slic3r::MachineObject::parse_json(), Slic3r::UserManager::parse_json(), Slic3r::DevPrintOptionsParser::ParseDetectionV1_0(), Slic3r::DevFilaSystemParser::ParseV1_0(), Slic3r::anonymous_namespace{ClipperUtils.cpp}::path_encloses(), Slic3r::WipeTowerIntegration::travel_to_tower_gap(), and Slic3r::MachineObject::update_slice_info().

Here is the caller graph for this function:

contains_skew()

bool Slic3r::Geometry::contains_skew ( const Transform3d & trafo )

static

{
    return !extract_scale(trafo).linear().isDiagonal();
}

References extract_scale().

Referenced by Slic3r::Geometry::Transformation::has_skew().

Here is the call graph for this function:

Here is the caller graph for this function:

convex_hull() [1/4]

Polygon Slic3r::Geometry::convex_hull

(

const ExPolygons &

expolygons

)

{
    Points pp;
    size_t sz = 0;
    for (const auto &expoly : expolygons)
        sz += expoly.contour.size();
    pp.reserve(sz);
    for (const auto &expoly : expolygons)
        pp.insert(pp.end(), expoly.contour.points.begin(), expoly.contour.points.end());
    return convex_hull(pp);
}

References convex_hull().

Here is the call graph for this function:

convex_hull() [2/4]

Polygon Slic3r::Geometry::convex_hull

(

const Polygons &

polygons

)

{
    Points pp;
    for (Polygons::const_iterator p = polygons.begin(); p != polygons.end(); ++p) {
        pp.insert(pp.end(), p->points.begin(), p->points.end());
    }
    return convex_hull(std::move(pp));
}

References convex_hull().

Here is the call graph for this function:

convex_hull() [3/4]

Pointf3s Slic3r::Geometry::convex_hull

(

Pointf3s

points

)

{
    assert(points.size() >= 3);
    // sort input points
    std::sort(points.begin(), points.end(), [](const Vec3d &a, const Vec3d &b){ return a.x() < b.x() || (a.x() == b.x() && a.y() < b.y()); });
 
    int n = points.size(), k = 0;
    Pointf3s hull;
 
    if (n >= 3)
    {
        hull.resize(2 * n);
 
        // Build lower hull
        for (int i = 0; i < n; ++i)
        {
            Point p = Point::new_scale(points[i](0), points[i](1));
            while (k >= 2)
            {
                Point k1 = Point::new_scale(hull[k - 1](0), hull[k - 1](1));
                Point k2 = Point::new_scale(hull[k - 2](0), hull[k - 2](1));
 
                if (Geometry::orient(p, k2, k1) != Geometry::ORIENTATION_CCW)
                    --k;
                else
                    break;
            }
 
            hull[k++] = points[i];
        }
 
        // Build upper hull
        for (int i = n - 2, t = k + 1; i >= 0; --i)
        {
            Point p = Point::new_scale(points[i](0), points[i](1));
            while (k >= t)
            {
                Point k1 = Point::new_scale(hull[k - 1](0), hull[k - 1](1));
                Point k2 = Point::new_scale(hull[k - 2](0), hull[k - 2](1));
 
                if (Geometry::orient(p, k2, k1) != Geometry::ORIENTATION_CCW)
                    --k;
                else
                    break;
            }
 
            hull[k++] = points[i];
        }
 
        hull.resize(k);
 
        assert(hull.front() == hull.back());
        hull.pop_back();
    }
 
    return hull;
}

References Slic3r::Point::new_scale(), orient(), and ORIENTATION_CCW.

Here is the call graph for this function:

convex_hull() [4/4]

Polygon Slic3r::Geometry::convex_hull

(

Points

pts

)

{
    std::sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) { return a.x() < b.x() || (a.x() == b.x() && a.y() < b.y()); });
    pts.erase(std::unique(pts.begin(), pts.end(), [](const Point& a, const Point& b) { return a.x() == b.x() && a.y() == b.y(); }), pts.end());
 
    Polygon hull;
    int n = (int)pts.size();
    if (n >= 3) {
        int k = 0;
        hull.points.resize(2 * n);
        // Build lower hull
        for (int i = 0; i < n; ++ i) {
            while (k >= 2 && Geometry::orient(pts[i], hull[k-2], hull[k-1]) != Geometry::ORIENTATION_CCW)
                -- k;
            hull[k ++] = pts[i];
        }
        // Build upper hull
        for (int i = n-2, t = k+1; i >= 0; i--) {
            while (k >= t && Geometry::orient(pts[i], hull[k-2], hull[k-1]) != Geometry::ORIENTATION_CCW)
                -- k;
            hull[k ++] = pts[i];
        }
        hull.points.resize(k);
        assert(hull.points.front() == hull.points.back());
        hull.points.pop_back();
    }
    return hull;
}

References orient(), ORIENTATION_CCW, and Slic3r::MultiPoint::points.

Referenced by Slic3r::BuildVolume::BuildVolume(), Slic3r::ModelVolume::ModelVolume(), Slic3r::Print::_make_skirt(), Slic3r::bed_exclusion_arrange_polygon(), Slic3r::ModelVolume::calculate_convex_hull_2d(), Slic3r::compacted_tower_print_instance_hull(), Slic3r::compacted_wipe_tower_zone(), Slic3r::ExPolygonCollection::convex_hull(), convex_hull(), convex_hull(), Slic3r::TriangleMesh::convex_hull(), Slic3r::ModelObject::convex_hull_2d(), convex_hulll(), Slic3r::GUI::CameraUtils::create_hull2d(), Slic3r::Print::finalize_first_layer_convex_hull(), Slic3r::generate_extra_perimeters_over_overhangs(), Slic3r::get_arrange_poly(), Slic3r::GUI::anonymous_namespace{GLGizmoAlignment.cpp}::instance_box_in_frame(), Slic3r::its_convex_hull_2d_above(), Slic3r::lay_on_face_planes(), Slic3r::GLVolumeCollection::load_object_auxiliary(), Slic3r::nearest_clear_wipe_tower_anchor(), Slic3r::Print::sequential_print_clearance_valid(), Slic3r::solid_bodies(), Slic3r::ModelVolume::transform_this_mesh(), Slic3r::ModelVolume::transform_this_mesh(), Slic3r::sla::SupportPointGenerator::uniformly_cover(), Slic3r::GUI::GLCanvas3D::update_sequential_clearance(), and Slic3r::Print::validate_compacted_wipe_tower_clearance().

Here is the call graph for this function:

Here is the caller graph for this function:

convex_hulll()

Polygon Slic3r::Geometry::convex_hulll

(

const Polylines &

polylines

)

{
    Points pp;
    size_t sz = 0;
    for (const auto &polyline : polylines)
        sz += polyline.points.size();
    pp.reserve(sz);
    for (const auto &polyline : polylines)
        pp.insert(pp.end(), polyline.points.begin(), polyline.points.end());
    return convex_hull(pp);
}

References convex_hull().

Here is the call graph for this function:

convex_polygons_intersect()

bool Slic3r::Geometry::convex_polygons_intersect	(	const Polygon &	A,
		const Polygon &	B )

{
    using namespace rotcalip;
 
    // Establish starting antipodals as extremes in XY plane. Use the
    // easily obtainable bounding boxes to check if A and B is disjoint
    // and return false if the are.
    struct BB
    {
        size_t         xmin = 0, xmax = 0, ymin = 0, ymax = 0;
        const Polygon &P;
        static bool cmpy(const Point &l, const Point &u)
        {
            return l.y() < u.y() || (l.y() == u.y() && l.x() < u.x());
        }
 
        BB(const Polygon &poly): P{poly}
        {
            for (size_t i = 0; i < P.size(); ++i) {
                if (P[i] < P[xmin]) xmin = i;
                if (P[xmax] < P[i]) xmax = i;
                if (cmpy(P[i], P[ymin])) ymin = i;
                if (cmpy(P[ymax], P[i])) ymax = i;
            }
        }
    };
 
    BB bA{A}, bB{B};
    BoundingBox bbA{{A[bA.xmin].x(), A[bA.ymin].y()}, {A[bA.xmax].x(), A[bA.ymax].y()}};
    BoundingBox bbB{{B[bB.xmin].x(), B[bB.ymin].y()}, {B[bB.xmax].x(), B[bB.ymax].y()}};
 
//    if (!bbA.overlap(bbB))
//        return false;
 
    // Establish starting antipodals as extreme vertex pairs in X or Y direction
    // which reside on different polygons. If no such pair is found, the two
    // polygons are certainly not disjoint.
    Idx imin{bA.xmin, A}, imax{bB.xmax, B};
    if (B[bB.xmin] < imin.pt())  imin = Idx{bB.xmin, B};
    if (imax.pt()  < A[bA.xmax]) imax = Idx{bA.xmax, A};
    if (&imin.poly() == &imax.poly()) {
        imin = Idx{bA.ymin, A};
        imax = Idx{bB.ymax, B};
        if (B[bB.ymin] < imin.pt())  imin = Idx{bB.ymin, B};
        if (imax.pt()  < A[bA.ymax]) imax = Idx{bA.ymax, A};
    }
 
    if (&imin.poly() == &imax.poly())
        return true;
 
    bool found_divisor = false;
    visit_antipodals<AntipodalVisitMode::EdgesOnly>(
        imin, imax,
        [&imin, &imax, &found_divisor](size_t ia, size_t ib, const Point &dir) {
            //        std::cout << "A" << ia << " B" << ib << " dir " <<
            //        dir.x() << " " << dir.y() << std::endl;
            const Polygon &A = imin.poly(), &B = imax.poly();
 
            Point ref_a = A[(ia + 2) % A.size()], ref_b = B[(ib + 2) % B.size()];
 
            bool is_left_a = dotperp( dir, ref_a - A[ia]) > 0;
            bool is_left_b = dotperp(-dir, ref_b - B[ib]) > 0;
 
            // If both reference points are on the left (or right) of their
            // respective support lines and the opposite support line is to
            // the right (or left), the divisor line is found. We only test
            // the reference point, as by definition, if that is on one side,
            // all the other points must be on the same side of a support
            // line. If the support lines are collinear, the polygons must be
            // on the same side of their respective support lines.
 
            auto d = dotperp(dir, B[ib] - A[ia]);
            if (d == 0) {
                // The caliper lines are collinear, not just parallel
                found_divisor = (is_left_a && is_left_b) || (!is_left_a && !is_left_b);
            } else if (d > 0) { // B is to the left of (A, A+1)
                found_divisor = !is_left_a && !is_left_b;
            } else { // B is to the right of (A, A+1)
                found_divisor = is_left_a && is_left_b;
            }
 
            return !found_divisor;
        });
 
    // Intersects if the divisor was not found
    return !found_divisor;
}

References Slic3r::P, and Slic3r::MultiPoint::size().

Here is the call graph for this function:

cubic_interpolate()

template<typename KernelWrapper>

KernelWrapper::FloatType Slic3r::Geometry::cubic_interpolate ( const Eigen::ArrayBase< typename KernelWrapper::FloatType > & F, const typename KernelWrapper::FloatType pt )

static

                                                  {
    typedef typename KernelWrapper::FloatType T;
    const int w = int(F.size());
    const int ix = (int) floor(pt);
    const T s = pt - T( ix);
 
    if (ix > 1 && ix + 2 < w) {
        // Inside the fully interpolated region.
        return KernelWrapper::interpolate(F[ix - 1], F[ix], F[ix + 1], F[ix + 2], s);
    }
    // Transition region. Extend with a constant function.
    auto f = [&F, w](T x) {
        return F[BicubicInternal::clamp(x, 0, w - 1)];
    };
    return KernelWrapper::interpolate(f(ix - 1), f(ix), f(ix + 1), f(ix + 2), s);
}

References Slic3r::Geometry::BicubicInternal::clamp(), Slic3r::F, and Slic3r::f().

Here is the call graph for this function:

decode_input_segment_endpoint()

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, typenameboost::polygon::segment_point_type< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type Slic3r::Geometry::decode_input_segment_endpoint ( const VD::vertex_type::color_type color, const SegmentIterator segment_begin, const SegmentIterator segment_end )

inline

{
    using SegmentType = typename std::iterator_traits<SegmentIterator>::value_type;
    using PointType   = typename boost::polygon::segment_traits<SegmentType>::point_type;
 
    const size_t          segment_idx  = (color >> 1) - 1;
    const SegmentIterator segment_it   = segment_begin + segment_idx;
    const PointType       source_point = boost::polygon::segment_traits<SegmentType>::get(*segment_it, ((color & 1) ? boost::polygon::HIGH :
                                                                                                                      boost::polygon::LOW));
    return source_point;
}

Referenced by Slic3r::Geometry::VoronoiDiagram::try_to_repair_degenerated_voronoi_diagram_by_rotation().

Here is the caller graph for this function:

decompose_convex_polygon_top_bottom()

std::pair< std::vector< Vec2d >, std::vector< Vec2d > > Slic3r::Geometry::decompose_convex_polygon_top_bottom

(

const std::vector< Vec2d > &

src

)

{
    std::pair<std::vector<Vec2d>, std::vector<Vec2d>> out;
    std::vector<Vec2d> &bottom = out.first;
    std::vector<Vec2d> &top    = out.second;
 
    // Find the minimum point.
    auto left_bottom  = std::min_element(src.begin(), src.end(), [](const auto &l, const auto &r) { return l.x() < r.x() || (l.x() == r.x() && l.y() < r.y()); });
    auto right_top    = std::max_element(src.begin(), src.end(), [](const auto &l, const auto &r) { return l.x() < r.x() || (l.x() == r.x() && l.y() < r.y()); });
    if (left_bottom != src.end() && left_bottom != right_top) {
        // Produce the bottom and bottom chains.
        if (left_bottom < right_top) {
            bottom.assign(left_bottom, right_top + 1);
            size_t cnt = (src.end() - right_top) + (left_bottom + 1 - src.begin());
            top.reserve(cnt);
            top.assign(right_top, src.end());
            top.insert(top.end(), src.begin(), left_bottom + 1);
        } else {
            size_t cnt = (src.end() - left_bottom) + (right_top + 1 - src.begin());
            bottom.reserve(cnt);
            bottom.assign(left_bottom, src.end());
            bottom.insert(bottom.end(), src.begin(), right_top + 1);
            top.assign(right_top, left_bottom + 1);
        }
        // Remove strictly vertical segments at the end.
        if (bottom.size() > 1) {
            auto it = bottom.end();
            for (-- it; it != bottom.begin() && (it - 1)->x() == bottom.back().x(); -- it) ;
            bottom.erase(it + 1, bottom.end());
        }
        if (top.size() > 1) {
            auto it = top.end();
            for (-- it; it != top.begin() && (it - 1)->x() == top.back().x(); -- it) ;
            top.erase(it + 1, top.end());
        }
        std::reverse(top.begin(), top.end());
    }
 
    if (top.size() < 2 || bottom.size() < 2) {
        // invalid
        top.clear();
        bottom.clear();
    }
    return out;
}

Referenced by Slic3r::BuildVolume::BuildVolume().

Here is the caller graph for this function:

deg2rad()

template<typename T>

T Slic3r::Geometry::deg2rad ( const T angle )

constexpr

{
    static_assert(std::is_floating_point<T>::value, "Why do you want to calculate angle in integer?");
    return T(PI) * angle / T(180.0);
}

References Slic3r::angle(), and PI.

Referenced by Slic3r::SupportGridParams::SupportGridParams(), Slic3r::SupportParameters::SupportParameters(), Slic3r::Print::_make_wipe_tower(), Slic3r::GUI::belt_calib_rotation_params(), Slic3r::TriangleSelector::bucket_fill_select_triangles(), Slic3r::build_plate_tilt_slope(), Slic3r::GUI::build_plate_tilt_up_direction(), Slic3r::BeltTransformPipeline::build_rotation_matrix(), Slic3r::calculate_infill_rotation_angle(), Slic3r::anonymous_namespace{BeltTransform.cpp}::compute_belt_height_and_floor_impl(), Slic3r::detect_overhangs(), Slic3r::TreeSupport::detect_overhangs(), Slic3r::GUI::ensure_belt_purge_tower(), Slic3r::GUI::PartPlate::estimate_wipe_tower_polygon(), Slic3r::estimated_wipe_tower_footprint(), Slic3r::FillLateralLattice::fill_surface(), Slic3r::Print::first_layer_wipe_tower_corners(), Slic3r::BeltTransformPipeline::floor_shear(), Slic3r::Arachne::WallToolPaths::generate(), Slic3r::InterlockingGenerator::generate_interlocking_structure(), Slic3r::WipeTower2::generate_support_cone_wall(), Slic3r::TreeSupport::generate_toolpaths(), Slic3r::GLVolumeCollection::get_selection_support_normal_z(), Slic3r::WipeTower2::get_wipe_tower_cone_base(), Slic3r::get_wipe_tower_extrusions_extents(), Slic3r::FakeWipeTower::getFakeExtrusionPathsFromWipeTower2(), Slic3r::group_fills(), Slic3r::GUI::PartPlate::imex_wipe_tower_hull(), Slic3r::GUI::init_arrange_params(), Slic3r::MachineFrameTransform::init_from_config(), Slic3r::layered_print_cleareance_valid(), Slic3r::GUI::Plater::priv::load_files(), Slic3r::Layer::make_ironing(), anonymous_namespace{OrcaSlicer_profile_validator.cpp}::place_wipe_tower(), Slic3r::LayerRegion::process_external_surfaces(), Slic3r::PerimeterGenerator::process_no_bridge(), Slic3r::anonymous_namespace{PrintConfig.cpp}::project_bed_material_keepouts(), Slic3r::GUI::GLGizmoCut3D::render_angle_input(), Slic3r::GUI::GLGizmoTextureDisplacement::render_painted_colors(), Slic3r::GUI::GLGizmoPainterBase::render_triangles(), Slic3r::GUI::Bed_2D::repaint(), Slic3r::GUI::Camera::rotate_on_sphere(), Slic3r::GUI::Camera::rotate_on_sphere_with_target(), Slic3r::CLI::run(), Slic3r::TriangleSelector::seed_fill_select_triangles(), Slic3r::TriangleSelector::select_patch(), Slic3r::GUI::Camera::set_default_orientation(), Slic3r::GLVolumeCollection::set_default_slope_normal_z(), Slic3r::GUI::GLCanvas3D::Slope::set_normal_angle(), Slic3r::GUI::GLGizmoMeasure::set_to_around_center_of_faces(), Slic3r::spreadDotsArea(), Slic3r::WipeTower2::toolchange_Change(), and Slic3r::Print::validate_compacted_wipe_tower_clearance().

Here is the call graph for this function:

directions_parallel()

bool Slic3r::Geometry::directions_parallel	(	double	angle1,
		double	angle2,
		double	max_diff )

{
    double diff = fabs(angle1 - angle2);
    max_diff += EPSILON;
    return diff < max_diff || fabs(diff - PI) < max_diff;
}

References Slic3r::diff(), EPSILON, and PI.

Referenced by Slic3r::BridgeDetector::bridge_direction_candidates(), Slic3r::Line::parallel_to(), and Slic3r::BridgeDetector::unsupported_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

directions_perpendicular()

bool Slic3r::Geometry::directions_perpendicular	(	double	angle1,
		double	angle2,
		double	max_diff )

{
    double diff = fabs(angle1 - angle2);
    max_diff += EPSILON;
    return fabs(diff - 0.5 * PI) < max_diff || fabs(diff - 1.5 * PI) < max_diff;
}

References Slic3r::diff(), EPSILON, and PI.

Referenced by Slic3r::Line::perpendicular_to().

Here is the call graph for this function:

Here is the caller graph for this function:

dist()

template<typename T>

T Slic3r::Geometry::dist	(	const boost::polygon::point_data< T > &	p1,
		const boost::polygon::point_data< T > &	p2 )

{
  T dx = p2(0) - p1(0);
  T dy = p2(1) - p1(1);
  return sqrt(dx*dx+dy*dy);
}

Referenced by Slic3r::FanMover::_process_gcode_line(), Slic3r::GUI::anonymous_namespace{McpControl.cpp}::action_chamfer(), Slic3r::sla::ConcaveHull::add_connector_rectangles(), arrange(), Slic3r::tex2color::color_utils::calc_nearest_color_id(), Slic3r::chain_points_with_postprocessing(), Slic3r::chain_segments_greedy_constrained_reversals2_(), Slic3r::clip_extrusion(), Slic3r::sla::cluster(), Slic3r::sla::cluster(), Slic3r::sla::SupportTreeBuildsteps::connect_to_model_body(), Slic3r::contour_distance(), Slic3r::contour_distance2(), Slic3r::contour_extrusion_path(), Slic3r::cut_mesh_at_steps(), Slic3r::KDTreeIndirect< 3, float, SeamPlacerImpl::SeamCandidateCoordinateFunctor >::descent_mask(), Slic3r::AABBTreeLines::LinesDistancer< Linef3 >::distance_from_lines(), Slic3r::sla::anonymous_namespace{Clustering.cpp}::distance_queryfn(), Slic3r::GUI::DesignSketchTool::drag_rib_handle(), Slic3r::Model::duplicate_objects_grid(), Slic3r::GCode::extrude_loop(), Slic3r::GCode::extrude_path(), Slic3r::find_closest_points(), Slic3r::sla::anonymous_namespace{Rotfinder.cpp}::find_min_score(), Slic3r::find_nearby_points(), Slic3r::follow_slope_down(), Slic3r::WipeTower2::generate_support_cone_wall(), Slic3r::Measure::MeasuringImpl::get_feature(), Slic3r::sla::DrainHole::get_intersections(), Slic3r::Measure::get_measurement(), Slic3r::get_real_skirt_dist(), Slic3r::arrangement::get_shrink_bedpts(), Slic3r::Arachne::SkeletalTrapezoidation::getNearestBeading(), Slic3r::Arachne::SkeletalTrapezoidation::getOrCreateBeading(), Slic3r::MultiPoint::has_boundary_point(), Slic3r::improve_chain_by_local_search(), Slic3r::improve_cycle_by_or_opt(), Slic3r::Arachne::SkeletalTrapezoidationGraph::insertRib(), Slic3r::TriangleSelector::Capsule2D::is_edge_inside_cursor(), Slic3r::sla::DrainHole::is_inside(), Slic3r::ConflictChecker::line_intersect(), Slic3r::Arachne::SkeletalTrapezoidationGraph::makeRib(), Slic3r::GUI::GLGizmoTextureDisplacement::mark_seam_path(), measure_edge_thickness(), Slic3r::FillAdaptive::multiline_paths(), Slic3r::SpiralVaseHelpers::nearest_point_on_line(), Slic3r::SpiralVaseHelpers::nearest_point_on_lines(), Slic3r::arrangement::AutoArranger< TBin >::objfunc(), Slic3r::Voronoi::offset(), Slic3r::GUI::UVEditorCanvas::on_mouse(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::patch_boundary_distance(), Slic3r::TimelapsePosPicker::pick_nearest_object_center(), Slic3r::pick_pos_internal(), Slic3r::SeamPlacer::place_seam(), Slic3r::TreeSupport::plan_layer_heights(), Slic3r::SketchConstraints::point_line_distance(), Slic3r::TreeSupport3D::polyline_sample_next_point_at_distance(), Slic3r::SpiralVase::process_layer(), Slic3r::projection_onto(), Slic3r::PrintObjectSupportMaterial::raft_and_intermediate_support_layers(), Slic3r::anonymous_namespace{OrcaCloudServiceAgent.cpp}::random_bytes(), Slic3r::Feature::FuzzySkin::random_value(), Slic3r::GUI::GLGizmoTextureDisplacement::rank_mixes(), Slic3r::GUI::TexturePreviewCanvas::render(), Slic3r::resample_polygon(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::scan_steps(), Slic3r::separated_body_at(), Slic3r::GUI::GLGizmoMeasure::set_parallel_distance(), Slic3r::GUI::CommonGizmosDataObjects::ObjectClipper::set_position_by_ratio(), Slic3r::Voronoi::signed_vertex_distances(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::simplify_polyline(), Slic3r::solve_system(), Slic3r::sort_extra_perimeters(), Slic3r::MinCostMaxFlow::spfa(), Slic3r::AABBMesh::AABBImpl::squared_distance(), Slic3r::sla::IndexedMesh::AABBImpl::squared_distance(), Slic3r::Arachne::PolylineStitcher< Paths, Path, Junction >::stitch(), Slic3r::GeometryEngine::surface_deviation(), Slic3r::thick_lines_to_geometry(), Slic3r::WipeTower2::toolchange_Unload(), Slic3r::WipeTower::toolchange_Unload(), Slic3r::tsp_exact_cycle(), Slic3r::GUI::GLGizmoCut3D::update_clipper(), Slic3r::GUI::DesignCanvas::view_normal_to_sketch(), and Slic3r::visit_nearby_points().

encode_input_segment_endpoint()

VD::vertex_type::color_type Slic3r::Geometry::encode_input_segment_endpoint ( const VD::cell_type::source_index_type cell_source_index, const boost::polygon::direction_1d dir )

inline

{
    return (cell_source_index + 1) << 1 | (dir.to_int() ? 1 : 0);
}

Referenced by Slic3r::Geometry::VoronoiDiagram::try_to_repair_degenerated_voronoi_diagram_by_rotation().

Here is the caller graph for this function:

extract_euler_angles() [1/2]

Vec3d Slic3r::Geometry::extract_euler_angles

(

const Eigen::Matrix< double, 3, 3, Eigen::DontAlign > &

rotation_matrix

)

{
    // The extracted "rotation" is a triplet of numbers such that Geometry::rotation_transform
    // returns the original transform. Because of the chosen order of rotations, the triplet
    // is not equivalent to Euler angles in the usual sense.
    Vec3d angles = rotation_matrix.eulerAngles(2,1,0);
    std::swap(angles(0), angles(2));
    return angles;
}

Referenced by extract_euler_angles(), Slic3r::Geometry::Transformation::get_rotation(), Slic3r::ModelVolume::rotate(), Slic3r::ModelInstance::rotate_assemble(), Slic3r::Geometry::Transformation::set_rotation(), Slic3r::GUI::GLGizmoMeasure::set_to_parallel(), and Slic3r::Geometry::Transformation::volume_to_bed_transformation().

Here is the caller graph for this function:

extract_euler_angles() [2/2]

Vec3d Slic3r::Geometry::extract_euler_angles

(

const Transform3d &

transform

)

{
    // use only the non-translational part of the transform
    Eigen::Matrix<double, 3, 3, Eigen::DontAlign> m = transform.matrix().block(0, 0, 3, 3);
    // remove scale
    m.col(0).normalize();
    m.col(1).normalize();
    m.col(2).normalize();
    return extract_euler_angles(m);
}

References extract_euler_angles(), and Slic3r::transform().

Here is the call graph for this function:

extract_rotation_matrix()

Transform3d Slic3r::Geometry::extract_rotation_matrix ( const Transform3d & trafo )

static

{
    return extract_rotation_scale(trafo).first;
}

References extract_rotation_scale().

Referenced by Slic3r::Geometry::Transformation::get_rotation(), Slic3r::Geometry::Transformation::get_rotation_matrix(), and Slic3r::Geometry::Transformation::set_scaling_factor().

Here is the call graph for this function:

Here is the caller graph for this function:

extract_rotation_scale()

std::pair< Transform3d, Transform3d > Slic3r::Geometry::extract_rotation_scale ( const Transform3d & trafo )

static

{
    Matrix3d rotation;
    Matrix3d scale;
    if (trafo.linear().determinant() >= 0.0) {
        trafo.computeRotationScaling(&rotation, &scale);
        return { Transform3d(rotation), Transform3d(scale) };
    }
    for (int axis = 0; axis < 3; ++axis) {
        Transform3d flipped = trafo;
        flipped.linear().col(axis) *= -1.0;
        Matrix3d r;
        Matrix3d s;
        flipped.computeRotationScaling(&r, &s);
        // EPSILON keeps the lowest axis on ties, e.g. a mirror rotated by 90 degrees.
        if (axis == 0 || r.trace() > rotation.trace() + EPSILON) {
            rotation = r;
            scale    = s;
            scale.col(axis) *= -1.0;
        }
    }
    return { Transform3d(rotation), Transform3d(scale) };
}

References EPSILON, and scale().

Referenced by extract_rotation_matrix(), extract_scale(), Slic3r::Geometry::Transformation::set_mirror(), Slic3r::Geometry::Transformation::set_mirror(), Slic3r::Geometry::Transformation::set_rotation(), and Slic3r::Geometry::Transformation::set_scaling_factor().

Here is the call graph for this function:

Here is the caller graph for this function:

extract_scale()

Transform3d Slic3r::Geometry::extract_scale ( const Transform3d & trafo )

static

{
    return extract_rotation_scale(trafo).second;
}

References extract_rotation_scale().

Referenced by contains_skew(), Slic3r::Geometry::Transformation::get_mirror(), Slic3r::Geometry::Transformation::get_mirror_matrix(), Slic3r::Geometry::Transformation::get_scaling_factor(), Slic3r::Geometry::Transformation::get_scaling_factor_matrix(), and Slic3r::Geometry::Transformation::set_rotation().

Here is the call graph for this function:

Here is the caller graph for this function:

fit_catmul_rom_spline()

template<int Dimension, typename NumberType>

PiecewiseFittedCurve< Dimension, NumberType, CubicCatmulRomKernel< NumberType > > Slic3r::Geometry::fit_catmul_rom_spline	(	const std::vector< Vec< Dimension, NumberType > > &	observations,
		std::vector< NumberType >	observation_points,
		std::vector< NumberType >	weights,
		size_t	segments_count,
		size_t	endpoints_level_of_freedom = 0 )

                                               {
    return fit_curve<CubicCatmulRomKernel<NumberType>>(observations, observation_points, weights, segments_count,
            endpoints_level_of_freedom);
}

References fit_curve().

Here is the call graph for this function:

fit_cubic_bspline()

template<int Dimension, typename NumberType>

PiecewiseFittedCurve< Dimension, NumberType, CubicBSplineKernel< NumberType > > Slic3r::Geometry::fit_cubic_bspline	(	const std::vector< Vec< Dimension, NumberType > > &	observations,
		std::vector< NumberType >	observation_points,
		std::vector< NumberType >	weights,
		size_t	segments_count,
		size_t	endpoints_level_of_freedom = 0 )

                                               {
    return fit_curve<CubicBSplineKernel<NumberType>>(observations, observation_points, weights, segments_count,
            endpoints_level_of_freedom);
}

References fit_curve().

Referenced by Slic3r::SeamPlacer::align_seam_points().

Here is the call graph for this function:

Here is the caller graph for this function:

fit_curve()

template<typename Kernel, int Dimension, typename NumberType>

PiecewiseFittedCurve< Dimension, NumberType, Kernel > Slic3r::Geometry::fit_curve	(	const std::vector< Vec< Dimension, NumberType > > &	observations,
		const std::vector< NumberType > &	observation_points,
		const std::vector< NumberType > &	weights,
		size_t	segments_count,
		size_t	endpoints_level_of_freedom )

                                           {
 
    // check to make sure inputs are correct
    assert(segments_count > 0);
    assert(observations.size() > 0);
    assert(observation_points.size() == observations.size());
    assert(observation_points.size() == weights.size());
    assert(segments_count <= observations.size());
 
    //prepare sqrt of weights, which will then be applied to both matrix T and observed data: https://en.wikipedia.org/wiki/Weighted_least_squares
    std::vector<NumberType> sqrt_weights(weights.size());
    for (size_t index = 0; index < weights.size(); ++index) {
        assert(weights[index] > 0);
        sqrt_weights[index] = sqrt(weights[index]);
    }
 
    // prepare result and compute metadata
    PiecewiseFittedCurve<Dimension, NumberType, Kernel> result { };
 
    NumberType valid_length = observation_points.back() - observation_points.front();
    NumberType segment_size = valid_length / NumberType(segments_count);
    result.start = observation_points.front();
    result.segment_size = segment_size;
    result.endpoints_level_of_freedom = endpoints_level_of_freedom;
 
    // prepare observed data
    // Eigen defaults to column major memory layout.
    Eigen::MatrixXf data_points(Dimension, observations.size());
    for (size_t index = 0; index < observations.size(); ++index) {
        data_points.col(index) = observations[index] * sqrt_weights[index];
    }
    // parameters count is always increased by one to make the parametric space of the curve symmetric.
    // without this fix, the end of the curve is less flexible than the beginning
    size_t parameters_count = segments_count + 1 + 2 * endpoints_level_of_freedom;
    //Create weight matrix T for each point and each segment;
    Eigen::MatrixXf T(observation_points.size(), parameters_count);
    T.setZero();
    //Fill the weight matrix
    for (size_t i = 0; i < observation_points.size(); ++i) {
        NumberType observation_point = observation_points[i];
        //find corresponding segment index; expects kernels to be centered
        int middle_right_segment_index = floor((observation_point - result.start) / result.segment_size);
        //find index of first segment that is affected by the point i; this can be deduced from kernel_span
        int start_segment_idx = middle_right_segment_index - int(Kernel::kernel_span / 2) + 1;
        for (int segment_index = start_segment_idx; segment_index < int(start_segment_idx + Kernel::kernel_span);
                segment_index++) {
            NumberType segment_start = result.start + segment_index * result.segment_size;
            NumberType normalized_segment_distance = (segment_start - observation_point) / result.segment_size;
 
            int parameter_index = segment_index + endpoints_level_of_freedom;
            parameter_index = std::clamp(parameter_index, 0, int(parameters_count) - 1);
            T(i, parameter_index) += Kernel::kernel(normalized_segment_distance) * sqrt_weights[i];
        }
    }
 
#ifdef LSQR_DEBUG
    std::cout << "weight matrix: " << std::endl;
    for (int obs = 0; obs < observation_points.size(); ++obs) {
        std::cout << std::endl;
        for (int segment = 0; segment < parameters_count; ++segment) {
            std::cout << T(obs, segment) << "  ";
        }
    }
    std::cout << std::endl;
#endif
 
    // Solve for linear least square fit
    result.coefficients.resize(Dimension, parameters_count);
    const auto QR = T.fullPivHouseholderQr();
    for (size_t dim = 0; dim < Dimension; ++dim) {
        result.coefficients.row(dim) = QR.solve(data_points.row(dim).transpose());
    }
 
    return result;
}

References Slic3r::Geometry::PiecewiseFittedCurve< Dimension, NumberType, KernelType >::coefficients, Slic3r::Geometry::PiecewiseFittedCurve< Dimension, NumberType, KernelType >::endpoints_level_of_freedom, Slic3r::Geometry::PiecewiseFittedCurve< Dimension, NumberType, KernelType >::segment_size, and Slic3r::Geometry::PiecewiseFittedCurve< Dimension, NumberType, KernelType >::start.

Referenced by fit_catmul_rom_spline(), fit_cubic_bspline(), and fit_linear_spline().

Here is the caller graph for this function:

fit_linear_spline()

template<int Dimension, typename NumberType>

PiecewiseFittedCurve< Dimension, NumberType, LinearKernel< NumberType > > Slic3r::Geometry::fit_linear_spline	(	const std::vector< Vec< Dimension, NumberType > > &	observations,
		std::vector< NumberType >	observation_points,
		std::vector< NumberType >	weights,
		size_t	segments_count,
		size_t	endpoints_level_of_freedom = 0 )

                                               {
    return fit_curve<LinearKernel<NumberType>>(observations, observation_points, weights, segments_count,
            endpoints_level_of_freedom);
}

References fit_curve().

Here is the call graph for this function:

fit_polynomial()

template<int Dimension, typename NumberType>

PolynomialCurve< Dimension, NumberType > Slic3r::Geometry::fit_polynomial	(	const std::vector< Vec< Dimension, NumberType > > &	observations,
		const std::vector< NumberType > &	observation_points,
		const std::vector< NumberType > &	weights,
		size_t	order )

                                                            {
    // check to make sure inputs are correct
    size_t cols = order + 1;
    assert(observation_points.size() >= cols);
    assert(observation_points.size() == weights.size());
    assert(observations.size() == weights.size());
 
    Eigen::MatrixXf data_points(Dimension, observations.size());
    Eigen::MatrixXf T(observations.size(), cols);
    for (size_t i = 0; i < weights.size(); ++i) {
        auto squared_weight = sqrt(weights[i]);
        data_points.col(i) = observations[i] * squared_weight;
        // Populate the matrix
        auto x = squared_weight;
        auto c = observation_points[i];
        for (size_t j = 0; j < cols; ++j, x *= c)
            T(i, j) = x;
    }
 
    const auto QR = T.householderQr();
    Eigen::MatrixXf coefficients(Dimension, cols);
    // Solve for linear least square fit
    for (size_t dim = 0; dim < Dimension; ++dim) {
        coefficients.row(dim) = QR.solve(data_points.row(dim).transpose());
    }
 
    return {std::move(coefficients)};
}

foot_pt() [1/2]

Vec2d Slic3r::Geometry::foot_pt ( const Line & iline, const Point & ipt )

inline

{
    return foot_pt<Vec2d>(iline.a.cast<double>(), (iline.b - iline.a).cast<double>(), ipt.cast<double>());
}

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

Here is the call graph for this function:

foot_pt() [2/2]

template<typename T>

T Slic3r::Geometry::foot_pt ( const T & line_pt, const T & line_dir, const T & pt )

inline

{
    T      v   = pt - line_pt;
    auto   l2  = line_dir.squaredNorm();
    auto   t   = (l2 == 0) ? 0 : v.dot(line_dir) / l2;
    return line_pt + line_dir * t;
}

References Slic3r::l2().

Referenced by Slic3r::Voronoi::detail::dist_to_site(), Slic3r::Voronoi::edge_offset_contour_intersections(), Slic3r::foot_pt(), Slic3r::foot_pt(), foot_pt(), Slic3r::ExtrusionLoop::get_closest_path_and_point(), Slic3r::Voronoi::detail::line_point_equal_distance_points(), Slic3r::Voronoi::detail::point_segment_dr_dl_thresholds(), Slic3r::Voronoi::detail::point_segment_skeleton_thresholds(), Slic3r::TreeSupport3D::polyline_sample_next_point_at_distance(), ray_point_distance(), ray_point_distance(), ray_point_distance_squared(), and ray_point_distance_squared().

Here is the call graph for this function:

Here is the caller graph for this function:

generate_transform()

Transformation Slic3r::Geometry::generate_transform	(	const Vec3d &	x_dir,
		const Vec3d &	y_dir,
		const Vec3d &	z_dir,
		const Vec3d &	origin )

                                                                                                                   {
     Matrix3d m;
     m.col(0) = x_dir.normalized();
     m.col(1) = y_dir.normalized();
     m.col(2) = z_dir.normalized();
     Transform3d    mm(m);
     Transformation tran(mm);
     tran.set_offset(origin);
     return tran;
}

References Slic3r::Geometry::Transformation::set_offset().

Here is the call graph for this function:

get_parabolic_segment()

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, ParabolicSegment >::type Slic3r::Geometry::get_parabolic_segment ( const VD::edge_type & edge, const SegmentIterator segment_begin, const SegmentIterator segment_end )

inlinestatic

{
    using Segment = typename std::iterator_traits<SegmentIterator>::value_type;
    assert(edge.is_curved());
 
    const VD::cell_type *left_cell  = edge.cell();
    const VD::cell_type *right_cell = edge.twin()->cell();
 
    const Point       focus_pt   = VoronoiUtils::get_source_point(*(left_cell->contains_point() ? left_cell : right_cell), segment_begin, segment_end);
    const Segment    &directrix  = VoronoiUtils::get_source_segment(*(left_cell->contains_point() ? right_cell : left_cell), segment_begin, segment_end);
    CGAL::Orientation focus_side = CGAL::opposite(CGAL::orientation(to_cgal_point(edge.vertex0()), to_cgal_point(edge.vertex1()), to_cgal_point(focus_pt)));
 
    assert(focus_side == CGAL::Orientation::LEFT_TURN || focus_side == CGAL::Orientation::RIGHT_TURN);
 
    const Point directrix_from = boost::polygon::segment_traits<Segment>::get(directrix, boost::polygon::LOW);
    const Point directrix_to   = boost::polygon::segment_traits<Segment>::get(directrix, boost::polygon::HIGH);
    return {focus_pt, Line(directrix_from, directrix_to), make_linef(edge), focus_side};
}

References Slic3r::Geometry::VoronoiUtils::get_source_point(), Slic3r::Geometry::VoronoiUtils::get_source_segment(), make_linef(), and to_cgal_point().

Referenced by orientation_of_two_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

inside_convex_polygon()

bool Slic3r::Geometry::inside_convex_polygon	(	const std::pair< std::vector< Vec2d >, std::vector< Vec2d > > &	top_bottom_decomposition,
		const Vec2d &	pt )

{
    auto it_bottom = std::lower_bound(top_bottom_decomposition.first.begin(),  top_bottom_decomposition.first.end(),  pt, [](const auto &l, const auto &r){ return l.x() < r.x(); });
    auto it_top    = std::lower_bound(top_bottom_decomposition.second.begin(), top_bottom_decomposition.second.end(), pt, [](const auto &l, const auto &r){ return l.x() < r.x(); });
    if (it_bottom == top_bottom_decomposition.first.end()) {
        // Above max x.
        assert(it_top == top_bottom_decomposition.second.end());
        return false;
    }
    if (it_bottom == top_bottom_decomposition.first.begin()) {
        // Below or at min x.
        if (pt.x() < it_bottom->x()) {
            // Below min x.
            assert(pt.x() < it_top->x());
            return false;
        }
        // At min x.
        assert(pt.x() == it_bottom->x());
        assert(pt.x() == it_top->x());
        assert(it_bottom->y() <= pt.y() && pt.y() <= it_top->y());
        return pt.y() >= it_bottom->y() && pt.y() <= it_top->y();
    }
 
    // Trapezoid or a triangle.
    assert(it_bottom != top_bottom_decomposition.first .begin() && it_bottom != top_bottom_decomposition.first .end());
    assert(it_top    != top_bottom_decomposition.second.begin() && it_top    != top_bottom_decomposition.second.end());
    assert(pt.x() <= it_bottom->x());
    assert(pt.x() <= it_top->x());
    auto it_top_prev    = it_top - 1;
    auto it_bottom_prev = it_bottom - 1;
    assert(pt.x() >= it_top_prev->x());
    assert(pt.x() >= it_bottom_prev->x());
    double det = cross2(*it_bottom - *it_bottom_prev, pt - *it_bottom_prev);
    if (det < 0)
        return false;
    det = cross2(*it_top - *it_top_prev, pt - *it_top_prev);
    return det <= 0;
}

References Slic3r::cross2().

Referenced by Slic3r::BuildVolume::object_state().

Here is the call graph for this function:

Here is the caller graph for this function:

is_ccw()

bool Slic3r::Geometry::is_ccw ( const Polygon & poly )

inlinestatic

{
    // The polygon shall be at least a triangle.
    assert(poly.points.size() >= 3);
    if (poly.points.size() < 3)
        return true;
 
    // 1) Find the lowest lexicographical point.
    unsigned int imin = 0;
    for (unsigned int i = 1; i < poly.points.size(); ++ i) {
        const Point &pmin = poly.points[imin];
        const Point &p    = poly.points[i];
        if (p(0) < pmin(0) || (p(0) == pmin(0) && p(1) < pmin(1)))
            imin = i;
    }
 
    // 2) Detect the orientation of the corner imin.
    size_t iPrev = ((imin == 0) ? poly.points.size() : imin) - 1;
    size_t iNext = ((imin + 1 == poly.points.size()) ? 0 : imin + 1);
    Orientation o = orient(poly.points[iPrev], poly.points[imin], poly.points[iNext]);
    // The lowest bottom point must not be collinear if the polygon does not contain duplicate points
    // or overlapping segments.
    assert(o != ORIENTATION_COLINEAR);
    return o == ORIENTATION_CCW;
}

References orient(), ORIENTATION_CCW, and ORIENTATION_COLINEAR.

Referenced by Slic3r::ExPolygonWithOffset::ExPolygonWithOffset(), Slic3r::GCodeG2G3Formatter::GCodeG2G3Formatter(), Slic3r::Geometry::ArcWelder::arc_center(), Slic3r::ArcSegment::calc_arc_length(), Slic3r::ArcSegment::calc_arc_radian(), Slic3r::Circle::calc_tangential_vector(), Slic3r::GCodeWriter::extrude_arc_as_polyline(), Slic3r::GCodeWriter::extrude_arc_to_xy(), Slic3r::GCodeWriter::extrude_arc_to_xy(), Slic3r::GCode::extrude_loop(), Slic3r::CoolingBuffer::parse_layer_gcode(), Slic3r::rounding_polygon(), Slic3r::WipeTower::rounding_polygon(), Slic3r::rounding_rectangle(), Slic3r::wipe_offset_direction(), and Slic3r::wipe_on_loops_destination().

Here is the call graph for this function:

Here is the caller graph for this function:

is_equal()

bool Slic3r::Geometry::is_equal ( const VD::vertex_type & vertex_first, const VD::vertex_type & vertex_second )

inline

{ return vertex_first.x() == vertex_second.x() && vertex_first.y() == vertex_second.y(); }

Referenced by check_if_three_edges_are_ccw(), Slic3r::cut_mesh(), Slic3r::is_equal(), orientation_of_two_edges(), Slic3r::slice_facet_for_cut_mesh(), and Slic3r::triangulate_slice().

Here is the caller graph for this function:

is_point_inside_polygon_corner()

bool Slic3r::Geometry::is_point_inside_polygon_corner	(	const Point &	a,
		const Point &	b,
		const Point &	c,
		const Point &	query_point )

Checks if a given point is inside a corner of a polygon.

The corner of a polygon is defined by three points A, B, C in counterclockwise order.

Adapted from CuraEngine LinearAlg2D::isInsideCorner by Tim Kuipers @BagelOrb and @Ghostkeeper.

Parameters

a	The first point of the corner.
b	The second point of the corner (the common vertex of the two edges forming the corner).
c	The third point of the corner.
query_point	The point to be checked if is inside the corner.

Returns

True if the query point is inside the corner, false otherwise.

                                                                                                              {
    // Cast all input points into int64_t to prevent overflows when points are close to max values of coord_t.
    const Vec2i64 a_i64           = a.cast<int64_t>();
    const Vec2i64 b_i64           = b.cast<int64_t>();
    const Vec2i64 c_i64           = c.cast<int64_t>();
    const Vec2i64 query_point_i64 = query_point.cast<int64_t>();
 
    // Shift all points to have a base in vertex B.
    // Then construct normalized vectors to ensure that we will work with vectors with endpoints on the unit circle.
    const Vec2d ba = (a_i64 - b_i64).cast<double>().normalized();
    const Vec2d bc = (c_i64 - b_i64).cast<double>().normalized();
    const Vec2d bq = (query_point_i64 - b_i64).cast<double>().normalized();
 
    // Points A and C has to be different.
    assert(ba != bc);
 
    // Construct a normal for the vector BQ that points to the left side of the vector BQ.
    const Vec2d bq_left_normal = perp(bq);
 
    const double proj_a_on_bq_normal = ba.dot(bq_left_normal); // Project point A on the normal of BQ.
    const double proj_c_on_bq_normal = bc.dot(bq_left_normal); // Project point C on the normal of BQ.
    if ((proj_a_on_bq_normal > 0. && proj_c_on_bq_normal <= 0.) || (proj_a_on_bq_normal <= 0. && proj_c_on_bq_normal > 0.)) {
        // Q is between points A and C or lies on one of those vectors (BA or BC).
 
        // Based on the CCW order of polygons (contours) and order of corner ABC,
        // when this condition is met, the query point is inside the corner.
        return proj_a_on_bq_normal > 0.;
    } else {
        // Q isn't between points A and C, but still it can be inside the corner.
 
        const double proj_a_on_bq = ba.dot(bq); // Project point A on BQ.
        const double proj_c_on_bq = bc.dot(bq); // Project point C on BQ.
 
        // The value of proj_a_on_bq_normal is the same when we project the vector BA on the normal of BQ.
        // So we can say that the Q is on the right side of the vector BA when proj_a_on_bq_normal > 0, and
        // that the Q is on the left side of the vector BA proj_a_on_bq_normal < 0.
        // Also, the Q is on the right side of the bisector of oriented angle ABC when proj_c_on_bq < proj_a_on_bq, and
        // the Q is on the left side of the bisector of oriented angle ABC when proj_c_on_bq > proj_a_on_bq.
 
        // So the Q is inside the corner when one of the following conditions is met:
        //  * The Q is on the right side of the vector BA, and the Q is on the right side of the bisector of the oriented angle ABC.
        //  * The Q is on the left side of the vector BA, and the Q is on the left side of the bisector of the oriented angle ABC.
        return (proj_a_on_bq_normal > 0. && proj_c_on_bq < proj_a_on_bq) || (proj_a_on_bq_normal <= 0. && proj_c_on_bq >= proj_a_on_bq);
    }
}

References Slic3r::cast(), and Slic3r::perp().

Referenced by Slic3r::Geometry::VoronoiUtils::compute_point_cell_range().

Here is the call graph for this function:

Here is the caller graph for this function:

is_rotation_ninety_degrees() [1/2]

bool Slic3r::Geometry::is_rotation_ninety_degrees ( const Vec3d & rotation )

inline

{
    return is_rotation_ninety_degrees(rotation.x()) && is_rotation_ninety_degrees(rotation.y()) && is_rotation_ninety_degrees(rotation.z());
}

References is_rotation_ninety_degrees().

Here is the call graph for this function:

is_rotation_ninety_degrees() [2/2]

bool Slic3r::Geometry::is_rotation_ninety_degrees ( double a )

inline

{
    a = fmod(std::abs(a), 0.5 * PI);
    if (a > 0.25 * PI)
        a = 0.5 * PI - a;
    return a < 0.001;
}

References PI.

Referenced by Slic3r::ModelObject::bake_xy_rotation_into_meshes(), is_rotation_ninety_degrees(), and Slic3r::Geometry::Transformation::volume_to_bed_transformation().

Here is the caller graph for this function:

liang_barsky_line_clipping() [1/2]

template<typename T>

bool Slic3r::Geometry::liang_barsky_line_clipping	(	const Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &	x0src,
		const Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &	x1src,
		const BoundingBoxBase< Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > &	bbox,
		Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &	x0clip,
		Eigen::Matrix< T, 2, 1, Eigen::DontAlign > &	x1clip )

{
  x0clip = x0src;
  x1clip = x1src;
  return liang_barsky_line_clipping(x0clip, x1clip, bbox);
}

References liang_barsky_line_clipping().

Here is the call graph for this function:

liang_barsky_line_clipping() [2/2]

template<typename T>

bool Slic3r::Geometry::liang_barsky_line_clipping ( Eigen::Matrix< T, 2, 1, Eigen::DontAlign > & x0, Eigen::Matrix< T, 2, 1, Eigen::DontAlign > & x1, const BoundingBoxBase< Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > & bbox )

inline

{
    Eigen::Matrix<T, 2, 1, Eigen::DontAlign> v = x1 - x0;
    std::pair<double, double> interval;
    if (liang_barsky_line_clipping_interval(x0, v, bbox, interval)) {
        // Clipped successfully.
        x1  = x0 + interval.second * v;
        x0 += interval.first * v;
        return true;
    }
    return false;
}

References liang_barsky_line_clipping_interval().

Referenced by Slic3r::Line::clip_with_bbox(), liang_barsky_line_clipping(), Slic3r::FillAdaptive::multiline_paths(), and Slic3r::Voronoi::offset().

Here is the call graph for this function:

Here is the caller graph for this function:

liang_barsky_line_clipping_interval()

template<typename T>

bool Slic3r::Geometry::liang_barsky_line_clipping_interval ( const Eigen::Matrix< T, 2, 1, Eigen::DontAlign > & x0, const Eigen::Matrix< T, 2, 1, Eigen::DontAlign > & v, const BoundingBoxBase< Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > & bbox, std::pair< double, double > & out_interval )

inline

{
    double t0 = 0.0;
    double t1 = 1.0;
    // Traverse through left, right, bottom, top edges.
    auto clip_side = [&t0, &t1](double p, double q) -> bool {
        if (p == 0) {
            if (q < 0)
                // Line parallel to the bounding box edge is fully outside of the bounding box.
                return false;
            // else don't clip
        } else {
            double r = q / p;
            if (p < 0) {
                if (r > t1)
                    // Fully clipped.
                    return false;
                if (r > t0)
                    // Partially clipped.
                    t0 = r;
            } else {
                assert(p > 0);
                if (r < t0)
                    // Fully clipped.
                    return false;
                if (r < t1)
                    // Partially clipped.
                    t1 = r;
            }
        }
        return true;
    };
 
    if (clip_side(- v.x(), - bbox.min.x() + x0.x()) &&
        clip_side(  v.x(),   bbox.max.x() - x0.x()) &&
        clip_side(- v.y(), - bbox.min.y() + x0.y()) &&
        clip_side(  v.y(),   bbox.max.y() - x0.y())) {
        out_interval.first = t0;
        out_interval.second = t1;
        return true;
    }
    return false;
}

Referenced by liang_barsky_line_clipping(), and Slic3r::line_rounded_thick_segment_collision().

Here is the caller graph for this function:

linint()

double Slic3r::Geometry::linint	(	double	value,
		double	oldmin,
		double	oldmax,
		double	newmin,
		double	newmax )

{
    return (value - oldmin) * (newmax - newmin) / (oldmax - oldmin) + newmin;
}

Referenced by arrange().

Here is the caller graph for this function:

make_linef()

Linef Slic3r::Geometry::make_linef ( const VD::edge_type & edge )

inline

{
    const VD::vertex_type *v0 = edge.vertex0();
    const VD::vertex_type *v1 = edge.vertex1();
    return {Vec2d(v0->x(), v0->y()), Vec2d(v1->x(), v1->y())};
}

Referenced by get_parabolic_segment().

Here is the caller graph for this function:

mat_around_a_point_rotate()

Transformation Slic3r::Geometry::mat_around_a_point_rotate	(	const Transformation &	InMat,
		const Vec3d &	pt,
		const Vec3d &	axis,
		float	rotate_theta_radian )

{
    auto           xyz = InMat.get_offset();
    Transformation left;
    left.set_offset(-xyz); // at world origin
    auto curMat = left * InMat;
 
    auto qua = Eigen::Quaterniond(Eigen::AngleAxisd(rotate_theta_radian, axis));
    qua.normalize();
    Transform3d    cur_matrix;
    Transformation rotateMat4;
    rotateMat4.set_matrix(cur_matrix.fromPositionOrientationScale(Vec3d(0., 0., 0.), qua, Vec3d(1., 1., 1.)));
 
    curMat = rotateMat4 * curMat; // along_fix_axis
    // rotate mat4 along fix pt
    Transformation temp_world;
    auto           qua_world = Eigen::Quaterniond(Eigen::AngleAxisd(0, axis));
    qua_world.normalize();
    Transform3d cur_matrix_world;
    temp_world.set_matrix(cur_matrix_world.fromPositionOrientationScale(pt, qua_world, Vec3d(1., 1., 1.)));
    Vec3d temp_xyz = temp_world.get_matrix().inverse() * xyz;
    Vec3d new_pos  = temp_world.get_matrix() * (rotateMat4.get_matrix() * temp_xyz);
    curMat.set_offset(new_pos);
 
    return curMat;
}

References Slic3r::Geometry::Transformation::get_matrix(), Slic3r::Geometry::Transformation::get_offset(), and Slic3r::Geometry::Transformation::set_matrix().

Referenced by Slic3r::GUI::GLGizmoMeasure::set_to_around_center_of_faces(), and Slic3r::GUI::GLGizmoMeasure::set_to_reverse_rotation().

Here is the call graph for this function:

Here is the caller graph for this function:

measure_edge_thickness()

template<typename VD, typename SEGMENTS>

std::pair< typename VD::coord_type, typename VD::coord_type > Slic3r::Geometry::measure_edge_thickness ( const VD & vd, const typename VD::edge_type & edge, const SEGMENTS & segments )

inline

{
    typedef typename VD::coord_type T;
    const typename VD::point_type  pa(edge.vertex0()->x(), edge.vertex0()->y());
    const typename VD::point_type  pb(edge.vertex1()->x(), edge.vertex1()->y());
    const typename VD::cell_type  &cell1 = *edge.cell();
    const typename VD::cell_type  &cell2 = *edge.twin()->cell();
    if (cell1.contains_segment()) {
        if (cell2.contains_segment()) {
            // Both cells contain a linear segment, the left / right cells are symmetric.
            // Project pa, pb to the left segment.
            const typename VD::segment_type segment1 = segments[cell1.source_index()];
            const typename VD::point_type p1a = project_point_to_segment(segment1, pa);
            const typename VD::point_type p1b = project_point_to_segment(segment1, pb);
            return std::pair<T, T>(T(2.)*dist(pa, p1a), T(2.)*dist(pb, p1b));
        } else {
            // 1st cell contains a linear segment, 2nd cell contains a point.
            // The medial axis between the cells is a parabolic arc.
            // Project pa, pb to the left segment.
            const typename  VD::point_type p2 = retrieve_cell_point<VD>(cell2, segments);
            return std::pair<T, T>(T(2.)*dist(pa, p2), T(2.)*dist(pb, p2));
        }
    } else if (cell2.contains_segment()) {
        // 1st cell contains a point, 2nd cell contains a linear segment.
        // The medial axis between the cells is a parabolic arc.
        const typename VD::point_type p1 = retrieve_cell_point<VD>(cell1, segments);
        return std::pair<T, T>(T(2.)*dist(pa, p1), T(2.)*dist(pb, p1));
    } else {
        // Both cells contain a point. The left / right regions are triangular and symmetric.
        const typename VD::point_type p1 = retrieve_cell_point<VD>(cell1, segments);
        return std::pair<T, T>(T(2.)*dist(pa, p1), T(2.)*dist(pb, p1));
    }
}

References dist(), project_point_to_segment(), and retrieve_cell_point().

Here is the call graph for this function:

orient()

Orientation Slic3r::Geometry::orient ( const Point & a, const Point & b, const Point & c )

inlinestatic

                                                                                 {
    //static_assert(sizeof(coord_t) * 2 == sizeof(int64_t), "orient works with 32 bit coordinates");
    // BOOST_STATIC_ASSERT(sizeof(coord_t) == sizeof(int64_t));
    if (a.x() <= 0xffffffff && b.x() <= 0xffffffff && c.x() <= 0xffffffff &&
        a.y() <= 0xffffffff && b.y() <= 0xffffffff && c.y() <= 0xffffffff) {
        int64_t u = int64_t(b(0)) * int64_t(c(1)) - int64_t(b(1)) * int64_t(c(0));
        int64_t v = int64_t(a(0)) * int64_t(c(1)) - int64_t(a(1)) * int64_t(c(0));
        int64_t w = int64_t(a(0)) * int64_t(b(1)) - int64_t(a(1)) * int64_t(b(0));
        int64_t d = u - v + w;
        return (d > 0) ? ORIENTATION_CCW : ((d == 0) ? ORIENTATION_COLINEAR : ORIENTATION_CW);
    } else {
        double u = double(b(0)) * double(c(1)) - double(b(1)) * double(c(0));
        double v = double(a(0)) * double(c(1)) - double(a(1)) * double(c(0));
        double w = double(a(0)) * double(b(1)) - double(a(1)) * double(b(0));
        double d = u - v + w;
        return (d > 0) ? ORIENTATION_CCW : ((d == 0) ? ORIENTATION_COLINEAR : ORIENTATION_CW);
    }
}

References ORIENTATION_CCW, ORIENTATION_COLINEAR, and ORIENTATION_CW.

Referenced by convex_hull(), convex_hull(), Slic3r::GUI::ObjectGrid::DrawColLabel(), Slic3r::GUI::DesignSketchTool::drop_orientation_constraints(), is_ccw(), Slic3r::GeometryEngine::tessellate(), and Slic3r::SketchEngine::tessellate().

Here is the caller graph for this function:

orientation_of_two_edges()

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, CGAL::Orientation >::type Slic3r::Geometry::orientation_of_two_edges ( const VD::edge_type & edge_a, const VD::edge_type & edge_b, const SegmentIterator segment_begin, const SegmentIterator segment_end )

inlinestatic

{
    assert(is_equal(*edge_a.vertex0(), *edge_b.vertex0()));
    CGAL::Orientation orientation;
    if (edge_a.is_linear() && edge_b.is_linear()) {
        orientation = CGAL::orientation(to_cgal_point(edge_a.vertex0()), to_cgal_point(edge_a.vertex1()), to_cgal_point(edge_b.vertex1()));
    } else if (edge_a.is_curved() && edge_b.is_curved()) {
        const ParabolicSegment parabolic_a = get_parabolic_segment(edge_a, segment_begin, segment_end);
        const ParabolicSegment parabolic_b = get_parabolic_segment(edge_b, segment_begin, segment_end);
        orientation = ParabolicTangentToParabolicTangentOrientation{}(to_cgal_point(parabolic_a.segment.a),
                                                                      to_cgal_point(parabolic_a.focus),
                                                                      to_cgal_point(parabolic_a.directrix.a),
                                                                      to_cgal_point(parabolic_a.directrix.b),
                                                                      parabolic_a.is_focus_on_left,
                                                                      to_cgal_point(parabolic_b.focus),
                                                                      to_cgal_point(parabolic_b.directrix.a),
                                                                      to_cgal_point(parabolic_b.directrix.b),
                                                                      parabolic_b.is_focus_on_left);
        return orientation;
    } else {
        assert(edge_a.is_curved() != edge_b.is_curved());
 
        const VD::edge_type   &linear_edge    = edge_a.is_curved() ? edge_b : edge_a;
        const VD::edge_type   &parabolic_edge = edge_a.is_curved() ? edge_a : edge_b;
        const ParabolicSegment parabolic      = get_parabolic_segment(parabolic_edge, segment_begin, segment_end);
        orientation = ParabolicTangentToSegmentOrientation{}(to_cgal_point(parabolic.segment.a), to_cgal_point(linear_edge.vertex1()),
                                                             to_cgal_point(parabolic.focus),
                                                             to_cgal_point(parabolic.directrix.a),
                                                             to_cgal_point(parabolic.directrix.b),
                                                             parabolic.is_focus_on_left);
 
        if (edge_b.is_curved())
            orientation = CGAL::opposite(orientation);
    }
 
    return orientation;
}

References Slic3r::Line::a, Slic3r::Linef::a, Slic3r::Line::b, Slic3r::Geometry::ParabolicSegment::directrix, Slic3r::Geometry::ParabolicSegment::focus, get_parabolic_segment(), is_equal(), Slic3r::Geometry::ParabolicSegment::is_focus_on_left, Slic3r::Geometry::ParabolicSegment::segment, and to_cgal_point().

Referenced by check_if_three_edges_are_ccw().

Here is the call graph for this function:

Here is the caller graph for this function:

project_point_to_segment()

template<typename segment_type, typename point_type>

point_type Slic3r::Geometry::project_point_to_segment ( segment_type & seg, point_type & px )

inline

{
    typedef typename point_type::coordinate_type T;
    const point_type &p0 = low(seg);
    const point_type &p1 = high(seg);
    const point_type  dir(p1(0)-p0(0), p1(1)-p0(1));
    const point_type  dproj(px(0)-p0(0), px(1)-p0(1));
    const T           t = (dir(0)*dproj(0) + dir(1)*dproj(1)) / (dir(0)*dir(0) + dir(1)*dir(1));
    assert(t >= T(-1e-6) && t <= T(1. + 1e-6));
    return point_type(p0(0) + t*dir(0), p0(1) + t*dir(1));
}

Referenced by measure_edge_thickness().

Here is the caller graph for this function:

rad2deg()

template<typename T>

T Slic3r::Geometry::rad2deg

(

T

angle

)

{ return T(180.0) * angle / T(PI); }

References Slic3r::angle(), and PI.

Referenced by Slic3r::GUI::GLGizmoScale3D::calc_ratio(), Slic3r::BridgeDetector::coverage(), Slic3r::BridgeDetector::detect_angle(), Slic3r::GUI::Camera::get_fov(), Slic3r::GUI::GLGizmoCut3D::get_tooltip(), Slic3r::GUI::GLGizmoRotate::get_tooltip(), rad2deg_dir(), Slic3r::GUI::GLGizmoCut3D::render_angle_input(), Slic3r::GUI::GLGizmoMeasure::render_dimensioning(), Slic3r::TriangleMesh::rotate(), Slic3r::GUI::Camera::rotate_on_sphere(), Slic3r::GUI::Camera::rotate_on_sphere_with_target(), Slic3r::GUI::GLGizmoMeasure::show_distance_xyz_ui(), and Slic3r::GUI::Camera::update_zenit().

Here is the call graph for this function:

Here is the caller graph for this function:

rad2deg_dir()

double Slic3r::Geometry::rad2deg_dir

(

double

angle

)

{
    angle = (angle < PI) ? (-angle + PI/2.0) : (angle + PI/2.0);
    if (angle < 0) angle += PI;
    return rad2deg(angle);
}

References Slic3r::angle(), PI, and rad2deg().

Here is the call graph for this function:

ray_circle_intersections()

template<typename T>

int Slic3r::Geometry::ray_circle_intersections	(	T	r,
		T	a,
		T	b,
		T	c,
		std::pair< Eigen::Matrix< T, 2, 1, Eigen::DontAlign >, Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > &	out )

{
    T lv2 = a * a + b * b;
    if (lv2 < T(SCALED_EPSILON * SCALED_EPSILON)) {
        //FIXME what is the correct epsilon?
        // What if the line touches the circle?
        return false;
    }
    return ray_circle_intersections_r2_lv2_c2(r * r, a, b, a * a + b * b, c, out);
}

References SCALED_EPSILON.

ray_circle_intersections_r2_lv2_c()

template<typename T>

int Slic3r::Geometry::ray_circle_intersections_r2_lv2_c	(	T	r2,
		T	a,
		T	b,
		T	lv2,
		T	c,
		std::pair< Eigen::Matrix< T, 2, 1, Eigen::DontAlign >, Eigen::Matrix< T, 2, 1, Eigen::DontAlign > > &	out )

{
    T x0 = - a * c;
    T y0 = - b * c;
    T d2 = r2 * lv2 - c * c;
    if (d2 < T(0))
        return 0;
    T d = sqrt(d2);
    out.first.x() = (x0 + b * d) / lv2;
    out.first.y() = (y0 - a * d) / lv2;
    out.second.x() = (x0 - b * d) / lv2;
    out.second.y() = (y0 + a * d) / lv2;
    return d == T(0) ? 1 : 2;
}

Referenced by Slic3r::line_rounded_thick_segment_collision().

Here is the caller graph for this function:

ray_point_distance() [1/2]

double Slic3r::Geometry::ray_point_distance ( const Line & iline, const Point & ipt )

inline

{
    return (foot_pt(iline, ipt) - ipt.cast<double>()).norm();
}

References foot_pt().

Here is the call graph for this function:

ray_point_distance() [2/2]

template<typename T>

auto Slic3r::Geometry::ray_point_distance ( const T & ray_pt, const T & ray_dir, const T & pt )

inline

{
    return (foot_pt(ray_pt, ray_dir, pt) - pt).norm();
}

References foot_pt().

Referenced by Slic3r::Voronoi::detail::line_point_equal_distance_points(), and Slic3r::Voronoi::signed_vertex_distances().

Here is the call graph for this function:

Here is the caller graph for this function:

ray_point_distance_squared() [1/2]

double Slic3r::Geometry::ray_point_distance_squared ( const Line & iline, const Point & ipt )

inline

{
    return (foot_pt(iline, ipt) - ipt.cast<double>()).squaredNorm();
}

References foot_pt().

Here is the call graph for this function:

ray_point_distance_squared() [2/2]

template<typename T>

auto Slic3r::Geometry::ray_point_distance_squared ( const T & ray_pt, const T & ray_dir, const T & pt )

inline

{
    return (foot_pt(ray_pt, ray_dir, pt) - pt).squaredNorm();
}

References foot_pt().

Here is the call graph for this function:

ray_ray_intersection()

bool Slic3r::Geometry::ray_ray_intersection ( const Vec2d & p1, const Vec2d & v1, const Vec2d & p2, const Vec2d & v2, Vec2d & res )

inline

{
    double denom = v1(0) * v2(1) - v2(0) * v1(1);
    if (std::abs(denom) < EPSILON)
        return false;
    double t = (v2(0) * (p1(1) - p2(1)) - v2(1) * (p1(0) - p2(0))) / denom;
    res(0) = p1(0) + t * v1(0);
    res(1) = p1(1) + t * v1(1);
    return true;
}

References EPSILON.

retrieve_cell_point()

template<typename VD, typename SEGMENTS>

const VD::point_type Slic3r::Geometry::retrieve_cell_point ( const typename VD::cell_type & cell, const SEGMENTS & segments )

inline

{
    assert(cell.source_category() == boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT || cell.source_category() == boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT);
    return (cell.source_category() == boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT) ? low(segments[cell.source_index()]) : high(segments[cell.source_index()]);
}

Referenced by measure_edge_thickness().

Here is the caller graph for this function:

rotation_diff_z()

double Slic3r::Geometry::rotation_diff_z	(	const Vec3d &	rot_xyz_from,
		const Vec3d &	rot_xyz_to )

{
    const Eigen::AngleAxisd angle_axis(rotation_xyz_diff(rot_xyz_from, rot_xyz_to));
    const Vec3d  axis  = angle_axis.axis();
    const double angle = angle_axis.angle();
#ifndef NDEBUG
    if (std::abs(angle) > 1e-8) {
        assert(std::abs(axis.x()) < 1e-8);
        assert(std::abs(axis.y()) < 1e-8);
    }
#endif /* NDEBUG */
    return (axis.z() < 0) ? -angle : angle;
}

References Slic3r::angle(), and rotation_xyz_diff().

Referenced by Slic3r::PrintObject::PrintObject(), Slic3r::ModelObject::bake_xy_rotation_into_meshes(), and Slic3r::sla_instances().

Here is the call graph for this function:

Here is the caller graph for this function:

rotation_from_two_vectors()

void Slic3r::Geometry::rotation_from_two_vectors	(	Vec3d	from,
		Vec3d	to,
		Vec3d &	rotation_axis,
		double &	phi,
		Matrix3d *	rotation_matrix )

{
    const Matrix3d m = Eigen::Quaterniond().setFromTwoVectors(from, to).toRotationMatrix();
    const Eigen::AngleAxisd aa(m);
    rotation_axis = aa.axis();
    phi           = aa.angle();
    if (rotation_matrix)
        *rotation_matrix = m;
}

Referenced by Slic3r::orientation::_orient(), Slic3r::orientation::orient(), Slic3r::orientation::orient(), Slic3r::orientation::orient_for_cooling(), and Slic3r::GUI::GLGizmoMeasure::set_to_parallel().

Here is the caller graph for this function:

rotation_transform() [1/2]

Transform3d Slic3r::Geometry::rotation_transform

(

const Vec3d &

rotation

)

{
    Transform3d transform;
    rotation_transform(transform, rotation);
    return transform;
}

References rotation_transform(), and Slic3r::transform().

Here is the call graph for this function:

rotation_transform() [2/2]

void Slic3r::Geometry::rotation_transform	(	Transform3d &	transform,
		const Vec3d &	rotation )

{
    transform = Transform3d::Identity();
    transform.rotate(Eigen::AngleAxisd(rotation.z(), Vec3d::UnitZ()) * Eigen::AngleAxisd(rotation.y(), Vec3d::UnitY()) * Eigen::AngleAxisd(rotation.x(), Vec3d::UnitX()));
}

References Slic3r::transform().

Referenced by Slic3r::GUI::GLCanvas3D::_render_3d_navigator(), Slic3r::GUI::GLGizmoCut3D::apply_cut_connectors(), Slic3r::apply_tolerance(), Slic3r::GUI::GLGizmoCut3D::dragging_grabber_rotation(), Slic3r::GUI::GLGizmoCut3D::flip_cut_plane(), Slic3r::GUI::GLGizmoRotate::local_transform(), Slic3r::Cut::perform_with_groove(), Slic3r::GUI::GCodeViewer::SequentialView::Marker::render(), Slic3r::GUI::GLGizmoCut3D::render_connectors(), Slic3r::GUI::GLGizmoCut3D::render_cut_plane_grabbers(), Slic3r::GUI::GLGizmoCut3D::render_rotation_snapping(), Slic3r::reset_instance_transformation(), Slic3r::GUI::Selection::rotate(), rotation_transform(), Slic3r::Geometry::Transformation::set_rotation(), Slic3r::Geometry::Transformation::set_rotation(), and Slic3r::GUI::GLGizmoCut3D::update_raycasters_for_picking_transform().

Here is the call graph for this function:

Here is the caller graph for this function:

rotation_xyz_diff()

Eigen::Quaterniond Slic3r::Geometry::rotation_xyz_diff	(	const Vec3d &	rot_xyz_from,
		const Vec3d &	rot_xyz_to )

{
    return
        // From the current coordinate system to world.
        Eigen::AngleAxisd(rot_xyz_to.z(), Vec3d::UnitZ()) * Eigen::AngleAxisd(rot_xyz_to.y(), Vec3d::UnitY()) * Eigen::AngleAxisd(rot_xyz_to.x(), Vec3d::UnitX()) *
        // From world to the initial coordinate system.
        Eigen::AngleAxisd(-rot_xyz_from.x(), Vec3d::UnitX()) * Eigen::AngleAxisd(-rot_xyz_from.y(), Vec3d::UnitY()) * Eigen::AngleAxisd(-rot_xyz_from.z(), Vec3d::UnitZ());
}

Referenced by rotation_diff_z().

Here is the caller graph for this function:

scale_transform() [1/4]

Transform3d Slic3r::Geometry::scale_transform

(

const Vec3d &

scale

)

{
    Transform3d transform;
    scale_transform(transform, scale);
    return transform;
}

References scale(), scale_transform(), and Slic3r::transform().

Here is the call graph for this function:

scale_transform() [2/4]

Transform3d Slic3r::Geometry::scale_transform

(

double

scale

)

{
    return scale_transform(scale * Vec3d::Ones());
}

References scale(), and scale_transform().

Here is the call graph for this function:

scale_transform() [3/4]

void Slic3r::Geometry::scale_transform	(	Transform3d &	transform,
		const Vec3d &	scale )

{
    transform = Transform3d::Identity();
    transform.scale(scale);
}

References scale(), and Slic3r::transform().

Here is the call graph for this function:

scale_transform() [4/4]

void Slic3r::Geometry::scale_transform	(	Transform3d &	transform,
		double	scale )

{
    return scale_transform(transform, scale * Vec3d::Ones());
}

References scale(), scale_transform(), and Slic3r::transform().

Referenced by Slic3r::GUI::GLGizmoCut3D::apply_cut_connectors(), Slic3r::Geometry::Transformation::get_matrix_with_applied_shrinkage_compensation(), Slic3r::GUI::GLGizmoCut3D::is_conflict_for_connector(), Slic3r::lay_on_face_planes(), Slic3r::GUI::GLGizmoMeasure::on_render(), Slic3r::GUI::GCodeViewer::SequentialView::Marker::render(), Slic3r::GUI::GLGizmoCut3D::render_connectors(), Slic3r::GUI::GLGizmoPainterBase::render_cursor_circle(), Slic3r::GUI::GLGizmoCut3D::render_cut_plane_grabbers(), Slic3r::GUI::GLGizmoMeasure::render_dimensioning(), Slic3r::GUI::GLGizmoCut3D::render_grabber_connection(), Slic3r::GUI::GLGizmoBrimEars::render_points(), Slic3r::reset_instance_transformation(), Slic3r::Geometry::Transformation::reset_skew(), Slic3r::GUI::Selection::scale_and_translate(), scale_transform(), scale_transform(), scale_transform(), Slic3r::Geometry::Transformation::set_scaling_factor(), and Slic3r::GUI::GLGizmoCut3D::update_raycasters_for_picking_transform().

Here is the call graph for this function:

Here is the caller graph for this function:

segment_segment_intersection()

bool Slic3r::Geometry::segment_segment_intersection ( const Vec2d & p1, const Vec2d & v1, const Vec2d & p2, const Vec2d & v2, Vec2d & res )

inline

{
    double denom = v1(0) * v2(1) - v2(0) * v1(1);
    if (std::abs(denom) < EPSILON)
        // Lines are collinear.
        return false;
    double s12_x = p1(0) - p2(0);
    double s12_y = p1(1) - p2(1);
    double s_numer = v1(0) * s12_y - v1(1) * s12_x;
    bool   denom_is_positive = false;
    if (denom < 0.) {
        denom_is_positive = true;
        denom   = - denom;
        s_numer = - s_numer;
    }
    if (s_numer < 0.)
        // Intersection outside of the 1st segment.
        return false;
    double t_numer = v2(0) * s12_y - v2(1) * s12_x;
    if (! denom_is_positive)
        t_numer = - t_numer;
    if (t_numer < 0. || s_numer > denom || t_numer > denom)
        // Intersection outside of the 1st or 2nd segment.
        return false;
    // Intersection inside both of the segments.
    double t = t_numer / denom;
    res(0) = p1(0) + t * v1(0);
    res(1) = p1(1) + t * v1(1);
    return true;
}

References EPSILON.

Referenced by Slic3r::FillLightning::lineSegmentPolygonsIntersection().

Here is the caller graph for this function:

segments_intersect()

bool Slic3r::Geometry::segments_intersect ( const Slic3r::Point & ip1, const Slic3r::Point & ip2, const Slic3r::Point & jp1, const Slic3r::Point & jp2 )

inline

{    
    //assert(ip1 != ip2);
    //assert(jp1 != jp2);
 
    auto segments_could_intersect = [](
        const Slic3r::Point &ip1, const Slic3r::Point &ip2,
        const Slic3r::Point &jp1, const Slic3r::Point &jp2) -> std::pair<int, int>
    {
        Vec2i64 iv   = (ip2 - ip1).cast<int64_t>();
        Vec2i64 vij1 = (jp1 - ip1).cast<int64_t>();
        Vec2i64 vij2 = (jp2 - ip1).cast<int64_t>();
        int64_t tij1 = cross2(iv, vij1);
        int64_t tij2 = cross2(iv, vij2);
        return std::make_pair(
            // signum
            (tij1 > 0) ? 1 : ((tij1 < 0) ? -1 : 0),
            (tij2 > 0) ? 1 : ((tij2 < 0) ? -1 : 0));
    };
 
    std::pair<int, int> sign1 = segments_could_intersect(ip1, ip2, jp1, jp2);
    std::pair<int, int> sign2 = segments_could_intersect(jp1, jp2, ip1, ip2);
    int                 test1 = sign1.first * sign1.second;
    int                 test2 = sign2.first * sign2.second;
    if (test1 <= 0 && test2 <= 0) {
        // The segments possibly intersect. They may also be collinear, but not intersect.
        if (test1 != 0 || test2 != 0)
            // Certainly not collinear, then the segments intersect.
            return true;
        // If the first segment is collinear with the other, the other is collinear with the first segment.
        assert((sign1.first == 0 && sign1.second == 0) == (sign2.first == 0 && sign2.second == 0));
        if (sign1.first == 0 && sign1.second == 0) {
            // The segments are certainly collinear. Now verify whether they overlap.
            Slic3r::Point vi = ip2 - ip1;
            // Project both on the longer coordinate of vi.
            int axis = std::abs(vi.x()) > std::abs(vi.y()) ? 0 : 1;
            coord_t i = ip1(axis);
            coord_t j = ip2(axis);
            coord_t k = jp1(axis);
            coord_t l = jp2(axis);
            if (i > j)
                std::swap(i, j);
            if (k > l)
                std::swap(k, l);
            return (k >= i && k <= j) || (i >= k && i <= l);
        }
    }
    return false;
}

References Slic3r::cast(), and Slic3r::cross2().

Referenced by Slic3r::connect_brim_lines(), Slic3r::contour_distance(), Slic3r::EdgeGrid::Grid::has_intersecting_edges(), Slic3r::EdgeGrid::Grid::intersecting_edges(), Slic3r::join_close_ends(), Slic3r::FirstIntersectionVisitor::operator()(), Slic3r::FillLightning::polygonCollidesWithLineSegment(), Slic3r::trim_loop(), and Slic3r::tsp_remove_crossings().

Here is the call graph for this function:

Here is the caller graph for this function:

simplify_polygons()

void Slic3r::Geometry::simplify_polygons	(	const Polygons &	polygons,
		double	tolerance,
		Polygons *	retval )

{
    Polygons pp;
    for (Polygons::const_iterator it = polygons.begin(); it != polygons.end(); ++it) {
        Polygon p = *it;
        p.points.push_back(p.points.front());
        p.points = MultiPoint::_douglas_peucker(p.points, tolerance);
        p.points.pop_back();
        pp.push_back(p);
    }
    *retval = Slic3r::simplify_polygons(pp);
}

References Slic3r::MultiPoint::_douglas_peucker(), Slic3r::MultiPoint::points, and Slic3r::simplify_polygons().

Referenced by Slic3r::Print::_make_skirt().

Here is the call graph for this function:

Here is the caller graph for this function:

smallest_enclosing_circle2_welzl()

template<typename Vector, typename Points>

CircleSq< Vector > Slic3r::Geometry::smallest_enclosing_circle2_welzl	(	const Points &	points,
		const typename Vector::Scalar	epsilon )

{
    using Scalar = typename Vector::Scalar;
    CircleSq<Vector> circle;
 
    if (! points.empty()) {
      const auto &p0 = points[0].template cast<Scalar>();
      if (points.size() == 1) {
        circle.center = p0;
        circle.radius2 = epsilon * epsilon;
      } else {
        circle = CircleSq<Vector>(p0, points[1].template cast<Scalar>()).inflated(epsilon);
        for (size_t i = 2; i < points.size(); ++ i)
            if (const Vector &p = points[i].template cast<Scalar>(); ! circle.contains(p)) {
                // p is the first point on the smallest circle enclosing points[0..i]
                circle = CircleSq<Vector>(p0, p).inflated(epsilon);
                for (size_t j = 1; j < i; ++ j)
                    if (const Vector &q = points[j].template cast<Scalar>(); ! circle.contains(q)) {
                        // q is the second point on the smallest circle enclosing points[0..i]
                        circle = CircleSq<Vector>(p, q).inflated(epsilon);
                        for (size_t k = 0; k < j; ++ k)
                            if (const Vector &r = points[k].template cast<Scalar>(); ! circle.contains(r))
                                    circle = CircleSq<Vector>(p, q, r, epsilon).inflated(epsilon);
                    }
            }
    }
  }
 
    return circle;
}

References Slic3r::cast(), Slic3r::Geometry::CircleSq< Vector >::center, Slic3r::Geometry::CircleSq< Vector >::contains(), Slic3r::Geometry::CircleSq< Vector >::inflated(), and Slic3r::Geometry::CircleSq< Vector >::radius2.

Referenced by smallest_enclosing_circle_welzl().

Here is the call graph for this function:

Here is the caller graph for this function:

smallest_enclosing_circle_welzl() [1/2]

Circled Slic3r::Geometry::smallest_enclosing_circle_welzl ( const Points & points )

inline

{
    return smallest_enclosing_circle_welzl<Vec2d, Points>(points, SCALED_EPSILON);
}

References SCALED_EPSILON, and smallest_enclosing_circle_welzl().

Here is the call graph for this function:

smallest_enclosing_circle_welzl() [2/2]

template<typename Vector, typename Points>

Circle< Vector > Slic3r::Geometry::smallest_enclosing_circle_welzl	(	const Points &	points,
		const typename Vector::Scalar	epsilon )

{
    return Circle<Vector>(smallest_enclosing_circle2_welzl<Vector, Points>(points, epsilon));
}

References Slic3r::Circle, and smallest_enclosing_circle2_welzl().

Referenced by Slic3r::BuildVolume::BuildVolume(), and smallest_enclosing_circle_welzl().

Here is the call graph for this function:

Here is the caller graph for this function:

to_cgal_point() [1/3]

CGAL_Point Slic3r::Geometry::to_cgal_point ( const Point & pt )

inline

{ return {pt.x(), pt.y()}; }

to_cgal_point() [2/3]

CGAL_Point Slic3r::Geometry::to_cgal_point ( const VD::vertex_type * pt )

inline

{ return {pt->x(), pt->y()}; }

Referenced by get_parabolic_segment(), Slic3r::Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_intersection(), and orientation_of_two_edges().

Here is the caller graph for this function:

to_cgal_point() [3/3]

CGAL_Point Slic3r::Geometry::to_cgal_point ( const Vec2d & pt )

inline

{ return {pt.x(), pt.y()}; }

to_range_pi_pi()

template<typename T>

void Slic3r::Geometry::to_range_pi_pi

(

T &

angle

)

                                                  {
    if (angle > T(PI) || angle <= -T(PI)) {
        int count = static_cast<int>(std::round(angle / (2 * PI)));
        angle -= static_cast<T>(count * 2 * PI);
        assert(angle <= T(PI) && angle > -T(PI));
    }
}

References Slic3r::angle(), count, and PI.

Referenced by Slic3r::GUI::dragging_rotate_gizmo(), Slic3r::GUI::GLGizmoEmboss::draw_advanced(), and Slic3r::GUI::GLGizmoSVG::draw_rotation().

Here is the call graph for this function:

Here is the caller graph for this function:

transform3d_from_string()

Transform3d Slic3r::Geometry::transform3d_from_string

(

const std::string &

transform_str

)

{
    assert(is_decimal_separator_point()); // for atof
    Transform3d transform = Transform3d::Identity();
 
    if (!transform_str.empty()) {
        std::vector<std::string> mat_elements_str;
        boost::split(mat_elements_str, transform_str, boost::is_any_of(" "), boost::token_compress_on);
 
        const unsigned int size = (unsigned int)mat_elements_str.size();
        if (size == 16) {
            unsigned int i = 0;
            for (unsigned int r = 0; r < 4; ++r) {
                for (unsigned int c = 0; c < 4; ++c) {
                    transform(r, c) = ::atof(mat_elements_str[i++].c_str());
                }
            }
        }
    }
 
    return transform;
}

References Slic3r::is_decimal_separator_point(), and Slic3r::transform().

Referenced by Slic3r::_3MF_Importer::_generate_volumes(), and Slic3r::_BBS_3MF_Importer::_generate_volumes_new().

Here is the call graph for this function:

Here is the caller graph for this function:

translation_transform() [1/2]

Transform3d Slic3r::Geometry::translation_transform

(

const Vec3d &

translation

)

{
    Transform3d transform;
    translation_transform(transform, translation);
    return transform;
}

References Slic3r::transform(), and translation_transform().

Here is the call graph for this function:

translation_transform() [2/2]

void Slic3r::Geometry::translation_transform	(	Transform3d &	transform,
		const Vec3d &	translation )

{
    transform = Transform3d::Identity();
    transform.translate(translation);
}

References Slic3r::transform().

Referenced by Slic3r::GUI::GLGizmoCut3D::PartSelection::PartSelection(), Slic3r::GUI::GLCanvas3D::_render_platelist(), Slic3r::GUI::GLGizmoCut3D::apply_cut_connectors(), Slic3r::GUI::Plater::cut_horizontal(), Slic3r::GUI::cut_model(), Slic3r::GUI::GLGizmoCut3D::dragging_grabber_move(), Slic3r::GUI::GLGizmoCut3D::get_cut_matrix(), Slic3r::Geometry::Transformation::get_offset_matrix(), Slic3r::GUI::GLGizmoCut3D::has_valid_groove(), Slic3r::GUI::init_torus_data(), Slic3r::GUI::GLGizmoCut3D::is_conflict_for_connector(), Slic3r::GUI::GLGizmoCut3D::is_outside_of_cut_contour(), Slic3r::GUI::GLGizmoFlatten::on_register_raycasters_for_picking(), Slic3r::GUI::GLGizmoFlatten::on_render(), Slic3r::GUI::GLGizmoMeasure::on_render(), Slic3r::Cut::perform_with_groove(), Slic3r::Cut::perform_with_plane(), Slic3r::process_volume_cut(), Slic3r::GUI::Plater::priv::reload_from_disk(), Slic3r::GUI::GCodeViewer::SequentialView::Marker::render(), Slic3r::GUI::GLGizmoCut3D::PartSelection::render(), Slic3r::GUI::GLGizmoCut3D::render_connectors(), Slic3r::GUI::GLGizmoPainterBase::render_cursor_circle(), Slic3r::GUI::GLGizmoCut3D::render_cut_plane(), Slic3r::GUI::GLGizmoCut3D::render_cut_plane_grabbers(), Slic3r::GUI::GLGizmoMeasure::render_dimensioning(), Slic3r::GUI::GCodeViewer::render_markers(), Slic3r::GUI::GLGizmoBrimEars::render_points(), Slic3r::GUI::GLGizmoCut3D::render_rotation_snapping(), Slic3r::GUI::Plater::priv::replace_volume_with_stl(), Slic3r::ModelVolume::restore_painting(), Slic3r::GUI::Selection::rotate(), Slic3r::GUI::GLGizmoCut3D::rotate_vec3d_around_plane_center(), Slic3r::GUI::Selection::scale_and_translate(), Slic3r::GUI::GLGizmoMeasure::set_distance(), Slic3r::GUI::GLGizmoCut3D::PartSelection::toggle_selection(), Slic3r::GUI::Selection::transform_instance_relative(), Slic3r::GUI::Selection::transform_volume_relative(), Slic3r::GUI::GLGizmoCut3D::transformed_bounding_box(), Slic3r::GUI::Selection::translate(), translation_transform(), and Slic3r::GUI::GLGizmoCut3D::update_raycasters_for_picking_transform().

Here is the call graph for this function:

Here is the caller graph for this function: