Slic3r::SeamPlacerImpl Namespace Reference

Classes
struct	CoordinateFunctor
class	Frame
	Coordinate frame. More...
struct	GlobalModelInfo
struct	Perimeter
struct	SeamCandidate
struct	SeamCandidateCoordinateFunctor
struct	SeamComparator

Enumerations
enum class	EnforcedBlockedSeamPoint { Blocked = 0 , Neutral = 1 , Enforced = 2 }

Functions
template<typename T >
int	sgn (T val)
float	gauss (float value, float mean_x_coord, float mean_value, float falloff_speed)
float	compute_angle_penalty (float ccw_angle)
Vec3f	sample_sphere_uniform (const Vec2f &samples)
Vec3f	sample_hemisphere_uniform (const Vec2f &samples)
Vec3f	sample_power_cosine_hemisphere (const Vec2f &samples, float power)
std::vector< float >	raycast_visibility (const AABBTreeIndirect::Tree< 3, float > &raycasting_tree, const indexed_triangle_set &triangles, const TriangleSetSamples &samples, size_t negative_volumes_start_index)
std::vector< float >	calculate_polygon_angles_at_vertices (const Polygon &polygon, const std::vector< float > &lengths, float min_arm_length)
Polygons	extract_perimeter_polygons (const Layer *layer, std::vector< const LayerRegion * > &corresponding_regions_out)
void	process_perimeter_polygon (const Polygon &orig_polygon, float z_coord, const LayerRegion *region, const GlobalModelInfo &global_model_info, PrintObjectSeamData::LayerSeams &result)
std::pair< size_t, size_t >	find_previous_and_next_perimeter_point (const std::vector< SeamCandidate > &perimeter_points, size_t point_index)
void	compute_global_occlusion (GlobalModelInfo &result, const PrintObject *po, std::function< void(void)> throw_if_canceled)
void	gather_enforcers_blockers (GlobalModelInfo &result, const PrintObject *po)
void	pick_seam_point (std::vector< SeamCandidate > &perimeter_points, size_t start_index, const SeamComparator &comparator)
size_t	pick_nearest_seam_point_index (const std::vector< SeamCandidate > &perimeter_points, size_t start_index, const Vec2f &preffered_location)
void	pick_random_seam_point (const std::vector< SeamCandidate > &perimeter_points, size_t start_index)

---

Class Documentation

Slic3r::SeamPlacerImpl::Perimeter

struct Slic3r::SeamPlacerImpl::Perimeter

Collaboration diagram for Slic3r::SeamPlacerImpl::Perimeter:

Class Members
size_t	end_index {}
Vec3f	final_seam_position = Vec3f::Zero()
bool	finalized = false
float	flow_width {}
size_t	seam_index {}
size_t	start_index {}

Enumeration Type Documentation

EnforcedBlockedSeamPoint

enum class Slic3r::SeamPlacerImpl::EnforcedBlockedSeamPoint

strong

Enumerator
Blocked
Neutral
Enforced

                                    {
    Blocked = 0,
    Neutral = 1,
    Enforced = 2,
};

Function Documentation

calculate_polygon_angles_at_vertices()

std::vector< float > Slic3r::SeamPlacerImpl::calculate_polygon_angles_at_vertices	(	const Polygon &	polygon,
		const std::vector< float > &	lengths,
		float	min_arm_length
	)

                              {
    std::vector<float> result(polygon.size());
 
    if (polygon.size() == 1) {
        result[0] = 0.0f;
    }
 
    size_t idx_prev = 0;
    size_t idx_curr = 0;
    size_t idx_next = 0;
 
    float distance_to_prev = 0;
    float distance_to_next = 0;
 
    //push idx_prev far enough back as initialization
    while (distance_to_prev < min_arm_length) {
        idx_prev = Slic3r::prev_idx_modulo(idx_prev, polygon.size());
        distance_to_prev += lengths[idx_prev];
    }
 
    for (size_t _i = 0; _i < polygon.size(); ++_i) {
        // pull idx_prev to current as much as possible, while respecting the min_arm_length
        while (distance_to_prev - lengths[idx_prev] > min_arm_length) {
            distance_to_prev -= lengths[idx_prev];
            idx_prev = Slic3r::next_idx_modulo(idx_prev, polygon.size());
        }
 
        //push idx_next forward as far as needed
        while (distance_to_next < min_arm_length) {
            distance_to_next += lengths[idx_next];
            idx_next = Slic3r::next_idx_modulo(idx_next, polygon.size());
        }
 
        // Calculate angle between idx_prev, idx_curr, idx_next.
        const Point &p0 = polygon.points[idx_prev];
        const Point &p1 = polygon.points[idx_curr];
        const Point &p2 = polygon.points[idx_next];
        result[idx_curr] = float(angle(p1 - p0, p2 - p1));
 
        // increase idx_curr by one
        float curr_distance = lengths[idx_curr];
        idx_curr++;
        distance_to_prev += curr_distance;
        distance_to_next -= curr_distance;
    }
 
    return result;
}

