Slic3r::Measure::MeasuringImpl Class Reference

Collaboration diagram for Slic3r::Measure::MeasuringImpl:

Classes
struct	PlaneData

Public Member Functions
	MeasuringImpl (const indexed_triangle_set &its)
std::optional< SurfaceFeature >	get_feature (size_t face_idx, const Vec3d &point)
int	get_num_of_planes () const
const std::vector< int > &	get_plane_triangle_indices (int idx) const
const std::vector< SurfaceFeature > &	get_plane_features (unsigned int plane_id)
const TriangleMesh &	get_mesh () const

Private Member Functions
void	update_planes ()
void	extract_features (int plane_idx)

Private Attributes
std::vector< PlaneData >	m_planes
std::vector< size_t >	m_face_to_plane
TriangleMesh	m_mesh

Detailed Description

---

Class Documentation

Slic3r::Measure::MeasuringImpl::PlaneData

struct Slic3r::Measure::MeasuringImpl::PlaneData

Collaboration diagram for Slic3r::Measure::MeasuringImpl::PlaneData:

Class Members
float	area
vector< vector< Vec3d > >	borders
vector< int >	facets
bool	features_extracted = false
Vec3d	normal
vector< SurfaceFeature >	surface_features

Constructor & Destructor Documentation

MeasuringImpl()

Slic3r::Measure::MeasuringImpl::MeasuringImpl ( const indexed_triangle_set &  its )

explicit

: m_mesh(its)
{
    update_planes();
 
    // Extracting features will be done as needed.
    // To extract all planes at once, run the following:
#if DEBUG_EXTRACT_ALL_FEATURES_AT_ONCE
    for (int i=0; i<int(m_planes.size()); ++i)
        extract_features(i);
#endif
}

References extract_features(), m_planes, and update_planes().

Here is the call graph for this function:

Member Function Documentation

extract_features()

void Slic3r::Measure::MeasuringImpl::extract_features ( int  plane_idx )

private

