Slic3r::TriangleSelector Class Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/TriangleSelector.hpp>

Inheritance diagram for Slic3r::TriangleSelector:

Collaboration diagram for Slic3r::TriangleSelector:

Classes
struct	ClippingPlane
class	Cursor
class	SinglePointCursor
class	DoublePointCursor
class	Sphere
class	Circle
class	HeightRange
class	Capsule3D
class	Capsule2D
struct	TriangleBitStreamMapping
struct	TriangleSplittingData
struct	SavedPainting
class	Triangle
struct	Vertex

Public Types
enum	CursorType {   CIRCLE , SPHERE , POINTER , HEIGHT_RANGE ,   GAP_FILL }

Public Member Functions
std::pair< std::vector< Vec3i32 >, std::vector< Vec3i32 > >	precompute_all_neighbors () const
void	precompute_all_neighbors_recursive (int facet_idx, const Vec3i32 &neighbors, const Vec3i32 &neighbors_propagated, std::vector< Vec3i32 > &neighbors_out, std::vector< Vec3i32 > &neighbors_normal_out) const
void	set_edge_limit (float edge_limit)
	TriangleSelector (const TriangleMesh &mesh, float edge_limit=0.6f)
int	select_unsplit_triangle (const Vec3f &hit, int facet_idx) const
int	select_unsplit_triangle (const Vec3f &hit, int facet_idx, const Vec3i32 &neighbors) const
void	select_patch (int facet_start, std::unique_ptr< Cursor > &&cursor, EnforcerBlockerType new_state, const Transform3d &trafo_no_translate, bool triangle_splitting, float highlight_by_angle_deg=0.f, const Vec3f &up_direction=Vec3f::UnitZ(), bool select_partially=false)
void	seed_fill_select_triangles (const Vec3f &hit, int facet_start, const Transform3d &trafo_no_translate, const ClippingPlane &clp, float seed_fill_angle, float highlight_by_angle_deg=0.f, const Vec3f &up_direction=Vec3f::UnitZ(), bool force_reselection=false)
void	bucket_fill_select_triangles (const Vec3f &hit, int facet_start, const ClippingPlane &clp, float seed_fill_angle, bool propagate, bool force_reselection=false)
bool	has_facets (EnforcerBlockerType state) const
int	num_facets (EnforcerBlockerType state) const
indexed_triangle_set	get_facets (EnforcerBlockerType state) const
indexed_triangle_set	get_facets_strict (EnforcerBlockerType state, std::vector< int > *out_source=nullptr) const
std::vector< Vec2i32 >	get_seed_fill_contour () const
void	get_facets (std::vector< indexed_triangle_set > &facets_per_type) const
void	set_facet (int facet_idx, EnforcerBlockerType state)
void	reset ()
void	garbage_collect ()
void	remap_triangle_state (const EnforcerBlockerStateMap &state_map)
TriangleSplittingData	serialize () const
void	deserialize (const TriangleSplittingData &data, bool needs_reset=true, EnforcerBlockerType max_ebt=EnforcerBlockerType::ExtruderMax, EnforcerBlockerType to_delete_filament=EnforcerBlockerType::NONE, EnforcerBlockerType replace_filament=EnforcerBlockerType::NONE)
void	seed_fill_unselect_all_triangles ()
void	shift_states_above (EnforcerBlockerType threshold, int delta)
void	seed_fill_apply_on_triangles (EnforcerBlockerType new_state)

Static Public Member Functions
static bool	has_facets (const TriangleSplittingData &data, EnforcerBlockerType test_state)
static std::vector< EnforcerBlockerType >	extract_used_facet_states (const TriangleSplittingData &data)
static TriangleSplittingData	remap_painting (const indexed_triangle_set &source_its, const TriangleSplittingData &source_painting, const indexed_triangle_set &target_its, const Transform3d &target_transform, const std::optional< std::reference_wrapper< const TriangleSplittingData > > &existing_painting)

Protected Member Functions
void	append_touching_subtriangles (int itriangle, int vertexi, int vertexj, std::vector< int > &touching_subtriangles_out) const
bool	verify_triangle_neighbors (const Triangle &tr, const Vec3i32 &neighbors) const

Protected Attributes
std::vector< Vertex >	m_vertices
std::vector< Triangle >	m_triangles
const TriangleMesh &	m_mesh
const std::vector< Vec3i32 >	m_neighbors
const std::vector< Vec3f >	m_face_normals
float	m_edge_limit = 0.6f
int	m_invalid_triangles
float	m_edge_limit_sqr = 1.f
int	m_orig_size_vertices = 0
int	m_orig_size_indices = 0
std::unique_ptr< Cursor >	m_cursor
float	m_old_cursor_radius_sqr = 0

Private Types
enum class	Partition { First , Second }

Private Member Functions
bool	select_triangle (int facet_idx, EnforcerBlockerType type, bool triangle_splitting, bool select_partially)
bool	select_triangle_recursive (int facet_idx, const Vec3i32 &neighbors, EnforcerBlockerType type, bool triangle_splitting, bool select_partially)
void	undivide_triangle (int facet_idx)
void	split_triangle (int facet_idx, const Vec3i32 &neighbors)
void	remove_useless_children (int facet_idx)
bool	is_facet_clipped (int facet_idx, const ClippingPlane &clp) const
int	push_triangle (int a, int b, int c, int source_triangle, EnforcerBlockerType state=EnforcerBlockerType{0})
void	perform_split (int facet_idx, const Vec3i32 &neighbors, EnforcerBlockerType old_state)
Vec3i32	child_neighbors (const Triangle &tr, const Vec3i32 &neighbors, int child_idx) const
Vec3i32	child_neighbors_propagated (const Triangle &tr, const Vec3i32 &neighbors_propagated, int child_idx, const Vec3i32 &child_neighbors) const
int	neighbor_child (const Triangle &tr, int vertexi, int vertexj, Partition partition) const
int	neighbor_child (int itriangle, int vertexi, int vertexj, Partition partition) const
int	triangle_midpoint (const Triangle &tr, int vertexi, int vertexj) const
int	triangle_midpoint (int itriangle, int vertexi, int vertexj) const
int	triangle_midpoint_or_allocate (int itriangle, int vertexi, int vertexj)
std::pair< int, int >	triangle_subtriangles (int itriangle, int vertexi, int vertexj) const
void	append_touching_edges (int itriangle, int vertexi, int vertexj, std::vector< Vec2i32 > &touching_edges_out) const
bool	verify_triangle_midpoints (const Triangle &tr) const
void	get_facets_strict_recursive (const Triangle &tr, const Vec3i32 &neighbors, EnforcerBlockerType state, std::vector< stl_triangle_vertex_indices > &out_triangles) const
void	get_facets_split_by_tjoints (const Vec3i32 &vertices, const Vec3i32 &neighbors, std::vector< stl_triangle_vertex_indices > &out_triangles) const
void	get_seed_fill_contour_recursive (int facet_idx, const Vec3i32 &neighbors, const Vec3i32 &neighbors_propagated, std::vector< Vec2i32 > &edges_out) const

Static Private Member Functions
static std::pair< int, int >	triangle_subtriangles (const Triangle &tr, int vertexi, int vertexj)

Private Attributes
int	m_free_triangles_head { -1 }
int	m_free_vertices_head { -1 }

Friends
class	TriangleCursor

Detailed Description

---

Class Documentation

Slic3r::TriangleSelector::SavedPainting

struct Slic3r::TriangleSelector::SavedPainting

Collaboration diagram for Slic3r::TriangleSelector::SavedPainting:

Class Members
TriangleSplittingData	fuzzy
TriangleMesh	mesh
TriangleSplittingData	mmu
TriangleSplittingData	seam
TriangleSplittingData	supported

Member Enumeration Documentation

CursorType

enum Slic3r::TriangleSelector::CursorType

Enumerator
CIRCLE
SPHERE
POINTER
HEIGHT_RANGE
GAP_FILL

                    {
        CIRCLE,
        SPHERE,
        POINTER,
        // BBS
        HEIGHT_RANGE,
        GAP_FILL,
    };

Partition

enum class Slic3r::TriangleSelector::Partition

strongprivate

Enumerator
First
Second

                         {
        First,
        Second,
    };

Constructor & Destructor Documentation

TriangleSelector()

Slic3r::TriangleSelector::TriangleSelector ( const TriangleMesh & mesh, float edge_limit = 0.6f )

explicit

    : m_mesh{mesh}, m_neighbors(its_face_neighbors(mesh.its)), m_face_normals(its_face_normals(mesh.its)), m_edge_limit(edge_limit)
{
    reset();
}

References Slic3r::its_face_neighbors(), Slic3r::its_face_normals(), m_edge_limit, m_face_normals, m_mesh, m_neighbors, and reset().

Referenced by Slic3r::GUI::TriangleSelectorGUI::TriangleSelectorGUI(), remap_painting(), and serialize().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

append_touching_edges()

void Slic3r::TriangleSelector::append_touching_edges ( int itriangle, int vertexi, int vertexj, std::vector< Vec2i32 > & touching_edges_out ) const

private

{
    if (itriangle == -1)
        return;
 
    auto process_subtriangle = [this, &itriangle, &vertexi, &vertexj, &touching_edges_out](const int subtriangle_idx, Partition partition) -> void {
        assert(subtriangle_idx != -1);
        if (!m_triangles[subtriangle_idx].is_split()) {
            if (!m_triangles[subtriangle_idx].is_selected_by_seed_fill()) {
                int midpoint = this->triangle_midpoint(itriangle, vertexi, vertexj);
                if (partition == Partition::First && midpoint != -1) {
                    touching_edges_out.emplace_back(vertexi, midpoint);
                } else if (partition == Partition::First && midpoint == -1) {
                    touching_edges_out.emplace_back(vertexi, vertexj);
                } else {
                    assert(midpoint != -1 && partition == Partition::Second);
                    touching_edges_out.emplace_back(midpoint, vertexj);
                }
            }
        } else if (int midpoint = this->triangle_midpoint(itriangle, vertexi, vertexj); midpoint != -1)
            append_touching_edges(subtriangle_idx, partition == Partition::First ? vertexi : midpoint, partition == Partition::First ? midpoint : vertexj,
                                  touching_edges_out);
        else
            append_touching_edges(subtriangle_idx, vertexi, vertexj, touching_edges_out);
    };
 
    std::pair<int, int> touching = this->triangle_subtriangles(itriangle, vertexi, vertexj);
    if (touching.first != -1)
        process_subtriangle(touching.first, Partition::First);
 
    if (touching.second != -1)
        process_subtriangle(touching.second, Partition::Second);
}

References append_touching_edges(), First, m_triangles, Second, triangle_midpoint(), and triangle_subtriangles().

Referenced by append_touching_edges(), and get_seed_fill_contour_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

append_touching_subtriangles()

void Slic3r::TriangleSelector::append_touching_subtriangles ( int itriangle, int vertexi, int vertexj, std::vector< int > & touching_subtriangles_out ) const

protected

{
    if (itriangle == -1)
        return;
 
    auto process_subtriangle = [this, &itriangle, &vertexi, &vertexj, &touching_subtriangles_out](const int subtriangle_idx, Partition partition) -> void {
        assert(subtriangle_idx != -1);
        if (!m_triangles[subtriangle_idx].is_split())
            touching_subtriangles_out.emplace_back(subtriangle_idx);
        else if (int midpoint = this->triangle_midpoint(itriangle, vertexi, vertexj); midpoint != -1)
            append_touching_subtriangles(subtriangle_idx, partition == Partition::First ? vertexi : midpoint, partition == Partition::First ? midpoint : vertexj, touching_subtriangles_out);
        else
            append_touching_subtriangles(subtriangle_idx, vertexi, vertexj, touching_subtriangles_out);
    };
 
    std::pair<int, int> touching = this->triangle_subtriangles(itriangle, vertexi, vertexj);
    if (touching.first != -1)
        process_subtriangle(touching.first, Partition::First);
 
    if (touching.second != -1)
        process_subtriangle(touching.second, Partition::Second);
}

References append_touching_subtriangles(), First, m_triangles, Second, triangle_midpoint(), and triangle_subtriangles().

Referenced by append_touching_subtriangles(), bucket_fill_select_triangles(), and Slic3r::GUI::TriangleSelectorPatch::update_triangles_per_patch().

Here is the call graph for this function:

Here is the caller graph for this function:

bucket_fill_select_triangles()

void Slic3r::TriangleSelector::bucket_fill_select_triangles	(	const Vec3f &	hit,
		int	facet_start,
		const ClippingPlane &	clp,
		float	seed_fill_angle,
		bool	propagate,
		bool	force_reselection = false )

{
    int start_facet_idx = select_unsplit_triangle(hit, facet_start);
    assert(start_facet_idx != -1);
    // Recompute bucket fill only if the cursor is pointing on facet unselected by bucket fill or a clipping plane is active.
    if (start_facet_idx == -1 || (m_triangles[start_facet_idx].is_selected_by_seed_fill() && !force_reselection && !clp.is_active()))
        return;
 
    assert(!m_triangles[start_facet_idx].is_split());
    EnforcerBlockerType start_facet_state = m_triangles[start_facet_idx].get_state();
    this->seed_fill_unselect_all_triangles();
 
    if (!propagate) {
        m_triangles[start_facet_idx].select_by_seed_fill();
        return;
    }
 
    // seed_fill_angle < 0.f to disable edge detection
    const double facet_angle_limit = (seed_fill_angle < 0.f ? -1.f : cos(Geometry::deg2rad(seed_fill_angle))) - EPSILON;
 
    auto get_all_touching_triangles = [this](int facet_idx, const Vec3i32 &neighbors, const Vec3i32 &neighbors_propagated) -> std::vector<int> {
        assert(facet_idx != -1 && facet_idx < int(m_triangles.size()));
        assert(this->verify_triangle_neighbors(m_triangles[facet_idx], neighbors));
        std::vector<int> touching_triangles;
        Vec3i32            vertices = {m_triangles[facet_idx].verts_idxs[0], m_triangles[facet_idx].verts_idxs[1], m_triangles[facet_idx].verts_idxs[2]};
        append_touching_subtriangles(neighbors(0), vertices(1), vertices(0), touching_triangles);
        append_touching_subtriangles(neighbors(1), vertices(2), vertices(1), touching_triangles);
        append_touching_subtriangles(neighbors(2), vertices(0), vertices(2), touching_triangles);
 
        for (int neighbor_idx : neighbors_propagated)
            if (neighbor_idx != -1 && !m_triangles[neighbor_idx].is_split())
                touching_triangles.emplace_back(neighbor_idx);
 
        return touching_triangles;
    };
 
    auto [neighbors, neighbors_propagated] = this->precompute_all_neighbors();
    std::vector<bool>  visited(m_triangles.size(), false);
    std::queue<int>    facet_queue;
 
    facet_queue.push(start_facet_idx);
    while (!facet_queue.empty()) {
        int current_facet = facet_queue.front();
        facet_queue.pop();
        assert(!m_triangles[current_facet].is_split());
 
        if (!visited[current_facet]) {
            m_triangles[current_facet].select_by_seed_fill();
 
            std::vector<int> touching_triangles = get_all_touching_triangles(current_facet, neighbors[current_facet], neighbors_propagated[current_facet]);
            for(const int tr_idx : touching_triangles) {
                if (tr_idx < 0 || visited[tr_idx] || m_triangles[tr_idx].get_state() != start_facet_state || is_facet_clipped(tr_idx, clp))
                    continue;
 
                const Vec3f& n1 = m_face_normals[m_triangles[tr_idx].source_triangle];
                const Vec3f& n2 = m_face_normals[m_triangles[current_facet].source_triangle];
                if (seed_fill_angle >= -EPSILON && std::clamp(n1.dot(n2), 0.f, 1.f) < facet_angle_limit)
                    continue;
 
                assert(!m_triangles[tr_idx].is_split());
                facet_queue.push(tr_idx);
            }
        }
 
        visited[current_facet] = true;
    }
}