References Slic3r::angle(), calculate_polygon_angles_at_vertices(), Slic3r::next_idx_modulo(), Slic3r::MultiPoint::points, Slic3r::prev_idx_modulo(), and Slic3r::MultiPoint::size().

Referenced by calculate_polygon_angles_at_vertices(), and process_perimeter_polygon().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_angle_penalty()

float Slic3r::SeamPlacerImpl::compute_angle_penalty

(

float

ccw_angle

)

                                             {
    // This function is used:
    // ((ℯ^(((1)/(x^(2)*3+1)))-1)/(ℯ-1))*1+((1)/(2+ℯ^(-x)))
    // looks scary, but it is gaussian combined with sigmoid,
    // so that concave points have much smaller penalty over convex ones
    // https://github.com/prusa3d/PrusaSlicer/tree/master/doc/seam_placement/corner_penalty_function.png
    return gauss(ccw_angle, 0.0f, 1.0f, 3.0f) +
            1.0f / (2 + std::exp(-ccw_angle));
}

References gauss().

Referenced by Slic3r::SeamPlacerImpl::SeamComparator::is_first_not_much_worse().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_global_occlusion()

void Slic3r::SeamPlacerImpl::compute_global_occlusion	(	GlobalModelInfo &	result,
		const PrintObject *	po,
		std::function< void(void)>	throw_if_canceled
	)

                                                   {
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: gather occlusion meshes: start";
    auto obj_transform = po->trafo_centered();
    indexed_triangle_set triangle_set;
    indexed_triangle_set negative_volumes_set;
    //add all parts
    for (const ModelVolume *model_volume : po->model_object()->volumes) {
        if (model_volume->type() == ModelVolumeType::MODEL_PART
                || model_volume->type() == ModelVolumeType::NEGATIVE_VOLUME) {
            auto model_transformation = model_volume->get_matrix();
            indexed_triangle_set model_its = model_volume->mesh().its;
            its_transform(model_its, model_transformation);
            if (model_volume->type() == ModelVolumeType::MODEL_PART) {
                its_merge(triangle_set, model_its);
            } else {
                its_merge(negative_volumes_set, model_its);
            }
        }
    }
    throw_if_canceled();
 
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: gather occlusion meshes: end";
 
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: decimate: start";
    its_short_edge_collpase(triangle_set, SeamPlacer::fast_decimation_triangle_count_target);
    its_short_edge_collpase(negative_volumes_set, SeamPlacer::fast_decimation_triangle_count_target);
 
    size_t negative_volumes_start_index = triangle_set.indices.size();
    its_merge(triangle_set, negative_volumes_set);
    its_transform(triangle_set, obj_transform);
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: decimate: end";
 
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: Compute visibility sample points: start";
 
    result.mesh_samples = sample_its_uniform_parallel(SeamPlacer::raycasting_visibility_samples_count,
            triangle_set);
    result.mesh_samples_coordinate_functor = CoordinateFunctor(&result.mesh_samples.positions);
    result.mesh_samples_tree = KDTreeIndirect<3, float, CoordinateFunctor>(result.mesh_samples_coordinate_functor,
            result.mesh_samples.positions.size());
 
    // The following code determines search area for random visibility samples on the mesh when calculating visibility of each perimeter point
    // number of random samples in the given radius (area) is approximately poisson distribution
    // to compute ideal search radius (area), we use exponential distribution (complementary distr to poisson)
    // parameters of exponential distribution to compute area that will have with probability="probability" more than given number of samples="samples"
    float probability = 0.9f;
    float samples = 4;
    float density = SeamPlacer::raycasting_visibility_samples_count / result.mesh_samples.total_area;
    // exponential probability distrubtion function is : f(x) = P(X > x) = e^(l*x) where l is the rate parameter (computed as 1/u where u is mean value)
    // probability that sampled area A with S samples contains more than samples count:
    //  P(S > samples in A) = e^-(samples/(density*A));   express A:
    float search_area = samples / (-logf(probability) * density);
    float search_radius = sqrt(search_area / PI);
    result.mesh_samples_radius = search_radius;
 
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: Compute visiblity sample points: end";
    throw_if_canceled();
 
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: Mesh sample raidus: " << result.mesh_samples_radius;
 
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: build AABB tree: start";
    auto raycasting_tree = AABBTreeIndirect::build_aabb_tree_over_indexed_triangle_set(triangle_set.vertices,
            triangle_set.indices);
 
    throw_if_canceled();
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: build AABB tree: end";
    result.mesh_samples_visibility = raycast_visibility(raycasting_tree, triangle_set, result.mesh_samples,
            negative_volumes_start_index);
    throw_if_canceled();
#ifdef DEBUG_FILES
    result.debug_export(triangle_set);
#endif
}

References Slic3r::AABBTreeIndirect::build_aabb_tree_over_indexed_triangle_set(), compute_global_occlusion(), Slic3r::SeamPlacer::fast_decimation_triangle_count_target, indexed_triangle_set::indices, Slic3r::its_merge(), Slic3r::its_short_edge_collpase(), its_transform(), Slic3r::SeamPlacerImpl::GlobalModelInfo::mesh_samples, Slic3r::SeamPlacerImpl::GlobalModelInfo::mesh_samples_coordinate_functor, Slic3r::SeamPlacerImpl::GlobalModelInfo::mesh_samples_radius, Slic3r::SeamPlacerImpl::GlobalModelInfo::mesh_samples_tree, Slic3r::SeamPlacerImpl::GlobalModelInfo::mesh_samples_visibility, Slic3r::PrintObjectBase::model_object(), Slic3r::MODEL_PART, Slic3r::NEGATIVE_VOLUME, PI, Slic3r::TriangleSetSamples::positions, raycast_visibility(), Slic3r::SeamPlacer::raycasting_visibility_samples_count, Slic3r::sample_its_uniform_parallel(), sqrt(), Slic3r::TriangleSetSamples::total_area, Slic3r::PrintObject::trafo_centered(), indexed_triangle_set::vertices, and Slic3r::ModelObject::volumes.

Referenced by compute_global_occlusion().

Here is the call graph for this function:

Here is the caller graph for this function:

extract_perimeter_polygons()

Polygons Slic3r::SeamPlacerImpl::extract_perimeter_polygons	(	const Layer *	layer,
		std::vector< const LayerRegion * > &	corresponding_regions_out
	)

                                                                                                                  {
    Polygons polygons;
    for (const LayerRegion *layer_region : layer->regions()) {
        for (const ExtrusionEntity *ex_entity : layer_region->perimeters()) {
            if (ex_entity->is_collection()) { //collection of inner, outer, and overhang perimeters
                for (const ExtrusionEntity *perimeter : static_cast<const ExtrusionEntityCollection*>(ex_entity)->entities) {
                    ExtrusionRole role = perimeter->role();
                    if (perimeter->is_loop()) {
                        for (const ExtrusionPath &path : static_cast<const ExtrusionLoop*>(perimeter)->paths) {
                            if (path.role() == ExtrusionRole::ExternalPerimeter) {
                                role = ExtrusionRole::ExternalPerimeter;
                            }
                        }
                    }
 
                    if (role == ExtrusionRole::ExternalPerimeter) {
                        Points p;
                        perimeter->collect_points(p);
                        polygons.emplace_back(std::move(p));
                        corresponding_regions_out.push_back(layer_region);
                    }
                }
                if (polygons.empty()) {
                    Points p;
                    ex_entity->collect_points(p);
                    polygons.emplace_back(std::move(p));
                    corresponding_regions_out.push_back(layer_region);
                }
            } else {
                Points p;
                ex_entity->collect_points(p);
                polygons.emplace_back(std::move(p));
                corresponding_regions_out.push_back(layer_region);
            }
        }
    }
 
    if (polygons.empty()) { // If there are no perimeter polygons for whatever reason (disabled perimeters .. ) insert dummy point
        // it is easier than checking everywhere if the layer is not emtpy, no seam will be placed to this layer anyway
        polygons.emplace_back(Points{ { 0, 0 } });
        corresponding_regions_out.push_back(nullptr);
    }
 
    return polygons;
}

References Slic3r::ExtrusionRole::ExternalPerimeter, extract_perimeter_polygons(), and Slic3r::Layer::regions().

Referenced by extract_perimeter_polygons().

Here is the call graph for this function:

Here is the caller graph for this function:

find_previous_and_next_perimeter_point()

std::pair< size_t, size_t > Slic3r::SeamPlacerImpl::find_previous_and_next_perimeter_point	(	const std::vector< SeamCandidate > &	perimeter_points,
		size_t	point_index
	)

                            {
    const SeamCandidate &current = perimeter_points[point_index];
    int prev = point_index - 1; //for majority of points, it is true that neighbours lie behind and in front of them in the vector
    int next = point_index + 1;
 
    if (point_index == current.perimeter.start_index) {
        // if point_index is equal to start, it means that the previous neighbour is at the end
        prev = current.perimeter.end_index;
    }
 
    if (point_index == current.perimeter.end_index - 1) {
        // if point_index is equal to end, than next neighbour is at the start
        next = current.perimeter.start_index;
    }
 
    assert(prev >= 0);
    assert(next >= 0);
    return {size_t(prev),size_t(next)};
}