{
    assert(! m_planes[plane_idx].features_extracted);
 
    PlaneData& plane = m_planes[plane_idx];
    plane.surface_features.clear();
    const Vec3d& normal = plane.normal;
 
    Eigen::Quaterniond q;
    q.setFromTwoVectors(plane.normal, Vec3d::UnitZ());
    Transform3d trafo = Transform3d::Identity();
    trafo.rotate(q);
    const Transform3d trafo_inv = trafo.inverse();
 
    std::vector<double> angles; // placed in outer scope to prevent reallocations
    std::vector<double> lengths;
 
    for (const std::vector<Vec3d>& border : plane.borders) {
        if (border.size() <= 1)
            continue;
 
        bool done = false;
 
        if (border.size() > 4) {
            const auto& [center, radius, err] = get_center_and_radius(border, trafo, trafo_inv);
 
            if (err < 0.05) {
                // The whole border is one circle. Just add it into the list of features
                // and we are done.
 
                bool is_polygon = border.size()>4 && border.size()<=8;
                bool lengths_match = std::all_of(border.begin()+2, border.end(), [is_polygon](const Vec3d& pt) {
                        return Slic3r::is_approx((pt - *((&pt)-1)).squaredNorm(), (*((&pt)-1) - *((&pt)-2)).squaredNorm(), is_polygon ? 0.01 : 0.01);
                    });
 
                if (lengths_match && (is_polygon || border.size() > 8)) {
                    if (is_polygon) {
                        // This is a polygon, add the separate edges with the center.
                        for (int j=0; j<int(border.size()); ++j)
                            plane.surface_features.emplace_back(SurfaceFeature(SurfaceFeatureType::Edge,
                                border[j==0 ? border.size()-1 : j-1], border[j],
                                std::make_optional(center)));
                    } else {
                        // The fit went well and it has more than 8 points - let's consider this a circle.
                        plane.surface_features.emplace_back(SurfaceFeature(SurfaceFeatureType::Circle, center, plane.normal, std::nullopt, radius));
                    }
                    done = true;
                }
            }
        }
 
        if (! done) {
            // In this case, the border is not a circle and may contain circular
            // segments. Try to find them and then add all remaining edges as edges.
 
            auto are_angles_same  = [](double a, double b) { return Slic3r::is_approx(a,b,0.01); };
            auto are_lengths_same = [](double a, double b) { return Slic3r::is_approx(a,b,0.01); };
 
 
            // Given an idx into border, return the index that is idx+offset position,
            // while taking into account the need for wrap-around and the fact that
            // the first and last point are the same.
            auto offset_to_index = [border_size = int(border.size())](int idx, int offset) -> int {
                assert(std::abs(offset) < border_size);
                int out = idx+offset;
                if (out >= border_size)
                    out = out - border_size;
                else if (out < 0)
                    out = border_size + out;
 
                return out;
            };
 
            // First calculate angles at all the vertices.
            angles.clear();
            lengths.clear();
            int first_different_angle_idx = 0;
            for (int i=0; i<int(border.size()); ++i) {
                const Vec3d& v2 = border[i] - (i == 0 ? border[border.size()-1] : border[i-1]);
                const Vec3d& v1 = (i == int(border.size()-1) ? border[0] : border[i+1]) - border[i];
                double angle = atan2(-normal.dot(v1.cross(v2)), -v1.dot(v2)) + M_PI;
                if (angle > M_PI)
                    angle = 2*M_PI - angle;
 
                angles.push_back(angle);
                lengths.push_back(v2.norm());
                if (first_different_angle_idx == 0 && angles.size() > 1) {
                    if (! are_angles_same(angles.back(), angles[angles.size()-2]))
                        first_different_angle_idx = angles.size()-1;
                }
            }
            assert(border.size() == angles.size());
            assert(border.size() == lengths.size());
 
            // First go around the border and pick what might be circular segments.
            // Save pair of indices to where such potential segments start and end.
            // Also remember the length of these segments.
            int start_idx = -1;
            bool circle = false;
            bool first_iter = true;
            std::vector<SurfaceFeature> circles;
            std::vector<SurfaceFeature> edges;
            std::vector<std::pair<int, int>> circles_idxs;
            //std::vector<double> circles_lengths;
            std::vector<Vec3d> single_circle; // could be in loop-scope, but reallocations
            double single_circle_length = 0.;
            int first_pt_idx = offset_to_index(first_different_angle_idx, 1);
            int i = first_pt_idx;
            while (i != first_pt_idx || first_iter) {
                if (are_angles_same(angles[i], angles[offset_to_index(i,-1)])
                && i != offset_to_index(first_pt_idx, -1) // not the last point
                && i != start_idx  ) {
                    // circle
                    if (! circle) {
                        circle = true;
                        single_circle.clear();
                        single_circle_length = 0.;
                        start_idx = offset_to_index(i, -2);
                        single_circle = { border[start_idx], border[offset_to_index(start_idx,1)] };
                        single_circle_length += lengths[offset_to_index(i, -1)];
                    }
                    single_circle.emplace_back(border[i]);
                    single_circle_length += lengths[i];
                } else {
                    if (circle && single_circle.size() >= 5) { // Less than 5 vertices? Not a circle.
                        single_circle.emplace_back(border[i]);
                        single_circle_length += lengths[i];
 
                        bool accept_circle = true;
                        {
                            // Check that lengths of internal (!!!) edges match.
                            int j = offset_to_index(start_idx, 3);
                            while (j != i) {
                                if (! are_lengths_same(lengths[offset_to_index(j,-1)], lengths[j])) {
                                    accept_circle = false;
                                    break;
                                }
                                j = offset_to_index(j, 1);
                            }
                        }
 
                        if (accept_circle) {
                            const auto& [center, radius, err] = get_center_and_radius(single_circle, trafo, trafo_inv);
 
                            // Check that the fit went well. The tolerance is high, only to
                            // reject complete failures.
                            accept_circle &= err < 0.05;
 
                            // If the segment subtends less than 90 degrees, throw it away.
                            accept_circle &= single_circle_length / radius > 0.9*M_PI/2.;
 
                            if (accept_circle) {
                                // Add the circle and remember indices into borders.
                                circles_idxs.emplace_back(start_idx, i);
                                circles.emplace_back(SurfaceFeature(SurfaceFeatureType::Circle, center, plane.normal, std::nullopt, radius));
                            }
                        }
                    }
                    circle = false;
                }
                // Take care of the wrap around.
                first_iter = false;
                i = offset_to_index(i, 1);
            }
 
            // We have the circles. Now go around again and pick edges, while jumping over circles.
            if (circles_idxs.empty()) {
                // Just add all edges.
                for (int i=1; i<int(border.size()); ++i)
                    edges.emplace_back(SurfaceFeature(SurfaceFeatureType::Edge, border[i-1], border[i]));
                edges.emplace_back(SurfaceFeature(SurfaceFeatureType::Edge, border[0], border[border.size()-1]));
            } else if (circles_idxs.size() > 1 || circles_idxs.front().first != circles_idxs.front().second) {
                // There is at least one circular segment. Start at its end and add edges until the start of the next one.
                int i = circles_idxs.front().second;
                int circle_idx = 1;
                while (true) {
                    i = offset_to_index(i, 1);
                    edges.emplace_back(SurfaceFeature(SurfaceFeatureType::Edge, border[offset_to_index(i,-1)], border[i]));
                    if (circle_idx < int(circles_idxs.size()) && i == circles_idxs[circle_idx].first) {
                        i = circles_idxs[circle_idx].second;
                        ++circle_idx;
                    }
                    if (i == circles_idxs.front().first)
                        break;
                }
            }
 
            // Merge adjacent edges where needed.
            assert(std::all_of(edges.begin(), edges.end(),
                            [](const SurfaceFeature& f) { return f.get_type() == SurfaceFeatureType::Edge; }));
            for (int i=edges.size()-1; i>=0; --i) {
                const auto& [first_start, first_end] = edges[i==0 ? edges.size()-1 : i-1].get_edge();
                const auto& [second_start, second_end] =   edges[i].get_edge();
 
                if (Slic3r::is_approx(first_end, second_start)
                    && Slic3r::is_approx((first_end-first_start).normalized().dot((second_end-second_start).normalized()), 1.)) {
                    // The edges have the same direction and share a point. Merge them.
                    edges[i==0 ? edges.size()-1 : i-1] = SurfaceFeature(SurfaceFeatureType::Edge, first_start, second_end);
                    edges.erase(edges.begin() + i);
                }
            }
 
            // Now move the circles and edges into the feature list for the plane.
            assert(std::all_of(circles.begin(), circles.end(), [](const SurfaceFeature& f) {
                return f.get_type() == SurfaceFeatureType::Circle;
            }));
            assert(std::all_of(edges.begin(), edges.end(), [](const SurfaceFeature& f) {
                return f.get_type() == SurfaceFeatureType::Edge;
            }));
            plane.surface_features.insert(plane.surface_features.end(), std::make_move_iterator(circles.begin()),
                std::make_move_iterator(circles.end()));
            plane.surface_features.insert(plane.surface_features.end(), std::make_move_iterator(edges.begin()),
                std::make_move_iterator(edges.end()));
        }
    }
 
    // The last surface feature is the plane itself.
    Vec3d cog = Vec3d::Zero();
    size_t counter = 0;
    for (const std::vector<Vec3d>& b : plane.borders) {
        for (size_t i = 1; i < b.size(); ++i) {
            cog += b[i];
            ++counter;
        }
    }
    cog /= double(counter);
    plane.surface_features.emplace_back(SurfaceFeature(SurfaceFeatureType::Plane,
        plane.normal, cog, std::optional<Vec3d>(), plane_idx + 0.0001));
 
    plane.borders.clear();
    plane.borders.shrink_to_fit();
 
    plane.features_extracted = true;
}

