#include <src/libslic3r/Arachne/SkeletalTrapezoidationGraph.hpp>

Inheritance diagram for Slic3r::Arachne::SkeletalTrapezoidationGraph:

Collaboration diagram for Slic3r::Arachne::SkeletalTrapezoidationGraph:

Public Types
using	Edges = std::list< edge_t >

using	Nodes = std::list< node_t >

Public Member Functions
void	collapseSmallEdges (coord_t snap_dist=5)

void	makeRib (edge_t *&prev_edge, Point start_source_point, Point end_source_point, bool is_next_to_start_or_end)

edge_t *	insertNode (edge_t *edge, Point mid, coord_t mide_node_bead_count)

std::pair< edge_t , edge_t >	insertRib (edge_t &edge, node_t *mid_node)

Public Attributes
Edges	edges

Nodes	nodes

Protected Member Functions
Line	getSource (const edge_t &edge) const

Private Types
using	edge_t = STHalfEdge

using	node_t = STHalfEdgeNode

Detailed Description

Member Typedef Documentation

◆ edge_t

using Slic3r::Arachne::SkeletalTrapezoidationGraph::edge_t = STHalfEdge

private

◆ Edges

using Slic3r::Arachne::HalfEdgeGraph< SkeletalTrapezoidationJoint , SkeletalTrapezoidationEdge , STHalfEdgeNode , STHalfEdge >::Edges = std::list<edge_t>

inherited

◆ node_t

using Slic3r::Arachne::SkeletalTrapezoidationGraph::node_t = STHalfEdgeNode

private

◆ Nodes

using Slic3r::Arachne::HalfEdgeGraph< SkeletalTrapezoidationJoint , SkeletalTrapezoidationEdge , STHalfEdgeNode , STHalfEdge >::Nodes = std::list<node_t>

inherited

Member Function Documentation

◆ collapseSmallEdges()

void Slic3r::Arachne::SkeletalTrapezoidationGraph::collapseSmallEdges ( coord_t snap_dist = 5 )

If an edge is too small, collapse it and its twin and fix the surrounding edges to ensure a consistent graph.

Don't collapse support edges, unless we can collapse the whole quad.

o-, | "-o | | > Don't collapse this edge only. o o