References Slic3r::SeamPlacerImpl::Perimeter::end_index, find_previous_and_next_perimeter_point(), Slic3r::SeamPlacerImpl::SeamCandidate::perimeter, and Slic3r::SeamPlacerImpl::Perimeter::start_index.

Referenced by find_previous_and_next_perimeter_point().

Here is the call graph for this function:

Here is the caller graph for this function:

gather_enforcers_blockers()

void Slic3r::SeamPlacerImpl::gather_enforcers_blockers	(	GlobalModelInfo &	result,
		const PrintObject *	po
	)

                                                                               {
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: build AABB trees for raycasting enforcers/blockers: start";
 
    auto obj_transform = po->trafo_centered();
 
    for (const ModelVolume *mv : po->model_object()->volumes) {
        if (mv->is_seam_painted()) {
            auto model_transformation = obj_transform * mv->get_matrix();
 
            indexed_triangle_set enforcers = mv->seam_facets.get_facets(*mv, EnforcerBlockerType::ENFORCER);
            its_transform(enforcers, model_transformation);
            its_merge(result.enforcers, enforcers);
 
            indexed_triangle_set blockers = mv->seam_facets.get_facets(*mv, EnforcerBlockerType::BLOCKER);
            its_transform(blockers, model_transformation);
            its_merge(result.blockers, blockers);
        }
    }
 
    result.enforcers_tree = AABBTreeIndirect::build_aabb_tree_over_indexed_triangle_set(result.enforcers.vertices,
            result.enforcers.indices);
    result.blockers_tree = AABBTreeIndirect::build_aabb_tree_over_indexed_triangle_set(result.blockers.vertices,
            result.blockers.indices);
 
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: build AABB trees for raycasting enforcers/blockers: end";
}

References Slic3r::BLOCKER, Slic3r::SeamPlacerImpl::GlobalModelInfo::blockers, Slic3r::SeamPlacerImpl::GlobalModelInfo::blockers_tree, Slic3r::AABBTreeIndirect::build_aabb_tree_over_indexed_triangle_set(), Slic3r::ENFORCER, Slic3r::SeamPlacerImpl::GlobalModelInfo::enforcers, Slic3r::SeamPlacerImpl::GlobalModelInfo::enforcers_tree, gather_enforcers_blockers(), indexed_triangle_set::indices, Slic3r::its_merge(), its_transform(), Slic3r::PrintObjectBase::model_object(), Slic3r::PrintObject::trafo_centered(), indexed_triangle_set::vertices, and Slic3r::ModelObject::volumes.

Referenced by gather_enforcers_blockers().

Here is the call graph for this function:

Here is the caller graph for this function:

gauss()

float Slic3r::SeamPlacerImpl::gauss	(	float	value,
		float	mean_x_coord,
		float	mean_value,
		float	falloff_speed
	)

                                                                                    {
    float shifted = value - mean_x_coord;
    float denominator = falloff_speed * shifted * shifted + 1.0f;
    float exponent = 1.0f / denominator;
    return mean_value * (std::exp(exponent) - 1.0f) / (std::exp(1.0f) - 1.0f);
}

Referenced by compute_angle_penalty().

Here is the caller graph for this function:

pick_nearest_seam_point_index()

size_t Slic3r::SeamPlacerImpl::pick_nearest_seam_point_index	(	const std::vector< SeamCandidate > &	perimeter_points,
		size_t	start_index,
		const Vec2f &	preffered_location
	)

                                         {
    size_t end_index = perimeter_points[start_index].perimeter.end_index;
    SeamComparator comparator { spNearest };
 
    size_t seam_index = start_index;
    for (size_t index = start_index; index < end_index; ++index) {
        if (comparator.is_first_better(perimeter_points[index], perimeter_points[seam_index], preffered_location)) {
            seam_index = index;
        }
    }
    return seam_index;
}

References pick_nearest_seam_point_index(), and Slic3r::spNearest.

Referenced by pick_nearest_seam_point_index().

Here is the call graph for this function:

Here is the caller graph for this function:

pick_random_seam_point()