References Slic3r::angle(), Slic3r::Measure::MeasuringImpl::PlaneData::borders, Slic3r::Measure::Circle, done, Slic3r::dot(), Slic3r::Measure::Edge, Slic3r::f(), Slic3r::Measure::MeasuringImpl::PlaneData::features_extracted, Slic3r::Measure::get_center_and_radius(), Eigen::Transform< double, 3, Eigen::Affine, Eigen::DontAlign >::Identity(), Eigen::Transform< _Scalar, _Dim, _Mode, _Options >::inverse(), Slic3r::is_approx(), M_PI, m_planes, Slic3r::Measure::MeasuringImpl::PlaneData::normal, Slic3r::offset(), Slic3r::Measure::Plane, Eigen::Transform< _Scalar, _Dim, _Mode, _Options >::rotate(), Eigen::QuaternionBase< Derived >::setFromTwoVectors(), and Slic3r::Measure::MeasuringImpl::PlaneData::surface_features.

Referenced by MeasuringImpl(), get_feature(), and get_plane_features().

Here is the call graph for this function:

Here is the caller graph for this function:

get_feature()

std::optional< SurfaceFeature > Slic3r::Measure::MeasuringImpl::get_feature	(	size_t	face_idx,
		const Vec3d &	point
	)

{
    if (face_idx >= m_face_to_plane.size())
        return std::optional<SurfaceFeature>();
 
    const PlaneData& plane = m_planes[m_face_to_plane[face_idx]];
 
    if (! plane.features_extracted)
        extract_features(m_face_to_plane[face_idx]);
    
    size_t closest_feature_idx = size_t(-1);
    double min_dist = std::numeric_limits<double>::max();
 
    MeasurementResult res;
    SurfaceFeature point_sf(point);
 
    assert(plane.surface_features.empty() || plane.surface_features.back().get_type() == SurfaceFeatureType::Plane);
 
    for (size_t i=0; i<plane.surface_features.size() - 1; ++i) {
        // The -1 is there to prevent measuring distance to the plane itself,
        // which is needless and relatively expensive.
        res = get_measurement(plane.surface_features[i], point_sf);
        if (res.distance_strict) { // TODO: this should become an assert after all combinations are implemented.
            double dist = res.distance_strict->dist;
            if (dist < feature_hover_limit && dist < min_dist) {
                min_dist = std::min(dist, min_dist);
                closest_feature_idx = i;
            }
        }
    }
 
    if (closest_feature_idx != size_t(-1)) {
        const SurfaceFeature& f = plane.surface_features[closest_feature_idx];
        if (f.get_type() == SurfaceFeatureType::Edge) {
            // If this is an edge, check if we are not close to the endpoint. If so,
            // we will include the endpoint as well. Close = 10% of the lenghth of
            // the edge, clamped between 0.025 and 0.5 mm.
            const auto& [sp, ep] = f.get_edge();
            double len_sq = (ep-sp).squaredNorm();
            double limit_sq = std::max(0.025*0.025, std::min(0.5*0.5, 0.1 * 0.1 * len_sq));
 
            if ((point-sp).squaredNorm() < limit_sq)
                return std::make_optional(SurfaceFeature(sp));
            if ((point-ep).squaredNorm() < limit_sq)
                return std::make_optional(SurfaceFeature(ep));
        }
        return std::make_optional(f);
    }
 
    // Nothing detected, return the plane as a whole.
    assert(plane.surface_features.back().get_type() == SurfaceFeatureType::Plane);
    return std::make_optional(plane.surface_features.back());
}

