Slic3r::AABBTreeLines::detail Namespace Reference

Classes
struct	IndexedLinesDistancer

Functions
template<typename LineType, typename TreeType, typename VectorType, int coordinate>
std::tuple< int, int >	coordinate_aligned_ray_hit_count (size_t node_idx, const TreeType &tree, const std::vector< LineType > &lines, const VectorType &ray_origin)
template<typename LineType, typename TreeType, typename VectorType>
std::vector< std::pair< VectorType, size_t > >	get_intersections_with_line (size_t node_idx, const TreeType &tree, const std::vector< LineType > &lines, const LineType &line, const typename TreeType::BoundingBox &line_bb)

Function Documentation

coordinate_aligned_ray_hit_count()

template<typename LineType, typename TreeType, typename VectorType, int coordinate>

std::tuple< int, int > Slic3r::AABBTreeLines::detail::coordinate_aligned_ray_hit_count ( size_t node_idx, const TreeType & tree, const std::vector< LineType > & lines, const VectorType & ray_origin )

inline

        {
            static constexpr int other_coordinate = (coordinate + 1) % 2;
            using Scalar = typename LineType::Scalar;
            using Floating = typename std::conditional<std::is_floating_point<Scalar>::value, Scalar, double>::type;
            const auto& node = tree.node(node_idx);
            assert(node.is_valid());
            if (node.is_leaf()) {
                const LineType& line = lines[node.idx];
                if (ray_origin[other_coordinate] < std::min(line.a[other_coordinate], line.b[other_coordinate]) || ray_origin[other_coordinate] >= std::max(line.a[other_coordinate], line.b[other_coordinate])) {
                    // the second inequality is nonsharp for a reason
                    //  without it, we may count contour border twice when the lines meet exactly at the spot of intersection. this prevents is
                    return { 0, 0 };
                }
 
                Scalar line_max = std::max(line.a[coordinate], line.b[coordinate]);
                Scalar line_min = std::min(line.a[coordinate], line.b[coordinate]);
                if (ray_origin[coordinate] > line_max) {
                    return { 1, 0 };
                } else if (ray_origin[coordinate] < line_min) {
                    return { 0, 1 };
                } else {
                    // find intersection of ray with line
                    //  that is when ( line.a + t * (line.b - line.a) )[other_coordinate] == ray_origin[other_coordinate]
                    //  t = ray_origin[oc] - line.a[oc] / (line.b[oc] - line.a[oc]);
                    //  then we want to get value of intersection[ coordinate]
                    //  val_c = line.a[c] + t * (line.b[c] - line.a[c]);
                    //  Note that ray and line may overlap, when  (line.b[oc] - line.a[oc]) is zero
                    //  In that case, we return negative number
                    Floating distance_oc = line.b[other_coordinate] - line.a[other_coordinate];
                    Floating t = (ray_origin[other_coordinate] - line.a[other_coordinate]) / distance_oc;
                    Floating val_c = line.a[coordinate] + t * (line.b[coordinate] - line.a[coordinate]);
                    if (ray_origin[coordinate] > val_c) {
                        return { 1, 0 };
                    } else if (ray_origin[coordinate] < val_c) {
                        return { 0, 1 };
                    } else { // ray origin is on boundary
                        return { -1, -1 };
                    }
                }
            } else {
                int intersections_above = 0;
                int intersections_below = 0;
                size_t left_node_idx = node_idx * 2 + 1;
                size_t right_node_idx = left_node_idx + 1;
                const auto& node_left = tree.node(left_node_idx);
                const auto& node_right = tree.node(right_node_idx);
                assert(node_left.is_valid());
                assert(node_right.is_valid());
 
                if (node_left.bbox.min()[other_coordinate] <= ray_origin[other_coordinate] && node_left.bbox.max()[other_coordinate] >= ray_origin[other_coordinate]) {
                    auto [above, below] = coordinate_aligned_ray_hit_count<LineType, TreeType, VectorType, coordinate>(left_node_idx, tree, lines,
                        ray_origin);
                    if (above < 0 || below < 0)
                        return { -1, -1 };
                    intersections_above += above;
                    intersections_below += below;
                }
 
                if (node_right.bbox.min()[other_coordinate] <= ray_origin[other_coordinate] && node_right.bbox.max()[other_coordinate] >= ray_origin[other_coordinate]) {
                    auto [above, below] = coordinate_aligned_ray_hit_count<LineType, TreeType, VectorType, coordinate>(right_node_idx, tree, lines,
                        ray_origin);
                    if (above < 0 || below < 0)
                        return { -1, -1 };
                    intersections_above += above;
                    intersections_below += below;
                }
                return { intersections_above, intersections_below };
            }
        }

References coordinate_aligned_ray_hit_count().

Referenced by coordinate_aligned_ray_hit_count(), and Slic3r::AABBTreeLines::point_outside_closed_contours().

Here is the call graph for this function:

Here is the caller graph for this function:

get_intersections_with_line()

template<typename LineType, typename TreeType, typename VectorType>

std::vector< std::pair< VectorType, size_t > > Slic3r::AABBTreeLines::detail::get_intersections_with_line ( size_t node_idx, const TreeType & tree, const std::vector< LineType > & lines, const LineType & line, const typename TreeType::BoundingBox & line_bb )

inline

        {
            const auto& node = tree.node(node_idx);
            assert(node.is_valid());
            if (node.is_leaf()) {
                VectorType intersection_pt;
                if (line_alg::intersection(line, lines[node.idx], &intersection_pt)) {
                    return { std::pair<VectorType, size_t>(intersection_pt, node.idx) };
                } else {
                    return {};
                }
            } else {
                size_t left_node_idx = node_idx * 2 + 1;
                size_t right_node_idx = left_node_idx + 1;
                const auto& node_left = tree.node(left_node_idx);
                const auto& node_right = tree.node(right_node_idx);
                assert(node_left.is_valid());
                assert(node_right.is_valid());
 
                std::vector<std::pair<VectorType, size_t>> result;
 
                if (node_left.bbox.intersects(line_bb)) {
                    std::vector<std::pair<VectorType, size_t>> intersections = get_intersections_with_line<LineType, TreeType, VectorType>(left_node_idx, tree, lines, line, line_bb);
                    result.insert(result.end(), intersections.begin(), intersections.end());
                }
 
                if (node_right.bbox.intersects(line_bb)) {
                    std::vector<std::pair<VectorType, size_t>> intersections = get_intersections_with_line<LineType, TreeType, VectorType>(right_node_idx, tree, lines, line, line_bb);
                    result.insert(result.end(), intersections.begin(), intersections.end());
                }
 
                return result;
            }
        }

References get_intersections_with_line(), and Slic3r::line_alg::intersection().

Referenced by get_intersections_with_line(), and Slic3r::AABBTreeLines::get_intersections_with_line().

Here is the call graph for this function:

Here is the caller graph for this function: