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

#include "utils/polygonUtils.h" //For moveInside.

#include "TreeSupport.h"

#define SQRT_2 1.4142135623730950488 //Square root of 2.

namespace cura
{

TreeSupport::TreeSupport()
{
}

void TreeSupport::generateSupportAreas(SliceDataStorage& storage)
{
    std::vector<std::vector<Point>> contact_points;
    contact_points.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();
    }
    for (SliceMeshStorage& mesh : storage.meshes)
    {
        if (!mesh.getSettingBoolean("support_tree_enable"))
        {
            return;
        }
        generateContactPoints(mesh, contact_points);
    }

    //Placeholder to test with that generates a simple diamond at each contact point (without generating any trees yet).
    for (size_t layer_nr = 0; layer_nr < contact_points.size(); layer_nr++)
    {
        for (Point point : contact_points[layer_nr])
        {
            PolygonsPart outline;
            Polygon diamond;
            diamond.add(point + Point(0, 1000));
            diamond.add(point + Point(-1000, 0));
            diamond.add(point + Point(0, -1000));
            diamond.add(point + Point(1000, 0));
            outline.add(diamond);
            storage.support.supportLayers[layer_nr].support_infill_parts.emplace_back(outline, 350);
        }
        if (!contact_points[layer_nr].empty())
        {
            storage.support.layer_nr_max_filled_layer = layer_nr;
        }
    }

    //TODO: Use Minimum Spanning Tree to connect the points on each layer.
    //TODO: Drop down and contract the leaves of the tree.
    //TODO: Create a pyramid out of the mesh and move points away from that.
    //TODO: When reaching the bottom, cut away all edges of the MST that are still not contracted.
    //TODO: Do a second pass of dropping down but with leftover edges removed.
    //TODO: Apply some diameter to the tree branches.
    
    storage.support.generated = true;
}

void TreeSupport::generateContactPoints(const SliceMeshStorage& mesh, std::vector<std::vector<Point>>& contact_points)
{
    for (size_t layer_nr = 0; layer_nr < mesh.overhang_areas.size(); layer_nr++)
    {
        const Polygons& overhang = mesh.overhang_areas[layer_nr];
        if (overhang.empty())
        {
            continue;
        }

        //First generate a lot of points in a grid pattern.
        Polygons outside_polygons = overhang.getOutsidePolygons();
        AABB bounding_box(outside_polygons); //To know how far we should generate points.
        coord_t point_spread = mesh.getSettingInMicrons("support_tree_branch_distance");
        point_spread *= SQRT_2; //We'll rotate these points 45 degrees, so this is the point distance when axis-aligned.
        bounding_box.round(point_spread);
        for (PolygonRef overhang_part : outside_polygons)
        {
            AABB bounding_box(outside_polygons);
            bounding_box.round(point_spread);
            bool added = false; //Did we add a point this way?<commit_msg>Apply Z distance<commit_after>//Copyright (c) 2017 <NAME>.
//CuraEngine is released under the terms of the AGPLv3 or higher.

#include "utils/math.h" //For round_up_divide.
#include "utils/polygonUtils.h" //For moveInside.

#include "TreeSupport.h"

#define SQRT_2 1.4142135623730950488 //Square root of 2.

namespace cura
{

TreeSupport::TreeSupport()
{
}

void TreeSupport::generateSupportAreas(SliceDataStorage& storage)
{
    std::vector<std::vector<Point>> contact_points;
    contact_points.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();
    }
    for (SliceMeshStorage& mesh : storage.meshes)
    {
        if (!mesh.getSettingBoolean("support_tree_enable"))
        {
            return;
        }
        generateContactPoints(mesh, contact_points);
    }

    //Placeholder to test with that generates a simple diamond at each contact point (without generating any trees yet).
    for (size_t layer_nr = 0; layer_nr < contact_points.size(); layer_nr++)
    {
        for (Point point : contact_points[layer_nr])
        {
            PolygonsPart outline;
            Polygon diamond;
            diamond.add(point + Point(0, 1000));
            diamond.add(point + Point(-1000, 0));
            diamond.add(point + Point(0, -1000));
            diamond.add(point + Point(1000, 0));
            outline.add(diamond);
            storage.support.supportLayers[layer_nr].support_infill_parts.emplace_back(outline, 350);
        }
        if (!contact_points[layer_nr].empty())
        {
            storage.support.layer_nr_max_filled_layer = layer_nr;
        }
    }

    //TODO: Use Minimum Spanning Tree to connect the points on each layer.
    //TODO: Drop down and contract the leaves of the tree.
    //TODO: Create a pyramid out of the mesh and move points away from that.
    //TODO: When reaching the bottom, cut away all edges of the MST that are still not contracted.
    //TODO: Do a second pass of dropping down but with leftover edges removed.
    //TODO: Apply some diameter to the tree branches.
    
    storage.support.generated = true;
}

void TreeSupport::generateContactPoints(const SliceMeshStorage& mesh, std::vector<std::vector<Point>>& contact_points)
{
    const coord_t layer_height = mesh.getSettingInMicrons("layer_height");
    const coord_t z_distance_top = mesh.getSettingInMicrons("support_top_distance");
    const size_t z_distance_top_layers = std::max(0U, round_up_divide(z_distance_top, layer_height)) + 1; //Support must always be 1 layer below overhang.
    for (size_t layer_nr = 0; layer_nr < mesh.overhang_areas.size() - z_distance_top_layers; layer_nr++)
    {
        const Polygons& overhang = mesh.overhang_areas[layer_nr + z_distance_top_layers];
        if (overhang.empty())
        {
            continue;
        }

        //First generate a lot of points in a grid pattern.
        Polygons outside_polygons = overhang.getOutsidePolygons();
        AABB bounding_box(outside_polygons); //To know how far we should generate points.
        coord_t point_spread = mesh.getSettingInMicrons("support_tree_branch_distance");
        point_spread *= SQRT_2; //We'll rotate these points 45 degrees, so this is the point distance when axis-aligned.
        bounding_box.round(point_spread);
        for (PolygonRef overhang_part : outside_polygons)
        {
            AABB bounding_box(outside_polygons);
            bounding_box.round(point_spread);
            bool added = false; //Did we add a point this way?
{'fraction_non_alphanumeric': 0.09743366681165724, 'fraction_numerical': 0.016673916195447294, 'mean_word_length': 2.921546333143832, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 13, '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': '4637449', 'n_tokens_mistral': 2153, 'n_tokens_neox': 2016, 'n_words': 570}