References Slic3r::Measure::MeasurementResult::distance_strict, Slic3r::Measure::Edge, extract_features(), Slic3r::f(), Slic3r::Measure::feature_hover_limit, Slic3r::Measure::MeasuringImpl::PlaneData::features_extracted, Slic3r::Measure::get_measurement(), m_face_to_plane, m_planes, Slic3r::Measure::Plane, and Slic3r::Measure::MeasuringImpl::PlaneData::surface_features.

Here is the call graph for this function:

get_mesh()

const TriangleMesh & Slic3r::Measure::MeasuringImpl::get_mesh

(

)

const

{
    return this->m_mesh;
}

References m_mesh.

get_num_of_planes()

int Slic3r::Measure::MeasuringImpl::get_num_of_planes

(

)

const

{
    return (m_planes.size());
}

References m_planes.

get_plane_features()

const std::vector< SurfaceFeature > & Slic3r::Measure::MeasuringImpl::get_plane_features

(

unsigned int

plane_id

)

{
    assert(plane_id < m_planes.size());
    if (! m_planes[plane_id].features_extracted)
        extract_features(plane_id);
    return m_planes[plane_id].surface_features;
}

References extract_features(), and m_planes.

Here is the call graph for this function:

get_plane_triangle_indices()

const std::vector< int > & Slic3r::Measure::MeasuringImpl::get_plane_triangle_indices