{
    ankerl::unordered_dense::map<edge_t*, Edges::iterator> edge_locator;
    ankerl::unordered_dense::map<node_t*, Nodes::iterator> node_locator;
    
    for (auto edge_it = edges.begin(); edge_it != edges.end(); ++edge_it)
    {
        edge_locator.emplace(&*edge_it, edge_it);
    }
    
    for (auto node_it = nodes.begin(); node_it != nodes.end(); ++node_it)
    {
        node_locator.emplace(&*node_it, node_it);
    }
    
    auto safelyRemoveEdge = [this, &edge_locator](edge_t* to_be_removed, Edges::iterator& current_edge_it, bool& edge_it_is_updated)
    {
        if (current_edge_it != edges.end()
            && to_be_removed == &*current_edge_it)
        {
            current_edge_it = edges.erase(current_edge_it);
            edge_it_is_updated = true;
        }
        else
        {
            edges.erase(edge_locator[to_be_removed]);
        }
    };
 
    auto should_collapse = [snap_dist](node_t* a, node_t* b) 
    { 
        return shorter_then(a->p - b->p, snap_dist);
    };
        
    for (auto edge_it = edges.begin(); edge_it != edges.end();)
    {
        if (edge_it->prev)
        {
            edge_it++;
            continue;
        }
        
        edge_t* quad_start = &*edge_it;
        edge_t* quad_end = quad_start; while (quad_end->next) quad_end = quad_end->next;
        edge_t* quad_mid = (quad_start->next == quad_end)? nullptr : quad_start->next;
 
        bool edge_it_is_updated = false;
        if (quad_mid && should_collapse(quad_mid->from, quad_mid->to))
        {
            assert(quad_mid->twin);
            if(!quad_mid->twin)
            {
                BOOST_LOG_TRIVIAL(warning) << "Encountered quad edge without a twin.";
                continue; //Prevent accessing unallocated memory.
            }
            int count = 0;
            for (edge_t* edge_from_3 = quad_end; edge_from_3 && edge_from_3 != quad_mid->twin; edge_from_3 = edge_from_3->twin->next)
            {
                edge_from_3->from = quad_mid->from;
                edge_from_3->twin->to = quad_mid->from;
                if (count > 50)
                {
                    std::cerr << edge_from_3->from->p << " - " << edge_from_3->to->p << '\n';
                }
                if (++count > 1000) 
                {
                    break;
                }
            }
 
            // o-o > collapse top
            // | |
            // | |
            // | |
            // o o
            if (quad_mid->from->incident_edge == quad_mid)
            {
                if (quad_mid->twin->next)
                {
                    quad_mid->from->incident_edge = quad_mid->twin->next;
                }
                else
                {
                    quad_mid->from->incident_edge = quad_mid->prev->twin;
                }
            }
            
            nodes.erase(node_locator[quad_mid->to]);
 
            quad_mid->prev->next = quad_mid->next;
            quad_mid->next->prev = quad_mid->prev;
            quad_mid->twin->next->prev = quad_mid->twin->prev;
            quad_mid->twin->prev->next = quad_mid->twin->next;
 
            safelyRemoveEdge(quad_mid->twin, edge_it, edge_it_is_updated);
            safelyRemoveEdge(quad_mid, edge_it, edge_it_is_updated);
        }
 
        //  o-o
        //  | | > collapse sides
        //  o o
        if ( should_collapse(quad_start->from, quad_end->to) && should_collapse(quad_start->to, quad_end->from))
        { // Collapse start and end edges and remove whole cell
 
            quad_start->twin->to = quad_end->to;
            quad_end->to->incident_edge = quad_end->twin;
            if (quad_end->from->incident_edge == quad_end)
            {
                if (quad_end->twin->next)
                {
                    quad_end->from->incident_edge = quad_end->twin->next;
                }
                else
                {
                    quad_end->from->incident_edge = quad_end->prev->twin;
                }
            }
            nodes.erase(node_locator[quad_start->from]);
 
            quad_start->twin->twin = quad_end->twin;
            quad_end->twin->twin = quad_start->twin;
            safelyRemoveEdge(quad_start, edge_it, edge_it_is_updated);
            safelyRemoveEdge(quad_end, edge_it, edge_it_is_updated);
        }
        // If only one side had collapsable length then the cell on the other side of that edge has to collapse
        // if we would collapse that one edge then that would change the quad_start and/or quad_end of neighboring cells
        // this is to do with the constraint that !prev == !twin.next
 
        if (!edge_it_is_updated)
        {
            edge_it++;
        }
    }
}

Referenced by Slic3r::Arachne::SkeletalTrapezoidation::constructFromPolygons().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getSource()

Line Slic3r::Arachne::SkeletalTrapezoidationGraph::getSource ( const edge_t & edge ) const

protected

{
    const edge_t *from_edge = &edge;
    while (from_edge->prev)
        from_edge = from_edge->prev;
 
    const edge_t *to_edge = &edge;
    while (to_edge->next)
        to_edge = to_edge->next;
 
    return Line(from_edge->from->p, to_edge->to->p);
}

References Slic3r::Arachne::HalfEdge< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::from, Slic3r::Arachne::HalfEdge< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::next, Slic3r::Arachne::HalfEdgeNode< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::p, Slic3r::Arachne::HalfEdge< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::prev, and Slic3r::Arachne::HalfEdge< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::to.

Referenced by insertRib().

Here is the caller graph for this function:

◆ insertNode()

