Nesting

«Подавляющее большинство задач инженерного и технологического проектирования, независимо от того, в какой сфере деятельности они возникают, характеризуется исключительной сложностью и обладает общими специфическими чертами, которые выводят исследователей за рамки классических математических теорий.» [Ю. Г. Стоян., Н. И. Гиль «Методы и алгоритмы размещения плоских геометрических объектов», Киев — 1976].

These days I found myself surrounded with NP-hard problems. In two dimensions, irregular shape nesting is NP-hard. Also, bend sequence simulation is NP-hard and it comes from the same application domain as nesting. If we increase the "blank's" dimension to three, we will encounter the 3D packing problem, which is also NP-hard [4]. Actually, it may seem that any nontrivial production task is NP-hard. Today let's discuss the 3D nesting problem as it feels appropriate to draw parallels between 2D and 3D nesting.

Probably the most intriguing approach has been reported by Lutters et al. [3]. With a doze of gamification, they attack nesting through the "Brazil Nut" approach, which is dropping the parts to a powder bed and literally seeing what happens next. Rigid body simulation not only makes this story fun, but also emphasizes one key property of the approach: at any stage of the nesting process the parts never geometrically penetrate each other. The employed collision boxes driven by the gravity and reaction forces just keep the simulated bodies away from each other and so it goes until equilibrium is reached. The problem with this approach is that it's not an optimization routine as such. There's no guarantee that the ultimate 3D layout will minimize the height of the stacked items.

Animation from the slide deck of Bullet "Bullet Physics Simulation: Introduction to rigid body dynamics and collision detection" by Erwin Coumans (do not forget to check slide notes).

Lutters et al. employ MATLAB for their simulations, but in C++ we can potentially use some fancy physics engine like Bullet. It should be noted that Bullet as a library is clean and concise, so such an exercise should not be too hard to conduct. But let's check what else do we have in the "state of the art" pool of knowledge.

Y. Yang et al. describe a method of 3D nesting based on voxelization [1]. By using the convexity props of the voxelized models, they try to find possible placements of parts in the 3D space. The layout of parts is chosen w.r.t. "rasterization" of the 3D space, which sounds like a smart idea as it avoids blind placements. Because of the employed convexity hints, the placed parts should not penetrate each other, although there is no physical constraint which would restrict them from doing so.

The final paper in my spontaneous review is by Yau and Hsu [2]. The approach is geometrically clear and conceptually straightforward: we utilize a global optimizer to put pieces in the target volume and verify collisions to penalize incorrect placements. Unlike solutions that prohibit [3] or limit the likelihood [1] of part penetrations, this one appears to be the most ignorant. We effectively seed the solution space with candidate placements and see if we've hit the jackpot. If not, rather than reseeding the search space (which would be the stupidest idea ever), we let a global optimizer to suggest something better.

The reviewed methods range in their attitude to part overlapping. Not letting parts go through each other resembles the motivation behind NFP in 2D nesting — we can do without it but then we have to take care of infeasible configurations. From this perspective, the bottom-left filling approach in 2D nesting is like the simulation-based approach in 3D.

I should have probably done my homework and checked the whole volume of studies by Chekanin (e.g., starting from this conference talk) who seems to have devoted his professional life to nesting. We might probably come back to his studies in the future, but here I mention these works mostly for completeness.

References

1. Yang, Y., Li, H., Zhang, K., Jia, X., Wang, G., & Liu, B. (2023). A 3D nesting method based on the convex-concave coding similarity of the voxelized model for additive manufacturing. Additive Manufacturing, 64 (January), 103429. https://doi.org/10.1016/j.addma.2023.103429 (full text).

2. Yau, H., & Hsu, C. (2022). Nesting of 3D irregular shaped objects applied to powder-based additive manufacturing. 1843–1858 (full text).

3. Lutters, E., Dam, D., & Faneker, T. (2014). 3D Nesting of Complex Shapes. December 2012. https://doi.org/10.1016/j.procir.2012.07.006 (full text).

4. Luiz J.P. Araujo et al. (2018). Analysis of irregular three-dimensional packing problems in additive manufacturing : a new taxonomy and dataset. https://doi.org/10.1080/00207543.2018.1534016 (full text).

Want to discuss this? Jump in to our forum.