Slic3r::Triangulation Class Reference

#include <src/libslic3r/Triangulation.hpp>

Public Types
using	HalfEdge = std::pair< uint32_t, uint32_t >
using	HalfEdges = std::vector< HalfEdge >
using	Indices = std::vector< Vec3i >
using	Changes = std::vector< uint32_t >

Public Member Functions
	Triangulation ()=delete

Static Public Member Functions
static Indices	triangulate (const Points &points, const HalfEdges &half_edges)
	Connect points by triangulation to create filled surface by triangles Input points have to be unique Inspiration for make unique points is Emboss::dilate_to_unique_points.
static Indices	triangulate (const Polygon &polygon)
static Indices	triangulate (const Polygons &polygons)
static Indices	triangulate (const ExPolygon &expolygon)
static Indices	triangulate (const ExPolygons &expolygons)
static Changes	create_changes (const Points &points, const Points &duplicits)
	Create conversion map from original index into new with respect of duplicit point.
static Indices	triangulate (const ExPolygons &expolygons, const Points &points)
	Triangulation for expolygons, speed up when points are already collected NOTE: Not working properly for ExPolygons with multiple point on same coordinate You should check it by "collect_changes".
static Indices	triangulate (const ExPolygons &expolygons, const Points &points, const Changes &changes)
	Triangulation for expolygons containing multiple points with same coordinate.

Detailed Description

Member Typedef Documentation

Changes

using Slic3r::Triangulation::Changes = std::vector<uint32_t>

HalfEdge

using Slic3r::Triangulation::HalfEdge = std::pair<uint32_t, uint32_t>

HalfEdges

using Slic3r::Triangulation::HalfEdges = std::vector<HalfEdge>

Indices

using Slic3r::Triangulation::Indices = std::vector<Vec3i>

Constructor & Destructor Documentation

Triangulation()

Slic3r::Triangulation::Triangulation ( )

delete

Member Function Documentation

create_changes()

Triangulation::Changes Triangulation::create_changes ( const Points &  points, const Points &  duplicits  )

static

Create conversion map from original index into new with respect of duplicit point.

Parameters

points	input set of points
duplicits	duplicit points collected from points

Returns

Conversion map for point index

{
    assert(!duplicits.empty());
    assert(duplicits.size() < points.size()/2);
    std::vector<uint32_t> duplicit_indices(duplicits.size(), std::numeric_limits<uint32_t>::max());
    Changes changes; 
    changes.reserve(points.size());
    uint32_t index = 0;
    for (const Point &p: points) {
        auto it = std::lower_bound(duplicits.begin(), duplicits.end(), p);
        if (it == duplicits.end() || *it != p) { 
            changes.push_back(index);
            ++index;
            continue;
        }
        uint32_t &d_index = duplicit_indices[it - duplicits.begin()];
        if (d_index == std::numeric_limits<uint32_t>::max()) {
            d_index = index;
            changes.push_back(index);
            ++index;
        } else {
            changes.push_back(d_index);
        }
    }
    return changes;
}

Referenced by priv::polygons2model_duplicit(), and triangulate().

Here is the caller graph for this function:

triangulate() [1/7]

Triangulation::Indices Triangulation::triangulate ( const ExPolygon &  expolygon )

static

                                                                         {
    ExPolygons expolys({expolygon}); 
    return triangulate(expolys);
}

References triangulate().

Here is the call graph for this function:

triangulate() [2/7]

Triangulation::Indices Triangulation::triangulate ( const ExPolygons &  expolygons )

static

                                                                           {
    Points pts = to_points(expolygons);
    Points d_pts = collect_duplicates(pts);
    if (d_pts.empty()) return triangulate(expolygons, pts);
 
    Changes changes = create_changes(pts, d_pts);
    Indices indices = triangulate(expolygons, pts, changes);
    // reverse map for changes
    Changes changes2(changes.size(), std::numeric_limits<uint32_t>::max());
    for (size_t i = 0; i < changes.size(); ++i)
        changes2[changes[i]] = i;
 
    // convert indices into expolygons indicies
    for (Vec3i &t : indices) 
        for (size_t ti = 0; ti < 3; ti++) t[ti] = changes2[t[ti]];
    
    return indices;
}

References Slic3r::collect_duplicates(), create_changes(), Slic3r::to_points(), and triangulate().

Here is the call graph for this function:

triangulate() [3/7]

Triangulation::Indices Triangulation::triangulate ( const ExPolygons &  expolygons, const Points &  points  )

static

Triangulation for expolygons, speed up when points are already collected NOTE: Not working properly for ExPolygons with multiple point on same coordinate You should check it by "collect_changes".

Parameters

expolygons	Input shape to triangulation - define edges
points	Points from expolygons