void Slic3r::SeamPlacerImpl::pick_random_seam_point	(	const std::vector< SeamCandidate > &	perimeter_points,
		size_t	start_index
	)

                                                                                                  {
    SeamComparator comparator { spRandom };
 
    // algorithm keeps a list of viable points and their lengths. If it finds a point
    // that is much better than the viable_example_index (e.g. better type, no overhang; see is_first_not_much_worse)
    // then it throws away stored lists and starts from start
    // in the end, the list should contain points with same type (Enforced > Neutral > Blocked) and also only those which are not
    // big overhang.
    size_t viable_example_index = start_index;
    size_t end_index = perimeter_points[start_index].perimeter.end_index;
    struct Viable {
        // Candidate seam point index.
        size_t index;
        float edge_length;
        Vec3f edge;
    };
    std::vector<Viable> viables;
 
    const Vec3f pseudornd_seed = perimeter_points[viable_example_index].position;
    float rand = std::abs(sin(pseudornd_seed.dot(Vec3f(12.9898f,78.233f, 133.3333f))) * 43758.5453f);
    rand = rand - (int) rand;
 
    for (size_t index = start_index; index < end_index; ++index) {
        if (comparator.are_similar(perimeter_points[index], perimeter_points[viable_example_index])) {
            // index ok, push info into viables
            Vec3f edge_to_next { perimeter_points[index == end_index - 1 ? start_index : index + 1].position
                    - perimeter_points[index].position };
            float dist_to_next = edge_to_next.norm();
            viables.push_back( { index, dist_to_next, edge_to_next });
        } else if (comparator.is_first_not_much_worse(perimeter_points[viable_example_index],
                perimeter_points[index])) {
            // index is worse then viable_example_index, skip this point
        } else {
            // index is better than viable example index, update example, clear gathered info, start again
            // clear up all gathered info, start from scratch, update example index
            viable_example_index = index;
            viables.clear();
 
            Vec3f edge_to_next = (perimeter_points[index == end_index - 1 ? start_index : index + 1].position
                    - perimeter_points[index].position);
            float dist_to_next = edge_to_next.norm();
            viables.push_back( { index, dist_to_next, edge_to_next });
        }
    }
 
    // now pick random point from the stored options
    float len_sum = std::accumulate(viables.begin(), viables.end(), 0.0f, [](const float acc, const Viable &v) {
        return acc + v.edge_length;
    });
    float picked_len = len_sum * rand;
 
    size_t point_idx = 0;
    while (picked_len - viables[point_idx].edge_length > 0) {
        picked_len = picked_len - viables[point_idx].edge_length;
        point_idx++;
    }
 
    Perimeter &perimeter = perimeter_points[start_index].perimeter;
    perimeter.seam_index = viables[point_idx].index;
    perimeter.final_seam_position = perimeter_points[perimeter.seam_index].position
            + viables[point_idx].edge.normalized() * picked_len;
    perimeter.finalized = true;
}

References Slic3r::SeamPlacerImpl::Perimeter::final_seam_position, Slic3r::SeamPlacerImpl::Perimeter::finalized, pick_random_seam_point(), Slic3r::SeamPlacerImpl::Perimeter::seam_index, sin(), and Slic3r::spRandom.

Referenced by pick_random_seam_point().

Here is the call graph for this function:

Here is the caller graph for this function:

pick_seam_point()

void Slic3r::SeamPlacerImpl::pick_seam_point	(	std::vector< SeamCandidate > &	perimeter_points,
		size_t	start_index,
		const SeamComparator &	comparator
	)

                                          {
    size_t end_index = perimeter_points[start_index].perimeter.end_index;
 
    size_t seam_index = start_index;
    for (size_t index = start_index; index < end_index; ++index) {
        if (comparator.is_first_better(perimeter_points[index], perimeter_points[seam_index])) {
            seam_index = index;
        }
    }
    perimeter_points[start_index].perimeter.seam_index = seam_index;
}

References Slic3r::SeamPlacerImpl::SeamComparator::is_first_better(), and pick_seam_point().

Referenced by pick_seam_point().

Here is the call graph for this function:

Here is the caller graph for this function:

process_perimeter_polygon()