References append_touching_subtriangles(), Slic3r::Geometry::deg2rad(), EPSILON, Slic3r::TriangleSelector::ClippingPlane::is_active(), is_facet_clipped(), m_face_normals, m_triangles, precompute_all_neighbors(), seed_fill_unselect_all_triangles(), select_unsplit_triangle(), and verify_triangle_neighbors().

Here is the call graph for this function:

child_neighbors()

Vec3i32 Slic3r::TriangleSelector::child_neighbors ( const Triangle & tr, const Vec3i32 & neighbors, int child_idx ) const

private

{
    assert(this->verify_triangle_neighbors(tr, neighbors));
 
    assert(child_idx >= 0 && child_idx <= tr.number_of_split_sides());
    int   i = tr.special_side();
    int   j = next_idx_modulo(i, 3);
    int   k = next_idx_modulo(j, 3);
 
    Vec3i32 out;
    switch (tr.number_of_split_sides()) {
    case 1:
        switch (child_idx) {
        case 0:
            out(0) = neighbors(i);
            out(1) = this->neighbor_child(neighbors(j), tr.verts_idxs[k], tr.verts_idxs[j], Partition::Second);
            out(2) = tr.children[1];
            break;
        default:
            assert(child_idx == 1);
            out(0) = this->neighbor_child(neighbors(j), tr.verts_idxs[k], tr.verts_idxs[j], Partition::First);
            out(1) = neighbors(k);
            out(2) = tr.children[0];
            break;
        }
        break;
 
    case 2:
        switch (child_idx) {
        case 0:
            out(0) = this->neighbor_child(neighbors(i), tr.verts_idxs[j], tr.verts_idxs[i], Partition::Second);
            out(1) = tr.children[1];
            out(2) = this->neighbor_child(neighbors(k), tr.verts_idxs[i], tr.verts_idxs[k], Partition::First);
            break;
        case 1:
            assert(child_idx == 1);
            out(0) = this->neighbor_child(neighbors(i), tr.verts_idxs[j], tr.verts_idxs[i], Partition::First);
            out(1) = tr.children[2];
            out(2) = tr.children[0];
            break;
        default:
            assert(child_idx == 2);
            out(0) = neighbors(j);
            out(1) = this->neighbor_child(neighbors(k), tr.verts_idxs[i], tr.verts_idxs[k], Partition::Second);
            out(2) = tr.children[1];
            break;
        }
        break;
 
    case 3:
        assert(tr.special_side() == 0);
        switch (child_idx) {
        case 0:
            out(0) = this->neighbor_child(neighbors(0), tr.verts_idxs[1], tr.verts_idxs[0], Partition::Second);
            out(1) = tr.children[3];
            out(2) = this->neighbor_child(neighbors(2), tr.verts_idxs[0], tr.verts_idxs[2], Partition::First);
            break;
        case 1:
            out(0) = this->neighbor_child(neighbors(0), tr.verts_idxs[1], tr.verts_idxs[0], Partition::First);
            out(1) = this->neighbor_child(neighbors(1), tr.verts_idxs[2], tr.verts_idxs[1], Partition::Second);
            out(2) = tr.children[3];
            break;
        case 2:
            out(0) = this->neighbor_child(neighbors(1), tr.verts_idxs[2], tr.verts_idxs[1], Partition::First);
            out(1) = this->neighbor_child(neighbors(2), tr.verts_idxs[0], tr.verts_idxs[2], Partition::Second);
            out(2) = tr.children[3];
            break;
        default:
            assert(child_idx == 3);
            out(0) = tr.children[1];
            out(1) = tr.children[2];
            out(2) = tr.children[0];
            break;
        }
        break;
 
    default:
        assert(false);
    }
 
    assert(this->verify_triangle_neighbors(tr, neighbors));
    assert(this->verify_triangle_neighbors(m_triangles[tr.children[child_idx]], out));
    return out;
}