SkeletalTrapezoidationGraph::edge_t * Slic3r::Arachne::SkeletalTrapezoidationGraph::insertNode	(	edge_t *	edge,
		Point	mid,
		coord_t	mide_node_bead_count
	)

Insert a node into the graph and connect it to the input polygon using ribs

Returns: the last edge which replaced [edge], which points to the same [to] node

{
    edge_t* last_edge_replacing_input = edge;
 
    nodes.emplace_back(SkeletalTrapezoidationJoint(), mid);
    node_t* mid_node = &nodes.back();
 
    edge_t* twin = last_edge_replacing_input->twin;
    last_edge_replacing_input->twin = nullptr;
    twin->twin = nullptr;
    std::pair<edge_t*, edge_t*> left_pair = insertRib(*last_edge_replacing_input, mid_node);
    std::pair<edge_t*, edge_t*> right_pair = insertRib(*twin, mid_node);
    edge_t* first_edge_replacing_input = left_pair.first;
    last_edge_replacing_input = left_pair.second;
    edge_t* first_edge_replacing_twin = right_pair.first;
    edge_t* last_edge_replacing_twin = right_pair.second;
 
    first_edge_replacing_input->twin = last_edge_replacing_twin;
    last_edge_replacing_twin->twin = first_edge_replacing_input;
    last_edge_replacing_input->twin = first_edge_replacing_twin;
    first_edge_replacing_twin->twin = last_edge_replacing_input;
 
    mid_node->data.bead_count = mide_node_bead_count;
 
    return last_edge_replacing_input;
}

References Slic3r::Arachne::SkeletalTrapezoidationJoint::bead_count, Slic3r::Arachne::HalfEdgeNode< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::data, insertRib(), Slic3r::Arachne::HalfEdgeGraph< SkeletalTrapezoidationJoint, SkeletalTrapezoidationEdge, STHalfEdgeNode, STHalfEdge >::nodes, and Slic3r::Arachne::HalfEdge< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::twin.

Referenced by Slic3r::Arachne::SkeletalTrapezoidation::applyTransitions(), and Slic3r::Arachne::SkeletalTrapezoidation::generateExtraRibs().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insertRib()

std::pair< SkeletalTrapezoidationGraph::edge_t , SkeletalTrapezoidationGraph::edge_t > Slic3r::Arachne::SkeletalTrapezoidationGraph::insertRib	(	edge_t &	edge,
		node_t *	mid_node
	)

Return the first and last edge of the edges replacing edge pointing to the same node

{
    edge_t* edge_before = edge.prev;
    edge_t* edge_after = edge.next;
    node_t* node_before = edge.from;
    node_t* node_after = edge.to;
    
    Point p = mid_node->p;
 
    const Line source_segment = getSource(edge);
    Point      px;
    source_segment.distance_to_squared(p, &px);
    coord_t dist = (p - px).cast<int64_t>().norm();
    assert(dist > 0);
    mid_node->data.distance_to_boundary = dist;
    mid_node->data.transition_ratio = 0; // Both transition end should have rest = 0, because at the ends a whole number of beads fits without rest
 
    nodes.emplace_back(SkeletalTrapezoidationJoint(), px);
    node_t* source_node = &nodes.back();
    source_node->data.distance_to_boundary = 0;
 
    edge_t* first = &edge;
    edges.emplace_back(SkeletalTrapezoidationEdge());
    edge_t* second = &edges.back();
    edges.emplace_back(SkeletalTrapezoidationEdge(SkeletalTrapezoidationEdge::EdgeType::TRANSITION_END));
    edge_t* outward_edge = &edges.back();
    edges.emplace_back(SkeletalTrapezoidationEdge(SkeletalTrapezoidationEdge::EdgeType::TRANSITION_END));
    edge_t* inward_edge = &edges.back();
 
    if (edge_before)
    {
        edge_before->next = first;
    }
    first->next = outward_edge;
    outward_edge->next = nullptr;
    inward_edge->next = second;
    second->next = edge_after;
 
    if (edge_after) 
    {
        edge_after->prev = second;
    }
    second->prev = inward_edge;
    inward_edge->prev = nullptr;
    outward_edge->prev = first;
    first->prev = edge_before;
 
    first->to = mid_node;
    outward_edge->to = source_node;
    inward_edge->to = mid_node;
    second->to = node_after;
 
    first->from = node_before;
    outward_edge->from = mid_node;
    inward_edge->from = source_node;
    second->from = mid_node;
 
    node_before->incident_edge = first;
    mid_node->incident_edge = outward_edge;
    source_node->incident_edge = inward_edge;
    if (edge_after) 
    {
        node_after->incident_edge = edge_after;
    }
 
    first->data.setIsCentral(true);
    outward_edge->data.setIsCentral(false); // TODO verify this is always the case.
    inward_edge->data.setIsCentral(false);
    second->data.setIsCentral(true);
 
    outward_edge->twin = inward_edge;
    inward_edge->twin = outward_edge;
 
    first->twin = nullptr; // we don't know these yet!
    second->twin = nullptr;
 
    assert(second->prev->from->data.distance_to_boundary == 0);
 
    return std::make_pair(first, second);
}