void Slic3r::SeamPlacerImpl::process_perimeter_polygon	(	const Polygon &	orig_polygon,
		float	z_coord,
		const LayerRegion *	region,
		const GlobalModelInfo &	global_model_info,
		PrintObjectSeamData::LayerSeams &	result
	)

                                                                                         {
    if (orig_polygon.size() == 0) {
        return;
    }
    Polygon polygon = orig_polygon;
    bool was_clockwise = polygon.make_counter_clockwise();
    float angle_arm_len = region != nullptr ? region->flow(FlowRole::frExternalPerimeter).nozzle_diameter() : 0.5f;
 
    std::vector<float> lengths { };
    for (size_t point_idx = 0; point_idx < polygon.size() - 1; ++point_idx) {
        lengths.push_back((unscale(polygon[point_idx]) - unscale(polygon[point_idx + 1])).norm());
    }
    lengths.push_back(std::max((unscale(polygon[0]) - unscale(polygon[polygon.size() - 1])).norm(), 0.1));
    std::vector<float> polygon_angles = calculate_polygon_angles_at_vertices(polygon, lengths,
            angle_arm_len);
 
    result.perimeters.push_back( { });
    Perimeter &perimeter = result.perimeters.back();
 
    std::queue<Vec3f> orig_polygon_points { };
    for (size_t index = 0; index < polygon.size(); ++index) {
        Vec2f unscaled_p = unscale(polygon[index]).cast<float>();
        orig_polygon_points.emplace(unscaled_p.x(), unscaled_p.y(), z_coord);
    }
    Vec3f first = orig_polygon_points.front();
    std::queue<Vec3f> oversampled_points { };
    size_t orig_angle_index = 0;
    perimeter.start_index = result.points.size();
    perimeter.flow_width = region != nullptr ? region->flow(FlowRole::frExternalPerimeter).width() : 0.0f;
    bool some_point_enforced = false;
    while (!orig_polygon_points.empty() || !oversampled_points.empty()) {
        EnforcedBlockedSeamPoint type = EnforcedBlockedSeamPoint::Neutral;
        Vec3f position;
        float local_ccw_angle = 0;
        bool orig_point = false;
        if (!oversampled_points.empty()) {
            position = oversampled_points.front();
            oversampled_points.pop();
        } else {
            position = orig_polygon_points.front();
            orig_polygon_points.pop();
            local_ccw_angle = was_clockwise ? -polygon_angles[orig_angle_index] : polygon_angles[orig_angle_index];
            orig_angle_index++;
            orig_point = true;
        }
 
        if (global_model_info.is_enforced(position, perimeter.flow_width)) {
            type = EnforcedBlockedSeamPoint::Enforced;
        }
 
        if (global_model_info.is_blocked(position, perimeter.flow_width)) {
            type = EnforcedBlockedSeamPoint::Blocked;
        }
        some_point_enforced = some_point_enforced || type == EnforcedBlockedSeamPoint::Enforced;
 
        if (orig_point) {
            Vec3f pos_of_next = orig_polygon_points.empty() ? first : orig_polygon_points.front();
            float distance_to_next = (position - pos_of_next).norm();
            if (global_model_info.is_enforced(position, distance_to_next)) {
                Vec3f vec_to_next = (pos_of_next - position).normalized();
                float step_size = SeamPlacer::enforcer_oversampling_distance;
                float step = step_size;
                while (step < distance_to_next) {
                    oversampled_points.push(position + vec_to_next * step);
                    step += step_size;
                }
            }
        }
 
        result.points.emplace_back(position, perimeter, local_ccw_angle, type);
    }
 
    perimeter.end_index = result.points.size();
 
    if (some_point_enforced) {
        // We will patches of enforced points (patch: continuous section of enforced points), choose
        // the longest patch, and select the middle point or sharp point (depending on the angle)
        // this point will have high priority on this perimeter
        size_t perimeter_size = perimeter.end_index - perimeter.start_index;
        const auto next_index = [&](size_t idx) {
            return perimeter.start_index + Slic3r::next_idx_modulo(idx - perimeter.start_index, perimeter_size);
        };
 
        std::vector<size_t> patches_starts_ends;
        for (size_t i = perimeter.start_index; i < perimeter.end_index; ++i) {
            if (result.points[i].type != EnforcedBlockedSeamPoint::Enforced &&
                    result.points[next_index(i)].type == EnforcedBlockedSeamPoint::Enforced) {
                patches_starts_ends.push_back(next_index(i));
            }
            if (result.points[i].type == EnforcedBlockedSeamPoint::Enforced &&
                    result.points[next_index(i)].type != EnforcedBlockedSeamPoint::Enforced) {
                patches_starts_ends.push_back(next_index(i));
            }
        }
        //if patches_starts_ends are empty, it means that the whole perimeter is enforced.. don't do anything in that case
        if (!patches_starts_ends.empty()) {
            //if the first point in the patches is not enforced, it marks a patch end. in that case, put it to the end and start on next
            // to simplify the processing
            assert(patches_starts_ends.size() % 2 == 0);
            bool start_on_second = false;
            if (result.points[patches_starts_ends[0]].type != EnforcedBlockedSeamPoint::Enforced) {
                start_on_second = true;
                patches_starts_ends.push_back(patches_starts_ends[0]);
            }
            //now pick the longest patch
            std::pair<size_t, size_t> longest_patch { 0, 0 };
            auto patch_len = [perimeter_size](const std::pair<size_t, size_t> &start_end) {
                if (start_end.second < start_end.first) {
                    return start_end.first + (perimeter_size - start_end.second);
                } else {
                    return start_end.second - start_end.first;
                }
            };
            for (size_t patch_idx = start_on_second ? 1 : 0; patch_idx < patches_starts_ends.size(); patch_idx += 2) {
                std::pair<size_t, size_t> current_patch { patches_starts_ends[patch_idx], patches_starts_ends[patch_idx
                        + 1] };
                if (patch_len(longest_patch) < patch_len(current_patch)) {
                    longest_patch = current_patch;
                }
            }
            std::vector<size_t> viable_points_indices;
            std::vector<size_t> large_angle_points_indices;
            for (size_t point_idx = longest_patch.first; point_idx != longest_patch.second;
                    point_idx = next_index(point_idx)) {
                viable_points_indices.push_back(point_idx);
                if (std::abs(result.points[point_idx].local_ccw_angle)
                        > SeamPlacer::sharp_angle_snapping_threshold) {
                    large_angle_points_indices.push_back(point_idx);
                }
            }
            assert(viable_points_indices.size() > 0);
            if (large_angle_points_indices.empty()) {
                size_t central_idx = viable_points_indices[viable_points_indices.size() / 2];
                result.points[central_idx].central_enforcer = true;
            } else {
                size_t central_idx = large_angle_points_indices.size() / 2;
                result.points[large_angle_points_indices[central_idx]].central_enforcer = true;
            }
        }
    }
 
}

