Transforming assemblies are products that alter their shapes by re-assembling their parts. This idea is applied to a wide range of objects from folding gadgets as outdoor gear aimed at saving space, to robotic characters fighting in Hollywood films which drastically change their appearance. While the former type falls into a folding or packing problems, the latter requires a different viewpoint to be solved since the destination shape is not necessarily aiming at minimizing the occupation space. As a possible solution, this kind of deformation can be decomposed into segmentation of the shape to parts and parts matching. Segmentation is a general problem in shape modeling and numerous algorithms have been proposed for this. On the other hand, matching simultaneously multiple parts (many-to-many matching) has hardly been explored. This study develops a many-to-many matching algorithm for surface meshes of parts from two distinct destination shapes of a single transforming assembly. The proposed algorithm consists of a local geometry analysis and a global optimization of parts combination based on such analysis. For the local geometry analysis, the surface geometric feature is described by a local shape descriptor. Some vertices are detected as feature points by intrinsic shape signature (ISS) and the geometry at the feature points is expressed by the signature of histogram of orientation (SHOT). For all the combination of pairs from each destination shape, the number of feature points with similar descriptor values is counted. In the global optimization, the final matching is determined by the maximum weight matching on a complete bipartite graph whose nodes are the parts, and edges are weighted by the number of the feature points with similar descriptors. We present successful results for several examples to empirically show the effectiveness of the proposed algorithm.

1. [1] M. Sugi, Y. Shiomi, T. Okubo, H. Nagai, K. Inoue, and J. Ota, “Solution of the rectangular strip packing problem considering a 3-stage guillotine cutting constraint with finite slitter blades,” Int. J. Automation Technol., Vol.13, No.3, pp. 447-458, 2020.
2. [2] C. R. Collins and K. Stephenson, “A circle packing algorithm,” Computational Geometry, Vol.25, No.3, pp. 233-256, 2003.
3. [3] Y. Zhou, S. Sueda, W. Matusik, and A. Shamir, “Boxelization: folding 3D objects into boxes,” ACM Trans. on Graphics, Vol.33, No.4, 71, 2014.
4. [4] A. Shamir, “A survey on mesh segmentation techniques,” Computer Graphics Forum, Vol.27, No.6, pp. 1539-1556, 2008.
5. [5] R. S. V. Rodrigues, J. F. M. Morgado, and A. J. P. Gomes, “Part-based mesh segmentation: a survey,” Computer Graphics Forum, Vol.37, No.6, pp. 235-274, 2018.
6. [6] A. Jain, T. Thormählen, T. Ritschel, and H. P. Seidel, “Exploring shape variations by 3D-model decomposition and part-based recombination,” Computer Graphics Forum, Vol.31, No.2, pp. 631-640, 2012.
7. [7] A. Shamir, B. Bickel, and W. Matusik, “Computational tools for 3D printing,” ACM SIGGRAPH 2015 Courses, 9, 2016.
8. [8] C. Araujo, D. Cabiddu, M. Attene, M. Livesu, N. Vining, and A. Sheffer, “Surface2Volume: surface segmentation conforming assemblable volumetric partition,” ACM Trans. on Graphics, Vol.38, No.4, 80, 2019.
9. [9] P. Song, B. Deng, Z. Wang, Z. Dong, W. Li, C. W. Fu, and L. Liu, “CofiFab: coarse-to-fine fabrication of large 3D objects,” ACM Trans. on Graphics, Vol.35, No.4, 45, 2016.
10. [10] J. W. H. Tangelder and R. C. Veltkamp, “A survey of content based 3D shape retrieval methods,” Multimedia Tools and Applications, Vol.39, pp. 441-471, 2008.
11. [11] M. Eitz, R. Richter, T. Boubekeur, K. Hildebrand, and M. Alexa, “Sketch-based shape retrieval,” ACM Trans. on Graphics, Vol.31, No.4, 31, 2012.
12. [12] K. Lupinetti, F. Giannini, M. Monti, and J. P. Pernot, “Multi-criteria retrieval of CAD assembly models,” J. of Computational Design and Engineering, Vol.5, No.1, pp. 41-53, 2018.
13. [13] T. Miura and S. Kanai, “3D shape retrieval considering assembly structure,” Proc. of Asian Symp. for Precision Engineering and Nanotechnology, 2009.
14. [14] F. Tombari, S. Salti, and L. D. Stefano, “Performance Evaluation of 3D Keypoint Detectors,” Int. J. of Computer Vision, Vol.102, No.1, pp. 198-220, 2013.
15. [15] S. Salti, F. Tombari, and L. D. Stefano, “SHOT: unique signatures of histograms for surface and texture description,” Computer Vision and Image Understanding, Vol.125, pp. 251-264, 2014.
16. [16] A. Zaharescu, E. Boyer, K. Varanasi, and R. Horaud, “Surface feature detection and description with applications to mesh matching,” Proc. of 2009 IEEE Conf. on Computer Vision and Pattern Recognition, pp. 373-380, 2009.
17. [17] A. Mian, M. Bennamoun, and R. Owens, “On the repeatability and quality of keypoints for local feature-based 3D object retrieval from cluttered scenes,” Int. J. of Computer Vision, Vol.89, No.2, pp. 348-361, 2010.
18. [18] Y. Zhong, “Intrinsic shape signatures: a shape descriptor for 3D object recognition,” Proc. of 2009 IEEE 12th Int. Conf. on Computer Vision Workshops, pp. 689-696, 2009.
19. [19] A. Neubeck and L. V. Gool, “Efficient Non-Maximum Suppression,” Proc. of 18th Int. Conf. on Pattern Recognition (ICPR’06), pp. 850-855, 2006.
20. [20] A. Johnson, “Spin-images: a representation for 3-D surface matching,” Ph.D. thesis, Carnegie Mellon University, CMU-RI-TR-97-47, 1997.
21. [21] R. B. Rusu, N. Blodow, and M. Beetz, “Fast point feature histograms (FPFH) for 3D registration,” Proc. of 2009 IEEE Int. Conf. on Robotics and Automation, pp. 3212-3217, 2009.
22. [22] H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, Vol.2, Nos.1-2, pp. 83-97, 1955.
23. [23] Y. Nagai, Y. Ohtake, and H. Suzuki, “SegMo: CT volume segmentation using a multi-level Morse complex,” Computer-Aided Design, Vol.107, pp. 23-36, 2019.