<commit_before>//Copyright (c) 2017 <NAME>.
//CuraEngine is released under the terms of the AGPLv3 or higher.

#include "utils/intpoint.h" //To normalize vectors.
#include "utils/math.h" //For round_up_divide and PI.
#include "utils/MinimumSpanningTree.h" //For connecting the correct nodes together to form an efficient tree.
#include "utils/polygonUtils.h" //For moveInside.

#include "TreeSupport.h"

#define SQRT_2 1.4142135623730950488 //Square root of 2.
#define CIRCLE_RESOLUTION 10 //The number of vertices in each circle.

namespace cura
{

TreeSupport::TreeSupport()
{
}

void TreeSupport::generateSupportAreas(SliceDataStorage& storage)
{
    std::vector<std::unordered_set<Point>> contact_points;
    std::vector<std::unordered_map<Point, Node>> contact_nodes;
    contact_points.reserve(storage.support.supportLayers.size());
    contact_nodes.reserve(storage.support.supportLayers.size());
    for (size_t layer_nr = 0; layer_nr < storage.support.supportLayers.size(); layer_nr++) //Generate empty layers to store the points in.
    {
        contact_points.emplace_back();
        contact_nodes.emplace_back();
    }
    for (SliceMeshStorage& mesh : storage.meshes)
    {
        if (!mesh.getSettingBoolean("support_tree_enable"))
        {
            return;
        }
        generateContactPoints(mesh, contact_points, contact_nodes);
    }

    //Generate areas that have to be avoided.
    const coord_t layer_height = storage.getSettingInMicrons("layer_height");
    const double angle = storage.getSettingInAngleRadians("support_tree_angle");
    const coord_t maximum_move_distance = tan(angle) * layer_height;
    const coord_t branch_radius = storage.getSettingInMicrons("support_tree_branch_diameter") >> 1;
    std::vector<Polygons> model_collision; //Areas that have to be avoided by the tips of the branches.
    std::vector<Polygons> model_collision_branch_radius; //Areas that have to be avoided by the base of the branches (with branch diameter added for a better approximation).
    const coord_t xy_distance = storage.getSettingInMicrons("support_xy_distance");
    constexpr bool include_helper_parts = false;
    model_collision.push_back(storage.getLayerOutlines(0, include_helper_parts).offset(xy_distance, ClipperLib::JoinType::jtRound));
    model_collision_branch_radius.push_back(model_collision[0].offset(branch_radius, ClipperLib::JoinType::jtRound));
    //TODO: If allowing support to rest on model, these need to be just the model outlines.
    for (size_t layer_nr = 1; layer_nr < storage.print_layer_count; layer_nr++)
    {
        //Generate an area above the current layer where you'd still collide with the current layer if you were to move with at most maximum_move_distance.
        model_collision.push_back(model_collision[layer_nr - 1].offset(-maximum_move_distance, ClipperLib::JoinType::jtRound)); //Inset previous layer with maximum_move_distance to allow some movement.
        model_collision[layer_nr] = model_collision[layer_nr].unionPolygons(storage.getLayerOutlines(layer_nr, include_helper_parts).offset(xy_distance, ClipperLib::JoinType::jtRound)); //Add current layer's collision to that.
        model_collision_branch_radius.push_back(model_collision[layer_nr].offset(branch_radius, ClipperLib::JoinType::jtRound));
    }

    //Use Minimum Spanning Tree to connect the points on each layer and move them while dropping them down.
    const coord_t line_width = storage.getSettingInMicrons("support_line_width");
    const double diameter_angle_scale_factor = sin(storage.getSettingInAngleRadians("support_tree_branch_diameter_angle")) * layer_height / branch_radius; //Scale factor per layer to produce the desired angle.
    const size_t tip_layers = branch_radius / layer_height; //The number of layers to be shrinking the circle to create a tip. This produces a 45 degree angle.
    for (size_t layer_nr = contact_points.size() - 1; layer_nr > 0; layer_nr--) //Skip layer 0, since we can't drop down the vertices there.
    {
        MinimumSpanningTree mst(contact_points[layer_nr]);
        for (Point vertex : contact_points[layer_nr])
        {
            const Node node = contact_nodes[layer_nr][vertex];
            Point next_layer_vertex = vertex;
            std::vector<Point> neighbours = mst.adjacentNodes(vertex);
            if (!neighbours.empty()) //Need to move towards the neighbours.
            {
                Point sum_direction(0, 0);
                for (Point neighbour : neighbours)
                {
                    sum_direction += neighbour - vertex;
                }
                Point motion = normal(sum_direction, maximum_move_distance);
                if (neighbours.size() == 1 && vSize2(sum_direction) < maximum_move_distance * maximum_move_distance)
                {
                    if (mst.adjacentNodes(neighbours[0]).size() == 1) //We just have two nodes left!
                    {
                        next_layer_vertex += motion / 2;
                    }
                    else //This is a leaf that's about to collapse. Leave it out on the next layer.
                    {
                        contact_nodes[layer_nr - 1][neighbours[0]].distance_to_top = std::max(contact_nodes[layer_nr - 1][neighbours[0]].distance_to_top, node.distance_to_top);
                        contact_nodes[layer_nr - 1][neighbours[0]].support_roof_layers_below = std::max(contact_nodes[layer_nr - 1][neighbours[0]].support_roof_layers_below, node.support_roof_layers_below);
                        continue;
                    }
                }
                else
                {
                    next_layer_vertex += motion;
                }
            }

            //Avoid collisions.
            if (node.distance_to_top > tip_layers) //Main branch.
            {
                const coord_t branch_radius_node = branch_radius * node.distance_to_top * diameter_angle_scale_factor;
                PolygonUtils::moveOutside(model_collision_branch_radius[layer_nr - 1], next_layer_vertex, branch_radius_node, maximum_move_distance * maximum_move_distance);
            }
            else //Tip.
            {
                const coord_t branch_radius_node = branch_radius * node.distance_to_top / tip_layers;
                PolygonUtils::moveOutside(model_collision[layer_nr - 1], next_layer_vertex, branch_radius_node, maximum_move_distance * maximum_move_distance);
            }
            if (model_collision[layer_nr].inside(next_layer_vertex)) //We're stuck inside the model down there! Sadly, this branch will have to rest on the model.
            {
                continue;
            }
            contact_points[layer_nr - 1].insert(next_layer_vertex);
            contact_nodes[layer_nr - 1][next_layer_vertex].distance_to_top = node.distance_to_top + 1;
            contact_nodes[layer_nr - 1][next_layer_vertex].skin_direction = node.skin_direction;
            contact_nodes[layer_nr - 1][next_layer_vertex].support_roof_layers_below = node.support_roof_layers_below - 1;
        }
    }

    const unsigned int wall_count = storage.getSettingAsCount("support_tree_wall_count");
    Polygon branch_circle; //Pre-generate a circle with correct diameter so that we don't have to recompute those (co)sines every time.
    for (unsigned int i = 0; i < CIRCLE_RESOLUTION; i++)
    {
        const double angle = (double)i / CIRCLE_RESOLUTION * 2 * M_PI; //In radians.
        branch_circle.emplace_back(cos(angle) * branch_radius, sin(angle) * branch_radius);
    }
    const coord_t circle_side_length = 2 * branch_radius * sin(M_PI / CIRCLE_RESOLUTION); //Side length of a regular polygon.
    for (size_t layer_nr = 0; layer_nr < contact_points.size(); layer_nr++)
    {
        Polygons support_layer;
        Polygons& roof_layer = storage.support.supportLayers[layer_nr].support_roof;

        for (const Point point : contact_points[layer_nr])
        {
            const Node& node = contact_nodes[layer_nr][point];
            Polygon circle;
            const double scale = (double)(node.distance_to_top + 1) / tip_layers;
            for (Point corner : branch_circle)
            {
                if (node.distance_to_top < tip_layers) //We're in the tip.
                {
                    if (node.skin_direction)
                    {
                        corner = Point(corner.X * (0.5 + scale / 2) + corner.Y * (0.5 - scale / 2), corner.X * (0.5 - scale / 2) + corner.Y * (0.5 + scale / 2));
                    }
                    else
                    {
                        corner = Point(corner.X * (0.5 + scale / 2) - corner.Y * (0.5 - scale / 2), corner.X * (-0.5 + scale / 2) + corner.Y * (0.5 + scale / 2));
                    }
                }
                else
                {
                    corner *= 1 + (double)(node.distance_to_top - tip_layers) * diameter_angle_scale_factor;
                }
                circle.add(point + corner);
            }
            if (node.support_roof_layers_below >= 0)
            {
                roof_layer.add(circle);
            }
            else
            {
                support_layer.add(circle);
            }
        }
        support_layer = support_layer.unionPolygons();
        roof_layer = roof_layer.unionPolygons();
        support_layer = support_layer.difference(roof_layer);
        //We smooth this support as much as possible without altering single circles. So we remove any line less than the side length of those circles.
        const double diameter_angle_scale_factor_this_layer = (double)(storage.support.supportLayers.size() - layer_nr - tip_layers) * diameter_angle_scale_factor; //Maximum scale factor.
        support_layer.simplify(circle_side_length * (1 + diameter_angle_scale_factor_this_layer), line_width >> 2); //Deviate at most a quarter of a line so that the lines still stack properly.
        for (PolygonRef part : support_layer) //Convert every part into a PolygonsPart for the support.
        {
            PolygonsPart outline;
            outline.add(part);
            storage.support.supportLayers[layer_nr].support_infill_parts.emplace_back(outline, line_width, wall_count);
        }
        if (!storage.support.supportLayers[layer_nr].support_infill_parts.empty() || !storage.support.supportLayers[layer_nr].support_roof.empty())
        {
            storage.support.layer_nr_max_filled_layer = layer_nr;
        }
    }<commit_msg>Fix generating model collision areas with offset<commit_after>//Copyright (c) 2017 <NAME>.
//CuraEngine is released under the terms of the AGPLv3 or higher.

#include "utils/intpoint.h" //To normalize vectors.
#include "utils/math.h" //For round_up_divide and PI.
#include "utils/MinimumSpanningTree.h" //For connecting the correct nodes together to form an efficient tree.
#include "utils/polygonUtils.h" //For moveInside.

#include "TreeSupport.h"

#define SQRT_2 1.4142135623730950488 //Square root of 2.
#define CIRCLE_RESOLUTION 10 //The number of vertices in each circle.

namespace cura
{

TreeSupport::TreeSupport()
{
}

void TreeSupport::generateSupportAreas(SliceDataStorage& storage)
{
    std::vector<std::unordered_set<Point>> contact_points;
    std::vector<std::unordered_map<Point, Node>> contact_nodes;
    contact_points.reserve(storage.support.supportLayers.size());
    contact_nodes.reserve(storage.support.supportLayers.size());
    for (size_t layer_nr = 0; layer_nr < storage.support.supportLayers.size(); layer_nr++) //Generate empty layers to store the points in.
    {
        contact_points.emplace_back();
        contact_nodes.emplace_back();
    }
    for (SliceMeshStorage& mesh : storage.meshes)
    {
        if (!mesh.getSettingBoolean("support_tree_enable"))
        {
            return;
        }
        generateContactPoints(mesh, contact_points, contact_nodes);
    }

    //Generate areas that have to be avoided.
    const coord_t layer_height = storage.getSettingInMicrons("layer_height");
    const double angle = storage.getSettingInAngleRadians("support_tree_angle");
    const coord_t maximum_move_distance = tan(angle) * layer_height;
    const coord_t branch_radius = storage.getSettingInMicrons("support_tree_branch_diameter") >> 1;
    std::vector<Polygons> model_collision; //Areas that have to be avoided by the tips of the branches.
    std::vector<Polygons> model_collision_branch_radius; //Areas that have to be avoided by the base of the branches (with branch diameter added for a better approximation).
    const coord_t xy_distance = storage.getSettingInMicrons("support_xy_distance");
    constexpr bool include_helper_parts = false;
    model_collision.push_back(storage.getLayerOutlines(0, include_helper_parts).offset(xy_distance, ClipperLib::JoinType::jtRound));
    model_collision_branch_radius.push_back(model_collision[0].offset(branch_radius, ClipperLib::JoinType::jtRound));
    //TODO: If allowing support to rest on model, these need to be just the model outlines.
    for (size_t layer_nr = 1; layer_nr < storage.print_layer_count; layer_nr++)
    {
        //Generate an area above the current layer where you'd still collide with the current layer if you were to move with at most maximum_move_distance.
        model_collision.push_back(model_collision[layer_nr - 1].offset(-maximum_move_distance, ClipperLib::JoinType::jtRound)); //Inset previous layer with maximum_move_distance to allow some movement.
        model_collision[layer_nr] = model_collision[layer_nr].unionPolygons(storage.getLayerOutlines(layer_nr, include_helper_parts).offset(xy_distance, ClipperLib::JoinType::jtRound)); //Add current layer's collision to that.
        model_collision_branch_radius.push_back(model_collision_branch_radius[layer_nr - 1].offset(-maximum_move_distance, ClipperLib::JoinType::jtRound));
        model_collision_branch_radius[layer_nr] = model_collision_branch_radius[layer_nr].unionPolygons(storage.getLayerOutlines(layer_nr, include_helper_parts).offset(xy_distance + branch_radius, ClipperLib::JoinType::jtRound));
    }

    //Use Minimum Spanning Tree to connect the points on each layer and move them while dropping them down.
    const coord_t line_width = storage.getSettingInMicrons("support_line_width");
    const double diameter_angle_scale_factor = sin(storage.getSettingInAngleRadians("support_tree_branch_diameter_angle")) * layer_height / branch_radius; //Scale factor per layer to produce the desired angle.
    const size_t tip_layers = branch_radius / layer_height; //The number of layers to be shrinking the circle to create a tip. This produces a 45 degree angle.
    for (size_t layer_nr = contact_points.size() - 1; layer_nr > 0; layer_nr--) //Skip layer 0, since we can't drop down the vertices there.
    {
        MinimumSpanningTree mst(contact_points[layer_nr]);
        for (Point vertex : contact_points[layer_nr])
        {
            const Node node = contact_nodes[layer_nr][vertex];
            Point next_layer_vertex = vertex;
            std::vector<Point> neighbours = mst.adjacentNodes(vertex);
            if (!neighbours.empty()) //Need to move towards the neighbours.
            {
                Point sum_direction(0, 0);
                for (Point neighbour : neighbours)
                {
                    sum_direction += neighbour - vertex;
                }
                Point motion = normal(sum_direction, maximum_move_distance);
                if (neighbours.size() == 1 && vSize2(sum_direction) < maximum_move_distance * maximum_move_distance)
                {
                    if (mst.adjacentNodes(neighbours[0]).size() == 1) //We just have two nodes left!
                    {
                        next_layer_vertex += motion / 2;
                    }
                    else //This is a leaf that's about to collapse. Leave it out on the next layer.
                    {
                        contact_nodes[layer_nr - 1][neighbours[0]].distance_to_top = std::max(contact_nodes[layer_nr - 1][neighbours[0]].distance_to_top, node.distance_to_top);
                        contact_nodes[layer_nr - 1][neighbours[0]].support_roof_layers_below = std::max(contact_nodes[layer_nr - 1][neighbours[0]].support_roof_layers_below, node.support_roof_layers_below);
                        continue;
                    }
                }
                else
                {
                    next_layer_vertex += motion;
                }
            }

            //Avoid collisions.
            if (node.distance_to_top > tip_layers) //Main branch.
            {
                const coord_t branch_radius_node = branch_radius * node.distance_to_top * diameter_angle_scale_factor;
                PolygonUtils::moveOutside(model_collision_branch_radius[layer_nr - 1], next_layer_vertex, branch_radius_node, maximum_move_distance * maximum_move_distance);
            }
            else //Tip.
            {
                const coord_t branch_radius_node = branch_radius * node.distance_to_top / tip_layers;
                PolygonUtils::moveOutside(model_collision[layer_nr - 1], next_layer_vertex, branch_radius_node, maximum_move_distance * maximum_move_distance);
            }
            if (model_collision[layer_nr].inside(next_layer_vertex)) //We're stuck inside the model down there! Sadly, this branch will have to rest on the model.
            {
                continue;
            }
            contact_points[layer_nr - 1].insert(next_layer_vertex);
            contact_nodes[layer_nr - 1][next_layer_vertex].distance_to_top = node.distance_to_top + 1;
            contact_nodes[layer_nr - 1][next_layer_vertex].skin_direction = node.skin_direction;
            contact_nodes[layer_nr - 1][next_layer_vertex].support_roof_layers_below = node.support_roof_layers_below - 1;
        }
    }

    const unsigned int wall_count = storage.getSettingAsCount("support_tree_wall_count");
    Polygon branch_circle; //Pre-generate a circle with correct diameter so that we don't have to recompute those (co)sines every time.
    for (unsigned int i = 0; i < CIRCLE_RESOLUTION; i++)
    {
        const double angle = (double)i / CIRCLE_RESOLUTION * 2 * M_PI; //In radians.
        branch_circle.emplace_back(cos(angle) * branch_radius, sin(angle) * branch_radius);
    }
    const coord_t circle_side_length = 2 * branch_radius * sin(M_PI / CIRCLE_RESOLUTION); //Side length of a regular polygon.
    for (size_t layer_nr = 0; layer_nr < contact_points.size(); layer_nr++)
    {
        Polygons support_layer;
        Polygons& roof_layer = storage.support.supportLayers[layer_nr].support_roof;

        for (const Point point : contact_points[layer_nr])
        {
            const Node& node = contact_nodes[layer_nr][point];
            Polygon circle;
            const double scale = (double)(node.distance_to_top + 1) / tip_layers;
            for (Point corner : branch_circle)
            {
                if (node.distance_to_top < tip_layers) //We're in the tip.
                {
                    if (node.skin_direction)
                    {
                        corner = Point(corner.X * (0.5 + scale / 2) + corner.Y * (0.5 - scale / 2), corner.X * (0.5 - scale / 2) + corner.Y * (0.5 + scale / 2));
                    }
                    else
                    {
                        corner = Point(corner.X * (0.5 + scale / 2) - corner.Y * (0.5 - scale / 2), corner.X * (-0.5 + scale / 2) + corner.Y * (0.5 + scale / 2));
                    }
                }
                else
                {
                    corner *= 1 + (double)(node.distance_to_top - tip_layers) * diameter_angle_scale_factor;
                }
                circle.add(point + corner);
            }
            if (node.support_roof_layers_below >= 0)
            {
                roof_layer.add(circle);
            }
            else
            {
                support_layer.add(circle);
            }
        }
        support_layer = support_layer.unionPolygons();
        roof_layer = roof_layer.unionPolygons();
        support_layer = support_layer.difference(roof_layer);
        //We smooth this support as much as possible without altering single circles. So we remove any line less than the side length of those circles.
        const double diameter_angle_scale_factor_this_layer = (double)(storage.support.supportLayers.size() - layer_nr - tip_layers) * diameter_angle_scale_factor; //Maximum scale factor.
        support_layer.simplify(circle_side_length * (1 + diameter_angle_scale_factor_this_layer), line_width >> 2); //Deviate at most a quarter of a line so that the lines still stack properly.
        for (PolygonRef part : support_layer) //Convert every part into a PolygonsPart for the support.
        {
            PolygonsPart outline;
            outline.add(part);
            storage.support.supportLayers[layer_nr].support_infill_parts.emplace_back(outline, line_width, wall_count);
        }
        PolygonsPart debug;
        debug.add(model_collision_branch_radius[layer_nr]);
        storage.support.supportLayers[layer_nr].support_infill_parts.emplace_back(debug, line_width, wall_count);
        if (!storage.support.supportLayers[layer_nr].support_infill_parts.empty() || !storage.support.supportLayers[layer_nr].support_roof.empty())
        {
            storage.support.layer_nr_max_filled_layer = layer_nr;
        }
    }
{'fraction_non_alphanumeric': 0.09193684013827899, 'fraction_numerical': 0.009016163692422686, 'mean_word_length': 2.648091342876619, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 33, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1415159', 'n_tokens_mistral': 6345, 'n_tokens_neox': 5993, 'n_words': 1444}