References calculate_polygon_angles_at_vertices(), Slic3r::SeamPlacerImpl::Perimeter::end_index, Slic3r::SeamPlacer::enforcer_oversampling_distance, Slic3r::LayerRegion::flow(), Slic3r::SeamPlacerImpl::Perimeter::flow_width, Slic3r::frExternalPerimeter, Slic3r::SeamPlacerImpl::GlobalModelInfo::is_blocked(), Slic3r::SeamPlacerImpl::GlobalModelInfo::is_enforced(), Slic3r::Polygon::make_counter_clockwise(), Slic3r::next_idx_modulo(), Slic3r::Flow::nozzle_diameter(), Slic3r::PrintObjectSeamData::LayerSeams::perimeters, Slic3r::PrintObjectSeamData::LayerSeams::points, process_perimeter_polygon(), Slic3r::SeamPlacer::sharp_angle_snapping_threshold, Slic3r::MultiPoint::size(), Slic3r::SeamPlacerImpl::Perimeter::start_index, Slic3r::unscale(), and Slic3r::Flow::width().

Referenced by process_perimeter_polygon().

Here is the call graph for this function:

Here is the caller graph for this function:

raycast_visibility()

std::vector< float > Slic3r::SeamPlacerImpl::raycast_visibility	(	const AABBTreeIndirect::Tree< 3, float > &	raycasting_tree,
		const indexed_triangle_set &	triangles,
		const TriangleSetSamples &	samples,
		size_t	negative_volumes_start_index
	)

                                             {
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: raycast visibility of " << samples.positions.size() << " samples over " << triangles.indices.size()
            << " triangles: end";
 
    //prepare uniform samples of a hemisphere
    float step_size = 1.0f / SeamPlacer::sqr_rays_per_sample_point;
    std::vector<Vec3f> precomputed_sample_directions(
            SeamPlacer::sqr_rays_per_sample_point * SeamPlacer::sqr_rays_per_sample_point);
    for (size_t x_idx = 0; x_idx < SeamPlacer::sqr_rays_per_sample_point; ++x_idx) {
        float sample_x = x_idx * step_size + step_size / 2.0;
        for (size_t y_idx = 0; y_idx < SeamPlacer::sqr_rays_per_sample_point; ++y_idx) {
            size_t dir_index = x_idx * SeamPlacer::sqr_rays_per_sample_point + y_idx;
            float sample_y = y_idx * step_size + step_size / 2.0;
            precomputed_sample_directions[dir_index] = sample_hemisphere_uniform( { sample_x, sample_y });
        }
    }
 
    bool model_contains_negative_parts = negative_volumes_start_index < triangles.indices.size();
 
    std::vector<float> result(samples.positions.size());
    tbb::parallel_for(tbb::blocked_range<size_t>(0, result.size()),
            [&triangles, &precomputed_sample_directions, model_contains_negative_parts, negative_volumes_start_index,
                    &raycasting_tree, &result, &samples](tbb::blocked_range<size_t> r) {
                // Maintaining hits memory outside of the loop, so it does not have to be reallocated for each query.
                std::vector<igl::Hit> hits;
                for (size_t s_idx = r.begin(); s_idx < r.end(); ++s_idx) {
                    result[s_idx] = 1.0f;
                    constexpr float decrease_step = 1.0f
                            / (SeamPlacer::sqr_rays_per_sample_point * SeamPlacer::sqr_rays_per_sample_point);
 
                    const Vec3f &center = samples.positions[s_idx];
                    const Vec3f &normal = samples.normals[s_idx];
                    // apply the local direction via Frame struct - the local_dir is with respect to +Z being forward
                    Frame f;
                    f.set_from_z(normal);
 
                    for (const auto &dir : precomputed_sample_directions) {
                        Vec3f final_ray_dir = (f.to_world(dir));
                        if (!model_contains_negative_parts) {
                            igl::Hit hitpoint;
                            // FIXME: This AABBTTreeIndirect query will not compile for float ray origin and
                            // direction.
                            Vec3d final_ray_dir_d = final_ray_dir.cast<double>();
                            Vec3d ray_origin_d = (center + normal * 0.01f).cast<double>(); // start above surface.
                            bool hit = AABBTreeIndirect::intersect_ray_first_hit(triangles.vertices,
                                    triangles.indices, raycasting_tree, ray_origin_d, final_ray_dir_d, hitpoint);
                            if (hit && its_face_normal(triangles, hitpoint.id).dot(final_ray_dir) <= 0) {
                                result[s_idx] -= decrease_step;
                            }
                        } else { //TODO improve logic for order based boolean operations - consider order of volumes
                            bool casting_from_negative_volume = samples.triangle_indices[s_idx]
                                    >= negative_volumes_start_index;
 
                            Vec3d ray_origin_d = (center + normal * 0.01f).cast<double>(); // start above surface.
                            if (casting_from_negative_volume) { // if casting from negative volume face, invert direction, change start pos
                                final_ray_dir = -1.0 * final_ray_dir;
                                ray_origin_d = (center - normal * 0.01f).cast<double>();
                            }
                            Vec3d final_ray_dir_d = final_ray_dir.cast<double>();
                            bool some_hit = AABBTreeIndirect::intersect_ray_all_hits(triangles.vertices,
                                    triangles.indices, raycasting_tree,
                                    ray_origin_d, final_ray_dir_d, hits);
                            if (some_hit) {
                                int counter = 0;
                                // NOTE: iterating in reverse, from the last hit for one simple reason: We know the state of the ray at that point;
                                //  It cannot be inside model, and it cannot be inside negative volume
                                for (int hit_index = int(hits.size()) - 1; hit_index >= 0; --hit_index) {
                                    Vec3f face_normal = its_face_normal(triangles, hits[hit_index].id);
                                    if (hits[hit_index].id >= int(negative_volumes_start_index)) { //negative volume hit
                                        counter -= sgn(face_normal.dot(final_ray_dir)); // if volume face aligns with ray dir, we are leaving negative space
                                        // which in reverse hit analysis means, that we are entering negative space :) and vice versa
                                    } else {
                                        counter += sgn(face_normal.dot(final_ray_dir));
                                    }
                                }
                                if (counter == 0) {
                                    result[s_idx] -= decrease_step;
                                }
                            }
                        }
                    }
                }
            });
 
    BOOST_LOG_TRIVIAL(debug)
    << "SeamPlacer: raycast visibility of " << samples.positions.size() << " samples over " << triangles.indices.size()
            << " triangles: end";
 
    return result;
}