References Slic3r::TriangleSelector::Triangle::children, First, m_triangles, neighbor_child(), Slic3r::next_idx_modulo(), Slic3r::TriangleSelector::Triangle::number_of_split_sides(), Second, Slic3r::TriangleSelector::Triangle::special_side(), verify_triangle_neighbors(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by child_neighbors_propagated(), deserialize(), get_seed_fill_contour_recursive(), perform_split(), and precompute_all_neighbors_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

child_neighbors_propagated()

Vec3i32 Slic3r::TriangleSelector::child_neighbors_propagated ( const Triangle & tr, const Vec3i32 & neighbors_propagated, int child_idx, const Vec3i32 & child_neighbors ) const

private

{
    int i = tr.special_side();
    int j = next_idx_modulo(i, 3);
    int k = next_idx_modulo(j, 3);
 
    Vec3i32 out = child_neighbors;
    auto  replace_if_not_exists = [&out, &neighbors_propagated](int index_to_replace, int neighbor_idx) {
        if (out(index_to_replace) == -1)
            out(index_to_replace) = neighbors_propagated(neighbor_idx);
    };
 
    switch (tr.number_of_split_sides()) {
    case 1:
        switch (child_idx) {
        case 0:
            replace_if_not_exists(0, i);
            replace_if_not_exists(1, j);
            break;
        default:
            assert(child_idx == 1);
            replace_if_not_exists(0, j);
            replace_if_not_exists(1, k);
            break;
        }
        break;
 
    case 2:
        switch (child_idx) {
        case 0:
            replace_if_not_exists(0, i);
            replace_if_not_exists(2, k);
            break;
        case 1:
            assert(child_idx == 1);
            replace_if_not_exists(0, i);
            break;
        default:
            assert(child_idx == 2);
            replace_if_not_exists(0, j);
            replace_if_not_exists(1, k);
            break;
        }
        break;
 
    case 3:
        assert(tr.special_side() == 0);
        switch (child_idx) {
        case 0:
            replace_if_not_exists(0, 0);
            replace_if_not_exists(2, 2);
            break;
        case 1:
            replace_if_not_exists(0, 0);
            replace_if_not_exists(1, 1);
            break;
        case 2:
            replace_if_not_exists(0, 1);
            replace_if_not_exists(1, 2);
            break;
        default:
            assert(child_idx == 3);
            break;
        }
        break;
 
    default: assert(false);
    }
 
    return out;
}

References child_neighbors(), Slic3r::next_idx_modulo(), Slic3r::TriangleSelector::Triangle::number_of_split_sides(), and Slic3r::TriangleSelector::Triangle::special_side().

Here is the call graph for this function:

deserialize()

void Slic3r::TriangleSelector::deserialize	(	const TriangleSplittingData &	data,
		bool	needs_reset = true,
		EnforcerBlockerType	max_ebt = EnforcerBlockerType::ExtruderMax,
		EnforcerBlockerType	to_delete_filament = EnforcerBlockerType::NONE,
		EnforcerBlockerType	replace_filament = EnforcerBlockerType::NONE )

{
    if (needs_reset)
        reset(); // dump any current state
    for (auto [triangle_id, ibit] : data.triangles_to_split) {
        if (triangle_id >= int(m_triangles.size())) {
            BOOST_LOG_TRIVIAL(info) << __FUNCTION__ << "array bound:error:triangle_id >= int(m_triangles.size())";
            return;
        }
    }
    // Reserve number of triangles as if each triangle was saved with 4 bits.
    // With MMU painting this estimate may be somehow low, but better than nothing.
    m_triangles.reserve(std::max(m_mesh.its.indices.size(), data.bitstream.size() / 4));
    // Number of triangles is twice the number of vertices on a large manifold mesh of genus zero.
    // Here the triangles count account for both the nodes and leaves, thus the following line may overestimate.
    m_vertices.reserve(std::max(m_mesh.its.vertices.size(), m_triangles.size() / 2));
 
    // Vector to store all parents that have offsprings.
    struct ProcessingInfo {
        int facet_id = 0;
        Vec3i32 neighbors { -1, -1, -1 };
        int processed_children = 0;
        int total_children = 0;
    };
    // Depth-first queue of a source mesh triangle and its childern.
    // kept outside of the loop to avoid re-allocating inside the loop.
    std::vector<ProcessingInfo> parents;
 
    for (auto [triangle_id, ibit] : data.triangles_to_split) {
        assert(triangle_id < int(m_triangles.size()));
        // Set when the bitstream runs out or holds an impossible split before this triangle's tree is complete.
        bool corrupt = false;
        auto next_nibble = [&data, &ibit = ibit, &corrupt]() {
            int n = 0;
            if (! data.read_nibble(ibit, n))
                corrupt = true;
            return n;
        };
        // Decode a leaf state stored behind the "11" prefix: one nibble of (state-3) for states
        // 3..17, or 0b1111 followed by a nibble of (state-18) above that.
        auto decode_leaf_state = [&next_nibble]() {
            const int nibble = next_nibble();
            return EnforcerBlockerType(nibble == 0b1111 ? next_nibble() + 18 : nibble + 3);
        };
 
        parents.clear();
        while (true) {
            // Read next triangle info.
            int code = next_nibble();
            int num_of_split_sides = code & 0b11;
            int num_of_children = num_of_split_sides == 0 ? 0 : num_of_split_sides + 1;
            bool is_split = num_of_children != 0;
            // Only valid if not is_split.
            auto state = is_split ? EnforcerBlockerType::NONE : ((code & 0b1100) == 0b1100 ? decode_leaf_state() : EnforcerBlockerType(code >> 2));
            if (is_split && ! split_code_valid(code))
                corrupt = true;
            if (corrupt)
                break;
 
            // BBS
            if (state == to_delete_filament)
                state = replace_filament;
            else if (to_delete_filament != EnforcerBlockerType::NONE && state != EnforcerBlockerType::NONE) {
                state = state > to_delete_filament ? EnforcerBlockerType((int)state - 1) : state;
            }
 
            if (state > max_ebt) {
                assert(false);
                state = EnforcerBlockerType::NONE;
            }
 
            // Only valid if is_split.
            int special_side = num_of_split_sides == 3 ? 0 : code >> 2;
 
            // Take care of the first iteration separately, so handling of the others is simpler.
            if (parents.empty()) {
                if (is_split) {
                    // root is split, add it into list of parents and split it.
                    // then go to the next.
                    Vec3i32 neighbors = m_neighbors[triangle_id];
                    parents.push_back({triangle_id, neighbors, 0, num_of_children});
                    m_triangles[triangle_id].set_division(num_of_split_sides, special_side);
                    perform_split(triangle_id, neighbors, EnforcerBlockerType::NONE);
                    continue;
                } else {
                    // root is not split. just set the state and that's it.
                    m_triangles[triangle_id].set_state(state);
                    break;
                }
            }
 
            // This is not the first iteration. This triangle is a child of last seen parent.
            assert(! parents.empty());
            assert(parents.back().processed_children < parents.back().total_children);
 
            if (ProcessingInfo& last = parents.back();  is_split) {
                // split the triangle and save it as parent of the next ones.
                const Triangle &tr = m_triangles[last.facet_id];
                int   child_idx = last.total_children - last.processed_children - 1;
                Vec3i32 neighbors = this->child_neighbors(tr, last.neighbors, child_idx);
                int this_idx = tr.children[child_idx];
                m_triangles[this_idx].set_division(num_of_split_sides, special_side);
                perform_split(this_idx, neighbors, EnforcerBlockerType::NONE);
                parents.push_back({this_idx, neighbors, 0, num_of_children});
            } else {
                // this triangle belongs to last split one
                int child_idx = last.total_children - last.processed_children - 1;
                m_triangles[m_triangles[last.facet_id].children[child_idx]].set_state(state);
                ++last.processed_children;
            }
 
            // If all children of the past parent triangle are claimed, move to grandparent.
            while (parents.back().processed_children == parents.back().total_children) {
                parents.pop_back();
 
                if (parents.empty())
                    break;
 
                // And increment the grandparent children counter, because
                // we have just finished that branch and got back here.
                ++parents.back().processed_children;
            }
 
            // In case we popped back the root, we should be done.
            if (parents.empty())
                break;
        }
 
        if (corrupt) {
            // Every split above allocated all of its children, so the partial tree unwinds cleanly.
            BOOST_LOG_TRIVIAL(warning) << __FUNCTION__ << ": malformed paint data, dropping paint of triangle " << triangle_id;
            undivide_triangle(triangle_id);
            m_triangles[triangle_id].set_state(EnforcerBlockerType::NONE);
        }
    }
}

References Slic3r::TriangleSelector::TriangleSplittingData::bitstream, child_neighbors(), Slic3r::TriangleSelector::Triangle::children, m_mesh, m_neighbors, m_triangles, m_vertices, Slic3r::NONE, perform_split(), Slic3r::TriangleSelector::TriangleSplittingData::read_nibble(), reset(), Slic3r::split_code_valid(), Slic3r::TriangleSelector::TriangleSplittingData::triangles_to_split, and undivide_triangle().

Referenced by Slic3r::build_texture_displacement_in_place(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::build_texture_displacement_v2(), Slic3r::GUI::GLGizmoTextureDisplacement::collect_paint_region(), Slic3r::extract_painted_patch(), Slic3r::SeamPlacerImpl::gather_enforcers_blockers(), Slic3r::FacetsAnnotation::get_facets(), Slic3r::FacetsAnnotation::get_facets(), Slic3r::FacetsAnnotation::get_facets_strict(), Slic3r::GUI::GLGizmoTextureDisplacement::painted_colors(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::prepare_sampleable_layers(), Slic3r::GUI::GLGizmoTextureDisplacement::rebuild_other_paint_overlay(), remap_painting(), Slic3r::FacetsAnnotation::remap_states(), Slic3r::GUI::anonymous_namespace{GLGizmoTextureDisplacement.cpp}::remap_texture_paint_spatial(), Slic3r::FacetsAnnotation::set_enforcer_block_type_limit(), Slic3r::FacetsAnnotation::shift_states_above(), and Slic3r::transfer_facet_paint().

Here is the call graph for this function:

Here is the caller graph for this function:

extract_used_facet_states()

std::vector< EnforcerBlockerType > Slic3r::TriangleSelector::extract_used_facet_states ( const TriangleSplittingData & data )

static

{
    std::vector<EnforcerBlockerType> out;
    for (size_t i = 0; i < data.used_states.size(); ++i) {
        if (data.used_states[i])
            out.push_back(static_cast<EnforcerBlockerType>(i));
    }
    return out;
}

References Slic3r::TriangleSelector::TriangleSplittingData::used_states.

Referenced by Slic3r::GUI::GLGizmoTextureDisplacement::painted_colors(), and Slic3r::GUI::GLGizmoMmuSegmentation::update_used_filaments().

Here is the caller graph for this function:

garbage_collect()

void Slic3r::TriangleSelector::garbage_collect

(

)

{
    // First make a map from old to new triangle indices.
    int new_idx = m_orig_size_indices;
    std::vector<int> new_triangle_indices(m_triangles.size(), -1);
    for (int i = m_orig_size_indices; i<int(m_triangles.size()); ++i)
        if (m_triangles[i].valid())
            new_triangle_indices[i] = new_idx ++;
 
    // Now we know which vertices are not referenced anymore. Make a map
    // from old idxs to new ones, like we did for triangles.
    new_idx = m_orig_size_vertices;
    std::vector<int> new_vertices_indices(m_vertices.size(), -1);
    for (int i=m_orig_size_vertices; i<int(m_vertices.size()); ++i) {
        assert(m_vertices[i].ref_cnt >= 0);
        if (m_vertices[i].ref_cnt != 0)
            new_vertices_indices[i] = new_idx ++;
    }
 
    // We can remove all invalid triangles and vertices that are no longer referenced.
    m_triangles.erase(std::remove_if(m_triangles.begin()+m_orig_size_indices, m_triangles.end(),
                          [](const Triangle& tr) { return ! tr.valid(); }),
                      m_triangles.end());
    m_vertices.erase(std::remove_if(m_vertices.begin()+m_orig_size_vertices, m_vertices.end(),
                          [](const Vertex& vert) { return vert.ref_cnt == 0; }),
                      m_vertices.end());
 
    // Now go through all remaining triangles and update changed indices.
    for (Triangle& tr : m_triangles) {
        assert(tr.valid());
 
        if (tr.is_split()) {
            // There are children. Update their indices.
            for (int j=0; j<=tr.number_of_split_sides(); ++j) {
                assert(new_triangle_indices[tr.children[j]] != -1);
                tr.children[j] = new_triangle_indices[tr.children[j]];
            }
        }
 
        // Update indices into m_vertices. The original vertices are never
        // touched and need not be reindexed.
        for (int& idx : tr.verts_idxs) {
            if (idx >= m_orig_size_vertices) {
                assert(new_vertices_indices[idx] != -1);
                idx = new_vertices_indices[idx];
            }
        }
    }
 
    m_invalid_triangles = 0;
    m_free_triangles_head = -1;
    m_free_vertices_head = -1;
}

References Slic3r::TriangleSelector::Triangle::children, Slic3r::TriangleSelector::Triangle::is_split(), m_free_triangles_head, m_free_vertices_head, m_invalid_triangles, m_orig_size_indices, m_orig_size_vertices, m_triangles, m_vertices, Slic3r::TriangleSelector::Triangle::number_of_split_sides(), Slic3r::TriangleSelector::Triangle::valid(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by select_triangle().

Here is the call graph for this function:

Here is the caller graph for this function:

get_facets() [1/2]

indexed_triangle_set Slic3r::TriangleSelector::get_facets

(

EnforcerBlockerType

state

)

const

{
    indexed_triangle_set out;
    std::vector<int> vertex_map(m_vertices.size(), -1);
    for (const Triangle& tr : m_triangles) {
        if (tr.valid() && ! tr.is_split() && tr.get_state() == state) {
            stl_triangle_vertex_indices indices;
            for (int i=0; i<3; ++i) {
                int j = tr.verts_idxs[i];
                if (vertex_map[j] == -1) {
                    vertex_map[j] = int(out.vertices.size());
                    out.vertices.emplace_back(m_vertices[j].v);
                }
                indices[i] = vertex_map[j];
            }
            out.indices.emplace_back(indices);
        }
    }
    return out;
}

References m_triangles, and m_vertices.

Referenced by Slic3r::SeamPlacerImpl::gather_enforcers_blockers(), Slic3r::FacetsAnnotation::get_facets(), Slic3r::FacetsAnnotation::get_facets(), and Slic3r::transfer_facet_paint().

Here is the caller graph for this function:

get_facets() [2/2]

void Slic3r::TriangleSelector::get_facets

(

std::vector< indexed_triangle_set > &

facets_per_type

)

const

{
    facets_per_type.clear();
 
    for (int type = (int)EnforcerBlockerType::NONE; type <= (int)EnforcerBlockerType::ExtruderMax; type++) {
        facets_per_type.emplace_back();
        indexed_triangle_set& its = facets_per_type.back();
        std::vector<int> vertex_map(m_vertices.size(), -1);
 
        for (const Triangle& tr : m_triangles) {
            if (tr.valid() && !tr.is_split() && tr.get_state() == (EnforcerBlockerType)type) {
                stl_triangle_vertex_indices indices;
                for (int i = 0; i < 3; ++i) {
                    int j = tr.verts_idxs[i];
                    if (vertex_map[j] == -1) {
                        vertex_map[j] = int(its.vertices.size());
                        its.vertices.emplace_back(m_vertices[j].v);
                    }
                    indices[i] = vertex_map[j];
                }
                its.indices.emplace_back(indices);
            }
        }
    }
}

References Slic3r::ExtruderMax, m_triangles, m_vertices, and Slic3r::NONE.

get_facets_split_by_tjoints()

void Slic3r::TriangleSelector::get_facets_split_by_tjoints ( const Vec3i32 & vertices, const Vec3i32 & neighbors, std::vector< stl_triangle_vertex_indices > & out_triangles ) const

private

{
// Export this triangle, but first collect the T-joint vertices along its edges.
    Vec3i32 midpoints(
        this->triangle_midpoint(neighbors(0), vertices(1), vertices(0)),
        this->triangle_midpoint(neighbors(1), vertices(2), vertices(1)),
        this->triangle_midpoint(neighbors(2), vertices(0), vertices(2)));
    int splits = (midpoints(0) != -1) + (midpoints(1) != -1) + (midpoints(2) != -1);
    switch (splits) {
    case 0:
        // Just emit this triangle.
        out_triangles.emplace_back(vertices(0), vertices(1), vertices(2));
        break;
    case 1:
    {
        // Split to two triangles
        int i = midpoints(0) != -1 ? 2 : midpoints(1) != -1 ? 0 : 1;
        int j = next_idx_modulo(i, 3);
        int k = next_idx_modulo(j, 3);
        this->get_facets_split_by_tjoints(
            { vertices(i), vertices(j), midpoints(j) },
            { neighbors(i),
              this->neighbor_child(neighbors(j), vertices(k), vertices(j), Partition::Second),
              -1 },
              out_triangles);
        this->get_facets_split_by_tjoints(
            { midpoints(j), vertices(k), vertices(i) },
            { this->neighbor_child(neighbors(j), vertices(k), vertices(j), Partition::First),
              neighbors(k),
              -1 },
              out_triangles);
        break;
    }
    case 2:
    {
        // Split to three triangles.
        int i = midpoints(0) == -1 ? 2 : midpoints(1) == -1 ? 0 : 1;
        int j = next_idx_modulo(i, 3);
        int k = next_idx_modulo(j, 3);
        this->get_facets_split_by_tjoints(
            { vertices(i), midpoints(i), midpoints(k) },
            { this->neighbor_child(neighbors(i), vertices(j), vertices(i), Partition::Second),
              -1,
              this->neighbor_child(neighbors(k), vertices(i), vertices(k), Partition::First) },
              out_triangles);
        this->get_facets_split_by_tjoints(
            { midpoints(i), vertices(j), midpoints(k) },
            { this->neighbor_child(neighbors(i), vertices(j), vertices(i), Partition::First),
              -1, -1 },
              out_triangles);
        this->get_facets_split_by_tjoints(
            { vertices(j), vertices(k), midpoints(k) },
            { neighbors(j),
              this->neighbor_child(neighbors(k), vertices(i), vertices(k), Partition::Second),
              -1 },
              out_triangles);
        break;
    }
    default:
        assert(splits == 3);
        // Split to 4 triangles.
        this->get_facets_split_by_tjoints(
            { vertices(0), midpoints(0), midpoints(2) },
            { this->neighbor_child(neighbors(0), vertices(1), vertices(0), Partition::Second),
              -1,
              this->neighbor_child(neighbors(2), vertices(0), vertices(2), Partition::First) },
              out_triangles);
        this->get_facets_split_by_tjoints(
            { midpoints(0), vertices(1), midpoints(1) },
            { this->neighbor_child(neighbors(0), vertices(1), vertices(0), Partition::First),
              this->neighbor_child(neighbors(1), vertices(2), vertices(1), Partition::Second),
              -1 },
              out_triangles);
        this->get_facets_split_by_tjoints(
            { midpoints(1), vertices(2), midpoints(2) },
            { this->neighbor_child(neighbors(1), vertices(2), vertices(1), Partition::First),
              this->neighbor_child(neighbors(2), vertices(0), vertices(2), Partition::Second),
              -1 },
              out_triangles);
        out_triangles.emplace_back(midpoints);
        break;
    }
}

References First, get_facets_split_by_tjoints(), neighbor_child(), Slic3r::next_idx_modulo(), Second, and triangle_midpoint().

Referenced by get_facets_split_by_tjoints(), and get_facets_strict_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

get_facets_strict()

indexed_triangle_set Slic3r::TriangleSelector::get_facets_strict	(	EnforcerBlockerType	state,
		std::vector< int > *	out_source = nullptr ) const

{
    indexed_triangle_set out;
    if (out_source)
        out_source->clear();
 
    size_t num_vertices = 0;
    for (const Vertex &v : m_vertices)
        if (v.ref_cnt > 0)
            ++ num_vertices;
    out.vertices.reserve(num_vertices);
    std::vector<int> vertex_map(m_vertices.size(), -1);
    for (size_t i = 0; i < m_vertices.size(); ++ i)
        if (const Vertex &v = m_vertices[i]; v.ref_cnt > 0) {
            vertex_map[i] = int(out.vertices.size());
            out.vertices.emplace_back(v.v);
        }
 
    for (int itriangle = 0; itriangle < m_orig_size_indices; ++ itriangle) {
        this->get_facets_strict_recursive(m_triangles[itriangle], m_neighbors[itriangle], state, out.indices);
        // Everything the recursion just appended came from this original triangle, whatever depth it
        // was split to. Recording it here keeps the recursive helpers untouched.
        if (out_source)
            out_source->resize(out.indices.size(), itriangle);
    }
 
    for (auto &triangle : out.indices)
        for (int i = 0; i < 3; ++ i)
            triangle(i) = vertex_map[triangle(i)];
 
    return out;
}

References get_facets_strict_recursive(), m_neighbors, m_orig_size_indices, m_triangles, and m_vertices.

Referenced by Slic3r::build_texture_displacement_in_place(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::build_texture_displacement_v2(), Slic3r::GUI::GLGizmoTextureDisplacement::collect_paint_region(), Slic3r::extract_painted_patch(), Slic3r::SeamPlacerImpl::gather_enforcers_blockers(), Slic3r::FacetsAnnotation::get_facets_strict(), Slic3r::GUI::GLGizmoTextureDisplacement::painted_colors(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::prepare_sampleable_layers(), Slic3r::GUI::GLGizmoTextureDisplacement::rebuild_other_paint_overlay(), and Slic3r::GUI::anonymous_namespace{GLGizmoTextureDisplacement.cpp}::remap_texture_paint_spatial().

Here is the call graph for this function:

Here is the caller graph for this function:

get_facets_strict_recursive()

void Slic3r::TriangleSelector::get_facets_strict_recursive ( const Triangle & tr, const Vec3i32 & neighbors, EnforcerBlockerType state, std::vector< stl_triangle_vertex_indices > & out_triangles ) const

private

{
    if (tr.is_split()) {
        for (int i = 0; i <= tr.number_of_split_sides(); ++ i)
            this->get_facets_strict_recursive(
                m_triangles[tr.children[i]],
                this->child_neighbors(tr, neighbors, i),
                state, out_triangles);
    } else if (tr.get_state() == state)
        this->get_facets_split_by_tjoints({tr.verts_idxs[0], tr.verts_idxs[1], tr.verts_idxs[2]}, neighbors, out_triangles);
}

References Slic3r::TriangleSelector::Triangle::children, get_facets_split_by_tjoints(), get_facets_strict_recursive(), Slic3r::TriangleSelector::Triangle::get_state(), Slic3r::TriangleSelector::Triangle::is_split(), m_triangles, Slic3r::TriangleSelector::Triangle::number_of_split_sides(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by get_facets_strict(), and get_facets_strict_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

get_seed_fill_contour()

std::vector< Vec2i32 > Slic3r::TriangleSelector::get_seed_fill_contour

(

)

const

                                                                 {
    std::vector<Vec2i32> edges_out;
    for (int facet_idx = 0; facet_idx < this->m_orig_size_indices; ++facet_idx) {
        const Vec3i32 neighbors = m_neighbors[facet_idx];
        assert(this->verify_triangle_neighbors(m_triangles[facet_idx], neighbors));
        this->get_seed_fill_contour_recursive(facet_idx, neighbors, neighbors, edges_out);
    }
 
    return edges_out;
}

References get_seed_fill_contour_recursive(), m_neighbors, m_orig_size_indices, m_triangles, and verify_triangle_neighbors().

Referenced by Slic3r::GUI::TriangleSelectorGUI::update_paint_contour().

Here is the call graph for this function:

Here is the caller graph for this function:

get_seed_fill_contour_recursive()

void Slic3r::TriangleSelector::get_seed_fill_contour_recursive ( int facet_idx, const Vec3i32 & neighbors, const Vec3i32 & neighbors_propagated, std::vector< Vec2i32 > & edges_out ) const

private

                                                                                                                                                                              {
    assert(facet_idx != -1 && facet_idx < int(m_triangles.size()));
    assert(this->verify_triangle_neighbors(m_triangles[facet_idx], neighbors));
    const Triangle *tr = &m_triangles[facet_idx];
    if (!tr->valid())
        return;
 
    if (tr->is_split()) {
        int num_of_children = tr->number_of_split_sides() + 1;
        if (num_of_children != 1) {
            for (int i = 0; i < num_of_children; ++i) {
                assert(i < int(tr->children.size()));
                assert(tr->children[i] < int(m_triangles.size()));
                // Recursion, deep first search over the children of this triangle.
                // All children of this triangle were created by splitting a single source triangle of the original mesh.
                const Vec3i32 child_neighbors = this->child_neighbors(*tr, neighbors, i);
                this->get_seed_fill_contour_recursive(tr->children[i], child_neighbors,
                                                      this->child_neighbors_propagated(*tr, neighbors_propagated, i, child_neighbors), edges_out);
            }
        }
    } else if (tr->is_selected_by_seed_fill()) {
        Vec3i32 vertices = {m_triangles[facet_idx].verts_idxs[0], m_triangles[facet_idx].verts_idxs[1], m_triangles[facet_idx].verts_idxs[2]};
        append_touching_edges(neighbors(0), vertices(1), vertices(0), edges_out);
        append_touching_edges(neighbors(1), vertices(2), vertices(1), edges_out);
        append_touching_edges(neighbors(2), vertices(0), vertices(2), edges_out);
 
        // It appends the edges that are touching the triangle only by part of the edge that means the triangles are from lower depth.
        for (int idx = 0; idx < 3; ++idx)
            if (int neighbor_tr_idx = neighbors_propagated(idx); neighbor_tr_idx != -1 && !m_triangles[neighbor_tr_idx].is_split() && !m_triangles[neighbor_tr_idx].is_selected_by_seed_fill())
                edges_out.emplace_back(vertices(idx), vertices(next_idx_modulo(idx, 3)));
    }
}

References append_touching_edges(), child_neighbors(), Slic3r::TriangleSelector::Triangle::children, get_seed_fill_contour_recursive(), Slic3r::TriangleSelector::Triangle::is_selected_by_seed_fill(), Slic3r::TriangleSelector::Triangle::is_split(), m_triangles, Slic3r::next_idx_modulo(), Slic3r::TriangleSelector::Triangle::number_of_split_sides(), Slic3r::TriangleSelector::Triangle::valid(), and verify_triangle_neighbors().

Referenced by get_seed_fill_contour(), and get_seed_fill_contour_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

has_facets() [1/2]

bool Slic3r::TriangleSelector::has_facets ( const TriangleSplittingData & data, EnforcerBlockerType test_state )

static

                                                                                                         {
    // Depth-first queue of a number of unvisited children.
    // Kept outside of the loop to avoid re-allocating inside the loop.
    std::vector<int> parents_children;
    parents_children.reserve(64);
 
    for (const TriangleBitStreamMapping &triangle_id_and_ibit : data.triangles_to_split) {
        int ibit = triangle_id_and_ibit.bitstream_start_idx;
        // Stop reading a triangle whose stream is truncated.
        bool truncated = false;
        auto next_nibble = [&data, &ibit = ibit, &truncated]() {
            int n = 0;
            if (! data.read_nibble(ibit, n))
                truncated = true;
            return n;
        };
        // < 0 -> negative of a number of children
        // >= 0 -> state
        auto num_children_or_state = [&next_nibble]() -> int {
            int code               = next_nibble();
            int num_of_split_sides = code & 0b11;
            if (num_of_split_sides != 0)
                return - num_of_split_sides - 1;
            if ((code & 0b1100) != 0b1100)
                return code >> 2;
            // Leaf behind the "11" prefix: one nibble of (state-3), or 0b1111 + (state-18).
            const int nibble = next_nibble();
            return nibble == 0b1111 ? next_nibble() + 18 : nibble + 3;
        };
 
        int state = num_children_or_state();
        if (truncated)
            continue;
        if (state < 0) {
            // Root is split.
            parents_children.clear();
            parents_children.emplace_back(- state);
            do {
                if (-- parents_children.back() >= 0) {
                    int state = num_children_or_state();
                    if (truncated)
                        break;
                    if (state < 0)
                        // Child is split.
                        parents_children.emplace_back(- state);
                    else if (state == int(test_state))
                        // Child is not split and a face of test_state was found.
                        return true;
                } else
                    parents_children.pop_back();
            } while (! parents_children.empty());
        } else if (state == int(test_state))
            // Root is not split and a face of test_state was found.
            return true;
    }
 
    return false;
}

References Slic3r::TriangleSelector::TriangleBitStreamMapping::bitstream_start_idx, Slic3r::TriangleSelector::TriangleSplittingData::read_nibble(), and Slic3r::TriangleSelector::TriangleSplittingData::triangles_to_split.

Here is the call graph for this function:

has_facets() [2/2]

bool Slic3r::TriangleSelector::has_facets

(

EnforcerBlockerType

state

)

const

{
    for (const Triangle& tr : m_triangles)
        if (tr.valid() && ! tr.is_split() && tr.get_state() == state)
            return true;
    return false;
}

References m_triangles.

Referenced by Slic3r::GUI::GLGizmoTextureDisplacement::collect_paint_region(), Slic3r::FacetsAnnotation::has_facets(), and Slic3r::GUI::GLGizmoTextureDisplacement::prepare_mesh().

Here is the caller graph for this function:

is_facet_clipped()

bool Slic3r::TriangleSelector::is_facet_clipped ( int facet_idx, const ClippingPlane & clp ) const

private

{
    for (int vert_idx : m_triangles[facet_idx].verts_idxs)
        if (clp.is_active() && clp.is_mesh_point_clipped(m_vertices[vert_idx].v))
            return true;
 
    return false;
}

References Slic3r::TriangleSelector::ClippingPlane::is_active(), Slic3r::TriangleSelector::ClippingPlane::is_mesh_point_clipped(), m_triangles, and m_vertices.

Referenced by bucket_fill_select_triangles(), and seed_fill_select_triangles().

Here is the call graph for this function:

Here is the caller graph for this function:

neighbor_child() [1/2]

int Slic3r::TriangleSelector::neighbor_child ( const Triangle & tr, int vertexi, int vertexj, Partition partition ) const

private

{
    if (tr.number_of_split_sides() == 0)
        // If this triangle is not split, then there is no upper / lower subtriangle sharing the edge.
        return -1;
 
    // Find the triangle edge.
    int edge = tr.verts_idxs[0] == vertexi ? 0 : tr.verts_idxs[1] == vertexi ? 1 : 2;
    assert(tr.verts_idxs[edge] == vertexi);
    assert(tr.verts_idxs[next_idx_modulo(edge, 3)] == vertexj);
 
    int child_idx;
    if (tr.number_of_split_sides() == 1) {
        if (edge != next_idx_modulo(tr.special_side(), 3))
            // A child may or may not be split at this side.
            return this->neighbor_child(m_triangles[tr.children[edge == tr.special_side() ? 0 : 1]], vertexi, vertexj, partition);
        child_idx = partition == Partition::First ? 0 : 1;
    } else if (tr.number_of_split_sides() == 2) {
        if (edge == next_idx_modulo(tr.special_side(), 3))
            // A child may or may not be split at this side.
            return this->neighbor_child(m_triangles[tr.children[2]], vertexi, vertexj, partition);
        child_idx = edge == tr.special_side() ?
            (partition == Partition::First ? 0 : 1) :
            (partition == Partition::First ? 2 : 0);
    } else {
        assert(tr.number_of_split_sides() == 3);
        assert(tr.special_side() == 0);
        switch(edge) {
        case 0:  child_idx = partition == Partition::First ? 0 : 1; break;
        case 1:  child_idx = partition == Partition::First ? 1 : 2; break;
        default: assert(edge == 2);
                 child_idx = partition == Partition::First ? 2 : 0; break;
        }
    }
    return tr.children[child_idx];
}

References Slic3r::TriangleSelector::Triangle::children, First, m_triangles, neighbor_child(), Slic3r::next_idx_modulo(), Slic3r::TriangleSelector::Triangle::number_of_split_sides(), Slic3r::TriangleSelector::Triangle::special_side(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by child_neighbors(), get_facets_split_by_tjoints(), neighbor_child(), and neighbor_child().

Here is the call graph for this function:

Here is the caller graph for this function:

neighbor_child() [2/2]

int Slic3r::TriangleSelector::neighbor_child ( int itriangle, int vertexi, int vertexj, Partition partition ) const

private

{
    return itriangle == -1 ? -1 : this->neighbor_child(m_triangles[itriangle], vertexi, vertexj, partition);
}

References m_triangles, and neighbor_child().

Here is the call graph for this function:

num_facets()

int Slic3r::TriangleSelector::num_facets

(

EnforcerBlockerType

state

)

const

{
    int cnt = 0;
    for (const Triangle& tr : m_triangles)
        if (tr.valid() && ! tr.is_split() && tr.get_state() == state)
            ++ cnt;
    return cnt;
}

References m_triangles.

perform_split()

void Slic3r::TriangleSelector::perform_split ( int facet_idx, const Vec3i32 & neighbors, EnforcerBlockerType old_state )

private

{
    // Reserve space for the new triangles upfront, so that the reference to this triangle will not change.
    {
        size_t num_triangles_new = m_triangles.size() + m_triangles[facet_idx].number_of_split_sides() + 1;
        if (m_triangles.capacity() < num_triangles_new)
            m_triangles.reserve(next_highest_power_of_2(num_triangles_new));
    }
 
    Triangle &tr = m_triangles[facet_idx];
    assert(tr.is_split());
 
    // indices of triangle vertices
#ifdef NDEBUG
    boost::container::small_vector<int, 6> verts_idxs;
#else // NDEBUG
    // For easier debugging.
    std::vector<int> verts_idxs;
    verts_idxs.reserve(6);
#endif // NDEBUG
    for (int j=0, idx = tr.special_side(); j<3; ++j, idx = next_idx_modulo(idx, 3))
        verts_idxs.push_back(tr.verts_idxs[idx]);
 
    auto get_alloc_vertex = [this, &neighbors, &verts_idxs](int edge, int i1, int i2) -> int {
        return this->triangle_midpoint_or_allocate(neighbors(edge), verts_idxs[i1], verts_idxs[i2]);
    };
 
    int ichild = 0;
    switch (tr.number_of_split_sides()) {
    case 1:
        verts_idxs.insert(verts_idxs.begin()+2, get_alloc_vertex(next_idx_modulo(tr.special_side(), 3), 2, 1));
        tr.children[ichild ++] = push_triangle(verts_idxs[0], verts_idxs[1], verts_idxs[2], tr.source_triangle, old_state);
        tr.children[ichild   ] = push_triangle(verts_idxs[2], verts_idxs[3], verts_idxs[0], tr.source_triangle, old_state);
        break;
 
    case 2:
        verts_idxs.insert(verts_idxs.begin()+1, get_alloc_vertex(tr.special_side(), 1, 0));
        verts_idxs.insert(verts_idxs.begin()+4, get_alloc_vertex(prev_idx_modulo(tr.special_side(), 3), 0, 3));
        tr.children[ichild ++] = push_triangle(verts_idxs[0], verts_idxs[1], verts_idxs[4], tr.source_triangle, old_state);
        tr.children[ichild ++] = push_triangle(verts_idxs[1], verts_idxs[2], verts_idxs[4], tr.source_triangle, old_state);
        tr.children[ichild   ] = push_triangle(verts_idxs[2], verts_idxs[3], verts_idxs[4], tr.source_triangle, old_state);
        break;
 
    case 3:
        assert(tr.special_side() == 0);
        verts_idxs.insert(verts_idxs.begin()+1, get_alloc_vertex(0, 1, 0));
        verts_idxs.insert(verts_idxs.begin()+3, get_alloc_vertex(1, 3, 2));
        verts_idxs.insert(verts_idxs.begin()+5, get_alloc_vertex(2, 0, 4));
        tr.children[ichild ++] = push_triangle(verts_idxs[0], verts_idxs[1], verts_idxs[5], tr.source_triangle, old_state);
        tr.children[ichild ++] = push_triangle(verts_idxs[1], verts_idxs[2], verts_idxs[3], tr.source_triangle, old_state);
        tr.children[ichild ++] = push_triangle(verts_idxs[3], verts_idxs[4], verts_idxs[5], tr.source_triangle, old_state);
        tr.children[ichild   ] = push_triangle(verts_idxs[1], verts_idxs[3], verts_idxs[5], tr.source_triangle, old_state);
        break;
 
    default:
        break;
    }
 
#ifndef NDEBUG
    assert(this->verify_triangle_neighbors(tr, neighbors));
    for (int i = 0; i <= tr.number_of_split_sides(); ++i) {
        Vec3i32 n = this->child_neighbors(tr, neighbors, i);
        assert(this->verify_triangle_neighbors(m_triangles[tr.children[i]], n));
    }
#endif // NDEBUG
}

References child_neighbors(), Slic3r::TriangleSelector::Triangle::children, Slic3r::TriangleSelector::Triangle::is_split(), m_triangles, Slic3r::next_highest_power_of_2(), Slic3r::next_idx_modulo(), Slic3r::TriangleSelector::Triangle::number_of_split_sides(), Slic3r::prev_idx_modulo(), push_triangle(), Slic3r::TriangleSelector::Triangle::source_triangle, Slic3r::TriangleSelector::Triangle::special_side(), triangle_midpoint_or_allocate(), verify_triangle_neighbors(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by deserialize(), and split_triangle().

Here is the call graph for this function:

Here is the caller graph for this function:

precompute_all_neighbors()

std::pair< std::vector< Vec3i32 >, std::vector< Vec3i32 > > Slic3r::TriangleSelector::precompute_all_neighbors

(

)

const

{
    std::vector<Vec3i32> neighbors(m_triangles.size(), Vec3i32(-1, -1, -1));
    std::vector<Vec3i32> neighbors_propagated(m_triangles.size(), Vec3i32(-1, -1, -1));
    for (int facet_idx = 0; facet_idx < this->m_orig_size_indices; ++facet_idx) {
        neighbors[facet_idx]            = m_neighbors[facet_idx];
        neighbors_propagated[facet_idx] = neighbors[facet_idx];
        assert(this->verify_triangle_neighbors(m_triangles[facet_idx], neighbors[facet_idx]));
        if (m_triangles[facet_idx].is_split())
            this->precompute_all_neighbors_recursive(facet_idx, neighbors[facet_idx], neighbors_propagated[facet_idx], neighbors, neighbors_propagated);
    }
    return std::make_pair(std::move(neighbors), std::move(neighbors_propagated));
}

References m_neighbors, m_orig_size_indices, m_triangles, precompute_all_neighbors_recursive(), and verify_triangle_neighbors().

Referenced by bucket_fill_select_triangles(), and Slic3r::GUI::TriangleSelectorPatch::update_triangles_per_patch().

Here is the call graph for this function:

Here is the caller graph for this function:

precompute_all_neighbors_recursive()

void Slic3r::TriangleSelector::precompute_all_neighbors_recursive	(	int	facet_idx,
		const Vec3i32 &	neighbors,
		const Vec3i32 &	neighbors_propagated,
		std::vector< Vec3i32 > &	neighbors_out,
		std::vector< Vec3i32 > &	neighbors_normal_out ) const

{
    assert(facet_idx < int(m_triangles.size()));
 
    const Triangle *tr = &m_triangles[facet_idx];
    if (!tr->valid())
        return;
 
    neighbors_out[facet_idx]            = neighbors;
    neighbors_propagated_out[facet_idx] = neighbors_propagated;
    if (tr->is_split()) {
        assert(this->verify_triangle_neighbors(*tr, neighbors));
 
        int num_of_children = tr->number_of_split_sides() + 1;
        if (num_of_children != 1) {
            for (int i = 0; i < num_of_children; ++i) {
                assert(i < int(tr->children.size()));
                assert(tr->children[i] < int(m_triangles.size()));
                // Recursion, deep first search over the children of this triangle.
                // All children of this triangle were created by splitting a single source triangle of the original mesh.
                const Vec3i32 child_neighbors = this->child_neighbors(*tr, neighbors, i);
                this->precompute_all_neighbors_recursive(tr->children[i], child_neighbors,
                                                         this->child_neighbors_propagated(*tr, neighbors_propagated, i, child_neighbors), neighbors_out,
                                                         neighbors_propagated_out);
            }
        }
    }
}

References child_neighbors(), Slic3r::TriangleSelector::Triangle::children, Slic3r::TriangleSelector::Triangle::is_split(), m_triangles, Slic3r::TriangleSelector::Triangle::number_of_split_sides(), precompute_all_neighbors_recursive(), Slic3r::TriangleSelector::Triangle::valid(), and verify_triangle_neighbors().

Referenced by precompute_all_neighbors(), and precompute_all_neighbors_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

push_triangle()

int Slic3r::TriangleSelector::push_triangle ( int a, int b, int c, int source_triangle, EnforcerBlockerType state = EnforcerBlockerType{0} )

private

{
    for (int i : {a, b, c}) {
        assert(i >= 0 && i < int(m_vertices.size()));
        ++m_vertices[i].ref_cnt;
    }
    int idx;
    if (m_free_triangles_head == -1) {
        // Allocate a new triangle.
        assert(m_invalid_triangles == 0);
        idx = int(m_triangles.size());
        m_triangles.emplace_back(a, b, c, source_triangle, state);
    } else {
        // Reuse triangle from the free list.
        assert(m_free_triangles_head >= -1 && m_free_triangles_head < int(m_triangles.size()));
        assert(! m_triangles[m_free_triangles_head].valid());
        assert(m_invalid_triangles > 0);
        idx = m_free_triangles_head;
        m_free_triangles_head = m_triangles[idx].children[0];
        -- m_invalid_triangles;
        assert(m_free_triangles_head >= -1 && m_free_triangles_head < int(m_triangles.size()));
        assert(m_free_triangles_head == -1 || ! m_triangles[m_free_triangles_head].valid());
        assert(m_invalid_triangles >= 0);
        assert((m_invalid_triangles == 0) == (m_free_triangles_head == -1));
        m_triangles[idx] = {a, b, c, source_triangle, state};
    }
    assert(m_triangles[idx].valid());
    return idx;
}

References m_free_triangles_head, m_invalid_triangles, m_triangles, and m_vertices.

Referenced by perform_split(), and reset().

Here is the caller graph for this function:

remap_painting()

TriangleSelector::TriangleSplittingData Slic3r::TriangleSelector::remap_painting ( const indexed_triangle_set & source_its, const TriangleSplittingData & source_painting, const indexed_triangle_set & target_its, const Transform3d & target_transform, const std::optional< std::reference_wrapper< const TriangleSplittingData > > & existing_painting )

static

{
    TriangleSelector::TriangleSplittingData result;
    if (source_painting.bitstream.empty())
        return result;
 
    // 1. Deserialize source painting
    TriangleMesh source_mesh(source_its);
    TriangleSelector source_selector(source_mesh);
    source_selector.deserialize(source_painting, false);
 
    // 2. Extract painted geometry
    std::vector<std::reference_wrapper<const Triangle>> painted_triangles;
    painted_triangles.reserve(source_selector.m_triangles.size());
    for (const Triangle& tr : source_selector.m_triangles) {
        if (tr.valid() && !tr.is_split() && tr.get_state() != EnforcerBlockerType::NONE) {
            painted_triangles.push_back(std::ref(tr));
        }
    }
 
    if (painted_triangles.empty())
        return result;
 
    // 3. Build AABB tree of target mesh so we could find nearest face quickly
    TriangleMesh target_mesh(target_its);
    target_mesh.transform(target_transform);
    AABBTreeIndirect::Tree3f target_tree = AABBTreeIndirect::build_aabb_tree_over_indexed_triangle_set(target_mesh.its.vertices, target_mesh.its.indices);
    
    // Helper: check overlap between a paint triangle and a target triangle.
    // Uses 3D barycentric point-in-triangle tests and dominant-axis 2D projection
    // for edge-edge intersection to handle all triangle orientations correctly.
    auto check_overlap = [&](const Vec3f& pa, const Vec3f& pb, const Vec3f& pc,
                             const Vec3f& ta, const Vec3f& tb, const Vec3f& tc) -> bool {
        // Check if any target vertex is inside the paint triangle
        if (is_point_inside_triangle(ta, pa, pb, pc)) return true;
        if (is_point_inside_triangle(tb, pa, pb, pc)) return true;
        if (is_point_inside_triangle(tc, pa, pb, pc)) return true;
 
        // Check if any paint vertex is inside the target triangle
        if (is_point_inside_triangle(pa, ta, tb, tc)) return true;
        if (is_point_inside_triangle(pb, ta, tb, tc)) return true;
        if (is_point_inside_triangle(pc, ta, tb, tc)) return true;
 
        // Check edge-edge intersections using dominant-axis 2D projection.
        // Project onto the plane (XY, XZ, or YZ) where the triangles have the
        // most area, avoiding degenerate projections for vertical/angled surfaces.
        Vec3f n1 = (pb - pa).cross(pc - pa);
        Vec3f n2 = (tb - ta).cross(tc - ta);
        Vec3f n_abs = (n1.cwiseAbs() + n2.cwiseAbs());
        int axis = (n_abs.x() >= n_abs.y() && n_abs.x() >= n_abs.z()) ? 0
                 : (n_abs.y() >= n_abs.z()) ? 1 : 2;
        const int u_axis = (axis + 1) % 3;
        const int v_axis = (axis + 2) % 3;
        const std::pair<int, int> proj{u_axis, v_axis};
 
        if (segments_intersect_proj(pa, pb, ta, tb, proj)) return true;
        if (segments_intersect_proj(pa, pb, tb, tc, proj)) return true;
        if (segments_intersect_proj(pa, pb, tc, ta, proj)) return true;
        if (segments_intersect_proj(pb, pc, ta, tb, proj)) return true;
        if (segments_intersect_proj(pb, pc, tb, tc, proj)) return true;
        if (segments_intersect_proj(pb, pc, tc, ta, proj)) return true;
        if (segments_intersect_proj(pc, pa, ta, tb, proj)) return true;
        if (segments_intersect_proj(pc, pa, tb, tc, proj)) return true;
        if (segments_intersect_proj(pc, pa, tc, ta, proj)) return true;
 
        return false;
    };
 
    // 4. For each painted face, we find the nearest target face, and apply the TriangleCursor to paint it
    TriangleSelector target_selector(target_mesh);
    if (existing_painting) {
        // Restore existing painting first, if given
        target_selector.deserialize(existing_painting->get(), false);
    }
    for (auto tri_ref : painted_triangles) {
        const Triangle& tri = tri_ref.get();
        const Vec3f& pv0    = source_selector.m_vertices[tri.verts_idxs[0]].v;
        const Vec3f& pv1    = source_selector.m_vertices[tri.verts_idxs[1]].v;
        const Vec3f& pv2    = source_selector.m_vertices[tri.verts_idxs[2]].v;
 
        // Find ALL target faces whose bounding boxes overlap with the paint
        // triangle's bounding box, not just the nearest one.
        Eigen::AlignedBox3f pt_bbox;
        pt_bbox.extend(pv0);
        pt_bbox.extend(pv1);
        pt_bbox.extend(pv2);
        pt_bbox.min() -= Eigen::Vector3f::Constant(TriangleCursor::tolerance);
        pt_bbox.max() += Eigen::Vector3f::Constant(TriangleCursor::tolerance);
 
        AABBTreeIndirect::traverse(target_tree, AABBTreeIndirect::intersecting(pt_bbox), [&](const AABBTreeIndirect::Tree3f::Node& node) -> bool {
            size_t face_idx = node.idx;
            if (face_idx >= target_mesh.its.indices.size())
                return true;
 
            const Vec3f& norm_a = source_selector.m_face_normals[tri.source_triangle];
            const Vec3f& norm_b = target_selector.m_face_normals[face_idx];
 
            const Vec3i32& face = target_mesh.its.indices[face_idx];
            const Vec3f& ta     = target_mesh.its.vertices[face(0)];
            const Vec3f& tb     = target_mesh.its.vertices[face(1)];
            const Vec3f& tc     = target_mesh.its.vertices[face(2)];
 
            if (TriangleCursor::check_normal(norm_b, -norm_a) && check_overlap(pv0, pv1, pv2, ta, tb, tc)) {
                // Paint this face
                target_selector.select_patch(face_idx, TriangleCursor::build_cursor(source_selector, tri), tri.get_state(),
                                             Transform3d::Identity(), true, 0.f, Vec3f::UnitZ(), true);
            }
            return true; // continue traversal
        });
    }
 
    return target_selector.serialize();
}

References TriangleSelector(), Slic3r::TriangleSelector::TriangleSplittingData::bitstream, Slic3r::AABBTreeIndirect::build_aabb_tree_over_indexed_triangle_set(), Slic3r::TriangleCursor::build_cursor(), Slic3r::TriangleCursor::check_normal(), Slic3r::cross(), deserialize(), Slic3r::TriangleSelector::Triangle::get_state(), Slic3r::AABBTreeIndirect::intersecting(), Slic3r::is_point_inside_triangle(), Slic3r::TriangleSelector::Triangle::is_split(), Slic3r::TriangleMesh::its, m_face_normals, m_triangles, m_vertices, Slic3r::NONE, Slic3r::segments_intersect_proj(), select_patch(), serialize(), Slic3r::TriangleSelector::Triangle::source_triangle, Slic3r::TriangleCursor::tolerance, Slic3r::TriangleMesh::transform(), Slic3r::AABBTreeIndirect::traverse(), Slic3r::TriangleSelector::Triangle::valid(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by Slic3r::ModelVolume::restore_painting().

Here is the call graph for this function:

Here is the caller graph for this function:

remap_triangle_state()

void Slic3r::TriangleSelector::remap_triangle_state

(

const EnforcerBlockerStateMap &

state_map

)

{
    if (m_triangles.empty())
        return;
 
    tbb::parallel_for(tbb::blocked_range<size_t>(0, m_triangles.size()), [this, &state_map](const tbb::blocked_range<size_t>& range) {
        for (size_t i = range.begin(); i != range.end(); ++i) {
            Triangle& tr = m_triangles[i];
            if (tr.valid()) {
                const auto current_state = static_cast<size_t>(tr.get_state());
                tr.set_state(state_map[current_state]);
            }
        }
    });
}

References m_triangles, and Slic3r::range().

Referenced by Slic3r::GUI::GLGizmoMmuSegmentation::remap_filament_assignments(), and Slic3r::FacetsAnnotation::remap_states().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_useless_children()

void Slic3r::TriangleSelector::remove_useless_children ( int facet_idx )

private

{
    // Check that all children are leafs of the same type. If not, try to
    // make them (recursive call). Remove them if sucessful.
 
    assert(facet_idx < int(m_triangles.size()) && m_triangles[facet_idx].valid());
    Triangle& tr = m_triangles[facet_idx];
 
    if (! tr.is_split()) {
        // This is a leaf, there nothing to do. This can happen during the
        // first (non-recursive call). Shouldn't otherwise.
        return;
    }
 
    // Call this for all non-leaf children.
    for (int child_idx=0; child_idx<=tr.number_of_split_sides(); ++child_idx) {
        assert(child_idx < int(m_triangles.size()) && m_triangles[child_idx].valid());
        if (m_triangles[tr.children[child_idx]].is_split())
            remove_useless_children(tr.children[child_idx]);
    }
 
 
    // Return if a child is not leaf or two children differ in type.
    EnforcerBlockerType first_child_type = EnforcerBlockerType::NONE;
    for (int child_idx=0; child_idx<=tr.number_of_split_sides(); ++child_idx) {
        if (m_triangles[tr.children[child_idx]].is_split())
            return;
        if (child_idx == 0)
            first_child_type = m_triangles[tr.children[0]].get_state();
        else if (m_triangles[tr.children[child_idx]].get_state() != first_child_type)
            return;
    }
 
    // If we got here, the children can be removed.
    undivide_triangle(facet_idx);
    tr.set_state(first_child_type);
}

References Slic3r::TriangleSelector::Triangle::children, Slic3r::TriangleSelector::Triangle::is_split(), m_triangles, Slic3r::NONE, Slic3r::TriangleSelector::Triangle::number_of_split_sides(), remove_useless_children(), Slic3r::TriangleSelector::Triangle::set_state(), and undivide_triangle().

Referenced by remove_useless_children(), seed_fill_apply_on_triangles(), and select_triangle().

Here is the call graph for this function:

Here is the caller graph for this function:

reset()

void Slic3r::TriangleSelector::reset

(

)

{
    m_vertices.clear();
    m_triangles.clear();
    m_invalid_triangles = 0;
    m_free_triangles_head = -1;
    m_free_vertices_head = -1;
    m_vertices.reserve(m_mesh.its.vertices.size());
    for (const stl_vertex& vert : m_mesh.its.vertices)
        m_vertices.emplace_back(vert);
    m_triangles.reserve(m_mesh.its.indices.size());
    for (size_t i = 0; i < m_mesh.its.indices.size(); ++i) {
        const stl_triangle_vertex_indices &ind = m_mesh.its.indices[i];
        push_triangle(ind[0], ind[1], ind[2], int(i));
    }
    m_orig_size_vertices = int(m_vertices.size());
    m_orig_size_indices  = int(m_triangles.size());
}

References m_free_triangles_head, m_free_vertices_head, m_invalid_triangles, m_mesh, m_orig_size_indices, m_orig_size_vertices, m_triangles, m_vertices, and push_triangle().

Referenced by TriangleSelector(), deserialize(), and Slic3r::GUI::GLGizmoTextureDisplacement::select_visible_faces().

Here is the call graph for this function:

Here is the caller graph for this function:

seed_fill_apply_on_triangles()

void Slic3r::TriangleSelector::seed_fill_apply_on_triangles

(

EnforcerBlockerType

new_state

)

{
    for (Triangle &triangle : m_triangles)
        if (!triangle.is_split() && triangle.is_selected_by_seed_fill())
            triangle.set_state(new_state);
 
    for (Triangle &triangle : m_triangles)
        if (triangle.is_split() && triangle.valid()) {
            size_t facet_idx = &triangle - &m_triangles.front();
            remove_useless_children(int(facet_idx));
        }
}

References m_triangles, and remove_useless_children().

Here is the call graph for this function:

seed_fill_select_triangles()

void Slic3r::TriangleSelector::seed_fill_select_triangles	(	const Vec3f &	hit,
		int	facet_start,
		const Transform3d &	trafo_no_translate,
		const ClippingPlane &	clp,
		float	seed_fill_angle,
		float	highlight_by_angle_deg = 0.f,
		const Vec3f &	up_direction = Vec3f::UnitZ(),
		bool	force_reselection = false )

{
    assert(facet_start < m_orig_size_indices);
 
    // Recompute seed fill only if the cursor is pointing on facet unselected by seed fill or a clipping plane is active.
    if (int start_facet_idx = select_unsplit_triangle(hit, facet_start); start_facet_idx >= 0 && m_triangles[start_facet_idx].is_selected_by_seed_fill() && !force_reselection && !clp.is_active())
        return;
 
    this->seed_fill_unselect_all_triangles();
 
    std::vector<bool> visited(m_triangles.size(), false);
    std::queue<int>   facet_queue;
    facet_queue.push(facet_start);
 
    const double facet_angle_limit     = cos(Geometry::deg2rad(seed_fill_angle)) - EPSILON;
    const float  highlight_angle_limit = -cos(Geometry::deg2rad(highlight_by_angle_deg));
 
    // Depth-first traversal of neighbors of the face hit by the ray thrown from the mouse cursor.
    while (!facet_queue.empty()) {
        int current_facet = facet_queue.front();
        facet_queue.pop();
 
        const Vec3f &facet_normal = m_face_normals[m_triangles[current_facet].source_triangle];
        Matrix3f     normal_matrix  = static_cast<Matrix3f>(trafo_no_translate.matrix().block(0, 0, 3, 3).inverse().transpose().cast<float>());
        float        world_normal_dot = (normal_matrix * facet_normal).normalized().dot(up_direction);
        if (!visited[current_facet] && (highlight_by_angle_deg == 0.f || world_normal_dot < highlight_angle_limit)) {
            if (m_triangles[current_facet].is_split()) {
                for (int split_triangle_idx = 0; split_triangle_idx <= m_triangles[current_facet].number_of_split_sides(); ++split_triangle_idx) {
                    assert(split_triangle_idx < int(m_triangles[current_facet].children.size()));
                    assert(m_triangles[current_facet].children[split_triangle_idx] < int(m_triangles.size()));
                    if (int child = m_triangles[current_facet].children[split_triangle_idx]; !visited[child])
                        // Child triangle shares normal with its parent. Select it.
                        facet_queue.push(child);
                }
            } else
                m_triangles[current_facet].select_by_seed_fill();
 
            if (current_facet < m_orig_size_indices)
                // Propagate over the original triangles.
                for (int neighbor_idx : m_neighbors[current_facet]) {
                    assert(neighbor_idx >= -1);
                    if (neighbor_idx >= 0 && !visited[neighbor_idx] && !is_facet_clipped(neighbor_idx, clp)) {
                        // Check if neighbour_facet_idx is satisfies angle in seed_fill_angle and append it to facet_queue if it do.
                        const Vec3f &n1 = m_face_normals[m_triangles[neighbor_idx].source_triangle];
                        const Vec3f &n2 = m_face_normals[m_triangles[current_facet].source_triangle];
                        if (std::clamp(n1.dot(n2), 0.f, 1.f) >= facet_angle_limit)
                            facet_queue.push(neighbor_idx);
                    }
                }
        }
        visited[current_facet] = true;
    }
}

References Slic3r::cast(), Slic3r::Geometry::deg2rad(), EPSILON, Slic3r::TriangleSelector::ClippingPlane::is_active(), is_facet_clipped(), m_face_normals, m_neighbors, m_orig_size_indices, m_triangles, seed_fill_unselect_all_triangles(), and select_unsplit_triangle().

Here is the call graph for this function:

seed_fill_unselect_all_triangles()

void Slic3r::TriangleSelector::seed_fill_unselect_all_triangles

(

)

{
    for (Triangle &triangle : m_triangles)
        if (!triangle.is_split())
            triangle.unselect_by_seed_fill();
}

References m_triangles.

Referenced by bucket_fill_select_triangles(), and seed_fill_select_triangles().

Here is the caller graph for this function:

select_patch()

void Slic3r::TriangleSelector::select_patch	(	int	facet_start,
		std::unique_ptr< Cursor > &&	cursor,
		EnforcerBlockerType	new_state,
		const Transform3d &	trafo_no_translate,
		bool	triangle_splitting,
		float	highlight_by_angle_deg = 0.f,
		const Vec3f &	up_direction = Vec3f::UnitZ(),
		bool	select_partially = false )

{
    assert(facet_start < m_orig_size_indices);
 
    // Save current cursor center, squared radius and camera direction, so we don't
    // have to pass it around.
    m_cursor = std::move(cursor);
 
    // In case user changed cursor size since last time, update triangle edge limit.
    // It is necessary to compare the internal radius in m_cursor! radius is in
    // world coords and does not change after scaling.
    if (m_old_cursor_radius_sqr != m_cursor->radius_sqr) {
        // BBS: improve details for large cursor radius
        TriangleSelector::HeightRange* hr_cursor = dynamic_cast<TriangleSelector::HeightRange*>(m_cursor.get());
        if (hr_cursor == nullptr) {
            set_edge_limit(std::min(std::sqrt(m_cursor->radius_sqr) / 5.f, 0.05f));
            m_old_cursor_radius_sqr = m_cursor->radius_sqr;
        }
        else {
            set_edge_limit(0.1);
            m_old_cursor_radius_sqr = 0.1;
        }
    }
 
    const float highlight_angle_limit = -cos(Geometry::deg2rad(highlight_by_angle_deg));
 
    // BBS
    std::vector<int> start_facets;
    HeightRange* hr_cursor = dynamic_cast<HeightRange*>(m_cursor.get());
    if (hr_cursor) {
        for (int facet_id = 0; facet_id < m_orig_size_indices; facet_id++) {
            const Triangle& tr = m_triangles[facet_id];
            if (m_cursor->is_edge_inside_cursor(tr, m_vertices)) {
                start_facets.push_back(facet_id);
            }
        }
    }
    else {
        start_facets.push_back(facet_start);
    }
 
    // Keep track of facets of the original mesh we already processed.
    std::vector<bool> visited(m_orig_size_indices, false);
 
    for (int i = 0; i < start_facets.size(); i++) {
        int start_facet_id = start_facets[i];
        if (visited[start_facet_id])
            continue;
 
        // Now start with the facet the pointer points to and check all adjacent facets.
        std::vector<int> facets_to_check;
        facets_to_check.reserve(16);
        facets_to_check.emplace_back(start_facet_id);
 
        // Breadth-first search around the hit point. facets_to_check may grow significantly large.
        // Head of the bread-first facets_to_check FIFO.
        int facet_idx = 0;
        while (facet_idx < int(facets_to_check.size())) {
            int          facet = facets_to_check[facet_idx];
            const Vec3f& facet_normal = m_face_normals[m_triangles[facet].source_triangle];
            Matrix3f     normal_matrix = static_cast<Matrix3f>(trafo_no_translate.matrix().block(0, 0, 3, 3).inverse().transpose().cast<float>());
            float        world_normal_dot = (normal_matrix * facet_normal).normalized().dot(up_direction);
            if (!visited[facet] && (highlight_by_angle_deg == 0.f || world_normal_dot < highlight_angle_limit)) {
                if (select_triangle(facet, new_state, triangle_splitting, select_partially)) {
                    // add neighboring facets to list to be processed later
                    for (int neighbor_idx : m_neighbors[facet])
                        if (neighbor_idx >= 0 && m_cursor->is_facet_visible(neighbor_idx, m_face_normals))
                            facets_to_check.push_back(neighbor_idx);
                }
            }
            visited[facet] = true;
            ++facet_idx;
        }
    }
}

References Slic3r::cast(), Slic3r::Geometry::deg2rad(), m_cursor, m_face_normals, m_neighbors, m_old_cursor_radius_sqr, m_orig_size_indices, m_triangles, m_vertices, select_triangle(), and set_edge_limit().

Referenced by remap_painting().

Here is the call graph for this function:

Here is the caller graph for this function:

select_triangle()

bool Slic3r::TriangleSelector::select_triangle ( int facet_idx, EnforcerBlockerType type, bool triangle_splitting, bool select_partially )

private

{
    assert(facet_idx < int(m_triangles.size()));
 
    if (! m_triangles[facet_idx].valid())
        return false;
 
    Vec3i32 neighbors = m_neighbors[facet_idx];
    assert(this->verify_triangle_neighbors(m_triangles[facet_idx], neighbors));
 
    if (! select_triangle_recursive(facet_idx, neighbors, type, triangle_splitting, select_partially))
        return false;
 
    // In case that all children are leafs and have the same state now,
    // they may be removed and substituted by the parent triangle.
    remove_useless_children(facet_idx);
 
#ifdef EXPENSIVE_DEBUG_CHECKS
    // Make sure that we did not lose track of invalid triangles.
    assert(m_invalid_triangles == std::count_if(m_triangles.begin(), m_triangles.end(),
               [](const Triangle& tr) { return ! tr.valid(); }));
#endif // EXPENSIVE_DEBUG_CHECKS
 
    // Do garbage collection maybe?
    if (2*m_invalid_triangles > int(m_triangles.size()))
        garbage_collect();
 
    return true;
}

References garbage_collect(), m_invalid_triangles, m_neighbors, m_triangles, remove_useless_children(), select_triangle_recursive(), and verify_triangle_neighbors().

Referenced by select_patch().

Here is the call graph for this function:

Here is the caller graph for this function:

select_triangle_recursive()

bool Slic3r::TriangleSelector::select_triangle_recursive ( int facet_idx, const Vec3i32 & neighbors, EnforcerBlockerType type, bool triangle_splitting, bool select_partially )

private

{
    assert(facet_idx < int(m_triangles.size()));
 
    Triangle* tr = &m_triangles[facet_idx];
    if (! tr->valid())
        return false;
 
    assert(this->verify_triangle_neighbors(*tr, neighbors));
 
    int num_of_inside_vertices = m_cursor->vertices_inside(*tr, m_vertices);
 
    if (num_of_inside_vertices == 0
     && ! m_cursor->is_pointer_in_triangle(*tr, m_vertices)
     && ! m_cursor->is_edge_inside_cursor(*tr, m_vertices))
        return false;
 
    if (num_of_inside_vertices == 3) {
        // dump any subdivision and select whole triangle
        undivide_triangle(facet_idx);
        tr->set_state(type);
    } else {
        // the triangle is partially inside, let's recursively divide it
        // (if not already) and try selecting its children.
 
        if (! tr->is_split() && tr->get_state() == type) {
            // This is leaf triangle that is already of correct type as a whole.
            // No need to split, all children would end up selected anyway.
            return true;
        }
 
        if (triangle_splitting)
            split_triangle(facet_idx, neighbors);
        if ((!triangle_splitting || select_partially) && !m_triangles[facet_idx].is_split()) {
            m_triangles[facet_idx].set_state(type);
            return true;
        }
        tr = &m_triangles[facet_idx]; // might have been invalidated by split_triangle().
 
        int num_of_children = tr->number_of_split_sides() + 1;
        if (num_of_children != 1) {
            for (int i=0; i<num_of_children; ++i) {
                assert(i < int(tr->children.size()));
                assert(tr->children[i] < int(m_triangles.size()));
                // Recursion, deep first search over the children of this triangle.
                // All children of this triangle were created by splitting a single source triangle of the original mesh.
                select_triangle_recursive(tr->children[i], this->child_neighbors(*tr, neighbors, i), type, triangle_splitting, select_partially);
                tr = &m_triangles[facet_idx]; // might have been invalidated
            }
        }
    }
 
    return true;
}

References Slic3r::TriangleSelector::Triangle::children, Slic3r::TriangleSelector::Triangle::get_state(), Slic3r::TriangleSelector::Triangle::is_split(), m_cursor, m_triangles, m_vertices, Slic3r::TriangleSelector::Triangle::number_of_split_sides(), select_triangle_recursive(), Slic3r::TriangleSelector::Triangle::set_state(), split_triangle(), undivide_triangle(), Slic3r::TriangleSelector::Triangle::valid(), and verify_triangle_neighbors().

Referenced by select_triangle(), and select_triangle_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

select_unsplit_triangle() [1/2]

int Slic3r::TriangleSelector::select_unsplit_triangle ( const Vec3f & hit, int facet_idx ) const

nodiscard

{
    assert(facet_idx < int(m_triangles.size()));
    if (!m_triangles[facet_idx].valid())
        return -1;
 
    Vec3i32 neighbors = m_neighbors[facet_idx];
    assert(this->verify_triangle_neighbors(m_triangles[facet_idx], neighbors));
    return this->select_unsplit_triangle(hit, facet_idx, neighbors);
}

References m_neighbors, m_triangles, select_unsplit_triangle(), and verify_triangle_neighbors().

Referenced by bucket_fill_select_triangles(), seed_fill_select_triangles(), select_unsplit_triangle(), and select_unsplit_triangle().

Here is the call graph for this function:

Here is the caller graph for this function:

select_unsplit_triangle() [2/2]

int Slic3r::TriangleSelector::select_unsplit_triangle ( const Vec3f & hit, int facet_idx, const Vec3i32 & neighbors ) const

nodiscard

{
    assert(facet_idx < int(m_triangles.size()));
    const Triangle *tr = &m_triangles[facet_idx];
    if (!tr->valid())
        return -1;
 
    if (!tr->is_split()) {
        if (const std::array<int, 3> &t_vert = m_triangles[facet_idx].verts_idxs; is_point_inside_triangle(hit, m_vertices[t_vert[0]].v, m_vertices[t_vert[1]].v, m_vertices[t_vert[2]].v))
            return facet_idx;
 
        return -1;
    }
 
    assert(this->verify_triangle_neighbors(*tr, neighbors));
 
    int num_of_children = tr->number_of_split_sides() + 1;
    if (num_of_children != 1) {
        for (int i = 0; i < num_of_children; ++i) {
            assert(i < int(tr->children.size()));
            assert(tr->children[i] < int(m_triangles.size()));
            // Recursion, deep first search over the children of this triangle.
            // All children of this triangle were created by splitting a single source triangle of the original mesh.
 
            const std::array<int, 3> &t_vert = m_triangles[tr->children[i]].verts_idxs;
            if (is_point_inside_triangle(hit, m_vertices[t_vert[0]].v, m_vertices[t_vert[1]].v, m_vertices[t_vert[2]].v))
                return this->select_unsplit_triangle(hit, tr->children[i], this->child_neighbors(*tr, neighbors, i));
        }
    }
 
    return -1;
}

References Slic3r::TriangleSelector::Triangle::children, Slic3r::is_point_inside_triangle(), Slic3r::TriangleSelector::Triangle::is_split(), m_triangles, m_vertices, Slic3r::TriangleSelector::Triangle::number_of_split_sides(), select_unsplit_triangle(), Slic3r::TriangleSelector::Triangle::valid(), and verify_triangle_neighbors().

Here is the call graph for this function:

serialize()

TriangleSelector::TriangleSplittingData Slic3r::TriangleSelector::serialize

(

)

const

                                                                        {
    // Each original triangle of the mesh is assigned a number encoding its state
    // or how it is split. Each triangle is encoded by 4 bits (xxyy) or 8 bits (zzzzxxyy):
    // leaf triangle: xx = EnforcerBlockerType (Only values 0, 1, and 2. Value 3 is used as an indicator for additional 4 bits.), yy = 0
    // leaf triangle: xx = 0b11, yy = 0b00, zzzz = EnforcerBlockerType (subtracted by 3)
    // non-leaf:      xx = special side, yy = number of split sides
    // These are bitwise appended and formed into one 64-bit integer.
 
    // The function returns a map from original triangle indices to
    // stream of bits encoding state and offsprings.
 
    // Using an explicit function object to support recursive call of Serializer::serialize().
    // This is cheaper than the previous implementation using a recursive call of type erased std::function.
    // (std::function calls using a pointer, while this implementation calls directly).
    struct Serializer {
        const TriangleSelector* triangle_selector;
        TriangleSplittingData data;
 
        void serialize(int facet_idx) {
            const Triangle& tr = triangle_selector->m_triangles[facet_idx];
 
            // Always save number of split sides. It is zero for unsplit triangles.
            int split_sides = tr.number_of_split_sides();
            assert(split_sides >= 0 && split_sides <= 3);
 
            data.bitstream.push_back(split_sides & 0b01);
            data.bitstream.push_back(split_sides & 0b10);
 
            if (split_sides) {
                // If this triangle is split, save which side is split (in case
                // of one split) or kept (in case of two splits). The value will
                // be ignored for 3-side split.
                assert(tr.is_split() && split_sides > 0);
                assert(tr.special_side() >= 0 && tr.special_side() <= 3);
                data.bitstream.push_back(tr.special_side() & 0b01);
                data.bitstream.push_back(tr.special_side() & 0b10);
                // Now save all children.
                // Serialized in reverse order for compatibility with PrusaSlicer 2.3.1.
                for (int child_idx = split_sides; child_idx >= 0; -- child_idx)
                    this->serialize(tr.children[child_idx]);
            } else {
                // In case this is leaf, we better save information about its state.
                int n = int(tr.get_state());
                if (n <= static_cast<size_t>(EnforcerBlockerType::ExtruderMax))
                    data.used_states[n] = true;
 
                if (n >= 3) {
                    assert(n <= int(EnforcerBlockerType::ExtruderMax));
                    // Store "11" plus 4 bits of (n-3), which covers states 3..17. State 18 and
                    // above set that nibble to 0b1111 and store (n-18) in a second nibble. This is
                    // the encoding the CONST_FILAMENTS table in Model.cpp already writes for
                    // colored mesh imports.
                    data.bitstream.insert(data.bitstream.end(), { true, true });
                    auto &bitstream = data.bitstream;
                    auto push_nibble = [&bitstream](int value) {
                        for (size_t bit_idx = 0; bit_idx < 4; ++bit_idx)
                            bitstream.push_back(value & (uint64_t(0b0001) << bit_idx));
                    };
                    if (n <= 17) {
                        push_nibble(n - 3);
                    } else {
                        push_nibble(0b1111);
                        push_nibble(n - 18);
                    }
                } else {
                    // Simple case, compatible with PrusaSlicer 2.3.1 and older for storing paint on supports and seams.
                    // Store 2 bits of n.
                    data.bitstream.push_back(n & 0b01);
                    data.bitstream.push_back(n & 0b10);
                }
            }
        }
    } out { this };
 
    out.data.triangles_to_split.reserve(m_orig_size_indices);
    for (int i=0; i<m_orig_size_indices; ++i)
        if (const Triangle& tr = m_triangles[i]; tr.is_split() || tr.get_state() != EnforcerBlockerType::NONE) {
            // Store index of the first bit assigned to ith triangle.
            out.data.triangles_to_split.emplace_back(i, int(out.data.bitstream.size()));
            // out the triangle bits.
            out.serialize(i);
        }
 
    // May be stored onto Undo / Redo stack, thus conserve memory.
    out.data.triangles_to_split.shrink_to_fit();
    out.data.bitstream.shrink_to_fit();
    return out.data;
}

References TriangleSelector(), Slic3r::TriangleSelector::TriangleSplittingData::bitstream, Slic3r::TriangleSelector::Triangle::children, Slic3r::ExtruderMax, Slic3r::TriangleSelector::Triangle::get_state(), Slic3r::TriangleSelector::Triangle::is_split(), m_orig_size_indices, m_triangles, Slic3r::NONE, Slic3r::TriangleSelector::Triangle::number_of_split_sides(), serialize(), Slic3r::TriangleSelector::Triangle::special_side(), and Slic3r::TriangleSelector::TriangleSplittingData::used_states.

Referenced by Slic3r::GUI::GLGizmoTextureDisplacement::masks_after_subdivision(), remap_painting(), and Slic3r::FacetsAnnotation::set().

Here is the call graph for this function:

Here is the caller graph for this function:

set_edge_limit()

void Slic3r::TriangleSelector::set_edge_limit

(

float

edge_limit

)

{
    m_edge_limit_sqr = std::pow(edge_limit, 2.f);
}

References m_edge_limit_sqr.

Referenced by select_patch().

Here is the caller graph for this function:

set_facet()

void Slic3r::TriangleSelector::set_facet	(	int	facet_idx,
		EnforcerBlockerType	state )

{
    assert(facet_idx < m_orig_size_indices);
    undivide_triangle(facet_idx);
    assert(! m_triangles[facet_idx].is_split());
    m_triangles[facet_idx].set_state(state);
}

References m_orig_size_indices, m_triangles, and undivide_triangle().

Referenced by Slic3r::apply_painted_mesh_to_volume(), Slic3r::GUI::GLGizmoTextureDisplacement::masks_after_subdivision(), and Slic3r::GUI::GLGizmoTextureDisplacement::select_visible_faces().

Here is the call graph for this function:

Here is the caller graph for this function:

shift_states_above()

void Slic3r::TriangleSelector::shift_states_above	(	EnforcerBlockerType	threshold,
		int	delta )

{
    for (Triangle &triangle : m_triangles) {
        if (triangle.is_split() || !triangle.valid())
            continue;
        EnforcerBlockerType s = triangle.get_state();
        if (s >= threshold && s != EnforcerBlockerType::NONE) {
            int new_val = (int)s + delta;
            if (new_val >= 0)
                triangle.set_state(EnforcerBlockerType(new_val));
        }
    }
}

References m_triangles, and Slic3r::NONE.

Referenced by Slic3r::FacetsAnnotation::shift_states_above().

Here is the caller graph for this function:

split_triangle()

void Slic3r::TriangleSelector::split_triangle ( int facet_idx, const Vec3i32 & neighbors )

private

{
    if (m_triangles[facet_idx].is_split()) {
        // The triangle is divided already.
        return;
    }
 
    Triangle* tr = &m_triangles[facet_idx];
    assert(this->verify_triangle_neighbors(*tr, neighbors));
 
    EnforcerBlockerType old_type = tr->get_state();
 
    // If we got here, we are about to actually split the triangle.
    const double limit_squared = m_edge_limit_sqr;
 
    std::array<int, 3>& facet = tr->verts_idxs;
    std::array<const stl_vertex*, 3> pts = { &m_vertices[facet[0]].v,
                                             &m_vertices[facet[1]].v,
                                             &m_vertices[facet[2]].v};
    std::array<stl_vertex, 3> pts_transformed; // must stay in scope of pts !!!
 
    // In case the object is non-uniformly scaled, transform the
    // points to world coords.
    if (! m_cursor->uniform_scaling) {
        for (size_t i=0; i<pts.size(); ++i) {
            pts_transformed[i] = m_cursor->trafo * (*pts[i]);
            pts[i] = &pts_transformed[i];
        }
    }
 
    std::array<double, 3> sides = {(*pts[2] - *pts[1]).squaredNorm(),
                                   (*pts[0] - *pts[2]).squaredNorm(),
                                   (*pts[1] - *pts[0]).squaredNorm()};
 
    boost::container::small_vector<int, 3> sides_to_split;
    int side_to_keep = -1;
    for (int pt_idx = 0; pt_idx<3; ++pt_idx) {
        if (sides[pt_idx] > limit_squared)
            sides_to_split.push_back(pt_idx);
        else
            side_to_keep = pt_idx;
    }
    if (sides_to_split.empty()) {
        // This shall be unselected.
        tr->set_division(0, 0);
        return;
    }
 
    // Save how the triangle will be split. Second argument makes sense only for one
    // or two split sides, otherwise the value is ignored.
    tr->set_division(int(sides_to_split.size()),
        sides_to_split.size() == 2 ? side_to_keep : sides_to_split[0]);
 
    perform_split(facet_idx, neighbors, old_type);
}

References Slic3r::TriangleSelector::Triangle::get_state(), m_cursor, m_edge_limit_sqr, m_triangles, m_vertices, perform_split(), Slic3r::TriangleSelector::Triangle::set_division(), verify_triangle_neighbors(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by select_triangle_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

triangle_midpoint() [1/2]

int Slic3r::TriangleSelector::triangle_midpoint ( const Triangle & tr, int vertexi, int vertexj ) const

private

{
    if (tr.number_of_split_sides() == 0)
        // If this triangle is not split, then there is no upper / lower subtriangle sharing the edge.
        return -1;
 
    // Find the triangle edge.
    int edge = tr.verts_idxs[0] == vertexi ? 0 : tr.verts_idxs[1] == vertexi ? 1 : 2;
    assert(tr.verts_idxs[edge] == vertexi);
    assert(tr.verts_idxs[next_idx_modulo(edge, 3)] == vertexj);
 
    if (tr.number_of_split_sides() == 1) {
        return edge == next_idx_modulo(tr.special_side(), 3) ?
            m_triangles[tr.children[0]].verts_idxs[2] :
            this->triangle_midpoint(m_triangles[tr.children[edge == tr.special_side() ? 0 : 1]], vertexi, vertexj);
    } else if (tr.number_of_split_sides() == 2) {
        return edge == next_idx_modulo(tr.special_side(), 3) ?
                    this->triangle_midpoint(m_triangles[tr.children[2]], vertexi, vertexj) :
               edge == tr.special_side() ?
                    m_triangles[tr.children[0]].verts_idxs[1] :
                    m_triangles[tr.children[1]].verts_idxs[2];
    } else {
        assert(tr.number_of_split_sides() == 3);
        assert(tr.special_side() == 0);
        return
            (edge == 0) ? m_triangles[tr.children[0]].verts_idxs[1] :
            (edge == 1) ? m_triangles[tr.children[1]].verts_idxs[2] :
                          m_triangles[tr.children[2]].verts_idxs[2];
    }
}

References Slic3r::TriangleSelector::Triangle::children, m_triangles, Slic3r::next_idx_modulo(), Slic3r::TriangleSelector::Triangle::number_of_split_sides(), Slic3r::TriangleSelector::Triangle::special_side(), triangle_midpoint(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by append_touching_edges(), append_touching_subtriangles(), get_facets_split_by_tjoints(), triangle_midpoint(), triangle_midpoint(), triangle_midpoint_or_allocate(), and verify_triangle_midpoints().

Here is the call graph for this function:

Here is the caller graph for this function:

triangle_midpoint() [2/2]

int Slic3r::TriangleSelector::triangle_midpoint ( int itriangle, int vertexi, int vertexj ) const

private

{
    return itriangle == -1 ? -1 : this->triangle_midpoint(m_triangles[itriangle], vertexi, vertexj);
}

References m_triangles, and triangle_midpoint().

Here is the call graph for this function:

triangle_midpoint_or_allocate()

int Slic3r::TriangleSelector::triangle_midpoint_or_allocate ( int itriangle, int vertexi, int vertexj )

private

{
    int midpoint = this->triangle_midpoint(itriangle, vertexi, vertexj);
    if (midpoint == -1) {
        Vec3f c = 0.5f * (m_vertices[vertexi].v + m_vertices[vertexj].v);
#ifdef EXPENSIVE_DEBUG_CHECKS
        // Verify that the vertex is really a new one.
        auto it = std::find_if(m_vertices.begin(), m_vertices.end(), [c](const Vertex &v) {
            return v.ref_cnt > 0 && (v.v - c).norm() < EPSILON; });
        assert(it == m_vertices.end());
#endif // EXPENSIVE_DEBUG_CHECKS
        // Allocate a new vertex, possibly reusing the free list.
        if (m_free_vertices_head == -1) {
            // Allocate a new vertex.
            midpoint = int(m_vertices.size());
            m_vertices.emplace_back(c);
        } else {
            // Reuse a vertex from the free list.
            assert(m_free_vertices_head >= -1 && m_free_vertices_head < int(m_vertices.size()));
            midpoint = m_free_vertices_head;
            memcpy(&m_free_vertices_head, &m_vertices[midpoint].v[0], sizeof(m_free_vertices_head));
            assert(m_free_vertices_head >= -1 && m_free_vertices_head < int(m_vertices.size()));
            m_vertices[midpoint].v = c;
        }
        assert(m_vertices[midpoint].ref_cnt == 0);
    } else {
#ifndef NDEBUG
        Vec3f c1 = 0.5f * (m_vertices[vertexi].v + m_vertices[vertexj].v);
        Vec3f c2 = m_vertices[midpoint].v;
        float d = (c2 - c1).norm();
        assert(std::abs(d) < EPSILON);
#endif // NDEBUG
        assert(m_vertices[midpoint].ref_cnt > 0);
    }
    return midpoint;
}

References EPSILON, m_free_vertices_head, m_vertices, and triangle_midpoint().

Referenced by perform_split().

Here is the call graph for this function:

Here is the caller graph for this function:

triangle_subtriangles() [1/2]

std::pair< int, int > Slic3r::TriangleSelector::triangle_subtriangles ( const Triangle & tr, int vertexi, int vertexj )

staticprivate

{
    if (tr.number_of_split_sides() == 0)
        // If this triangle is not split, then there is no subtriangles touching the edge.
        return std::make_pair(-1, -1);
 
    // Find the triangle edge.
    int edge = tr.verts_idxs[0] == vertexi ? 0 : tr.verts_idxs[1] == vertexi ? 1 : 2;
    assert(tr.verts_idxs[edge] == vertexi);
    assert(tr.verts_idxs[next_idx_modulo(edge, 3)] == vertexj);
 
    if (tr.number_of_split_sides() == 1) {
        return edge == next_idx_modulo(tr.special_side(), 3) ? std::make_pair(tr.children[0], tr.children[1]) :
                                                                     std::make_pair(tr.children[edge == tr.special_side() ? 0 : 1], -1);
    } else if (tr.number_of_split_sides() == 2) {
        return edge == next_idx_modulo(tr.special_side(), 3) ? std::make_pair(tr.children[2], -1) :
               edge == tr.special_side()                           ? std::make_pair(tr.children[0], tr.children[1]) :
                                                                     std::make_pair(tr.children[2], tr.children[0]);
    } else {
        assert(tr.number_of_split_sides() == 3);
        assert(tr.special_side() == 0);
        return edge == 0 ? std::make_pair(tr.children[0], tr.children[1]) :
               edge == 1 ? std::make_pair(tr.children[1], tr.children[2]) :
                           std::make_pair(tr.children[2], tr.children[0]);
    }
 
    return std::make_pair(-1, -1);
}

References Slic3r::TriangleSelector::Triangle::children, Slic3r::next_idx_modulo(), Slic3r::TriangleSelector::Triangle::number_of_split_sides(), Slic3r::TriangleSelector::Triangle::special_side(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by append_touching_edges(), append_touching_subtriangles(), and triangle_subtriangles().

Here is the call graph for this function:

Here is the caller graph for this function:

triangle_subtriangles() [2/2]

std::pair< int, int > Slic3r::TriangleSelector::triangle_subtriangles ( int itriangle, int vertexi, int vertexj ) const

private

{
    return itriangle == -1 ? std::make_pair(-1, -1) : Slic3r::TriangleSelector::triangle_subtriangles(m_triangles[itriangle], vertexi, vertexj);
}

References m_triangles, and triangle_subtriangles().

Here is the call graph for this function:

undivide_triangle()

void Slic3r::TriangleSelector::undivide_triangle ( int facet_idx )

private

{
    assert(facet_idx < int(m_triangles.size()));
    Triangle& tr = m_triangles[facet_idx];
 
    if (tr.is_split()) {
        for (int i = 0; i <= tr.number_of_split_sides(); ++i) {
            int       child    = tr.children[i];
            Triangle &child_tr = m_triangles[child];
            assert(child_tr.valid());
            undivide_triangle(child);
            for (int j = 0; j < 3; ++j) {
                int     iv = child_tr.verts_idxs[j];
                Vertex &v  = m_vertices[iv];
                assert(v.ref_cnt > 0);
                if (-- v.ref_cnt == 0) {
                    // Release this vertex.
                    // Chain released vertices into a linked list through ref_cnt.
                    assert(m_free_vertices_head >= -1 && m_free_vertices_head < int(m_vertices.size()));
                    memcpy(&m_vertices[iv].v[0], &m_free_vertices_head, sizeof(m_free_vertices_head));
                    m_free_vertices_head = iv;
                    assert(m_free_vertices_head >= -1 && m_free_vertices_head < int(m_vertices.size()));
                }
            }
            // Chain released triangles into a linked list through children[0].
            assert(child_tr.valid());
            child_tr.m_valid = false;
            assert(m_free_triangles_head >= -1 && m_free_triangles_head < int(m_triangles.size()));
            assert(m_free_triangles_head == -1 || ! m_triangles[m_free_triangles_head].valid());
            child_tr.children[0] = m_free_triangles_head;
            m_free_triangles_head = child;
            assert(m_free_triangles_head >= -1 && m_free_triangles_head < int(m_triangles.size()));
            ++m_invalid_triangles;
        }
        tr.set_division(0, 0); // not split
    }
}

References Slic3r::TriangleSelector::Triangle::children, Slic3r::TriangleSelector::Triangle::is_split(), m_free_triangles_head, m_free_vertices_head, m_invalid_triangles, m_triangles, Slic3r::TriangleSelector::Triangle::m_valid, m_vertices, Slic3r::TriangleSelector::Triangle::number_of_split_sides(), Slic3r::TriangleSelector::Vertex::ref_cnt, Slic3r::TriangleSelector::Triangle::set_division(), undivide_triangle(), Slic3r::TriangleSelector::Triangle::valid(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by deserialize(), remove_useless_children(), select_triangle_recursive(), set_facet(), and undivide_triangle().

Here is the call graph for this function:

Here is the caller graph for this function:

verify_triangle_midpoints()

bool Slic3r::TriangleSelector::verify_triangle_midpoints ( const Triangle & tr ) const

private

{
    for (int i = 0; i < 3; ++ i) {
        int v1   = tr.verts_idxs[i];
        int v2   = tr.verts_idxs[next_idx_modulo(i, 3)];
        int vmid = this->triangle_midpoint(tr, v1, v2);
        assert(vmid >= -1);
        if (vmid != -1) {
            Vec3f c1 = 0.5f * (m_vertices[v1].v + m_vertices[v2].v);
            Vec3f c2 = m_vertices[vmid].v;
            float d  = (c2 - c1).norm();
            assert(std::abs(d) < EPSILON);
        }
    }
    return true;
}

References EPSILON, m_vertices, Slic3r::next_idx_modulo(), triangle_midpoint(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by verify_triangle_neighbors().

Here is the call graph for this function:

Here is the caller graph for this function:

verify_triangle_neighbors()

bool Slic3r::TriangleSelector::verify_triangle_neighbors ( const Triangle & tr, const Vec3i32 & neighbors ) const

protected

{
    assert(neighbors(0) >= -1);
    assert(neighbors(1) >= -1);
    assert(neighbors(2) >= -1);
    assert(verify_triangle_midpoints(tr));
 
    for (int i = 0; i < 3; ++i)
        if (neighbors(i) != -1) {
            const Triangle &tr2 = m_triangles[neighbors(i)];
            assert(verify_triangle_midpoints(tr2));
            int v1 = tr.verts_idxs[i];
            int v2 = tr.verts_idxs[next_idx_modulo(i, 3)];
            assert(tr2.verts_idxs[0] == v1 || tr2.verts_idxs[1] == v1 || tr2.verts_idxs[2] == v1);
            int j = tr2.verts_idxs[0] == v1 ? 0 : tr2.verts_idxs[1] == v1 ? 1 : 2;
            assert(tr2.verts_idxs[j] == v1);
            assert(tr2.verts_idxs[prev_idx_modulo(j, 3)] == v2);
        }
    return true;
}

References m_triangles, Slic3r::next_idx_modulo(), Slic3r::prev_idx_modulo(), verify_triangle_midpoints(), and Slic3r::TriangleSelector::Triangle::verts_idxs.

Referenced by bucket_fill_select_triangles(), child_neighbors(), get_seed_fill_contour(), get_seed_fill_contour_recursive(), perform_split(), precompute_all_neighbors(), precompute_all_neighbors_recursive(), select_triangle(), select_triangle_recursive(), select_unsplit_triangle(), select_unsplit_triangle(), split_triangle(), and Slic3r::GUI::TriangleSelectorPatch::update_triangles_per_patch().

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Symbol Documentation

TriangleCursor

friend class TriangleCursor

friend

References TriangleCursor.

Referenced by TriangleCursor.

Member Data Documentation

m_cursor

std::unique_ptr<Cursor> Slic3r::TriangleSelector::m_cursor

protected

Referenced by select_patch(), select_triangle_recursive(), and split_triangle().

m_edge_limit

float Slic3r::TriangleSelector::m_edge_limit = 0.6f

protected

Referenced by TriangleSelector().

m_edge_limit_sqr

float Slic3r::TriangleSelector::m_edge_limit_sqr = 1.f

protected

Referenced by set_edge_limit(), and split_triangle().

m_face_normals

const std::vector<Vec3f> Slic3r::TriangleSelector::m_face_normals

protected

Referenced by TriangleSelector(), bucket_fill_select_triangles(), Slic3r::TriangleCursor::build_cursor(), remap_painting(), seed_fill_select_triangles(), and select_patch().

m_free_triangles_head

int Slic3r::TriangleSelector::m_free_triangles_head { -1 }

private

{ -1 };

Referenced by garbage_collect(), push_triangle(), reset(), and undivide_triangle().

m_free_vertices_head

int Slic3r::TriangleSelector::m_free_vertices_head { -1 }

private

{ -1 };

Referenced by garbage_collect(), reset(), triangle_midpoint_or_allocate(), and undivide_triangle().

m_invalid_triangles

int Slic3r::TriangleSelector::m_invalid_triangles

protected

Referenced by garbage_collect(), push_triangle(), reset(), select_triangle(), and undivide_triangle().

m_mesh

const TriangleMesh& Slic3r::TriangleSelector::m_mesh

protected

Referenced by TriangleSelector(), deserialize(), and reset().

m_neighbors

const std::vector<Vec3i32> Slic3r::TriangleSelector::m_neighbors

protected

Referenced by TriangleSelector(), deserialize(), get_facets_strict(), get_seed_fill_contour(), precompute_all_neighbors(), seed_fill_select_triangles(), select_patch(), select_triangle(), and select_unsplit_triangle().

m_old_cursor_radius_sqr

float Slic3r::TriangleSelector::m_old_cursor_radius_sqr = 0

protected

Referenced by select_patch().

m_orig_size_indices

int Slic3r::TriangleSelector::m_orig_size_indices = 0

protected

Referenced by garbage_collect(), get_facets_strict(), get_seed_fill_contour(), precompute_all_neighbors(), reset(), seed_fill_select_triangles(), select_patch(), serialize(), and set_facet().

m_orig_size_vertices

int Slic3r::TriangleSelector::m_orig_size_vertices = 0

protected

Referenced by garbage_collect(), and reset().

m_triangles

std::vector<Triangle> Slic3r::TriangleSelector::m_triangles

protected

Referenced by append_touching_edges(), append_touching_subtriangles(), bucket_fill_select_triangles(), child_neighbors(), deserialize(), garbage_collect(), get_facets(), get_facets(), get_facets_strict(), get_facets_strict_recursive(), get_seed_fill_contour(), get_seed_fill_contour_recursive(), has_facets(), is_facet_clipped(), neighbor_child(), neighbor_child(), num_facets(), perform_split(), precompute_all_neighbors(), precompute_all_neighbors_recursive(), push_triangle(), remap_painting(), remap_triangle_state(), remove_useless_children(), reset(), seed_fill_apply_on_triangles(), seed_fill_select_triangles(), seed_fill_unselect_all_triangles(), select_patch(), select_triangle(), select_triangle_recursive(), select_unsplit_triangle(), select_unsplit_triangle(), serialize(), set_facet(), shift_states_above(), split_triangle(), triangle_midpoint(), triangle_midpoint(), triangle_subtriangles(), undivide_triangle(), Slic3r::GUI::TriangleSelectorGUI::update_render_data(), Slic3r::GUI::TriangleSelectorPatch::update_selector_triangles(), Slic3r::GUI::TriangleSelectorPatch::update_triangles_per_patch(), Slic3r::GUI::TriangleSelectorPatch::update_triangles_per_type(), and verify_triangle_neighbors().

m_vertices

std::vector<Vertex> Slic3r::TriangleSelector::m_vertices

protected

Referenced by Slic3r::TriangleCursor::build_cursor(), deserialize(), garbage_collect(), get_facets(), get_facets(), get_facets_strict(), is_facet_clipped(), push_triangle(), remap_painting(), reset(), select_patch(), select_triangle_recursive(), select_unsplit_triangle(), split_triangle(), triangle_midpoint_or_allocate(), undivide_triangle(), Slic3r::GUI::TriangleSelectorGUI::update_paint_contour(), Slic3r::GUI::TriangleSelectorGUI::update_render_data(), Slic3r::GUI::TriangleSelectorPatch::update_triangles_per_patch(), Slic3r::GUI::TriangleSelectorPatch::update_triangles_per_type(), and verify_triangle_midpoints().

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/TriangleSelector.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/TriangleSelector.cpp