Returns

Triangle indices

{
    assert(count_points(expolygons) == points.size());
    // when contain duplicit coordinate in points will not work properly
    assert(collect_duplicates(points).empty());
 
    HalfEdges edges;
    edges.reserve(points.size());
    uint32_t offset = 0;
    for (const ExPolygon &expolygon : expolygons) {
        priv::insert_edges(edges, offset, expolygon.contour);
        for (const Polygon &hole : expolygon.holes)
            priv::insert_edges(edges, offset, hole);
    }
    std::sort(edges.begin(), edges.end());
    return triangulate(points, edges);
}

References Slic3r::collect_duplicates(), Slic3r::count_points(), Slic3r::empty(), priv::insert_edges(), Slic3r::offset(), and triangulate().

Here is the call graph for this function:

triangulate() [4/7]

Triangulation::Indices Triangulation::triangulate ( const ExPolygons &  expolygons, const Points &  points, const Changes &  changes  )

static

Triangulation for expolygons containing multiple points with same coordinate.

Parameters

expolygons	Input shape to triangulation - define edge
points	Points from expolygons
changes	Changes swap for indicies into points

Returns

Triangle indices

{
    assert(!points.empty());
    assert(count_points(expolygons) == points.size());
    assert(changes.size() == points.size());
    // IMPROVE: search from end and somehow distiquish that value is not a change
    uint32_t count_points = *std::max_element(changes.begin(), changes.end())+1;
    Points pts(count_points);
    for (size_t i = 0; i < changes.size(); i++)
        pts[changes[i]] = points[i];    
 
    HalfEdges edges;
    edges.reserve(points.size());
    uint32_t offset = 0;
    for (const ExPolygon &expolygon : expolygons) {
        priv::insert_edges(edges, offset, expolygon.contour, changes);
        for (const Polygon &hole : expolygon.holes)
            priv::insert_edges(edges, offset, hole, changes);
    }
 
    std::sort(edges.begin(), edges.end());
    return triangulate(pts, edges);
}

References Slic3r::count_points(), priv::insert_edges(), Slic3r::offset(), and triangulate().

Here is the call graph for this function:

triangulate() [5/7]

Triangulation::Indices Triangulation::triangulate ( const Points &  points, const HalfEdges &  half_edges  )

static

Connect points by triangulation to create filled surface by triangles Input points have to be unique Inspiration for make unique points is Emboss::dilate_to_unique_points.

Parameters

points	Points to connect
edges	Constraint for edges, pair is from point(first) to point(second), sorted lexicographically

Returns

Triangles