References indexed_triangle_set::indices, Slic3r::TriangleSetSamples::positions, sample_hemisphere_uniform(), and Slic3r::SeamPlacer::sqr_rays_per_sample_point.

Referenced by compute_global_occlusion().

Here is the call graph for this function:

Here is the caller graph for this function:

sample_hemisphere_uniform()

Vec3f Slic3r::SeamPlacerImpl::sample_hemisphere_uniform

(

const Vec2f &

samples

)

                                                      {
    float term1 = 2.0f * float(PI) * samples.x();
    float term2 = 2.0f * sqrt(samples.y() - samples.y() * samples.y());
    return {cos(term1) * term2, sin(term1) * term2,
        abs(1.0f - 2.0f * samples.y())};
}

References cos(), PI, sin(), and sqrt().

Referenced by raycast_visibility().

Here is the call graph for this function:

Here is the caller graph for this function:

sample_power_cosine_hemisphere()

Vec3f Slic3r::SeamPlacerImpl::sample_power_cosine_hemisphere	(	const Vec2f &	samples,
		float	power
	)

                                                                        {
    float term1 = 2.f * float(PI) * samples.x();
    float term2 = pow(samples.y(), 1.f / (power + 1.f));
    float term3 = sqrt(1.f - term2 * term2);
 
    return Vec3f(cos(term1) * term3, sin(term1) * term3, term2);
}

References cos(), PI, sin(), and sqrt().

Here is the call graph for this function:

sample_sphere_uniform()

Vec3f Slic3r::SeamPlacerImpl::sample_sphere_uniform

(

const Vec2f &

samples

)

                                                  {
    float term1 = 2.0f * float(PI) * samples.x();
    float term2 = 2.0f * sqrt(samples.y() - samples.y() * samples.y());
    return {cos(term1) * term2, sin(term1) * term2,
        1.0f - 2.0f * samples.y()};
}

References cos(), PI, sin(), and sqrt().

Here is the call graph for this function:

sgn()

template<typename T >

int Slic3r::SeamPlacerImpl::sgn

(

T

val

)

                                    {
    return int(T(0) < val) - int(val < T(0));
}