(

int

idx

)

const

{
    assert(idx >= 0 && idx < int(m_planes.size()));
    return m_planes[idx].facets;
}

References m_planes.

update_planes()

void Slic3r::Measure::MeasuringImpl::update_planes ( )

private

{
    m_planes.clear();
 
    // Now we'll go through all the facets and append Points of facets sharing the same normal.
    // This part is still performed in mesh coordinate system.
    const size_t             num_of_facets = m_mesh.its.indices.size();
    m_face_to_plane.resize(num_of_facets, size_t(-1));
    const std::vector<Vec3f> face_normals = its_face_normals(m_mesh.its);
    const std::vector<Vec3i> face_neighbors = its_face_neighbors(m_mesh.its);
    std::vector<int>         facet_queue(num_of_facets, 0);
    int                      facet_queue_cnt = 0;
    const stl_normal*        normal_ptr      = nullptr;
    size_t seed_facet_idx = 0;
 
    auto is_same_normal = [](const stl_normal& a, const stl_normal& b) -> bool {
        return (std::abs(a(0) - b(0)) < 0.001 && std::abs(a(1) - b(1)) < 0.001 && std::abs(a(2) - b(2)) < 0.001);
    };
 
    // First go through all the triangles and fill in m_planes vector. For each "plane"
    // detected on the model, it will contain list of facets that are part of it.
    // We will also fill in m_face_to_plane, which contains index into m_planes
    // for each of the source facets.
    while (1) {
        // Find next unvisited triangle:
        for (; seed_facet_idx < num_of_facets; ++ seed_facet_idx)
            if (m_face_to_plane[seed_facet_idx] == size_t(-1)) {
                facet_queue[facet_queue_cnt ++] = seed_facet_idx;
                normal_ptr = &face_normals[seed_facet_idx];
                m_face_to_plane[seed_facet_idx] = m_planes.size();
                m_planes.emplace_back();                
                break;
            }
        if (seed_facet_idx == num_of_facets)
            break; // Everything was visited already
 
        while (facet_queue_cnt > 0) {
            int facet_idx = facet_queue[-- facet_queue_cnt];
            const stl_normal& this_normal = face_normals[facet_idx];
            if (is_same_normal(this_normal, *normal_ptr)) {
//                const Vec3i& face = m_its.indices[facet_idx];
 
                m_face_to_plane[facet_idx] = m_planes.size() - 1;
                m_planes.back().facets.emplace_back(facet_idx);
                for (int j = 0; j < 3; ++ j)
                    if (int neighbor_idx = face_neighbors[facet_idx][j]; neighbor_idx >= 0 && m_face_to_plane[neighbor_idx] == size_t(-1))
                        facet_queue[facet_queue_cnt ++] = neighbor_idx;
            }
        }
 
        m_planes.back().normal = normal_ptr->cast<double>();
        std::sort(m_planes.back().facets.begin(), m_planes.back().facets.end());
    }
    
    // Check that each facet is part of one of the planes.
    assert(std::none_of(m_face_to_plane.begin(), m_face_to_plane.end(), [](size_t val) { return val == size_t(-1); }));
 
    // Now we will walk around each of the planes and save vertices which form the border.
    SurfaceMesh sm(m_mesh.its);
    for (int plane_id=0; plane_id < int(m_planes.size()); ++plane_id) {
        const auto& facets = m_planes[plane_id].facets;
        m_planes[plane_id].borders.clear();
        std::vector<std::array<bool, 3>> visited(facets.size(), {false, false, false});
        
        
 
        for (int face_id=0; face_id<int(facets.size()); ++face_id) {
            assert(m_face_to_plane[facets[face_id]] == plane_id);
 
            for (int edge_id=0; edge_id<3; ++edge_id) {
                // Every facet's edge which has a neighbor from a different plane is
                // part of an edge that we want to walk around. Skip the others.
                int neighbor_idx = face_neighbors[facets[face_id]][edge_id];
                if (neighbor_idx == -1)
                    goto PLANE_FAILURE;
                if (visited[face_id][edge_id] || (int)m_face_to_plane[neighbor_idx] == plane_id) {
                    visited[face_id][edge_id] = true;
                    continue;
                }
 
                Halfedge_index he = sm.halfedge(Face_index(facets[face_id]));
                while (he.side() != edge_id)
                    he = sm.next(he);
            
                // he is the first halfedge on the border. Now walk around and append the points.
                //const Halfedge_index he_orig = he;
                m_planes[plane_id].borders.emplace_back();
                std::vector<Vec3d>& last_border = m_planes[plane_id].borders.back();
                last_border.emplace_back(sm.point(sm.source(he)).cast<double>());
                //Vertex_index target = sm.target(he);
                const Halfedge_index he_start = he;
                
                Face_index fi = he.face();
                auto face_it = std::lower_bound(facets.begin(), facets.end(), int(fi));
                assert(face_it != facets.end());
                assert(*face_it == int(fi));
                visited[face_it - facets.begin()][he.side()] = true;
 
                do {
                    const Halfedge_index he_orig = he;
                    he = sm.next_around_target(he);
                    if (he.is_invalid())
                        goto PLANE_FAILURE;
 
                    // For broken meshes, the iteration might never get back to he_orig.
                    // Remember all halfedges we saw to break out of such infinite loops.
                    boost::container::small_vector<Halfedge_index, 10> he_seen;
 
                    while ( (int)m_face_to_plane[sm.face(he)] == plane_id && he != he_orig) {
                        he_seen.emplace_back(he);
                        he = sm.next_around_target(he);
                        if (he.is_invalid() || std::find(he_seen.begin(), he_seen.end(), he) != he_seen.end())
                            goto PLANE_FAILURE;
                    }
                    he = sm.opposite(he);
                    if (he.is_invalid())
                        goto PLANE_FAILURE;
                    
                    Face_index fi = he.face();
                    auto face_it = std::lower_bound(facets.begin(), facets.end(), int(fi));
                    if (face_it == facets.end() || *face_it != int(fi)) // This indicates a broken mesh.
                        goto PLANE_FAILURE;
 
                    if (visited[face_it - facets.begin()][he.side()] && he != he_start) {
                        last_border.resize(1);
                        break;
                    }
                    visited[face_it - facets.begin()][he.side()] = true;
 
                    last_border.emplace_back(sm.point(sm.source(he)).cast<double>());
 
                    // In case of broken meshes, this loop might be infinite. Break
                    // out in case it is clearly going bad.
                    if (last_border.size() > 3*facets.size()+1)
                        goto PLANE_FAILURE;
 
                } while (he != he_start);
 
                if (last_border.size() == 1)
                    m_planes[plane_id].borders.pop_back();
                else {
                    assert(last_border.front() == last_border.back());
                    last_border.pop_back();
                }
            }
        }
        continue; // There was no failure.
 
        PLANE_FAILURE:
            m_planes[plane_id].borders.clear();
    }
}