{
    assert(!points.empty());
    assert(!constrained_half_edges.empty());
    // constrained must be sorted
    assert(std::is_sorted(constrained_half_edges.begin(),
                          constrained_half_edges.end()));
    // check that there is no duplicit constrained edge
    assert(std::adjacent_find(constrained_half_edges.begin(), constrained_half_edges.end()) == constrained_half_edges.end());
    // edges can NOT contain bidirectional constrained
    assert(!priv::has_bidirectional_constrained(constrained_half_edges));
    // check that there is only unique poistion of points
    assert(priv::is_unique(points));
    assert(!priv::has_self_intersection(points, constrained_half_edges));
    // use cgal triangulation
    using K   = CGAL::Exact_predicates_inexact_constructions_kernel;
    using Vb  = CGAL::Triangulation_vertex_base_with_info_2<uint32_t, K>;
    using Fb  = CGAL::Constrained_triangulation_face_base_2<K>;
    using Tds = CGAL::Triangulation_data_structure_2<Vb, Fb>;
    using CDT = CGAL::Constrained_Delaunay_triangulation_2<K, Tds, CGAL::Exact_predicates_tag>;
 
    // construct a constrained triangulation
    CDT cdt;
    {
        std::vector<CDT::Vertex_handle> vertices_handle(points.size()); // for constriants
        using Point_with_ord = std::pair<CDT::Point, size_t>;
        using SearchTrait    = CGAL::Spatial_sort_traits_adapter_2
            <K, CGAL::First_of_pair_property_map<Point_with_ord> >;
 
        std::vector<Point_with_ord> cdt_points;
        cdt_points.reserve(points.size());
        size_t ord = 0;
        for (const auto &p : points)
            cdt_points.emplace_back(std::make_pair(CDT::Point{p.x(), p.y()}, ord++));
        
        SearchTrait st;
        CGAL::spatial_sort(cdt_points.begin(), cdt_points.end(), st);
        CDT::Face_handle f;
        for (const auto& p : cdt_points) {
            auto handle = cdt.insert(p.first, f);
            handle->info() = p.second;
            vertices_handle[p.second] = handle;
            f = handle->face();
        }
 
        // Constrain the triangulation.
        for (const HalfEdge &edge : constrained_half_edges)
            cdt.insert_constraint(vertices_handle[edge.first], vertices_handle[edge.second]);
    }
 
    auto faces = cdt.finite_face_handles();
 
    // Unmark constrained edges of outside faces.
    size_t num_faces = 0;
    for (CDT::Face_handle fh : faces) {
        for (int i = 0; i < 3; ++i) {
            if (!fh->is_constrained(i)) continue;
            auto key = std::make_pair(fh->vertex((i + 2) % 3)->info(), fh->vertex((i + 1) % 3)->info());
            auto it = std::lower_bound(constrained_half_edges.begin(), constrained_half_edges.end(), key);
            if (it == constrained_half_edges.end() || *it != key) continue;
            // This face contains a constrained edge and it is outside.
            for (int j = 0; j < 3; ++ j)
                fh->set_constraint(j, false);
            --num_faces;
            break;            
        }
        ++num_faces;
    }
 
    auto inside = [](CDT::Face_handle &fh) { 
        return fh->neighbor(0) != fh && 
               (fh->is_constrained(0) ||
                fh->is_constrained(1) ||
                fh->is_constrained(2)); 
    };
 
#ifdef VISUALIZE_TRIANGULATION
    std::vector<Vec3i> indices2;
    indices2.reserve(num_faces);
    for (CDT::Face_handle fh : faces)
        if (inside(fh)) indices2.emplace_back(fh->vertex(0)->info(), fh->vertex(1)->info(), fh->vertex(2)->info());
    visualize(points, indices2, "C:/data/temp/triangulation_without_floodfill.obj");
#endif // VISUALIZE_TRIANGULATION
 
    // Propagate inside the constrained regions.
    std::vector<CDT::Face_handle> queue;
    queue.reserve(num_faces);
    for (CDT::Face_handle seed : faces){
        if (!inside(seed)) continue;    
        // Seed fill to neighbor faces.
        queue.emplace_back(seed);
        while (! queue.empty()) {
            CDT::Face_handle fh = queue.back();
            queue.pop_back();
            for (int i = 0; i < 3; ++i) {
                if (fh->is_constrained(i)) continue;
                // Propagate along this edge.
                fh->set_constraint(i, true);
                CDT::Face_handle nh = fh->neighbor(i);
                bool was_inside = inside(nh);
                // Mark the other side of this edge.
                nh->set_constraint(nh->index(fh), true);
                if (! was_inside)
                    queue.push_back(nh);
            }
        }
    }
 
    std::vector<Vec3i> indices;
    indices.reserve(num_faces);
    for (CDT::Face_handle fh : faces)
        if (inside(fh))
            indices.emplace_back(fh->vertex(0)->info(), fh->vertex(1)->info(), fh->vertex(2)->info());
 
#ifdef VISUALIZE_TRIANGULATION
    visualize(points, indices, "C:/data/temp/triangulation.obj");
#endif // VISUALIZE_TRIANGULATION
 
    return indices;
}

References Slic3r::f(), priv::has_bidirectional_constrained(), priv::has_self_intersection(), and priv::is_unique().

Referenced by priv::polygons2model_duplicit(), priv::polygons2model_unique(), triangulate(), triangulate(), triangulate(), triangulate(), triangulate(), and triangulate().

Here is the call graph for this function:

Here is the caller graph for this function:

triangulate() [6/7]

Triangulation::Indices Triangulation::triangulate ( const Polygon &  polygon )

static

{
    const Points &pts = polygon.points;
    HalfEdges edges;
    edges.reserve(pts.size());
    uint32_t offset = 0;
    priv::insert_edges(edges, offset, polygon);
    std::sort(edges.begin(), edges.end());
    return triangulate(pts, edges);
}

References priv::insert_edges(), Slic3r::offset(), Slic3r::MultiPoint::points, and triangulate().

Here is the call graph for this function:

triangulate() [7/7]

Triangulation::Indices Triangulation::triangulate ( const Polygons &  polygons )

static

{
    size_t count = count_points(polygons);
    Points points;
    points.reserve(count);
 
    HalfEdges edges;
    edges.reserve(count);
    uint32_t  offset = 0;
 
    for (const Polygon &polygon : polygons) {
        Slic3r::append(points, polygon.points);
        priv::insert_edges(edges, offset, polygon);
    }
 
    std::sort(edges.begin(), edges.end());
    return triangulate(points, edges);
}

References Slic3r::append(), Slic3r::count_points(), priv::insert_edges(), Slic3r::offset(), and triangulate().

Here is the call graph for this function:

---

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

• src/libslic3r/Triangulation.hpp
• src/libslic3r/Triangulation.cpp