Referenced by insertNode().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ makeRib()

void Slic3r::Arachne::SkeletalTrapezoidationGraph::makeRib	(	edge_t *&	prev_edge,
		Point	start_source_point,
		Point	end_source_point,
		bool	is_next_to_start_or_end
	)

{
    Point p;
    Line(start_source_point, end_source_point).distance_to_infinite_squared(prev_edge->to->p, &p);
    coord_t dist = (prev_edge->to->p - p).cast<int64_t>().norm();
    prev_edge->to->data.distance_to_boundary = dist;
    assert(dist >= 0);
 
    nodes.emplace_front(SkeletalTrapezoidationJoint(), p);
    node_t* node = &nodes.front();
    node->data.distance_to_boundary = 0;
    
    edges.emplace_front(SkeletalTrapezoidationEdge(SkeletalTrapezoidationEdge::EdgeType::EXTRA_VD));
    edge_t* forth_edge = &edges.front();
    edges.emplace_front(SkeletalTrapezoidationEdge(SkeletalTrapezoidationEdge::EdgeType::EXTRA_VD));
    edge_t* back_edge = &edges.front();
    
    prev_edge->next = forth_edge;
    forth_edge->prev = prev_edge;
    forth_edge->from = prev_edge->to;
    forth_edge->to = node;
    forth_edge->twin = back_edge;
    back_edge->twin = forth_edge;
    back_edge->from = node;
    back_edge->to = prev_edge->to;
    node->incident_edge = back_edge;
    
    prev_edge = back_edge;
}

Referenced by Slic3r::Arachne::SkeletalTrapezoidation::constructFromPolygons(), and Slic3r::Arachne::SkeletalTrapezoidation::transferEdge().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ edges

Edges Slic3r::Arachne::HalfEdgeGraph< SkeletalTrapezoidationJoint , SkeletalTrapezoidationEdge , STHalfEdgeNode , STHalfEdge >::edges

inherited

◆ nodes

Nodes Slic3r::Arachne::HalfEdgeGraph< SkeletalTrapezoidationJoint , SkeletalTrapezoidationEdge , STHalfEdgeNode , STHalfEdge >::nodes

inherited

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

src/libslic3r/Arachne/SkeletalTrapezoidationGraph.hpp
src/libslic3r/Arachne/SkeletalTrapezoidationGraph.cpp

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Private Types

Detailed Description

Member Typedef Documentation

◆ edge_t

◆ Edges

◆ node_t

◆ Nodes

Member Function Documentation

◆ collapseSmallEdges()

◆ getSource()

◆ insertNode()

◆ insertRib()

◆ makeRib()

Member Data Documentation

◆ edges

◆ nodes