1 //Copyright (c) 2018 Ultimaker B.V.
2 //CuraEngine is released under the terms of the AGPLv3 or higher.
3
4 #include "SubDivCube.h"
5
6 #include <functional>
7
8 #include "../sliceDataStorage.h"
9 #include "../settings/types/AngleRadians.h" //For the infill angle.
10 #include "../utils/math.h"
11 #include "../utils/polygonUtils.h"
12
13 #define ONE_OVER_SQRT_2 0.7071067811865475244008443621048490392848359376884740 //1 / sqrt(2)
14 #define ONE_OVER_SQRT_3 0.577350269189625764509148780501957455647601751270126876018 //1 / sqrt(3)
15 #define ONE_OVER_SQRT_6 0.408248290463863016366214012450981898660991246776111688072 //1 / sqrt(6)
16 #define SQRT_TWO_THIRD 0.816496580927726032732428024901963797321982493552223376144 //sqrt(2 / 3)
17
18 namespace cura
19 {
20
21 std::vector<SubDivCube::CubeProperties> SubDivCube::cube_properties_per_recursion_step;
22 coord_t SubDivCube::radius_addition = 0;
23 Point3Matrix SubDivCube::rotation_matrix;
24 PointMatrix SubDivCube::infill_rotation_matrix;
25
~SubDivCube()26 SubDivCube::~SubDivCube()
27 {
28 for (int child_idx = 0; child_idx < 8; child_idx++)
29 {
30 if (children[child_idx])
31 {
32 delete children[child_idx];
33 }
34 }
35 }
36
precomputeOctree(SliceMeshStorage & mesh,const Point & infill_origin)37 void SubDivCube::precomputeOctree(SliceMeshStorage& mesh, const Point& infill_origin)
38 {
39 radius_addition = mesh.settings.get<coord_t>("sub_div_rad_add");
40
41 // if infill_angles is not empty use the first value, otherwise use 0
42 const std::vector<AngleDegrees> infill_angles = mesh.settings.get<std::vector<AngleDegrees>>("infill_angles");
43 const AngleDegrees infill_angle = (!infill_angles.empty()) ? infill_angles[0] : AngleDegrees(0);
44
45 const coord_t furthest_dist_from_origin = std::sqrt(square(mesh.settings.get<coord_t>("machine_height")) + square(mesh.settings.get<coord_t>("machine_depth") / 2) + square(mesh.settings.get<coord_t>("machine_width") / 2));
46 const coord_t max_side_length = furthest_dist_from_origin * 2;
47
48 size_t curr_recursion_depth = 0;
49 const coord_t infill_line_distance = mesh.settings.get<coord_t>("infill_line_distance");
50 if (infill_line_distance > 0)
51 {
52 for (coord_t curr_side_length = infill_line_distance * 2; curr_side_length < max_side_length * 2; curr_side_length *= 2)
53 {
54 cube_properties_per_recursion_step.emplace_back();
55 CubeProperties& cube_properties_here = cube_properties_per_recursion_step.back();
56 cube_properties_here.side_length = curr_side_length;
57 cube_properties_here.height = sqrt(3) * curr_side_length;
58 cube_properties_here.square_height = sqrt(2) * curr_side_length;
59 cube_properties_here.max_draw_z_diff = ONE_OVER_SQRT_3 * curr_side_length;
60 cube_properties_here.max_line_offset = ONE_OVER_SQRT_6 * curr_side_length;
61 curr_recursion_depth++;
62 }
63 }
64 Point3 center(infill_origin.X, infill_origin.Y, 0);
65
66 Point3Matrix tilt; // rotation matrix to get from axis aligned cubes to cubes standing on their tip
67 // The Z axis is transformed to go in positive Y direction
68 //
69 // cross section in a horizontal plane horizontal plane showing
70 // looking down at the origin O positive X and positive Y
71 // Z .
72 // /:\ Y .
73 // / : \ ^ .
74 // / : \ | .
75 // / .O. \ | .
76 // /.~' '~.\ O---->X .
77 // X """"""""""" Y .
78 tilt.matrix[0] = -ONE_OVER_SQRT_2; tilt.matrix[1] = ONE_OVER_SQRT_2; tilt.matrix[2] = 0;
79 tilt.matrix[3] = -ONE_OVER_SQRT_6; tilt.matrix[4] = -ONE_OVER_SQRT_6; tilt.matrix[5] = SQRT_TWO_THIRD ;
80 tilt.matrix[6] = ONE_OVER_SQRT_3; tilt.matrix[7] = ONE_OVER_SQRT_3; tilt.matrix[8] = ONE_OVER_SQRT_3;
81
82 infill_rotation_matrix = PointMatrix(infill_angle);
83 Point3Matrix infill_angle_mat(infill_rotation_matrix);
84
85 rotation_matrix = infill_angle_mat.compose(tilt);
86
87 mesh.base_subdiv_cube = new SubDivCube(mesh, center, curr_recursion_depth - 1);
88 }
89
generateSubdivisionLines(const coord_t z,Polygons & result)90 void SubDivCube::generateSubdivisionLines(const coord_t z, Polygons& result)
91 {
92 if (cube_properties_per_recursion_step.empty()) //Infill is set to 0%.
93 {
94 return;
95 }
96 Polygons directional_line_groups[3];
97
98 generateSubdivisionLines(z, result, directional_line_groups);
99
100 for (int dir_idx = 0; dir_idx < 3; dir_idx++)
101 {
102 Polygons& line_group = directional_line_groups[dir_idx];
103 for (unsigned int line_idx = 0; line_idx < line_group.size(); line_idx++)
104 {
105 result.addLine(line_group[line_idx][0], line_group[line_idx][1]);
106 }
107 }
108 }
109
generateSubdivisionLines(const coord_t z,Polygons & result,Polygons (& directional_line_groups)[3])110 void SubDivCube::generateSubdivisionLines(const coord_t z, Polygons& result, Polygons (&directional_line_groups)[3])
111 {
112 CubeProperties cube_properties = cube_properties_per_recursion_step[depth];
113
114 const coord_t z_diff = std::abs(z - center.z); //!< the difference between the cube center and the target layer.
115 if (z_diff > cube_properties.height / 2) //!< this cube does not touch the target layer. Early exit.
116 {
117 return;
118 }
119 if (z_diff < cube_properties.max_draw_z_diff) //!< this cube has lines that need to be drawn.
120 {
121 Point relative_a, relative_b; //!< relative coordinates of line endpoints around cube center
122 Point a, b; //!< absolute coordinates of line endpoints
123 relative_a.X = (cube_properties.square_height / 2) * (cube_properties.max_draw_z_diff - z_diff) / cube_properties.max_draw_z_diff;
124 relative_b.X = -relative_a.X;
125 relative_a.Y = cube_properties.max_line_offset - ((z - (center.z - cube_properties.max_draw_z_diff)) * ONE_OVER_SQRT_2);
126 relative_b.Y = relative_a.Y;
127 rotatePointInitial(relative_a);
128 rotatePointInitial(relative_b);
129 for (int dir_idx = 0; dir_idx < 3; dir_idx++)//!< draw the line, then rotate 120 degrees.
130 {
131 a.X = center.x + relative_a.X;
132 a.Y = center.y + relative_a.Y;
133 b.X = center.x + relative_b.X;
134 b.Y = center.y + relative_b.Y;
135 addLineAndCombine(directional_line_groups[dir_idx], a, b);
136 if (dir_idx < 2)
137 {
138 rotatePoint120(relative_a);
139 rotatePoint120(relative_b);
140 }
141 }
142 }
143 for (int idx = 0; idx < 8; idx++) //!< draws the eight children
144 {
145 if (children[idx] != nullptr)
146 {
147 children[idx]->generateSubdivisionLines(z, result, directional_line_groups);
148 }
149 }
150 }
151
SubDivCube(SliceMeshStorage & mesh,Point3 & center,size_t depth)152 SubDivCube::SubDivCube(SliceMeshStorage& mesh, Point3& center, size_t depth)
153 {
154 this->depth = depth;
155 this->center = center;
156
157 if (depth == 0) // lowest layer, no need for subdivision, exit.
158 {
159 return;
160 }
161 if (depth >= cube_properties_per_recursion_step.size()) //Depth is out of bounds of what we pre-computed.
162 {
163 return;
164 }
165
166 CubeProperties cube_properties = cube_properties_per_recursion_step[depth];
167 Point3 child_center;
168 coord_t radius = double(cube_properties.height) / 4.0 + radius_addition;
169
170 int child_nr = 0;
171 std::vector<Point3> rel_child_centers;
172 rel_child_centers.emplace_back(1, 1, 1); // top
173 rel_child_centers.emplace_back(-1, 1, 1); // top three
174 rel_child_centers.emplace_back(1, -1, 1);
175 rel_child_centers.emplace_back(1, 1, -1);
176 rel_child_centers.emplace_back(-1, -1, -1); // bottom
177 rel_child_centers.emplace_back(1, -1, -1); // bottom three
178 rel_child_centers.emplace_back(-1, 1, -1);
179 rel_child_centers.emplace_back(-1, -1, 1);
180 for (Point3 rel_child_center : rel_child_centers)
181 {
182 child_center = center + rotation_matrix.apply(rel_child_center * int32_t(cube_properties.side_length / 4));
183 if (isValidSubdivision(mesh, child_center, radius))
184 {
185 children[child_nr] = new SubDivCube(mesh, child_center, depth - 1);
186 child_nr++;
187 }
188 }
189 }
190
isValidSubdivision(SliceMeshStorage & mesh,Point3 & center,coord_t radius)191 bool SubDivCube::isValidSubdivision(SliceMeshStorage& mesh, Point3& center, coord_t radius)
192 {
193 coord_t distance2 = 0;
194 coord_t sphere_slice_radius2;//!< squared radius of bounding sphere slice on target layer
195 bool inside_somewhere = false;
196 bool outside_somewhere = false;
197 int inside;
198 Ratio part_dist;//what percentage of the radius the target layer is away from the center along the z axis. 0 - 1
199 const coord_t layer_height = mesh.settings.get<coord_t>("layer_height");
200 int bottom_layer = (center.z - radius) / layer_height;
201 int top_layer = (center.z + radius) / layer_height;
202 for (int test_layer = bottom_layer; test_layer <= top_layer; test_layer += 3) // steps of three. Low-hanging speed gain.
203 {
204 part_dist = static_cast<Ratio>(test_layer * layer_height - center.z) / radius;
205 sphere_slice_radius2 = radius * radius * (1.0 - (part_dist * part_dist));
206 Point loc(center.x, center.y);
207
208 inside = distanceFromPointToMesh(mesh, test_layer, loc, &distance2);
209 if (inside == 1)
210 {
211 inside_somewhere = true;
212 }
213 else
214 {
215 outside_somewhere = true;
216 }
217 if (outside_somewhere && inside_somewhere)
218 {
219 return true;
220 }
221 if ((inside != 2) && distance2 < sphere_slice_radius2)
222 {
223 return true;
224 }
225 }
226 return false;
227 }
228
distanceFromPointToMesh(SliceMeshStorage & mesh,const LayerIndex layer_nr,Point & location,coord_t * distance2)229 coord_t SubDivCube::distanceFromPointToMesh(SliceMeshStorage& mesh, const LayerIndex layer_nr, Point& location, coord_t* distance2)
230 {
231 if (layer_nr < 0 || (unsigned int)layer_nr >= mesh.layers.size()) //!< this layer is outside of valid range
232 {
233 return 2;
234 *distance2 = 0;
235 }
236 Polygons& collide = mesh.layers[layer_nr].getInnermostWalls(2, mesh);
237 Point centerpoint = location;
238 bool inside = collide.inside(centerpoint);
239 ClosestPolygonPoint border_point = PolygonUtils::moveInside2(collide, centerpoint);
240 Point diff = border_point.location - location;
241 *distance2 = vSize2(diff);
242 if (inside)
243 {
244 return 1;
245 }
246 return 0;
247 }
248
249
rotatePointInitial(Point & target)250 void SubDivCube::rotatePointInitial(Point& target)
251 {
252 target = infill_rotation_matrix.apply(target);
253 }
254
rotatePoint120(Point & target)255 void SubDivCube::rotatePoint120(Point& target)
256 {
257 //constexpr double sqrt_three_fourths = sqrt(3.0 / 4.0); //TODO: Reactivate once MacOS is upgraded to a more modern compiler.
258 #define sqrt_three_fourths 0.86602540378443864676372317
259 const coord_t x = -0.5 * target.X - sqrt_three_fourths * target.Y;
260 target.Y = -0.5 * target.Y + sqrt_three_fourths * target.X;
261 target.X = x;
262 }
263
addLineAndCombine(Polygons & group,Point from,Point to)264 void SubDivCube::addLineAndCombine(Polygons& group, Point from, Point to)
265 {
266 int epsilon = 10; // the smallest distance of two points which are viewed as coincident (dist > 0 due to rounding errors)
267 for (unsigned int idx = 0; idx < group.size(); idx++)
268 {
269 if (std::abs(from.X - group[idx][1].X) < epsilon && std::abs(from.Y - group[idx][1].Y) < epsilon)
270 {
271 from = group[idx][0];
272 group.remove(idx);
273 idx--;
274 continue;
275 }
276 if (std::abs(to.X - group[idx][0].X) < epsilon && std::abs(to.Y - group[idx][0].Y) < epsilon)
277 {
278 to = group[idx][1];
279 group.remove(idx);
280 idx--;
281 continue;
282 }
283 }
284 group.addLine(from, to);
285 }
286
287 }//namespace cura
288