FillAdaptive.cpp 73 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553
  1. #include "../ClipperUtils.hpp"
  2. #include "../ExPolygon.hpp"
  3. #include "../Surface.hpp"
  4. #include "../Geometry.hpp"
  5. #include "../Layer.hpp"
  6. #include "../Print.hpp"
  7. #include "../ShortestPath.hpp"
  8. #include "FillAdaptive.hpp"
  9. // for indexed_triangle_set
  10. #include <admesh/stl.h>
  11. #include <cstdlib>
  12. #include <cmath>
  13. #include <algorithm>
  14. #include <numeric>
  15. // Boost pool: Don't use mutexes to synchronize memory allocation.
  16. #define BOOST_POOL_NO_MT
  17. #include <boost/pool/object_pool.hpp>
  18. #include <boost/geometry.hpp>
  19. #include <boost/geometry/geometries/point.hpp>
  20. #include <boost/geometry/geometries/segment.hpp>
  21. #include <boost/geometry/index/rtree.hpp>
  22. namespace Slic3r {
  23. namespace FillAdaptive {
  24. // Derived from https://github.com/juj/MathGeoLib/blob/master/src/Geometry/Triangle.cpp
  25. // The AABB-Triangle test implementation is based on the pseudo-code in
  26. // Christer Ericson's Real-Time Collision Detection, pp. 169-172. It is
  27. // practically a standard SAT test.
  28. //
  29. // Original MathGeoLib benchmark:
  30. // Best: 17.282 nsecs / 46.496 ticks, Avg: 17.804 nsecs, Worst: 18.434 nsecs
  31. //
  32. //FIXME Vojtech: The MathGeoLib contains a vectorized implementation.
  33. template<typename Vector>
  34. bool triangle_AABB_intersects(const Vector &a, const Vector &b, const Vector &c, const BoundingBoxBase<Vector> &aabb)
  35. {
  36. using Scalar = typename Vector::Scalar;
  37. Vector tMin = a.cwiseMin(b.cwiseMin(c));
  38. Vector tMax = a.cwiseMax(b.cwiseMax(c));
  39. if (tMin.x() >= aabb.max.x() || tMax.x() <= aabb.min.x()
  40. || tMin.y() >= aabb.max.y() || tMax.y() <= aabb.min.y()
  41. || tMin.z() >= aabb.max.z() || tMax.z() <= aabb.min.z())
  42. return false;
  43. Vector center = (aabb.min + aabb.max) * 0.5f;
  44. Vector h = aabb.max - center;
  45. const Vector t[3] { b-a, c-a, c-b };
  46. Vector ac = a - center;
  47. Vector n = t[0].cross(t[1]);
  48. Scalar s = n.dot(ac);
  49. Scalar r = std::abs(h.dot(n.cwiseAbs()));
  50. if (abs(s) >= r)
  51. return false;
  52. const Vector at[3] = { t[0].cwiseAbs(), t[1].cwiseAbs(), t[2].cwiseAbs() };
  53. Vector bc = b - center;
  54. Vector cc = c - center;
  55. // SAT test all cross-axes.
  56. // The following is a fully unrolled loop of this code, stored here for reference:
  57. /*
  58. Scalar d1, d2, a1, a2;
  59. const Vector e[3] = { DIR_VEC(1, 0, 0), DIR_VEC(0, 1, 0), DIR_VEC(0, 0, 1) };
  60. for(int i = 0; i < 3; ++i)
  61. for(int j = 0; j < 3; ++j)
  62. {
  63. Vector axis = Cross(e[i], t[j]);
  64. ProjectToAxis(axis, d1, d2);
  65. aabb.ProjectToAxis(axis, a1, a2);
  66. if (d2 <= a1 || d1 >= a2) return false;
  67. }
  68. */
  69. // eX <cross> t[0]
  70. Scalar d1 = t[0].y() * ac.z() - t[0].z() * ac.y();
  71. Scalar d2 = t[0].y() * cc.z() - t[0].z() * cc.y();
  72. Scalar tc = (d1 + d2) * 0.5f;
  73. r = std::abs(h.y() * at[0].z() + h.z() * at[0].y());
  74. if (r + std::abs(tc - d1) < std::abs(tc))
  75. return false;
  76. // eX <cross> t[1]
  77. d1 = t[1].y() * ac.z() - t[1].z() * ac.y();
  78. d2 = t[1].y() * bc.z() - t[1].z() * bc.y();
  79. tc = (d1 + d2) * 0.5f;
  80. r = std::abs(h.y() * at[1].z() + h.z() * at[1].y());
  81. if (r + std::abs(tc - d1) < std::abs(tc))
  82. return false;
  83. // eX <cross> t[2]
  84. d1 = t[2].y() * ac.z() - t[2].z() * ac.y();
  85. d2 = t[2].y() * bc.z() - t[2].z() * bc.y();
  86. tc = (d1 + d2) * 0.5f;
  87. r = std::abs(h.y() * at[2].z() + h.z() * at[2].y());
  88. if (r + std::abs(tc - d1) < std::abs(tc))
  89. return false;
  90. // eY <cross> t[0]
  91. d1 = t[0].z() * ac.x() - t[0].x() * ac.z();
  92. d2 = t[0].z() * cc.x() - t[0].x() * cc.z();
  93. tc = (d1 + d2) * 0.5f;
  94. r = std::abs(h.x() * at[0].z() + h.z() * at[0].x());
  95. if (r + std::abs(tc - d1) < std::abs(tc))
  96. return false;
  97. // eY <cross> t[1]
  98. d1 = t[1].z() * ac.x() - t[1].x() * ac.z();
  99. d2 = t[1].z() * bc.x() - t[1].x() * bc.z();
  100. tc = (d1 + d2) * 0.5f;
  101. r = std::abs(h.x() * at[1].z() + h.z() * at[1].x());
  102. if (r + std::abs(tc - d1) < std::abs(tc))
  103. return false;
  104. // eY <cross> t[2]
  105. d1 = t[2].z() * ac.x() - t[2].x() * ac.z();
  106. d2 = t[2].z() * bc.x() - t[2].x() * bc.z();
  107. tc = (d1 + d2) * 0.5f;
  108. r = std::abs(h.x() * at[2].z() + h.z() * at[2].x());
  109. if (r + std::abs(tc - d1) < std::abs(tc))
  110. return false;
  111. // eZ <cross> t[0]
  112. d1 = t[0].x() * ac.y() - t[0].y() * ac.x();
  113. d2 = t[0].x() * cc.y() - t[0].y() * cc.x();
  114. tc = (d1 + d2) * 0.5f;
  115. r = std::abs(h.y() * at[0].x() + h.x() * at[0].y());
  116. if (r + std::abs(tc - d1) < std::abs(tc))
  117. return false;
  118. // eZ <cross> t[1]
  119. d1 = t[1].x() * ac.y() - t[1].y() * ac.x();
  120. d2 = t[1].x() * bc.y() - t[1].y() * bc.x();
  121. tc = (d1 + d2) * 0.5f;
  122. r = std::abs(h.y() * at[1].x() + h.x() * at[1].y());
  123. if (r + std::abs(tc - d1) < std::abs(tc))
  124. return false;
  125. // eZ <cross> t[2]
  126. d1 = t[2].x() * ac.y() - t[2].y() * ac.x();
  127. d2 = t[2].x() * bc.y() - t[2].y() * bc.x();
  128. tc = (d1 + d2) * 0.5f;
  129. r = std::abs(h.y() * at[2].x() + h.x() * at[2].y());
  130. if (r + std::abs(tc - d1) < std::abs(tc))
  131. return false;
  132. // No separating axis exists, the AABB and triangle intersect.
  133. return true;
  134. }
  135. // static double dist2_to_triangle(const Vec3d &a, const Vec3d &b, const Vec3d &c, const Vec3d &p)
  136. // {
  137. // double out = std::numeric_limits<double>::max();
  138. // const Vec3d v1 = b - a;
  139. // auto l1 = v1.squaredNorm();
  140. // const Vec3d v2 = c - b;
  141. // auto l2 = v2.squaredNorm();
  142. // const Vec3d v3 = a - c;
  143. // auto l3 = v3.squaredNorm();
  144. // // Is the triangle valid?
  145. // if (l1 > 0. && l2 > 0. && l3 > 0.)
  146. // {
  147. // // 1) Project point into the plane of the triangle.
  148. // const Vec3d n = v1.cross(v2);
  149. // double d = (p - a).dot(n);
  150. // const Vec3d foot_pt = p - n * d / n.squaredNorm();
  151. // // 2) Maximum projection of n.
  152. // int proj_axis;
  153. // n.array().cwiseAbs().maxCoeff(&proj_axis);
  154. // // 3) Test whether the foot_pt is inside the triangle.
  155. // {
  156. // auto inside_triangle = [](const Vec2d& v1, const Vec2d& v2, const Vec2d& v3, const Vec2d& pt) {
  157. // const double d1 = cross2(v1, pt);
  158. // const double d2 = cross2(v2, pt);
  159. // const double d3 = cross2(v3, pt);
  160. // // Testing both CCW and CW orientations.
  161. // return (d1 >= 0. && d2 >= 0. && d3 >= 0.) || (d1 <= 0. && d2 <= 0. && d3 <= 0.);
  162. // };
  163. // bool inside;
  164. // switch (proj_axis) {
  165. // case 0:
  166. // inside = inside_triangle({v1.y(), v1.z()}, {v2.y(), v2.z()}, {v3.y(), v3.z()}, {foot_pt.y(), foot_pt.z()}); break;
  167. // case 1:
  168. // inside = inside_triangle({v1.z(), v1.x()}, {v2.z(), v2.x()}, {v3.z(), v3.x()}, {foot_pt.z(), foot_pt.x()}); break;
  169. // default:
  170. // assert(proj_axis == 2);
  171. // inside = inside_triangle({v1.x(), v1.y()}, {v2.x(), v2.y()}, {v3.x(), v3.y()}, {foot_pt.x(), foot_pt.y()}); break;
  172. // }
  173. // if (inside)
  174. // return (p - foot_pt).squaredNorm();
  175. // }
  176. // // 4) Find minimum distance to triangle vertices and edges.
  177. // out = std::min((p - a).squaredNorm(), std::min((p - b).squaredNorm(), (p - c).squaredNorm()));
  178. // auto t = (p - a).dot(v1);
  179. // if (t > 0. && t < l1)
  180. // out = std::min(out, (a + v1 * (t / l1) - p).squaredNorm());
  181. // t = (p - b).dot(v2);
  182. // if (t > 0. && t < l2)
  183. // out = std::min(out, (b + v2 * (t / l2) - p).squaredNorm());
  184. // t = (p - c).dot(v3);
  185. // if (t > 0. && t < l3)
  186. // out = std::min(out, (c + v3 * (t / l3) - p).squaredNorm());
  187. // }
  188. // return out;
  189. // }
  190. // Ordering of children cubes.
  191. static const std::array<Vec3d, 8> child_centers {
  192. Vec3d(-1, -1, -1), Vec3d( 1, -1, -1), Vec3d(-1, 1, -1), Vec3d( 1, 1, -1),
  193. Vec3d(-1, -1, 1), Vec3d( 1, -1, 1), Vec3d(-1, 1, 1), Vec3d( 1, 1, 1)
  194. };
  195. // Traversal order of octree children cells for three infill directions,
  196. // so that a single line will be discretized in a strictly monotonic order.
  197. static constexpr std::array<std::array<int, 8>, 3> child_traversal_order {
  198. std::array<int, 8>{ 2, 3, 0, 1, 6, 7, 4, 5 },
  199. std::array<int, 8>{ 4, 0, 6, 2, 5, 1, 7, 3 },
  200. std::array<int, 8>{ 1, 5, 0, 4, 3, 7, 2, 6 },
  201. };
  202. struct Cube
  203. {
  204. Vec3d center;
  205. #ifndef NDEBUG
  206. Vec3d center_octree;
  207. #endif // NDEBUG
  208. std::array<Cube*, 8> children {}; // initialized to nullptrs
  209. Cube(const Vec3d &center) : center(center) {}
  210. };
  211. struct CubeProperties
  212. {
  213. double edge_length; // Lenght of edge of a cube
  214. double height; // Height of rotated cube (standing on the corner)
  215. double diagonal_length; // Length of diagonal of a cube a face
  216. double line_z_distance; // Defines maximal distance from a center of a cube on Z axis on which lines will be created
  217. double line_xy_distance;// Defines maximal distance from a center of a cube on X and Y axis on which lines will be created
  218. };
  219. struct Octree
  220. {
  221. // Octree will allocate its Cubes from the pool. The pool only supports deletion of the complete pool,
  222. // perfect for building up our octree.
  223. boost::object_pool<Cube> pool;
  224. Cube* root_cube { nullptr };
  225. Vec3d origin;
  226. std::vector<CubeProperties> cubes_properties;
  227. Octree(const Vec3d &origin, const std::vector<CubeProperties> &cubes_properties)
  228. : root_cube(pool.construct(origin)), origin(origin), cubes_properties(cubes_properties) {}
  229. void insert_triangle(const Vec3d &a, const Vec3d &b, const Vec3d &c, Cube *current_cube, const BoundingBoxf3 &current_bbox, int depth);
  230. };
  231. void OctreeDeleter::operator()(Octree *p) {
  232. delete p;
  233. }
  234. std::pair<double, double> adaptive_fill_line_spacing(const PrintObject &print_object)
  235. {
  236. // Output, spacing for icAdaptiveCubic and icSupportCubic
  237. double adaptive_line_spacing = 0.;
  238. double support_line_spacing = 0.;
  239. enum class Tristate {
  240. Yes,
  241. No,
  242. Maybe
  243. };
  244. struct RegionFillData {
  245. Tristate has_adaptive_infill;
  246. Tristate has_support_infill;
  247. double density;
  248. double extrusion_width;
  249. };
  250. std::vector<RegionFillData> region_fill_data;
  251. region_fill_data.reserve(print_object.num_printing_regions());
  252. bool build_octree = false;
  253. const std::vector<double> &nozzle_diameters = print_object.print()->config().nozzle_diameter.values;
  254. double max_nozzle_diameter = *std::max_element(nozzle_diameters.begin(), nozzle_diameters.end());
  255. double default_infill_extrusion_width = Flow::auto_extrusion_width(FlowRole::frInfill, float(max_nozzle_diameter));
  256. for (size_t region_id = 0; region_id < print_object.num_printing_regions(); ++ region_id) {
  257. const PrintRegionConfig &config = print_object.printing_region(region_id).config();
  258. bool nonempty = config.fill_density > 0;
  259. bool has_adaptive_infill = nonempty && config.fill_pattern.value == ipAdaptiveCubic;
  260. bool has_support_infill = nonempty && config.fill_pattern.value == ipSupportCubic;
  261. double infill_extrusion_width = config.infill_extrusion_width.get_abs_value(max_nozzle_diameter);
  262. region_fill_data.push_back(RegionFillData({
  263. has_adaptive_infill ? Tristate::Maybe : Tristate::No,
  264. has_support_infill ? Tristate::Maybe : Tristate::No,
  265. config.fill_density,
  266. infill_extrusion_width != 0. ? infill_extrusion_width : default_infill_extrusion_width
  267. }));
  268. build_octree |= has_adaptive_infill || has_support_infill;
  269. }
  270. if (build_octree) {
  271. // Compute the average of above parameters over all layers
  272. for (const Layer *layer : print_object.layers())
  273. for (size_t region_id = 0; region_id < layer->regions().size(); ++ region_id) {
  274. RegionFillData &rd = region_fill_data[region_id];
  275. if (rd.has_adaptive_infill == Tristate::Maybe && ! layer->regions()[region_id]->fill_surfaces.empty())
  276. rd.has_adaptive_infill = Tristate::Yes;
  277. if (rd.has_support_infill == Tristate::Maybe && ! layer->regions()[region_id]->fill_surfaces.empty())
  278. rd.has_support_infill = Tristate::Yes;
  279. }
  280. double adaptive_fill_density = 0.;
  281. double adaptive_infill_extrusion_width = 0.;
  282. int adaptive_cnt = 0;
  283. double support_fill_density = 0.;
  284. double support_infill_extrusion_width = 0.;
  285. int support_cnt = 0;
  286. for (const RegionFillData &rd : region_fill_data) {
  287. if (rd.has_adaptive_infill == Tristate::Yes) {
  288. adaptive_fill_density += rd.density;
  289. adaptive_infill_extrusion_width += rd.extrusion_width;
  290. ++ adaptive_cnt;
  291. } else if (rd.has_support_infill == Tristate::Yes) {
  292. support_fill_density += rd.density;
  293. support_infill_extrusion_width += rd.extrusion_width;
  294. ++ support_cnt;
  295. }
  296. }
  297. auto to_line_spacing = [](int cnt, double density, double extrusion_width) {
  298. if (cnt) {
  299. density /= double(cnt);
  300. extrusion_width /= double(cnt);
  301. return extrusion_width / ((density / 100.0f) * 0.333333333f);
  302. } else
  303. return 0.;
  304. };
  305. adaptive_line_spacing = to_line_spacing(adaptive_cnt, adaptive_fill_density, adaptive_infill_extrusion_width);
  306. support_line_spacing = to_line_spacing(support_cnt, support_fill_density, support_infill_extrusion_width);
  307. }
  308. return std::make_pair(adaptive_line_spacing, support_line_spacing);
  309. }
  310. // Context used by generate_infill_lines() when recursively traversing an octree in a DDA fashion
  311. // (Digital Differential Analyzer).
  312. struct FillContext
  313. {
  314. // The angles have to agree with child_traversal_order.
  315. static constexpr double direction_angles[3] {
  316. 0.,
  317. (2.0 * M_PI) / 3.0,
  318. -(2.0 * M_PI) / 3.0
  319. };
  320. FillContext(const Octree &octree, double z_position, int direction_idx) :
  321. cubes_properties(octree.cubes_properties),
  322. z_position(z_position),
  323. traversal_order(child_traversal_order[direction_idx]),
  324. cos_a(cos(direction_angles[direction_idx])),
  325. sin_a(sin(direction_angles[direction_idx]))
  326. {
  327. static constexpr auto unused = std::numeric_limits<coord_t>::max();
  328. temp_lines.assign((1 << octree.cubes_properties.size()) - 1, Line(Point(unused, unused), Point(unused, unused)));
  329. }
  330. // Rotate the point, uses the same convention as Point::rotate().
  331. Vec2d rotate(const Vec2d& v) { return Vec2d(this->cos_a * v.x() - this->sin_a * v.y(), this->sin_a * v.x() + this->cos_a * v.y()); }
  332. const std::vector<CubeProperties> &cubes_properties;
  333. // Top of the current layer.
  334. const double z_position;
  335. // Order of traversal for this line direction.
  336. const std::array<int, 8> traversal_order;
  337. // Rotation of the generated line for this line direction.
  338. const double cos_a;
  339. const double sin_a;
  340. // Linearized tree spanning a single Octree wall, used to connect lines spanning
  341. // neighboring Octree cells. Unused lines have the Line::a::x set to infinity.
  342. std::vector<Line> temp_lines;
  343. // Final output
  344. std::vector<Line> output_lines;
  345. };
  346. static constexpr double octree_rot[3] = { 5.0 * M_PI / 4.0, Geometry::deg2rad(215.264), M_PI / 6.0 };
  347. Eigen::Quaterniond transform_to_world()
  348. {
  349. return Eigen::AngleAxisd(octree_rot[2], Vec3d::UnitZ()) * Eigen::AngleAxisd(octree_rot[1], Vec3d::UnitY()) * Eigen::AngleAxisd(octree_rot[0], Vec3d::UnitX());
  350. }
  351. Eigen::Quaterniond transform_to_octree()
  352. {
  353. return Eigen::AngleAxisd(- octree_rot[0], Vec3d::UnitX()) * Eigen::AngleAxisd(- octree_rot[1], Vec3d::UnitY()) * Eigen::AngleAxisd(- octree_rot[2], Vec3d::UnitZ());
  354. }
  355. #ifndef NDEBUG
  356. // Verify that the traversal order of the octree children matches the line direction,
  357. // therefore the infill line may get extended with O(1) time & space complexity.
  358. static bool verify_traversal_order(
  359. FillContext &context,
  360. const Cube *cube,
  361. int depth,
  362. const Vec2d &line_from,
  363. const Vec2d &line_to)
  364. {
  365. std::array<Vec3d, 8> c;
  366. Eigen::Quaterniond to_world = transform_to_world();
  367. for (int i = 0; i < 8; ++i) {
  368. int j = context.traversal_order[i];
  369. Vec3d cntr = to_world * (cube->center_octree + (child_centers[j] * (context.cubes_properties[depth].edge_length / 4.)));
  370. assert(!cube->children[j] || cube->children[j]->center.isApprox(cntr));
  371. c[i] = cntr;
  372. }
  373. std::array<Vec3d, 10> dirs = {
  374. c[1] - c[0], c[2] - c[0], c[3] - c[1], c[3] - c[2], c[3] - c[0],
  375. c[5] - c[4], c[6] - c[4], c[7] - c[5], c[7] - c[6], c[7] - c[4]
  376. };
  377. assert(std::abs(dirs[4].z()) < 0.005);
  378. assert(std::abs(dirs[9].z()) < 0.005);
  379. assert(dirs[0].isApprox(dirs[3]));
  380. assert(dirs[1].isApprox(dirs[2]));
  381. assert(dirs[5].isApprox(dirs[8]));
  382. assert(dirs[6].isApprox(dirs[7]));
  383. Vec3d line_dir = Vec3d(line_to.x() - line_from.x(), line_to.y() - line_from.y(), 0.).normalized();
  384. for (auto& dir : dirs) {
  385. double d = dir.normalized().dot(line_dir);
  386. assert(d > 0.7);
  387. }
  388. return true;
  389. }
  390. #endif // NDEBUG
  391. static void generate_infill_lines_recursive(
  392. FillContext &context,
  393. const Cube *cube,
  394. // Address of this wall in the octree, used to address context.temp_lines.
  395. int address,
  396. int depth)
  397. {
  398. assert(cube != nullptr);
  399. const std::vector<CubeProperties> &cubes_properties = context.cubes_properties;
  400. const double z_diff = context.z_position - cube->center.z();
  401. const double z_diff_abs = std::abs(z_diff);
  402. if (z_diff_abs > cubes_properties[depth].height / 2.)
  403. return;
  404. if (z_diff_abs < cubes_properties[depth].line_z_distance) {
  405. // Discretize a single wall splitting the cube into two.
  406. const double zdist = cubes_properties[depth].line_z_distance;
  407. Vec2d from(
  408. 0.5 * cubes_properties[depth].diagonal_length * (zdist - z_diff_abs) / zdist,
  409. cubes_properties[depth].line_xy_distance - (zdist + z_diff) / sqrt(2.));
  410. Vec2d to(-from.x(), from.y());
  411. from = context.rotate(from);
  412. to = context.rotate(to);
  413. // Relative to cube center
  414. const Vec2d offset(cube->center.x(), cube->center.y());
  415. from += offset;
  416. to += offset;
  417. // Verify that the traversal order of the octree children matches the line direction,
  418. // therefore the infill line may get extended with O(1) time & space complexity.
  419. assert(verify_traversal_order(context, cube, depth, from, to));
  420. // Either extend an existing line or start a new one.
  421. Line &last_line = context.temp_lines[address];
  422. Line new_line(Point::new_scale(from), Point::new_scale(to));
  423. if (last_line.a.x() == std::numeric_limits<coord_t>::max()) {
  424. last_line.a = new_line.a;
  425. } else if ((new_line.a - last_line.b).cwiseAbs().maxCoeff() > 1000) { // SCALED_EPSILON is 100 and it is not enough
  426. context.output_lines.emplace_back(last_line);
  427. last_line.a = new_line.a;
  428. }
  429. last_line.b = new_line.b;
  430. }
  431. // left child index
  432. address = address * 2 + 1;
  433. -- depth;
  434. size_t i = 0;
  435. for (const int child_idx : context.traversal_order) {
  436. const Cube *child = cube->children[child_idx];
  437. if (child != nullptr)
  438. generate_infill_lines_recursive(context, child, address, depth);
  439. if (++ i == 4)
  440. // right child index
  441. ++ address;
  442. }
  443. }
  444. #ifndef NDEBUG
  445. // #define ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  446. #endif
  447. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  448. static void export_infill_lines_to_svg(const ExPolygon &expoly, const Polylines &polylines, const std::string &path, const Points &pts = Points())
  449. {
  450. BoundingBox bbox = get_extents(expoly);
  451. bbox.offset(scale_(3.));
  452. ::Slic3r::SVG svg(path, bbox);
  453. svg.draw(expoly);
  454. svg.draw_outline(expoly, "green");
  455. svg.draw(polylines, "red");
  456. static constexpr double trim_length = scale_(0.4);
  457. for (Polyline polyline : polylines) {
  458. if (! polyline.empty()) {
  459. Vec2d a = polyline.points.front().cast<double>();
  460. Vec2d d = polyline.points.back().cast<double>();
  461. if (polyline.size() == 2) {
  462. Vec2d v = d - a;
  463. double l = v.norm();
  464. if (l > 2. * trim_length) {
  465. a += v * trim_length / l;
  466. d -= v * trim_length / l;
  467. polyline.points.front() = a.cast<coord_t>();
  468. polyline.points.back() = d.cast<coord_t>();
  469. } else
  470. polyline.points.clear();
  471. } else if (polyline.size() > 2) {
  472. Vec2d b = polyline.points[1].cast<double>();
  473. Vec2d c = polyline.points[polyline.points.size() - 2].cast<double>();
  474. Vec2d v = b - a;
  475. double l = v.norm();
  476. if (l > trim_length) {
  477. a += v * trim_length / l;
  478. polyline.points.front() = a.cast<coord_t>();
  479. } else
  480. polyline.points.erase(polyline.points.begin());
  481. v = d - c;
  482. l = v.norm();
  483. if (l > trim_length)
  484. polyline.points.back() = (d - v * trim_length / l).cast<coord_t>();
  485. else
  486. polyline.points.pop_back();
  487. }
  488. svg.draw(polyline, "black");
  489. }
  490. }
  491. svg.draw(pts, "magenta");
  492. }
  493. #endif /* ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT */
  494. // Representing a T-joint (in general case) between two infill lines
  495. // (between one end point of intersect_pl/intersect_line and
  496. struct Intersection
  497. {
  498. // Closest line to intersect_point.
  499. const Line *closest_line;
  500. // The line for which is computed closest line from intersect_point to closest_line
  501. const Line *intersect_line;
  502. // Pointer to the polyline from which is computed closest_line
  503. Polyline *intersect_pl;
  504. // Point for which is computed closest line (closest_line)
  505. Point intersect_point;
  506. // Indicate if intersect_point is the first or the last point of intersect_pl
  507. bool front;
  508. // Signum of intersect_line_dir.cross(closest_line.dir()):
  509. bool left;
  510. // Indication if this intersection has been proceed
  511. bool used = false;
  512. bool fresh() const throw() { return ! used && ! intersect_pl->empty(); }
  513. Intersection(const Line &closest_line, const Line &intersect_line, Polyline *intersect_pl, const Point &intersect_point, bool front) :
  514. closest_line(&closest_line), intersect_line(&intersect_line), intersect_pl(intersect_pl), intersect_point(intersect_point), front(front)
  515. {
  516. // Calculate side of this intersection line of the closest line.
  517. Vec2d v1((this->closest_line->b - this->closest_line->a).cast<double>());
  518. Vec2d v2(this->intersect_line_dir());
  519. #ifndef NDEBUG
  520. {
  521. Vec2d v1n = v1.normalized();
  522. Vec2d v2n = v2.normalized();
  523. double c = cross2(v1n, v2n);
  524. assert(std::abs(c) > sin(M_PI / 12.));
  525. }
  526. #endif // NDEBUG
  527. this->left = cross2(v1, v2) > 0.;
  528. }
  529. std::optional<Line> other_hook() const {
  530. std::optional<Line> out;
  531. const Points &pts = intersect_pl->points;
  532. if (pts.size() >= 3)
  533. out = this->front ? Line(pts[1], pts[2]) : Line(pts[pts.size() - 2], pts[pts.size() - 3]);
  534. return out;
  535. }
  536. bool other_hook_intersects(const Line &l, Point &pt) {
  537. std::optional<Line> h = other_hook();
  538. return h && h->intersection(l, &pt);
  539. }
  540. bool other_hook_intersects(const Line &l) { Point pt; return this->other_hook_intersects(l, pt); }
  541. // Direction to intersect_point.
  542. Vec2d intersect_line_dir() const throw() {
  543. return (this->intersect_point == intersect_line->a ? intersect_line->b - intersect_line->a : intersect_line->a - intersect_line->b).cast<double>();
  544. }
  545. };
  546. static inline Intersection* get_nearest_intersection(std::vector<std::pair<Intersection*, double>>& intersect_line, const size_t first_idx)
  547. {
  548. assert(intersect_line.size() >= 2);
  549. bool take_next = false;
  550. if (first_idx == 0)
  551. take_next = true;
  552. else if (first_idx + 1 == intersect_line.size())
  553. take_next = false;
  554. else {
  555. // Has both prev and next.
  556. const std::pair<Intersection*, double> &ithis = intersect_line[first_idx];
  557. const std::pair<Intersection*, double> &iprev = intersect_line[first_idx - 1];
  558. const std::pair<Intersection*, double> &inext = intersect_line[first_idx + 1];
  559. take_next = iprev.first->fresh() && inext.first->fresh() ?
  560. inext.second - ithis.second < ithis.second - iprev.second :
  561. inext.first->fresh();
  562. }
  563. return intersect_line[take_next ? first_idx + 1 : first_idx - 1].first;
  564. }
  565. // Create a line representing the anchor aka hook extrusion based on line_to_offset
  566. // translated in the direction of the intersection line (intersection.intersect_line).
  567. static Line create_offset_line(Line offset_line, const Intersection &intersection, const coordf_t scaled_offset)
  568. {
  569. offset_line.translate((perp(intersection.closest_line->vector().cast<double>().normalized()) * (intersection.left ? scaled_offset : - scaled_offset)).cast<coord_t>());
  570. // Extend the line by a small value to guarantee a collision with adjacent lines
  571. offset_line.extend(coordf_t(coord_t(scaled_offset * 1.16))); // / cos(PI/6)
  572. return offset_line;
  573. }
  574. namespace bg = boost::geometry;
  575. namespace bgm = boost::geometry::model;
  576. namespace bgi = boost::geometry::index;
  577. // float is needed because for coord_t bgi::intersects throws "bad numeric conversion: positive overflow"
  578. using rtree_point_t = bgm::point<float, 2, boost::geometry::cs::cartesian>;
  579. using rtree_segment_t = bgm::segment<rtree_point_t>;
  580. using rtree_t = bgi::rtree<std::pair<rtree_segment_t, size_t>, bgi::rstar<16, 4>>;
  581. static inline rtree_point_t mk_rtree_point(const Point &pt) {
  582. return rtree_point_t(float(pt.x()), float(pt.y()));
  583. }
  584. static inline rtree_segment_t mk_rtree_seg(const Point &a, const Point &b) {
  585. return { mk_rtree_point(a), mk_rtree_point(b) };
  586. }
  587. static inline rtree_segment_t mk_rtree_seg(const Line &l) {
  588. return mk_rtree_seg(l.a, l.b);
  589. }
  590. // Create a hook based on hook_line and append it to the begin or end of the polyline in the intersection
  591. static void add_hook(
  592. const Intersection &intersection, const double scaled_offset,
  593. const coordf_t hook_length, double scaled_trim_distance,
  594. const rtree_t &rtree, const Lines &lines_src)
  595. {
  596. if (hook_length < SCALED_EPSILON)
  597. // Ignore open hooks.
  598. return;
  599. #ifndef NDEBUG
  600. {
  601. const Vec2d v = (intersection.closest_line->b - intersection.closest_line->a).cast<double>();
  602. const Vec2d va = (intersection.intersect_point - intersection.closest_line->a).cast<double>();
  603. const double l2 = v.squaredNorm(); // avoid a sqrt
  604. assert(l2 > 0.);
  605. const double t = va.dot(v) / l2;
  606. assert(t > 0. && t < 1.);
  607. const double d = (t * v - va).norm();
  608. assert(d < 1000.);
  609. }
  610. #endif // NDEBUG
  611. // Trim the hook start by the infill line it will connect to.
  612. Point hook_start;
  613. [[maybe_unused]] bool intersection_found = intersection.intersect_line->intersection(
  614. create_offset_line(*intersection.closest_line, intersection, scaled_offset),
  615. &hook_start);
  616. assert(intersection_found);
  617. std::optional<Line> other_hook = intersection.other_hook();
  618. Vec2d hook_vector_norm = intersection.closest_line->vector().cast<double>().normalized();
  619. // hook_vector is extended by the thickness of the infill line, so that a collision is found against
  620. // the infill centerline to be later trimmed by the thickened line.
  621. Vector hook_vector = ((hook_length + 1.16 * scaled_trim_distance) * hook_vector_norm).cast<coord_t>();
  622. Line hook_forward(hook_start, hook_start + hook_vector);
  623. auto filter_itself = [&intersection, &lines_src](const auto &item) { return item.second != (long unsigned int)(intersection.intersect_line - lines_src.data()); };
  624. std::vector<std::pair<rtree_segment_t, size_t>> hook_intersections;
  625. rtree.query(bgi::intersects(mk_rtree_seg(hook_forward)) && bgi::satisfies(filter_itself), std::back_inserter(hook_intersections));
  626. Point self_intersection_point;
  627. bool self_intersection = other_hook && other_hook->intersection(hook_forward, &self_intersection_point);
  628. // Find closest intersection of a line segment starting with pt pointing in dir
  629. // with any of the hook_intersections, returns Euclidian distance.
  630. // dir is normalized.
  631. auto max_hook_length = [hook_length, scaled_trim_distance, &lines_src](
  632. const Vec2d &pt, const Vec2d &dir,
  633. const std::vector<std::pair<rtree_segment_t, size_t>> &hook_intersections,
  634. bool self_intersection, const std::optional<Line> &self_intersection_line, const Point &self_intersection_point) {
  635. // No hook is longer than hook_length, there shouldn't be any intersection closer than that.
  636. auto max_length = hook_length;
  637. auto update_max_length = [&max_length](double d) {
  638. if (d < max_length)
  639. max_length = d;
  640. };
  641. // Shift the trimming point away from the colliding thick line.
  642. auto shift_from_thick_line = [&dir, scaled_trim_distance](const Vec2d& dir2) {
  643. return scaled_trim_distance * std::abs(cross2(dir, dir2.normalized()));
  644. };
  645. for (const auto &hook_intersection : hook_intersections) {
  646. const rtree_segment_t &segment = hook_intersection.first;
  647. // Segment start and end points, segment vector.
  648. Vec2d pt2(bg::get<0, 0>(segment), bg::get<0, 1>(segment));
  649. Vec2d dir2 = Vec2d(bg::get<1, 0>(segment), bg::get<1, 1>(segment)) - pt2;
  650. // Find intersection of (pt, dir) with (pt2, dir2), where dir is normalized.
  651. double denom = cross2(dir, dir2);
  652. assert(std::abs(denom) > EPSILON);
  653. double t = cross2(pt2 - pt, dir2) / denom;
  654. if (hook_intersection.second < lines_src.size())
  655. // Trimming by another infill line. Reduce overlap.
  656. t -= shift_from_thick_line(dir2);
  657. update_max_length(t);
  658. }
  659. if (self_intersection) {
  660. double t = (self_intersection_point.cast<double>() - pt).dot(dir) - shift_from_thick_line((*self_intersection_line).vector().cast<double>());
  661. max_length = std::min(max_length, t);
  662. }
  663. return std::max(0., max_length);
  664. };
  665. Vec2d hook_startf = hook_start.cast<double>();
  666. double hook_forward_max_length = max_hook_length(hook_startf, hook_vector_norm, hook_intersections, self_intersection, other_hook, self_intersection_point);
  667. double hook_backward_max_length = 0.;
  668. if (hook_forward_max_length < hook_length - SCALED_EPSILON) {
  669. // Try the other side.
  670. hook_intersections.clear();
  671. Line hook_backward(hook_start, hook_start - hook_vector);
  672. rtree.query(bgi::intersects(mk_rtree_seg(hook_backward)) && bgi::satisfies(filter_itself), std::back_inserter(hook_intersections));
  673. self_intersection = other_hook && other_hook->intersection(hook_backward, &self_intersection_point);
  674. hook_backward_max_length = max_hook_length(hook_startf, - hook_vector_norm, hook_intersections, self_intersection, other_hook, self_intersection_point);
  675. }
  676. // Take the longer hook.
  677. Vec2d hook_dir = (hook_forward_max_length > hook_backward_max_length ? hook_forward_max_length : - hook_backward_max_length) * hook_vector_norm;
  678. Point hook_end = hook_start + hook_dir.cast<coord_t>();
  679. Points &pl = intersection.intersect_pl->points;
  680. if (intersection.front) {
  681. pl.front() = hook_start;
  682. pl.emplace(pl.begin(), hook_end);
  683. } else {
  684. pl.back() = hook_start;
  685. pl.emplace_back(hook_end);
  686. }
  687. }
  688. #ifndef NDEBUG
  689. bool validate_intersection_t_joint(const Intersection &intersection)
  690. {
  691. const Vec2d v = (intersection.closest_line->b - intersection.closest_line->a).cast<double>();
  692. const Vec2d va = (intersection.intersect_point - intersection.closest_line->a).cast<double>();
  693. const double l2 = v.squaredNorm(); // avoid a sqrt
  694. assert(l2 > 0.);
  695. const double t = va.dot(v);
  696. assert(t > SCALED_EPSILON && t < l2 - SCALED_EPSILON);
  697. const double d = ((t / l2) * v - va).norm();
  698. assert(d < 1000.);
  699. return true;
  700. }
  701. bool validate_intersections(const std::vector<Intersection> &intersections)
  702. {
  703. for (const Intersection& intersection : intersections)
  704. assert(validate_intersection_t_joint(intersection));
  705. return true;
  706. }
  707. #endif // NDEBUG
  708. static Polylines connect_lines_using_hooks(Polylines &&lines, const ExPolygon &boundary, const double spacing, const coordf_t hook_length, const coordf_t hook_length_max)
  709. {
  710. rtree_t rtree;
  711. size_t poly_idx = 0;
  712. // 19% overlap, slightly lower than the allowed overlap in Fill::connect_infill()
  713. const float scaled_offset = float(scale_(spacing) * 0.81);
  714. // 25% overlap
  715. const float scaled_trim_distance = float(scale_(spacing) * 0.5 * 0.75);
  716. // Keeping the vector of closest points outside the loop, so the vector does not need to be reallocated.
  717. std::vector<std::pair<rtree_segment_t, size_t>> closest;
  718. // Pairs of lines touching at one end point. The pair is sorted to make the end point connection test symmetric.
  719. std::vector<std::pair<const Polyline*, const Polyline*>> lines_touching_at_endpoints;
  720. {
  721. // Insert infill lines into rtree, merge close collinear segments split by the infill boundary,
  722. // collect lines_touching_at_endpoints.
  723. double r2_close = Slic3r::sqr(1200.);
  724. for (Polyline &poly : lines) {
  725. assert(poly.points.size() == 2);
  726. if (&poly != lines.data()) {
  727. // Join collinear segments separated by a tiny gap. These gaps were likely created by clipping the infill lines with a concave dent in an infill boundary.
  728. auto collinear_segment = [&rtree, &closest, &lines, &lines_touching_at_endpoints, r2_close](const Point& pt, const Point& pt_other, const Polyline* polyline) -> std::pair<Polyline*, bool> {
  729. closest.clear();
  730. rtree.query(bgi::nearest(mk_rtree_point(pt), 1), std::back_inserter(closest));
  731. const Polyline *other = &lines[closest.front().second];
  732. double dist2_front = (other->points.front() - pt).cast<double>().squaredNorm();
  733. double dist2_back = (other->points.back() - pt).cast<double>().squaredNorm();
  734. double dist2_min = std::min(dist2_front, dist2_back);
  735. if (dist2_min < r2_close) {
  736. // Don't connect the segments in an opposite direction.
  737. double dist2_min_other = std::min((other->points.front() - pt_other).cast<double>().squaredNorm(), (other->points.back() - pt_other).cast<double>().squaredNorm());
  738. if (dist2_min_other > dist2_min) {
  739. // End points of the two lines are very close, they should have been merged together if they are collinear.
  740. Vec2d v1 = (pt_other - pt).cast<double>();
  741. Vec2d v2 = (other->points.back() - other->points.front()).cast<double>();
  742. Vec2d v1n = v1.normalized();
  743. Vec2d v2n = v2.normalized();
  744. // The vectors must not be collinear.
  745. double d = v1n.dot(v2n);
  746. if (std::abs(d) > 0.99f) {
  747. // Lines are collinear, merge them.
  748. rtree.remove(closest.front());
  749. return std::make_pair(const_cast<Polyline*>(other), dist2_min == dist2_front);
  750. } else {
  751. if (polyline > other)
  752. std::swap(polyline, other);
  753. lines_touching_at_endpoints.emplace_back(polyline, other);
  754. }
  755. }
  756. }
  757. return std::make_pair(static_cast<Polyline*>(nullptr), false);
  758. };
  759. auto collinear_front = collinear_segment(poly.points.front(), poly.points.back(), &poly);
  760. auto collinear_back = collinear_segment(poly.points.back(), poly.points.front(), &poly);
  761. assert(! collinear_front.first || ! collinear_back.first || collinear_front.first != collinear_back.first);
  762. if (collinear_front.first) {
  763. Polyline &other = *collinear_front.first;
  764. assert(&other != &poly);
  765. poly.points.front() = collinear_front.second ? other.points.back() : other.points.front();
  766. other.points.clear();
  767. }
  768. if (collinear_back.first) {
  769. Polyline &other = *collinear_back.first;
  770. assert(&other != &poly);
  771. poly.points.back() = collinear_back.second ? other.points.back() : other.points.front();
  772. other.points.clear();
  773. }
  774. }
  775. rtree.insert(std::make_pair(mk_rtree_seg(poly.points.front(), poly.points.back()), poly_idx++));
  776. }
  777. }
  778. // Convert input polylines to lines_src after the colinear segments were merged.
  779. Lines lines_src;
  780. lines_src.reserve(lines.size());
  781. std::transform(lines.begin(), lines.end(), std::back_inserter(lines_src), [](const Polyline &pl) {
  782. return pl.empty() ? Line(Point(0, 0), Point(0, 0)) : Line(pl.points.front(), pl.points.back()); });
  783. sort_remove_duplicates(lines_touching_at_endpoints);
  784. std::vector<Intersection> intersections;
  785. {
  786. // Minimum lenght of an infill line to anchor. Very short lines cannot be trimmed from both sides,
  787. // it does not help to anchor extremely short infill lines, it consumes too much plastic while not adding
  788. // to the object rigidity.
  789. assert(scaled_offset > scaled_trim_distance);
  790. const double line_len_threshold_drop_both_sides = scaled_offset * (2. / cos(PI / 6.) + 0.5) + SCALED_EPSILON;
  791. const double line_len_threshold_anchor_both_sides = line_len_threshold_drop_both_sides + scaled_offset;
  792. const double line_len_threshold_drop_single_side = scaled_offset * (1. / cos(PI / 6.) + 1.5) + SCALED_EPSILON;
  793. const double line_len_threshold_anchor_single_side = line_len_threshold_drop_single_side + scaled_offset;
  794. for (size_t line_idx = 0; line_idx < lines.size(); ++ line_idx) {
  795. Polyline &line = lines[line_idx];
  796. if (line.points.empty())
  797. continue;
  798. Point &front_point = line.points.front();
  799. Point &back_point = line.points.back();
  800. // Find the nearest line from the start point of the line.
  801. std::optional<size_t> tjoint_front, tjoint_back;
  802. {
  803. auto has_tjoint = [&closest, line_idx, &rtree, &lines, &lines_src](const Point &pt) {
  804. auto filter_t_joint = [line_idx, &lines_src, pt](const auto &item) {
  805. if (item.second != line_idx) {
  806. // Verify that the point projects onto the line.
  807. const Line &line = lines_src[item.second];
  808. const Vec2d v = (line.b - line.a).cast<double>();
  809. const Vec2d va = (pt - line.a).cast<double>();
  810. const double l2 = v.squaredNorm(); // avoid a sqrt
  811. if (l2 > 0.) {
  812. const double t = va.dot(v);
  813. return t > SCALED_EPSILON && t < l2 - SCALED_EPSILON;
  814. }
  815. }
  816. return false;
  817. };
  818. closest.clear();
  819. rtree.query(bgi::nearest(mk_rtree_point(pt), 1) && bgi::satisfies(filter_t_joint), std::back_inserter(closest));
  820. std::optional<size_t> out;
  821. if (! closest.empty()) {
  822. const Polyline &pl = lines[closest.front().second];
  823. if (pl.points.empty()) {
  824. // The closest infill line was already dropped as it was too short.
  825. // Such an infill line should not make a T-joint anyways.
  826. #if 0 // #ifndef NDEBUG
  827. const auto &seg = closest.front().first;
  828. struct Linef { Vec2d a; Vec2d b; };
  829. Linef l { { bg::get<0, 0>(seg), bg::get<0, 1>(seg) }, { bg::get<1, 0>(seg), bg::get<1, 1>(seg) } };
  830. assert(line_alg::distance_to_squared(l, Vec2d(pt.cast<double>())) > 1000 * 1000);
  831. #endif // NDEBUG
  832. } else if (pl.size() >= 2 &&
  833. //FIXME Hoping that pl is really a line, trimmed by a polygon using ClipperUtils. Sometimes Clipper leaves some additional collinear points on the polyline, let's hope it is all right.
  834. Line{ pl.front(), pl.back() }.distance_to_squared(pt) <= 1000 * 1000)
  835. out = closest.front().second;
  836. }
  837. return out;
  838. };
  839. // Refuse to create a T-joint if the infill lines touch at their ends.
  840. auto filter_end_point_connections = [&lines_touching_at_endpoints, &lines, &line](std::optional<size_t> in) {
  841. std::optional<size_t> out;
  842. if (in) {
  843. const Polyline *lo = &line;
  844. const Polyline *hi = &lines[*in];
  845. if (lo > hi)
  846. std::swap(lo, hi);
  847. if (! std::binary_search(lines_touching_at_endpoints.begin(), lines_touching_at_endpoints.end(), std::make_pair(lo, hi)))
  848. // Not an end-point connection, it is a valid T-joint.
  849. out = in;
  850. }
  851. return out;
  852. };
  853. tjoint_front = filter_end_point_connections(has_tjoint(front_point));
  854. tjoint_back = filter_end_point_connections(has_tjoint(back_point));
  855. }
  856. int num_tjoints = int(tjoint_front.has_value()) + int(tjoint_back.has_value());
  857. if (num_tjoints > 0) {
  858. double line_len = line.length();
  859. bool drop = false;
  860. bool anchor = false;
  861. if (num_tjoints == 1) {
  862. // Connected to perimeters on a single side only, connected to another infill line on the other side.
  863. drop = line_len < line_len_threshold_drop_single_side;
  864. anchor = line_len > line_len_threshold_anchor_single_side;
  865. } else {
  866. // Not connected to perimeters at all, connected to two infill lines.
  867. assert(num_tjoints == 2);
  868. drop = line_len < line_len_threshold_drop_both_sides;
  869. anchor = line_len > line_len_threshold_anchor_both_sides;
  870. }
  871. if (drop) {
  872. // Drop a very short line if connected to another infill line.
  873. // Lines shorter than spacing are skipped because it is needed to shrink a line by the value of spacing.
  874. // A shorter line than spacing could produce a degenerate polyline.
  875. line.points.clear();
  876. } else if (anchor) {
  877. if (tjoint_front) {
  878. // T-joint of line's front point with the 'closest' line.
  879. intersections.emplace_back(lines_src[*tjoint_front], lines_src[line_idx], &line, front_point, true);
  880. assert(validate_intersection_t_joint(intersections.back()));
  881. }
  882. if (tjoint_back) {
  883. // T-joint of line's back point with the 'closest' line.
  884. intersections.emplace_back(lines_src[*tjoint_back], lines_src[line_idx], &line, back_point, false);
  885. assert(validate_intersection_t_joint(intersections.back()));
  886. }
  887. } else {
  888. if (tjoint_front)
  889. // T joint at the front at a 60 degree angle, the line is very short.
  890. // Trim the front side.
  891. front_point += ((scaled_trim_distance * 1.155) * (back_point - front_point).cast<double>().normalized()).cast<coord_t>();
  892. if (tjoint_back)
  893. // T joint at the front at a 60 degree angle, the line is very short.
  894. // Trim the front side.
  895. back_point += ((scaled_trim_distance * 1.155) * (front_point - back_point).cast<double>().normalized()).cast<coord_t>();
  896. }
  897. }
  898. }
  899. // Remove those intersections, that point to a dropped line.
  900. for (auto it = intersections.begin(); it != intersections.end(); ) {
  901. assert(! lines[it->intersect_line - lines_src.data()].points.empty());
  902. if (lines[it->closest_line - lines_src.data()].points.empty()) {
  903. *it = intersections.back();
  904. intersections.pop_back();
  905. } else
  906. ++ it;
  907. }
  908. }
  909. assert(validate_intersections(intersections));
  910. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  911. static int iRun = 0;
  912. int iStep = 0;
  913. {
  914. Points pts;
  915. for (const Intersection &i : intersections)
  916. pts.emplace_back(i.intersect_point);
  917. export_infill_lines_to_svg(boundary, lines, debug_out_path("FillAdaptive-Tjoints-%d.svg", iRun++), pts);
  918. }
  919. #endif /* ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT */
  920. // Sort lexicographically by closest_line_idx and left/right orientation.
  921. std::sort(intersections.begin(), intersections.end(),
  922. [](const Intersection &i1, const Intersection &i2) {
  923. return (i1.closest_line == i2.closest_line) ?
  924. int(i1.left) < int(i2.left) :
  925. i1.closest_line < i2.closest_line;
  926. });
  927. std::vector<size_t> merged_with(lines.size());
  928. std::iota(merged_with.begin(), merged_with.end(), 0);
  929. // Appends the boundary polygon with all holes to rtree for detection to check whether hooks are not crossing the boundary
  930. {
  931. Point prev = boundary.contour.points.back();
  932. for (const Point &point : boundary.contour.points) {
  933. rtree.insert(std::make_pair(mk_rtree_seg(prev, point), poly_idx++));
  934. prev = point;
  935. }
  936. for (const Polygon &polygon : boundary.holes) {
  937. Point prev = polygon.points.back();
  938. for (const Point &point : polygon.points) {
  939. rtree.insert(std::make_pair(mk_rtree_seg(prev, point), poly_idx++));
  940. prev = point;
  941. }
  942. }
  943. }
  944. auto update_merged_polyline_idx = [&merged_with](size_t pl_idx) {
  945. // Update the polyline index to index which is merged
  946. for (size_t last = pl_idx;;) {
  947. size_t lower = merged_with[last];
  948. if (lower == last) {
  949. merged_with[pl_idx] = lower;
  950. return lower;
  951. }
  952. last = lower;
  953. }
  954. assert(false);
  955. return size_t(0);
  956. };
  957. auto update_merged_polyline = [&lines, update_merged_polyline_idx](Intersection& intersection) {
  958. // Update the polyline index to index which is merged
  959. size_t intersect_pl_idx = update_merged_polyline_idx(intersection.intersect_pl - lines.data());
  960. intersection.intersect_pl = &lines[intersect_pl_idx];
  961. // After polylines are merged, it is necessary to update "forward" based on if intersect_point is the first or the last point of intersect_pl.
  962. if (intersection.fresh()) {
  963. assert(intersection.intersect_pl->points.front() == intersection.intersect_point ||
  964. intersection.intersect_pl->points.back() == intersection.intersect_point);
  965. intersection.front = intersection.intersect_pl->points.front() == intersection.intersect_point;
  966. }
  967. };
  968. // Merge polylines touching at their ends. This should be a very rare case, but it happens surprisingly often.
  969. for (auto it = lines_touching_at_endpoints.rbegin(); it != lines_touching_at_endpoints.rend(); ++ it) {
  970. Polyline *pl1 = const_cast<Polyline*>(it->first);
  971. Polyline *pl2 = const_cast<Polyline*>(it->second);
  972. assert(pl1 < pl2);
  973. // pl1 was visited for the 1st time.
  974. // pl2 may have alread been merged with another polyline, even with this one.
  975. pl2 = &lines[update_merged_polyline_idx(pl2 - lines.data())];
  976. assert(pl1 <= pl2);
  977. // Avoid closing a loop, ignore dropped infill lines.
  978. if (pl1 != pl2 && ! pl1->points.empty() && ! pl2->points.empty()) {
  979. // Merge the polylines.
  980. assert(pl1 < pl2);
  981. assert(pl1->points.size() >= 2);
  982. assert(pl2->points.size() >= 2);
  983. double d11 = (pl1->points.front() - pl2->points.front()).cast<double>().squaredNorm();
  984. double d12 = (pl1->points.front() - pl2->points.back()) .cast<double>().squaredNorm();
  985. double d21 = (pl1->points.back() - pl2->points.front()).cast<double>().squaredNorm();
  986. double d22 = (pl1->points.back() - pl2->points.back()) .cast<double>().squaredNorm();
  987. double d1min = std::min(d11, d12);
  988. double d2min = std::min(d21, d22);
  989. if (d1min < d2min) {
  990. pl1->reverse();
  991. if (d12 == d1min)
  992. pl2->reverse();
  993. } else if (d22 == d2min)
  994. pl2->reverse();
  995. pl1->points.back() = (pl1->points.back() + pl2->points.front()) / 2;
  996. pl1->append(pl2->points.begin() + 1, pl2->points.end());
  997. pl2->points.clear();
  998. merged_with[pl2 - lines.data()] = pl1 - lines.data();
  999. }
  1000. }
  1001. // Keep intersect_line outside the loop, so it does not get reallocated.
  1002. std::vector<std::pair<Intersection*, double>> intersect_line;
  1003. for (size_t min_idx = 0; min_idx < intersections.size();) {
  1004. intersect_line.clear();
  1005. // All the nearest points (T-joints) ending at the same line are projected onto this line. Because of it, it can easily find the nearest point.
  1006. {
  1007. const Vec2d line_dir = intersections[min_idx].closest_line->vector().cast<double>();
  1008. size_t max_idx = min_idx;
  1009. for (; max_idx < intersections.size() &&
  1010. intersections[min_idx].closest_line == intersections[max_idx].closest_line &&
  1011. intersections[min_idx].left == intersections[max_idx].left;
  1012. ++ max_idx)
  1013. intersect_line.emplace_back(&intersections[max_idx], line_dir.dot(intersections[max_idx].intersect_point.cast<double>()));
  1014. min_idx = max_idx;
  1015. assert(intersect_line.size() > 0);
  1016. // Sort the intersections along line_dir.
  1017. std::sort(intersect_line.begin(), intersect_line.end(), [](const auto &i1, const auto &i2) { return i1.second < i2.second; });
  1018. }
  1019. if (intersect_line.size() == 1) {
  1020. // Simple case: The current intersection is the only one touching its adjacent line.
  1021. Intersection &first_i = *intersect_line.front().first;
  1022. update_merged_polyline(first_i);
  1023. if (first_i.fresh()) {
  1024. // Try to connect left or right. If not enough space for hook_length, take the longer side.
  1025. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1026. export_infill_lines_to_svg(boundary, lines, debug_out_path("FillAdaptive-add_hook0-pre-%d-%d.svg", iRun, iStep), { first_i.intersect_point });
  1027. #endif // ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1028. add_hook(first_i, scaled_offset, hook_length, scaled_trim_distance, rtree, lines_src);
  1029. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1030. export_infill_lines_to_svg(boundary, lines, debug_out_path("FillAdaptive-add_hook0-pre-%d-%d.svg", iRun, iStep), { first_i.intersect_point });
  1031. ++ iStep;
  1032. #endif // ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1033. first_i.used = true;
  1034. }
  1035. continue;
  1036. }
  1037. for (size_t first_idx = 0; first_idx < intersect_line.size(); ++ first_idx) {
  1038. Intersection &first_i = *intersect_line[first_idx].first;
  1039. update_merged_polyline(first_i);
  1040. if (! first_i.fresh())
  1041. // The intersection has been processed, or the polyline has been merged to another polyline.
  1042. continue;
  1043. // Get the previous or next intersection on the same line, pick the closer one.
  1044. if (first_idx > 0)
  1045. update_merged_polyline(*intersect_line[first_idx - 1].first);
  1046. if (first_idx + 1 < intersect_line.size())
  1047. update_merged_polyline(*intersect_line[first_idx + 1].first);
  1048. Intersection &nearest_i = *get_nearest_intersection(intersect_line, first_idx);
  1049. assert(first_i.closest_line == nearest_i.closest_line);
  1050. assert(first_i.intersect_line != nearest_i.intersect_line);
  1051. assert(first_i.intersect_line != first_i.closest_line);
  1052. assert(nearest_i.intersect_line != first_i.closest_line);
  1053. // A line between two intersections points
  1054. Line offset_line = create_offset_line(Line(first_i.intersect_point, nearest_i.intersect_point), first_i, scaled_offset);
  1055. // Check if both intersections lie on the offset_line and simultaneously get their points of intersecting.
  1056. // These points are used as start and end of the hook
  1057. Point first_i_point, nearest_i_point;
  1058. bool could_connect = false;
  1059. if (nearest_i.fresh()) {
  1060. could_connect = first_i.intersect_line->intersection(offset_line, &first_i_point) &&
  1061. nearest_i.intersect_line->intersection(offset_line, &nearest_i_point);
  1062. assert(could_connect);
  1063. }
  1064. Points &first_points = first_i.intersect_pl->points;
  1065. Points &second_points = nearest_i.intersect_pl->points;
  1066. could_connect &= (nearest_i_point - first_i_point).cast<double>().squaredNorm() <= Slic3r::sqr(hook_length_max);
  1067. if (could_connect) {
  1068. // Both intersections are so close that their polylines can be connected.
  1069. // Verify that no other infill line intersects this anchor line.
  1070. closest.clear();
  1071. rtree.query(
  1072. bgi::intersects(mk_rtree_seg(first_i_point, nearest_i_point)) &&
  1073. bgi::satisfies([&first_i, &nearest_i, &lines_src](const auto &item)
  1074. { return item.second != (long unsigned int)(first_i.intersect_line - lines_src.data())
  1075. && item.second != (long unsigned int)(nearest_i.intersect_line - lines_src.data()); }),
  1076. std::back_inserter(closest));
  1077. could_connect = closest.empty();
  1078. #if 0
  1079. // Avoid self intersections. Maybe it is better to trim the self intersection after the connection?
  1080. if (could_connect && first_i.intersect_pl != nearest_i.intersect_pl) {
  1081. Line l(first_i_point, nearest_i_point);
  1082. could_connect = ! first_i.other_hook_intersects(l) && ! nearest_i.other_hook_intersects(l);
  1083. }
  1084. #endif
  1085. }
  1086. bool connected = false;
  1087. if (could_connect) {
  1088. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1089. export_infill_lines_to_svg(boundary, lines, debug_out_path("FillAdaptive-connecting-pre-%d-%d.svg", iRun, iStep), { first_i.intersect_point, nearest_i.intersect_point });
  1090. #endif // ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1091. // No other infill line intersects this anchor line. Extrude it as a whole.
  1092. if (first_i.intersect_pl == nearest_i.intersect_pl) {
  1093. // Both intersections are on the same polyline, that means a loop is being closed.
  1094. assert(first_i.front != nearest_i.front);
  1095. if (! first_i.front)
  1096. std::swap(first_i_point, nearest_i_point);
  1097. first_points.front() = first_i_point;
  1098. first_points.back() = nearest_i_point;
  1099. //FIXME trim the end of a closed loop a bit?
  1100. first_points.emplace(first_points.begin(), nearest_i_point);
  1101. } else {
  1102. // Both intersections are on different polylines
  1103. Line l(first_i_point, nearest_i_point);
  1104. l.translate((perp(first_i.closest_line->vector().cast<double>().normalized()) * (first_i.left ? scaled_trim_distance : - scaled_trim_distance)).cast<coord_t>());
  1105. Point pt_start, pt_end;
  1106. bool trim_start = first_i .intersect_pl->points.size() == 3 && first_i .other_hook_intersects(l, pt_start);
  1107. bool trim_end = nearest_i.intersect_pl->points.size() == 3 && nearest_i.other_hook_intersects(l, pt_end);
  1108. first_points.reserve(first_points.size() + second_points.size());
  1109. if (first_i.front)
  1110. std::reverse(first_points.begin(), first_points.end());
  1111. if (trim_start)
  1112. first_points.front() = pt_start;
  1113. first_points.back() = first_i_point;
  1114. first_points.emplace_back(nearest_i_point);
  1115. if (nearest_i.front)
  1116. first_points.insert(first_points.end(), second_points.begin() + 1, second_points.end());
  1117. else
  1118. first_points.insert(first_points.end(), second_points.rbegin() + 1, second_points.rend());
  1119. if (trim_end)
  1120. first_points.back() = pt_end;
  1121. // Keep the polyline at the lower index slot.
  1122. if (first_i.intersect_pl < nearest_i.intersect_pl) {
  1123. second_points.clear();
  1124. merged_with[nearest_i.intersect_pl - lines.data()] = first_i.intersect_pl - lines.data();
  1125. } else {
  1126. second_points = std::move(first_points);
  1127. first_points.clear();
  1128. merged_with[first_i.intersect_pl - lines.data()] = nearest_i.intersect_pl - lines.data();
  1129. }
  1130. }
  1131. nearest_i.used = true;
  1132. connected = true;
  1133. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1134. export_infill_lines_to_svg(boundary, lines, debug_out_path("FillAdaptive-connecting-post-%d-%d.svg", iRun, iStep), { first_i.intersect_point, nearest_i.intersect_point });
  1135. #endif // ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1136. }
  1137. if (! connected) {
  1138. // Try to connect left or right. If not enough space for hook_length, take the longer side.
  1139. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1140. export_infill_lines_to_svg(boundary, lines, debug_out_path("FillAdaptive-add_hook-pre-%d-%d.svg", iRun, iStep), { first_i.intersect_point });
  1141. #endif // ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1142. add_hook(first_i, scaled_offset, hook_length, scaled_trim_distance, rtree, lines_src);
  1143. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1144. export_infill_lines_to_svg(boundary, lines, debug_out_path("FillAdaptive-add_hook-post-%d-%d.svg", iRun, iStep), { first_i.intersect_point });
  1145. #endif // ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1146. }
  1147. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1148. ++ iStep;
  1149. #endif // ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1150. first_i.used = true;
  1151. }
  1152. }
  1153. Polylines polylines_out;
  1154. polylines_out.reserve(polylines_out.size() + std::count_if(lines.begin(), lines.end(), [](const Polyline &pl) { return !pl.empty(); }));
  1155. for (Polyline &pl : lines)
  1156. if (!pl.empty()) polylines_out.emplace_back(std::move(pl));
  1157. return polylines_out;
  1158. }
  1159. #ifndef NDEBUG
  1160. bool has_no_collinear_lines(const Polylines &polylines)
  1161. {
  1162. // Create line end point lookup.
  1163. struct LineEnd {
  1164. LineEnd(const Polyline *line, bool start) : line(line), start(start) {}
  1165. const Polyline *line;
  1166. // Is it the start or end point?
  1167. bool start;
  1168. const Point& point() const { return start ? line->points.front() : line->points.back(); }
  1169. const Point& other_point() const { return start ? line->points.back() : line->points.front(); }
  1170. LineEnd other_end() const { return LineEnd(line, !start); }
  1171. Vec2d vec() const { return Vec2d((this->other_point() - this->point()).cast<double>()); }
  1172. bool operator==(const LineEnd &rhs) const { return this->line == rhs.line && this->start == rhs.start; }
  1173. };
  1174. struct LineEndAccessor {
  1175. const Point* operator()(const LineEnd &pt) const { return &pt.point(); }
  1176. };
  1177. typedef ClosestPointInRadiusLookup<LineEnd, LineEndAccessor> ClosestPointLookupType;
  1178. ClosestPointLookupType closest_end_point_lookup(coord_t(1001. * sqrt(2.)));
  1179. for (const Polyline& pl : polylines) {
  1180. // assert(pl.points.size() == 2);
  1181. auto line_start = LineEnd(&pl, true);
  1182. auto line_end = LineEnd(&pl, false);
  1183. auto assert_not_collinear = [&closest_end_point_lookup](const LineEnd &line_start) {
  1184. std::vector<std::pair<const LineEnd*, double>> hits = closest_end_point_lookup.find_all(line_start.point());
  1185. for (const std::pair<const LineEnd*, double> &hit : hits)
  1186. if ((line_start.point() - hit.first->point()).cwiseAbs().maxCoeff() <= 1000) {
  1187. // End points of the two lines are very close, they should have been merged together if they are collinear.
  1188. Vec2d v1 = line_start.vec();
  1189. Vec2d v2 = hit.first->vec();
  1190. Vec2d v1n = v1.normalized();
  1191. Vec2d v2n = v2.normalized();
  1192. // The vectors must not be collinear.
  1193. assert(std::abs(v1n.dot(v2n)) < cos(M_PI / 12.));
  1194. }
  1195. };
  1196. assert_not_collinear(line_start);
  1197. assert_not_collinear(line_end);
  1198. closest_end_point_lookup.insert(line_start);
  1199. closest_end_point_lookup.insert(line_end);
  1200. }
  1201. return true;
  1202. }
  1203. #endif
  1204. void Filler::_fill_surface_single(
  1205. const FillParams & params,
  1206. unsigned int thickness_layers,
  1207. const std::pair<float, Point> &direction,
  1208. ExPolygon expolygon,
  1209. Polylines &polylines_out) const
  1210. {
  1211. assert (this->adapt_fill_octree);
  1212. Polylines all_polylines;
  1213. {
  1214. // 3 contexts for three directions of infill lines
  1215. std::array<FillContext, 3> contexts {
  1216. FillContext { *adapt_fill_octree, this->z, 0 },
  1217. FillContext { *adapt_fill_octree, this->z, 1 },
  1218. FillContext { *adapt_fill_octree, this->z, 2 }
  1219. };
  1220. // Generate the infill lines along the octree cells, merge touching lines of the same direction.
  1221. size_t num_lines = 0;
  1222. for (auto &context : contexts) {
  1223. generate_infill_lines_recursive(context, adapt_fill_octree->root_cube, 0, int(adapt_fill_octree->cubes_properties.size()) - 1);
  1224. num_lines += context.output_lines.size() + context.temp_lines.size();
  1225. }
  1226. #if 0
  1227. // Collect the lines, trim them by the expolygon.
  1228. all_polylines.reserve(num_lines);
  1229. auto boundary = to_polygons(expolygon);
  1230. for (auto &context : contexts) {
  1231. Polylines lines;
  1232. lines.reserve(context.output_lines.size() + context.temp_lines.size());
  1233. std::transform(context.output_lines.begin(), context.output_lines.end(), std::back_inserter(lines), [](const Line& l) { return Polyline{ l.a, l.b }; });
  1234. for (const Line &l : context.temp_lines)
  1235. if (l.a.x() != std::numeric_limits<coord_t>::max())
  1236. lines.push_back({ l.a, l.b });
  1237. // Crop all polylines
  1238. append(all_polylines, intersection_pl(std::move(lines), boundary));
  1239. }
  1240. // assert(has_no_collinear_lines(all_polylines));
  1241. #else
  1242. // Collect the lines.
  1243. std::vector<Line> lines;
  1244. lines.reserve(num_lines);
  1245. for (auto &context : contexts) {
  1246. append(lines, context.output_lines);
  1247. for (const Line &line : context.temp_lines)
  1248. if (line.a.x() != std::numeric_limits<coord_t>::max())
  1249. lines.emplace_back(line);
  1250. }
  1251. // Convert lines to polylines.
  1252. all_polylines.reserve(lines.size());
  1253. std::transform(lines.begin(), lines.end(), std::back_inserter(all_polylines), [](const Line& l) { return Polyline{ l.a, l.b }; });
  1254. // Crop all polylines
  1255. all_polylines = intersection_pl(std::move(all_polylines), expolygon);
  1256. #endif
  1257. }
  1258. // After intersection_pl some polylines with only one line are split into more lines
  1259. for (Polyline &polyline : all_polylines) {
  1260. //FIXME assert that all the points are collinear and in between the start and end point.
  1261. if (polyline.points.size() > 2)
  1262. polyline.points.erase(polyline.points.begin() + 1, polyline.points.end() - 1);
  1263. }
  1264. // assert(has_no_collinear_lines(all_polylines));
  1265. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1266. {
  1267. static int iRun = 0;
  1268. export_infill_lines_to_svg(expolygon, all_polylines, debug_out_path("FillAdaptive-initial-%d.svg", iRun++));
  1269. }
  1270. #endif /* ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT */
  1271. const coordf_t hook_length = std::min<coordf_t>((coordf_t)std::numeric_limits<coord_t>::max(), scale_d(params.anchor_length));
  1272. const coordf_t hook_length_max = std::min<coordf_t>((coordf_t)std::numeric_limits<coord_t>::max(), scale_d(params.anchor_length_max));
  1273. Polylines all_polylines_with_hooks = all_polylines.size() > 1 ? connect_lines_using_hooks(std::move(all_polylines), expolygon, this->get_spacing(), hook_length, hook_length_max) : std::move(all_polylines);
  1274. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1275. {
  1276. static int iRun = 0;
  1277. export_infill_lines_to_svg(expolygon, all_polylines_with_hooks, debug_out_path("FillAdaptive-hooks-%d.svg", iRun++));
  1278. }
  1279. #endif /* ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT */
  1280. if (params.connection == InfillConnection::icNotConnected || all_polylines_with_hooks.size() <= 1)
  1281. append(polylines_out, chain_polylines(std::move(all_polylines_with_hooks)));
  1282. else
  1283. connect_infill(std::move(all_polylines_with_hooks), expolygon, polylines_out, scale_t(this->get_spacing()), params);
  1284. #ifdef ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT
  1285. {
  1286. static int iRun = 0;
  1287. export_infill_lines_to_svg(expolygon, polylines_out, debug_out_path("FillAdaptive-final-%d.svg", iRun ++));
  1288. }
  1289. #endif /* ADAPTIVE_CUBIC_INFILL_DEBUG_OUTPUT */
  1290. }
  1291. //static double bbox_max_radius(const BoundingBoxf3 &bbox, const Vec3d &center)
  1292. //{
  1293. // const auto p = (bbox.min - center);
  1294. // const auto s = bbox.size();
  1295. // double r2max = 0.;
  1296. // for (int i = 0; i < 8; ++ i)
  1297. // r2max = std::max(r2max, (p + Vec3d(s.x() * double(i & 1), s.y() * double(i & 2), s.z() * double(i & 4))).squaredNorm());
  1298. // return sqrt(r2max);
  1299. //}
  1300. static std::vector<CubeProperties> make_cubes_properties(double max_cube_edge_length, double line_spacing)
  1301. {
  1302. max_cube_edge_length += EPSILON;
  1303. std::vector<CubeProperties> cubes_properties;
  1304. for (double edge_length = line_spacing * 2.;; edge_length *= 2.)
  1305. {
  1306. CubeProperties props{};
  1307. props.edge_length = edge_length;
  1308. props.height = edge_length * sqrt(3);
  1309. props.diagonal_length = edge_length * sqrt(2);
  1310. props.line_z_distance = edge_length / sqrt(3);
  1311. props.line_xy_distance = edge_length / sqrt(6);
  1312. cubes_properties.emplace_back(props);
  1313. if (edge_length > max_cube_edge_length)
  1314. break;
  1315. }
  1316. return cubes_properties;
  1317. }
  1318. static inline bool is_overhang_triangle(const Vec3d &a, const Vec3d &b, const Vec3d &c, const Vec3d &up)
  1319. {
  1320. // Calculate triangle normal.
  1321. auto n = (b - a).cross(c - b);
  1322. return n.dot(up) > 0.707 * n.norm();
  1323. }
  1324. static void transform_center(Cube *current_cube, const Eigen::Matrix3d &rot)
  1325. {
  1326. #ifndef NDEBUG
  1327. current_cube->center_octree = current_cube->center;
  1328. #endif // NDEBUG
  1329. current_cube->center = rot * current_cube->center;
  1330. for (auto *child : current_cube->children)
  1331. if (child)
  1332. transform_center(child, rot);
  1333. }
  1334. OctreePtr build_octree(
  1335. // Mesh is rotated to the coordinate system of the octree.
  1336. const indexed_triangle_set &triangle_mesh,
  1337. // Overhang triangles extracted from fill surfaces with stInternalBridge type,
  1338. // rotated to the coordinate system of the octree.
  1339. const std::vector<Vec3d> &overhang_triangles,
  1340. coordf_t line_spacing,
  1341. bool support_overhangs_only)
  1342. {
  1343. assert(line_spacing > 0);
  1344. assert(! std::isnan(line_spacing));
  1345. BoundingBox3Base<Vec3f> bbox(triangle_mesh.vertices);
  1346. Vec3d cube_center = bbox.center().cast<double>();
  1347. std::vector<CubeProperties> cubes_properties = make_cubes_properties(double(bbox.size().maxCoeff()), line_spacing);
  1348. auto octree = OctreePtr(new Octree(cube_center, cubes_properties));
  1349. if (cubes_properties.size() > 1) {
  1350. Octree *octree_ptr = octree.get();
  1351. double edge_length_half = 0.5 * cubes_properties.back().edge_length;
  1352. Vec3d diag_half(edge_length_half, edge_length_half, edge_length_half);
  1353. int max_depth = int(cubes_properties.size()) - 1;
  1354. auto process_triangle = [octree_ptr, max_depth, diag_half](const Vec3d &a, const Vec3d &b, const Vec3d &c) {
  1355. octree_ptr->insert_triangle(
  1356. a, b, c,
  1357. octree_ptr->root_cube,
  1358. BoundingBoxf3(octree_ptr->root_cube->center - diag_half, octree_ptr->root_cube->center + diag_half),
  1359. max_depth);
  1360. };
  1361. auto up_vector = support_overhangs_only ? Vec3d(transform_to_octree() * Vec3d(0., 0., 1.)) : Vec3d();
  1362. for (auto &tri : triangle_mesh.indices) {
  1363. auto a = triangle_mesh.vertices[tri[0]].cast<double>();
  1364. auto b = triangle_mesh.vertices[tri[1]].cast<double>();
  1365. auto c = triangle_mesh.vertices[tri[2]].cast<double>();
  1366. if (! support_overhangs_only || is_overhang_triangle(a, b, c, up_vector))
  1367. process_triangle(a, b, c);
  1368. }
  1369. for (size_t i = 0; i < overhang_triangles.size(); i += 3)
  1370. process_triangle(overhang_triangles[i], overhang_triangles[i + 1], overhang_triangles[i + 2]);
  1371. {
  1372. // Transform the octree to world coordinates to reduce computation when extracting infill lines.
  1373. auto rot = transform_to_world().toRotationMatrix();
  1374. transform_center(octree->root_cube, rot);
  1375. octree->origin = rot * octree->origin;
  1376. }
  1377. }
  1378. return octree;
  1379. }
  1380. void Octree::insert_triangle(const Vec3d &a, const Vec3d &b, const Vec3d &c, Cube *current_cube, const BoundingBoxf3 &current_bbox, int depth)
  1381. {
  1382. assert(current_cube);
  1383. assert(depth > 0);
  1384. --depth;
  1385. // Squared radius of a sphere around the child cube.
  1386. // const double r2_cube = Slic3r::sqr(0.5 * this->cubes_properties[depth].height + EPSILON);
  1387. for (size_t i = 0; i < 8; ++ i) {
  1388. const Vec3d &child_center_dir = child_centers[i];
  1389. // Calculate a slightly expanded bounding box of a child cube to cope with triangles touching a cube wall and other numeric errors.
  1390. // We will rather densify the octree a bit more than necessary instead of missing a triangle.
  1391. BoundingBoxf3 bbox;
  1392. for (int k = 0; k < 3; ++ k) {
  1393. if (child_center_dir[k] == -1.) {
  1394. bbox.min[k] = current_bbox.min[k];
  1395. bbox.max[k] = current_cube->center[k] + EPSILON;
  1396. } else {
  1397. bbox.min[k] = current_cube->center[k] - EPSILON;
  1398. bbox.max[k] = current_bbox.max[k];
  1399. }
  1400. }
  1401. Vec3d child_center = current_cube->center + (child_center_dir * (this->cubes_properties[depth].edge_length / 2.));
  1402. //if (dist2_to_triangle(a, b, c, child_center) < r2_cube) {
  1403. // dist2_to_triangle and r2_cube are commented out too.
  1404. if (triangle_AABB_intersects(a, b, c, bbox)) {
  1405. if (! current_cube->children[i])
  1406. current_cube->children[i] = this->pool.construct(child_center);
  1407. if (depth > 0)
  1408. this->insert_triangle(a, b, c, current_cube->children[i], bbox, depth);
  1409. }
  1410. }
  1411. }
  1412. } // namespace FillAdaptive
  1413. } // namespace Slic3r