1 #ifndef libslic3r_TriangleSelector_hpp_ 2 #define libslic3r_TriangleSelector_hpp_ 3 4 // #define PRUSASLICER_TRIANGLE_SELECTOR_DEBUG 5 6 7 #include "Point.hpp" 8 #include "TriangleMesh.hpp" 9 10 namespace Slic3r { 11 12 enum class EnforcerBlockerType : int8_t; 13 14 15 16 // Following class holds information about selected triangles. It also has power 17 // to recursively subdivide the triangles and make the selection finer. 18 class TriangleSelector { 19 public: 20 enum CursorType { 21 CIRCLE, 22 SPHERE 23 }; 24 25 void set_edge_limit(float edge_limit); 26 27 // Create new object on a TriangleMesh. The referenced mesh must 28 // stay valid, a ptr to it is saved and used. 29 explicit TriangleSelector(const TriangleMesh& mesh); 30 31 // Select all triangles fully inside the circle, subdivide where needed. 32 void select_patch(const Vec3f& hit, // point where to start 33 int facet_start, // facet that point belongs to 34 const Vec3f& source, // camera position (mesh coords) 35 float radius, // radius of the cursor 36 CursorType type, // current type of cursor 37 EnforcerBlockerType new_state, // enforcer or blocker? 38 const Transform3d& trafo); // matrix to get from mesh to world 39 40 // Get facets currently in the given state. 41 indexed_triangle_set get_facets(EnforcerBlockerType state) const; 42 43 // Set facet of the mesh to a given state. Only works for original triangles. 44 void set_facet(int facet_idx, EnforcerBlockerType state); 45 46 // Clear everything and make the tree empty. 47 void reset(); 48 49 // Remove all unnecessary data. 50 void garbage_collect(); 51 52 // Store the division trees in compact form (a long stream of 53 // bits for each triangle of the original mesh). 54 std::map<int, std::vector<bool>> serialize() const; 55 56 // Load serialized data. Assumes that correct mesh is loaded. 57 void deserialize(const std::map<int, std::vector<bool>> data); 58 59 60 protected: 61 // Triangle and info about how it's split. 62 class Triangle { 63 public: 64 // Use TriangleSelector::push_triangle to create a new triangle. 65 // It increments/decrements reference counter on vertices. Triangle(int a,int b,int c)66 Triangle(int a, int b, int c) 67 : verts_idxs{a, b, c}, 68 state{EnforcerBlockerType(0)}, 69 number_of_splits{0}, 70 special_side_idx{0}, 71 old_number_of_splits{0} 72 {} 73 // Indices into m_vertices. 74 std::array<int, 3> verts_idxs; 75 76 // Is this triangle valid or marked to be removed? 77 bool valid{true}; 78 79 // Children triangles. 80 std::array<int, 4> children; 81 82 // Set the division type. 83 void set_division(int sides_to_split, int special_side_idx = -1); 84 85 // Get/set current state. set_state(EnforcerBlockerType type)86 void set_state(EnforcerBlockerType type) { assert(! is_split()); state = type; } get_state() const87 EnforcerBlockerType get_state() const { assert(! is_split()); return state; } 88 89 // Get info on how it's split. is_split() const90 bool is_split() const { return number_of_split_sides() != 0; } number_of_split_sides() const91 int number_of_split_sides() const { return number_of_splits; } special_side() const92 int special_side() const { assert(is_split()); return special_side_idx; } was_split_before() const93 bool was_split_before() const { return old_number_of_splits != 0; } forget_history()94 void forget_history() { old_number_of_splits = 0; } 95 96 private: 97 int number_of_splits; 98 int special_side_idx; 99 EnforcerBlockerType state; 100 101 // How many children were spawned during last split? 102 // Is not reset on remerging the triangle. 103 int old_number_of_splits; 104 }; 105 106 struct Vertex { VertexSlic3r::TriangleSelector::Vertex107 explicit Vertex(const stl_vertex& vert) 108 : v{vert}, 109 ref_cnt{0} 110 {} 111 stl_vertex v; 112 int ref_cnt; 113 }; 114 115 // Lists of vertices and triangles, both original and new 116 std::vector<Vertex> m_vertices; 117 std::vector<Triangle> m_triangles; 118 const TriangleMesh* m_mesh; 119 120 // Number of invalid triangles (to trigger garbage collection). 121 int m_invalid_triangles; 122 123 // Limiting length of triangle side (squared). 124 float m_edge_limit_sqr = 1.f; 125 126 // Number of original vertices and triangles. 127 int m_orig_size_vertices = 0; 128 int m_orig_size_indices = 0; 129 130 // Cache for cursor position, radius and direction. 131 struct Cursor { 132 Cursor() = default; 133 Cursor(const Vec3f& center_, const Vec3f& source_, float radius_world, 134 CursorType type_, const Transform3d& trafo_); 135 bool is_mesh_point_inside(Vec3f pt) const; 136 bool is_pointer_in_triangle(const Vec3f& p1, const Vec3f& p2, const Vec3f& p3) const; 137 138 Vec3f center; 139 Vec3f source; 140 Vec3f dir; 141 float radius_sqr; 142 CursorType type; 143 Transform3f trafo; 144 Transform3f trafo_normal; 145 bool uniform_scaling; 146 }; 147 148 Cursor m_cursor; 149 float m_old_cursor_radius_sqr; 150 151 // Private functions: 152 bool select_triangle(int facet_idx, EnforcerBlockerType type, 153 bool recursive_call = false); 154 int vertices_inside(int facet_idx) const; 155 bool faces_camera(int facet) const; 156 void undivide_triangle(int facet_idx); 157 void split_triangle(int facet_idx); 158 void remove_useless_children(int facet_idx); // No hidden meaning. Triangles are meant. 159 bool is_pointer_in_triangle(int facet_idx) const; 160 bool is_edge_inside_cursor(int facet_idx) const; 161 void push_triangle(int a, int b, int c); 162 void perform_split(int facet_idx, EnforcerBlockerType old_state); 163 }; 164 165 166 167 168 } // namespace Slic3r 169 170 #endif // libslic3r_TriangleSelector_hpp_ 171