References Slic3r::Halfedge_index::face(), Slic3r::SurfaceMesh::face(), Slic3r::SurfaceMesh::halfedge(), indexed_triangle_set::indices, Slic3r::Halfedge_index::is_invalid(), Slic3r::TriangleMesh::its, Slic3r::its_face_neighbors(), Slic3r::its_face_normals(), m_face_to_plane, m_mesh, m_planes, Slic3r::SurfaceMesh::next(), Slic3r::SurfaceMesh::next_around_target(), Slic3r::SurfaceMesh::opposite(), Slic3r::SurfaceMesh::point(), Slic3r::Halfedge_index::side(), and Slic3r::SurfaceMesh::source().

Referenced by MeasuringImpl().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

m_face_to_plane

std::vector<size_t> Slic3r::Measure::MeasuringImpl::m_face_to_plane

private

Referenced by get_feature(), and update_planes().

m_mesh

TriangleMesh Slic3r::Measure::MeasuringImpl::m_mesh

private

Referenced by get_mesh(), and update_planes().

m_planes

std::vector<PlaneData> Slic3r::Measure::MeasuringImpl::m_planes

private

Referenced by MeasuringImpl(), extract_features(), get_feature(), get_num_of_planes(), get_plane_features(), get_plane_triangle_indices(), and update_planes().

---

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

• src/libslic3r/Measure.cpp