A Distributed Model for Computing 3D Mesh Local Descriptors Based on k-Rings
DOI:
https://doi.org/10.26439/interfases2022.n015.5886Keywords:
3D local descriptor, geometry processing, distributed computing, large meshesAbstract
In order to facilitate 3D object processing, it is common to use high-level representations such as local descriptors that are usually computed using defined neighborhoods. K-rings, a technique to define them, is widely used by several methods. In this work, we propose a model for the distributed computation of local descriptors over 3D triangular meshes, using the concept of k-rings. In our experiments, we measure the performance of our model on huge meshes, evaluating the speedup, the scalability, and the descriptor computation time. We show the optimal configuration of our model for the cluster we implemented and the linear growth of computation time regarding the mesh size and the number of rings. We used the Harris response, which describes the saliency of the object, for our tests.
Downloads
References
Aleardi, L., Devillers, O., & Schaeffer, G. (2005). Succinct representation of triangulations with a boundary. In F. Dehne, A. López-Ortiz, & J.-R. Sack (Eds.), Algorithms and data structures. WADS 2005. Lecture Notes in Computer Science, vol 3608 (pp. 134-145). Springer. https://doi.org/10.1007/11534273_13
Areias, P., & Rabczuk, T. (2017). Steiner-point free edge cutting of tetrahedral meshes with applications in fracture. Finite Elements in Analysis and Design, 132, 27-41. https://doi.org/10.1016/j.finel.2017.05.001
Balman, M. (2006). Tetrahedral mesh refinement in distributed environments. In T. M. Pinkston & F. Ozguner (Eds.), Proceedings of the 2006 International Conference on Parallel Processing Workshops (ICPPW’06) (pp. 498-504). IEEE Computer Society. https://doi.org/10.1109/ICPPW.2006.72
Cabiddu, D., & Attene, M. (2015). Distributed processing of large polygon meshes. In A. Giachetti, S. Biasotti, & M. Tarini (Eds.), Smart tools and apps for graphics—Eurographics Italian chapter conference (pp. 139-148). The Eurographics Association. https://doi.org/10.2312/stag.20151301
Castellani, U., Cristani, M., Fantoni, S., & Murino, V. (2008). Sparse points matching by combining 3D mesh saliency with statistical descriptors. Computer Graphics Forum, 27(2), 643-652. https://doi.org/10.1111/j.1467-8659.2008.01162.x
Chen, X., Golovinskiy, A., & Funkhouser, T. (2009). A benchmark for 3D mesh segmentation. ACM TransActions on Graphics, 28(3), 1-12. https://doi.org/10.1145/1531326.1531379
Cignoni, P., Montani, C., Rocchini, C., & Scopigno, R. (2003). External memory management and simplification of huge meshes. IEEE Transactions on Visualization and Computer Graphics, 9(4), 525-537. https://doi.org/10.1109/TVCG.2003.1260746
Figueiredo, L., Ivson, P., & Celes, W. (2021). Deep learning-based framework for Shape Instance Registration on 3D CAD models. Computers & Graphics, 101, 72-81. https://doi.org/10.1016/j.cag.2021.08.012
Gao, L., Cao, Y.-P., Lai, Y.-K., Huang, H.-Z., Kobbelt, L., & Hu, S.-M. (2015). Active exploration of large 3D model repositories. IEEE Transactions on Visualization and Computer Graphics, 21(12), 1390-1402. https://doi.org/10.1109/TVCG.2014.2369039
Gelfand, N., Mitra, N. J., Guibas, L. J., & Pottmann, H. (2005). Robust global registration. In M. Desbrun & H. Pottmann (Eds), Europgraphics Symposium on Geometry Processing (pp. 197-206). Alvety Vision Club. http://vecg.cs.ucl.ac.uk/Projects/SmartGeometry/global_registration/paper_docs/global_registration_sgp_05.pdf
Gupta, O., & Rani, S. (2013). Accelerating molecular sequence analysis using distributed computing environment. International Journal of Scientific & Engineering Research–IJSER, 4(10), 262-265. https://www.ijser.org/onlineResearchPaperViewer.aspx?Accelerating-Molecular-Sequence-Analysis-using-Distributed Computing-Environment.pdf
Gurung, T., Laney, D., Lindstrom, P., & Rossignac, J. (2011). SQuad: Compact representation for triangle meshes. Computer Graphics Forum, 30(2), 355-364. https://doi.org/10.1111/j.1467-8659.2011.01866.x
Gurung, T., Luffel, M., Lindstrom, P., & Rossignac, J. (2013). Zipper: A compact connectivity data structure for triangle meshes. Computer-Aided Design, 45(2), 262-269. https://doi.org/10.1016/j.cad.2012.10.009
Harris, C., & Stephens, M. (1988). A combined corner and edge detector. In C. J. Taylor (Ed.), Proceedings of the Alvey Vision Conference (pp. 23.1-23.6). http://dx.doi.org/10.5244/C.2.23
Herath, U., Tavadze, P., He, X., Bousquet, E., Singh, S., Muñoz, F., & Romero, A. H. (2020). PyProcar: A Python library for electronic structure pre/post-processing. Computer Physics Communications, 251, 107080. https://doi.org/10.1016/j.cpc.2019.107080
Lee, C. H., Varshney, A., & Jacobs, D. W. (2005). Mesh saliency. ACM Transactions on Graphics, 24(3), 659-666. https://doi.org/10.1145/1186822.1073244
Le Tien, M., Tan, K. N., & Raffin, R. (2021, 15-16 December). Analysis of geometrical features of 3D model based on the surface curvature of a set of point cloud. In The 5th International Conference on Future Networks & Distributed Systems (pp. 17-23). The Association of Computing Machinery. https://doi.org/10.1145/3508072.3508076
Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., Shade, J., & Fulk, D. (2000). The digital Michelangelo project: 3D scanning of large statues. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (pp. 131-144). SIFFGRAPH. https://doi.org/10.1145/344779.344849
Li, B., Lu, Y., Li, C., Godil, A., Schreck, T., Aono, M., Burtscher, M., Chen, Q., Chowdhury, N. K., Fang, B., Fu, H., Furuya, T., Li, H., Liu, J., Johan, H., Kosaka, R., Koyanagi, H., Ohbuchi, R., Tatsuma, A., Wan, Y, Zhang, C., & Zou, C. (2015). A comparison of 3D shape retrieval methods based on a large-scale benchmark supporting multimodal queries. Computer Vision and Image Understanding, 131, 1-27. https://doi.org/10.1016/j.cviu.2014.10.006
Luffel, M., Gurung, T., Lindstrom, P., & Rossignac, J. (2014). Grouper: A Compact, Streamable Triangle Mesh Data Structure. IEEE Transactions on Visualization and Computer Graphics, 20(1), 84-98. https://doi.org/10.1109/TVCG.2013.81
Maquart, T., Elguedj, T., Gravouil, A., & Rochette, M. (2021). 3D B-Rep meshing for real-time data-based geometric parametric analysis. Advanced Modeling and Simulation in Engineering Sciences, 8, 8. https://doi.org/10.1186/s40323-021-00194-5
Mitra, N. J., Pauly, M., Wand, M., & Ceylan, D. (2013). Symmetry in 3D geometry: Extraction and applications. Computer Graphics Forum, 32(6), 1-23. https://doi.org/10.1111/cgf.12010
O’ Sullivan, E., Van de Lande, L. S., Papaioannou, A., Breakey, R. W. F., Jeelani, N. O., Ponniah, A., Duncan, C., Schievano, S., Khonsari, R. H., Zafeiriou, S., & Dunaway, D. J. (2022). Convolutional mesh autoencoders for the 3-dimensional identification of FGFR-related craniosynostosis. Scientific Reports, 12, 2230. https://doi.org/10.1038/s41598-021-02411-y
Pavlakos, G., Zhu, L., Zhou, X., & Daniilidis, K. (2018). Learning to estimate 3D human pose and shape from a single color image. In L. O’Conner (Ed.), Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 459-468). IEEE Computer Society; Conference Publishing Services. https://doi.org/10.1109/CVPR.2018.00055
Pereira, R., Azambuja, M., Breitman, K., & Endler, M. (2010). An architecture for distributed high performance video processing in the cloud. In R. Bilof (Ed,), Proceedings of the 2010 IEEE 3rd International Conference on Cloud Computing (pp. 482–489). IEEE Computer Society; Conference Publishing Services. https://doi.org/10.1109/CLOUD.2010.73
Prajapati, H. B., & Vij, S. K. (2011). Analytical study of parallel and distributed image processing. In R Siddavatam & S. P. Ghrera (Eds.), 2011 International Conference on Image Information Processing (pp. 1-6). The Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ICIIP.2011.6108870
Rocca, L., De Giorgis, N., Panozzo, D., & Puppo, E. (2011). Fast neighborhood search on polygonal meshes. In A. F. Abate, M. Nappi, & G. Tortora (Eds.). Eurographics Italian Chapter Conference 2011 (pp.15-21). The Eurographics Association. https://doi.org/10.2312/LocalChapterEvents/ItalChap/ItalianChapConf2011/015-021
Sankaranarayanan, J., Samet, H., & Varshney, A. (2007). A fast all nearest neighbor algorithm for applications involving large point-clouds. Computers & Graphics, 31(2), 157-174. https://doi.org/10.1016/j.cag.2006.11.011
Sipiran, I., & Bustos, B. (2011). Harris 3D: a robust extension of the Harris operator for interest point detection on 3D meshes. The Visual Computer, 27, 963. https://doi.org/10.1007/s00371-011-0610-y
Squyres, J. M., Lumsdaine, A., McCandless, B. C., & Stevenson, R. L. (2000). Parallel and distributed algorithms for high speed image processing. University of Notre Dame. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.939.2869&rep=rep1&type=pdf
Van Kaick, O., Zhang, H., Hamarneh, G., & Cohen-Or, D. (2011). A survey on shape correspondence. Computer Graphics Forum, 30(6), 1681-1707. https://doi.org/10.1111/j.1467-8659.2011.01884.x
Verma, N., Boyer, E., & Verbeek, J. (2018). FeaStNet: Feature-steered graph convolutions for 3d shape analysis. In L. O’Conner, (Ed.), Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 2598-2606). IEEE Computer Society; Conference Publishing Services. https://doi.org/10.1109/CVPR.2018.00275
Vo, H. T., Bronson, J., Summa, B., Comba, J. L. D., Freire, J., Howe, B., Pascucci, V., & Silva, C. T. (2011). Parallel visualization on large clusters using MapReduce. In D. Rogers & C. T. Silva. Proceedings of the 2011 IEEE Symposium on Large Data Analysis and Visualization (pp. 81-88). IEEE Computer Society Press. https://doi.org/10.1109/LDAV.2011.6092321
Warn, S., Emeneker, W., Cothren, J., & Apon, A. (2009, 31 de Agosto-4 de setiembre). Accelerating SIFT on parallel architectures [written presentation]. 2009 IEEE International Conference on Cluster Computing and Workshops, Nueva Orleans, Louisiana, USA.. https://doi.org/10.1109/CLUSTR.2009.5289155
Zaharescu, A., Boyer, E., Varanasi, K., & Horaud, R. (2009, 20-25 de junio). Surface feature detection and description with applications to mesh matching. [written presentation] 2009 IEEE Conference on Computer Vision and Pattern Recognition, Miami,Florida, Estados Unidos. https://doi.org/10.1109/CVPR.2009.5206748
Zamolo, R., Miotti, D., & Nobile, E. (2022). Numerical analysis of thermo-fluid problems in 3D domains by means of the RBF-FD meshless method. Journal of Physics: Conference Series, 2177, 012007. https://doi.org/10.1088/1742-6596/2177/1/012007
Zhou, R., Song, Z., & Lu, Y. (2017). 3D mesoscale finite element modelling of concrete. Computers & Structures, 192, 96–113. https://doi.org/10.1016/j.compstruc.2017.07.009
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under an Attribution 4.0 International (CC BY 4.0) License. that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Last updated 03/05/21
